Class BitMappedTrie<T>

java.lang.Object
io.vavr.collection.BitMappedTrie<T>
All Implemented Interfaces:
Serializable

final class BitMappedTrie<T> extends Object implements Serializable
A `bit-mapped trie` is a very wide and shallow tree (for integer indices the depth will be `≤6`). Each node has a maximum of `32` children (configurable). Access to a given position is done by converting the index to a base 32 number and using each digit to descend down the tree. Modifying the tree is done similarly, but along the way the path is copied, returning a new root every time. `Append` inserts in the last leaf, or if the tree is full from the right, it adds another layer on top of it (the old root will be the first of the new one). `Prepend` is done similarly, but an offset is needed, because adding a new top node (where the current root would be the last node of the new root) shifts the indices by half of the current tree's full size. The `offset` shifts them back to the correct index. `Slice` is done by trimming the path from the root and discarding any `leading`/`trailing` values in effectively constant time (without memory leak, as in `Java`/`Clojure`).
  • Field Details

    • BRANCHING_BASE

      static final int BRANCHING_BASE
      See Also:
    • BRANCHING_FACTOR

      static final int BRANCHING_FACTOR
      See Also:
    • BRANCHING_MASK

      static final int BRANCHING_MASK
      See Also:
    • serialVersionUID

      private static final long serialVersionUID
      See Also:
    • EMPTY

      private static final BitMappedTrie<?> EMPTY
    • type

      final ArrayType<T> type
    • array

      private final Object array
    • offset

      private final int offset
    • length

      private final int length
    • depthShift

      private final int depthShift
  • Constructor Details

    • BitMappedTrie

      private BitMappedTrie(ArrayType<T> type, Object array, int offset, int length, int depthShift)
  • Method Details

    • firstDigit

      static int firstDigit(int num, int depthShift)
    • digit

      static int digit(int num, int depthShift)
    • lastDigit

      static int lastDigit(int num)
    • empty

      static <T> BitMappedTrie<T> empty()
    • treeSize

      private static int treeSize(int branchCount, int depthShift)
    • ofAll

      static <T> BitMappedTrie<T> ofAll(Object array)
    • ofAll

      private static <T> BitMappedTrie<T> ofAll(Object array, ArrayType<T> type, int size)
    • boxed

      private BitMappedTrie<T> boxed()
    • prependAll

      BitMappedTrie<T> prependAll(Iterable<? extends T> iterable)
    • prepend

      private BitMappedTrie<T> prepend(Iterator<? extends T> iterator, int size)
    • isFullLeft

      private boolean isFullLeft()
    • prependToLeaf

      private NodeModifier prependToLeaf(Iterator<? extends T> iterator)
    • appendAll

      BitMappedTrie<T> appendAll(Iterable<? extends T> iterable)
    • append

      private BitMappedTrie<T> append(Iterator<? extends T> iterator, int size)
    • isFullRight

      private boolean isFullRight()
    • appendToLeaf

      private NodeModifier appendToLeaf(Iterator<? extends T> iterator, int leafSize)
    • update

      BitMappedTrie<T> update(int index, T element)
    • updateLeafWith

      private NodeModifier updateLeafWith(ArrayType<T> type, T element)
    • drop

      BitMappedTrie<T> drop(int n)
    • take

      BitMappedTrie<T> take(int n)
    • arePointingToSameLeaf

      private boolean arePointingToSameLeaf(int i, int j)
    • collapsed

      private static <T> BitMappedTrie<T> collapsed(ArrayType<T> type, Object array, int offset, int length, int shift)
    • modify

      private Object modify(Object root, int depthShift, int index, NodeModifier node, NodeModifier leaf)
    • modifyNonLeaf

      private Object modifyNonLeaf(Object root, int depthShift, int index, NodeModifier node, NodeModifier leaf)
    • setNewNode

      private Object setNewNode(NodeModifier node, int previousIndex, Object array, int offset)
    • get

      T get(int index)
    • getLeaf

      Object getLeaf(int index)
      fetch the leaf, corresponding to the given index. Node: the offset and length should be taken into consideration as there may be leading and trailing garbage. Also, the returned array is mutable, but should not be mutated!
    • getLeafGeneral

      private Object getLeafGeneral(int index)
    • iterator

      Iterator<T> iterator()
    • visit

      <T2> int visit(LeafVisitor<T2> visitor)
    • getMin

      private int getMin(int start, int index, Object leaf)
    • filter

      BitMappedTrie<T> filter(Predicate<? super T> predicate)
    • filter

      private int filter(Predicate<? super T> predicate, Object results, int index, T leaf, int start, int end)
    • map

      <U> BitMappedTrie<U> map(Function<? super T,? extends U> mapper)
    • map

      private <U> int map(Function<? super T,? extends U> mapper, Object results, int index, T leaf, int start, int end)
    • length

      int length()