Package org.apache.cassandra.db.tries

Class Trie<T>

java.lang.Object
org.apache.cassandra.db.tries.Trie<T>
Type Parameters:
T - The content type of the trie.
Direct Known Subclasses:
InMemoryReadTrie, SlicedTrie
public abstract class Trie<T> extends Object
Base class for tries. Normal users of tries will only use the public methods, which provide various transformations of the trie, conversion of its content to other formats (e.g. iterable of values), and several forms of processing. For any unimplemented data extraction operations one can build on the TrieEntriesWalker (for-each processing) and TrieEntriesIterator (to iterator) base classes, which provide the necessary mechanisms to handle walking the trie. The internal representation of tries using this interface is defined in the Trie.Cursor interface. Cursors are a method of presenting the internal structure of a trie without representing nodes as objects, which is still useful for performing the basic operations on tries (iteration, slicing/intersection and merging). A cursor will list the nodes of a trie in order, together with information about the path that was taken to reach them. To begin traversal over a trie, one must retrieve a cursor by calling cursor(). Because cursors are stateful, the traversal must always proceed from one thread. Should concurrent reads be required, separate calls to cursor() must be made. Any modification that has completed before the construction of a cursor must be visible, but any later concurrent modifications may be presented fully, partially or not at all; this also means that if multiple are made, the cursor may see any part of any subset of them. Note: This model only supports depth-first traversals. We do not currently have a need for breadth-first walks. See Trie.md for further description of the trie representation model.

  • Field Details

  • Constructor Details

    • Trie

      public Trie()

  • Method Details

    • cursor

      protected abstract Trie.Cursor<T> cursor()

    • forEachValue

      public void forEachValue(Trie.ValueConsumer<T> consumer)
      Call the given consumer on all content values in the trie in order.

    • forEachEntry

      public void forEachEntry(BiConsumer<ByteComparable,T> consumer)
      Call the given consumer on all (path, content) pairs with non-null content in the trie in order.

    • process

      public <R> R process(Trie.Walker<T,R> walker)
      Process the trie using the given Walker.

    • dump

      public String dump()
      Constuct a textual representation of the trie.

    • dump

      public String dump(Function<T,String> contentToString)
      Constuct a textual representation of the trie using the given content-to-string mapper.

    • singleton

      public static <T> Trie<T> singleton(ByteComparable b, T v)
      Returns a singleton trie mapping the given byte path to content.

    • subtrie

      public Trie<T> subtrie(ByteComparable left, boolean includeLeft, ByteComparable right, boolean includeRight)
      Returns a view of the subtrie containing everything in this trie whose keys fall between the given boundaries. The view is live, i.e. any write to the source will be reflected in the subtrie. This method will not check its arguments for correctness. The resulting trie may be empty or throw an exception if the right bound is smaller than the left.
      Parameters:
      left - the left bound for the returned subtrie. If null, the resulting subtrie is not left-bounded.
      includeLeft - whether left is an inclusive bound of not.
      right - the right bound for the returned subtrie. If null, the resulting subtrie is not right-bounded.
      includeRight - whether right is an inclusive bound of not.
      Returns:
      a view of the subtrie containing all the keys of this trie falling between left (inclusively if includeLeft) and right (inclusively if includeRight).

    • subtrie

      public Trie<T> subtrie(ByteComparable left, ByteComparable right)
      Returns a view of the subtrie containing everything in this trie whose keys fall between the given boundaries, left-inclusive and right-exclusive. The view is live, i.e. any write to the source will be reflected in the subtrie. This method will not check its arguments for correctness. The resulting trie may be empty or throw an exception if the right bound is smaller than the left. Equivalent to calling subtrie(left, true, right, false).
      Parameters:
      left - the left bound for the returned subtrie. If null, the resulting subtrie is not left-bounded.
      right - the right bound for the returned subtrie. If null, the resulting subtrie is not right-bounded.
      Returns:
      a view of the subtrie containing all the keys of this trie falling between left (inclusively if includeLeft) and right (inclusively if includeRight).

    • entrySet

      public Iterable<Map.Entry<ByteComparable,T>> entrySet()
      Returns the ordered entry set of this trie's content as an iterable.

    • entryIterator

      public Iterator<Map.Entry<ByteComparable,T>> entryIterator()
      Returns the ordered entry set of this trie's content in an iterator.

    • values

      public Iterable<T> values()
      Returns the ordered set of values of this trie as an iterable.

    • valueIterator

      public Iterator<T> valueIterator()
      Returns the ordered set of values of this trie in an iterator.

    • valuesUnordered

      public Iterable<T> valuesUnordered()
      Returns the values in any order. For some tries this is much faster than the ordered iterable.

    • mergeWith

      public Trie<T> mergeWith(Trie<T> other, Trie.MergeResolver<T> resolver)
      Constructs a view of the merge of this trie with the given one. The view is live, i.e. any write to any of the sources will be reflected in the merged view. If there is content for a given key in both sources, the resolver will be called to obtain the combination. (The resolver will not be called if there's content from only one source.)

    • throwingResolver

      public static <T> Trie.CollectionMergeResolver<T> throwingResolver()
      Returns a resolver that throws whenever more than one of the merged nodes contains content. Can be used to merge tries that are known to have distinct content paths.

    • merge

      public static <T> Trie<T> merge(Collection<? extends Trie<T>> sources, Trie.CollectionMergeResolver<T> resolver)
      Constructs a view of the merge of multiple tries. The view is live, i.e. any write to any of the sources will be reflected in the merged view. If there is content for a given key in more than one sources, the resolver will be called to obtain the combination. (The resolver will not be called if there's content from only one source.)

    • mergeDistinct

      public static <T> Trie<T> mergeDistinct(Collection<? extends Trie<T>> sources)
      Constructs a view of the merge of multiple tries, where each source must have distinct keys. The view is live, i.e. any write to any of the sources will be reflected in the merged view. If there is content for a given key in more than one sources, the merge will throw an assertion error.

    • empty

      public static <T> Trie<T> empty()