edu.wisc.ssec.mcidasv.util.trie

Interface PatriciaTrie.KeyAnalyzer<K>

All Superinterfaces:

Comparator<K>, Serializable

All Known Implementing Classes:

AddeEntryKeyAnalyzer, CharSequenceKeyAnalyzer, StringListKeyAnalyzer

Enclosing class:

PatriciaTrie<K,V>

public static interface PatriciaTrie.KeyAnalyzer<K>
extends 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).

KeyAnalyzer defines:

NULL_BIT_KEY	When key's bits are all zero
EQUAL_BIT_KEY	When keys are the same

Field Summary

Fields

Modifier and Type	Field and Description
static int	EQUAL_BIT_KEY Returned by bitIndex if key and found key are equal.
static int	NULL_BIT_KEY Returned by bitIndex if key's bits are all 0

Method Summary

Modifier and Type	Method and Description
int	bitIndex(K key, int keyStart, int keyLength, K found, int foundStart, int foundLength) Returns the n-th different bit between key and found.
int	bitsPerElement() Returns the number of bits per element in the key.
boolean	isBitSet(K key, int keyLength, int bitIndex) Returns whether or not a bit is set
boolean	isPrefix(K prefix, int offset, int length, K key) Determines whether or not the given prefix (from offset to length) is a prefix of the given key.
int	length(K key) Returns the length of the Key in bits.

Methods inherited from interface java.util.Comparator

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

Field Detail

NULL_BIT_KEY

static final int NULL_BIT_KEY

Returned by bitIndex if key's bits are all 0

See Also:

Constant Field Values

EQUAL_BIT_KEY

static final int EQUAL_BIT_KEY

Returned by bitIndex 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

Method Detail

length

int length(K key)

Returns the length of the Key in bits.

Parameters:

key - Key whose length should be computed.

Returns:

Length of key.

isBitSet

boolean isBitSet(K key,
                 int keyLength,
                 int bitIndex)

Returns whether or not a bit is set

Parameters:

key -

keyLength -

bitIndex -

bitIndex

int bitIndex(K key,
             int keyStart,
             int keyLength,
             K found,
             int foundStart,
             int foundLength)

Returns the n-th different bit between key and found. This starts the comparison in key at 'keyStart' and goes for 'keyLength' bits, and compares to the found key starting at 'foundStart' and going for 'foundLength' bits.

Parameters:

key -

keyStart -

keyLength -

found -

foundStart -

foundLength -

Returns:

bitsPerElement

int bitsPerElement()

Returns the number of bits per element in the key. This is only useful for variable-length keys, such as Strings.

Returns:

Bits per key element.

isPrefix

boolean isPrefix(K prefix,
                 int offset,
                 int length,
                 K key)

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

Returns:

true if prefix matches the given offset start and length for key.