Package org.apache.commons.collections4.trie

Class AbstractPatriciaTrie<K,​V>

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      protected static class  AbstractPatriciaTrie.TrieEntry<K,​V>
      A Trie is a set of AbstractPatriciaTrie.TrieEntry nodes.

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

        java.util.AbstractMap.SimpleEntry<K extends java.lang.Object,​V extends java.lang.Object>, java.util.AbstractMap.SimpleImmutableEntry<K extends java.lang.Object,​V extends java.lang.Object>

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

        java.util.Map.Entry<K extends java.lang.Object,​V extends java.lang.Object>

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected int modCount
      The number of times this Trie has been modified.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()
      Removes all of the mappings from this map.
      java.util.Comparator<? super K> comparator()  
      boolean containsKey​(java.lang.Object k)
      Tests for presence of a given key.
      java.util.Set<java.util.Map.Entry<K,​V>> entrySet()
      Gets a set view of the mappings contained in this map.
      K firstKey()
      Gets the first key currently in this map.
      V get​(java.lang.Object k)
      Gets a value at a given key.
      java.util.SortedMap<K,​V> headMap​(K toKey)  
      java.util.Set<K> keySet()
      Gets a view of the keys contained in this map.
      K lastKey()
      Gets the last key currently in this map.
      OrderedMapIterator<K,​V> mapIterator()
      Obtains an OrderedMapIterator over the map.
      K nextKey​(K key)
      Gets the next key after the one specified.
      java.util.SortedMap<K,​V> prefixMap​(K key)
      Returns a view of this Trie of all elements that are prefixed by the given key.
      K previousKey​(K key)
      Gets the previous key before the one specified.
      V put​(K key, V value)
      Associates the specified value with the specified key in this map.
      V remove​(java.lang.Object k)
      Remove a key-value mappings.
      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.
      K selectKey​(K key)
      Returns the key that is closest in a bitwise XOR metric to the provided key.
      V selectValue​(K key)
      Returns the value whose key is closest in a bitwise XOR metric to the provided key.
      int size()
      Gets the number of key-value mappings in this map.
      java.util.SortedMap<K,​V> subMap​(K fromKey, K toKey)  
      java.util.SortedMap<K,​V> tailMap​(K fromKey)  
      java.util.Collection<V> values()
      Gets a a collection view of the values contained in this map.

      • Methods inherited from class java.util.AbstractMap

        clone, containsValue, equals, hashCode, isEmpty, 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, containsValue, equals, forEach, getOrDefault, hashCode, isEmpty, merge, putAll, putIfAbsent, remove, replace, replace, replaceAll

      • Methods inherited from interface org.apache.commons.collections4.Put

        putAll

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

    • Method Detail

      • clear

        public void clear()
        Description copied from interface: Put
        Removes all of the mappings from this map.
        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()

      • comparator

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

      • containsKey

        public boolean containsKey​(java.lang.Object k)
        Description copied from interface: Get
        Tests for presence of a given key.
        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()
        Description copied from interface: Get
        Gets a set view of the mappings contained in this map.
        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()

      • 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

      • get

        public V get​(java.lang.Object k)
        Description copied from interface: Get
        Gets a value at a given key.
        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)

      • headMap

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

      • keySet

        public java.util.Set<K> keySet()
        Description copied from interface: Get
        Gets a view of the keys contained in this map.
        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()

      • 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

      • mapIterator

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

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

        Returns:
        a map iterator

      • 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

      • 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

      • 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

      • put

        public V put​(K key,
             V value)
        Description copied from interface: Put
        Associates the specified value with the specified key in this map.

        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)

      • remove

        public V remove​(java.lang.Object k)
        Remove a key-value mappings.
        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)

      • 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

      • size

        public int size()
        Description copied from interface: Get
        Gets the number of key-value mappings in this map.
        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()

      • subMap

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

      • tailMap

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

      • values

        public java.util.Collection<V> values()
        Description copied from interface: Get
        Gets a a collection view of the values contained in this map.
        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()