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

    • serialVersionUID

      private static final long serialVersionUID
      See Also:

    • root

      private transient AbstractPatriciaTrie.TrieEntry<K,V> root
      The root node of the Trie.

    • keySet

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

    • entrySet

      private transient volatile Set<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.

  • Constructor Details

  • Method Details

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

    • size

      public int size()
      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:

    • incrementSize

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

    • decrementSize

      void decrementSize()
      A helper method to decrement the
      invalid reference 
      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 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:

    • addEntry

      AbstractPatriciaTrie.TrieEntry<K,V> addEntry(AbstractPatriciaTrie.TrieEntry<K,V> entry, int lengthInBits)
      Adds the given AbstractPatriciaTrie.TrieEntry to the
      invalid reference 
      Trie
      .

    • get

      public V get(Object k)
      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:

    • getEntry

      AbstractPatriciaTrie.TrieEntry<K,V> getEntry(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 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<Map.Entry<K,V>> reference)
      This is equivalent to the other
      invalid reference 
      #selectR(TrieEntry, int, Object, int, Cursor, Reference)
      method but without its overhead because we're selecting only one best matching Entry from the
      invalid reference 
      Trie
      .

    • containsKey

      public boolean containsKey(Object k)
      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:

    • entrySet

      public Set<Map.Entry<K,V>> entrySet()
      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:

    • keySet

      public Set<K> keySet()
      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:

    • values

      public Collection<V> values()
      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:

    • remove

      public V remove(Object k)
      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:

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

    • nextEntry

      AbstractPatriciaTrie.TrieEntry<K,V> nextEntry(AbstractPatriciaTrie.TrieEntry<K,V> node)
      Returns the entry lexicographically after the given entry. If the given entry is null, returns the first node.

    • 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 invalid input: '&' 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
      invalid reference 
      Trie
      is storing.

      This is implemented by going always to the left until we encounter a valid uplink. That uplink is the first key.

    • followLeft

      AbstractPatriciaTrie.TrieEntry<K,V> followLeft(AbstractPatriciaTrie.TrieEntry<K,V> node)
      Goes left through the tree until it finds a valid node.

    • 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: 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 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 SortedMap<K,V> getPrefixMapByBits(K key, int offsetInBits, int lengthInBits)
      Returns a view of this
      invalid reference 
      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

      invalid reference 
      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
      invalid reference 
      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)

    • higherEntry

      AbstractPatriciaTrie.TrieEntry<K,V> higherEntry(K key)
      Returns an entry strictly higher than the given key, or null if no such entry exists.

    • 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
      invalid reference 
      Trie
      is storing.

      This is implemented by going always to the right until we encounter a valid uplink. That uplink is the last key.

    • followRight

      AbstractPatriciaTrie.TrieEntry<K,V> followRight(AbstractPatriciaTrie.TrieEntry<K,V> node)
      Traverses down the right path until it finds an uplink.

    • 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 invalid input: '&' root isEmpty, return null. - If it is root invalid input: '&' 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

    • nextEntryInSubtree

      AbstractPatriciaTrie.TrieEntry<K,V> nextEntryInSubtree(AbstractPatriciaTrie.TrieEntry<K,V> node, AbstractPatriciaTrie.TrieEntry<K,V> parentOfSubtree)
      Returns the entry lexicographically after the given entry. If the given entry is null, returns the first node. This will traverse only within the subtree. If the given node is not within the subtree, this will have undefined results.

    • isValidUplink

      static boolean isValidUplink(AbstractPatriciaTrie.TrieEntry<?,?> next, AbstractPatriciaTrie.TrieEntry<?,?> from)
      Returns true if 'next' is a valid uplink coming from 'from'.

    • readObject

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

    • writeObject

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