Package org.apache.cassandra.utils.btree
Class BTree
- java.lang.Object
-
- org.apache.cassandra.utils.btree.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>
longaccumulate(java.lang.Object[] btree, BiLongAccumulator<A,V> accumulator, A arg, long initialValue)
static <V,A>
longaccumulate(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>
voidapply(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 methodstatic <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 methodstatic <V,A>
voidapplyLeaf(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 collectionstatic <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 ofArrays.binarySearch(long[], long)
, as though it were performed on the tree flattened into an arraystatic <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 treestatic 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 targetOffsetstatic <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 sizestatic 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 itemsstatic <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)
-
-
-
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 updatecomparator
- the comparator that defines the ordering over the items in the treeupdateWith
- the items to either insert / update. MUST BE IN STRICTLY ASCENDING ORDER.updateWithLength
- then number of elements in updateWithupdateF
- 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 overdir
- 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 overcomparator
- the comparator that defines the ordering over the items in the treestart
- 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 overcomparator
- the comparator that defines the ordering over the items in the treestartIndex
- the start index of the range to return, inclusiveendIndex
- the end index of the range to return, inclusivedir
- 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 overcomparator
- the comparator that defines the ordering over the items in the treestart
- low bound of the rangestartInclusive
- inclusivity of lower boundend
- high bound of the rangeendInclusive
- inclusivity of higher bounddir
- 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 ofArrays.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
- sourcetarget
- arraytargetOffset
- 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 withinkeyIndex
- 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 withinkeyIndex
- 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 withinchildIndex
- 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)
-
-