org.apache.commons.collections4.trie

Class PatriciaTrie<E>

  • All Implemented Interfaces:
    Serializable, Map<String,E>, SortedMap<String,E>, Get<String,E>, IterableGet<String,E>, IterableMap<String,E>, IterableSortedMap<String,E>, OrderedMap<String,E>, Put<String,E>, Trie<String,E> 

    public class PatriciaTrie<E>
extends AbstractBitwiseTrie<K,V>
    Implementation of a PATRICIA Trie (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(Object) 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 'prefixMap', '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 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 prefixMap(Object) are suited only to variable length keys.

    Since:
    4.0
    See Also:
    Radix Tree, PATRICIA, Crit-Bit Tree, Serialized Form

    • Field Detail

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

    • Constructor Detail

      • PatriciaTrie

        public PatriciaTrie()

      • PatriciaTrie

        public PatriciaTrie(Map<? extends String,? extends E> m)

    • Method Detail

      • 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  Map<K,V>
        Specified by:
        put in interface  Put<K,V>
        Overrides:
        put in class  AbstractMap<K,V>
        See Also:
        Map.put(Object, Object)

      • select

        public Map.Entry<K,V> select(K key)
        Returns the 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 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

      • comparator

        public 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: IterableGet
        Obtains a MapIterator over the map.

        A map iterator is an efficient way of iterating over maps. There is no need to access the entry set or use Map Entry objects. 

         IterableMap
                          
                             map = new HashedMap
                            
                              (); MapIterator
                              
                                 it = map.mapIterator(); while (it.hasNext()) { String key = it.next(); Integer value = it.getValue(); it.setValue(value + 1); }
        Returns:
        a map iterator

      • prefixMap

        public 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

      • headMap

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

      • subMap

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

      • tailMap

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