Package org.apache.commons.collections4.trie

Class AbstractPatriciaTrie<K,​V>

  • All Implemented Interfaces:
    java.io.Serializable, java.util.Map<K,​V>, java.util.SortedMap<K,​V>, Get<K,​V>, IterableGet<K,​V>, IterableMap<K,​V>, IterableSortedMap<K,​V>, OrderedMap<K,​V>, Put<K,​V>, Trie<K,​V>
    Direct Known Subclasses:
    PatriciaTrie
    abstract class AbstractPatriciaTrie<K,​V>
extends AbstractBitwiseTrie<K,​V>
    This class implements the base PATRICIA algorithm and everything that is related to the Map interface.
    Since:
    4.0

    • Field Detail

      • keySet

        private transient volatile java.util.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 java.util.Collection<V> values

      • entrySet

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

      • size

        private transient int size
        The current size of the Trie.

      • modCount

        protected transient int modCount
        The number of times this Trie has been modified. It's used to detect concurrent modifications and fail-fast the Iterators.

    • Method Detail

      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Map<K,​V>
        Specified by:
        clear in interface Put<K,​V>
        Overrides:
        clear in class java.util.AbstractMap<K,​V>
        See Also:
        Map.clear()

      • size

        public int size()
        Specified by:
        size in interface Get<K,​V>
        Specified by:
        size in interface java.util.Map<K,​V>
        Overrides:
        size in class java.util.AbstractMap<K,​V>
        Returns:
        the number of key-value mappings in this map
        See Also:
        Map.size()

      • incrementSize

        void incrementSize()
        A helper method to increment the Trie size and the modification counter.

      • decrementSize

        void decrementSize()
        A helper method to decrement the Trie size and increment the modification counter.

      • incrementModCount

        private void incrementModCount()
        A helper method to increment the modification counter.

      • put

        public V put​(K key,
             V value)
        Description copied from interface: Put
        Note that the return type is Object, rather than V as in the Map interface. See the class Javadoc for further info.
        Specified by:
        put in interface java.util.Map<K,​V>
        Specified by:
        put in interface Put<K,​V>
        Overrides:
        put in class java.util.AbstractMap<K,​V>
        Parameters:
        key - key with which the specified value is to be associated
        value - value to be associated with the specified key
        Returns:
        the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key, if the implementation supports null values.)
        See Also:
        Map.put(Object, Object)

      • get

        public V get​(java.lang.Object k)
        Specified by:
        get in interface Get<K,​V>
        Specified by:
        get in interface java.util.Map<K,​V>
        Overrides:
        get in class java.util.AbstractMap<K,​V>
        Parameters:
        k - the key whose associated value is to be returned
        Returns:
        the value to which the specified key is mapped, or null if this map contains no mapping for the key
        See Also:
        Map.get(Object)

      • getEntry

        AbstractPatriciaTrie.TrieEntry<K,​V> getEntry​(java.lang.Object k)
        Returns the entry associated with the specified key in the PatriciaTrieBase. Returns null if the map contains no mapping for this key.

        This may throw ClassCastException if the object is not of type K.

      • select

        public java.util.Map.Entry<K,​V> select​(K key)
        Returns the Map.Entry whose key is closest in a bitwise XOR metric to the given key. This is NOT lexicographic closeness. For example, given the keys:
        1. D = 1000100
        2. H = 1001000
        3. L = 1001100
        If the Trie contained 'H' and 'L', a lookup of 'D' would return 'L', because the XOR distance between D & L is smaller than the XOR distance between D & H.
        Parameters:
        key - the key to use in the search
        Returns:
        the Map.Entry whose key is closest in a bitwise XOR metric to the provided key

      • selectKey

        public K selectKey​(K key)
        Returns the key that is closest in a bitwise XOR metric to the provided key. This is NOT lexicographic closeness! For example, given the keys:
        1. D = 1000100
        2. H = 1001000
        3. L = 1001100
        If the Trie contained 'H' and 'L', a lookup of 'D' would return 'L', because the XOR distance between D & L is smaller than the XOR distance between D & H.
        Parameters:
        key - the key to use in the search
        Returns:
        the key that is closest in a bitwise XOR metric to the provided key

      • selectValue

        public V selectValue​(K key)
        Returns the value whose key is closest in a bitwise XOR metric to the provided key. This is NOT lexicographic closeness! For example, given the keys:
        1. D = 1000100
        2. H = 1001000
        3. L = 1001100
        If the Trie contained 'H' and 'L', a lookup of 'D' would return 'L', because the XOR distance between D & L is smaller than the XOR distance between D & H.
        Parameters:
        key - the key to use in the search
        Returns:
        the value whose key is closest in a bitwise XOR metric to the provided key

      • selectR

        private boolean selectR​(AbstractPatriciaTrie.TrieEntry<K,​V> h,
                        int bitIndex,
                        K key,
                        int lengthInBits,
                        AbstractPatriciaTrie.Reference<java.util.Map.Entry<K,​V>> reference)
        This is equivalent to the other #selectR(TrieEntry, int, Object, int, Cursor, Reference) method but without its overhead because we're selecting only one best matching Entry from the Trie.

      • containsKey

        public boolean containsKey​(java.lang.Object k)
        Specified by:
        containsKey in interface Get<K,​V>
        Specified by:
        containsKey in interface java.util.Map<K,​V>
        Overrides:
        containsKey in class java.util.AbstractMap<K,​V>
        Parameters:
        k - key whose presence in this map is to be tested
        Returns:
        true if this map contains a mapping for the specified key
        See Also:
        Map.containsKey(Object)

      • entrySet

        public java.util.Set<java.util.Map.Entry<K,​V>> entrySet()
        Specified by:
        entrySet in interface Get<K,​V>
        Specified by:
        entrySet in interface java.util.Map<K,​V>
        Specified by:
        entrySet in interface java.util.SortedMap<K,​V>
        Specified by:
        entrySet in class java.util.AbstractMap<K,​V>
        Returns:
        a set view of the mappings contained in this map
        See Also:
        Map.entrySet()

      • keySet

        public java.util.Set<K> keySet()
        Specified by:
        keySet in interface Get<K,​V>
        Specified by:
        keySet in interface java.util.Map<K,​V>
        Specified by:
        keySet in interface java.util.SortedMap<K,​V>
        Overrides:
        keySet in class java.util.AbstractMap<K,​V>
        Returns:
        a set view of the keys contained in this map
        See Also:
        Map.keySet()

      • values

        public java.util.Collection<V> values()
        Specified by:
        values in interface Get<K,​V>
        Specified by:
        values in interface java.util.Map<K,​V>
        Specified by:
        values in interface java.util.SortedMap<K,​V>
        Overrides:
        values in class java.util.AbstractMap<K,​V>
        Returns:
        a collection view of the values contained in this map
        See Also:
        Map.values()

      • remove

        public V remove​(java.lang.Object k)
        Specified by:
        remove in interface Get<K,​V>
        Specified by:
        remove in interface java.util.Map<K,​V>
        Overrides:
        remove in class java.util.AbstractMap<K,​V>
        Parameters:
        k - key whose mapping is to be removed from the map
        Returns:
        the previous value associated with key, or null if there was no mapping for key.
        Throws:
        java.lang.ClassCastException - if provided key is of an incompatible type
        See Also:
        Map.remove(Object)

      • getNearestEntryForKey

        AbstractPatriciaTrie.TrieEntry<K,​V> getNearestEntryForKey​(K key,
                                                                int lengthInBits)
        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.

      • removeEntry

        V removeEntry​(AbstractPatriciaTrie.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​(AbstractPatriciaTrie.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​(AbstractPatriciaTrie.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.

      • nextEntryImpl

        AbstractPatriciaTrie.TrieEntry<K,​V> nextEntryImpl​(AbstractPatriciaTrie.TrieEntry<K,​V> start,
                                                        AbstractPatriciaTrie.TrieEntry<K,​V> previous,
                                                        AbstractPatriciaTrie.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.

      • firstEntry

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

      • comparator

        public java.util.Comparator<? super K> comparator()

      • firstKey

        public K firstKey()
        Description copied from interface: OrderedMap
        Gets the first key currently in this map.
        Returns:
        the first key currently in this map

      • lastKey

        public K lastKey()
        Description copied from interface: OrderedMap
        Gets the last key currently in this map.
        Returns:
        the last key currently in this map

      • nextKey

        public K nextKey​(K key)
        Description copied from interface: OrderedMap
        Gets the next key after the one specified.
        Parameters:
        key - the key to search for next from
        Returns:
        the next key, null if no match or at end

      • previousKey

        public K previousKey​(K key)
        Description copied from interface: OrderedMap
        Gets the previous key before the one specified.
        Parameters:
        key - the key to search for previous from
        Returns:
        the previous key, null if no match or at start

      • mapIterator

        public OrderedMapIterator<K,​V> mapIterator()
        Description copied from interface: OrderedMap
        Obtains an OrderedMapIterator over the map.

        A ordered map iterator is an efficient way of iterating over maps in both directions.

        Returns:
        a map iterator

      • prefixMap

        public java.util.SortedMap<K,​V> prefixMap​(K key)
        Description copied from interface: Trie
        Returns a view of this Trie of all elements that are prefixed by the given key.

        In a Trie with fixed size keys, this is essentially a Map.get(Object) operation.

        For example, if the Trie contains 'Anna', 'Anael', 'Analu', 'Andreas', 'Andrea', 'Andres', and 'Anatole', then a lookup of 'And' would return 'Andreas', 'Andrea', and 'Andres'.

        Parameters:
        key - the key used in the search
        Returns:
        a SortedMap view of this Trie with all elements whose key is prefixed by the search key

      • getPrefixMapByBits

        private java.util.SortedMap<K,​V> getPrefixMapByBits​(K key,
                                                          int offsetInBits,
                                                          int lengthInBits)
        Returns a view of this Trie of all elements that are prefixed by the number of bits in the given Key.

        The view that this returns is optimized to have a very efficient Iterator. The SortedMap.firstKey(), SortedMap.lastKey() & Map.size() methods must iterate over all possible values in order to determine the results. This information is cached until the PATRICIA Trie 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 - the key to use in the search
        offsetInBits - the prefix offset
        lengthInBits - the number of significant prefix bits
        Returns:
        a SortedMap view of this Trie with all elements whose key is prefixed by the search key

      • headMap

        public java.util.SortedMap<K,​V> headMap​(K toKey)

      • subMap

        public java.util.SortedMap<K,​V> subMap​(K fromKey,
                                             K toKey)

      • tailMap

        public java.util.SortedMap<K,​V> tailMap​(K fromKey)

      • ceilingEntry

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

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

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

        AbstractPatriciaTrie.TrieEntry<K,​V> subtree​(K prefix,
                                                  int offsetInBits,
                                                  int lengthInBits)
        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 > lengthInBits.

      • lastEntry

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

      • previousEntry

        AbstractPatriciaTrie.TrieEntry<K,​V> previousEntry​(AbstractPatriciaTrie.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 - the start entry

      • readObject

        private void readObject​(java.io.ObjectInputStream stream)
                 throws java.io.IOException,
                        java.lang.ClassNotFoundException
        Reads the content of the stream.
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException

      • writeObject

        private void writeObject​(java.io.ObjectOutputStream stream)
                  throws java.io.IOException
        Writes the content to the stream for serialization.
        Throws:
        java.io.IOException