Overview  Package   Class  Use  Tree  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

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

java.lang.Object
  extended by java.util.AbstractMap<K,V>
      extended by 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
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
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
PatriciaTrie(PatriciaTrie.KeyAnalyzer<? super K> keyAnalyzer)
          Constructs a new PatriciaTrie using the given keyAnalyzer.
 
Method Summary
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.

Overview  Package   Class  Use  Tree  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD