Package org.apache.commons.collections4.trie

# Class KeyAnalyzer<K>

java.lang.Object
org.apache.commons.collections4.trie.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

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `static final int`
  `EQUAL_BIT_KEY`
  Returned by `bitIndex(Object, int, int, Object, int, int)` if key and found key are equal.
  `static final int`
  `NULL_BIT_KEY`
  Returned by `bitIndex(Object, int, int, Object, int, int)` if key's bits are all 0.
  `static final int`
  `OUT_OF_BOUNDS_BIT_KEY`
  Used to test a `bitIndex` in `isOutOfBoundsIndex(int)`.

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `KeyAnalyzer()`
  Constructs a new instance.

- ## Method Summary

  Modifier and Type
  Method
  Description
  `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.
  `abstract int`
  `bitsPerElement()`
  Returns the number of bits per element in the key.
  `int`
  `compare(K o1, K o2)`
  `abstract boolean`
  `isBitSet(K key, int bitIndex, int lengthInBits)`
  Returns whether or not a bit is set.
  `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.
  `abstract int`
  `lengthInBits(K key)`
  Returns the length of the Key in bits.

  ### Methods inherited from class java.lang.Object

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

  ### Methods inherited from interface java.util.Comparator

  `equals, reversed, thenComparing, thenComparing, thenComparing, thenComparingDouble, thenComparingInt, thenComparingLong`

- ## Field Details

  - ### NULL_BIT_KEY

    public static final int NULL_BIT_KEY
    Returned by `bitIndex(Object, int, int, Object, int, int)` if key's bits are all 0.
    See Also:
      - Constant Field Values

  - ### EQUAL_BIT_KEY

    public static final int EQUAL_BIT_KEY
    Returned by `bitIndex(Object, int, int, Object, int, int)` if key and found key are equal. This is a very specific case and shouldn't happen on a regular basis.
    See Also:
      - Constant Field Values

  - ### OUT_OF_BOUNDS_BIT_KEY

    public static final int OUT_OF_BOUNDS_BIT_KEY
    Used to test a `bitIndex` in `isOutOfBoundsIndex(int)`.
    See Also:
      - Constant Field Values

- ## Constructor Details

  - ### KeyAnalyzer

    public KeyAnalyzer()
    Constructs a new instance.

- ## Method Details

  - ### 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

  - ### 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

  - ### compare

    public int compare(K o1, K o2)
    Specified by:
      `compare` in interface `Comparator<K>`

  - ### 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.

  - ### 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

  - ### 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