PatriciaTrie (McIDAS-V 1.6 Developer Documentation)

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 and 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` 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` Number of times this has been modified (to fail-fast the iterators).
`private PatriciaTrie.TrieEntry<K,V>`	`root` Root element of the Trie.
`private static long`	`serialVersionUID`
`private int`	`size` 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.

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

Method Summary

All Methods Static Methods Instance Methods Concrete 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 an object of type `K`.
`private int`	`bitIndex(K key, K foundKey)` Utility method for calling `PatriciaTrie.KeyAnalyzer.bitIndex(Object, int, int, Object, int, int)`.
`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)` Attempt to find the given key within the trie.
`(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 `PatriciaTrie.KeyAnalyzer.EQUAL_BIT_KEY`.
`private static boolean`	`isNullBitKey(int bitIndex)` Returns true if bitIndex is a `PatriciaTrie.KeyAnalyzer.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 `<key, value>` 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
compute, computeIfAbsent, computeIfPresent, equals, forEach, getOrDefault, hashCode, merge, putAll, putIfAbsent, remove, replace, replace, replaceAll

- Field Detail
  - serialVersionUID
```
private static final long serialVersionUID
```
    See Also:
    
    Constant Field Values
  - root
```
private final PatriciaTrie.TrieEntry<K,V> root
```
    Root element of the Trie.
  - size
```
private int size
```
    Current size (total number of elements) of the Trie.
  - modCount
```
private transient int modCount
```
    Number of times this has been modified (to fail-fast the iterators).
  - keyAnalyzer
```
private final PatriciaTrie.KeyAnalyzer<? super K> keyAnalyzer
```
    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.
    
    Parameters:
    
    keyAnalyzer - Used to analyze bit values of keys.
- Method Detail
  - getKeyAnalyzer
```
public PatriciaTrie.KeyAnalyzer<? super K> getKeyAnalyzer()
```
    Returns the KeyAnalyzer that constructed the trie.
    
    Returns:
    
    keyAnalyzer
  - comparator
```
public Comparator<? super K> comparator()
```
    Returns the KeyAnalyzer as a comparator.
    
    Specified by:
    
    comparator in interface SortedMap<K,V>
    
    Returns:
    
    Essentially just keyAnalyzer casted as a Comparator.
  - 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>
    
    Returns:
    
    true if the trie is empty, false otherwise.
  - 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>
    
    Returns:
    
    Items stored within trie.
  - 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 <key, value> 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.
    
    Parameters:
    
    toAdd - Trie entry to add.
    
    keyLength - Length of the entry's key.
    
    Returns:
    
    Newly added trie entry.
  - 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)
```
    Attempt to find the given key within the trie.
    
    Specified by:
    
    get in interface Map<K,V>
    
    Overrides:
    
    get in class AbstractMap<K,V>
    
    Parameters:
    
    k - Key to search for within the trie.
    
    Returns:
    
    Value whose Key equals our lookup Key or null if no such key exists.
  - 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.
    
    Parameters:
    
    k - Key to search for within the trie.
    
    Returns:
    
    Trie entry containing the given key and its associated value.
  - asKey
```
protected final K asKey(Object key)
```
    Gets the key as an object of type K.
    
    Parameters:
    
    key - Key to "cast" to type K.
    
    Returns:
    
    Essentially key casted to type 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.
    
    Parameters:
    
    key - Key to search for within the trie.
    
    keyLength - Length of key.
    
    Returns:
    
    Entry that is the closest match to the given key.
  - 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>
    
    Parameters:
    
    key - Key to search for within the trie.
    
    Returns:
    
    Value associated with key.
  - 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.
    
    Parameters:
    
    h - Node representing root of subtree being searched.
    
    bitIndex -
    
    key - Key being matched.
    
    keyLength - Length of key.
    
    result - Array containing best match.
    
    Returns:
    
    Whether or not a node was selected.
  - 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>
    
    Parameters:
    
    key - Key to match.
    
    cursor - Cursor being used to traverse the trie.
    
    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(), and 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 - Key to search for within the trie.
    
    Returns:
    
    Map containing keys matching the given prefix and their values.
  - 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(), and 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 - Key to search for within the trie.
    
    length - Length of key. Ignored for tries with a fixed key size.
    
    Returns:
    
    Map containing keys matching the given prefix and their values.
  - 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(), and 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 - Key to search for within the trie.
    
    offset - Offset to begin search at.
    
    length - Length of key. Ignored for tries with a fixed key size.
    
    Returns:
    
    Map containing keys matching the given prefix and their values.
  - 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(), and 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 - Key to search for within the trie.
    
    bitLength - Length of key in bits.
    
    Returns:
    
    Map containing keys matching the given prefix and their values.
  - 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(), and 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 - Key to search for within the trie.
    
    offset - Offset within key to begin search.
    
    length - Length of key in bits.
    
    Returns:
    
    Map containing keys matching the given prefix and their values.
  - 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>
    
    Parameters:
    
    k - Key to search for within trie.
    
    Returns:
    
    true if the trie contains the given k.
  - 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>
    
    Parameters:
    
    o - Value to search for within trie.
    
    Returns:
    
    true if the trie contains something equal to o.
  - 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 - 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)
    
    Parameters:
    
    h - Node to remove from the trie.
    
    Returns:
    
    Value that was removed from the trie.
  - 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.
    
    Parameters:
    
    h - Node to remove from the trie.
  - 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.
    
    Parameters:
    
    h - Node to remove from the trie.
  - 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 - Node from which the search should begin.
    
    Returns:
    
    Node that is lexicographically "before" 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.
    
    Parameters:
    
    node - Node whose subsequent entry is desired.
    
    Returns:
    
    Next lexicographic entry after the given 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.
    
    Parameters:
    
    node - Node whose subsequent entry is desired.
    
    parentOfSubtree - Node that is parent of subtree being searched.
    
    Returns:
    
    Next lexicographic entry after the given node.
  - 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 and returned the end of the Trie, so exit. 7) Do Step 1 on the parent's right child.
    
    Parameters:
    
    start - Node from which the search should begin.
    
    previous - Previously-searched node.
    
    tree - If not null, search will be limited to this subtree.
    
    Returns:
    
    Entry after previous.
  - 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>
    
    Parameters:
    
    cursor - Cursor being used to traverse the trie.
    
    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'.
    
    Parameters:
    
    next -
    
    from -
    
    Returns:
    
    true if next is a valid "uplink" from from.
  - isValidBitIndex
```
private static boolean isValidBitIndex(int bitIndex)
```
    Returns true if bitIndex is a valid index.
    
    Parameters:
    
    bitIndex - Bit index to check.
    
    Returns:
    
    Whether or not the given bitIndex is valid.
  - isNullBitKey
```
private static boolean isNullBitKey(int bitIndex)
```
    Returns true if bitIndex is a PatriciaTrie.KeyAnalyzer.NULL_BIT_KEY.
    
    Parameters:
    
    bitIndex -
    
    Returns:
  - isEqualBitKey
```
private static boolean isEqualBitKey(int bitIndex)
```
    Returns true if bitIndex is a PatriciaTrie.KeyAnalyzer.EQUAL_BIT_KEY.
    
    Parameters:
    
    bitIndex -
    
    Returns:
  - length
```
private int length(K key)
```
    Returns the length of the key, or 0 if the key is null.
    
    Parameters:
    
    key - Key whose length is desired. null is allowed.
    
    Returns:
    
    Length of key.
  - 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.
    
    Parameters:
    
    key - Key to check. null is allowed.
    
    keyLength - Length of key.
    
    bitIndex - Bit index of key that should be checked.
    
    Returns:
    
    Whether or not the bit at bitIndex on key is set. If key is null, false will be returned.
  - bitIndex
```
private int bitIndex(K key,
                     K foundKey)
```
    Utility method for calling PatriciaTrie.KeyAnalyzer.bitIndex(Object, int, int, Object, int, int).
    
    Parameters:
    
    key -
    
    foundKey -
    
    Returns:
  - 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.
    
    Parameters:
    
    key -
    
    Returns:
  - 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.
    
    Parameters:
    
    key -
    
    Returns:
  - 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.
    
    Parameters:
    
    key -
    
    Returns:
  - 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.
    
    Parameters:
    
    key -
    
    Returns:
  - 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.
    
    Parameters:
    
    prefix -
    
    offset -
    
    length -
    
    Returns:

Class PatriciaTrie<K,V>

Nested Class Summary

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

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

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

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.util.AbstractMap

Methods inherited from class java.lang.Object

Methods inherited from interface java.util.Map

Field Detail

serialVersionUID

root

size

modCount

keyAnalyzer

keySet

values

entrySet

Constructor Detail

PatriciaTrie

Method Detail

getKeyAnalyzer

comparator

clear

isEmpty

size

incrementSize

decrementSize

incrementModCount

put

addEntry

entrySet

get

getEntry

asKey

getNearestEntryForKey

select

selectR

select

selectR

getPrefixedBy

getPrefixedBy

getPrefixedBy

getPrefixedByBits

getPrefixedByBits

containsKey

containsValue

remove

removeEntry

removeExternalEntry

removeInternalEntry

previousEntry

nextEntry

nextEntryInSubtree

nextEntryImpl

toString

traverse

isValidUplink

isValidBitIndex

isNullBitKey

isEqualBitKey

length

isBitSet

bitIndex

newKeyIterator

newValueIterator

newEntryIterator

keySet

values

valEquals

firstEntry

followLeft

lastEntry

followRight

firstKey

headMap

lastKey

subMap