Package gw.internal.gosu.util

Class RabinKarpHash

java.lang.Object

gw.internal.gosu.util.RabinKarpHash

public class RabinKarpHash
extends java.lang.Object

Fast multi-pattern string matcher. Quick and dirty implementation of Rabin-Karp algorithm. Used for paths matching. We mach patterns from the end to reduce amount of possible collisions (filesystem paths tend to have common prefixes, like package names, etc). FIXME: Tests...

See Also:

Rabin–Karp algorithm

Field Summary

Fields

Modifier and Type	Field	Description
private int	_Apowblock
private int	_block
private java.util.Set<java.lang.Integer>	_hashes
private java.lang.String[]	_patterns
private static int	A
private static int[]	CHAR_HASHES

Constructor Summary

Constructors

Constructor	Description
RabinKarpHash(java.lang.String... patterns)

Method Summary

Modifier and Type	Method	Description
private boolean	exactMatch(java.lang.String str, int i)	Check for exact match.
boolean	matches(java.lang.String str)
private static int	minLen(java.lang.String... patterns)	Find the shortest of all patterns.
private int	reverseHash(java.lang.String str)	Take rolling hash of last 'block' characters.
private int	rollHash(int hashvalue, java.lang.String str, int i)	Update rolling hash values.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

A

private static final int A

See Also:

Constant Field Values

_block

private final int _block

_Apowblock

private final int _Apowblock

_hashes

private java.util.Set<java.lang.Integer> _hashes

_patterns

private java.lang.String[] _patterns

CHAR_HASHES

private static int[] CHAR_HASHES

Constructor Detail

RabinKarpHash

public RabinKarpHash(java.lang.String... patterns)

Method Detail

minLen

private static int minLen(java.lang.String... patterns)

Find the shortest of all patterns.

Parameters:

patterns -

Returns:

matches

public boolean matches(java.lang.String str)

exactMatch

private boolean exactMatch(java.lang.String str,
                           int i)

Check for exact match. FIXME:

Parameters:

str -

i -

Returns:

rollHash

private int rollHash(int hashvalue,
                     java.lang.String str,
                     int i)

Update rolling hash values.

Parameters:

hashvalue -

str -

i -

Returns:

reverseHash

private int reverseHash(java.lang.String str)

Take rolling hash of last 'block' characters. Start from the end of the string.

Parameters:

str -

Returns: