edu.wisc.ssec.mcidasv.util.trie

Class PatriciaTrie<K,V>

java.lang.Object

java.util.AbstractMap<K,V>

edu.wisc.ssec.mcidasv.util.trie.PatriciaTrie<K,V>

All Implemented Interfaces:

Trie<K,V>, Serializable, Map<K,V>, SortedMap<K,V>

public class PatriciaTrie<K,V>
extends AbstractMap<K,V>
implements Trie<K,V>, Serializable

A PATRICIA Trie.

PATRICIA = Practical Algorithm to Retrieve Information Coded in Alphanumeric

A PATRICIA Trie is a compressed Trie. Instead of storing all data at the edges of the Trie (and having empty internal nodes), PATRICIA stores data in every node. This allows for very efficient traversal, insert, delete, predecessor, successor, prefix, range, and 'select' operations. All operations are performed at worst in O(K) time, where K is the number of bits in the largest item in the tree. In practice, operations actually take O(A(K)) time, where A(K) is the average number of bits of all items in the tree.

Most importantly, PATRICIA requires very few comparisons to keys while doing any operation. While performing a lookup, each comparison (at most K of them, described above) will perform a single bit comparison against the given key, instead of comparing the entire key to another key.

The Trie can return operations in lexicographical order using the 'traverse', 'prefix', 'submap', or 'iterator' methods. The Trie can also scan for items that are 'bitwise' (using an XOR metric) by the 'select' method. Bitwise closeness is determined by the PatriciaTrie.KeyAnalyzer returning true or false for a bit being set or not in a given key.

This PATRICIA Trie supports both variable length & fixed length keys. Some methods, such as getPrefixedBy(...) are suited only to variable length keys, whereas getPrefixedByBits(...) is suited to fixed-size keys.

Additionally see PATRICIA for more information.

Any methods here that take an Object may throw a ClassCastException if the method is expecting an instance of K (and it isn't K).

    PatriciaTrie<String, String> trie = new PatriciaTrie<String, String>
    (new CharSequenceKeyAnalyzer());

    trie.put("Lime", "Lime");
    trie.put("LimeWire", "LimeWire");
    trie.put("LimeRadio", "LimeRadio");
    trie.put("Lax", "Lax");
    trie.put("Lake", "Lake");
    trie.put("Lovely", "Lovely");

    System.out.println(trie.select("Lo"));
    System.out.println(trie.select("Lime"));

    System.out.println(trie.getPrefixedBy("La").toString());            

    Output:
        Lovely
        Lime
        {Lake=Lake, Lax=Lax}

 

Author:

Roger Kapsi, Sam Berlin

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	PatriciaTrie.EmptyIterator
private class	PatriciaTrie.EntryIterator
private class	PatriciaTrie.EntrySet
static interface	PatriciaTrie.KeyAnalyzer<K> Defines the interface to analyze Trie keys on a bit level.
private class	PatriciaTrie.KeyIterator
private class	PatriciaTrie.KeySet
private class	PatriciaTrie.NodeIterator<E> An iterator for the entries.
private class	PatriciaTrie.PrefixEntryIterator An iterator for iterating over a prefix search.
private class	PatriciaTrie.PrefixSubMap A submap used for prefix views over the Trie.
private class	PatriciaTrie.SingletonIterator An iterator that stores a single TrieEntry.
private class	PatriciaTrie.SubMap
private class	PatriciaTrie.SubMapEntryIterator An iterator for submaps.
private static class	PatriciaTrie.TrieEntry<K,V> The actual Trie nodes.
private class	PatriciaTrie.ValueIterator
private class	PatriciaTrie.Values

Nested classes/interfaces inherited from class java.util.AbstractMap

AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>

Nested classes/interfaces inherited from interface edu.wisc.ssec.mcidasv.util.trie.Trie

Trie.Cursor<K,V>

Nested classes/interfaces inherited from interface java.util.Map

Map.Entry<K,V>

Field Summary

Fields

Modifier and Type	Field and Description
private Set<Map.Entry<K,V>>	entrySet
private PatriciaTrie.KeyAnalyzer<? super K>	keyAnalyzer The keyAnalyzer used to analyze bit values of keys.
private Set<K>	keySet Each of these fields are initialized to contain an instance of the appropriate view the first time this view is requested.
private int	modCount The number of times this has been modified (to fail-fast the iterators).
private PatriciaTrie.TrieEntry<K,V>	root The root element of the Trie.
private static long	serialVersionUID
private int	size The current size (total number of elements) of the Trie.
private Collection<V>	values

Constructor Summary

Constructors

Constructor and Description
PatriciaTrie(PatriciaTrie.KeyAnalyzer<? super K> keyAnalyzer) Constructs a new PatriciaTrie using the given keyAnalyzer.

Method Summary

Methods

Modifier and Type	Method and Description
private PatriciaTrie.TrieEntry<K,V>	addEntry(PatriciaTrie.TrieEntry<K,V> toAdd, int keyLength) Adds the given entry into the Trie.
protected K	asKey(Object key) Gets the key as a 'K'.
private int	bitIndex(K key, K foundKey) Utility method for calling keyAnalyzer.bitIndex(key, 0, length(key), foundKey, 0, length(foundKey))
protected PatriciaTrie.TrieEntry<K,V>	ceilingEntry(K key) Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.
void	clear() Clears the Trie (i.e. removes all elements).
Comparator<? super K>	comparator() Returns the KeyAnalyzer as a comparator.
boolean	containsKey(Object k) Returns true if this trie contains the specified Key This may throw ClassCastException if the object is not of type K.
boolean	containsValue(Object o) Returns true if this Trie contains the specified value.
private void	decrementSize() Decrements the size and increments the mod counter.
Set<Map.Entry<K,V>>	entrySet()
private PatriciaTrie.TrieEntry<K,V>	firstEntry() Returns the first entry the Trie is storing.
K	firstKey()
protected PatriciaTrie.TrieEntry<K,V>	floorEntry(K key) Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.
private PatriciaTrie.TrieEntry<K,V>	followLeft(PatriciaTrie.TrieEntry<K,V> node) Goes left through the tree until it finds a valid node.
protected PatriciaTrie.TrieEntry<K,V>	followRight(PatriciaTrie.TrieEntry<K,V> node) Traverses down the right path until it finds an uplink.
V	get(Object k) Returns the Value whose Key equals our lookup Key or null if no such key exists.
(package private) PatriciaTrie.TrieEntry<K,V>	getEntry(Object k) Returns the entry associated with the specified key in the PatriciaTrie.
PatriciaTrie.KeyAnalyzer<? super K>	getKeyAnalyzer() Returns the KeyAnalyzer that constructed the trie.
private PatriciaTrie.TrieEntry<K,V>	getNearestEntryForKey(K key, int keyLength) Returns the nearest entry for a given key.
SortedMap<K,V>	getPrefixedBy(K key) Returns a view of this Trie of all elements that are prefixed by the given key.
SortedMap<K,V>	getPrefixedBy(K key, int length) Returns a view of this Trie of all elements that are prefixed by the length of the key.
SortedMap<K,V>	getPrefixedBy(K key, int offset, int length) Returns a view of this Trie of all elements that are prefixed by the key, starting at the given offset and for the given length.
SortedMap<K,V>	getPrefixedByBits(K key, int bitLength) Returns a view of this Trie of all elements that are prefixed by the number of bits in the given Key.
private SortedMap<K,V>	getPrefixedByBits(K key, int offset, int length) Returns a view of this map, with entries containing only those that are prefixed by a value whose bits matches the bits between 'offset' and 'length' in the given key.
SortedMap<K,V>	headMap(K toKey)
protected PatriciaTrie.TrieEntry<K,V>	higherEntry(K key) Returns an entry strictly higher than the given key, or null if no such entry exists.
private void	incrementModCount() Increments the mod counter.
private void	incrementSize() Increments both the size and mod counter.
private boolean	isBitSet(K key, int keyLength, int bitIndex) Returns whether or not the given bit on the key is set, or false if the key is null
boolean	isEmpty() Returns true if the Trie is empty
private static boolean	isEqualBitKey(int bitIndex) Returns true if bitIndex is a EQUAL_BIT_KEY
private static boolean	isNullBitKey(int bitIndex) Returns true if bitIndex is a NULL_BIT_KEY
private static boolean	isValidBitIndex(int bitIndex) Returns true if bitIndex is a valid index
private boolean	isValidUplink(PatriciaTrie.TrieEntry<K,V> next, PatriciaTrie.TrieEntry<K,V> from) Returns true if 'next' is a valid uplink coming from 'from'.
Set<K>	keySet() Returns a set view of the keys contained in this map.
private PatriciaTrie.TrieEntry<K,V>	lastEntry() Returns the last entry the Trie is storing.
K	lastKey()
private int	length(K key) Returns the length of the key, or 0 if the key is null.
protected PatriciaTrie.TrieEntry<K,V>	lowerEntry(K key) Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.
(package private) Iterator<Map.Entry<K,V>>	newEntryIterator()
(package private) Iterator<K>	newKeyIterator()
(package private) Iterator<V>	newValueIterator()
private PatriciaTrie.TrieEntry<K,V>	nextEntry(PatriciaTrie.TrieEntry<K,V> node) Returns the entry lexicographically after the given entry.
private PatriciaTrie.TrieEntry<K,V>	nextEntryImpl(PatriciaTrie.TrieEntry<K,V> start, PatriciaTrie.TrieEntry<K,V> previous, PatriciaTrie.TrieEntry<K,V> tree) Scans for the next node, starting at the specified point, and using 'previous' as a hint that the last node we returned was 'previous' (so we know not to return it again).
private PatriciaTrie.TrieEntry<K,V>	nextEntryInSubtree(PatriciaTrie.TrieEntry<K,V> node, PatriciaTrie.TrieEntry<K,V> parentOfSubtree) Returns the entry lexicographically after the given entry.
private PatriciaTrie.TrieEntry<K,V>	previousEntry(PatriciaTrie.TrieEntry<K,V> start) Returns the node lexicographically before the given node (or null if none).
V	put(K key, V value) Adds a new pair to the Trie and if a pair already exists it will be replaced.
V	remove(Object k) Removes a Key from the Trie if one exists This may throw ClassCastException if the object is not of type K.
private V	removeEntry(PatriciaTrie.TrieEntry<K,V> h) Removes a single entry from the Trie.
private void	removeExternalEntry(PatriciaTrie.TrieEntry<K,V> h) Removes an external entry from the Trie.
private void	removeInternalEntry(PatriciaTrie.TrieEntry<K,V> h) Removes an internal entry from the Trie.
V	select(K key) Returns the Value whose Key has the longest prefix in common with our lookup key.
Map.Entry<K,V>	select(K key, Trie.Cursor<? super K,? super V> cursor) Iterates through the Trie, starting with the entry whose bitwise value is closest in an XOR metric to the given key.
private boolean	selectR(PatriciaTrie.TrieEntry<K,V> h, int bitIndex, K key, int keyLength, PatriciaTrie.TrieEntry[] result) This is equivalent to the other selectR() method but without its overhead because we're selecting only one best matching Entry from the Trie.
private boolean	selectR(PatriciaTrie.TrieEntry<K,V> h, int bitIndex, K key, int keyLength, Trie.Cursor<? super K,? super V> cursor, PatriciaTrie.TrieEntry[] result)
int	size() Returns the number items in the Trie
SortedMap<K,V>	subMap(K fromKey, K toKey)
private PatriciaTrie.TrieEntry<K,V>	subtree(K prefix, int offset, int length) Finds the subtree that contains the prefix.
SortedMap<K,V>	tailMap(K fromKey)
String	toString() Returns each entry as a string.
Map.Entry<K,V>	traverse(Trie.Cursor<? super K,? super V> cursor) Traverses the Trie in lexicographical order.
private static boolean	valEquals(Object o1, Object o2) Test two values for equality.
Collection<V>	values() Returns a collection view of the values contained in this map.

Methods inherited from class java.util.AbstractMap

clone, equals, hashCode, putAll

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map

equals, hashCode, putAll

Field Detail

serialVersionUID

private static final long serialVersionUID

See Also:

Constant Field Values

root

private final PatriciaTrie.TrieEntry<K,V> root

The root element of the Trie.

size

private int size

The current size (total number of elements) of the Trie.

modCount

private transient int modCount

The number of times this has been modified (to fail-fast the iterators).

keyAnalyzer

private final PatriciaTrie.KeyAnalyzer<? super K> keyAnalyzer

The keyAnalyzer used to analyze bit values of keys.

keySet

private transient volatile Set<K> keySet

Each of these fields are initialized to contain an instance of the appropriate view the first time this view is requested. The views are stateless, so there's no reason to create more than one of each.

values

private transient volatile Collection<V> values

entrySet

private transient volatile Set<Map.Entry<K,V>> entrySet

Constructor Detail

PatriciaTrie

public PatriciaTrie(PatriciaTrie.KeyAnalyzer<? super K> keyAnalyzer)

Constructs a new PatriciaTrie using the given keyAnalyzer.

Method Detail

getKeyAnalyzer

public PatriciaTrie.KeyAnalyzer<? super K> getKeyAnalyzer()

Returns the KeyAnalyzer that constructed the trie.

comparator

public Comparator<? super K> comparator()

Returns the KeyAnalyzer as a comparator.

Specified by:

comparator in interface SortedMap<K,V>

clear

public void clear()

Clears the Trie (i.e. removes all elements).

Specified by:

clear in interface Map<K,V>

Overrides:

clear in class AbstractMap<K,V>

isEmpty

public boolean isEmpty()

Returns true if the Trie is empty

Specified by:

isEmpty in interface Map<K,V>

Overrides:

isEmpty in class AbstractMap<K,V>

size

public int size()

Returns the number items in the Trie

Specified by:

size in interface Map<K,V>

Overrides:

size in class AbstractMap<K,V>

incrementSize

private void incrementSize()

Increments both the size and mod counter.

decrementSize

private void decrementSize()

Decrements the size and increments the mod counter.

incrementModCount

private void incrementModCount()

Increments the mod counter.

put

public V put(K key,
    V value)

Adds a new pair to the Trie and if a pair already exists it will be replaced. In the latter case it will return the old value.

Specified by:

put in interface Map<K,V>

Overrides:

put in class AbstractMap<K,V>

addEntry

private PatriciaTrie.TrieEntry<K,V> addEntry(PatriciaTrie.TrieEntry<K,V> toAdd,
                                   int keyLength)

Adds the given entry into the Trie.

entrySet

public Set<Map.Entry<K,V>> entrySet()

Specified by:

entrySet in interface Map<K,V>

Specified by:

entrySet in interface SortedMap<K,V>

Specified by:

entrySet in class AbstractMap<K,V>

get

public V get(Object k)

Returns the Value whose Key equals our lookup Key or null if no such key exists.

Specified by:

get in interface Map<K,V>

Overrides:

get in class AbstractMap<K,V>

getEntry

PatriciaTrie.TrieEntry<K,V> getEntry(Object k)

Returns the entry associated with the specified key in the PatriciaTrie. Returns null if the map contains no mapping for this key. This may throw ClassCastException if the object is not of type K.

asKey

protected final K asKey(Object key)

Gets the key as a 'K'.

getNearestEntryForKey

private PatriciaTrie.TrieEntry<K,V> getNearestEntryForKey(K key,
                                                int keyLength)

Returns the nearest entry for a given key. This is useful for finding knowing if a given key exists (and finding the value for it), or for inserting the key. The actual get implementation. This is very similar to selectR but with the exception that it might return the root Entry even if it's empty.

select

public V select(K key)

Returns the Value whose Key has the longest prefix in common with our lookup key.

Specified by:

select in interface Trie<K,V>

selectR

private boolean selectR(PatriciaTrie.TrieEntry<K,V> h,
              int bitIndex,
              K key,
              int keyLength,
              PatriciaTrie.TrieEntry[] result)

This is equivalent to the other selectR() method but without its overhead because we're selecting only one best matching Entry from the Trie.

select

public Map.Entry<K,V> select(K key,
                    Trie.Cursor<? super K,? super V> cursor)

Description copied from interface: Trie

Iterates through the Trie, starting with the entry whose bitwise value is closest in an XOR metric to the given key. After the closest entry is found, the Trie will call select on that entry and continue calling select for each entry (traversing in order of XOR closeness, NOT lexicographically) until the cursor returns Cursor.SelectStatus.EXIT.
The cursor can return Cursor.SelectStatus.CONTINUE to continue traversing.
Cursor.SelectStatus.REMOVE_AND_EXIT is used to remove the current element and stop traversing.

Note: The Trie.Cursor.SelectStatus.REMOVE operation is not supported.

Specified by:

select in interface Trie<K,V>

Returns:

The entry the cursor returned EXIT on, or null if it continued till the end.

selectR

private boolean selectR(PatriciaTrie.TrieEntry<K,V> h,
              int bitIndex,
              K key,
              int keyLength,
              Trie.Cursor<? super K,? super V> cursor,
              PatriciaTrie.TrieEntry[] result)

getPrefixedBy

public SortedMap<K,V> getPrefixedBy(K key)

Returns a view of this Trie of all elements that are prefixed by the given key. In a fixed-keysize Trie, this is essentially a 'get' operation. For example, if the trie contains 'Lime', 'LimeWire', 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then a lookup of 'Lime' would return 'Lime', 'LimeRadio', and 'LimeWire'. The view that this returns is optimized to have a very efficient Iterator. The firstKey, lastKey & size methods must iterate over all possible values in order to determine the results. This information is cached until the Patricia tree changes. All other methods (except Iterator) must compare the given key to the prefix to ensure that it is within the range of the view. The Iterator's remove method must also relocate the subtree that contains the prefixes if the entry holding the subtree is removed or changes. Changing the subtree takes O(K) time.

Specified by:

getPrefixedBy in interface Trie<K,V>

Parameters:

key -

getPrefixedBy

public SortedMap<K,V> getPrefixedBy(K key,
                           int length)

Returns a view of this Trie of all elements that are prefixed by the length of the key. Fixed-keysize Tries will not support this operation (because all keys will be the same length). For example, if the trie contains 'Lime', 'LimeWire', 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then a lookup of 'LimePlastics' with a length of 4 would return 'Lime', 'LimeRadio', and 'LimeWire'. The view that this returns is optimized to have a very efficient Iterator. The firstKey, lastKey & size methods must iterate over all possible values in order to determine the results. This information is cached until the Patricia tree changes. All other methods (except Iterator) must compare the given key to the prefix to ensure that it is within the range of the view. The Iterator's remove method must also relocate the subtree that contains the prefixes if the entry holding the subtree is removed or changes. Changing the subtree takes O(K) time.

Specified by:

getPrefixedBy in interface Trie<K,V>

Parameters:

key -

length -

getPrefixedBy

public SortedMap<K,V> getPrefixedBy(K key,
                           int offset,
                           int length)

Returns a view of this Trie of all elements that are prefixed by the key, starting at the given offset and for the given length. Fixed-keysize Tries will not support this operation (because all keys are the same length). For example, if the trie contains 'Lime', 'LimeWire', 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then a lookup of 'The Lime Plastics' with an offset of 4 and a length of 4 would return 'Lime', 'LimeRadio', and 'LimeWire'. The view that this returns is optimized to have a very efficient Iterator. The firstKey, lastKey & size methods must iterate over all possible values in order to determine the results. This information is cached until the Patricia tree changes. All other methods (except Iterator) must compare the given key to the prefix to ensure that it is within the range of the view. The Iterator's remove method must also relocate the subtree that contains the prefixes if the entry holding the subtree is removed or changes. Changing the subtree takes O(K) time.

Specified by:

getPrefixedBy in interface Trie<K,V>

Parameters:

key -

offset -

length -

getPrefixedByBits

public SortedMap<K,V> getPrefixedByBits(K key,
                               int bitLength)

Returns a view of this Trie of all elements that are prefixed by the number of bits in the given Key. Fixed-keysize Tries can support this operation as a way to do lookups of partial keys. That is, if the Trie is storing IP addresses, you can lookup all addresses that begin with '192.168' by providing the key '192.168.X.X' and a length of 16 would return all addresses that begin with '192.168'. The view that this returns is optimized to have a very efficient Iterator. The firstKey, lastKey & size methods must iterate over all possible values in order to determine the results. This information is cached until the Patricia tree changes. All other methods (except Iterator) must compare the given key to the prefix to ensure that it is within the range of the view. The Iterator's remove method must also relocate the subtree that contains the prefixes if the entry holding the subtree is removed or changes. Changing the subtree takes O(K) time.

Specified by:

getPrefixedByBits in interface Trie<K,V>

Parameters:

key -

bitLength -

getPrefixedByBits

private SortedMap<K,V> getPrefixedByBits(K key,
                               int offset,
                               int length)

Returns a view of this map, with entries containing only those that are prefixed by a value whose bits matches the bits between 'offset' and 'length' in the given key. The view that this returns is optimized to have a very efficient Iterator. The firstKey, lastKey & size methods must iterate over all possible values in order to determine the results. This information is cached until the Patricia tree changes. All other methods (except Iterator) must compare the given key to the prefix to ensure that it is within the range of the view. The Iterator's remove method must also relocate the subtree that contains the prefixes if the entry holding the subtree is removed or changes. Changing the subtree takes O(K) time.

Parameters:

key -

offset -

length -

containsKey

public boolean containsKey(Object k)

Returns true if this trie contains the specified Key This may throw ClassCastException if the object is not of type K.

Specified by:

containsKey in interface Map<K,V>

Overrides:

containsKey in class AbstractMap<K,V>

containsValue

public boolean containsValue(Object o)

Returns true if this Trie contains the specified value.

Specified by:

containsValue in interface Map<K,V>

Overrides:

containsValue in class AbstractMap<K,V>

remove

public V remove(Object k)

Removes a Key from the Trie if one exists This may throw ClassCastException if the object is not of type K.

Specified by:

remove in interface Map<K,V>

Overrides:

remove in class AbstractMap<K,V>

Parameters:

k - the Key to delete

Returns:

Returns the deleted Value

removeEntry

private V removeEntry(PatriciaTrie.TrieEntry<K,V> h)

Removes a single entry from the Trie. If we found a Key (Entry h) then figure out if it's an internal (hard to remove) or external Entry (easy to remove)

removeExternalEntry

private void removeExternalEntry(PatriciaTrie.TrieEntry<K,V> h)

Removes an external entry from the Trie. If it's an external Entry then just remove it. This is very easy and straight forward.

removeInternalEntry

private void removeInternalEntry(PatriciaTrie.TrieEntry<K,V> h)

Removes an internal entry from the Trie. If it's an internal Entry then "good luck" with understanding this code. The Idea is essentially that Entry p takes Entry h's place in the trie which requires some re-wiring.

previousEntry

private PatriciaTrie.TrieEntry<K,V> previousEntry(PatriciaTrie.TrieEntry<K,V> start)

Returns the node lexicographically before the given node (or null if none). This follows four simple branches: - If the uplink that returned us was a right uplink: - If predecessor's left is a valid uplink from predecessor, return it. - Else, follow the right path from the predecessor's left. - If the uplink that returned us was a left uplink: - Loop back through parents until we encounter a node where node != node.parent.left. - If node.parent.left is uplink from node.parent: - If node.parent.left is not root, return it. - If it is root & root isEmpty, return null. - If it is root & root !isEmpty, return root. - If node.parent.left is not uplink from node.parent: - Follow right path for first right child from node.parent.left

Parameters:

start -

nextEntry

private PatriciaTrie.TrieEntry<K,V> nextEntry(PatriciaTrie.TrieEntry<K,V> node)

Returns the entry lexicographically after the given entry. If the given entry is null, returns the first node.

nextEntryInSubtree

private PatriciaTrie.TrieEntry<K,V> nextEntryInSubtree(PatriciaTrie.TrieEntry<K,V> node,
                                             PatriciaTrie.TrieEntry<K,V> parentOfSubtree)

Returns the entry lexicographically after the given entry. If the given entry is null, returns the first node. This will traverse only within the subtree. If the given node is not within the subtree, this will have undefined results.

nextEntryImpl

private PatriciaTrie.TrieEntry<K,V> nextEntryImpl(PatriciaTrie.TrieEntry<K,V> start,
                                        PatriciaTrie.TrieEntry<K,V> previous,
                                        PatriciaTrie.TrieEntry<K,V> tree)

Scans for the next node, starting at the specified point, and using 'previous' as a hint that the last node we returned was 'previous' (so we know not to return it again). If 'tree' is non-null, this will limit the search to the given tree. The basic premise is that each iteration can follow the following steps: 1) Scan all the way to the left. a) If we already started from this node last time, proceed to Step 2. b) If a valid uplink is found, use it. c) If the result is an empty node (root not set), break the scan. d) If we already returned the left node, break the scan. 2) Check the right. a) If we already returned the right node, proceed to Step 3. b) If it is a valid uplink, use it. c) Do Step 1 from the right node. 3) Back up through the parents until we encounter find a parent that we're not the right child of. 4) If there's no right child of that parent, the iteration is finished. Otherwise continue to Step 5. 5) Check to see if the right child is a valid uplink. a) If we already returned that child, proceed to Step 6. Otherwise, use it. 6) If the right child of the parent is the parent itself, we've already found & returned the end of the Trie, so exit. 7) Do Step 1 on the parent's right child.

toString

public String toString()

Returns each entry as a string.

Overrides:

toString in class AbstractMap<K,V>

traverse

public Map.Entry<K,V> traverse(Trie.Cursor<? super K,? super V> cursor)

Description copied from interface: Trie

Traverses the Trie in lexicographical order. Cursor.select will be called on each entry.

The traversal will stop when the cursor returns Cursor.SelectStatus.EXIT.
Cursor.SelectStatus.CONTINUE is used to continue traversing.
Cursor.SelectStatus.REMOVE is used to remove the element that was selected and continue traversing.
Cursor.SelectStatus.REMOVE_AND_EXIT is used to remove the current element and stop traversing.

Specified by:

traverse in interface Trie<K,V>

Returns:

The entry the cursor returned EXIT on, or null if it continued till the end.

isValidUplink

private boolean isValidUplink(PatriciaTrie.TrieEntry<K,V> next,
                    PatriciaTrie.TrieEntry<K,V> from)

Returns true if 'next' is a valid uplink coming from 'from'.

isValidBitIndex

private static boolean isValidBitIndex(int bitIndex)

Returns true if bitIndex is a valid index

isNullBitKey

private static boolean isNullBitKey(int bitIndex)

Returns true if bitIndex is a NULL_BIT_KEY

isEqualBitKey

private static boolean isEqualBitKey(int bitIndex)

Returns true if bitIndex is a EQUAL_BIT_KEY

length

private int length(K key)

Returns the length of the key, or 0 if the key is null.

isBitSet

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

Returns whether or not the given bit on the key is set, or false if the key is null

bitIndex

private int bitIndex(K key,
           K foundKey)

Utility method for calling keyAnalyzer.bitIndex(key, 0, length(key), foundKey, 0, length(foundKey))

newKeyIterator

Iterator<K> newKeyIterator()

newValueIterator

Iterator<V> newValueIterator()

newEntryIterator

Iterator<Map.Entry<K,V>> newEntryIterator()

keySet

public Set<K> keySet()

Returns a set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Set.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

Specified by:

keySet in interface Map<K,V>

Specified by:

keySet in interface SortedMap<K,V>

Overrides:

keySet in class AbstractMap<K,V>

Returns:

a set view of the keys contained in this map.

values

public Collection<V> values()

Returns a collection view of the values contained in this map. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

Specified by:

values in interface Map<K,V>

Specified by:

values in interface SortedMap<K,V>

Overrides:

values in class AbstractMap<K,V>

Returns:

a collection view of the values contained in this map.

valEquals

private static boolean valEquals(Object o1,
                Object o2)

Test two values for equality. Works with null values.

firstEntry

private PatriciaTrie.TrieEntry<K,V> firstEntry()

Returns the first entry the Trie is storing. This is implemented by going always to the left until we encounter a valid uplink. That uplink is the first key.

followLeft

private PatriciaTrie.TrieEntry<K,V> followLeft(PatriciaTrie.TrieEntry<K,V> node)

Goes left through the tree until it finds a valid node.

lastEntry

private PatriciaTrie.TrieEntry<K,V> lastEntry()

Returns the last entry the Trie is storing.

This is implemented by going always to the right until we encounter a valid uplink. That uplink is the last key.

followRight

protected PatriciaTrie.TrieEntry<K,V> followRight(PatriciaTrie.TrieEntry<K,V> node)

Traverses down the right path until it finds an uplink.

firstKey

public K firstKey()

Specified by:

firstKey in interface SortedMap<K,V>

headMap

public SortedMap<K,V> headMap(K toKey)

Specified by:

headMap in interface SortedMap<K,V>

lastKey

public K lastKey()

Specified by:

lastKey in interface SortedMap<K,V>

subMap

public SortedMap<K,V> subMap(K fromKey,
                    K toKey)

Specified by:

subMap in interface SortedMap<K,V>

tailMap

public SortedMap<K,V> tailMap(K fromKey)

Specified by:

tailMap in interface SortedMap<K,V>

higherEntry

protected PatriciaTrie.TrieEntry<K,V> higherEntry(K key)

Returns an entry strictly higher than the given key, or null if no such entry exists.

ceilingEntry

protected PatriciaTrie.TrieEntry<K,V> ceilingEntry(K key)

Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.

lowerEntry

protected PatriciaTrie.TrieEntry<K,V> lowerEntry(K key)

Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.

floorEntry

protected PatriciaTrie.TrieEntry<K,V> floorEntry(K key)

Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.

subtree

private PatriciaTrie.TrieEntry<K,V> subtree(K prefix,
                                  int offset,
                                  int length)

Finds the subtree that contains the prefix. This is very similar to getR but with the difference that we stop the lookup if h.bitIndex > keyLength.