org.apache.commons.collections4.trie

## Class PatriciaTrie<E>

- java.lang.Object
- - java.util.AbstractMap<K,V>
  - - org.apache.commons.collections4.trie.AbstractBitwiseTrie<K,V>
    - - org.apache.commons.collections4.trie.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
  Version:
    $Id: PatriciaTrie.java 1543928 2013-11-20 20:15:35Z tn $
  See Also:
    Radix Tree, PATRICIA, Crit-Bit Tree, Serialized Form

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and 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

      `AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>`

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

      `Map.Entry<K,V>`

  - ### Field Summary

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

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `PatriciaTrie()`
    `PatriciaTrie(Map<? extends String,? extends E> m)`

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `clear()`
    `Comparator<? super K>` | `comparator()`
    `boolean` | `containsKey(Object k)`
    `Set<Map.Entry<K,V>>` | `entrySet()`
    `K` | `firstKey()` Gets the first key currently in this map.
    `V` | `get(Object k)`
    `SortedMap<K,V>` | `headMap(K toKey)`
    `Set<K>` | `keySet()`
    `K` | `lastKey()` Gets the last key currently in this map.
    `OrderedMapIterator<K,V>` | `mapIterator()` Obtains a `MapIterator` over the map.
    `K` | `nextKey(K key)` Gets the next key after the one specified.
    `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)` Note that the return type is Object, rather than V as in the Map interface.
    `V` | `remove(Object k)`
    `Map.Entry<K,V>` | `select(K key)` Returns the `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()`
    `SortedMap<K,V>` | `subMap(K fromKey, K toKey)`
    `SortedMap<K,V>` | `tailMap(K fromKey)`
    `Collection<V>` | `values()`

    - ### Methods inherited from class org.apache.commons.collections4.trie.AbstractBitwiseTrie

      `getKeyAnalyzer, toString`

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

      `containsValue, equals, hashCode, isEmpty, putAll`

    - ### Methods inherited from interface org.apache.commons.collections4.Put

      `putAll`

    - ### Methods inherited from interface org.apache.commons.collections4.Get

      `containsValue, isEmpty`

- - ### 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 `Iterator`s.

  - ### Constructor Detail

    - #### PatriciaTrie

          public PatriciaTrie()

    - #### PatriciaTrie

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

  - ### Method Detail

    - #### clear

          public void clear()

      Specified by:
        `clear` in interface `Map<K,V>`
      Specified by:
        `clear` in interface `Put<K,V>`
      Overrides:
        `clear` in class `AbstractMap<K,V>`
      See Also:
        `Map.clear()`

    - #### size

          public int size()

      Specified by:
        `size` in interface `Map<K,V>`
      Specified by:
        `size` in interface `Get<K,V>`
      Overrides:
        `size` in class `AbstractMap<K,V>`
      See Also:
        `Map.size()`

    - #### 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)`

    - #### get

          public V get(Object k)

      Specified by:
        `get` in interface `Map<K,V>`
      Specified by:
        `get` in interface `Get<K,V>`
      Overrides:
        `get` in class `AbstractMap<K,V>`
      See Also:
        `Map.get(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

    - #### containsKey

          public boolean containsKey(Object k)

      Specified by:
        `containsKey` in interface `Map<K,V>`
      Specified by:
        `containsKey` in interface `Get<K,V>`
      Overrides:
        `containsKey` in class `AbstractMap<K,V>`
      See Also:
        `Map.containsKey(Object)`

    - #### 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 interface `Get<K,V>`
      Specified by:
        `entrySet` in class `AbstractMap<K,V>`
      See Also:
        `Map.entrySet()`

    - #### keySet

          public Set<K> keySet()

      Specified by:
        `keySet` in interface `Map<K,V>`
      Specified by:
        `keySet` in interface `SortedMap<K,V>`
      Specified by:
        `keySet` in interface `Get<K,V>`
      Overrides:
        `keySet` in class `AbstractMap<K,V>`
      See Also:
        `Map.keySet()`

    - #### values

          public Collection<V> values()

      Specified by:
        `values` in interface `Map<K,V>`
      Specified by:
        `values` in interface `SortedMap<K,V>`
      Specified by:
        `values` in interface `Get<K,V>`
      Overrides:
        `values` in class `AbstractMap<K,V>`
      See Also:
        `Map.values()`

    - #### remove

          public V remove(Object k)

      Specified by:
        `remove` in interface `Map<K,V>`
      Specified by:
        `remove` in interface `Get<K,V>`
      Overrides:
        `remove` in class `AbstractMap<K,V>`
      Throws:
        `ClassCastException` - if provided key is of an incompatible type
      See Also:
        `Map.remove(Object)`

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

Copyright © 2001–2015 The Apache Software Foundation. All rights reserved.