Class KeyAnalyzer<K>

  • Type Parameters:
    K - the type of objects that may be compared by this analyzer
    All Implemented Interfaces:
    Serializable, Comparator<K>
    Direct Known Subclasses:
    StringKeyAnalyzer

    public abstract class KeyAnalyzer<K>
    extends Object
    implements Comparator<K>, Serializable
    Defines the interface to analyze Trie keys on a bit level. KeyAnalyzer's methods return the length of the key in bits, whether or not a bit is set, and bits per element in the key.

    Additionally, a method determines if a key is a prefix of another key and returns the bit index where one key is different from another key (if the key and found key are equal than the return value is EQUAL_BIT_KEY).

    Since:
    4.0
    See Also:
    Serialized Form
    • Constructor Detail

      • KeyAnalyzer

        public KeyAnalyzer()
    • Method Detail

      • bitsPerElement

        public abstract int bitsPerElement()
        Returns the number of bits per element in the key. This is only useful for variable-length keys, such as Strings.
        Returns:
        the number of bits per element
      • lengthInBits

        public abstract int lengthInBits​(K key)
        Returns the length of the Key in bits.
        Parameters:
        key - the key
        Returns:
        the bit length of the key
      • isBitSet

        public abstract boolean isBitSet​(K key,
                                         int bitIndex,
                                         int lengthInBits)
        Returns whether or not a bit is set.
        Parameters:
        key - the key to check, may not be null
        bitIndex - the bit index to check
        lengthInBits - the maximum key length in bits to check
        Returns:
        true if the bit is set in the given key and bitIndex < lengthInBits, false otherwise.
      • bitIndex

        public abstract int bitIndex​(K key,
                                     int offsetInBits,
                                     int lengthInBits,
                                     K other,
                                     int otherOffsetInBits,
                                     int otherLengthInBits)
        Returns the n-th different bit between key and other. This starts the comparison in key at 'offsetInBits' and goes for 'lengthInBits' bits, and compares to the other key starting at 'otherOffsetInBits' and going for 'otherLengthInBits' bits.
        Parameters:
        key - the key to use
        offsetInBits - the bit offset in the key
        lengthInBits - the maximum key length in bits to use
        other - the other key to use
        otherOffsetInBits - the bit offset in the other key
        otherLengthInBits - the maximum key length in bits for the other key
        Returns:
        the bit index where the key and other first differ
      • isPrefix

        public abstract boolean isPrefix​(K prefix,
                                         int offsetInBits,
                                         int lengthInBits,
                                         K key)
        Determines whether or not the given prefix (from offset to length) is a prefix of the given key.
        Parameters:
        prefix - the prefix to check
        offsetInBits - the bit offset in the key
        lengthInBits - the maximum key length in bits to use
        key - the key to check
        Returns:
        true if this is a valid prefix for the given key