Package org.apache.commons.collections4.trie

# Class AbstractPatriciaTrie<K,V>

java.lang.Object
java.util.AbstractMap<K,V>
org.apache.commons.collections4.trie.AbstractBitwiseTrie<K,V>
org.apache.commons.collections4.trie.AbstractPatriciaTrie<K,V>

Type Parameters:
  `K` - The type of the keys in this map
  `V` - The type of the values in this map

All Implemented Interfaces:
  `Serializable`, `Map<K,V>`, `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`

public 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
See Also:
  - Serialized Form

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

  `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
  Description
  `protected int`
  `modCount`
  The number of times this `Trie` has been modified.

- ## Constructor Summary

  Constructors
  Modifier
  Constructor
  Description
  `protected`
  `AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer)`
  Constructs a new `Trie` using the given `KeyAnalyzer`.
  `protected`
  `AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K,? extends V> map)`
  Constructs a new `Trie` using the given `KeyAnalyzer` and initializes the `Trie` with the values from the provided `Map`.

- ## Method Summary

  Modifier and Type
  Method
  Description
  `void`
  `clear()`
  Removes all of the mappings from this map.
  `Comparator<? super K>`
  `comparator()`
  `boolean`
  `containsKey(Object k)`
  Tests for presence of a given key.
  `Set<Map.Entry<K,V>>`
  `entrySet()`
  Gets a set view of the mappings contained in this map.
  `AbstractPatriciaTrie.TrieEntry<K,V>`
  `firstEntry()`
  Returns the first entry the `Trie` is storing.
  `K`
  `firstKey()`
  Gets the first key currently in this map.
  `V`
  `get(Object k)`
  Gets a value at a given key.
  `SortedMap<K,V>`
  `headMap(K toKey)`
  `Set<K>`
  `keySet()`
  Gets a view of the keys contained in this map.
  `AbstractPatriciaTrie.TrieEntry<K,V>`
  `lastEntry()`
  Returns the last entry the `Trie` is storing.
  `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.
  `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(Object k)`
  Remove a key-value mappings.
  `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.
  `SortedMap<K,V>`
  `subMap(K fromKey, K toKey)`
  `SortedMap<K,V>`
  `tailMap(K fromKey)`
  `Collection<V>`
  `values()`
  Gets a a collection view of the values contained in this map.

  ### 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 org.apache.commons.collections4.Get

  `containsValue, isEmpty`

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

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

  - ### AbstractPatriciaTrie

    protected AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer)
    Constructs a new `Trie` using the given `KeyAnalyzer`.
    Parameters:
      `keyAnalyzer` - The `KeyAnalyzer`.

  - ### AbstractPatriciaTrie

    protected AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K,? extends V> map)
    Constructs a new `Trie` using the given `KeyAnalyzer` and initializes the `Trie` with the values from the provided `Map`.
    Parameters:
      `keyAnalyzer` - The `KeyAnalyzer`.
      `map` - The source map.

- ## Method Details

  - ### clear

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

  - ### comparator

    public Comparator<? super K> comparator()

  - ### containsKey

    public boolean containsKey(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 `Map<K,V>`
    Overrides:
      `containsKey` in class `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 Set<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 `Map<K,V>`
    Specified by:
      `entrySet` in interface `SortedMap<K,V>`
    Specified by:
      `entrySet` in class `AbstractMap<K,V>`
    Returns:
      A set view of the mappings contained in this map.
    See Also:
      - `Map.entrySet()`

  - ### firstEntry

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

    Returns:
      The first entry the `Trie` is storing.
    Since:
      4.6.0

  - ### 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(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 `Map<K,V>`
    Overrides:
      `get` in class `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 SortedMap<K,V> headMap(K toKey)

  - ### keySet

    public 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 `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.
    See Also:
      - `Map.keySet()`

  - ### lastEntry

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

    Returns:
      The last entry the `Trie` is storing.
    Since:
      4.6.0

  - ### 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 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 `Map<K,V>`
    Specified by:
      `put` in interface `Put<K,V>`
    Overrides:
      `put` in class `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(Object k)
    Remove a key-value mappings.
    Specified by:
      `remove` in interface `Get<K,V>`
    Specified by:
      `remove` in interface `Map<K,V>`
    Overrides:
      `remove` in class `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:
      `ClassCastException` - if provided key is of an incompatible type
    See Also:
      - `Map.remove(Object)`

  - ### select

    public 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 `Map<K,V>`
    Overrides:
      `size` in class `AbstractMap<K,V>`
    Returns:
      The number of key-value mappings in this map.
    See Also:
      - `Map.size()`

  - ### subMap

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

  - ### tailMap

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

  - ### values

    public 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 `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.
    See Also:
      - `Map.values()`