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

Class PatriciaTrie<K,V>

java.lang.Object
java.util.AbstractMap<K,V>
org.apache.cassandra.index.sasi.utils.trie.PatriciaTrie<K,V>
All Implemented Interfaces:
Serializable, Map<K,V>, SortedMap<K,V>, Trie<K,V>
public class PatriciaTrie<K,V> extends AbstractMap<K,V> implements 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:

  • Field Details

  • Constructor Details

    • PatriciaTrie

      public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer)

    • PatriciaTrie

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

  • Method Details

    • comparator

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

    • prefixMap

      public 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 SortedMap<K,V>

    • lastKey

      public K lastKey()
      Specified by:
      lastKey in interface SortedMap<K,V>

    • headMap

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

    • subMap

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

    • tailMap

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

    • clear

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

    • size

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

    • put

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

    • get

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

    • select

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

    • traverse

      public Map.Entry<K,V> traverse(Cursor<? super K,? super V> cursor)
      Description copied from interface: Trie
      Traverses the Trie in lexicographical order. Cursor.select(java.util.Map.Entry) will be called on each entry.

      The traversal will stop when the cursor returns Cursor.Decision.EXIT, Cursor.Decision.CONTINUE is used to continue traversing and Cursor.Decision.REMOVE is used to remove the element that was selected and continue traversing.

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

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

    • containsKey

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

    • 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 class AbstractMap<K,V>

    • keySet

      public Set<K> keySet()
      Specified by:
      keySet in interface Map<K,V>
      Specified by:
      keySet in interface SortedMap<K,V>
      Overrides:
      keySet in class AbstractMap<K,V>

    • values

      public Collection<V> values()
      Specified by:
      values in interface Map<K,V>
      Specified by:
      values in interface SortedMap<K,V>
      Overrides:
      values in class AbstractMap<K,V>

    • remove

      public V remove(Object k)
      Specified by:
      remove in interface Map<K,V>
      Overrides:
      remove in class AbstractMap<K,V>
      Throws:
      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 String toString()
      Overrides:
      toString in class AbstractMap<K,V>