edu.wisc.ssec.mcidasv.util.trie

Class PatriciaTrie<K,V>

    • Field Detail

      • 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).

      • 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.

    • Method Detail

      • 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.

      • 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>

      • 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.

      • 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 -

      • 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 -

      • 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.

      • 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.

      • 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))

      • 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.

      • 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.

      • 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.