org.apache.commons.collections4.trie

Class KeyAnalyzer<K>

java.lang.Object

org.apache.commons.collections4.trie.KeyAnalyzer<K>

All Implemented Interfaces:

java.io.Serializable, java.util.Comparator<K>

Direct Known Subclasses:

StringKeyAnalyzer

public abstract class KeyAnalyzer<K>
extends java.lang.Object
implements java.util.Comparator<K>, java.io.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 and Description
static int	EQUAL_BIT_KEY Returned by bitIndex(Object, int, int, Object, int, int) if key and found key are equal.
static int	NULL_BIT_KEY Returned by bitIndex(Object, int, int, Object, int, int) if key's bits are all 0.
static int	OUT_OF_BOUNDS_BIT_KEY

Constructor Summary

Constructors

Constructor and Description
KeyAnalyzer()

Method Summary

Modifier and Type	Method and 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

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

Methods inherited from interface java.util.Comparator

comparing, comparing, comparingDouble, comparingInt, comparingLong, equals, naturalOrder, nullsFirst, nullsLast, reversed, reverseOrder, thenComparing, thenComparing, thenComparing, thenComparingDouble, thenComparingInt, thenComparingLong

Field Detail

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

See Also:

Constant Field Values

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

compare

public int compare(K o1,
                   K o2)

Specified by:

compare in interface java.util.Comparator<K>