Class RabinKarpHash

java.lang.Object
gw.internal.gosu.util.RabinKarpHash

public class RabinKarpHash extends 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:
  • Field Details

    • A

      private static final int A
      See Also:
    • _block

      private final int _block
    • _Apowblock

      private final int _Apowblock
    • _hashes

      private Set<Integer> _hashes
    • _patterns

      private String[] _patterns
    • CHAR_HASHES

      private static int[] CHAR_HASHES
  • Constructor Details

    • RabinKarpHash

      public RabinKarpHash(String... patterns)
  • Method Details

    • minLen

      private static int minLen(String... patterns)
      Find the shortest of all patterns.
      Parameters:
      patterns -
      Returns:
    • matches

      public boolean matches(String str)
    • exactMatch

      private boolean exactMatch(String str, int i)
      Check for exact match. FIXME:
      Parameters:
      str -
      i -
      Returns:
    • rollHash

      private int rollHash(int hashvalue, String str, int i)
      Update rolling hash values.
      Parameters:
      hashvalue -
      str -
      i -
      Returns:
    • reverseHash

      private int reverseHash(String str)
      Take rolling hash of last 'block' characters. Start from the end of the string.
      Parameters:
      str -
      Returns: