Top Description Fields Constructors Methods
org.apache.commons.collections4.trie

public abstract Class KeyAnalyzer<K>

extends Object
implements Comparator<K>, Serializable
Class Inheritance
All Implemented Interfaces
java.io.Serializable, java.util.Comparator
Known Direct Subclasses
org.apache.commons.collections4.trie.analyzer.StringKeyAnalyzer
Type Parameters
<K>
the type of objects that may be compared by this analyzer
Imports
java.io.Serializable, java.util.Comparator
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

Field Summary

Modifier and TypeField and Description
public static final int
EQUAL_BIT_KEY

Returned by bitIndex(Object, int, int, Object, int, int) if key and found key are equal.

public static final int
NULL_BIT_KEY

Returned by bitIndex(Object, int, int, Object, int, int) if key's bits are all 0.

public static final int
OUT_OF_BOUNDS_BIT_KEY

private static final long
serialVersionUID

Serialization version

Constructor Summary

AccessConstructor and Description
public
KeyAnalyzer()

Method Summary

Modifier and TypeMethod and Description
public abstract int

Returns:

the bit index where the key and other first differ
bitIndex(K
the key to use
key, int
the bit offset in the key
offsetInBits, int
the maximum key length in bits to use
lengthInBits, K
the other key to use
other, int
the bit offset in the other key
otherOffsetInBits, int
the maximum key length in bits for the other key
otherLengthInBits)

Returns the n-th different bit between key and other.

public abstract int

Returns:

the number of bits per element
bitsPerElement()

Returns the number of bits per element in the key.

public int
compare(final K
the first object to be compared.
o1, final K
the second object to be compared.
o2)

Implements java.util.Comparator.compare.

Compares its two arguments for order.
public abstract boolean

Returns:

true if the bit is set in the given key and bitIndex < lengthInBits, false otherwise.
isBitSet(K
the key to check, may not be null
key, int
the bit index to check
bitIndex, int
the maximum key length in bits to check
lengthInBits)

Returns whether or not a bit is set.

pack-priv static boolean
isEqualBitKey(final int bitIndex)

Returns true if bitIndex is a KeyAnalyzer#EQUAL_BIT_KEY.

pack-priv static boolean
isNullBitKey(final int bitIndex)

Returns true if bitIndex is a KeyAnalyzer#NULL_BIT_KEY.

pack-priv static boolean
isOutOfBoundsIndex(final int bitIndex)

Returns true if bitIndex is a KeyAnalyzer#OUT_OF_BOUNDS_BIT_KEY.

public abstract boolean

Returns:

true if this is a valid prefix for the given key
isPrefix(K
the prefix to check
prefix, int
the bit offset in the key
offsetInBits, int
the maximum key length in bits to use
lengthInBits, K
the key to check
key)

Determines whether or not the given prefix (from offset to length) is a prefix of the given key.

pack-priv static boolean
isValidBitIndex(final int bitIndex)

Returns true if the given bitIndex is valid.

public abstract int

Returns:

the bit length of the key
lengthInBits(K
the key
key)

Returns the length of the Key in bits.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

EQUAL_BIT_KEYback to summary
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.

NULL_BIT_KEYback to summary
public static final int NULL_BIT_KEY

Returned by bitIndex(Object, int, int, Object, int, int) if key's bits are all 0.

OUT_OF_BOUNDS_BIT_KEYback to summary
public static final int OUT_OF_BOUNDS_BIT_KEY
serialVersionUIDback to summary
private static final long serialVersionUID

Serialization version

Constructor Detail

KeyAnalyzerback to summary
public KeyAnalyzer()

Method Detail

bitIndexback to summary
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:K

the key to use

offsetInBits:int

the bit offset in the key

lengthInBits:int

the maximum key length in bits to use

other:K

the other key to use

otherOffsetInBits:int

the bit offset in the other key

otherLengthInBits:int

the maximum key length in bits for the other key

Returns:int

the bit index where the key and other first differ

bitsPerElementback to summary
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:int

the number of bits per element

compareback to summary
public int compare(final K o1, final K o2)

Implements java.util.Comparator.compare.

Doc from java.util.Comparator.compare.

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

The implementor must ensure that signum(compare(x, y)) == -signum(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

Finally, the implementor must ensure that compare(x, y)==0 implies that signum(compare(x, z))==signum(compare(y, z)) for all z.

Parameters
o1:K

the first object to be compared.

o2:K

the second object to be compared.

Returns:int

a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

Annotations
@Override
@SuppressWarnings:unchecked
isBitSetback to summary
public abstract boolean isBitSet(K key, int bitIndex, int lengthInBits)

Returns whether or not a bit is set.

Parameters
key:K

the key to check, may not be null

bitIndex:int

the bit index to check

lengthInBits:int

the maximum key length in bits to check

Returns:boolean

true if the bit is set in the given key and bitIndex < lengthInBits, false otherwise.

isEqualBitKeyback to summary
pack-priv static boolean isEqualBitKey(final int bitIndex)

Returns true if bitIndex is a KeyAnalyzer#EQUAL_BIT_KEY.

isNullBitKeyback to summary
pack-priv static boolean isNullBitKey(final int bitIndex)

Returns true if bitIndex is a KeyAnalyzer#NULL_BIT_KEY.

isOutOfBoundsIndexback to summary
pack-priv static boolean isOutOfBoundsIndex(final int bitIndex)

Returns true if bitIndex is a KeyAnalyzer#OUT_OF_BOUNDS_BIT_KEY.

isPrefixback to summary
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:K

the prefix to check

offsetInBits:int

the bit offset in the key

lengthInBits:int

the maximum key length in bits to use

key:K

the key to check

Returns:boolean

true if this is a valid prefix for the given key

isValidBitIndexback to summary
pack-priv static boolean isValidBitIndex(final int bitIndex)

Returns true if the given bitIndex is valid. Indices are considered valid if they're between 0 and Integer#MAX_VALUE

lengthInBitsback to summary
public abstract int lengthInBits(K key)

Returns the length of the Key in bits.

Parameters
key:K

the key

Returns:int

the bit length of the key