Package org.apache.cassandra.index.sasi.utils.trie

Class PatriciaTrie<K,​V>

  • All Implemented Interfaces:
    java.io.Serializable, java.util.Map<K,​V>, java.util.SortedMap<K,​V>, Trie<K,​V>
    public class PatriciaTrie<K,​V>
extends java.util.AbstractMap<K,​V>
implements java.io.Serializable

    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 Trie.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 Trie.traverse(Cursor), 'prefix', '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.

    Any methods here that take an Object argument may throw a ClassCastException if the method is expecting an instance of K and it isn't K.

    Author:
    Roger Kapsi, Sam Berlin
    See Also:
    Radix Tree, PATRICIA, Crit-Bit Tree, Serialized Form

    • Nested Class Summary

      • 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 KeyAnalyzer<? super K> keyAnalyzer
      The KeyAnalyzer that's being used to build the PATRICIA Trie

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()  
      java.util.Comparator<? super K> comparator()  
      boolean containsKey​(java.lang.Object k)  
      java.util.Set<java.util.Map.Entry<K,​V>> entrySet()  
      K firstKey()  
      V get​(java.lang.Object k)  
      java.util.SortedMap<K,​V> headMap​(K toKey)  
      java.util.Set<K> keySet()  
      K lastKey()  
      java.util.SortedMap<K,​V> prefixMap​(K prefix)
      Returns a view of this Trie of all elements that are prefixed by the given key.
      V put​(K key, V value)  
      V remove​(java.lang.Object k)
      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.
      java.util.Map.Entry<K,​V> select​(K key, Cursor<? super K,​? super V> cursor)
      Iterates through the Trie, starting with the entry whose bitwise value is closest in an 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()  
      java.util.SortedMap<K,​V> subMap​(K fromKey, K toKey)  
      java.util.SortedMap<K,​V> tailMap​(K fromKey)  
      java.lang.String toString()  
      java.util.Map.Entry<K,​V> traverse​(Cursor<? super K,​? super V> cursor)
      Traverses the Trie in lexicographical order.
      java.util.Collection<V> values()  

      • 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

    • Constructor Detail

      • PatriciaTrie

        public PatriciaTrie​(KeyAnalyzer<? super K> keyAnalyzer)

      • PatriciaTrie

        public PatriciaTrie​(KeyAnalyzer<? super K> keyAnalyzer,
                    java.util.Map<? extends K,​? extends V> m)

    • Method Detail

      • comparator

        public java.util.Comparator<? super K> comparator()
        Specified by:
        comparator in interface java.util.SortedMap<K,​V>

      • prefixMap

        public java.util.SortedMap<K,​V> prefixMap​(K prefix)
        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'.

        Specified by:
        prefixMap in interface Trie<K,​V>

      • firstKey

        public K firstKey()
        Specified by:
        firstKey in interface java.util.SortedMap<K,​V>

      • lastKey

        public K lastKey()
        Specified by:
        lastKey in interface java.util.SortedMap<K,​V>

      • headMap

        public java.util.SortedMap<K,​V> headMap​(K toKey)
        Specified by:
        headMap in interface java.util.SortedMap<K,​V>

      • subMap

        public java.util.SortedMap<K,​V> subMap​(K fromKey,
                                             K toKey)
        Specified by:
        subMap in interface java.util.SortedMap<K,​V>

      • tailMap

        public java.util.SortedMap<K,​V> tailMap​(K fromKey)
        Specified by:
        tailMap in interface java.util.SortedMap<K,​V>

      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Map<K,​V>
        Overrides:
        clear in class java.util.AbstractMap<K,​V>

      • size

        public int size()
        Specified by:
        size in interface java.util.Map<K,​V>
        Overrides:
        size in class java.util.AbstractMap<K,​V>

      • put

        public V put​(K key,
             V value)
        Specified by:
        put in interface java.util.Map<K,​V>
        Overrides:
        put in class java.util.AbstractMap<K,​V>

      • get

        public V get​(java.lang.Object k)
        Specified by:
        get in interface java.util.Map<K,​V>
        Overrides:
        get in class java.util.AbstractMap<K,​V>

      • select

        public java.util.Map.Entry<K,​V> select​(K key)
        Description copied from interface: Trie
        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.
        Returns:
        The Map.Entry whose key is closest in a bitwise XOR metric to the provided key.

      • select

        public java.util.Map.Entry<K,​V> select​(K key,
                                             Cursor<? super K,​? super V> cursor)
        Description copied from interface: Trie
        Iterates through the Trie, starting with the entry whose bitwise value is closest in an XOR metric to the given key. After the closest entry is found, the Trie will call select on that entry and continue calling select for each entry (traversing in order of XOR closeness, NOT lexicographically) until the cursor returns Cursor.Decision.EXIT.

        The cursor can return Cursor.Decision.CONTINUE to continue traversing.

        Cursor.Decision.REMOVE_AND_EXIT is used to remove the current element and stop traversing.

        Note: The Cursor.Decision.REMOVE operation is not supported.

        Returns:
        The entry the cursor returned Cursor.Decision.EXIT on, or null if it continued till the end.

      • containsKey

        public boolean containsKey​(java.lang.Object k)
        Specified by:
        containsKey in interface java.util.Map<K,​V>
        Overrides:
        containsKey in class java.util.AbstractMap<K,​V>

      • entrySet

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

      • keySet

        public java.util.Set<K> keySet()
        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>

      • values

        public java.util.Collection<V> values()
        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>

      • remove

        public V remove​(java.lang.Object k)
        Specified by:
        remove in interface java.util.Map<K,​V>
        Overrides:
        remove in class java.util.AbstractMap<K,​V>
        Throws:
        java.lang.ClassCastException - if provided key is of an incompatible type

      • selectKey

        public K selectKey​(K key)
        Description copied from interface: Trie
        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.
        Specified by:
        selectKey in interface Trie<K,​V>
        Returns:
        The key that is closest in a bitwise XOR metric to the provided key.

      • selectValue

        public V selectValue​(K key)
        Description copied from interface: Trie
        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.
        Specified by:
        selectValue in interface Trie<K,​V>
        Returns:
        The value whose key is closest in a bitwise XOR metric to the provided key.

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.util.AbstractMap<K,​V>