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

Interface Trie<K,​V>

  • All Superinterfaces:
    java.util.Map<K,​V>, java.util.SortedMap<K,​V>
    All Known Implementing Classes:
    PatriciaTrie
    public interface Trie<K,​V>
extends java.util.SortedMap<K,​V>
    Defines the interface for a prefix tree, an ordered tree data structure. For more information, see Tries.
    Author:
    Roger Kapsi, Sam Berlin

    • Nested Class Summary

      • Nested classes/interfaces inherited from interface java.util.Map

        java.util.Map.Entry<K extends java.lang.Object,​V extends java.lang.Object>

    • Method Summary

      All Methods Instance Methods Abstract Methods 
      Modifier and Type Method Description
      java.util.SortedMap<K,​V> prefixMap​(K prefix)
      Returns a view of this Trie of all elements that are prefixed by the given key.
      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.
      java.util.Map.Entry<K,​V> traverse​(Cursor<? super K,​? super V> cursor)
      Traverses the Trie in lexicographical order.

      • Methods inherited from interface java.util.Map

        clear, compute, computeIfAbsent, computeIfPresent, containsKey, containsValue, equals, forEach, get, getOrDefault, hashCode, isEmpty, merge, put, putAll, putIfAbsent, remove, remove, replace, replace, replaceAll, size

      • Methods inherited from interface java.util.SortedMap

        comparator, entrySet, firstKey, headMap, keySet, lastKey, subMap, tailMap, values

    • Method Detail

      • select

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

      • selectKey

        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.
        Returns:
        The key that is closest in a bitwise XOR metric to the provided key.

      • selectValue

        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.
        Returns:
        The value whose key is closest in a bitwise XOR metric to the provided key.

      • select

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

      • prefixMap

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