Class BTree


  • public class BTree
    extends java.lang.Object
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  BTree.Builder<V>  
      static class  BTree.Dir  
    • Constructor Summary

      Constructors 
      Constructor Description
      BTree()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static <V,​A>
      long
      accumulate​(java.lang.Object[] btree, BiLongAccumulator<A,​V> accumulator, A arg, long initialValue)  
      static <V,​A>
      long
      accumulate​(java.lang.Object[] btree, BiLongAccumulator<A,​V> accumulator, A arg, java.util.Comparator<V> comparator, V from, long initialValue)
      Walk the btree and accumulate a long value using the supplied accumulator function.
      static <V> long accumulate​(java.lang.Object[] btree, LongAccumulator<V> accumulator, long initialValue)  
      static <V> long accumulate​(java.lang.Object[] btree, LongAccumulator<V> accumulator, java.util.Comparator<V> comparator, V from, long initialValue)  
      static <V,​A>
      void
      apply​(java.lang.Object[] btree, java.util.function.BiConsumer<A,​V> function, A argument)
      Simple method to walk the btree forwards and apply a function till a stop condition is reached Private method
      static <V> void apply​(java.lang.Object[] btree, java.util.function.Consumer<V> function)
      Simple method to walk the btree forwards and apply a function till a stop condition is reached Private method
      static <V,​A>
      void
      applyLeaf​(java.lang.Object[] btree, java.util.function.BiConsumer<A,​V> function, A argument)  
      static <C,​K extends C,​V extends C>
      java.lang.Object[]
      build​(java.lang.Iterable<K> source, int size, UpdateFunction<K,​V> updateF)
      Creates a BTree containing all of the objects in the provided collection
      static <C,​K extends C,​V extends C>
      java.lang.Object[]
      build​(java.lang.Object[] source, int size, UpdateFunction<K,​V> updateF)  
      static <C,​K extends C,​V extends C>
      java.lang.Object[]
      build​(java.util.Collection<K> source, UpdateFunction<K,​V> updateF)  
      static <V> BTree.Builder<V> builder​(java.util.Comparator<? super V> comparator)  
      static <V> BTree.Builder<V> builder​(java.util.Comparator<? super V> comparator, int initialCapacity)  
      static <V> V ceil​(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)  
      static <V> int ceilIndex​(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)  
      static int depth​(java.lang.Object[] tree)  
      static java.lang.Object[] empty()  
      static boolean equals​(java.lang.Object[] a, java.lang.Object[] b)  
      static <V> V find​(java.lang.Object[] node, java.util.Comparator<? super V> comparator, V find)  
      static <V> V findByIndex​(java.lang.Object[] tree, int index)  
      static <V> int findIndex​(java.lang.Object[] node, java.util.Comparator<? super V> comparator, V find)
      Honours result semantics of Arrays.binarySearch(long[], long), as though it were performed on the tree flattened into an array
      static <V> V floor​(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)  
      static <V> int floorIndex​(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)  
      static int hashCode​(java.lang.Object[] btree)  
      static <V> V higher​(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)  
      static <V> int higherIndex​(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)  
      static boolean isEmpty​(java.lang.Object[] tree)  
      static boolean isLeaf​(java.lang.Object[] node)  
      static boolean isWellFormed​(java.lang.Object[] btree, java.util.Comparator<? extends java.lang.Object> cmp)  
      static <V> java.lang.Iterable<V> iterable​(java.lang.Object[] btree)  
      static <V> java.lang.Iterable<V> iterable​(java.lang.Object[] btree, int lb, int ub, BTree.Dir dir)  
      static <V> java.lang.Iterable<V> iterable​(java.lang.Object[] btree, BTree.Dir dir)  
      static <V> java.util.Iterator<V> iterator​(java.lang.Object[] btree)  
      static <V> java.util.Iterator<V> iterator​(java.lang.Object[] btree, int lb, int ub, BTree.Dir dir)  
      static <V> java.util.Iterator<V> iterator​(java.lang.Object[] btree, BTree.Dir dir)  
      static <V> V lower​(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)  
      static <V> int lowerIndex​(java.lang.Object[] btree, java.util.Comparator<? super V> comparator, V find)  
      static <K> java.lang.Object[] merge​(java.lang.Object[] tree1, java.lang.Object[] tree2, java.util.Comparator<? super K> comparator, UpdateFunction<K,​K> updateF)  
      static <V> void replaceInSitu​(java.lang.Object[] tree, int index, V replace)
      Modifies the provided btree directly.
      static <V> void replaceInSitu​(java.lang.Object[] node, java.util.Comparator<? super V> comparator, V find, V replace)
      Modifies the provided btree directly.
      static java.lang.Object[] singleton​(java.lang.Object value)  
      static int size​(java.lang.Object[] tree)  
      static long sizeOfStructureOnHeap​(java.lang.Object[] tree)  
      static <K,​V extends K>
      BTreeSearchIterator<K,​V>
      slice​(java.lang.Object[] btree, java.util.Comparator<? super K> comparator, int startIndex, int endIndex, BTree.Dir dir)  
      static <K,​V extends K>
      BTreeSearchIterator<K,​V>
      slice​(java.lang.Object[] btree, java.util.Comparator<? super K> comparator, K start, boolean startInclusive, K end, boolean endInclusive, BTree.Dir dir)  
      static <K,​V extends K>
      BTreeSearchIterator<K,​V>
      slice​(java.lang.Object[] btree, java.util.Comparator<? super K> comparator, K start, K end, BTree.Dir dir)  
      static <K,​V>
      BTreeSearchIterator<K,​V>
      slice​(java.lang.Object[] btree, java.util.Comparator<? super K> comparator, BTree.Dir dir)
      Returns an Iterator over the entire tree
      static int toArray​(java.lang.Object[] tree, int treeStart, int treeEnd, java.lang.Object[] target, int targetOffset)  
      static int toArray​(java.lang.Object[] tree, java.lang.Object[] target, int targetOffset)
      Fill the target array with the contents of the provided subtree, in ascending order, starting at targetOffset
      static <V> java.lang.Object[] transformAndFilter​(java.lang.Object[] btree, com.google.common.base.Function<? super V,​? extends V> function)
      Takes a btree and transforms it using the provided function, filtering out any null results.
      static int treeIndexOfBranchKey​(java.lang.Object[] root, int keyIndex)  
      static int treeIndexOffsetOfChild​(java.lang.Object[] root, int childIndex)  
      static int treeIndexOfKey​(java.lang.Object[] root, int keyIndex)
      tree index => index of key wrt all items in the tree laid out serially This version of the method permits requesting out-of-bounds indexes, -1 and size
      static int treeIndexOfLeafKey​(int keyIndex)  
      static <C,​K extends C,​V extends C>
      java.lang.Object[]
      update​(java.lang.Object[] btree, java.util.Comparator<C> comparator, java.lang.Iterable<K> updateWith, int updateWithLength, UpdateFunction<K,​V> updateF)
      Returns a new BTree with the provided collection inserting/replacing as necessary any equal items
      static <C,​K extends C,​V extends C>
      java.lang.Object[]
      update​(java.lang.Object[] btree, java.util.Comparator<C> comparator, java.util.Collection<K> updateWith, UpdateFunction<K,​V> updateF)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • BTree

        public BTree()
    • Method Detail

      • empty

        public static java.lang.Object[] empty()
      • singleton

        public static java.lang.Object[] singleton​(java.lang.Object value)
      • build

        public static <C,​K extends C,​V extends C> java.lang.Object[] build​(java.util.Collection<K> source,
                                                                                       UpdateFunction<K,​V> updateF)
      • build

        public static <C,​K extends C,​V extends C> java.lang.Object[] build​(java.lang.Iterable<K> source,
                                                                                       int size,
                                                                                       UpdateFunction<K,​V> updateF)
        Creates a BTree containing all of the objects in the provided collection
        Parameters:
        source - the items to build the tree with. MUST BE IN STRICTLY ASCENDING ORDER.
        size - the size of the source iterable
        Returns:
        a btree representing the contents of the provided iterable
      • build

        public static <C,​K extends C,​V extends C> java.lang.Object[] build​(java.lang.Object[] source,
                                                                                       int size,
                                                                                       UpdateFunction<K,​V> updateF)
      • update

        public static <C,​K extends C,​V extends C> java.lang.Object[] update​(java.lang.Object[] btree,
                                                                                        java.util.Comparator<C> comparator,
                                                                                        java.util.Collection<K> updateWith,
                                                                                        UpdateFunction<K,​V> updateF)
      • update

        public static <C,​K extends C,​V extends C> java.lang.Object[] update​(java.lang.Object[] btree,
                                                                                        java.util.Comparator<C> comparator,
                                                                                        java.lang.Iterable<K> updateWith,
                                                                                        int updateWithLength,
                                                                                        UpdateFunction<K,​V> updateF)
        Returns a new BTree with the provided collection inserting/replacing as necessary any equal items
        Type Parameters:
        V -
        Parameters:
        btree - the tree to update
        comparator - the comparator that defines the ordering over the items in the tree
        updateWith - the items to either insert / update. MUST BE IN STRICTLY ASCENDING ORDER.
        updateWithLength - then number of elements in updateWith
        updateF - the update function to apply to any pairs we are swapping, and maybe abort early
        Returns:
      • merge

        public static <K> java.lang.Object[] merge​(java.lang.Object[] tree1,
                                                   java.lang.Object[] tree2,
                                                   java.util.Comparator<? super K> comparator,
                                                   UpdateFunction<K,​K> updateF)
      • iterator

        public static <V> java.util.Iterator<V> iterator​(java.lang.Object[] btree)
      • iterator

        public static <V> java.util.Iterator<V> iterator​(java.lang.Object[] btree,
                                                         BTree.Dir dir)
      • iterator

        public static <V> java.util.Iterator<V> iterator​(java.lang.Object[] btree,
                                                         int lb,
                                                         int ub,
                                                         BTree.Dir dir)
      • iterable

        public static <V> java.lang.Iterable<V> iterable​(java.lang.Object[] btree)
      • iterable

        public static <V> java.lang.Iterable<V> iterable​(java.lang.Object[] btree,
                                                         BTree.Dir dir)
      • iterable

        public static <V> java.lang.Iterable<V> iterable​(java.lang.Object[] btree,
                                                         int lb,
                                                         int ub,
                                                         BTree.Dir dir)
      • slice

        public static <K,​V> BTreeSearchIterator<K,​V> slice​(java.lang.Object[] btree,
                                                                       java.util.Comparator<? super K> comparator,
                                                                       BTree.Dir dir)
        Returns an Iterator over the entire tree
        Type Parameters:
        V -
        Parameters:
        btree - the tree to iterate over
        dir - direction of iteration
        Returns:
      • slice

        public static <K,​V extends K> BTreeSearchIterator<K,​V> slice​(java.lang.Object[] btree,
                                                                                 java.util.Comparator<? super K> comparator,
                                                                                 K start,
                                                                                 K end,
                                                                                 BTree.Dir dir)
        Parameters:
        btree - the tree to iterate over
        comparator - the comparator that defines the ordering over the items in the tree
        start - the beginning of the range to return, inclusive (in ascending order)
        end - the end of the range to return, exclusive (in ascending order)
        dir - if false, the iterator will start at the last item and move backwards
        Returns:
        an Iterator over the defined sub-range of the tree
      • slice

        public static <K,​V extends K> BTreeSearchIterator<K,​V> slice​(java.lang.Object[] btree,
                                                                                 java.util.Comparator<? super K> comparator,
                                                                                 int startIndex,
                                                                                 int endIndex,
                                                                                 BTree.Dir dir)
        Parameters:
        btree - the tree to iterate over
        comparator - the comparator that defines the ordering over the items in the tree
        startIndex - the start index of the range to return, inclusive
        endIndex - the end index of the range to return, inclusive
        dir - if false, the iterator will start at the last item and move backwards
        Returns:
        an Iterator over the defined sub-range of the tree
      • slice

        public static <K,​V extends K> BTreeSearchIterator<K,​V> slice​(java.lang.Object[] btree,
                                                                                 java.util.Comparator<? super K> comparator,
                                                                                 K start,
                                                                                 boolean startInclusive,
                                                                                 K end,
                                                                                 boolean endInclusive,
                                                                                 BTree.Dir dir)
        Parameters:
        btree - the tree to iterate over
        comparator - the comparator that defines the ordering over the items in the tree
        start - low bound of the range
        startInclusive - inclusivity of lower bound
        end - high bound of the range
        endInclusive - inclusivity of higher bound
        dir - direction of iteration
        Returns:
        an Iterator over the defined sub-range of the tree
      • find

        public static <V> V find​(java.lang.Object[] node,
                                 java.util.Comparator<? super V> comparator,
                                 V find)
        Returns:
        the item in the tree that sorts as equal to the search argument, or null if no such item
      • replaceInSitu

        public static <V> void replaceInSitu​(java.lang.Object[] tree,
                                             int index,
                                             V replace)
        Modifies the provided btree directly. THIS SHOULD NOT BE USED WITHOUT EXTREME CARE as BTrees are meant to be immutable. Finds and replaces the item provided by index in the tree.
      • replaceInSitu

        public static <V> void replaceInSitu​(java.lang.Object[] node,
                                             java.util.Comparator<? super V> comparator,
                                             V find,
                                             V replace)
        Modifies the provided btree directly. THIS SHOULD NOT BE USED WITHOUT EXTREME CARE as BTrees are meant to be immutable. Finds and replaces the provided item in the tree. Both should sort as equal to each other (although this is not enforced)
      • findIndex

        public static <V> int findIndex​(java.lang.Object[] node,
                                        java.util.Comparator<? super V> comparator,
                                        V find)
        Honours result semantics of Arrays.binarySearch(long[], long), as though it were performed on the tree flattened into an array
        Returns:
        index of item in tree, or (-(insertion point) - 1) if not present
      • findByIndex

        public static <V> V findByIndex​(java.lang.Object[] tree,
                                        int index)
        Returns:
        the value at the index'th position in the tree, in tree order
      • lowerIndex

        public static <V> int lowerIndex​(java.lang.Object[] btree,
                                         java.util.Comparator<? super V> comparator,
                                         V find)
      • lower

        public static <V> V lower​(java.lang.Object[] btree,
                                  java.util.Comparator<? super V> comparator,
                                  V find)
      • floorIndex

        public static <V> int floorIndex​(java.lang.Object[] btree,
                                         java.util.Comparator<? super V> comparator,
                                         V find)
      • floor

        public static <V> V floor​(java.lang.Object[] btree,
                                  java.util.Comparator<? super V> comparator,
                                  V find)
      • higherIndex

        public static <V> int higherIndex​(java.lang.Object[] btree,
                                          java.util.Comparator<? super V> comparator,
                                          V find)
      • higher

        public static <V> V higher​(java.lang.Object[] btree,
                                   java.util.Comparator<? super V> comparator,
                                   V find)
      • ceilIndex

        public static <V> int ceilIndex​(java.lang.Object[] btree,
                                        java.util.Comparator<? super V> comparator,
                                        V find)
      • ceil

        public static <V> V ceil​(java.lang.Object[] btree,
                                 java.util.Comparator<? super V> comparator,
                                 V find)
      • size

        public static int size​(java.lang.Object[] tree)
      • sizeOfStructureOnHeap

        public static long sizeOfStructureOnHeap​(java.lang.Object[] tree)
      • isLeaf

        public static boolean isLeaf​(java.lang.Object[] node)
      • isEmpty

        public static boolean isEmpty​(java.lang.Object[] tree)
      • depth

        public static int depth​(java.lang.Object[] tree)
      • toArray

        public static int toArray​(java.lang.Object[] tree,
                                  java.lang.Object[] target,
                                  int targetOffset)
        Fill the target array with the contents of the provided subtree, in ascending order, starting at targetOffset
        Parameters:
        tree - source
        target - array
        targetOffset - offset in target array
        Returns:
        number of items copied (size of tree)
      • toArray

        public static int toArray​(java.lang.Object[] tree,
                                  int treeStart,
                                  int treeEnd,
                                  java.lang.Object[] target,
                                  int targetOffset)
      • transformAndFilter

        public static <V> java.lang.Object[] transformAndFilter​(java.lang.Object[] btree,
                                                                com.google.common.base.Function<? super V,​? extends V> function)
        Takes a btree and transforms it using the provided function, filtering out any null results. The result of any transformation must sort identically wrt the other results as their originals
      • equals

        public static boolean equals​(java.lang.Object[] a,
                                     java.lang.Object[] b)
      • hashCode

        public static int hashCode​(java.lang.Object[] btree)
      • treeIndexOfKey

        public static int treeIndexOfKey​(java.lang.Object[] root,
                                         int keyIndex)
        tree index => index of key wrt all items in the tree laid out serially This version of the method permits requesting out-of-bounds indexes, -1 and size
        Parameters:
        root - to calculate tree index within
        keyIndex - root-local index of key to calculate tree-index
        Returns:
        the number of items preceding the key in the whole tree of root
      • treeIndexOfLeafKey

        public static int treeIndexOfLeafKey​(int keyIndex)
        Parameters:
        keyIndex - node-local index of the key to calculate index of
        Returns:
        keyIndex; this method is here only for symmetry and clarity
      • treeIndexOfBranchKey

        public static int treeIndexOfBranchKey​(java.lang.Object[] root,
                                               int keyIndex)
        Parameters:
        root - to calculate tree-index within
        keyIndex - root-local index of key to calculate tree-index of
        Returns:
        the number of items preceding the key in the whole tree of root
      • treeIndexOffsetOfChild

        public static int treeIndexOffsetOfChild​(java.lang.Object[] root,
                                                 int childIndex)
        Parameters:
        root - to calculate tree-index within
        childIndex - root-local index of *child* to calculate tree-index of
        Returns:
        the number of items preceding the child in the whole tree of root
      • builder

        public static <V> BTree.Builder<V> builder​(java.util.Comparator<? super V> comparator)
      • builder

        public static <V> BTree.Builder<V> builder​(java.util.Comparator<? super V> comparator,
                                                   int initialCapacity)
      • isWellFormed

        public static boolean isWellFormed​(java.lang.Object[] btree,
                                           java.util.Comparator<? extends java.lang.Object> cmp)
      • applyLeaf

        public static <V,​A> void applyLeaf​(java.lang.Object[] btree,
                                                 java.util.function.BiConsumer<A,​V> function,
                                                 A argument)
      • apply

        public static <V,​A> void apply​(java.lang.Object[] btree,
                                             java.util.function.BiConsumer<A,​V> function,
                                             A argument)
        Simple method to walk the btree forwards and apply a function till a stop condition is reached Private method
        Parameters:
        btree -
        function -
      • apply

        public static <V> void apply​(java.lang.Object[] btree,
                                     java.util.function.Consumer<V> function)
        Simple method to walk the btree forwards and apply a function till a stop condition is reached Private method
        Parameters:
        btree -
        function -
      • accumulate

        public static <V,​A> long accumulate​(java.lang.Object[] btree,
                                                  BiLongAccumulator<A,​V> accumulator,
                                                  A arg,
                                                  java.util.Comparator<V> comparator,
                                                  V from,
                                                  long initialValue)
        Walk the btree and accumulate a long value using the supplied accumulator function. Iteration will stop if the accumulator function returns the sentinel values Long.MIN_VALUE or Long.MAX_VALUE If the optional from argument is not null, iteration will start from that value (or the one after it's insertion point if an exact match isn't found)
      • accumulate

        public static <V> long accumulate​(java.lang.Object[] btree,
                                          LongAccumulator<V> accumulator,
                                          java.util.Comparator<V> comparator,
                                          V from,
                                          long initialValue)
      • accumulate

        public static <V> long accumulate​(java.lang.Object[] btree,
                                          LongAccumulator<V> accumulator,
                                          long initialValue)
      • accumulate

        public static <V,​A> long accumulate​(java.lang.Object[] btree,
                                                  BiLongAccumulator<A,​V> accumulator,
                                                  A arg,
                                                  long initialValue)