Package io.vavr.collection

Class BitMappedTrie<T>

  • All Implemented Interfaces:
    java.io.Serializable
    final class BitMappedTrie<T>
extends java.lang.Object
implements java.io.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`).

    • Constructor Detail

      • BitMappedTrie

        private BitMappedTrie​(ArrayType<T> type,
                      java.lang.Object array,
                      int offset,
                      int length,
                      int depthShift)

    • Method Detail

      • firstDigit

        static int firstDigit​(int num,
                      int depthShift)

      • digit

        static int digit​(int num,
                 int depthShift)

      • lastDigit

        static int lastDigit​(int num)

      • treeSize

        private static int treeSize​(int branchCount,
                            int depthShift)

      • ofAll

        static <T> BitMappedTrie<T> ofAll​(java.lang.Object array)

      • ofAll

        private static <T> BitMappedTrie<T> ofAll​(java.lang.Object array,
                                          ArrayType<T> type,
                                          int size)

      • prependAll

        BitMappedTrie<T> prependAll​(java.lang.Iterable<? extends T> iterable)

      • prepend

        private BitMappedTrie<T> prepend​(java.util.Iterator<? extends T> iterator,
                                 int size)

      • isFullLeft

        private boolean isFullLeft()

      • prependToLeaf

        private NodeModifier prependToLeaf​(java.util.Iterator<? extends T> iterator)

      • appendAll

        BitMappedTrie<T> appendAll​(java.lang.Iterable<? extends T> iterable)

      • append

        private BitMappedTrie<T> append​(java.util.Iterator<? extends T> iterator,
                                int size)

      • isFullRight

        private boolean isFullRight()

      • appendToLeaf

        private NodeModifier appendToLeaf​(java.util.Iterator<? extends T> iterator,
                                  int leafSize)

      • arePointingToSameLeaf

        private boolean arePointingToSameLeaf​(int i,
                                      int j)

      • collapsed

        private static <T> BitMappedTrie<T> collapsed​(ArrayType<T> type,
                                              java.lang.Object array,
                                              int offset,
                                              int length,
                                              int shift)

      • modify

        private java.lang.Object modify​(java.lang.Object root,
                                int depthShift,
                                int index,
                                NodeModifier node,
                                NodeModifier leaf)

      • modifyNonLeaf

        private java.lang.Object modifyNonLeaf​(java.lang.Object root,
                                       int depthShift,
                                       int index,
                                       NodeModifier node,
                                       NodeModifier leaf)

      • setNewNode

        private java.lang.Object setNewNode​(NodeModifier node,
                                    int previousIndex,
                                    java.lang.Object array,
                                    int offset)

      • get

        T get​(int index)

      • getLeaf

        java.lang.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 java.lang.Object getLeafGeneral​(int index)

      • getMin

        private int getMin​(int start,
                   int index,
                   java.lang.Object leaf)

      • filter

        BitMappedTrie<T> filter​(java.util.function.Predicate<? super T> predicate)

      • filter

        private int filter​(java.util.function.Predicate<? super T> predicate,
                   java.lang.Object results,
                   int index,
                   T leaf,
                   int start,
                   int end)

      • map

        <U> BitMappedTrie<U> map​(java.util.function.Function<? super T,​? extends U> mapper)

      • map

        private <U> int map​(java.util.function.Function<? super T,​? extends U> mapper,
                    java.lang.Object results,
                    int index,
                    T leaf,
                    int start,
                    int end)

      • length

        int length()