You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by be...@apache.org on 2024/02/14 15:44:23 UTC
(cassandra-accord) branch trunk updated: copy over BTree (cleanup/share later)
This is an automated email from the ASF dual-hosted git repository.
benedict pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/cassandra-accord.git
The following commit(s) were added to refs/heads/trunk by this push:
new 150a1fb copy over BTree (cleanup/share later)
150a1fb is described below
commit 150a1fb0d624a9e349f36a5c71d6294373b145e2
Author: Benedict Elliott Smith <be...@apache.org>
AuthorDate: Wed Feb 14 15:43:56 2024 +0000
copy over BTree (cleanup/share later)
---
.../java/accord/utils/btree/AbstractBTreeMap.java | 157 +
.../src/main/java/accord/utils/btree/BTree.java | 3995 ++++++++++++++++++++
.../main/java/accord/utils/btree/BTreeBiMap.java | 102 +
.../src/main/java/accord/utils/btree/BTreeMap.java | 230 ++
.../java/accord/utils/btree/BTreeMultimap.java | 213 ++
.../main/java/accord/utils/btree/BTreeRemoval.java | 345 ++
.../accord/utils/btree/BTreeSearchIterator.java | 29 +
.../src/main/java/accord/utils/btree/BTreeSet.java | 682 ++++
.../main/java/accord/utils/btree/BulkIterator.java | 110 +
.../utils/btree/FullBTreeSearchIterator.java | 159 +
.../accord/utils/btree/IndexedSearchIterator.java | 38 +
.../utils/btree/LeafBTreeSearchIterator.java | 136 +
.../main/java/accord/utils/btree/NodeCursor.java | 198 +
.../java/accord/utils/btree/SearchIterator.java | 33 +
.../accord/utils/btree/TinyThreadLocalPool.java | 83 +
.../main/java/accord/utils/btree/TreeCursor.java | 269 ++
.../java/accord/utils/btree/UpdateFunction.java | 83 +
17 files changed, 6862 insertions(+)
diff --git a/accord-core/src/main/java/accord/utils/btree/AbstractBTreeMap.java b/accord-core/src/main/java/accord/utils/btree/AbstractBTreeMap.java
new file mode 100644
index 0000000..c9a2793
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/AbstractBTreeMap.java
@@ -0,0 +1,157 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package accord.utils.btree;
+
+import java.util.AbstractMap;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+
+import com.google.common.collect.ImmutableSet;
+
+public abstract class AbstractBTreeMap<K, V> extends AbstractMap<K, V>
+{
+ protected final Object[] tree;
+ protected final KeyComparator<K, V> comparator;
+
+ protected AbstractBTreeMap(Object[] tree, KeyComparator<K, V> comparator)
+ {
+ this.tree = tree;
+ this.comparator = comparator;
+ }
+
+ /**
+ * return a new map containing provided key and value
+ *
+ * @throws IllegalStateException if the key already exists in the map
+ */
+ public abstract AbstractBTreeMap<K, V> with(K key, V value);
+
+ /**
+ * returns a new map containing provided key and value - replaces existing key
+ */
+ public abstract AbstractBTreeMap<K, V> withForce(K key, V value);
+
+ /**
+ * returns a new map without key
+ */
+ public abstract AbstractBTreeMap<K, V> without(K key);
+
+ @Override
+ public int size()
+ {
+ return BTree.size(tree);
+ }
+
+ @Override
+ public boolean isEmpty()
+ {
+ return BTree.isEmpty(tree);
+ }
+
+ @Override
+ public boolean containsKey(Object key)
+ {
+ return get(key) != null;
+ }
+
+ @Override
+ public boolean containsValue(Object value)
+ {
+ Iterator<Entry<K, V>> iter = BTree.iterator(tree);
+ while (iter.hasNext())
+ {
+ Entry<K, V> entry = iter.next();
+ if (entry.getValue().equals(value))
+ return true;
+ }
+ return false;
+ }
+
+ @SuppressWarnings("unchecked")
+ public V get(Object key)
+ {
+ if (key == null)
+ throw new NullPointerException();
+ Entry<K, V> entry = BTree.find(tree, comparator, new Entry<>((K)key, null));
+ if (entry != null)
+ return entry.getValue();
+ return null;
+ }
+
+ private Set<K> keySet = null;
+ @Override
+ public Set<K> keySet()
+ {
+ if (keySet == null)
+ keySet = BTreeSet.wrap(BTree.transformAndFilter(tree, (entry) -> ((Map.Entry<K, V>)entry).getKey()), comparator.keyComparator);
+ return keySet;
+ }
+
+ @Override
+ public Set<V> values()
+ {
+ ImmutableSet.Builder<V> b = ImmutableSet.builder();
+ for (Map.Entry<K, V> e : entrySet())
+ b.add(e.getValue());
+ return b.build();
+ }
+
+ @Override
+ public Set<Map.Entry<K, V>> entrySet()
+ {
+ return BTreeSet.wrap(tree, comparator);
+ }
+
+ public V put(K key, V value) { throw new UnsupportedOperationException(); }
+ public V forcePut(K ignoredKey, V ignoredVal) { throw new UnsupportedOperationException(); }
+ public V remove(Object key) { throw new UnsupportedOperationException();}
+ public void putAll(Map<? extends K, ? extends V> m) { throw new UnsupportedOperationException(); }
+ public void clear() { throw new UnsupportedOperationException(); }
+ public Map.Entry<K, V> pollFirstEntry() { throw new UnsupportedOperationException(); }
+ public Map.Entry<K, V> pollLastEntry() { throw new UnsupportedOperationException(); }
+
+ protected static class KeyComparator<K, V> implements Comparator<Map.Entry<K, V>>
+ {
+ protected final Comparator<K> keyComparator;
+
+ protected KeyComparator(Comparator<K> keyComparator)
+ {
+ this.keyComparator = keyComparator;
+ }
+
+ @Override
+ public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2)
+ {
+ return keyComparator.compare(o1.getKey(), o2.getKey());
+ }
+ }
+
+ static class Entry<K, V> extends SimpleEntry<K, V>
+ {
+ public Entry(K key, V value)
+ {
+ super(key, value);
+ }
+
+ public V setValue(V value) { throw new UnsupportedOperationException(); }
+
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/BTree.java b/accord-core/src/main/java/accord/utils/btree/BTree.java
new file mode 100644
index 0000000..8d644e0
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/BTree.java
@@ -0,0 +1,3995 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package accord.utils.btree;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.Objects;
+import java.util.SortedSet;
+import java.util.function.BiConsumer;
+import java.util.function.BiFunction;
+import java.util.function.Consumer;
+import java.util.function.Function;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Iterators;
+import com.google.common.collect.Ordering;
+
+import static java.lang.Math.max;
+import static java.lang.Math.min;
+
+public class BTree
+{
+ /**
+ * The {@code BRANCH_FACTOR} is defined as the maximum number of children of each branch, with between
+ * BRANCH_FACTOR/2-1 and BRANCH_FACTOR-1 keys being stored in every node. This yields a minimum tree size of
+ * {@code (BRANCH_FACTOR/2)^height - 1} and a maximum tree size of {@code BRANCH_FACTOR^height - 1}.
+ * <p>
+ * Branches differ from leaves only in that they contain a suffix region containing the child nodes that occur
+ * either side of the keys, and a sizeMap in the last position, permitting seeking by index within the tree.
+ * Nodes are disambiguated by the length of the array that represents them: an even number is a branch, odd a leaf.
+ * <p>
+ * Leaf Nodes are represented by an odd-length array of keys, with the final element possibly null, i.e.
+ * Object[V1, V2, ...,null?]
+ * <p>
+ * Branch nodes: Object[V1, V2, ..., child[<V1.key], child[<V2.key], ..., child[< Inf], sizeMap]
+ * Each child is either a branch or leaf, i.e., always an Object[].
+ * The key elements in a branch node occupy the first half of the array (minus one)
+ * <p>
+ * BTrees are immutable; updating one returns a new tree that reuses unmodified nodes.
+ * <p>
+ * There are no references back to a parent node from its children (this would make it impossible to re-use
+ * subtrees when modifying the tree, since the modified tree would need new parent references).
+ * Instead, we store these references in a Path as needed when navigating the tree.
+ */
+ public static final int BRANCH_SHIFT = 5;
+
+ private static final int BRANCH_FACTOR = 1 << BRANCH_SHIFT;
+ public static final int MIN_KEYS = BRANCH_FACTOR / 2 - 1;
+ public static final int MAX_KEYS = BRANCH_FACTOR - 1;
+
+ // An empty BTree Leaf - which is the same as an empty BTree
+ private static final Object[] EMPTY_LEAF = new Object[1];
+
+ private static final int[][] DENSE_SIZE_MAPS = buildBalancedSizeMaps(BRANCH_SHIFT);
+
+ /**
+ * Represents the direction of iteration.
+ */
+ public enum Dir
+ {
+ ASC, DESC;
+
+ public Dir invert()
+ {
+ return this == ASC ? DESC : ASC;
+ }
+
+ public static Dir desc(boolean desc)
+ {
+ return desc ? DESC : ASC;
+ }
+ }
+
+ /**
+ * Returns an empty BTree
+ *
+ * @return an empty BTree
+ */
+ public static Object[] empty()
+ {
+ return EMPTY_LEAF;
+ }
+
+ /**
+ * Create a BTree containing only the specified object
+ *
+ * @return an new BTree containing only the specified object
+ */
+ public static Object[] singleton(Object value)
+ {
+ return new Object[]{ value };
+ }
+
+ public static <C, I extends C, O extends C> Object[] build(BulkIterator<I> source, int size, UpdateFunction<I, O> updateF)
+ {
+ assert size >= 0;
+ if (size == 0)
+ return EMPTY_LEAF;
+
+ if (size <= MAX_KEYS)
+ return buildLeaf(source, size, updateF);
+
+ return buildRoot(source, size, updateF);
+ }
+
+ /**
+ * Build a leaf with {@code size} elements taken in bulk from {@code insert}, and apply {@code updateF} to these elements
+ */
+ private static <C, I extends C, O extends C> Object[] buildLeaf(BulkIterator<I> insert,
+ int size,
+ UpdateFunction<I, O> updateF)
+ {
+ Object[] values = new Object[size | 1]; // ensure that we have an odd-length array
+ insert.fetch(values, 0, size);
+ if (!isSimple(updateF))
+ {
+ for (int i = 0; i < size; i++)
+ values[i] = updateF.insert((I) values[i]);
+ }
+ return values;
+ }
+
+ /**
+ * Build a leaf with {@code size} elements taken in bulk from {@code insert}, and apply {@code updateF} to these elements
+ * Do not invoke {@code updateF.onAllocated}. Used by {@link #buildPerfectDenseWithoutSizeTracking} which
+ * track the size for the entire tree they build in order to save on work.
+ */
+ private static <C, I extends C, O extends C> Object[] buildLeafWithoutSizeTracking(BulkIterator<I> insert, int size, UpdateFunction<I, O> updateF)
+ {
+ Object[] values = new Object[size | 1]; // ensure that we have an odd-length array
+ insert.fetch(values, 0, size);
+ if (!isSimple(updateF))
+ {
+ for (int i = 0; i < size; i++)
+ values[i] = updateF.insert((I) values[i]);
+ }
+ return values;
+ }
+
+ /**
+ * Build a root node from the first {@code size} elements from {@code source}, applying {@code updateF} to those elements.
+ * A root node is permitted to have as few as two children, if a branch (i.e. if {@code size > MAX_SIZE}.
+ */
+ private static <C, I extends C, O extends C> Object[] buildRoot(BulkIterator<I> source, int size, UpdateFunction<I, O> updateF)
+ {
+ // first calculate the minimum height needed for this size of tree
+ int height = minHeight(size);
+ assert height > 1;
+ assert height * BRANCH_SHIFT < 32;
+
+ int denseChildSize = denseSize(height - 1);
+ // Divide the size by the child size + 1, adjusting size by +1 to compensate for not having an upper key on the
+ // last child and rounding up, i.e. (size + 1 + div - 1) / div == size / div + 1 where div = childSize + 1
+ int childCount = size / (denseChildSize + 1) + 1;
+
+ return buildMaximallyDense(source, childCount, size, height, updateF);
+ }
+
+ /**
+ * Build a tree containing only dense nodes except at most two on any level. This matches the structure that
+ * a FastBuilder would create, with some optimizations in constructing the dense nodes.
+ * <p>
+ * We do this by repeatedly constructing fully dense children until we reach a threshold, chosen so that we would
+ * not be able to create another child with fully dense children and at least MIN_KEYS keys. After the threshold,
+ * the remainder may fit a single node, or is otherwise split roughly halfway to create one child with at least
+ * MIN_KEYS+1 fully dense children, and one that has at least MIN_KEYS-1 fully dense and up to two non-dense.
+ */
+ private static <C, I extends C, O extends C> Object[] buildMaximallyDense(BulkIterator<I> source,
+ int childCount,
+ int size,
+ int height,
+ UpdateFunction<I, O> updateF)
+ {
+ assert childCount <= MAX_KEYS + 1;
+
+ int keyCount = childCount - 1;
+ int[] sizeMap = new int[childCount];
+ Object[] branch = new Object[childCount * 2];
+
+ if (height == 2)
+ {
+ // we use the _exact same logic_ as below, only we invoke buildLeaf
+ int remaining = size;
+ int threshold = MAX_KEYS + 1 + MIN_KEYS;
+ int i = 0;
+ while (remaining >= threshold)
+ {
+ branch[keyCount + i] = buildLeaf(source, MAX_KEYS, updateF);
+ branch[i] = isSimple(updateF) ? source.next() : updateF.insert(source.next());
+ remaining -= MAX_KEYS + 1;
+ sizeMap[i++] = size - remaining - 1;
+ }
+ if (remaining > MAX_KEYS)
+ {
+ int childSize = remaining / 2;
+ branch[keyCount + i] = buildLeaf(source, childSize, updateF);
+ branch[i] = isSimple(updateF) ? source.next() : updateF.insert(source.next());
+ remaining -= childSize + 1;
+ sizeMap[i++] = size - remaining - 1;
+ }
+ branch[keyCount + i] = buildLeaf(source, remaining, updateF);
+ sizeMap[i++] = size;
+ assert i == childCount;
+ }
+ else
+ {
+ --height;
+ int denseChildSize = denseSize(height);
+ int denseGrandChildSize = denseSize(height - 1);
+ // The threshold is the point after which we can't add a dense child and still add another child with
+ // at least MIN_KEYS fully dense children plus at least one more key.
+ int threshold = denseChildSize + 1 + MIN_KEYS * (denseGrandChildSize + 1);
+ int remaining = size;
+ int i = 0;
+ // Add dense children until we reach the threshold.
+ while (remaining >= threshold)
+ {
+ branch[keyCount + i] = buildPerfectDense(source, height, updateF);
+ branch[i] = isSimple(updateF) ? source.next() : updateF.insert(source.next());
+ remaining -= denseChildSize + 1;
+ sizeMap[i++] = size - remaining - 1;
+ }
+ // At this point the remainder either fits in one child, or too much for one but too little for one
+ // perfectly dense and a second child with enough grandchildren to be valid. In the latter case, the
+ // remainder should be split roughly in half, where the first child only has dense grandchildren.
+ if (remaining > denseChildSize)
+ {
+ int grandChildCount = remaining / ((denseGrandChildSize + 1) * 2);
+ assert grandChildCount >= MIN_KEYS + 1;
+ int childSize = grandChildCount * (denseGrandChildSize + 1) - 1;
+ branch[keyCount + i] = buildMaximallyDense(source, grandChildCount, childSize, height, updateF);
+ branch[i] = isSimple(updateF) ? source.next() : updateF.insert(source.next());
+ remaining -= childSize + 1;
+ sizeMap[i++] = size - remaining - 1;
+ }
+ // Put the remainder in the last child, it is now guaranteed to fit and have the required minimum of children.
+ int grandChildCount = remaining / (denseGrandChildSize + 1) + 1;
+ assert grandChildCount >= MIN_KEYS + 1;
+ int childSize = remaining;
+ branch[keyCount + i] = buildMaximallyDense(source, grandChildCount, childSize, height, updateF);
+ sizeMap[i++] = size;
+ assert i == childCount;
+ }
+
+ branch[2 * keyCount + 1] = sizeMap;
+ return branch;
+ }
+
+ private static <C, I extends C, O extends C> Object[] buildPerfectDense(BulkIterator<I> source, int height, UpdateFunction<I, O> updateF)
+ {
+ Object[] result = buildPerfectDenseWithoutSizeTracking(source, height, updateF);
+ return result;
+ }
+
+ /**
+ * Build a tree of size precisely {@code branchFactor^height - 1}
+ */
+ private static <C, I extends C, O extends C> Object[] buildPerfectDenseWithoutSizeTracking(BulkIterator<I> source, int height, UpdateFunction<I, O> updateF)
+ {
+ int keyCount = (1 << BRANCH_SHIFT) - 1;
+ Object[] node = new Object[(1 << BRANCH_SHIFT) * 2];
+
+ if (height == 2)
+ {
+ int childSize = treeSize2n(1, BRANCH_SHIFT);
+ for (int i = 0; i < keyCount; i++)
+ {
+ node[keyCount + i] = buildLeafWithoutSizeTracking(source, childSize, updateF);
+ node[i] = isSimple(updateF) ? source.next() : updateF.insert(source.next());
+ }
+ node[2 * keyCount] = buildLeafWithoutSizeTracking(source, childSize, updateF);
+ }
+ else
+ {
+ for (int i = 0; i < keyCount; i++)
+ {
+ Object[] child = buildPerfectDenseWithoutSizeTracking(source, height - 1, updateF);
+ node[keyCount + i] = child;
+ node[i] = isSimple(updateF) ? source.next() : updateF.insert(source.next());
+ }
+ node[2 * keyCount] = buildPerfectDenseWithoutSizeTracking(source, height - 1, updateF);
+ }
+ node[keyCount * 2 + 1] = DENSE_SIZE_MAPS[height - 2];
+
+ return node;
+ }
+
+ public static <Compare> Object[] update(Object[] toUpdate, Object[] insert, Comparator<? super Compare> comparator)
+ {
+ return BTree.<Compare, Compare, Compare>update(toUpdate, insert, comparator, UpdateFunction.noOp());
+ }
+
+ /**
+ * Inserts {@code insert} into {@code update}, applying {@code updateF} to each new item in {@code insert},
+ * as well as any matched items in {@code update}.
+ * <p>
+ * Note that {@code UpdateFunction.noOp} is assumed to indicate a lack of interest in which value survives.
+ */
+ public static <Compare, Existing extends Compare, Insert extends Compare> Object[] update(Object[] toUpdate,
+ Object[] insert,
+ Comparator<? super Compare> comparator,
+ UpdateFunction<Insert, Existing> updateF)
+ {
+ // perform some initial obvious optimisations
+ if (isEmpty(insert))
+ return toUpdate; // do nothing if update is empty
+
+
+ if (isEmpty(toUpdate))
+ {
+ if (isSimple(updateF))
+ return insert; // if update is empty and updateF is trivial, return our new input
+
+ // if update is empty and updateF is non-trivial, perform a simple fast transformation of the input tree
+ insert = BTree.transform(insert, updateF::insert);
+ return insert;
+ }
+
+ if (isLeaf(toUpdate) && isLeaf(insert))
+ {
+ // if both are leaves, perform a tight-loop leaf variant of update
+ // possibly flipping the input order if sizes suggest and updateF permits
+ if (updateF == (UpdateFunction) UpdateFunction.noOp && toUpdate.length < insert.length)
+ {
+ Object[] tmp = toUpdate;
+ toUpdate = insert;
+ insert = tmp;
+ }
+ Object[] merged = updateLeaves(toUpdate, insert, comparator, updateF);
+ return merged;
+ }
+
+ if (!isLeaf(insert) && isSimple(updateF))
+ {
+ // consider flipping the order of application, if update is much larger than insert and applying unary no-op
+ int updateSize = size(toUpdate);
+ int insertSize = size(insert);
+ int scale = Integer.numberOfLeadingZeros(updateSize) - Integer.numberOfLeadingZeros(insertSize);
+ if (scale >= 4)
+ {
+ // i.e. at roughly 16x the size, or one tier deeper - very arbitrary, should pick more carefully
+ // experimentally, at least at 64x the size the difference in performance is ~10x
+ Object[] tmp = insert;
+ insert = toUpdate;
+ toUpdate = tmp;
+ if (updateF != (UpdateFunction) UpdateFunction.noOp)
+ updateF = ((UpdateFunction.Simple) updateF).flip();
+ }
+ }
+
+ try (Updater<Compare, Existing, Insert> updater = Updater.get())
+ {
+ return updater.update(toUpdate, insert, comparator, updateF);
+ }
+ }
+
+ /**
+ * A fast tight-loop variant of updating one btree with another, when both are leaves.
+ */
+ public static <Compare, Existing extends Compare, Insert extends Compare> Object[] updateLeaves(Object[] unode,
+ Object[] inode,
+ Comparator<? super Compare> comparator,
+ UpdateFunction<Insert, Existing> updateF)
+ {
+ int upos = -1, usz = sizeOfLeaf(unode);
+ Existing uk = (Existing) unode[0];
+ int ipos = 0, isz = sizeOfLeaf(inode);
+ Insert ik = (Insert) inode[0];
+
+ Existing merged = null;
+ int c = -1;
+ while (c <= 0) // optimistic: find the first point in the original leaf that is modified (if any)
+ {
+ if (c < 0)
+ {
+ upos = exponentialSearch(comparator, unode, upos + 1, usz, ik);
+ c = upos < 0 ? 1 : 0; // positive or zero
+ if (upos < 0)
+ upos = -(1 + upos);
+ if (upos == usz)
+ break;
+ uk = (Existing) unode[upos];
+ }
+ else // c == 0
+ {
+ merged = updateF.merge(uk, ik);
+ if (merged != uk)
+ break;
+ if (++ipos == isz)
+ return unode;
+ if (++upos == usz)
+ break;
+ c = comparator.compare(uk = (Existing) unode[upos], ik = (Insert) inode[ipos]);
+ }
+ }
+
+ // exit conditions: c == 0 && merged != uk
+ // or: c > 0
+ // or: upos == usz
+
+ try (FastBuilder<Existing> builder = fastBuilder())
+ {
+ if (upos > 0)
+ {
+ // copy any initial section that is unmodified
+ builder.leaf().copy(unode, 0, upos);
+ }
+
+ // handle prior loop's exit condition
+ // we always have either an ik, or an ik merged with uk, to handle
+ if (upos < usz)
+ {
+ if (c == 0)
+ {
+ builder.add(merged);
+ if (++upos < usz)
+ uk = (Existing) unode[upos];
+ }
+ else // c > 0
+ {
+ builder.add(updateF.insert(ik));
+ }
+ if (++ipos < isz)
+ ik = (Insert) inode[ipos];
+
+ if (upos < usz && ipos < isz)
+ {
+ // note: this code is _identical_ to equivalent section in FastUpdater
+ c = comparator.compare(uk, ik);
+ while (true)
+ {
+ if (c == 0)
+ {
+ builder.leaf().addKey(updateF.merge(uk, ik));
+ ++upos;
+ ++ipos;
+ if (upos == usz || ipos == isz)
+ break;
+ c = comparator.compare(uk = (Existing) unode[upos], ik = (Insert) inode[ipos]);
+ }
+ else if (c < 0)
+ {
+ int until = exponentialSearch(comparator, unode, upos + 1, usz, ik);
+ c = until < 0 ? 1 : 0; // must find greater or equal; set >= 0 (equal) to 0; set < 0 (greater) to c=+ve
+ if (until < 0)
+ until = -(1 + until);
+ builder.leaf().copy(unode, upos, until - upos);
+ if ((upos = until) == usz)
+ break;
+ uk = (Existing) unode[upos];
+ }
+ else
+ {
+ int until = exponentialSearch(comparator, inode, ipos + 1, isz, uk);
+ c = until & 0x80000000; // must find less or equal; set >= 0 (equal) to 0, otherwise leave intact
+ if (until < 0)
+ until = -(1 + until);
+ builder.leaf().copy(inode, ipos, until - ipos, updateF);
+ if ((ipos = until) == isz)
+ break;
+ ik = (Insert) inode[ipos];
+ }
+ }
+ }
+ if (upos < usz)
+ {
+ // ipos == isz
+ builder.leaf().copy(unode, upos, usz - upos);
+ }
+ }
+ if (ipos < isz)
+ {
+ // upos == usz
+ builder.leaf().copy(inode, ipos, isz - ipos, updateF);
+ }
+ return builder.build();
+ }
+ }
+
+ public static void reverseInSitu(Object[] tree)
+ {
+ reverseInSitu(tree, height(tree), true);
+ }
+
+ /**
+ * The internal implementation of {@link #reverseInSitu(Object[])}.
+ * Takes two arguments that help minimise garbage generation, by testing sizeMaps against
+ * known globallyl shared sizeMap for dense nodes that do not need to be modified, and
+ * for permitting certain users (namely FastBuilder) to declare that non-matching sizeMap
+ * can be mutated directly without allocating {@code new int[]}
+ *
+ * @param tree the tree to reverse in situ
+ * @param height the height of the tree
+ * @param copySizeMaps whether or not to copy any non-globally-shared sizeMap before reversing them
+ */
+ private static void reverseInSitu(Object[] tree, int height, boolean copySizeMaps)
+ {
+ if (isLeaf(tree))
+ {
+ reverse(tree, 0, sizeOfLeaf(tree));
+ }
+ else
+ {
+ int keyCount = shallowSizeOfBranch(tree);
+ reverse(tree, 0, keyCount);
+ reverse(tree, keyCount, keyCount * 2 + 1);
+ for (int i = keyCount; i <= keyCount * 2; ++i)
+ reverseInSitu((Object[]) tree[i], height - 1, copySizeMaps);
+
+ int[] sizeMap = (int[]) tree[2 * keyCount + 1];
+ if (sizeMap != DENSE_SIZE_MAPS[height - 2]) // no need to reverse a dense map; same in both directions
+ {
+ if (copySizeMaps)
+ sizeMap = sizeMap.clone();
+ sizeMapToSizes(sizeMap);
+ reverse(sizeMap, 0, sizeMap.length);
+ sizesToSizeMap(sizeMap);
+ }
+ }
+ }
+
+ public static <V> Iterator<V> iterator(Object[] btree)
+ {
+ return iterator(btree, Dir.ASC);
+ }
+
+ public static <V> Iterator<V> iterator(Object[] btree, Dir dir)
+ {
+ return isLeaf(btree) ? new LeafBTreeSearchIterator<>(btree, null, dir)
+ : new FullBTreeSearchIterator<>(btree, null, dir);
+ }
+
+ public static <V> Iterator<V> iterator(Object[] btree, int lb, int ub, Dir dir)
+ {
+ return isLeaf(btree) ? new LeafBTreeSearchIterator<>(btree, null, dir, lb, ub)
+ : new FullBTreeSearchIterator<>(btree, null, dir, lb, ub);
+ }
+
+ public static <V> Iterable<V> iterable(Object[] btree)
+ {
+ return iterable(btree, Dir.ASC);
+ }
+
+ public static <V> Iterable<V> iterable(Object[] btree, Dir dir)
+ {
+ return () -> iterator(btree, dir);
+ }
+
+ public static <V> Iterable<V> iterable(Object[] btree, int lb, int ub, Dir dir)
+ {
+ return () -> iterator(btree, lb, ub, dir);
+ }
+
+ /**
+ * Returns an Iterator over the entire tree
+ *
+ * @param btree the tree to iterate over
+ * @param dir direction of iteration
+ * @param <V>
+ * @return
+ */
+ public static <K, V> BTreeSearchIterator<K, V> slice(Object[] btree, Comparator<? super K> comparator, Dir dir)
+ {
+ return isLeaf(btree) ? new LeafBTreeSearchIterator<>(btree, comparator, dir)
+ : new FullBTreeSearchIterator<>(btree, comparator, dir);
+ }
+
+ /**
+ * @param btree the tree to iterate over
+ * @param comparator the comparator that defines the ordering over the items in the tree
+ * @param start the beginning of the range to return, inclusive (in ascending order)
+ * @param end the end of the range to return, exclusive (in ascending order)
+ * @param dir if false, the iterator will start at the last item and move backwards
+ * @return an Iterator over the defined sub-range of the tree
+ */
+ public static <K, V extends K> BTreeSearchIterator<K, V> slice(Object[] btree, Comparator<? super K> comparator, K start, K end, Dir dir)
+ {
+ return slice(btree, comparator, start, true, end, false, dir);
+ }
+
+ /**
+ * @param btree the tree to iterate over
+ * @param comparator the comparator that defines the ordering over the items in the tree
+ * @param startIndex the start index of the range to return, inclusive
+ * @param endIndex the end index of the range to return, inclusive
+ * @param dir if false, the iterator will start at the last item and move backwards
+ * @return an Iterator over the defined sub-range of the tree
+ */
+ public static <K, V extends K> BTreeSearchIterator<K, V> slice(Object[] btree, Comparator<? super K> comparator, int startIndex, int endIndex, Dir dir)
+ {
+ return isLeaf(btree) ? new LeafBTreeSearchIterator<>(btree, comparator, dir, startIndex, endIndex)
+ : new FullBTreeSearchIterator<>(btree, comparator, dir, startIndex, endIndex);
+ }
+
+ /**
+ * @param btree the tree to iterate over
+ * @param comparator the comparator that defines the ordering over the items in the tree
+ * @param start low bound of the range
+ * @param startInclusive inclusivity of lower bound
+ * @param end high bound of the range
+ * @param endInclusive inclusivity of higher bound
+ * @param dir direction of iteration
+ * @return an Iterator over the defined sub-range of the tree
+ */
+ public static <K, V extends K> BTreeSearchIterator<K, V> slice(Object[] btree, Comparator<? super K> comparator, K start, boolean startInclusive, K end, boolean endInclusive, Dir dir)
+ {
+ int inclusiveLowerBound = max(0,
+ start == null ? Integer.MIN_VALUE
+ : startInclusive ? ceilIndex(btree, comparator, start)
+ : higherIndex(btree, comparator, start));
+ int inclusiveUpperBound = min(size(btree) - 1,
+ end == null ? Integer.MAX_VALUE
+ : endInclusive ? floorIndex(btree, comparator, end)
+ : lowerIndex(btree, comparator, end));
+ return isLeaf(btree) ? new LeafBTreeSearchIterator<>(btree, comparator, dir, inclusiveLowerBound, inclusiveUpperBound)
+ : new FullBTreeSearchIterator<>(btree, comparator, dir, inclusiveLowerBound, inclusiveUpperBound);
+ }
+
+ /**
+ * @return the item in the tree that sorts as equal to the search argument, or null if no such item
+ */
+ public static <V> V find(Object[] node, Comparator<? super V> comparator, V find)
+ {
+ while (true)
+ {
+ int keyEnd = getKeyEnd(node);
+ int i = Arrays.binarySearch((V[]) node, 0, keyEnd, find, comparator);
+
+ if (i >= 0)
+ return (V) node[i];
+
+ if (isLeaf(node))
+ return null;
+
+ i = -1 - i;
+ node = (Object[]) node[keyEnd + i];
+ }
+ }
+
+ /**
+ * 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.
+ */
+ public static <V> void replaceInSitu(Object[] tree, int index, V replace)
+ {
+ // WARNING: if semantics change, see also InternalCursor.seekTo, which mirrors this implementation
+ if ((index < 0) | (index >= size(tree)))
+ throw new IndexOutOfBoundsException(index + " not in range [0.." + size(tree) + ")");
+
+ while (!isLeaf(tree))
+ {
+ final int[] sizeMap = getSizeMap(tree);
+ int boundary = Arrays.binarySearch(sizeMap, index);
+ if (boundary >= 0)
+ {
+ // exact match, in this branch node
+ assert boundary < sizeMap.length - 1;
+ tree[boundary] = replace;
+ return;
+ }
+
+ boundary = -1 - boundary;
+ if (boundary > 0)
+ {
+ assert boundary < sizeMap.length;
+ index -= (1 + sizeMap[boundary - 1]);
+ }
+ tree = (Object[]) tree[getChildStart(tree) + boundary];
+ }
+ assert index < getLeafKeyEnd(tree);
+ tree[index] = 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)
+ */
+ public static <V> void replaceInSitu(Object[] node, Comparator<? super V> comparator, V find, V replace)
+ {
+ while (true)
+ {
+ int keyEnd = getKeyEnd(node);
+ int i = Arrays.binarySearch((V[]) node, 0, keyEnd, find, comparator);
+
+ if (i >= 0)
+ {
+ assert find == node[i];
+ node[i] = replace;
+ return;
+ }
+
+ if (isLeaf(node))
+ throw new NoSuchElementException();
+
+ i = -1 - i;
+ node = (Object[]) node[keyEnd + i];
+ }
+ }
+
+ /**
+ * Honours result semantics of {@link Arrays#binarySearch}, as though it were performed on the tree flattened into an array
+ *
+ * @return index of item in tree, or <tt>(-(<i>insertion point</i>) - 1)</tt> if not present
+ */
+ public static <V> int findIndex(Object[] node, Comparator<? super V> comparator, V find)
+ {
+ int lb = 0;
+ while (true)
+ {
+ int keyEnd = getKeyEnd(node);
+ int i = Arrays.binarySearch((V[]) node, 0, keyEnd, find, comparator);
+ boolean exact = i >= 0;
+
+ if (isLeaf(node))
+ return exact ? lb + i : i - lb;
+
+ if (!exact)
+ i = -1 - i;
+
+ int[] sizeMap = getSizeMap(node);
+ if (exact)
+ return lb + sizeMap[i];
+ else if (i > 0)
+ lb += sizeMap[i - 1] + 1;
+
+ node = (Object[]) node[keyEnd + i];
+ }
+ }
+
+ /**
+ * @return the value at the index'th position in the tree, in tree order
+ */
+ public static <V> V findByIndex(Object[] tree, int index)
+ {
+ // WARNING: if semantics change, see also InternalCursor.seekTo, which mirrors this implementation
+ if ((index < 0) | (index >= size(tree)))
+ throw new IndexOutOfBoundsException(index + " not in range [0.." + size(tree) + ")");
+
+ Object[] node = tree;
+ while (true)
+ {
+ if (isLeaf(node))
+ {
+ int keyEnd = getLeafKeyEnd(node);
+ assert index < keyEnd;
+ return (V) node[index];
+ }
+
+ int[] sizeMap = getSizeMap(node);
+ int boundary = Arrays.binarySearch(sizeMap, index);
+ if (boundary >= 0)
+ {
+ // exact match, in this branch node
+ assert boundary < sizeMap.length - 1;
+ return (V) node[boundary];
+ }
+
+ boundary = -1 - boundary;
+ if (boundary > 0)
+ {
+ assert boundary < sizeMap.length;
+ index -= (1 + sizeMap[boundary - 1]);
+ }
+ node = (Object[]) node[getChildStart(node) + boundary];
+ }
+ }
+
+ /* since we have access to binarySearch semantics within indexOf(), we can use this to implement
+ * lower/upper/floor/higher very trivially
+ *
+ * this implementation is *not* optimal; it requires two logarithmic traversals, although the second is much cheaper
+ * (having less height, and operating over only primitive arrays), and the clarity is compelling
+ */
+
+ public static <V> int lowerIndex(Object[] btree, Comparator<? super V> comparator, V find)
+ {
+ int i = findIndex(btree, comparator, find);
+ if (i < 0)
+ i = -1 - i;
+ return i - 1;
+ }
+
+ public static <V> V lower(Object[] btree, Comparator<? super V> comparator, V find)
+ {
+ int i = lowerIndex(btree, comparator, find);
+ return i >= 0 ? findByIndex(btree, i) : null;
+ }
+
+ public static <V> int floorIndex(Object[] btree, Comparator<? super V> comparator, V find)
+ {
+ int i = findIndex(btree, comparator, find);
+ if (i < 0)
+ i = -2 - i;
+ return i;
+ }
+
+ public static <V> V floor(Object[] btree, Comparator<? super V> comparator, V find)
+ {
+ int i = floorIndex(btree, comparator, find);
+ return i >= 0 ? findByIndex(btree, i) : null;
+ }
+
+ public static <V> int higherIndex(Object[] btree, Comparator<? super V> comparator, V find)
+ {
+ int i = findIndex(btree, comparator, find);
+ if (i < 0)
+ i = -1 - i;
+ else
+ i++;
+ return i;
+ }
+
+ public static <V> V higher(Object[] btree, Comparator<? super V> comparator, V find)
+ {
+ int i = higherIndex(btree, comparator, find);
+ return i < size(btree) ? findByIndex(btree, i) : null;
+ }
+
+ public static <V> int ceilIndex(Object[] btree, Comparator<? super V> comparator, V find)
+ {
+ int i = findIndex(btree, comparator, find);
+ if (i < 0)
+ i = -1 - i;
+ return i;
+ }
+
+ public static <V> V ceil(Object[] btree, Comparator<? super V> comparator, V find)
+ {
+ int i = ceilIndex(btree, comparator, find);
+ return i < size(btree) ? findByIndex(btree, i) : null;
+ }
+
+ // UTILITY METHODS
+
+ // get the upper bound we should search in for keys in the node
+ static int getKeyEnd(Object[] node)
+ {
+ if (isLeaf(node))
+ return getLeafKeyEnd(node);
+ else
+ return getBranchKeyEnd(node);
+ }
+
+ // get the last index that is non-null in the leaf node
+ static int getLeafKeyEnd(Object[] node)
+ {
+ int len = node.length;
+ return node[len - 1] == null ? len - 1 : len;
+ }
+
+ // return the boundary position between keys/children for the branch node
+ // == number of keys, as they are indexed from zero
+ static int getBranchKeyEnd(Object[] branchNode)
+ {
+ return (branchNode.length / 2) - 1;
+ }
+
+ /**
+ * @return first index in a branch node containing child nodes
+ */
+ static int getChildStart(Object[] branchNode)
+ {
+ return getBranchKeyEnd(branchNode);
+ }
+
+ /**
+ * @return last index + 1 in a branch node containing child nodes
+ */
+ static int getChildEnd(Object[] branchNode)
+ {
+ return branchNode.length - 1;
+ }
+
+ /**
+ * @return number of children in a branch node
+ */
+ static int getChildCount(Object[] branchNode)
+ {
+ return branchNode.length / 2;
+ }
+
+ /**
+ * @return the size map for the branch node
+ */
+ static int[] getSizeMap(Object[] branchNode)
+ {
+ return (int[]) branchNode[getChildEnd(branchNode)];
+ }
+
+ /**
+ * @return the size map for the branch node
+ */
+ static int lookupSizeMap(Object[] branchNode, int index)
+ {
+ return getSizeMap(branchNode)[index];
+ }
+
+ // get the size from the btree's index (fails if not present)
+ public static int size(Object[] tree)
+ {
+ if (isLeaf(tree))
+ return getLeafKeyEnd(tree);
+ int length = tree.length;
+ // length - 1 == getChildEnd == getPositionOfSizeMap
+ // (length / 2) - 1 == getChildCount - 1 == position of full tree size
+ // hard code this, as will be used often;
+ return ((int[]) tree[length - 1])[(length / 2) - 1];
+ }
+
+ /**
+ * Checks is the node is a leaf.
+ *
+ * @return {@code true} if the provided node is a leaf, {@code false} if it is a branch.
+ */
+ public static boolean isLeaf(Object[] node)
+ {
+ // Nodes are disambiguated by the length of the array that represents them: an even number is a branch, odd a leaf
+ return (node.length & 1) == 1;
+ }
+
+ public static boolean isEmpty(Object[] tree)
+ {
+ return tree == EMPTY_LEAF;
+ }
+
+ // get the upper bound we should search in for keys in the node
+ static int shallowSize(Object[] node)
+ {
+ if (isLeaf(node))
+ return sizeOfLeaf(node);
+ else
+ return shallowSizeOfBranch(node);
+ }
+
+ static int sizeOfLeaf(Object[] leaf)
+ {
+ int len = leaf.length;
+ return leaf[len - 1] == null ? len - 1 : len;
+ }
+
+ // return the boundary position between keys/children for the branch node
+ // == number of keys, as they are indexed from zero
+ static int shallowSizeOfBranch(Object[] branch)
+ {
+ return (branch.length / 2) - 1;
+ }
+
+ /**
+ * @return first index in a branch node containing child nodes
+ */
+ static int childOffset(Object[] branch)
+ {
+ return shallowSizeOfBranch(branch);
+ }
+
+ /**
+ * @return last index + 1 in a branch node containing child nodes
+ */
+ static int childEndOffset(Object[] branch)
+ {
+ return branch.length - 1;
+ }
+
+ public static int depth(Object[] tree)
+ {
+ int depth = 1;
+ while (!isLeaf(tree))
+ {
+ depth++;
+ tree = (Object[]) tree[getKeyEnd(tree)];
+ }
+ return depth;
+ }
+
+ /**
+ * Fill the target array with the contents of the provided subtree, in ascending order, starting at targetOffset
+ *
+ * @param tree source
+ * @param target array
+ * @param targetOffset offset in target array
+ * @return number of items copied (size of tree)
+ */
+ public static int toArray(Object[] tree, Object[] target, int targetOffset)
+ {
+ return toArray(tree, 0, size(tree), target, targetOffset);
+ }
+
+ public static int toArray(Object[] tree, int treeStart, int treeEnd, Object[] target, int targetOffset)
+ {
+ if (isLeaf(tree))
+ {
+ int count = treeEnd - treeStart;
+ System.arraycopy(tree, treeStart, target, targetOffset, count);
+ return count;
+ }
+
+ int newTargetOffset = targetOffset;
+ int childCount = getChildCount(tree);
+ int childOffset = getChildStart(tree);
+ for (int i = 0; i < childCount; i++)
+ {
+ int childStart = treeIndexOffsetOfChild(tree, i);
+ int childEnd = treeIndexOfBranchKey(tree, i);
+ if (childStart <= treeEnd && childEnd >= treeStart)
+ {
+ newTargetOffset += toArray((Object[]) tree[childOffset + i], max(0, treeStart - childStart), min(childEnd, treeEnd) - childStart,
+ target, newTargetOffset);
+ if (treeStart <= childEnd && treeEnd > childEnd) // this check will always fail for the non-existent key
+ target[newTargetOffset++] = tree[i];
+ }
+ }
+ return newTargetOffset - targetOffset;
+ }
+
+ /**
+ * An efficient transformAndFilter implementation suitable for a tree consisting of a single leaf root
+ * NOTE: codewise *identical* to {@link #transformAndFilterLeaf(Object[], BiFunction, Object)}
+ */
+ private static <I, O> Object[] transformAndFilterLeaf(Object[] leaf, Function<? super I, ? extends O> apply)
+ {
+ int i = 0, sz = sizeOfLeaf(leaf);
+ I in;
+ O out;
+ do // optimistic loop, looking for first point transformation modifies the input (if any)
+ {
+ in = (I) leaf[i];
+ out = apply.apply(in);
+ } while (in == out && ++i < sz);
+
+ // in == out -> i == sz
+ // otherwise in == leaf[i]
+ int identicalUntil = i;
+
+ if (out == null && ++i < sz)
+ {
+ // optimistic loop, looking for first key {@code apply} modifies without removing it (if any)
+ do
+ {
+ in = (I) leaf[i];
+ out = apply.apply(in);
+ } while (null == out && ++i < sz);
+ }
+ // out == null -> i == sz
+ // otherwise out == apply.apply(leaf[i])
+
+ if (i == sz)
+ {
+ // if we have reached the end of the input, we're either:
+ // 1) returning input unmodified; or
+ // 2) copying some (possibly empty) prefix of it
+
+ if (identicalUntil == sz)
+ return leaf;
+
+ if (identicalUntil == 0)
+ return empty();
+
+ Object[] copy = new Object[identicalUntil | 1];
+ System.arraycopy(leaf, 0, copy, 0, identicalUntil);
+ return copy;
+ }
+
+ try (FastBuilder<O> builder = fastBuilder())
+ {
+ // otherwise copy the initial part that was unmodified, insert the non-null modified key, and continue
+ if (identicalUntil > 0)
+ builder.leaf().copyNoOverflow(leaf, 0, identicalUntil);
+ builder.leaf().addKeyNoOverflow(out);
+
+ while (++i < sz)
+ {
+ in = (I) leaf[i];
+ out = apply.apply(in);
+ if (out != null)
+ builder.leaf().addKeyNoOverflow(out);
+ }
+
+ return builder.build();
+ }
+ }
+
+ /**
+ * Takes a tree and transforms it using the provided function, filtering out any null results.
+ * The result of any transformation must sort identically as their originals, wrt other results.
+ * <p>
+ * If no modifications are made, the original is returned.
+ * NOTE: codewise *identical* to {@link #transformAndFilter(Object[], Function)}
+ */
+ public static <I, I2, O> Object[] transformAndFilter(Object[] tree, BiFunction<? super I, ? super I2, ? extends O> apply, I2 param)
+ {
+ if (isEmpty(tree))
+ return tree;
+
+ if (isLeaf(tree))
+ return transformAndFilterLeaf(tree, apply, param);
+
+ try (BiTransformer<I, I2, O> transformer = BiTransformer.get(apply, param))
+ {
+ return transformer.apply(tree);
+ }
+ }
+
+ /**
+ * Takes a tree and transforms it using the provided function, filtering out any null results.
+ * The result of any transformation must sort identically as their originals, wrt other results.
+ * <p>
+ * If no modifications are made, the original is returned.
+ * <p>
+ * An efficient transformAndFilter implementation suitable for a tree consisting of a single leaf root
+ * NOTE: codewise *identical* to {@link #transformAndFilter(Object[], BiFunction, Object)}
+ */
+ public static <I, O> Object[] transformAndFilter(Object[] tree, Function<? super I, ? extends O> apply)
+ {
+ if (isEmpty(tree))
+ return tree;
+
+ if (isLeaf(tree))
+ return transformAndFilterLeaf(tree, apply);
+
+ try (Transformer<I, O> transformer = Transformer.get(apply))
+ {
+ return transformer.apply(tree);
+ }
+ }
+
+ /**
+ * An efficient transformAndFilter implementation suitable for a tree consisting of a single leaf root
+ * NOTE: codewise *identical* to {@link #transformAndFilterLeaf(Object[], Function)}
+ */
+ private static <I, I2, O> Object[] transformAndFilterLeaf(Object[] leaf, BiFunction<? super I, ? super I2, ? extends O> apply, I2 param)
+ {
+ int i = 0, sz = sizeOfLeaf(leaf);
+ I in;
+ O out;
+ do // optimistic loop, looking for first point transformation modifies the input (if any)
+ {
+ in = (I) leaf[i];
+ out = apply.apply(in, param);
+ } while (in == out && ++i < sz);
+
+ // in == out -> i == sz
+ // otherwise in == leaf[i]
+ int identicalUntil = i;
+
+ if (out == null && ++i < sz)
+ {
+ // optimistic loop, looking for first key {@code apply} modifies without removing it (if any)
+ do
+ {
+ in = (I) leaf[i];
+ out = apply.apply(in, param);
+ } while (null == out && ++i < sz);
+ }
+ // out == null -> i == sz
+ // otherwise out == apply.apply(leaf[i])
+
+ if (i == sz)
+ {
+ // if we have reached the end of the input, we're either:
+ // 1) returning input unmodified; or
+ // 2) copying some (possibly empty) prefix of it
+
+ if (identicalUntil == sz)
+ return leaf;
+
+ if (identicalUntil == 0)
+ return empty();
+
+ Object[] copy = new Object[identicalUntil | 1];
+ System.arraycopy(leaf, 0, copy, 0, identicalUntil);
+ return copy;
+ }
+
+ try (FastBuilder<O> builder = fastBuilder())
+ {
+ // otherwise copy the initial part that was unmodified, insert the non-null modified key, and continue
+ if (identicalUntil > 0)
+ builder.leaf().copyNoOverflow(leaf, 0, identicalUntil);
+ builder.leaf().addKeyNoOverflow(out);
+
+ while (++i < sz)
+ {
+ in = (I) leaf[i];
+ out = apply.apply(in, param);
+ if (out != null)
+ builder.leaf().addKeyNoOverflow(out);
+ }
+
+ return builder.build();
+ }
+ }
+
+ /**
+ * Takes a tree and transforms it using the provided function.
+ * The result of any transformation must sort identically as their originals, wrt other results.
+ * <p>
+ * If no modifications are made, the original is returned.
+ */
+ public static <I, O> Object[] transform(Object[] tree, Function<? super I, ? extends O> function)
+ {
+ if (isEmpty(tree)) // isEmpty determined by identity; must return input
+ return tree;
+
+ if (isLeaf(tree)) // escape hatch for fast leaf transformation
+ return transformLeaf(tree, function);
+
+ Object[] result = tree; // optimistically assume we'll return our input unmodified
+ int keyCount = shallowSizeOfBranch(tree);
+ for (int i = 0; i < keyCount; ++i)
+ {
+ // operate on a pair of (child,key) each loop
+ Object[] curChild = (Object[]) tree[keyCount + i];
+ Object[] updChild = transform(curChild, function);
+ Object curKey = tree[i];
+ Object updKey = function.apply((I) curKey);
+ if (result == tree)
+ {
+ if (curChild == updChild && curKey == updKey)
+ continue; // if output still same as input, loop
+
+ // otherwise initialise output to a copy of input up to this point
+ result = transformCopyBranchHelper(tree, keyCount, i, i);
+ }
+ result[keyCount + i] = updChild;
+ result[i] = updKey;
+ }
+ // final unrolled copy of loop for last child only (unbalanced with keys)
+ Object[] curChild = (Object[]) tree[2 * keyCount];
+ Object[] updChild = transform(curChild, function);
+ if (result == tree)
+ {
+ if (curChild == updChild)
+ return tree;
+ result = transformCopyBranchHelper(tree, keyCount, keyCount, keyCount);
+ }
+ result[2 * keyCount] = updChild;
+ result[2 * keyCount + 1] = tree[2 * keyCount + 1]; // take the original sizeMap, as we are exactly the same shape
+ return result;
+ }
+
+ // create a copy of a branch, with the exact same size, copying the specified number of keys and children
+ private static Object[] transformCopyBranchHelper(Object[] branch, int keyCount, int copyKeyCount, int copyChildCount)
+ {
+ Object[] result = new Object[branch.length];
+ System.arraycopy(branch, 0, result, 0, copyKeyCount);
+ System.arraycopy(branch, keyCount, result, keyCount, copyChildCount);
+ return result;
+ }
+
+ // an efficient transformAndFilter implementation suitable for a tree consisting of a single leaf root
+ private static <I, O> Object[] transformLeaf(Object[] leaf, Function<? super I, ? extends O> apply)
+ {
+ Object[] result = leaf; // optimistically assume we'll return our input unmodified
+ int size = sizeOfLeaf(leaf);
+ for (int i = 0; i < size; ++i)
+ {
+ Object current = leaf[i];
+ Object updated = apply.apply((I) current);
+ if (result == leaf)
+ {
+ if (current == updated)
+ continue; // if output still same as input, loop
+
+ // otherwise initialise output to a copy of input up to this point
+ result = new Object[leaf.length];
+ System.arraycopy(leaf, 0, result, 0, i);
+ }
+ result[i] = updated;
+ }
+ return result;
+ }
+
+ public static boolean equals(Object[] a, Object[] b)
+ {
+ return size(a) == size(b) && Iterators.elementsEqual(iterator(a), iterator(b));
+ }
+
+ public static int hashCode(Object[] btree)
+ {
+ // we can't just delegate to Arrays.deepHashCode(),
+ // because two equivalent trees may be represented by differently shaped trees
+ int result = 1;
+ for (Object v : iterable(btree))
+ result = 31 * result + Objects.hashCode(v);
+ return result;
+ }
+
+ public static String toString(Object[] btree)
+ {
+ return appendBranchOrLeaf(new StringBuilder().append('['), btree).append(']').toString();
+ }
+
+ private static StringBuilder appendBranchOrLeaf(StringBuilder builder, Object[] node)
+ {
+ return isLeaf(node) ? appendLeaf(builder, node) : appendBranch(builder, node);
+ }
+
+ private static StringBuilder appendBranch(StringBuilder builder, Object[] branch)
+ {
+ int childCount = branch.length / 2;
+ int keyCount = childCount - 1;
+ // add keys
+ for (int i = 0; i < keyCount; i++)
+ {
+ if (i != 0)
+ builder.append(", ");
+ builder.append(branch[i]);
+ }
+ // add children
+ for (int i = keyCount, m = branch.length - 1; i < m; i++)
+ {
+ builder.append(", ");
+ appendBranchOrLeaf(builder, (Object[]) branch[i]);
+ }
+ // add sizeMap
+ builder.append(", ").append(Arrays.toString((int[]) branch[branch.length - 1]));
+ return builder;
+ }
+
+ private static StringBuilder appendLeaf(StringBuilder builder, Object[] leaf)
+ {
+ return builder.append(Arrays.toString(leaf));
+ }
+
+ /**
+ * tree index => index of key wrt all items in the tree laid out serially
+ * <p>
+ * This version of the method permits requesting out-of-bounds indexes, -1 and size
+ *
+ * @param root to calculate tree index within
+ * @param keyIndex root-local index of key to calculate tree-index
+ * @return the number of items preceding the key in the whole tree of root
+ */
+ public static int treeIndexOfKey(Object[] root, int keyIndex)
+ {
+ if (isLeaf(root))
+ return keyIndex;
+ int[] sizeMap = getSizeMap(root);
+ if ((keyIndex >= 0) & (keyIndex < sizeMap.length))
+ return sizeMap[keyIndex];
+ // we support asking for -1 or size, so that we can easily use this for iterator bounds checking
+ if (keyIndex < 0)
+ return -1;
+ return sizeMap[keyIndex - 1] + 1;
+ }
+
+ /**
+ * @param keyIndex node-local index of the key to calculate index of
+ * @return keyIndex; this method is here only for symmetry and clarity
+ */
+ public static int treeIndexOfLeafKey(int keyIndex)
+ {
+ return keyIndex;
+ }
+
+ /**
+ * @param root to calculate tree-index within
+ * @param keyIndex root-local index of key to calculate tree-index of
+ * @return the number of items preceding the key in the whole tree of root
+ */
+ public static int treeIndexOfBranchKey(Object[] root, int keyIndex)
+ {
+ return lookupSizeMap(root, keyIndex);
+ }
+
+ /**
+ * @param root to calculate tree-index within
+ * @param childIndex root-local index of *child* to calculate tree-index of
+ * @return the number of items preceding the child in the whole tree of root
+ */
+ public static int treeIndexOffsetOfChild(Object[] root, int childIndex)
+ {
+ if (childIndex == 0)
+ return 0;
+ return 1 + lookupSizeMap(root, childIndex - 1);
+ }
+
+ public static <V> Builder<V> builder(Comparator<? super V> comparator)
+ {
+ return new Builder<>(comparator);
+ }
+
+ public static <V> Builder<V> builder(Comparator<? super V> comparator, int initialCapacity)
+ {
+ return new Builder<>(comparator, initialCapacity);
+ }
+
+ public static class Builder<V>
+ {
+ // a user-defined bulk resolution, to be applied manually via resolve()
+ public static interface Resolver
+ {
+ // can return a different output type to input, so long as sort order is maintained
+ // if a resolver is present, this method will be called for every sequence of equal inputs
+ // even those with only one item
+ Object resolve(Object[] array, int lb, int ub);
+ }
+
+ // a user-defined resolver that is applied automatically on encountering two duplicate values
+ public static interface QuickResolver<V>
+ {
+ // can return a different output type to input, so long as sort order is maintained
+ // if a resolver is present, this method will be called for every sequence of equal inputs
+ // even those with only one item
+ V resolve(V a, V b);
+ }
+
+ Comparator<? super V> comparator;
+ Object[] values;
+ int count;
+ boolean detected = true; // true if we have managed to cheaply ensure sorted (+ filtered, if resolver == null) as we have added
+ boolean auto = true; // false if the user has promised to enforce the sort order and resolve any duplicates
+ QuickResolver<V> quickResolver;
+
+ protected Builder(Comparator<? super V> comparator)
+ {
+ this(comparator, 16);
+ }
+
+ protected Builder(Comparator<? super V> comparator, int initialCapacity)
+ {
+ if (initialCapacity == 0)
+ initialCapacity = 16;
+ this.comparator = comparator;
+ this.values = new Object[initialCapacity];
+ }
+
+ @VisibleForTesting
+ public Builder()
+ {
+ this.values = new Object[16];
+ }
+
+ private Builder(Builder<V> builder)
+ {
+ this.comparator = builder.comparator;
+ this.values = Arrays.copyOf(builder.values, builder.values.length);
+ this.count = builder.count;
+ this.detected = builder.detected;
+ this.auto = builder.auto;
+ this.quickResolver = builder.quickResolver;
+ }
+
+ /**
+ * Creates a copy of this {@code Builder}.
+ *
+ * @return a copy of this {@code Builder}.
+ */
+ public Builder<V> copy()
+ {
+ return new Builder<>(this);
+ }
+
+ public Builder<V> setQuickResolver(QuickResolver<V> quickResolver)
+ {
+ this.quickResolver = quickResolver;
+ return this;
+ }
+
+ public void reuse()
+ {
+ reuse(comparator);
+ }
+
+ public void reuse(Comparator<? super V> comparator)
+ {
+ this.comparator = comparator;
+ Arrays.fill(values, null);
+ count = 0;
+ detected = true;
+ }
+
+ public Builder<V> auto(boolean auto)
+ {
+ this.auto = auto;
+ return this;
+ }
+
+ public Builder<V> add(V v)
+ {
+ if (count == values.length)
+ values = Arrays.copyOf(values, count * 2);
+
+ Object[] values = this.values;
+ int prevCount = this.count++;
+ values[prevCount] = v;
+
+ if (auto && detected && prevCount > 0)
+ {
+ V prev = (V) values[prevCount - 1];
+ int c = comparator.compare(prev, v);
+ if (c == 0 && auto)
+ {
+ count = prevCount;
+ if (quickResolver != null)
+ values[prevCount - 1] = quickResolver.resolve(prev, v);
+ }
+ else if (c > 0)
+ {
+ detected = false;
+ }
+ }
+
+ return this;
+ }
+
+ public Builder<V> addAll(Collection<V> add)
+ {
+ if (auto && add instanceof SortedSet && equalComparators(comparator, ((SortedSet) add).comparator()))
+ {
+ // if we're a SortedSet, permit quick order-preserving addition of items
+ // if we collect all duplicates, don't bother as merge will necessarily be more expensive than sorting at end
+ return mergeAll(add, add.size());
+ }
+ detected = false;
+ if (values.length < count + add.size())
+ values = Arrays.copyOf(values, max(count + add.size(), count * 2));
+ for (V v : add)
+ values[count++] = v;
+ return this;
+ }
+
+ private static boolean equalComparators(Comparator<?> a, Comparator<?> b)
+ {
+ return a == b || (isNaturalComparator(a) && isNaturalComparator(b));
+ }
+
+ private static boolean isNaturalComparator(Comparator<?> a)
+ {
+ return a == null || a == Comparator.naturalOrder() || a == Ordering.natural();
+ }
+
+ // iter must be in sorted order!
+ private Builder<V> mergeAll(Iterable<V> add, int addCount)
+ {
+ assert auto;
+ // ensure the existing contents are in order
+ autoEnforce();
+
+ int curCount = count;
+ // we make room for curCount * 2 + addCount, so that we can copy the current values to the end
+ // if necessary for continuing the merge, and have the new values directly after the current value range
+ if (values.length < curCount * 2 + addCount)
+ values = Arrays.copyOf(values, max(curCount * 2 + addCount, curCount * 3));
+
+ if (add instanceof BTreeSet)
+ {
+ // use btree set's fast toArray method, to append directly
+ ((BTreeSet) add).toArray(values, curCount);
+ }
+ else
+ {
+ // consider calling toArray() and System.arraycopy
+ int i = curCount;
+ for (V v : add)
+ values[i++] = v;
+ }
+ return mergeAll(addCount);
+ }
+
+ private Builder<V> mergeAll(int addCount)
+ {
+ Object[] a = values;
+ int addOffset = count;
+
+ int i = 0, j = addOffset;
+ int curEnd = addOffset, addEnd = addOffset + addCount;
+
+ // save time in cases where we already have a subset, by skipping dir
+ while (i < curEnd && j < addEnd)
+ {
+ V ai = (V) a[i], aj = (V) a[j];
+ // in some cases, such as Columns, we may have identity supersets, so perform a cheap object-identity check
+ int c = ai == aj ? 0 : comparator.compare(ai, aj);
+ if (c > 0)
+ break;
+ else if (c == 0)
+ {
+ if (quickResolver != null)
+ a[i] = quickResolver.resolve(ai, aj);
+ j++;
+ }
+ i++;
+ }
+
+ if (j == addEnd)
+ return this; // already a superset of the new values
+
+ // otherwise, copy the remaining existing values to the very end, freeing up space for merge result
+ int newCount = i;
+ System.arraycopy(a, i, a, addEnd, count - i);
+ curEnd = addEnd + (count - i);
+ i = addEnd;
+
+ while (i < curEnd && j < addEnd)
+ {
+ V ai = (V) a[i];
+ V aj = (V) a[j];
+ // could avoid one comparison if we cared, but would make this ugly
+ int c = comparator.compare(ai, aj);
+ if (c == 0)
+ {
+ Object newValue = quickResolver == null ? ai : quickResolver.resolve(ai, aj);
+ a[newCount++] = newValue;
+ i++;
+ j++;
+ }
+ else
+ {
+ a[newCount++] = c < 0 ? a[i++] : a[j++];
+ }
+ }
+
+ // exhausted one of the inputs; fill in remainder of the other
+ if (i < curEnd)
+ {
+ System.arraycopy(a, i, a, newCount, curEnd - i);
+ newCount += curEnd - i;
+ }
+ else if (j < addEnd)
+ {
+ if (j != newCount)
+ System.arraycopy(a, j, a, newCount, addEnd - j);
+ newCount += addEnd - j;
+ }
+ count = newCount;
+ return this;
+ }
+
+ public boolean isEmpty()
+ {
+ return count == 0;
+ }
+
+ public Builder<V> reverse()
+ {
+ assert !auto;
+ int mid = count / 2;
+ for (int i = 0; i < mid; i++)
+ {
+ Object t = values[i];
+ values[i] = values[count - (1 + i)];
+ values[count - (1 + i)] = t;
+ }
+ return this;
+ }
+
+ public Builder<V> sort()
+ {
+ Arrays.sort((V[]) values, 0, count, comparator);
+ return this;
+ }
+
+ // automatically enforce sorted+filtered
+ private void autoEnforce()
+ {
+ if (!detected && count > 1)
+ {
+ sort();
+ int prevIdx = 0;
+ V prev = (V) values[0];
+ for (int i = 1; i < count; i++)
+ {
+ V next = (V) values[i];
+ if (comparator.compare(prev, next) != 0)
+ values[++prevIdx] = prev = next;
+ else if (quickResolver != null)
+ values[prevIdx] = prev = quickResolver.resolve(prev, next);
+ }
+ count = prevIdx + 1;
+ }
+ detected = true;
+ }
+
+ public Builder<V> resolve(Resolver resolver)
+ {
+ if (count > 0)
+ {
+ int c = 0;
+ int prev = 0;
+ for (int i = 1; i < count; i++)
+ {
+ if (comparator.compare((V) values[i], (V) values[prev]) != 0)
+ {
+ values[c++] = resolver.resolve((V[]) values, prev, i);
+ prev = i;
+ }
+ }
+ values[c++] = resolver.resolve((V[]) values, prev, count);
+ count = c;
+ }
+ return this;
+ }
+
+ public Object[] build()
+ {
+ if (auto)
+ autoEnforce();
+ try (BulkIterator<V> iterator = BulkIterator.of(values, 0))
+ {
+ return BTree.build(iterator, count, UpdateFunction.noOp());
+ }
+ }
+ }
+
+ private static <V, A> void applyValue(V value, BiConsumer<A, V> function, A argument)
+ {
+ function.accept(argument, value);
+ }
+
+ public static <V, A> void applyLeaf(Object[] btree, BiConsumer<A, V> function, A argument)
+ {
+ Preconditions.checkArgument(isLeaf(btree));
+ int limit = getLeafKeyEnd(btree);
+ for (int i = 0; i < limit; i++)
+ applyValue((V) btree[i], function, argument);
+ }
+
+ /**
+ * Simple method to walk the btree forwards and apply a function till a stop condition is reached
+ * <p>
+ * Private method
+ *
+ * @param btree
+ * @param function
+ */
+ public static <V, A> void apply(Object[] btree, BiConsumer<A, V> function, A argument)
+ {
+ if (isLeaf(btree))
+ {
+ applyLeaf(btree, function, argument);
+ return;
+ }
+
+ int childOffset = getChildStart(btree);
+ int limit = btree.length - 1 - childOffset;
+ for (int i = 0; i < limit; i++)
+ {
+
+ apply((Object[]) btree[childOffset + i], function, argument);
+
+ if (i < childOffset)
+ applyValue((V) btree[i], function, argument);
+ }
+ }
+
+ /**
+ * Simple method to walk the btree forwards and apply a function till a stop condition is reached
+ * <p>
+ * Private method
+ *
+ * @param btree
+ * @param function
+ */
+ public static <V> void apply(Object[] btree, Consumer<V> function)
+ {
+ BTree.<V, Consumer<V>>apply(btree, Consumer::accept, function);
+ }
+
+ private static <V> int find(Object[] btree, V from, Comparator<V> comparator)
+ {
+ // find the start index in iteration order
+ Preconditions.checkNotNull(comparator);
+ int keyEnd = getKeyEnd(btree);
+ return Arrays.binarySearch((V[]) btree, 0, keyEnd, from, comparator);
+ }
+
+ /**
+ * Calculate the minimum height needed for this size of tree
+ *
+ * @param size the tree size
+ * @return the minimum height needed for this size of tree
+ */
+ private static int minHeight(int size)
+ {
+ return heightAtSize2n(size, BRANCH_SHIFT);
+ }
+
+ private static int heightAtSize2n(int size, int branchShift)
+ {
+ // branch factor = 1 << branchShift
+ // => full size at height = (1 << (branchShift * height)) - 1
+ // => full size at height + 1 = 1 << (branchShift * height)
+ // => shift(full size at height + 1) = branchShift * height
+ // => shift(full size at height + 1) / branchShift = height
+ int lengthInBinary = 64 - Long.numberOfLeadingZeros(size);
+ return (branchShift - 1 + lengthInBinary) / branchShift;
+ }
+
+ private static int[][] buildBalancedSizeMaps(int branchShift)
+ {
+ int count = (32 / branchShift) - 1;
+ int childCount = 1 << branchShift;
+ int[][] sizeMaps = new int[count][childCount];
+ for (int height = 0; height < count; ++height)
+ {
+ int childSize = treeSize2n(height + 1, branchShift);
+ int size = 0;
+ int[] sizeMap = sizeMaps[height];
+ for (int i = 0; i < childCount; ++i)
+ {
+ sizeMap[i] = size += childSize;
+ size += 1;
+ }
+ }
+ return sizeMaps;
+ }
+
+ // simply utility to reverse the contents of array[from..to)
+ private static void reverse(Object[] array, int from, int to)
+ {
+ int mid = (from + to) / 2;
+ for (int i = from; i < mid; i++)
+ {
+ int j = to - (1 + i - from);
+ Object tmp = array[i];
+ array[i] = array[j];
+ array[j] = tmp;
+ }
+ }
+
+ // simply utility to reverse the contents of array[from..to)
+ private static void reverse(int[] array, int from, int to)
+ {
+ int mid = (from + to) / 2;
+ for (int i = from; i < mid; i++)
+ {
+ int j = to - (1 + i - from);
+ int tmp = array[i];
+ array[i] = array[j];
+ array[j] = tmp;
+ }
+ }
+
+ /**
+ * Mutate an array of child sizes into a cumulative sizeMap, returning the total size
+ */
+ private static int sizesToSizeMap(int[] sizeMap)
+ {
+ int total = sizeMap[0];
+ for (int i = 1; i < sizeMap.length; ++i)
+ sizeMap[i] = total += 1 + sizeMap[i];
+ return total;
+ }
+
+ private static int sizesToSizeMap(int[] sizes, int count)
+ {
+ int total = sizes[0];
+ for (int i = 1; i < count; ++i)
+ sizes[i] = total += 1 + sizes[i];
+ return total;
+ }
+
+ /**
+ * Mutate an array of child sizes into a cumulative sizeMap, returning the total size
+ */
+ private static void sizeMapToSizes(int[] sizeMap)
+ {
+ for (int i = sizeMap.length; i > 1; --i)
+ sizeMap[i] -= 1 + sizeMap[i - 1];
+ }
+
+ /**
+ * A simple utility method to handle a null upper bound that we treat as infinity
+ */
+ private static <Compare> int compareWithMaybeInfinity(Comparator<? super Compare> comparator, Compare key, Compare ub)
+ {
+ if (ub == null)
+ return -1;
+ return comparator.compare(key, ub);
+ }
+
+ /**
+ * Perform {@link #exponentialSearch} on {@code in[from..to)}, treating a {@code find} of {@code null} as infinity.
+ */
+ static <Compare> int exponentialSearchForMaybeInfinity(Comparator<? super Compare> comparator, Object[] in, int from, int to, Compare find)
+ {
+ if (find == null)
+ return -(1 + to);
+ return exponentialSearch(comparator, in, from, to, find);
+ }
+
+ /**
+ * Equivalent to {@link Arrays#binarySearch}, only more efficient algorithmically for linear merges.
+ * Binary search has worst case complexity {@code O(n.lg n)} for a linear merge, whereas exponential search
+ * has a worst case of {@code O(n)}. However compared to a simple linear merge, the best case for exponential
+ * search is {@code O(lg(n))} instead of {@code O(n)}.
+ */
+ private static <Compare> int exponentialSearch(Comparator<? super Compare> comparator, Object[] in, int from, int to, Compare find)
+ {
+ int step = 0;
+ while (from + step < to)
+ {
+ int i = from + step;
+ int c = comparator.compare(find, (Compare) in[i]);
+ if (c < 0)
+ {
+ to = i;
+ break;
+ }
+ if (c == 0)
+ return i;
+ from = i + 1;
+ step = step * 2 + 1; // jump in perfect binary search increments
+ }
+ return Arrays.binarySearch((Compare[]) in, from, to, find, comparator);
+ }
+
+ /**
+ * Perform {@link #exponentialSearch} on {@code in[from..to)}; if the value falls outside of the range of these
+ * elements, test against {@code ub} as though it occurred at position {@code to}
+ *
+ * @return same as {@link Arrays#binarySearch} if {@code find} occurs in the range {@code [in[from]..in[to])};
+ * otherwise the insertion position {@code -(1+to)} if {@code find} is less than {@code ub}, and {@code -(2+t)}
+ * if it is greater than or equal to.
+ * <p>
+ * {@code ub} may be {@code null}, representing infinity.
+ */
+ static <Compare> int exponentialSearchWithUpperBound(Comparator<? super Compare> comparator, Object[] in, int from, int to, Compare ub, Compare find)
+ {
+ int step = 0;
+ while (true)
+ {
+ int i = from + step;
+ if (i >= to)
+ {
+ int c = compareWithMaybeInfinity(comparator, find, ub);
+ if (c >= 0)
+ return -(2 + to);
+ break;
+ }
+ int c = comparator.compare(find, (Compare) in[i]);
+ if (c < 0)
+ {
+ to = i;
+ break;
+ }
+ if (c == 0)
+ return i;
+ from = i + 1;
+ step = step * 2 + 1; // jump in perfect binary search increments
+ }
+ return Arrays.binarySearch((Compare[]) in, from, to, find, comparator);
+ }
+
+ /**
+ * @return the actual height of {@code tree}
+ */
+ public static int height(Object[] tree)
+ {
+ if (isLeaf(tree))
+ return 1;
+
+ int height = 1;
+ while (!isLeaf(tree))
+ {
+ height++;
+ tree = (Object[]) tree[shallowSizeOfBranch(tree)];
+ }
+ return height;
+ }
+
+ /**
+ * @return the maximum representable size at {@code height}.
+ */
+ private static int denseSize(int height)
+ {
+ return treeSize2n(height, BRANCH_SHIFT);
+ }
+
+ /**
+ * @return the maximum representable size at {@code height}.
+ */
+ private static int checkedDenseSize(int height)
+ {
+ assert height * BRANCH_SHIFT < 32;
+ return denseSize(height);
+ }
+
+ /**
+ * Computes the number of nodes in a full tree of height {@code height}
+ * and with {@code 2^branchShift} branch factor.
+ * i.e. computes {@code (2^branchShift)^height - 1}
+ */
+ private static int treeSize2n(int height, int branchShift)
+ {
+ return (1 << (branchShift * height)) - 1;
+ }
+
+ // TODO: test
+ private static int maxRootHeight(int size)
+ {
+ if (size <= BRANCH_FACTOR)
+ return 1;
+ return 1 + heightAtSize2n((size - 1) / 2, BRANCH_SHIFT - 1);
+ }
+
+ private static int sizeOfBranch(Object[] branch)
+ {
+ int length = branch.length;
+ // length - 1 == getChildEnd == getPositionOfSizeMap
+ // (length / 2) - 1 == getChildCount - 1 == position of full tree size
+ // hard code this, as will be used often;
+ return ((int[]) branch[length - 1])[(length / 2) - 1];
+ }
+
+ /**
+ * Checks if the UpdateFunction is an instance of {@code UpdateFunction.Simple}.
+ */
+ private static boolean isSimple(UpdateFunction<?, ?> updateF)
+ {
+ return updateF instanceof UpdateFunction.Simple;
+ }
+
+ /**
+ * @return the size map for the branch node
+ */
+ static int[] sizeMap(Object[] branch)
+ {
+ return (int[]) branch[branch.length - 1];
+ }
+
+ // Arbitrary boundaries
+ private static Object POSITIVE_INFINITY = new Object();
+ private static Object NEGATIVE_INFINITY = new Object();
+
+ /**
+ * simple static wrapper to calls to cmp.compare() which checks if either a or b are Special (i.e. represent an infinity)
+ */
+ private static <V> int compareWellFormed(Comparator<V> cmp, Object a, Object b)
+ {
+ if (a == b)
+ return 0;
+ if (a == NEGATIVE_INFINITY | b == POSITIVE_INFINITY)
+ return -1;
+ if (b == NEGATIVE_INFINITY | a == POSITIVE_INFINITY)
+ return 1;
+ return cmp.compare((V) a, (V) b);
+ }
+
+ public static boolean isWellFormed(Object[] btree, Comparator<?> cmp)
+ {
+ return isWellFormedReturnHeight(cmp, btree, true, NEGATIVE_INFINITY, POSITIVE_INFINITY) >= 0;
+ }
+
+ private static int isWellFormedReturnHeight(Comparator<?> cmp, Object[] node, boolean isRoot, Object min, Object max)
+ {
+ if (isEmpty(node))
+ return 0;
+
+ if (cmp != null && !isNodeWellFormed(cmp, node, min, max))
+ return -1;
+
+ int keyCount = shallowSize(node);
+ if (keyCount < 1)
+ return -1;
+ if (!isRoot && keyCount < BRANCH_FACTOR / 2 - 1)
+ return -1;
+ if (keyCount >= BRANCH_FACTOR)
+ return -1;
+
+ if (isLeaf(node))
+ return 0;
+
+ int[] sizeMap = sizeMap(node);
+ int size = 0;
+ int childHeight = -1;
+ // compare each child node with the branch element at the head of this node it corresponds with
+ for (int i = childOffset(node); i < childEndOffset(node); i++)
+ {
+ Object[] child = (Object[]) node[i];
+ Object localmax = i < node.length - 2 ? node[i - childOffset(node)] : max;
+ int height = isWellFormedReturnHeight(cmp, child, false, min, localmax);
+ if (height == -1)
+ return -1;
+ if (childHeight == -1)
+ childHeight = height;
+ if (childHeight != height)
+ return -1;
+
+ min = localmax;
+ size += size(child);
+ if (sizeMap[i - childOffset(node)] != size)
+ return -1;
+ size += 1;
+ }
+
+ return childHeight + 1;
+ }
+
+ private static boolean isNodeWellFormed(Comparator<?> cmp, Object[] node, Object min, Object max)
+ {
+ Object previous = min;
+ int end = shallowSize(node);
+ for (int i = 0; i < end; i++)
+ {
+ Object current = node[i];
+ if (compareWellFormed(cmp, previous, current) >= 0)
+ return false;
+
+ previous = current;
+ }
+ return compareWellFormed(cmp, previous, max) < 0;
+ }
+
+ /**
+ * Build a tree of unknown size, in order.
+ * <p>
+ * Can be used with {@link #reverseInSitu} to build a tree in reverse.
+ */
+ public static <V> FastBuilder<V> fastBuilder()
+ {
+ TinyThreadLocalPool.TinyPool<FastBuilder<?>> pool = FastBuilder.POOL.get();
+ FastBuilder<V> builder = (FastBuilder<V>) pool.poll();
+ if (builder == null)
+ builder = new FastBuilder<>();
+ builder.pool = pool;
+ return builder;
+ }
+
+ /**
+ * Base class for AbstractFastBuilder.BranchBuilder, LeafBuilder and AbstractFastBuilder,
+ * containing shared behaviour and declaring some useful abstract methods.
+ */
+ private static abstract class LeafOrBranchBuilder
+ {
+ final int height;
+ final LeafOrBranchBuilder child;
+ BranchBuilder parent;
+
+ /**
+ * The current buffer contents (if any) of the leaf or branch - always sized to contain a complete
+ * node of the form being constructed. Always non-null, except briefly during overflow.
+ */
+ Object[] buffer;
+ /**
+ * The number of keys in our buffer, whether or not we are building a leaf or branch; if we are building
+ * a branch, we will ordinarily have the same number of children as well, except temporarily when finishing
+ * the construction of the node.
+ */
+ int count;
+
+ /**
+ * either
+ * 1) an empty leftover buffer from a past usage, which can be used when we exhaust {@code buffer}; or
+ * 2) a full {@code buffer} that has been parked until we next overflow, so we can steal some back
+ * if we finish before reaching MIN_KEYS in {@code buffer}
+ */
+ Object[] savedBuffer;
+ /**
+ * The key we overflowed on when populating savedBuffer. If null, {@link #savedBuffer} is logically empty.
+ */
+ Object savedNextKey;
+
+ LeafOrBranchBuilder(LeafOrBranchBuilder child)
+ {
+ this.height = child == null ? 1 : 1 + child.height;
+ this.child = child;
+ }
+
+ /**
+ * Do we have enough keys in the builder to construct at least one balanced node?
+ * We could have enough to build two.
+ */
+ final boolean isSufficient()
+ {
+ return hasOverflow() || count >= MIN_KEYS;
+ }
+
+ /**
+ * Do we have an already constructed node saved, that we can propagate or redistribute?
+ * This implies we are building two nodes, since {@link #savedNextKey} would overflow {@link #savedBuffer}
+ */
+ final boolean hasOverflow()
+ {
+ return savedNextKey != null;
+ }
+
+ /**
+ * Do we have an already constructed node saved AND insufficient keys in our buffer, so
+ * that we need to share the contents of {@link #savedBuffer} with {@link #buffer} to construct
+ * our results?
+ */
+ final boolean mustRedistribute()
+ {
+ return hasOverflow() && count < MIN_KEYS;
+ }
+
+ /**
+ * Are we empty, i.e. we have no contents in either {@link #buffer} or {@link #savedBuffer}
+ */
+ final boolean isEmpty()
+ {
+ return count == 0 && savedNextKey == null;
+ }
+
+ /**
+ * Drain the contents of this builder and build up to two nodes, as necessary.
+ * If {@code unode != null} and we are building a single node that is identical to it, use {@code unode} instead.
+ * If {@code propagateTo != null} propagate any nodes we build to it.
+ *
+ * @return the last node we construct
+ */
+ abstract Object[] drainAndPropagate(Object[] unode, BranchBuilder propagateTo);
+
+ /**
+ * Drain the contents of this builder and build at most one node.
+ * Requires {@code !hasOverflow()}
+ *
+ * @return the node we construct
+ */
+ abstract Object[] drain();
+
+ /**
+ * Complete the build. Drains the node and any used or newly-required parent and returns the root of the
+ * resulting tree.
+ *
+ * @return the root of the constructed tree.
+ */
+ public Object[] completeBuild()
+ {
+ LeafOrBranchBuilder level = this;
+ while (true)
+ {
+ if (!level.hasOverflow())
+ return level.drain();
+
+ BranchBuilder parent = level.ensureParent();
+ level.drainAndPropagate(null, parent);
+ if (level.savedBuffer != null)
+ Arrays.fill(level.savedBuffer, null);
+ level = parent;
+ }
+ }
+
+ /**
+ * Takes a node that would logically occur directly preceding the current buffer contents,
+ * and the key that would separate them in a parent node, and prepends their contents
+ * to the current buffer's contents. This can be used to redistribute already-propagated
+ * contents to a parent in cases where this is convenient (i.e. when transforming)
+ *
+ * @param predecessor directly preceding node
+ * @param predecessorNextKey key that would have separated predecessor from buffer contents
+ */
+ abstract void prepend(Object[] predecessor, Object predecessorNextKey);
+
+ /**
+ * Indicates if this builder produces dense nodes, i.e. those that are populated with MAX_KEYS
+ * at every level. Only the last two children of any branch may be non-dense, and in some cases only
+ * the last two nodes in any tier of the tree.
+ * <p>
+ * This flag switches whether or not we maintain a buffer of sizes, or use the globally shared contents of
+ * DENSE_SIZE_MAPS.
+ */
+ abstract boolean producesOnlyDense();
+
+ /**
+ * Ensure there is a {@code branch.parent}, and return it
+ */
+ final BranchBuilder ensureParent()
+ {
+ if (parent == null)
+ parent = new BranchBuilder(this);
+ parent.inUse = true;
+ return parent;
+ }
+
+ /**
+ * Mark a branch builder as utilised, so that we must clear it when resetting any {@link AbstractFastBuilder}
+ *
+ * @return {@code branch}
+ */
+ static BranchBuilder markUsed(BranchBuilder branch)
+ {
+ branch.inUse = true;
+ return branch;
+ }
+
+ /**
+ * A utility method for comparing a range of two arrays
+ */
+ static boolean areIdentical(Object[] a, int aOffset, Object[] b, int bOffset, int count)
+ {
+ for (int i = 0; i < count; ++i)
+ {
+ if (a[i + aOffset] != b[i + bOffset])
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * A utility method for comparing a range of two arrays
+ */
+ static boolean areIdentical(int[] a, int aOffset, int[] b, int bOffset, int count)
+ {
+ for (int i = 0; i < count; ++i)
+ {
+ if (a[i + aOffset] != b[i + bOffset])
+ return false;
+ }
+ return true;
+ }
+ }
+
+ /**
+ * LeafBuilder for methods pertaining specifically to building a leaf in an {@link AbstractFastBuilder}.
+ * Note that {@link AbstractFastBuilder} extends this class directly, however it is convenient to maintain
+ * distinct classes in the hierarchy for clarity of behaviour and intent.
+ */
+ private static abstract class LeafBuilder extends LeafOrBranchBuilder
+ {
+ LeafBuilder()
+ {
+ super(null);
+ buffer = new Object[MAX_KEYS];
+ }
+
+ /**
+ * Add {@code nextKey} to the buffer, overflowing if necessary
+ */
+ public void addKey(Object nextKey)
+ {
+ if (count == MAX_KEYS)
+ overflow(nextKey);
+ else
+ buffer[count++] = nextKey;
+ }
+
+ /**
+ * Add {@code nextKey} to the buffer; the caller specifying overflow is unnecessary
+ */
+ public void addKeyNoOverflow(Object nextKey)
+ {
+ buffer[count++] = nextKey;
+ }
+
+ /**
+ * Add {@code nextKey} to the buffer; the caller specifying overflow is unnecessary
+ */
+ public void maybeAddKeyNoOverflow(Object nextKey)
+ {
+ buffer[count] = nextKey;
+ count += nextKey != null ? 1 : 0;
+ }
+
+ /**
+ * Add {@code nextKey} to the buffer; the caller specifying overflow is unnecessary
+ */
+ public void maybeAddKey(Object nextKey)
+ {
+ if (count == MAX_KEYS)
+ {
+ if (nextKey != null)
+ overflow(nextKey);
+ }
+ else
+ {
+ buffer[count] = nextKey;
+ count += nextKey != null ? 1 : 0;
+ }
+ }
+
+ /**
+ * Copy the contents of {@code source[from..to)} to {@code buffer}, overflowing as necessary.
+ */
+ void copy(Object[] source, int offset, int length)
+ {
+ if (count + length > MAX_KEYS)
+ {
+ int copy = MAX_KEYS - count;
+ System.arraycopy(source, offset, buffer, count, copy);
+ offset += copy;
+// implicitly: count = MAX_KEYS;
+ overflow(source[offset++]);
+ length -= 1 + copy;
+ }
+ System.arraycopy(source, offset, buffer, count, length);
+ count += length;
+ }
+
+ /**
+ * Copy the contents of {@code source[from..to)} to {@code buffer}; the caller specifying overflow is unnecessary
+ */
+ void copyNoOverflow(Object[] source, int offset, int length)
+ {
+ System.arraycopy(source, offset, buffer, count, length);
+ count += length;
+ }
+
+ /**
+ * Copy the contents of the data to {@code buffer}, overflowing as necessary.
+ */
+ <Insert, Existing> void copy(Object[] source, int offset, int length, UpdateFunction<Insert, Existing> apply)
+ {
+ if (isSimple(apply))
+ {
+ copy(source, offset, length);
+ return;
+ }
+
+ if (count + length > MAX_KEYS)
+ {
+ int copy = MAX_KEYS - count;
+ for (int i = 0; i < copy; ++i)
+ buffer[count + i] = apply.insert((Insert) source[offset + i]);
+ offset += copy;
+// implicitly: leaf().count = MAX_KEYS;
+ overflow(apply.insert((Insert) source[offset++]));
+ length -= 1 + copy;
+ }
+
+ for (int i = 0; i < length; ++i)
+ buffer[count + i] = apply.insert((Insert) source[offset + i]);
+ count += length;
+
+ }
+
+ /**
+ * {@link #buffer} is full, and we need to make room either by populating {@link #savedBuffer},
+ * propagating its current contents, if any, to {@link #parent}
+ */
+ void overflow(Object nextKey)
+ {
+ if (hasOverflow())
+ propagateOverflow();
+
+ // precondition: count == MAX_KEYS and savedNextKey == null
+
+ Object[] newBuffer = savedBuffer;
+ if (newBuffer == null)
+ newBuffer = new Object[MAX_KEYS];
+
+ savedBuffer = buffer;
+ savedNextKey = nextKey;
+ buffer = newBuffer;
+ count = 0;
+ }
+
+ /**
+ * Redistribute the contents of {@link #savedBuffer} into {@link #buffer}, finalise {@link #savedBuffer} and flush upwards.
+ * Invoked when we are building from {@link #buffer}, have insufficient values but a complete leaf in {@link #savedBuffer}
+ *
+ * @return the size of the leaf we flushed to our parent from {@link #savedBuffer}
+ */
+ Object[] redistributeOverflowAndDrain()
+ {
+ Object[] newLeaf = redistributeAndDrain(savedBuffer, MAX_KEYS, savedNextKey);
+ savedNextKey = null;
+ return newLeaf;
+ }
+
+ /**
+ * Redistribute the contents of {@link #buffer} and an immediate predecessor into a new leaf,
+ * then construct a new predecessor with the remaining contents and propagate up to our parent
+ * Invoked when we are building from {@link #buffer}, have insufficient values but either a complete
+ * leaf in {@link #savedBuffer} or can exfiltrate one from our parent to redistribute.
+ *
+ * @return the second of the two new leaves
+ */
+ Object[] redistributeAndDrain(Object[] pred, int predSize, Object predNextKey)
+ {
+ // precondition: savedLeafCount == MAX_KEYS && leaf().count < MIN_KEYS
+ // ensure we have at least MIN_KEYS in leaf().buffer
+ // first shift leaf().buffer and steal some keys from leaf().savedBuffer and leaf().savedBufferNextKey
+ int steal = MIN_KEYS - count;
+ Object[] newLeaf = new Object[MIN_KEYS];
+ System.arraycopy(pred, predSize - (steal - 1), newLeaf, 0, steal - 1);
+ newLeaf[steal - 1] = predNextKey;
+ System.arraycopy(buffer, 0, newLeaf, steal, count);
+
+ // then create a leaf out of the remainder of savedBuffer
+ int newPredecessorCount = predSize - steal;
+ Object[] newPredecessor = new Object[newPredecessorCount | 1];
+ System.arraycopy(pred, 0, newPredecessor, 0, newPredecessorCount);
+ ensureParent().addChildAndNextKey(newPredecessor, newPredecessorCount, pred[newPredecessorCount]);
+ return newLeaf;
+ }
+
+ /**
+ * Invoked to fill our {@link #buffer} to >= MIN_KEYS with data ocurring before {@link #buffer};
+ * possibly instead fills {@link #savedBuffer}
+ *
+ * @param pred directly preceding node
+ * @param predNextKey key that would have separated predecessor from buffer contents
+ */
+ void prepend(Object[] pred, Object predNextKey)
+ {
+ assert !hasOverflow();
+ int predSize = sizeOfLeaf(pred);
+ int newKeys = 1 + predSize;
+ if (newKeys + count <= MAX_KEYS)
+ {
+ System.arraycopy(buffer, 0, buffer, newKeys, count);
+ System.arraycopy(pred, 0, buffer, 0, predSize);
+ buffer[predSize] = predNextKey;
+ count += newKeys;
+ }
+ else
+ {
+ if (savedBuffer == null)
+ savedBuffer = new Object[MAX_KEYS];
+ System.arraycopy(pred, 0, savedBuffer, 0, predSize);
+ if (predSize == MAX_KEYS)
+ {
+ savedNextKey = predNextKey;
+ }
+ else
+ {
+ int removeKeys = MAX_KEYS - predSize;
+ count -= removeKeys;
+ savedBuffer[predSize] = predNextKey;
+ System.arraycopy(buffer, 0, savedBuffer, predSize + 1, MAX_KEYS - newKeys);
+ savedNextKey = buffer[MAX_KEYS - newKeys];
+ System.arraycopy(buffer, removeKeys, buffer, 0, count);
+ }
+ }
+ }
+
+ /**
+ * Invoked when we want to add a key to the leaf buffer, but it is full
+ */
+ void propagateOverflow()
+ {
+ // propagate the leaf we have saved in savedBuffer
+ // precondition: savedLeafCount == MAX_KEYS
+ ensureParent().addChildAndNextKey(savedBuffer, MAX_KEYS, savedNextKey);
+ savedBuffer = null;
+ savedNextKey = null;
+ }
+
+ /**
+ * Construct a new leaf from the contents of {@link #buffer}, unless the contents have not changed
+ * from {@code unode}, in which case return {@code unode} to avoid allocating unnecessary objects.
+ *
+ * This is only called when we have enough data to complete the node, i.e. we have MIN_KEYS or more items added
+ * or the node is the BTree's root.
+ */
+ Object[] drainAndPropagate(Object[] unode, BranchBuilder propagateTo)
+ {
+ Object[] leaf;
+ int sizeOfLeaf;
+ if (mustRedistribute())
+ {
+ // we have too few items, so spread the two buffers across two new nodes
+ leaf = redistributeOverflowAndDrain();
+ sizeOfLeaf = MIN_KEYS;
+ }
+ else if (!hasOverflow() && unode != null && count == sizeOfLeaf(unode) && areIdentical(buffer, 0, unode, 0, count))
+ {
+ // we have exactly the same contents as the original node, so reuse it
+ leaf = unode;
+ sizeOfLeaf = count;
+ }
+ else
+ {
+ // we have maybe one saved full buffer, and one buffer with sufficient contents to copy
+ if (hasOverflow())
+ propagateOverflow();
+
+ sizeOfLeaf = count;
+ leaf = drain();
+ }
+
+ count = 0;
+ if (propagateTo != null)
+ propagateTo.addChild(leaf, sizeOfLeaf);
+ return leaf;
+ }
+
+ /**
+ * Construct a new leaf from the contents of {@code leaf().buffer}, assuming that the node does not overflow.
+ */
+ Object[] drain()
+ {
+ // the number of children here may be smaller than MIN_KEYS if this is the root node
+ assert !hasOverflow();
+ if (count == 0)
+ return empty();
+
+ Object[] newLeaf = new Object[count | 1];
+ System.arraycopy(buffer, 0, newLeaf, 0, count);
+ count = 0;
+ return newLeaf;
+ }
+ }
+
+ static class BranchBuilder extends LeafOrBranchBuilder
+ {
+ final LeafBuilder leaf;
+
+ /**
+ * sizes of the children in {@link #buffer}. If null, we only produce dense nodes.
+ */
+ int[] sizes;
+ /**
+ * sizes of the children in {@link #savedBuffer}
+ */
+ int[] savedSizes;
+ /**
+ * marker to limit unnecessary work with unused levels, esp. on reset
+ */
+ boolean inUse;
+
+ BranchBuilder(LeafOrBranchBuilder child)
+ {
+ super(child);
+ buffer = new Object[2 * (MAX_KEYS + 1)];
+ if (!child.producesOnlyDense())
+ sizes = new int[MAX_KEYS + 1];
+ this.leaf = child instanceof LeafBuilder ? (LeafBuilder) child : ((BranchBuilder) child).leaf;
+ }
+
+ /**
+ * Ensure there is room to add another key to {@code branchBuffers[branchIndex]}, and add it;
+ * invoke {@link #overflow} if necessary
+ */
+ void addKey(Object key)
+ {
+ if (count == MAX_KEYS)
+ overflow(key);
+ else
+ buffer[count++] = key;
+ }
+
+ /**
+ * To be invoked when there's a key already inserted to the buffer that requires a corresponding
+ * right-hand child, for which the buffers are sized to ensure there is always room.
+ */
+ void addChild(Object[] child, int sizeOfChild)
+ {
+ buffer[MAX_KEYS + count] = child;
+ recordSizeOfChild(sizeOfChild);
+ }
+
+ void recordSizeOfChild(int sizeOfChild)
+ {
+ if (sizes != null)
+ sizes[count] = sizeOfChild;
+ }
+
+ /**
+ * See {@link BranchBuilder#addChild(Object[], int)}
+ */
+ void addChild(Object[] child)
+ {
+ addChild(child, sizes == null ? 0 : size(child));
+ }
+
+ /**
+ * Insert a new child into a parent branch, when triggered by {@code overflowLeaf} or {@code overflowBranch}
+ */
+ void addChildAndNextKey(Object[] newChild, int newChildSize, Object nextKey)
+ {
+ // we should always have room for a child to the right of any key we have previously inserted
+ buffer[MAX_KEYS + count] = newChild;
+ recordSizeOfChild(newChildSize);
+ // but there may not be room for another key
+ addKey(nextKey);
+ }
+
+ /**
+ * Invoked when we want to add a key to the leaf buffer, but it is full
+ */
+ void propagateOverflow()
+ {
+ // propagate the leaf we have saved in leaf().savedBuffer
+ int size = setOverflowSizeMap(savedBuffer, MAX_KEYS);
+ ensureParent().addChildAndNextKey(savedBuffer, size, savedNextKey);
+ savedBuffer = null;
+ savedNextKey = null;
+ }
+
+ /**
+ * Invoked when a branch already contains {@code MAX_KEYS}, and another child is ready to be added.
+ * Creates a new neighbouring node containing MIN_KEYS items, shifting back the remaining MIN_KEYS+1
+ * items to the start of the buffer(s).
+ */
+ void overflow(Object nextKey)
+ {
+ if (hasOverflow())
+ propagateOverflow();
+
+ Object[] restoreBuffer = savedBuffer;
+ int[] restoreSizes = savedSizes;
+
+ savedBuffer = buffer;
+ savedSizes = sizes;
+ savedNextKey = nextKey;
+
+ sizes = restoreSizes == null && savedSizes != null ? new int[MAX_KEYS + 1] : restoreSizes;
+ buffer = restoreBuffer == null ? new Object[2 * (MAX_KEYS + 1)] : restoreBuffer;
+ count = 0;
+ }
+
+ /**
+ * Redistribute the contents of branch.savedBuffer into branch.buffer, finalise savedBuffer and flush upwards.
+ * Invoked when we are building from branch, have insufficient values but a complete branch in savedBuffer.
+ *
+ * @return the size of the branch we flushed to our parent from savedBuffer
+ */
+ Object[] redistributeOverflowAndDrain()
+ {
+ // now ensure we have at least MIN_KEYS in buffer
+ // both buffer and savedBuffer should be balanced, so that we have count+1 and MAX_KEYS+1 children respectively
+ // we need to utilise savedNextKey, so we want to take {@code steal-1} keys from savedBuffer, {@code steal) children
+ // and the dangling key we use in place of savedNextKey for our parent key.
+ int steal = MIN_KEYS - count;
+ Object[] newBranch = new Object[2 * (MIN_KEYS + 1)];
+ System.arraycopy(savedBuffer, MAX_KEYS - (steal - 1), newBranch, 0, steal - 1);
+ newBranch[steal - 1] = savedNextKey;
+ System.arraycopy(buffer, 0, newBranch, steal, count);
+ System.arraycopy(savedBuffer, 2 * MAX_KEYS + 1 - steal, newBranch, MIN_KEYS, steal);
+ System.arraycopy(buffer, MAX_KEYS, newBranch, MIN_KEYS + steal, count + 1);
+ setRedistributedSizeMap(newBranch, steal);
+
+ // then create a branch out of the remainder of savedBuffer
+ int savedBranchCount = MAX_KEYS - steal;
+ Object[] savedBranch = new Object[2 * (savedBranchCount + 1)];
+ System.arraycopy(savedBuffer, 0, savedBranch, 0, savedBranchCount);
+ System.arraycopy(savedBuffer, MAX_KEYS, savedBranch, savedBranchCount, savedBranchCount + 1);
+ int savedBranchSize = setOverflowSizeMap(savedBranch, savedBranchCount);
+ ensureParent().addChildAndNextKey(savedBranch, savedBranchSize, savedBuffer[savedBranchCount]);
+ savedNextKey = null;
+
+ return newBranch;
+ }
+
+ /**
+ * See {@link LeafOrBranchBuilder#prepend(Object[], Object)}
+ */
+ void prepend(Object[] pred, Object predNextKey)
+ {
+ assert !hasOverflow();
+ // assumes sizes != null, since only makes sense to use this method in that context
+
+ int predKeys = shallowSizeOfBranch(pred);
+ int[] sizeMap = (int[]) pred[2 * predKeys + 1];
+ int newKeys = 1 + predKeys;
+ if (newKeys + count <= MAX_KEYS)
+ {
+ System.arraycopy(buffer, 0, buffer, newKeys, count);
+ System.arraycopy(sizes, 0, sizes, newKeys, count + 1);
+ System.arraycopy(buffer, MAX_KEYS, buffer, MAX_KEYS + newKeys, count + 1);
+
+ System.arraycopy(pred, 0, buffer, 0, predKeys);
+ buffer[predKeys] = predNextKey;
+ System.arraycopy(pred, predKeys, buffer, MAX_KEYS, predKeys + 1);
+ copySizeMapToSizes(sizeMap, 0, sizes, 0, predKeys + 1);
+ count += newKeys;
+ }
+ else
+ {
+ if (savedBuffer == null)
+ {
+ savedBuffer = new Object[2 * (1 + MAX_KEYS)];
+ savedSizes = new int[1 + MAX_KEYS];
+ }
+
+ System.arraycopy(pred, 0, savedBuffer, 0, predKeys);
+ System.arraycopy(pred, predKeys, savedBuffer, MAX_KEYS, predKeys + 1);
+ copySizeMapToSizes(sizeMap, 0, savedSizes, 0, predKeys + 1);
+ if (newKeys == MAX_KEYS + 1)
+ {
+ savedNextKey = predNextKey;
+ }
+ else
+ {
+ int removeKeys = (1 + MAX_KEYS - newKeys);
+ int remainingKeys = count - removeKeys;
+
+ savedBuffer[predKeys] = predNextKey;
+ System.arraycopy(buffer, 0, savedBuffer, newKeys, MAX_KEYS - newKeys);
+ savedNextKey = buffer[MAX_KEYS - newKeys];
+ System.arraycopy(sizes, 0, savedSizes, newKeys, MAX_KEYS + 1 - newKeys);
+ System.arraycopy(buffer, MAX_KEYS, savedBuffer, MAX_KEYS + newKeys, MAX_KEYS + 1 - newKeys);
+ System.arraycopy(buffer, removeKeys, buffer, 0, remainingKeys);
+ System.arraycopy(buffer, MAX_KEYS + removeKeys, buffer, MAX_KEYS, remainingKeys + 1);
+ System.arraycopy(sizes, removeKeys, sizes, 0, remainingKeys + 1);
+ count = remainingKeys;
+ }
+ }
+ }
+
+ boolean producesOnlyDense()
+ {
+ return sizes == null;
+ }
+
+ /**
+ * Construct a new branch from the contents of {@code branchBuffers[branchIndex]}, unless the contents have
+ * not changed from {@code unode}, in which case return {@code unode} to avoid allocating unnecessary objects.
+ *
+ * This is only called when we have enough data to complete the node, i.e. we have MIN_KEYS or more items added
+ * or the node is the BTree's root.
+ */
+ Object[] drainAndPropagate(Object[] unode, BranchBuilder propagateTo)
+ {
+ int sizeOfBranch;
+ Object[] branch;
+ if (mustRedistribute())
+ {
+ branch = redistributeOverflowAndDrain();
+ sizeOfBranch = sizeOfBranch(branch);
+ }
+ else
+ {
+ int usz = unode != null ? shallowSizeOfBranch(unode) : -1;
+ if (!hasOverflow() && usz == count
+ && areIdentical(buffer, 0, unode, 0, usz)
+ && areIdentical(buffer, MAX_KEYS, unode, usz, usz + 1))
+ {
+ branch = unode;
+ sizeOfBranch = sizeOfBranch(branch);
+ }
+ else
+ {
+ if (hasOverflow())
+ propagateOverflow();
+
+ // the number of children here may be smaller than MIN_KEYS if this is the root node, but there must
+ // be at least one key / two children.
+ assert count > 0;
+ branch = new Object[2 * (count + 1)];
+ System.arraycopy(buffer, 0, branch, 0, count);
+ System.arraycopy(buffer, MAX_KEYS, branch, count, count + 1);
+ sizeOfBranch = setDrainSizeMap(unode, usz, branch, count);
+ }
+ }
+
+ count = 0;
+ if (propagateTo != null)
+ propagateTo.addChild(branch, sizeOfBranch);
+
+ return branch;
+ }
+
+ /**
+ * Construct a new branch from the contents of {@code buffer}, assuming that the node does not overflow.
+ */
+ Object[] drain()
+ {
+ assert !hasOverflow();
+ int keys = count;
+ count = 0;
+
+ Object[] branch = new Object[2 * (keys + 1)];
+ if (keys == MAX_KEYS)
+ {
+ Object[] tmp = buffer;
+ buffer = branch;
+ branch = tmp;
+ }
+ else
+ {
+ System.arraycopy(buffer, 0, branch, 0, keys);
+ System.arraycopy(buffer, MAX_KEYS, branch, keys, keys + 1);
+ }
+ setDrainSizeMap(null, -1, branch, keys);
+ return branch;
+ }
+
+ /**
+ * Compute (or fetch from cache) and set the sizeMap in {@code branch}, knowing that it
+ * was constructed from for the contents of {@code buffer}.
+ * <p>
+ * For {@link FastBuilder} these are mostly the same, so they are fetched from a global cache and
+ * resized accordingly, but for {@link AbstractUpdater} we maintain a buffer of sizes.
+ */
+ int setDrainSizeMap(Object[] original, int keysInOriginal, Object[] branch, int keysInBranch)
+ {
+ if (producesOnlyDense())
+ return setImperfectSizeMap(branch, keysInBranch);
+
+ // first convert our buffer contents of sizes to represent a sizeMap
+ int size = sizesToSizeMap(this.sizes, keysInBranch + 1);
+ // then attempt to reuse the sizeMap from the original node, by comparing the buffer's contents with it
+ int[] sizeMap;
+ if (keysInOriginal != keysInBranch || !areIdentical(sizeMap = sizeMap(original), 0, this.sizes, 0, keysInBranch + 1))
+ {
+ // if we cannot, then we either take the buffer wholesale and replace its buffer, or copy a prefix
+ sizeMap = this.sizes;
+ if (keysInBranch < MAX_KEYS)
+ sizeMap = Arrays.copyOf(sizeMap, keysInBranch + 1);
+ else
+ this.sizes = new int[MAX_KEYS + 1];
+ }
+ branch[2 * keysInBranch + 1] = sizeMap;
+ return size;
+ }
+
+ /**
+ * Compute (or fetch from cache) and set the sizeMap in {@code branch}, knowing that it
+ * was constructed from for the contents of {@code savedBuffer}.
+ * <p>
+ * For {@link FastBuilder} these are always the same size, so they are fetched from a global cache,
+ * but for {@link AbstractUpdater} we maintain a buffer of sizes.
+ *
+ * @return the size of {@code branch}
+ */
+ int setOverflowSizeMap(Object[] branch, int keys)
+ {
+ if (producesOnlyDense())
+ {
+ int[] sizeMap = DENSE_SIZE_MAPS[height - 2];
+ if (keys < MAX_KEYS)
+ sizeMap = Arrays.copyOf(sizeMap, keys + 1);
+ branch[2 * keys + 1] = sizeMap;
+ return keys < MAX_KEYS ? sizeMap[keys] : checkedDenseSize(height + 1);
+ }
+ else
+ {
+ int[] sizes = savedSizes;
+ if (keys < MAX_KEYS)
+ sizes = Arrays.copyOf(sizes, keys + 1);
+ else
+ savedSizes = null;
+ branch[2 * keys + 1] = sizes;
+ return sizesToSizeMap(sizes);
+ }
+ }
+
+ /**
+ * Compute (or fetch from cache) and set the sizeMap in {@code branch}, knowing that it
+ * was constructed from the contents of both {@code savedBuffer} and {@code buffer}
+ * <p>
+ * For {@link FastBuilder} these are mostly the same size, so they are fetched from a global cache
+ * and only the last items updated, but for {@link AbstractUpdater} we maintain a buffer of sizes.
+ */
+ void setRedistributedSizeMap(Object[] branch, int steal)
+ {
+ if (producesOnlyDense())
+ {
+ setImperfectSizeMap(branch, MIN_KEYS);
+ }
+ else
+ {
+ int[] sizeMap = new int[MIN_KEYS + 1];
+ System.arraycopy(sizes, 0, sizeMap, steal, count + 1);
+ System.arraycopy(savedSizes, MAX_KEYS + 1 - steal, sizeMap, 0, steal);
+ branch[2 * MIN_KEYS + 1] = sizeMap;
+ sizesToSizeMap(sizeMap);
+ }
+ }
+
+ /**
+ * Like {@link #setOverflowSizeMap}, but used for building the sizeMap of a node whose
+ * last two children may have had their contents redistributed; uses the perfect size map
+ * for all but the final two children, and queries the size of the last children directly
+ */
+ private int setImperfectSizeMap(Object[] branch, int keys)
+ {
+ int[] sizeMap = Arrays.copyOf(DENSE_SIZE_MAPS[height - 2], keys + 1);
+ int size = keys == 1 ? 0 : 1 + sizeMap[keys - 2];
+ sizeMap[keys - 1] = size += size((Object[]) branch[2 * keys - 1]);
+ sizeMap[keys] = size += 1 + size((Object[]) branch[2 * keys]);
+ branch[2 * keys + 1] = sizeMap;
+ return size;
+ }
+
+ /**
+ * Copy the contents of {@code unode} into {@code branchBuffers[branchIndex]},
+ * starting at the child before key with index {@code offset} up to and
+ * including the key with index {@code offset + length - 1}.
+ */
+ void copyPreceding(Object[] unode, int usz, int offset, int length)
+ {
+ int[] uszmap = sizeMap(unode);
+ if (count + length > MAX_KEYS)
+ {
+ // we will overflow, so copy to MAX_KEYS and trigger overflow
+ int copy = MAX_KEYS - count;
+ copyPrecedingNoOverflow(unode, usz, uszmap, offset, copy);
+ offset += copy;
+
+ // copy last child that fits
+ buffer[MAX_KEYS + MAX_KEYS] = unode[usz + offset];
+ sizes[MAX_KEYS] = uszmap[offset] - (offset > 0 ? (1 + uszmap[offset - 1]) : 0);
+
+ overflow(unode[offset]);
+
+ length -= 1 + copy;
+ ++offset;
+ }
+
+ copyPrecedingNoOverflow(unode, usz, uszmap, offset, length);
+ }
+
+ /**
+ * Copy the contents of {@code unode} into {@code branchBuffers[branchIndex]},
+ * between keys {@code from} and {@code to}, with the caller declaring overflow is unnecessary.
+ * {@code from} may be {@code -1}, representing the first child only;
+ * all other indices represent the key/child pairs that follow (i.e. a key and its right-hand child).
+ */
+ private void copyPrecedingNoOverflow(Object[] unode, int usz, int[] uszmap, int offset, int length)
+ {
+ if (length <= 1)
+ {
+ if (length == 0)
+ return;
+
+ buffer[count] = unode[offset];
+ buffer[MAX_KEYS + count] = unode[usz + offset];
+ sizes[count] = uszmap[offset] - (offset > 0 ? (1 + uszmap[offset - 1]) : 0);
+ ++count;
+ }
+ else
+ {
+ System.arraycopy(unode, offset, buffer, count, length);
+ System.arraycopy(unode, usz + offset, buffer, MAX_KEYS + count, length);
+ copySizeMapToSizes(uszmap, offset, sizes, count, length);
+ count += length;
+ }
+ }
+
+ /**
+ * Copy a region of a cumulative sizeMap into an array of plain sizes
+ */
+ static void copySizeMapToSizes(int[] in, int inOffset, int[] out, int outOffset, int count)
+ {
+ assert count > 0;
+ if (inOffset == 0)
+ {
+ // we don't need to subtract anything from the first node, so just copy it so we can keep the rest of the loop simple
+ out[outOffset++] = in[inOffset++];
+ --count;
+ }
+ for (int i = 0; i < count; ++i)
+ out[outOffset + i] = in[inOffset + i] - (1 + in[inOffset + i - 1]);
+ }
+ }
+
+ /**
+ * Shared parent of {@link FastBuilder} and {@link Updater}, both of which
+ * construct their trees in order without knowing the resultant size upfront.
+ * <p>
+ * Maintains a simple stack of buffers that we provide utilities to navigate and update.
+ */
+ private static abstract class AbstractFastBuilder extends LeafBuilder
+ {
+ final boolean producesOnlyDense()
+ {
+ return getClass() == FastBuilder.class;
+ }
+
+ /**
+ * An aesthetic convenience for declaring when we are interacting with the leaf, instead of invoking {@code this} directly
+ */
+ final LeafBuilder leaf()
+ {
+ return this;
+ }
+
+ /**
+ * Clear any references we might still retain, to avoid holding onto memory.
+ * <p>
+ * While this method is not strictly necessary, it exists to
+ * ensure the implementing classes are aware they must handle it.
+ */
+ abstract void reset();
+ }
+
+ /**
+ * A pooled builder for constructing a tree in-order, and without needing any reconciliation.
+ * <p>
+ * Constructs whole nodes in place, so that a flush of a complete node can take its buffer entirely.
+ * Since we build trees of a predictable shape (i.e. perfectly dense) we do not construct a size map.
+ */
+ public static class FastBuilder<V> extends AbstractFastBuilder implements AutoCloseable
+ {
+ private static final TinyThreadLocalPool<FastBuilder<?>> POOL = new TinyThreadLocalPool<>();
+ private TinyThreadLocalPool.TinyPool<FastBuilder<?>> pool;
+
+ FastBuilder()
+ {
+ } // disable allocation tracking
+
+ public void add(V value)
+ {
+ leaf().addKey(value);
+ }
+
+ public void add(Object[] from, int offset, int count)
+ {
+ leaf().copy(from, offset, count);
+ }
+
+ public Object[] build()
+ {
+ return leaf().completeBuild();
+ }
+
+ public Object[] buildReverse()
+ {
+ Object[] result = build();
+ reverseInSitu(result, height(result), false);
+ return result;
+ }
+
+ @Override
+ public void close()
+ {
+ reset();
+ pool.offer(this);
+ pool = null;
+ }
+
+ @Override
+ void reset()
+ {
+ // we clear precisely to leaf().count and branch.count because, in the case of a builder,
+ // if we ever fill the buffer we will consume it entirely for the tree we are building
+ // so the last count should match the number of non-null entries
+ Arrays.fill(leaf().buffer, 0, leaf().count, null);
+ leaf().count = 0;
+ BranchBuilder branch = leaf().parent;
+ while (branch != null && branch.inUse)
+ {
+ Arrays.fill(branch.buffer, 0, branch.count, null);
+ Arrays.fill(branch.buffer, MAX_KEYS, MAX_KEYS + 1 + branch.count, null);
+ branch.count = 0;
+ branch.inUse = false;
+ branch = branch.parent;
+ }
+ }
+ }
+
+ private static abstract class AbstractUpdater extends AbstractFastBuilder implements AutoCloseable
+ {
+ void reset()
+ {
+ assert leaf().count == 0;
+ clearLeafBuffer(leaf().buffer);
+ if (leaf().savedBuffer != null)
+ Arrays.fill(leaf().savedBuffer, null);
+
+ BranchBuilder branch = leaf().parent;
+ while (branch != null && branch.inUse)
+ {
+ assert branch.count == 0;
+ clearBranchBuffer(branch.buffer);
+ if (branch.savedBuffer != null && branch.savedBuffer[0] != null)
+ Arrays.fill(branch.savedBuffer, null); // by definition full, if non-empty
+ branch.inUse = false;
+ branch = branch.parent;
+ }
+ }
+
+ /**
+ * Clear the contents of a branch buffer, aborting once we encounter a null entry
+ * to save time on small trees
+ */
+ private void clearLeafBuffer(Object[] array)
+ {
+ if (array[0] == null)
+ return;
+ // find first null entry; loop from beginning, to amortise cost over size of working set
+ int i = 1;
+ while (i < array.length && array[i] != null)
+ ++i;
+ Arrays.fill(array, 0, i, null);
+ }
+
+ /**
+ * Clear the contents of a branch buffer, aborting once we encounter a null entry
+ * to save time on small trees
+ */
+ private void clearBranchBuffer(Object[] array)
+ {
+ if (array[0] == null)
+ return;
+
+ // find first null entry; loop from beginning, to amortise cost over size of working set
+ int i = 1;
+ while (i < MAX_KEYS && array[i] != null)
+ ++i;
+ Arrays.fill(array, 0, i, null);
+ Arrays.fill(array, MAX_KEYS, MAX_KEYS + i + 1, null);
+ }
+ }
+
+ /**
+ * A pooled object for modifying an existing tree with a new (typically smaller) tree.
+ * <p>
+ * Constructs the new tree around the shape of the existing tree, as though we had performed inserts in
+ * order, copying as much of the original tree as possible. We achieve this by simply merging leaf nodes
+ * up to the immediately following key in an ancestor, maintaining up to two complete nodes in a buffer until
+ * this happens, and flushing any nodes we produce in excess of this immediately into the parent buffer.
+ * <p>
+ * We construct whole nodes in place, except the size map, so that a flush of a complete node can take its buffer
+ * entirely.
+ * <p>
+ * Searches within both trees to accelerate the process of modification, instead of performing a simple
+ * iteration over the new tree.
+ */
+ private static class Updater<Compare, Existing extends Compare, Insert extends Compare> extends AbstractUpdater implements AutoCloseable
+ {
+ static final TinyThreadLocalPool<Updater> POOL = new TinyThreadLocalPool<>();
+ TinyThreadLocalPool.TinyPool<Updater> pool;
+
+ // the new tree we navigate linearly, and are always on a key or at the end
+ final SimpleTreeKeysIterator<Compare, Insert> insert = new SimpleTreeKeysIterator<>();
+
+ Comparator<? super Compare> comparator;
+ UpdateFunction<Insert, Existing> updateF;
+
+
+ static <Compare, Existing extends Compare, Insert extends Compare> Updater<Compare, Existing, Insert> get()
+ {
+ TinyThreadLocalPool.TinyPool<Updater> pool = POOL.get();
+ Updater<Compare, Existing, Insert> updater = pool.poll();
+ if (updater == null)
+ updater = new Updater<>();
+ updater.pool = pool;
+ return updater;
+ }
+
+ /**
+ * Precondition: {@code update} should not be empty.
+ * <p>
+ * Inserts {@code insert} into {@code update}, after applying {@code updateF} to each item, or matched item pairs.
+ */
+ Object[] update(Object[] update, Object[] insert, Comparator<? super Compare> comparator, UpdateFunction<Insert, Existing> updateF)
+ {
+ this.insert.init(insert);
+ this.updateF = updateF;
+ this.comparator = comparator;
+ int leafDepth = BTree.depth(update) - 1;
+ LeafOrBranchBuilder builder = leaf();
+ for (int i = 0; i < leafDepth; ++i)
+ builder = builder.ensureParent();
+
+ Insert ik = this.insert.next();
+ ik = updateRecursive(ik, update, null, builder);
+ assert ik == null;
+ Object[] result = builder.completeBuild();
+
+ return result;
+ }
+
+ /**
+ * Merge a BTree recursively with the contents of {@code insert} up to the given upper bound.
+ *
+ * @param ik The next key from the inserted data.
+ * @param unode The source branch to update.
+ * @param uub The branch's upper bound
+ * @param builder The builder that will receive the data. It needs to be at the same level of the hierarchy
+ * as the source unode.
+ * @return The next key from the inserted data, >= uub.
+ */
+ private Insert updateRecursive(Insert ik, Object[] unode, Existing uub, LeafOrBranchBuilder builder)
+ {
+ return builder == leaf()
+ ? updateRecursive(ik, unode, uub, (LeafBuilder) builder)
+ : updateRecursive(ik, unode, uub, (BranchBuilder) builder);
+ }
+
+ private Insert updateRecursive(Insert ik, Object[] unode, Existing uub, BranchBuilder builder)
+ {
+ int upos = 0;
+ int usz = shallowSizeOfBranch(unode);
+
+ while (ik != null)
+ {
+ int find = exponentialSearchWithUpperBound(comparator, unode, upos, usz, uub, ik);
+ int c = searchResultToComparison(find);
+ if (find < 0)
+ find = -1 - find;
+
+ if (find > usz)
+ break; // nothing else needs to be inserted in this branch
+ if (find > upos)
+ builder.copyPreceding(unode, usz, upos, find - upos);
+
+ final Existing nextUKey = find < usz ? (Existing) unode[find] : uub;
+ final Object[] childUNode = (Object[]) unode[find + usz];
+
+ // process next child
+ if (c < 0)
+ {
+ // ik fall inside it -- recursively merge the child with the update, using next key as an upper bound
+ LeafOrBranchBuilder childBuilder = builder.child;
+ ik = updateRecursive(ik, childUNode, nextUKey, childBuilder);
+ childBuilder.drainAndPropagate(childUNode, builder);
+ if (find == usz) // this was the right-most child, branch is complete and we can return immediately
+ return ik;
+ c = ik != null ? comparator.compare(nextUKey, ik) : -1;
+ }
+ else
+ builder.addChild(childUNode);
+
+ // process next key
+ if (c == 0)
+ {
+ // ik matches next key
+ builder.addKey(updateF.merge(nextUKey, ik));
+ ik = insert.next();
+ }
+ else
+ builder.addKey(nextUKey);
+
+ upos = find + 1;
+ }
+ // copy the rest of the branch and exit
+ if (upos <= usz)
+ {
+ builder.copyPreceding(unode, usz, upos, usz - upos);
+ builder.addChild((Object[]) unode[usz + usz]);
+ }
+
+ return ik;
+ }
+
+ private Insert updateRecursive(Insert ik, Object[] unode, Existing uub, LeafBuilder builder)
+ {
+ int upos = 0;
+ int usz = sizeOfLeaf(unode);
+ Existing uk = (Existing) unode[upos];
+ int c = comparator.compare(uk, ik);
+
+ while (true)
+ {
+ if (c == 0)
+ {
+ leaf().addKey(updateF.merge(uk, ik));
+ if (++upos < usz)
+ uk = (Existing) unode[upos];
+ ik = insert.next();
+ if (ik == null)
+ {
+ builder.copy(unode, upos, usz - upos);
+ return null;
+ }
+ if (upos == usz)
+ break;
+ c = comparator.compare(uk, ik);
+ }
+ else if (c < 0)
+ {
+ int ulim = exponentialSearch(comparator, unode, upos + 1, usz, ik);
+ c = -searchResultToComparison(ulim); // 0 if match, 1 otherwise
+ if (ulim < 0)
+ ulim = -(1 + ulim);
+ builder.copy(unode, upos, ulim - upos);
+ if ((upos = ulim) == usz)
+ break;
+ uk = (Existing) unode[upos];
+ }
+ else
+ {
+ builder.addKey(isSimple(updateF) ? ik : updateF.insert(ik));
+ c = insert.copyKeysSmallerThan(uk, comparator, builder, updateF); // 0 on match, -1 otherwise
+ ik = insert.next();
+ if (ik == null)
+ {
+ builder.copy(unode, upos, usz - upos);
+ return null;
+ }
+ }
+ }
+ if (uub == null || comparator.compare(ik, uub) < 0)
+ {
+ builder.addKey(isSimple(updateF) ? ik : updateF.insert(ik));
+ insert.copyKeysSmallerThan(uub, comparator, builder, updateF); // 0 on match, -1 otherwise
+ ik = insert.next();
+ }
+ return ik;
+ }
+
+
+ public void close()
+ {
+ reset();
+ pool.offer(this);
+ pool = null;
+ }
+
+ void reset()
+ {
+ super.reset();
+ insert.reset();
+ }
+ }
+
+ static int searchResultToComparison(int searchResult)
+ {
+ return searchResult >> 31;
+ }
+
+ /**
+ * Attempts to perform a clean transformation of the original tree into a new tree,
+ * by replicating its original shape as far as possible.
+ * <p>
+ * We do this by attempting to flush our buffers whenever we finish a source-branch at the given level;
+ * if there are too few contents, we wait until we finish another node at the same level.
+ * <p>
+ * This way, we are always resetting at the earliest point we might be able to reuse more parts of the original
+ * tree, maximising potential reuse.
+ * <p>
+ * This can permit us to build unbalanced right-most nodes at each level, in which case we simply rebalance
+ * when done.
+ * <p>
+ * The approach taken here hopefully balances simplicity, garbage generation and execution time.
+ */
+ private static abstract class AbstractTransformer<I, O> extends AbstractUpdater implements AutoCloseable
+ {
+ /**
+ * An iterator over the tree we are updating
+ */
+ final SimpleTreeIterator update = new SimpleTreeIterator();
+
+ /**
+ * A queue of nodes from update that we are ready to "finish" if we have buffered enough data from them
+ * The stack pointer is maintained inside of {@link #apply()}
+ */
+ Object[][] queuedToFinish = new Object[1][];
+
+ AbstractTransformer()
+ {
+ ensureParent();
+ parent.inUse = false;
+ }
+
+ abstract O apply(I v);
+
+ Object[] apply(Object[] update)
+ {
+ int height = this.update.init(update);
+ if (queuedToFinish.length < height - 1)
+ queuedToFinish = new Object[height - 1][];
+ return apply();
+ }
+
+ /**
+ * We base our operation on the shape of {@code update}, trying to steal as much of the original tree as
+ * possible for our new tree
+ */
+ private Object[] apply()
+ {
+ Object[] unode = update.node();
+ int upos = update.position(), usz = sizeOfLeaf(unode);
+
+ while (true)
+ {
+ // we always start the loop on a leaf node, for both input and output
+ boolean propagatedOriginalLeaf = false;
+ if (leaf().count == 0)
+ {
+ if (upos == 0)
+ { // fast path - buffer is empty and input unconsumed, so may be able to propagate original
+ I in;
+ O out;
+ do
+ { // optimistic loop - find first point the transformation modified our input
+ in = (I) unode[upos];
+ out = apply(in);
+ } while (in == out && ++upos < usz);
+
+ if ((propagatedOriginalLeaf = (upos == usz)))
+ {
+ // if input is unmodified by transformation, propagate the input node
+ markUsed(parent).addChild(unode, usz);
+ }
+ else
+ {
+ // otherwise copy up to the first modified portion,
+ // and fall-through to our below condition for transforming the remainder
+ leaf().copyNoOverflow(unode, 0, upos++);
+ if (out != null)
+ leaf().addKeyNoOverflow(out);
+ }
+ }
+
+ if (!propagatedOriginalLeaf)
+ transformLeafNoOverflow(unode, upos, usz);
+ }
+ else
+ {
+ transformLeaf(unode, upos, usz);
+ }
+
+ // we've finished a leaf, and have to hand it to a parent alongside its right-hand key
+ // so now we try to do two things:
+ // 1) find the next unfiltered key from our unfinished parent
+ // 2) determine how many parents are "finished" and whose buffers we should also attempt to propagate
+ // we do (1) unconditionally, because:
+ // a) we need to handle the branch keys somewhere, and it may as well happen in one place
+ // b) we either need more keys for our incomplete leaf; or
+ // c) we need a key to go after our last propagated node in any unfinished parent
+
+ int finishToHeight = 0;
+ O nextKey;
+ do
+ {
+ update.ascendToParent(); // always have a node above leaf level, else we'd invoke transformLeaf
+ BranchBuilder level = parent;
+ unode = update.node();
+ upos = update.position();
+ usz = shallowSizeOfBranch(unode);
+
+ while (upos == usz)
+ {
+ queuedToFinish[level.height - 2] = unode;
+ finishToHeight = max(finishToHeight, level.height);
+
+ if (!update.ascendToParent())
+ return finishAndDrain(propagatedOriginalLeaf);
+
+ level = level.ensureParent();
+ unode = update.node();
+ upos = update.position();
+ usz = shallowSizeOfBranch(unode);
+ }
+
+ nextKey = apply((I) unode[upos]);
+ if (nextKey == null && leaf().count > MIN_KEYS) // if we don't have a key, try to steal from leaf().buffer
+ nextKey = (O) leaf().buffer[--leaf().count];
+
+ update.descendIntoNextLeaf(unode, upos, usz);
+ unode = update.node();
+ upos = update.position();
+ usz = sizeOfLeaf(unode);
+
+ // nextKey might have been filtered, so we may need to look in this next leaf for it
+ while (nextKey == null && upos < usz)
+ nextKey = apply((I) unode[upos++]);
+
+ // if we still found no key loop and try again on the next parent, leaf, parent... ad infinitum
+ } while (nextKey == null);
+
+ // we always end with unode a leaf, though it may be that upos == usz and that we will do nothing with it
+
+ // we've found a non-null key, now decide what to do with it:
+ // 1) if we have insufficient keys in our leaf, simply append to the leaf and continue;
+ // 2) otherwise, walk our parent branches finishing those *before* {@code finishTo}
+ // 2a) if any cannot be finished, append our new key to it and stop finishing further parents; they
+ // will be finished the next time we ascend to their level with a complete chain of finishable branches
+ // 2b) otherwise, add our new key to {@code finishTo}
+
+ if (!propagatedOriginalLeaf && !finish(leaf(), null))
+ {
+ leaf().addKeyNoOverflow(nextKey);
+ continue;
+ }
+
+ BranchBuilder finish = parent;
+ while (true)
+ {
+ if (finish.height <= finishToHeight)
+ {
+ Object[] originalNode = queuedToFinish[finish.height - 2];
+ if (finish(finish, originalNode))
+ {
+ finish = finish.parent;
+ continue;
+ }
+ }
+
+ // add our key to the last unpropagated parent branch buffer
+ finish.addKey(nextKey);
+ break;
+ }
+ }
+ }
+
+ private void transformLeafNoOverflow(Object[] unode, int upos, int usz)
+ {
+ while (upos < usz)
+ {
+ O v = apply((I) unode[upos++]);
+ leaf().maybeAddKeyNoOverflow(v);
+ }
+ }
+
+ private void transformLeaf(Object[] unode, int upos, int usz)
+ {
+ while (upos < usz)
+ {
+ O v = apply((I) unode[upos++]);
+ leaf().maybeAddKey(v);
+ }
+ }
+
+ /**
+ * Invoked when we are finished transforming a branch. If the buffer contains insufficient elements,
+ * we refuse to construct a leaf and return null. Otherwise we propagate the branch to its parent's buffer
+ * and return the branch we have constructed.
+ */
+ private boolean finish(LeafOrBranchBuilder level, Object[] unode)
+ {
+ if (!level.isSufficient())
+ return false;
+
+ level.drainAndPropagate(unode, level.ensureParent());
+ return true;
+ }
+
+ /**
+ * Invoked once we have consumed all input.
+ * <p>
+ * Completes all unfinished buffers. If they do not contain enough keys, data is stolen from the preceding
+ * node to the left on the same level. This is easy if our parent already contains a completed child; if it
+ * does not, we recursively apply the stealing procedure to obtain a non-empty parent. If this process manages
+ * to reach the root and still find no preceding branch, this will result in making this branch the new root.
+ */
+ private Object[] finishAndDrain(boolean skipLeaf)
+ {
+ LeafOrBranchBuilder level = leaf();
+ if (skipLeaf)
+ {
+ level = nonEmptyParentMaybeSteal(level);
+ // handle an edge case, where we have propagated a single complete leaf but have no other contents in any parent
+ if (level == null)
+ return (Object[]) leaf().parent.buffer[MAX_KEYS];
+ }
+ while (true)
+ {
+ BranchBuilder parent = nonEmptyParentMaybeSteal(level);
+ if (parent != null && !level.isSufficient())
+ {
+ Object[] result = stealAndMaybeRepropagate(level, parent);
+ if (result != null)
+ return result;
+ }
+ else
+ {
+
+ Object[] originalNode = level == leaf() ? null : queuedToFinish[level.height - 2];
+ Object[] result = level.drainAndPropagate(originalNode, parent);
+ if (parent == null)
+ return result;
+ }
+ level = parent;
+ }
+ }
+
+ BranchBuilder nonEmptyParentMaybeSteal(LeafOrBranchBuilder level)
+ {
+ if (level.hasOverflow())
+ return level.ensureParent();
+ BranchBuilder parent = level.parent;
+ if (parent == null || !parent.inUse || (parent.isEmpty() && !tryPrependFromParent(parent)))
+ return null;
+ return parent;
+ }
+
+ /**
+ * precondition: {@code fill.parentInUse()} must return {@code fill.parent}
+ * <p>
+ * Steal some data from our ancestors, if possible.
+ * 1) If no ancestor has any data to steal, simply drain and return the current contents.
+ * 2) If we exhaust all of our ancestors, and are not now ourselves overflowing, drain and return
+ * 3) Otherwise propagate the redistributed contents to our parent and return null, indicating we can continue to parent
+ *
+ * @return {@code null} if {@code parent} is still logicallly in use after we execute;
+ * otherwise the return value is the final result
+ */
+ private Object[] stealAndMaybeRepropagate(LeafOrBranchBuilder fill, BranchBuilder parent)
+ {
+ // parent already stole, we steal one from it
+ prependFromParent(fill, parent);
+
+ // if we've emptied our parent, attempt to restore it from our grandparent,
+ // this is so that we can determine an accurate exhausted status
+ boolean exhausted = !fill.hasOverflow() && parent.isEmpty() && !tryPrependFromParent(parent);
+ if (exhausted)
+ return fill.drain();
+
+ fill.drainAndPropagate(null, parent);
+ return null;
+ }
+
+ private boolean tryPrependFromParent(BranchBuilder parent)
+ {
+ BranchBuilder grandparent = nonEmptyParentMaybeSteal(parent);
+ if (grandparent == null)
+ return false;
+ prependFromParent(parent, grandparent);
+ return true;
+ }
+
+ // should only be invoked with parent = parentIfStillInUse(fill), if non-null result
+ private void prependFromParent(LeafOrBranchBuilder fill, BranchBuilder parent)
+ {
+ assert !parent.isEmpty();
+
+ Object[] predecessor;
+ Object predecessorNextKey;
+ // parent will have same number of children as shallow key count (and may be empty)
+ if (parent.count == 0 && parent.hasOverflow())
+ {
+ // use the saved buffer instead of going to our parent
+ predecessorNextKey = parent.savedNextKey;
+ predecessor = (Object[]) parent.savedBuffer[2 * MAX_KEYS];
+ Object[] tmpBuffer = parent.savedBuffer;
+ int[] tmpSizes = parent.savedSizes;
+ parent.savedBuffer = parent.buffer;
+ parent.savedSizes = parent.sizes;
+ parent.buffer = tmpBuffer;
+ parent.sizes = tmpSizes;
+ parent.savedNextKey = null;
+ parent.count = MAX_KEYS;
+ // end with MAX_KEYS keys and children in parent, having stolen MAX_KEYS+1 child and savedNextKey
+ }
+ else
+ {
+ --parent.count;
+ predecessor = (Object[]) parent.buffer[MAX_KEYS + parent.count];
+ predecessorNextKey = parent.buffer[parent.count];
+ }
+
+ fill.prepend(predecessor, predecessorNextKey);
+ }
+
+ void reset()
+ {
+ Arrays.fill(queuedToFinish, 0, update.leafDepth, null);
+ update.reset();
+ super.reset();
+ }
+ }
+
+
+ private static class Transformer<I, O> extends AbstractTransformer<I, O>
+ {
+ static final TinyThreadLocalPool<Transformer> POOL = new TinyThreadLocalPool<>();
+ TinyThreadLocalPool.TinyPool<Transformer> pool;
+
+ Function<? super I, ? extends O> apply;
+
+ O apply(I v)
+ {
+ return apply.apply(v);
+ }
+
+ static <I, O> Transformer<I, O> get(Function<? super I, ? extends O> apply)
+ {
+ TinyThreadLocalPool.TinyPool<Transformer> pool = POOL.get();
+ Transformer<I, O> transformer = pool.poll();
+ if (transformer == null)
+ transformer = new Transformer<>();
+ transformer.pool = pool;
+ transformer.apply = apply;
+ return transformer;
+ }
+
+ public void close()
+ {
+ apply = null;
+ reset();
+ pool.offer(this);
+ pool = null;
+ }
+ }
+
+ private static class BiTransformer<I, I2, O> extends AbstractTransformer<I, O>
+ {
+ static final TinyThreadLocalPool<BiTransformer> POOL = new TinyThreadLocalPool<>();
+
+ BiFunction<? super I, ? super I2, ? extends O> apply;
+ I2 i2;
+ TinyThreadLocalPool.TinyPool<BiTransformer> pool;
+
+ O apply(I i1)
+ {
+ return apply.apply(i1, i2);
+ }
+
+ static <I, I2, O> BiTransformer<I, I2, O> get(BiFunction<? super I, ? super I2, ? extends O> apply, I2 i2)
+ {
+ TinyThreadLocalPool.TinyPool<BiTransformer> pool = POOL.get();
+ BiTransformer<I, I2, O> transformer = pool.poll();
+ if (transformer == null)
+ transformer = new BiTransformer<>();
+ transformer.pool = pool;
+ transformer.apply = apply;
+ transformer.i2 = i2;
+ return transformer;
+ }
+
+ public void close()
+ {
+ apply = null;
+ i2 = null;
+ reset();
+ pool.offer(this);
+ pool = null;
+ }
+ }
+
+ /**
+ * A base class for very simple walks of a tree without recursion, supporting reuse
+ */
+ private static abstract class SimpleTreeStack
+ {
+ // stack we have descended, with 0 the root node
+ Object[][] nodes;
+ /**
+ * the child node we are in, if at lower height, or the key we are on otherwise
+ * can be < 0, indicating we have not yet entered the contents of the node, and are deliberating
+ * whether we descend or consume the contents without descending
+ */
+ int[] positions;
+ int depth, leafDepth;
+
+ void reset()
+ {
+ Arrays.fill(nodes, 0, leafDepth + 1, null);
+ // positions gets zero'd during descent
+ }
+
+ Object[] node()
+ {
+ return nodes[depth];
+ }
+
+ int position()
+ {
+ return positions[depth];
+ }
+ }
+
+ // Similar to SimpleTreeNavigator, but visits values eagerly
+ // (the exception being ascendToParent(), which permits iterating through finished parents).
+ // Begins by immediately descending to first leaf; if empty terminates immediately.
+ private static class SimpleTreeIterator extends SimpleTreeStack
+ {
+ int init(Object[] tree)
+ {
+ int maxHeight = maxRootHeight(size(tree));
+ if (positions == null || maxHeight >= positions.length)
+ {
+ positions = new int[maxHeight + 1];
+ nodes = new Object[maxHeight + 1][];
+ }
+ nodes[0] = tree;
+ if (isEmpty(tree))
+ {
+ // already done
+ leafDepth = 0;
+ depth = -1;
+ }
+ else
+ {
+ depth = 0;
+ positions[0] = 0;
+ while (!isLeaf(tree))
+ {
+ tree = (Object[]) tree[shallowSizeOfBranch(tree)];
+ nodes[++depth] = tree;
+ positions[depth] = 0;
+ }
+ leafDepth = depth;
+ }
+ return leafDepth + 1;
+ }
+
+ void descendIntoNextLeaf(Object[] node, int pos, int sz)
+ {
+ positions[depth] = ++pos;
+ ++depth;
+ nodes[depth] = node = (Object[]) node[sz + pos];
+ positions[depth] = 0;
+ while (depth < leafDepth)
+ {
+ ++depth;
+ nodes[depth] = node = (Object[]) node[shallowSizeOfBranch(node)];
+ positions[depth] = 0;
+ }
+ }
+
+ boolean ascendToParent()
+ {
+ if (depth < 0)
+ return false;
+ return --depth >= 0;
+ }
+ }
+
+
+ private static class SimpleTreeKeysIterator<Compare, Insert extends Compare>
+ {
+ int leafSize;
+ int leafPos;
+ Object[] leaf;
+ Object[][] nodes;
+ int[] positions;
+ int depth;
+
+ void init(Object[] tree)
+ {
+ int maxHeight = maxRootHeight(size(tree));
+ if (positions == null || maxHeight >= positions.length)
+ {
+ positions = new int[maxHeight + 1];
+ nodes = new Object[maxHeight + 1][];
+ }
+ depth = 0;
+ descendToLeaf(tree);
+ }
+
+ void reset()
+ {
+ leaf = null;
+ Arrays.fill(nodes, 0, nodes.length, null);
+ }
+
+ Insert next()
+ {
+ if (leafPos < leafSize) // fast path
+ return (Insert) leaf[leafPos++];
+
+ if (depth == 0)
+ return null;
+
+ Object[] node = nodes[depth - 1];
+ final int position = positions[depth - 1];
+ Insert result = (Insert) node[position];
+ advanceBranch(node, position + 1);
+ return result;
+ }
+
+ private void advanceBranch(Object[] node, int position)
+ {
+ int count = shallowSizeOfBranch(node);
+ if (position < count)
+ positions[depth - 1] = position;
+ else
+ --depth; // no more children in this branch, remove from stack
+ descendToLeaf((Object[]) node[count + position]);
+ }
+
+ void descendToLeaf(Object[] node)
+ {
+ while (!isLeaf(node))
+ {
+ nodes[depth] = node;
+ positions[depth] = 0;
+ node = (Object[]) node[shallowSizeOfBranch(node)];
+ ++depth;
+ }
+ leaf = node;
+ leafPos = 0;
+ leafSize = sizeOfLeaf(node);
+ }
+
+ <Update> int copyKeysSmallerThan(Compare bound, Comparator<? super Compare> comparator, LeafBuilder builder, UpdateFunction<Insert, Update> transformer)
+ {
+ while (true)
+ {
+ int lim = exponentialSearchForMaybeInfinity(comparator, leaf, leafPos, leafSize, bound);
+ int end = lim >= 0 ? lim : -1 - lim;
+ if (end > leafPos)
+ {
+ builder.copy(leaf, leafPos, end - leafPos, transformer);
+ leafPos = end;
+ }
+ if (end < leafSize)
+ return searchResultToComparison(lim); // 0 if next is a match for bound, -1 otherwise
+
+ if (depth == 0)
+ return -1;
+
+ Object[] node = nodes[depth - 1];
+ final int position = positions[depth - 1];
+ Insert branchKey = (Insert) node[position];
+ int cmp = compareWithMaybeInfinity(comparator, branchKey, bound);
+ if (cmp >= 0)
+ return -cmp;
+ builder.addKey(isSimple(transformer) ? branchKey : transformer.insert(branchKey));
+ advanceBranch(node, position + 1);
+ }
+ }
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/BTreeBiMap.java b/accord-core/src/main/java/accord/utils/btree/BTreeBiMap.java
new file mode 100644
index 0000000..ae0fea6
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/BTreeBiMap.java
@@ -0,0 +1,102 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package accord.utils.btree;
+
+import java.util.Comparator;
+import java.util.Set;
+
+import com.google.common.collect.BiMap;
+
+import static java.util.Comparator.naturalOrder;
+
+public class BTreeBiMap<K, V> extends AbstractBTreeMap<K, V> implements BiMap<K, V>
+{
+ private final Object[] inverse;
+ private final KeyComparator<V, K> valueComparator;
+
+ protected static <K, V> BTreeBiMap<K, V> withComparators(Object[] tree, Object [] inverse, Comparator<K> comparator, Comparator<V> valueComparator)
+ {
+ return new BTreeBiMap<>(tree, inverse, new KeyComparator<>(comparator), new KeyComparator<>(valueComparator));
+ }
+
+ private BTreeBiMap(Object[] tree, Object [] inverse, KeyComparator<K, V> comparator, KeyComparator<V, K> valueComparator)
+ {
+ super(tree, comparator);
+ this.valueComparator = valueComparator;
+ this.inverse = inverse;
+ }
+
+ public static <K, V> BTreeBiMap<K, V> empty(Comparator<K> comparator, Comparator<V> valueComparator)
+ {
+ return withComparators(BTree.empty(), BTree.empty(), comparator, valueComparator);
+ }
+
+ public static <K extends Comparable<K>, V extends Comparable<V>> BTreeBiMap<K, V> empty()
+ {
+ return BTreeBiMap.<K, V>empty(naturalOrder(), naturalOrder());
+ }
+
+ @Override
+ public BiMap<V, K> inverse()
+ {
+ return new BTreeBiMap<>(inverse, tree, valueComparator, comparator);
+ }
+
+ @Override
+ public BTreeBiMap<K, V> with(K key, V value)
+ {
+ if (key == null || value == null)
+ throw new NullPointerException();
+ AbstractBTreeMap.Entry<K, V> entry = new AbstractBTreeMap.Entry<>(key, value);
+ AbstractBTreeMap.Entry<V, K> inverseEntry = new AbstractBTreeMap.Entry<>(value, key);
+ if (BTree.find(tree, comparator, entry) != null)
+ throw new IllegalArgumentException("Key already exists in map: " + key);
+ if (BTree.find(inverse, valueComparator, inverseEntry) != null)
+ throw new IllegalArgumentException("Value already exists in map: " + value);
+
+ return new BTreeBiMap<>(BTree.update(tree, new Object[]{ entry }, comparator, UpdateFunction.noOp()),
+ BTree.update(inverse, new Object[] { new AbstractBTreeMap.Entry<>(value, key) }, valueComparator, UpdateFunction.noOp()),
+ comparator,
+ valueComparator);
+ }
+
+ @Override
+ public BTreeBiMap<K, V> withForce(K key, V value)
+ {
+ // todo: optimise
+ return without(key).with(key, value);
+ }
+
+ public BTreeBiMap<K, V> without(K key)
+ {
+ AbstractBTreeMap.Entry<K, V> entry = new AbstractBTreeMap.Entry<>(key, null);
+ AbstractBTreeMap.Entry<K, V> existingEntry = BTree.find(tree, comparator, entry);
+ if (existingEntry == null)
+ return this;
+
+ Object[] newTree = BTreeRemoval.remove(tree, comparator, new AbstractBTreeMap.Entry<>(key, null));
+ Object[] newInverse = BTreeRemoval.remove(inverse, valueComparator, new AbstractBTreeMap.Entry<>(existingEntry.getValue(), null));
+ return new BTreeBiMap<>(newTree, newInverse, comparator, valueComparator);
+ }
+
+ public Set<V> values()
+ {
+ return inverse().keySet();
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/BTreeMap.java b/accord-core/src/main/java/accord/utils/btree/BTreeMap.java
new file mode 100644
index 0000000..ebf15c4
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/BTreeMap.java
@@ -0,0 +1,230 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package accord.utils.btree;
+
+import java.util.Comparator;
+import java.util.Map;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.SortedMap;
+
+import static java.util.Comparator.naturalOrder;
+
+
+public class BTreeMap<K, V> extends AbstractBTreeMap<K, V> implements NavigableMap<K, V>
+{
+ protected static <K, V> BTreeMap<K, V> withComparator(Object[] tree, Comparator<K> comparator)
+ {
+ return new BTreeMap<>(tree, new KeyComparator<>(comparator));
+ }
+
+ protected BTreeMap(Object[] tree, KeyComparator<K, V> comparator)
+ {
+ super(tree, comparator);
+ }
+
+ public static <K, V> BTreeMap<K, V> empty(Comparator<K> comparator)
+ {
+ return withComparator(BTree.empty(), comparator);
+ }
+
+ public static <K extends Comparable<K>, V> BTreeMap<K, V> empty()
+ {
+ return BTreeMap.<K, V>empty(naturalOrder());
+ }
+
+ @Override
+ public BTreeMap<K, V> with(K key, V value)
+ {
+ if (key == null || value == null)
+ throw new NullPointerException();
+
+ AbstractBTreeMap.Entry<K, V> entry = new AbstractBTreeMap.Entry<>(key, value);
+ AbstractBTreeMap.Entry<K, V> existing;
+ if ((existing = BTree.find(tree, comparator, entry)) != null && !existing.equals(entry))
+ throw new IllegalStateException("Map already contains " + key);
+ return new BTreeMap<>(BTree.update(tree, new Object[]{ entry }, comparator, UpdateFunction.noOp()), comparator);
+ }
+
+ public BTreeMap<K, V> withForce(K key, V value)
+ {
+ if (key == null || value == null)
+ throw new NullPointerException();
+ AbstractBTreeMap.Entry<K, V> entry = new AbstractBTreeMap.Entry<>(key, value);
+ return new BTreeMap<>(BTree.update(tree, new Object[] { entry }, comparator, UpdateFunction.Simple.of((a, b) -> b)), comparator);
+ }
+
+ public BTreeMap<K, V> without(K key)
+ {
+ if (key == null)
+ throw new NullPointerException();
+
+ return new BTreeMap<>(BTreeRemoval.remove(tree, comparator, new AbstractBTreeMap.Entry<>(key, null)), comparator);
+ }
+
+ @Override
+ public Map.Entry<K, V> lowerEntry(K key)
+ {
+ return BTree.lower(tree, comparator, new AbstractBTreeMap.Entry<>(key, null));
+ }
+
+ @Override
+ public K lowerKey(K key)
+ {
+ Map.Entry<K, V> entry = lowerEntry(key);
+ return entry == null ? null : entry.getKey();
+ }
+
+ @Override
+ public Map.Entry<K, V> floorEntry(K key)
+ {
+ return BTree.floor(tree, comparator, new AbstractBTreeMap.Entry<>(key, null));
+ }
+
+ @Override
+ public K floorKey(K key)
+ {
+ Map.Entry<K, V> entry = floorEntry(key);
+ return entry == null ? null : entry.getKey();
+ }
+
+ @Override
+ public Map.Entry<K, V> ceilingEntry(K key)
+ {
+ return BTree.ceil(tree, comparator, new AbstractBTreeMap.Entry<>(key, null));
+ }
+
+ @Override
+ public K ceilingKey(K key)
+ {
+ Map.Entry<K, V> entry = ceilingEntry(key);
+ return entry == null ? null : entry.getKey();
+ }
+
+ @Override
+ public Map.Entry<K, V> higherEntry(K key)
+ {
+ return BTree.higher(tree, comparator, new AbstractBTreeMap.Entry<>(key, null));
+ }
+
+ @Override
+ public K higherKey(K key)
+ {
+ Map.Entry<K, V> entry = higherEntry(key);
+ return entry == null ? null : entry.getKey();
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public Map.Entry<K, V> firstEntry()
+ {
+ if (isEmpty())
+ return null;
+ return (AbstractBTreeMap.Entry<K, V>) BTree.iterator(tree).next();
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public Map.Entry<K, V> lastEntry()
+ {
+ return getEntry(size() - 1);
+ }
+
+ @Override
+ public NavigableMap<K, V> descendingMap()
+ {
+ return new BTreeMap<>(BTree.build(BulkIterator.of(BTree.iterable(tree, BTree.Dir.DESC).iterator()), BTree.size(tree), UpdateFunction.noOp),
+ new KeyComparator<>(comparator.keyComparator.reversed()));
+ }
+
+ @Override
+ public NavigableSet<K> navigableKeySet()
+ {
+ throw new UnsupportedOperationException("todo");
+ }
+
+ @Override
+ public NavigableSet<K> descendingKeySet()
+ {
+ throw new UnsupportedOperationException("todo");
+ }
+
+ @Override
+ public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
+ {
+ throw new UnsupportedOperationException("todo");
+ }
+
+ @Override
+ public NavigableMap<K, V> headMap(K toKey, boolean inclusive)
+ {
+ throw new UnsupportedOperationException("todo");
+ }
+
+ @Override
+ public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive)
+ {
+ throw new UnsupportedOperationException("todo");
+ }
+
+ @Override
+ public Comparator<K> comparator()
+ {
+ return comparator.keyComparator;
+ }
+
+ @Override
+ public SortedMap<K, V> subMap(K fromKey, K toKey)
+ {
+ throw new UnsupportedOperationException("todo");
+ }
+
+ @Override
+ public SortedMap<K, V> headMap(K toKey)
+ {
+ throw new UnsupportedOperationException("todo");
+ }
+
+ @Override
+ public SortedMap<K, V> tailMap(K fromKey)
+ {
+ throw new UnsupportedOperationException("todo");
+ }
+
+ @Override
+ public K firstKey()
+ {
+ if (BTree.isEmpty(tree))
+ return null;
+ return BTree.<Map.Entry<K, V>>findByIndex(tree, 0).getKey();
+ }
+
+ @Override
+ public K lastKey()
+ {
+ if (BTree.isEmpty(tree))
+ return null;
+ return getEntry(size() - 1).getKey();
+ }
+
+ private Map.Entry<K, V> getEntry(int idx)
+ {
+ return BTree.findByIndex(tree, idx);
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/BTreeMultimap.java b/accord-core/src/main/java/accord/utils/btree/BTreeMultimap.java
new file mode 100644
index 0000000..aa7467d
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/BTreeMultimap.java
@@ -0,0 +1,213 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package accord.utils.btree;
+
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Set;
+import javax.annotation.Nullable;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMultiset;
+import com.google.common.collect.Multimap;
+import com.google.common.collect.Multiset;
+
+import static java.util.Comparator.naturalOrder;
+
+public class BTreeMultimap<K, V> implements Multimap<K, V>
+{
+ private final BTreeMap<K, Collection<V>> map;
+ private final Comparator<K> comparator;
+ private final Comparator<V> valueComparator;
+ private final int size;
+
+ private BTreeMultimap(BTreeMap<K, Collection<V>> map, Comparator<K> comparator, Comparator<V> valueComparator, int size)
+ {
+ this.map = map;
+ this.comparator = comparator;
+ this.valueComparator = valueComparator;
+ this.size = size;
+ }
+
+ public static <K extends Comparable<K>, V extends Comparable<V>> BTreeMultimap<K, V> empty()
+ {
+ return new BTreeMultimap<K, V>(BTreeMap.empty(), naturalOrder(), naturalOrder(), 0);
+ }
+
+ public BTreeMultimap<K, V> with(K key, V value)
+ {
+ if (map.containsKey(key))
+ {
+ BTreeSet<V> oldSet = (BTreeSet<V>) map.get(key);
+ BTreeSet<V> newSet = oldSet.with(value);
+ int newSize = size + newSet.size() - oldSet.size();
+ return new BTreeMultimap<>(map.without(key).with(key, newSet), comparator, valueComparator, newSize);
+ }
+ else
+ {
+ BTreeSet<V> newSet = BTreeSet.of(valueComparator, value);
+ return new BTreeMultimap<>(map.with(key, newSet), comparator, valueComparator, size + 1);
+ }
+ }
+
+ public BTreeMultimap<K, V> without(K key)
+ {
+ Collection<V> oldSet = map.get(key);
+ if (oldSet == null)
+ return this;
+ int newSize = size - oldSet.size();
+ return new BTreeMultimap<>(map.without(key), comparator, valueComparator, newSize);
+ }
+
+ public BTreeMultimap<K, V> without(K key, V value)
+ {
+ BTreeSet<V> values = (BTreeSet<V>) map.get(key);
+ if (values == null)
+ return this;
+ if (!values.contains(value))
+ return this;
+ BTreeSet<V> newValues = BTreeSet.wrap(BTreeRemoval.remove(values.tree, valueComparator, value), valueComparator);
+ BTreeMap<K, Collection<V>> newMap = map.without(key);
+ if (newValues.isEmpty())
+ return new BTreeMultimap<>(newMap, comparator, valueComparator, size - 1);
+
+ return new BTreeMultimap<>(newMap.with(key, newValues), comparator, valueComparator, size - 1);
+ }
+
+ @Override
+ public int size()
+ {
+ return size;
+ }
+
+ @Override
+ public boolean isEmpty()
+ {
+ return map.isEmpty();
+ }
+
+ @Override
+ public boolean containsKey(@Nullable Object o)
+ {
+ if (o == null)
+ return false;
+ return map.containsKey(o);
+ }
+
+ @Override
+ public boolean containsValue(@Nullable Object o)
+ {
+ if (o == null)
+ return false;
+ for (Map.Entry<K, Collection<V>> e : map.entrySet())
+ if (e.getValue().contains(o))
+ return true;
+ return false;
+ }
+
+ @Override
+ public boolean containsEntry(@Nullable Object key, @Nullable Object value)
+ {
+ if (key == null || value == null)
+ throw new NullPointerException();
+ return map.containsKey(key) && map.get(key).contains(value);
+ }
+
+ @Override
+ public Collection<V> get(@Nullable K k)
+ {
+ if (k == null)
+ return null;
+ return map.get(k);
+ }
+
+ @Override
+ public Set<K> keySet()
+ {
+ return map.keySet();
+ }
+
+ @Override
+ public Multiset<K> keys()
+ {
+ ImmutableMultiset.Builder<K> keys = ImmutableMultiset.builder();
+ keys.addAll(map.keySet());
+ return keys.build();
+ }
+
+ @Override
+ public Collection<V> values()
+ {
+ ImmutableList.Builder<V> builder = ImmutableList.builder();
+ for (Map.Entry<K, Collection<V>> entry : map.entrySet())
+ builder.addAll(entry.getValue());
+ return builder.build();
+ }
+
+ @Override
+ public Collection<Map.Entry<K, V>> entries()
+ {
+ Set<Map.Entry<K, V>> entries = new HashSet<>();
+ for (Map.Entry<K, Collection<V>> entry : map.entrySet())
+ for (V v : entry.getValue())
+ entries.add(new AbstractBTreeMap.Entry<>(entry.getKey(), v));
+ return entries;
+ }
+
+ @Override
+ public Map<K, Collection<V>> asMap()
+ {
+ return map;
+ }
+
+ public boolean put(@Nullable K k, @Nullable V v) { throw new UnsupportedOperationException();}
+ public boolean remove(@Nullable Object o, @Nullable Object o1) {throw new UnsupportedOperationException();}
+ public boolean putAll(@Nullable K k, Iterable<? extends V> iterable) {throw new UnsupportedOperationException();}
+ public boolean putAll(Multimap<? extends K, ? extends V> multimap) {throw new UnsupportedOperationException();}
+ public Collection<V> replaceValues(@Nullable K k, Iterable<? extends V> iterable) {throw new UnsupportedOperationException();}
+ public Collection<V> removeAll(@Nullable Object o) {throw new UnsupportedOperationException();}
+ public void clear() { throw new UnsupportedOperationException(); }
+
+ @Override
+ public String toString()
+ {
+ return map.toString();
+ }
+
+ @Override
+ public boolean equals(Object o)
+ {
+ if (this == o) return true;
+ if (!(o instanceof BTreeMultimap)) return false;
+ BTreeMultimap<?, ?> that = (BTreeMultimap<?, ?>) o;
+ return size == that.size &&
+ Objects.equals(map, that.map) &&
+ Objects.equals(comparator, that.comparator) &&
+ Objects.equals(valueComparator, that.valueComparator);
+ }
+
+ @Override
+ public int hashCode()
+ {
+ return Objects.hash(map, comparator, valueComparator, size);
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/BTreeRemoval.java b/accord-core/src/main/java/accord/utils/btree/BTreeRemoval.java
new file mode 100644
index 0000000..e52c0db
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/BTreeRemoval.java
@@ -0,0 +1,345 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package accord.utils.btree;
+
+import java.util.Arrays;
+import java.util.Comparator;
+
+public class BTreeRemoval
+{
+ /**
+ * Remove |elem| from |btree|. If it's not present then return |btree| itself.
+ */
+ public static <V> Object[] remove(final Object[] btree, final Comparator<? super V> comparator, final V elem)
+ {
+ if (BTree.isEmpty(btree))
+ return btree;
+ int index = -1;
+ V elemToSwap = null;
+ int lb = 0;
+ Object[] node = btree;
+ while (true)
+ {
+ int keyEnd = BTree.getKeyEnd(node);
+ int i = Arrays.binarySearch((V[]) node, 0, keyEnd, elem, comparator);
+
+ if (i >= 0)
+ {
+ if (BTree.isLeaf(node))
+ index = lb + i;
+ else
+ {
+ final int indexInNode = BTree.getSizeMap(node)[i];
+ index = lb + indexInNode - 1;
+ elemToSwap = BTree.findByIndex(node, indexInNode - 1);
+ }
+ break;
+ }
+ if (BTree.isLeaf(node))
+ return btree;
+
+ i = -1 - i;
+ if (i > 0)
+ lb += BTree.getSizeMap(node)[i - 1] + 1;
+
+ node = (Object[]) node[keyEnd + i];
+ }
+ if (BTree.size(btree) == 1)
+ return BTree.empty();
+ Object[] result = removeFromLeaf(btree, index);
+ if (elemToSwap != null)
+ BTree.replaceInSitu(result, index, elemToSwap);
+ return result;
+ }
+
+ /**
+ * Remove |elem| from |btree|. It has to be present and it has to reside in a leaf node.
+ */
+ private static Object[] removeFromLeaf(Object[] node, int index)
+ {
+ Object[] result = null;
+ Object[] prevNode = null;
+ int prevI = -1;
+ boolean needsCopy = true;
+ while (!BTree.isLeaf(node))
+ {
+ final int keyEnd = BTree.getBranchKeyEnd(node);
+ int i = -1 - Arrays.binarySearch(BTree.getSizeMap(node), index);
+ if (i > 0)
+ index -= (1 + BTree.getSizeMap(node)[i - 1]);
+ Object[] nextNode = (Object[]) node[keyEnd + i];
+ boolean nextNodeNeedsCopy = true;
+ if (BTree.getKeyEnd(nextNode) > BTree.MIN_KEYS)
+ node = copyIfNeeded(node, needsCopy);
+ else if (i > 0 && BTree.getKeyEnd((Object[]) node[keyEnd + i - 1]) > BTree.MIN_KEYS)
+ {
+ node = copyIfNeeded(node, needsCopy);
+ final Object[] leftNeighbour = (Object[]) node[keyEnd + i - 1];
+ index++;
+ if (!BTree.isLeaf(leftNeighbour))
+ index += BTree.size((Object[])leftNeighbour[BTree.getChildEnd(leftNeighbour) - 1]);
+ nextNode = rotateLeft(node, i);
+ }
+ else if (i < keyEnd && BTree.getKeyEnd((Object[]) node[keyEnd + i + 1]) > BTree.MIN_KEYS)
+ {
+ node = copyIfNeeded(node, needsCopy);
+ nextNode = rotateRight(node, i);
+ }
+ else
+ {
+ nextNodeNeedsCopy = false;
+ if (i > 0)
+ {
+ final Object[] leftNeighbour = (Object[]) node[keyEnd + i - 1];
+ final Object nodeKey = node[i - 1];
+ node = keyEnd == 1 ? null : copyWithKeyAndChildRemoved(node, i - 1, i - 1, false);
+ nextNode = merge(leftNeighbour, nextNode, nodeKey);
+ i = i - 1;
+ index += BTree.size(leftNeighbour) + 1;
+ }
+ else
+ {
+ final Object[] rightNeighbour = (Object[]) node[keyEnd + i + 1];
+ final Object nodeKey = node[i];
+ node = keyEnd == 1 ? null : copyWithKeyAndChildRemoved(node, i, i, false);
+ nextNode = merge(nextNode, rightNeighbour, nodeKey);
+ }
+ }
+
+ if (node != null)
+ {
+ final int[] sizeMap = BTree.getSizeMap(node);
+ for (int j = i; j < sizeMap.length; ++j)
+ sizeMap[j] -= 1;
+ if (prevNode != null)
+ prevNode[prevI] = node;
+ else
+ result = node;
+ prevNode = node;
+ prevI = BTree.getChildStart(node) + i;
+ }
+
+ node = nextNode;
+ needsCopy = nextNodeNeedsCopy;
+ }
+ final int keyEnd = BTree.getLeafKeyEnd(node);
+ final Object[] newLeaf = new Object[(keyEnd & 1) == 1 ? keyEnd : keyEnd - 1];
+ copyKeys(node, newLeaf, 0, index);
+ if (prevNode != null)
+ prevNode[prevI] = newLeaf;
+ else
+ result = newLeaf;
+ return result;
+ }
+
+ private static Object[] rotateRight(final Object[] node, final int i)
+ {
+ final int keyEnd = BTree.getBranchKeyEnd(node);
+ final Object[] nextNode = (Object[]) node[keyEnd + i];
+ final Object[] rightNeighbour = (Object[]) node[keyEnd + i + 1];
+ final boolean leaves = BTree.isLeaf(nextNode);
+ final int nextKeyEnd = BTree.getKeyEnd(nextNode);
+ final Object[] newChild = leaves ? null : (Object[]) rightNeighbour[BTree.getChildStart(rightNeighbour)];
+ final Object[] newNextNode =
+ copyWithKeyAndChildInserted(nextNode, nextKeyEnd, node[i], BTree.getChildCount(nextNode), newChild);
+ node[i] = rightNeighbour[0];
+ node[keyEnd + i + 1] = copyWithKeyAndChildRemoved(rightNeighbour, 0, 0, true);
+ BTree.getSizeMap(node)[i] +=
+ leaves ? 1 : 1 + BTree.size((Object[]) newNextNode[BTree.getChildEnd(newNextNode) - 1]);
+ return newNextNode;
+ }
+
+ private static Object[] rotateLeft(final Object[] node, final int i)
+ {
+ final int keyEnd = BTree.getBranchKeyEnd(node);
+ final Object[] nextNode = (Object[]) node[keyEnd + i];
+ final Object[] leftNeighbour = (Object[]) node[keyEnd + i - 1];
+ final int leftNeighbourEndKey = BTree.getKeyEnd(leftNeighbour);
+ final boolean leaves = BTree.isLeaf(nextNode);
+ final Object[] newChild = leaves ? null : (Object[]) leftNeighbour[BTree.getChildEnd(leftNeighbour) - 1];
+ final Object[] newNextNode = copyWithKeyAndChildInserted(nextNode, 0, node[i - 1], 0, newChild);
+ node[i - 1] = leftNeighbour[leftNeighbourEndKey - 1];
+ node[keyEnd + i - 1] = copyWithKeyAndChildRemoved(leftNeighbour, leftNeighbourEndKey - 1, leftNeighbourEndKey, true);
+ BTree.getSizeMap(node)[i - 1] -= leaves ? 1 : 1 + BTree.getSizeMap(newNextNode)[0];
+ return newNextNode;
+ }
+
+ private static <V> Object[] copyWithKeyAndChildInserted(final Object[] node, final int keyIndex, final V key, final int childIndex, final Object[] child)
+ {
+ final boolean leaf = BTree.isLeaf(node);
+ final int keyEnd = BTree.getKeyEnd(node);
+ final Object[] copy;
+ if (leaf)
+ copy = new Object[keyEnd + ((keyEnd & 1) == 1 ? 2 : 1)];
+ else
+ copy = new Object[node.length + 2];
+
+ if (keyIndex > 0)
+ System.arraycopy(node, 0, copy, 0, keyIndex);
+ copy[keyIndex] = key;
+ if (keyIndex < keyEnd)
+ System.arraycopy(node, keyIndex, copy, keyIndex + 1, keyEnd - keyIndex);
+
+ if (!leaf)
+ {
+ if (childIndex > 0)
+ System.arraycopy(node,
+ BTree.getChildStart(node),
+ copy,
+ keyEnd + 1,
+ childIndex);
+ copy[keyEnd + 1 + childIndex] = child;
+ if (childIndex <= keyEnd)
+ System.arraycopy(node,
+ BTree.getChildStart(node) + childIndex,
+ copy,
+ keyEnd + childIndex + 2,
+ keyEnd - childIndex + 1);
+ final int[] sizeMap = BTree.getSizeMap(node);
+ final int[] newSizeMap = new int[sizeMap.length + 1];
+ if (childIndex > 0)
+ System.arraycopy(sizeMap, 0, newSizeMap, 0, childIndex);
+ final int childSize = BTree.size(child);
+ newSizeMap[childIndex] = childSize + ((childIndex == 0) ? 0 : newSizeMap[childIndex - 1] + 1);
+ for (int i = childIndex + 1; i < newSizeMap.length; ++i)
+ newSizeMap[i] = sizeMap[i - 1] + childSize + 1;
+ copy[copy.length - 1] = newSizeMap;
+ }
+ return copy;
+ }
+
+ private static Object[] copyWithKeyAndChildRemoved(final Object[] node, final int keyIndex, final int childIndex, final boolean substractSize)
+ {
+ final boolean leaf = BTree.isLeaf(node);
+ final Object[] newNode;
+ if (leaf)
+ {
+ final int keyEnd = BTree.getKeyEnd(node);
+ newNode = new Object[keyEnd - ((keyEnd & 1) == 1 ? 0 : 1)];
+ }
+ else
+ {
+ newNode = new Object[node.length - 2];
+ }
+ int offset = copyKeys(node, newNode, 0, keyIndex);
+ if (!leaf)
+ {
+ offset = copyChildren(node, newNode, offset, childIndex);
+ final int[] nodeSizeMap = BTree.getSizeMap(node);
+ final int[] newNodeSizeMap = new int[nodeSizeMap.length - 1];
+ int pos = 0;
+ final int sizeToRemove = BTree.size((Object[])node[BTree.getChildStart(node) + childIndex]) + 1;
+ for (int i = 0; i < nodeSizeMap.length; ++i)
+ if (i != childIndex)
+ newNodeSizeMap[pos++] = nodeSizeMap[i] -
+ ((substractSize && i > childIndex) ? sizeToRemove : 0);
+ newNode[offset] = newNodeSizeMap;
+ }
+ return newNode;
+ }
+
+ private static <V> Object[] merge(final Object[] left, final Object[] right, final V nodeKey)
+ {
+ assert BTree.getKeyEnd(left) == BTree.MIN_KEYS;
+ assert BTree.getKeyEnd(right) == BTree.MIN_KEYS;
+ final boolean leaves = BTree.isLeaf(left);
+ final Object[] result;
+ if (leaves)
+ result = new Object[BTree.MIN_KEYS * 2 + 1];
+ else
+ result = new Object[left.length + right.length];
+ int offset = 0;
+ offset = copyKeys(left, result, offset);
+ result[offset++] = nodeKey;
+ offset = copyKeys(right, result, offset);
+ if (!leaves)
+ {
+ offset = copyChildren(left, result, offset);
+ offset = copyChildren(right, result, offset);
+ final int[] leftSizeMap = BTree.getSizeMap(left);
+ final int[] rightSizeMap = BTree.getSizeMap(right);
+ final int[] newSizeMap = new int[leftSizeMap.length + rightSizeMap.length];
+ offset = 0;
+ offset = copySizeMap(leftSizeMap, newSizeMap, offset, 0);
+ offset = copySizeMap(rightSizeMap, newSizeMap, offset, leftSizeMap[leftSizeMap.length - 1] + 1);
+ result[result.length - 1] = newSizeMap;
+ }
+ return result;
+ }
+
+ private static int copyKeys(final Object[] from, final Object[] to, final int offset)
+ {
+ final int keysCount = BTree.getKeyEnd(from);
+ System.arraycopy(from, 0, to, offset, keysCount);
+ return offset + keysCount;
+ }
+
+ private static int copyKeys(final Object[] from, final Object[] to, final int offset, final int skipIndex)
+ {
+ final int keysCount = BTree.getKeyEnd(from);
+ if (skipIndex > 0)
+ System.arraycopy(from, 0, to, offset, skipIndex);
+ if (skipIndex + 1 < keysCount)
+ System.arraycopy(from, skipIndex + 1, to, offset + skipIndex, keysCount - skipIndex - 1);
+ return offset + keysCount - 1;
+ }
+
+ private static int copyChildren(final Object[] from, final Object[] to, final int offset)
+ {
+ assert !BTree.isLeaf(from);
+ final int start = BTree.getChildStart(from);
+ final int childCount = BTree.getChildCount(from);
+ System.arraycopy(from, start, to, offset, childCount);
+ return offset + childCount;
+ }
+
+ private static int copyChildren(final Object[] from, final Object[] to, final int offset, final int skipIndex)
+ {
+ assert !BTree.isLeaf(from);
+ final int start = BTree.getChildStart(from);
+ final int childCount = BTree.getChildCount(from);
+ if (skipIndex > 0)
+ System.arraycopy(from, start, to, offset, skipIndex);
+ if (skipIndex + 1 <= childCount)
+ System.arraycopy(from, start + skipIndex + 1, to, offset + skipIndex, childCount - skipIndex - 1);
+ return offset + childCount - 1;
+ }
+
+ private static int copySizeMap(final int[] from, final int[] to, final int offset, final int extra)
+ {
+ for (int i = 0; i < from.length; ++i)
+ to[offset + i] = from[i] + extra;
+ return offset + from.length;
+ }
+
+ private static Object[] copyIfNeeded(final Object[] node, boolean needCopy)
+ {
+ if (!needCopy) return node;
+ final Object[] copy = new Object[node.length];
+ System.arraycopy(node, 0, copy, 0, node.length);
+ if (!BTree.isLeaf(node))
+ {
+ final int[] sizeMap = BTree.getSizeMap(node);
+ final int[] copySizeMap = new int[sizeMap.length];
+ System.arraycopy(sizeMap, 0, copySizeMap, 0, sizeMap.length);
+ copy[copy.length - 1] = copySizeMap;
+ }
+ return copy;
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/BTreeSearchIterator.java b/accord-core/src/main/java/accord/utils/btree/BTreeSearchIterator.java
new file mode 100644
index 0000000..de407c1
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/BTreeSearchIterator.java
@@ -0,0 +1,29 @@
+/*
+* Licensed to the Apache Software Foundation (ASF) under one
+* or more contributor license agreements. See the NOTICE file
+* distributed with this work for additional information
+* regarding copyright ownership. The ASF licenses this file
+* to you under the Apache License, Version 2.0 (the
+* "License"); you may not use this file except in compliance
+* with the License. You may obtain a copy of the License at
+*
+* http://www.apache.org/licenses/LICENSE-2.0
+*
+* Unless required by applicable law or agreed to in writing,
+* software distributed under the License is distributed on an
+* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+* KIND, either express or implied. See the License for the
+* specific language governing permissions and limitations
+* under the License.
+*/
+package accord.utils.btree;
+
+import java.util.Iterator;
+
+public interface BTreeSearchIterator<K, V> extends IndexedSearchIterator<K, V>, Iterator<V>
+{
+ /**
+ * Reset this Iterator to its starting position
+ */
+ public void rewind();
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/BTreeSet.java b/accord-core/src/main/java/accord/utils/btree/BTreeSet.java
new file mode 100644
index 0000000..1122da8
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/BTreeSet.java
@@ -0,0 +1,682 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package accord.utils.btree;
+
+import java.util.AbstractSet;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.NavigableSet;
+import java.util.NoSuchElementException;
+import java.util.Objects;
+import java.util.SortedSet;
+import java.util.Spliterator;
+import java.util.Spliterators;
+
+import com.google.common.collect.Ordering;
+
+import static accord.utils.btree.BTree.Dir;
+import static accord.utils.btree.BTree.findIndex;
+
+public class BTreeSet<V> extends AbstractSet<V> implements NavigableSet<V>, List<V>
+{
+ protected final Comparator<? super V> comparator;
+ protected final Object[] tree;
+
+ public BTreeSet(Object[] tree, Comparator<? super V> comparator)
+ {
+ this.tree = tree;
+ this.comparator = comparator;
+ }
+
+ @Override
+ public Comparator<? super V> comparator()
+ {
+ return comparator;
+ }
+
+ protected BTreeSearchIterator<V, V> slice(Dir dir)
+ {
+ return BTree.slice(tree, comparator, dir);
+ }
+
+ public Object[] tree()
+ {
+ return tree;
+ }
+
+ /**
+ * The index of the item within the list, or its insertion point otherwise. i.e. binarySearch semantics
+ */
+ public int indexOf(Object item)
+ {
+ return findIndex(tree, comparator, (V) item);
+ }
+
+ /**
+ * The converse of indexOf: provided an index between 0 and size, returns the i'th item, in set order.
+ */
+ public V get(int index)
+ {
+ return BTree.<V>findByIndex(tree, index);
+ }
+
+ public int lastIndexOf(Object o)
+ {
+ return indexOf(o);
+ }
+
+ public BTreeSet<V> subList(int fromIndex, int toIndex)
+ {
+ return new BTreeRange<V>(tree, comparator, fromIndex, toIndex - 1);
+ }
+
+ @Override
+ public int size()
+ {
+ return BTree.size(tree);
+ }
+
+ @Override
+ public boolean isEmpty()
+ {
+ return BTree.isEmpty(tree);
+ }
+
+ @Override
+ public BTreeSearchIterator<V, V> iterator()
+ {
+ return slice(Dir.ASC);
+ }
+
+ @Override
+ public BTreeSearchIterator<V, V> descendingIterator()
+ {
+ return slice(Dir.DESC);
+ }
+
+ @Override
+ public Object[] toArray()
+ {
+ return toArray(new Object[0]);
+ }
+
+ @Override
+ public <T> T[] toArray(T[] a)
+ {
+ return toArray(a, 0);
+ }
+
+ public <T> T[] toArray(T[] a, int offset)
+ {
+ int size = size();
+ if (a.length < size + offset)
+ a = Arrays.copyOf(a, size);
+ BTree.toArray(tree, a, offset);
+ return a;
+ }
+
+ public Spliterator<V> spliterator()
+ {
+ return Spliterators.spliterator(this, Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.IMMUTABLE | Spliterator.NONNULL | Spliterator.SIZED);
+ }
+
+ @Override
+ public BTreeSet<V> subSet(V fromElement, boolean fromInclusive, V toElement, boolean toInclusive)
+ {
+ return new BTreeRange<>(tree, comparator, fromElement, fromInclusive, toElement, toInclusive);
+ }
+
+ @Override
+ public BTreeSet<V> headSet(V toElement, boolean inclusive)
+ {
+ return new BTreeRange<>(tree, comparator, null, true, toElement, inclusive);
+ }
+
+ @Override
+ public BTreeSet<V> tailSet(V fromElement, boolean inclusive)
+ {
+ return new BTreeRange<>(tree, comparator, fromElement, inclusive, null, true);
+ }
+
+ @Override
+ public SortedSet<V> subSet(V fromElement, V toElement)
+ {
+ return subSet(fromElement, true, toElement, false);
+ }
+
+ @Override
+ public SortedSet<V> headSet(V toElement)
+ {
+ return headSet(toElement, false);
+ }
+
+ @Override
+ public SortedSet<V> tailSet(V fromElement)
+ {
+ return tailSet(fromElement, true);
+ }
+
+ @Override
+ public BTreeSet<V> descendingSet()
+ {
+ return new BTreeRange<V>(this.tree, this.comparator).descendingSet();
+ }
+
+ @Override
+ public V first()
+ {
+ if (isEmpty())
+ throw new NoSuchElementException();
+ return get(0);
+ }
+
+ @Override
+ public V last()
+ {
+ if (isEmpty())
+ throw new NoSuchElementException();
+ return get(size() - 1);
+ }
+
+ @Override
+ public V lower(V v)
+ {
+ return BTree.lower(tree, comparator, v);
+ }
+
+ @Override
+ public V floor(V v)
+ {
+ return BTree.floor(tree, comparator, v);
+ }
+
+ @Override
+ public V ceiling(V v)
+ {
+ return BTree.ceil(tree, comparator, v);
+ }
+
+ @Override
+ public V higher(V v)
+ {
+ return BTree.higher(tree, comparator, v);
+ }
+
+ @Override
+ public boolean contains(Object o)
+ {
+ return indexOf((V) o) >= 0;
+ }
+
+ @Override
+ public boolean containsAll(Collection<?> c)
+ {
+ // TODO: if we ever use this method, it can be specialized quite easily for SortedSet arguments
+ for (Object o : c)
+ if (!contains(o))
+ return false;
+ return true;
+ }
+ public int hashCode()
+ {
+ // we can't just delegate to Arrays.deepHashCode(),
+ // because two equivalent sets may be represented by differently shaped trees
+ int result = 1;
+ for (V v : this)
+ result = 31 * result + Objects.hashCode(v);
+ return result;
+ }
+
+
+ @Override
+ public boolean addAll(Collection<? extends V> c)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ public boolean addAll(int index, Collection<? extends V> c)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean retainAll(Collection<?> c)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean removeAll(Collection<?> c)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void clear()
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public V pollFirst()
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public V pollLast()
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean add(V v)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean remove(Object o)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ public V set(int index, V element)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ public void add(int index, V element)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ public V remove(int index)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ public ListIterator<V> listIterator()
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ public ListIterator<V> listIterator(int index)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ public static class BTreeRange<V> extends BTreeSet<V>
+ {
+ // both inclusive
+ protected final int lowerBound, upperBound;
+ BTreeRange(Object[] tree, Comparator<? super V> comparator)
+ {
+ this(tree, comparator, null, true, null, true);
+ }
+
+ BTreeRange(BTreeRange<V> from)
+ {
+ super(from.tree, from.comparator);
+ this.lowerBound = from.lowerBound;
+ this.upperBound = from.upperBound;
+ }
+
+ BTreeRange(Object[] tree, Comparator<? super V> comparator, int lowerBound, int upperBound)
+ {
+ super(tree, comparator);
+ if (upperBound < lowerBound - 1)
+ upperBound = lowerBound - 1;
+ this.lowerBound = lowerBound;
+ this.upperBound = upperBound;
+ }
+
+ BTreeRange(Object[] tree, Comparator<? super V> comparator, V lowerBound, boolean inclusiveLowerBound, V upperBound, boolean inclusiveUpperBound)
+ {
+ this(tree, comparator,
+ lowerBound == null ? 0 : inclusiveLowerBound ? BTree.ceilIndex(tree, comparator, lowerBound)
+ : BTree.higherIndex(tree, comparator, lowerBound),
+ upperBound == null ? BTree.size(tree) - 1 : inclusiveUpperBound ? BTree.floorIndex(tree, comparator, upperBound)
+ : BTree.lowerIndex(tree, comparator, upperBound));
+ }
+
+ // narrowing range constructor - makes this the intersection of the two ranges over the same tree b
+ BTreeRange(BTreeRange<V> a, BTreeRange<V> b)
+ {
+ this(a.tree, a.comparator, Math.max(a.lowerBound, b.lowerBound), Math.min(a.upperBound, b.upperBound));
+ assert a.tree == b.tree;
+ }
+
+ @Override
+ protected BTreeSearchIterator<V, V> slice(Dir dir)
+ {
+ return BTree.slice(tree, comparator, lowerBound, upperBound, dir);
+ }
+
+ @Override
+ public boolean isEmpty()
+ {
+ return upperBound < lowerBound;
+ }
+
+ public int size()
+ {
+ return (upperBound - lowerBound) + 1;
+ }
+
+ boolean outOfBounds(int i)
+ {
+ return (i < lowerBound) | (i > upperBound);
+ }
+
+ public V get(int index)
+ {
+ index += lowerBound;
+ if (outOfBounds(index))
+ throw new NoSuchElementException();
+ return super.get(index);
+ }
+
+ public int indexOf(Object item)
+ {
+ int i = super.indexOf(item);
+ boolean negate = i < 0;
+ if (negate)
+ i = -1 - i;
+ if (outOfBounds(i))
+ return i < lowerBound ? -1 : -1 - size();
+ i = i - lowerBound;
+ if (negate)
+ i = -1 -i;
+ return i;
+ }
+
+ public V lower(V v)
+ {
+ return maybe(Math.min(upperBound, BTree.lowerIndex(tree, comparator, v)));
+ }
+
+ public V floor(V v)
+ {
+ return maybe(Math.min(upperBound, BTree.floorIndex(tree, comparator, v)));
+ }
+
+ public V ceiling(V v)
+ {
+ return maybe(Math.max(lowerBound, BTree.ceilIndex(tree, comparator, v)));
+ }
+
+ public V higher(V v)
+ {
+ return maybe(Math.max(lowerBound, BTree.higherIndex(tree, comparator, v)));
+ }
+
+ private V maybe(int i)
+ {
+ if (outOfBounds(i))
+ return null;
+ return super.get(i);
+ }
+
+ @Override
+ public BTreeSet<V> subSet(V fromElement, boolean fromInclusive, V toElement, boolean toInclusive)
+ {
+ return new BTreeRange<>(this, new BTreeRange<>(tree, comparator, fromElement, fromInclusive, toElement, toInclusive));
+ }
+
+ @Override
+ public BTreeSet<V> headSet(V toElement, boolean inclusive)
+ {
+ return new BTreeRange<>(this, new BTreeRange<>(tree, comparator, null, true, toElement, inclusive));
+ }
+
+ @Override
+ public BTreeSet<V> tailSet(V fromElement, boolean inclusive)
+ {
+ return new BTreeRange<>(this, new BTreeRange<>(tree, comparator, fromElement, inclusive, null, true));
+ }
+
+ @Override
+ public BTreeSet<V> descendingSet()
+ {
+ return new BTreeDescRange<>(this);
+ }
+
+ public BTreeSet<V> subList(int fromIndex, int toIndex)
+ {
+ if (fromIndex < 0 || toIndex > size())
+ throw new IndexOutOfBoundsException();
+ return new BTreeRange<V>(tree, comparator, lowerBound + fromIndex, lowerBound + toIndex - 1);
+ }
+
+ @Override
+ public <T> T[] toArray(T[] a)
+ {
+ return toArray(a, 0);
+ }
+
+ public <T> T[] toArray(T[] a, int offset)
+ {
+ if (size() + offset < a.length)
+ a = Arrays.copyOf(a, size() + offset);
+
+ BTree.toArray(tree, lowerBound, upperBound + 1, a, offset);
+ return a;
+ }
+ }
+
+ public static class BTreeDescRange<V> extends BTreeRange<V>
+ {
+ BTreeDescRange(BTreeRange<V> from)
+ {
+ super(from.tree, from.comparator, from.lowerBound, from.upperBound);
+ }
+
+ @Override
+ protected BTreeSearchIterator<V, V> slice(Dir dir)
+ {
+ return super.slice(dir.invert());
+ }
+
+ /* Flip the methods we call for inequality searches */
+
+ public V higher(V v)
+ {
+ return super.lower(v);
+ }
+
+ public V ceiling(V v)
+ {
+ return super.floor(v);
+ }
+
+ public V floor(V v)
+ {
+ return super.ceiling(v);
+ }
+
+ public V lower(V v)
+ {
+ return super.higher(v);
+ }
+
+ public V get(int index)
+ {
+ index = upperBound - index;
+ if (outOfBounds(index))
+ throw new NoSuchElementException();
+ return BTree.findByIndex(tree, index);
+ }
+
+ public int indexOf(Object item)
+ {
+ int i = super.indexOf(item);
+ // i is in range [-1 - size()..size())
+ // so we just need to invert by adding/subtracting from size
+ return i < 0 ? -2 - size() - i : size() - (i + 1);
+ }
+
+ public BTreeSet<V> subList(int fromIndex, int toIndex)
+ {
+ if (fromIndex < 0 || toIndex > size())
+ throw new IndexOutOfBoundsException();
+ return new BTreeDescRange<V>(new BTreeRange<V>(tree, comparator, upperBound - (toIndex - 1), upperBound - fromIndex));
+ }
+
+ @Override
+ public BTreeSet<V> subSet(V fromElement, boolean fromInclusive, V toElement, boolean toInclusive)
+ {
+ return super.subSet(toElement, toInclusive, fromElement, fromInclusive).descendingSet();
+ }
+
+ @Override
+ public BTreeSet<V> headSet(V toElement, boolean inclusive)
+ {
+ return super.tailSet(toElement, inclusive).descendingSet();
+ }
+
+ @Override
+ public BTreeSet<V> tailSet(V fromElement, boolean inclusive)
+ {
+ return super.headSet(fromElement, inclusive).descendingSet();
+ }
+
+ @Override
+ public BTreeSet<V> descendingSet()
+ {
+ return new BTreeRange<>(this);
+ }
+
+ public Comparator<V> comparator()
+ {
+ return (a, b) -> comparator.compare(b, a);
+ }
+
+ public <T> T[] toArray(T[] a, int offset)
+ {
+ a = super.toArray(a, offset);
+ int count = size();
+ int flip = count / 2;
+ for (int i = 0 ; i < flip ; i++)
+ {
+ int j = count - (i + 1);
+ T t = a[i + offset];
+ a[i + offset] = a[j + offset];
+ a[j + offset] = t;
+ }
+ return a;
+ }
+ }
+
+ public static class Builder<V>
+ {
+ final BTree.Builder<V> wrapped;
+
+ protected Builder(Comparator<? super V> comparator)
+ {
+ wrapped = BTree.builder(comparator);
+ }
+
+ protected Builder(Comparator<? super V> comparator, int size)
+ {
+ wrapped = BTree.builder(comparator, size);
+ }
+
+ public Builder<V> add(V v)
+ {
+ wrapped.add(v);
+ return this;
+ }
+
+ public Builder<V> addAll(Collection<V> iter)
+ {
+ wrapped.addAll(iter);
+ return this;
+ }
+
+ public boolean isEmpty()
+ {
+ return wrapped.isEmpty();
+ }
+
+ public BTreeSet<V> build()
+ {
+ return new BTreeSet<>(wrapped.build(), wrapped.comparator);
+ }
+ }
+
+ public static <V> Builder<V> builder(Comparator<? super V> comparator)
+ {
+ return new Builder<>(comparator);
+ }
+
+ /** if you know the precise size of the resultant set use {@code perfectBuilder} instead. */
+ public static <V> Builder<V> builder(Comparator<? super V> comparator, int initialCapacity)
+ {
+ return new Builder<>(comparator, initialCapacity);
+ }
+
+ public static <V> BTreeSet<V> wrap(Object[] btree, Comparator<? super V> comparator)
+ {
+ return new BTreeSet<>(btree, comparator);
+ }
+
+ public BTreeSet<V> with(Collection<V> updateWith)
+ {
+ Object[] with = BTreeSet.<V>builder(comparator).addAll(updateWith).build().tree;
+ return new BTreeSet<>(BTree.update(tree, with, comparator, UpdateFunction.<V>noOp()), comparator);
+ }
+
+ public BTreeSet<V> with(V updateWith)
+ {
+ return new BTreeSet<>(BTree.update(tree, new Object[] { updateWith }, comparator, UpdateFunction.<V>noOp()), comparator);
+ }
+
+ public BTreeSet<V> without(V element)
+ {
+ return new BTreeSet<>(BTreeRemoval.remove(tree, comparator, element), comparator);
+ }
+
+ public static <V extends Comparable<V>> BTreeSet<V> of(V value)
+ {
+ return new BTreeSet<>(BTree.singleton(value), Ordering.<V>natural());
+ }
+
+ public static <V> BTreeSet<V> empty(Comparator<? super V> comparator)
+ {
+ return new BTreeSet<>(BTree.empty(), comparator);
+ }
+
+ public static <V> BTreeSet<V> of(Comparator<? super V> comparator, V value)
+ {
+ return new BTreeSet<>(BTree.singleton(value), comparator);
+ }
+
+ public static <V> BTreeSet<V> copy(SortedSet<? extends V> copy, Comparator<? super V> comparator)
+ {
+ try (BTree.FastBuilder<V> builder = BTree.fastBuilder())
+ {
+ copy.forEach(builder::add);
+ return wrap(builder.build(), comparator);
+ }
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/BulkIterator.java b/accord-core/src/main/java/accord/utils/btree/BulkIterator.java
new file mode 100644
index 0000000..63d6200
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/BulkIterator.java
@@ -0,0 +1,110 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package accord.utils.btree;
+
+import java.util.Iterator;
+
+public interface BulkIterator<V> extends AutoCloseable
+{
+ void fetch(Object[] into, int offset, int count);
+ V next();
+ default void close() {};
+
+ public static class FromArray<V> implements BulkIterator<V>, AutoCloseable
+ {
+ private static final TinyThreadLocalPool<FromArray> POOL = new TinyThreadLocalPool<>();
+
+ private Object[] from;
+ private int i;
+ private TinyThreadLocalPool.TinyPool<FromArray> pool;
+
+ private void init(Object[] from, int offset)
+ {
+ this.from = from;
+ this.i = offset;
+ }
+
+ public void close()
+ {
+ pool.offer(this);
+ from = null;
+ pool = null;
+ }
+
+ public void fetch(Object[] into, int offset, int count)
+ {
+ System.arraycopy(from, i, into, offset, count);
+ i += count;
+ }
+
+ public V next()
+ {
+ return (V) from[i++];
+ }
+ }
+
+ public static class Adapter<V> implements BulkIterator<V>
+ {
+ final Iterator<V> adapt;
+
+ private Adapter(Iterator<V> adapt)
+ {
+ this.adapt = adapt;
+ }
+
+ public void fetch(Object[] into, int offset, int count)
+ {
+ count += offset;
+ while (offset < count && adapt.hasNext())
+ into[offset++] = adapt.next();
+ }
+
+ public boolean hasNext()
+ {
+ return adapt.hasNext();
+ }
+
+ public V next()
+ {
+ return adapt.next();
+ }
+ }
+
+ public static <V> FromArray<V> of(Object[] from)
+ {
+ return of(from, 0);
+ }
+
+ public static <V> FromArray<V> of(Object[] from, int offset)
+ {
+ TinyThreadLocalPool.TinyPool<FromArray> pool = FromArray.POOL.get();
+ FromArray<V> result = pool.poll();
+ if (result == null)
+ result = new FromArray<>();
+ result.init(from, offset);
+ result.pool = pool;
+ return result;
+ }
+
+ public static <V> Adapter<V> of(Iterator<V> from)
+ {
+ return new Adapter<>(from);
+ }
+}
+
diff --git a/accord-core/src/main/java/accord/utils/btree/FullBTreeSearchIterator.java b/accord-core/src/main/java/accord/utils/btree/FullBTreeSearchIterator.java
new file mode 100644
index 0000000..7a92813
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/FullBTreeSearchIterator.java
@@ -0,0 +1,159 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package accord.utils.btree;
+
+import java.util.Comparator;
+import java.util.NoSuchElementException;
+
+import static accord.utils.btree.BTree.size;
+
+public class FullBTreeSearchIterator<K, V> extends TreeCursor<K> implements BTreeSearchIterator<K, V>
+{
+ private final boolean forwards;
+
+ // for simplicity, we just always use the index feature of the btree to maintain our bounds within the tree,
+ // whether or not they are constrained
+ private int index;
+ private byte state;
+ private final int lowerBound, upperBound; // inclusive
+
+ private static final int MIDDLE = 0; // only "exists" as an absence of other states
+ private static final int ON_ITEM = 1; // may only co-exist with LAST (or MIDDLE, which is 0)
+ private static final int BEFORE_FIRST = 2; // may not coexist with any other state
+ private static final int LAST = 4; // may co-exist with ON_ITEM, in which case we are also at END
+ private static final int END = 5; // equal to LAST | ON_ITEM
+
+ public FullBTreeSearchIterator(Object[] btree, Comparator<? super K> comparator, BTree.Dir dir)
+ {
+ this(btree, comparator, dir, 0, size(btree)-1);
+ }
+
+ FullBTreeSearchIterator(Object[] btree, Comparator<? super K> comparator, BTree.Dir dir, int lowerBound, int upperBound)
+ {
+ super(comparator, btree);
+ this.forwards = dir == BTree.Dir.ASC;
+ this.lowerBound = lowerBound;
+ this.upperBound = upperBound;
+ rewind();
+ }
+
+ /**
+ * @return 0 if we are on the last item, 1 if we are past the last item, and -1 if we are before it
+ */
+ private int compareToLast(int idx)
+ {
+ return forwards ? idx - upperBound : lowerBound - idx;
+ }
+
+ private int compareToFirst(int idx)
+ {
+ return forwards ? idx - lowerBound : upperBound - idx;
+ }
+
+ public boolean hasNext()
+ {
+ return state != END;
+ }
+
+ public V next()
+ {
+ switch (state)
+ {
+ case ON_ITEM:
+ if (compareToLast(index = moveOne(forwards)) >= 0)
+ state = END;
+ break;
+ case BEFORE_FIRST:
+ seekTo(index = forwards ? lowerBound : upperBound);
+ state = (byte) (upperBound == lowerBound ? LAST : MIDDLE);
+ case LAST:
+ case MIDDLE:
+ state |= ON_ITEM;
+ break;
+ default:
+ throw new NoSuchElementException();
+ }
+
+ return current();
+ }
+
+ public V next(K target)
+ {
+ if (!hasNext())
+ return null;
+
+ int state = this.state;
+ boolean found = seekTo(target, forwards, (state & (ON_ITEM | BEFORE_FIRST)) != 0);
+ int index = cur.globalIndex();
+
+ V next = null;
+ if (state == BEFORE_FIRST && compareToFirst(index) < 0)
+ return null;
+
+ int compareToLast = compareToLast(index);
+ if ((compareToLast <= 0))
+ {
+ state = compareToLast < 0 ? MIDDLE : LAST;
+ if (found)
+ {
+ state |= ON_ITEM;
+ next = (V) currentValue();
+ }
+ }
+ else state = END;
+
+ this.state = (byte) state;
+ this.index = index;
+ return next;
+ }
+
+ /**
+ * Reset this Iterator to its starting position
+ */
+ public void rewind()
+ {
+ if (upperBound < lowerBound)
+ {
+ state = (byte) END;
+ }
+ else
+ {
+ // we don't move into the tree until the first request is made, so we know where to go
+ reset(forwards);
+ state = (byte) BEFORE_FIRST;
+ }
+ }
+
+ private void checkOnItem()
+ {
+ if ((state & ON_ITEM) != ON_ITEM)
+ throw new NoSuchElementException();
+ }
+
+ public V current()
+ {
+ checkOnItem();
+ return (V) currentValue();
+ }
+
+ public int indexOfCurrent()
+ {
+ checkOnItem();
+ return compareToFirst(index);
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/IndexedSearchIterator.java b/accord-core/src/main/java/accord/utils/btree/IndexedSearchIterator.java
new file mode 100644
index 0000000..962c85c
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/IndexedSearchIterator.java
@@ -0,0 +1,38 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package accord.utils.btree;
+
+public interface IndexedSearchIterator<K, V> extends SearchIterator<K, V>
+{
+ /**
+ * @return true if iterator has any elements left, false otherwise
+ */
+ public boolean hasNext();
+
+ /**
+ * @return the value just recently returned by next()
+ * @throws java.util.NoSuchElementException if next() returned null
+ */
+ public V current();
+
+ /**
+ * @return the index of the value returned by current(), and just returned by next()
+ * @throws java.util.NoSuchElementException if next() returned null
+ */
+ public int indexOfCurrent();
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/LeafBTreeSearchIterator.java b/accord-core/src/main/java/accord/utils/btree/LeafBTreeSearchIterator.java
new file mode 100644
index 0000000..44e37bb
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/LeafBTreeSearchIterator.java
@@ -0,0 +1,136 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package accord.utils.btree;
+
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.NoSuchElementException;
+
+import static accord.utils.btree.BTree.size;
+
+public class LeafBTreeSearchIterator<K, V> implements BTreeSearchIterator<K, V>
+{
+ private final boolean forwards;
+ private final K[] keys;
+ private final Comparator<? super K> comparator;
+ private int nextPos;
+ private final int lowerBound, upperBound; // inclusive
+ private boolean hasNext;
+ private boolean hasCurrent;
+
+ public LeafBTreeSearchIterator(Object[] btree, Comparator<? super K> comparator, BTree.Dir dir)
+ {
+ this(btree, comparator, dir, 0, size(btree) -1);
+ }
+
+ LeafBTreeSearchIterator(Object[] btree, Comparator<? super K> comparator, BTree.Dir dir, int lowerBound, int upperBound)
+ {
+ this.keys = (K[]) btree;
+ this.forwards = dir == BTree.Dir.ASC;
+ this.comparator = comparator;
+ this.lowerBound = lowerBound;
+ this.upperBound = upperBound;
+ rewind();
+ }
+
+ public void rewind()
+ {
+ nextPos = forwards ? lowerBound : upperBound;
+ hasNext = nextPos >= lowerBound && nextPos <= upperBound;
+ }
+
+ public V next()
+ {
+ if (!hasNext)
+ throw new NoSuchElementException();
+ final V elem = (V) keys[nextPos];
+ nextPos += forwards ? 1 : -1;
+ hasNext = nextPos >= lowerBound && nextPos <= upperBound;
+ hasCurrent = true;
+ return elem;
+ }
+
+ public boolean hasNext()
+ {
+ return hasNext;
+ }
+
+ private int searchNext(K key)
+ {
+ int lb = forwards ? nextPos : lowerBound; // inclusive
+ int ub = forwards ? upperBound : nextPos; // inclusive
+
+ return Arrays.binarySearch(keys, lb, ub + 1, key, comparator);
+ }
+
+ private void updateHasNext()
+ {
+ hasNext = nextPos >= lowerBound && nextPos <= upperBound;
+ }
+
+ public V next(K key)
+ {
+ if (!hasNext)
+ return null;
+ V result = null;
+
+ // first check the current position in case of sequential access
+ if (comparator.compare(keys[nextPos], key) == 0)
+ {
+ hasCurrent = true;
+ result = (V) keys[nextPos];
+ nextPos += forwards ? 1 : -1;
+ }
+ updateHasNext();
+
+ if (result != null || !hasNext)
+ return result;
+
+ // otherwise search against the remaining values
+ int find = searchNext(key);
+ if (find >= 0)
+ {
+ hasCurrent = true;
+ result = (V) keys[find];
+ nextPos = find + (forwards ? 1 : -1);
+ }
+ else
+ {
+ nextPos = (forwards ? -1 : -2) - find;
+ hasCurrent = false;
+ }
+ updateHasNext();
+ return result;
+ }
+
+ public V current()
+ {
+ if (!hasCurrent)
+ throw new NoSuchElementException();
+ int current = forwards ? nextPos - 1 : nextPos + 1;
+ return (V) keys[current];
+ }
+
+ public int indexOfCurrent()
+ {
+ if (!hasCurrent)
+ throw new NoSuchElementException();
+ int current = forwards ? nextPos - 1 : nextPos + 1;
+ return forwards ? current - lowerBound : upperBound - current;
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/NodeCursor.java b/accord-core/src/main/java/accord/utils/btree/NodeCursor.java
new file mode 100644
index 0000000..295bfbe
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/NodeCursor.java
@@ -0,0 +1,198 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package accord.utils.btree;
+
+import java.util.Arrays;
+import java.util.Comparator;
+
+import static accord.utils.btree.BTree.*;
+
+/**
+ * A class for searching within one node of a btree: a linear chain (stack) of these is built of tree height
+ * to form a Cursor. Some corollaries of the basic building block operations in TreeCursor (moveOne and seekTo),
+ * along with some other methods for helping implement movement between two NodeCursor
+ *
+ * The behaviour is not dissimilar to that of NodeBuilder and TreeBuilder, wherein functions that may move
+ * us to a different node pass us the node we should move to, from which we continue our operations.
+ * @param <K>
+ */
+class NodeCursor<K>
+{
+ // TODO: consider splitting forwards from backwards
+ final NodeCursor<K> parent, child;
+ final Comparator<? super K> comparator;
+
+ boolean inChild;
+ // if !inChild, this is the key position we are currently on;
+ // if inChild, this is the child position we are currently descending into
+ int position;
+ Object[] node;
+ int nodeOffset;
+
+ NodeCursor(Object[] node, NodeCursor<K> parent, Comparator<? super K> comparator)
+ {
+ this.node = node;
+ this.parent = parent;
+ this.comparator = comparator;
+ // a well formed b-tree (text book, or ours) must be balanced, so by building a stack following the left-most branch
+ // we have a stack capable of visiting any path in the tree
+ this.child = BTree.isLeaf(node) ? null : new NodeCursor<>((Object[]) node[getChildStart(node)], this, comparator);
+ }
+
+ void resetNode(Object[] node, int nodeOffset)
+ {
+ this.node = node;
+ this.nodeOffset = nodeOffset;
+ }
+
+ /**
+ * adapt child position to key position within branch, knowing it is safe to do so
+ */
+ void safeAdvanceIntoBranchFromChild(boolean forwards)
+ {
+ if (!forwards)
+ --position;
+ }
+
+ /**
+ * adapt child position to key position within branch, and return if this was successful or we're now out of bounds
+ */
+ boolean advanceIntoBranchFromChild(boolean forwards)
+ {
+ return forwards ? position < getBranchKeyEnd(node) : --position >= 0;
+ }
+
+ boolean advanceLeafNode(boolean forwards)
+ {
+ return forwards ? ++position < getLeafKeyEnd(node)
+ : --position >= 0;
+ }
+
+ /**
+ * @return the upper/lower bound of the child we are currently descended in
+ */
+ K bound(boolean upper)
+ {
+ return (K) node[position - (upper ? 0 : 1)];
+ }
+
+ /**
+ * The parent that covers a range wider than ourselves, either ascending or descending,
+ * i.e. that defines the upper or lower bound on the subtree rooted at our node
+ * @param upper
+ * @return the NodeCursor parent that can tell us the upper/lower bound of ourselves
+ */
+ NodeCursor<K> boundIterator(boolean upper)
+ {
+ NodeCursor<K> bound = this.parent;
+ while (bound != null && (upper ? bound.position >= getChildCount(bound.node) - 1
+ : bound.position <= 0))
+ bound = bound.parent;
+ return bound;
+ }
+
+ /**
+ * look for the provided key in this node, in the specified direction:
+ * forwards => ceil search; otherwise floor
+ *
+ * we require that the node's "current" key (including the relevant bound if we are a parent we have ascended into)
+ * be already excluded by the search. this is useful for the following reasons:
+ * 1: we must ensure we never go backwards, so excluding that key from our binary search prevents our
+ * descending into a child we have already visited (without any further checks)
+ * 2: we already check the bounds as we search upwards for our natural parent;
+ * 3: we want to cheaply check sequential access, so we always check the first key we're on anyway (if it can be done easily)
+ */
+ boolean seekInNode(K key, boolean forwards)
+ {
+ int position = this.position;
+ int lb, ub;
+ if (forwards)
+ {
+ lb = position + 1;
+ ub = getKeyEnd(node);
+ }
+ else
+ {
+ ub = position;
+ lb = 0;
+ }
+
+ int find = Arrays.binarySearch((K[]) node, lb, ub, key, comparator);
+ if (find >= 0)
+ {
+ // exact key match, so we're in the correct node already. return success
+ this.position = find;
+ inChild = false;
+ return true;
+ }
+
+ // if we are a branch, and we are an inequality match, the direction of travel doesn't matter
+ // so we only need to modify if we are going backwards on a leaf node, to produce floor semantics
+ int delta = isLeaf() & !forwards ? -1 : 0;
+ this.position = delta -1 -find;
+ return false;
+ }
+
+ NodeCursor<K> descendToFirstChild(boolean forwards)
+ {
+ if (isLeaf())
+ {
+ position = forwards ? 0 : getLeafKeyEnd(node) - 1;
+ return null;
+ }
+ inChild = true;
+ position = forwards ? 0 : getChildCount(node) - 1;
+ return descend();
+ }
+
+ // descend into the child at "position"
+ NodeCursor<K> descend()
+ {
+ Object[] childNode = (Object[]) node[position + getChildStart(node)];
+ int childOffset = nodeOffset + treeIndexOffsetOfChild(node, position);
+ child.resetNode(childNode, childOffset);
+ inChild = true;
+ return child;
+ }
+
+ boolean isLeaf()
+ {
+ return child == null;
+ }
+
+ int globalIndex()
+ {
+ return nodeOffset + treeIndexOfKey(node, position);
+ }
+
+ int globalLeafIndex()
+ {
+ return nodeOffset + treeIndexOfLeafKey(position);
+ }
+
+ int globalBranchIndex()
+ {
+ return nodeOffset + treeIndexOfBranchKey(node, position);
+ }
+
+ K value()
+ {
+ return (K) node[position];
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/SearchIterator.java b/accord-core/src/main/java/accord/utils/btree/SearchIterator.java
new file mode 100644
index 0000000..7640da2
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/SearchIterator.java
@@ -0,0 +1,33 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package accord.utils.btree;
+
+public interface SearchIterator<K, V>
+{
+ /**
+ * Searches "forwards" (in direction of travel) in the iterator for the required key;
+ * if this or any key greater has already been returned by the iterator, the method may
+ * choose to return null, the correct or incorrect output, or fail an assertion.
+ *
+ * it is permitted to search past the end of the iterator, i.e. {@code !hasNext() => next(?) == null}
+ *
+ * @param key to search for
+ * @return value associated with key, if present in direction of travel
+ */
+ public V next(K key);
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/TinyThreadLocalPool.java b/accord-core/src/main/java/accord/utils/btree/TinyThreadLocalPool.java
new file mode 100644
index 0000000..1e2f048
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/TinyThreadLocalPool.java
@@ -0,0 +1,83 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package accord.utils.btree;
+
+public class TinyThreadLocalPool<V> extends ThreadLocal<TinyThreadLocalPool.TinyPool<V>>
+{
+ protected TinyPool<V> initialValue()
+ {
+ return new TinyPool<>();
+ }
+
+ // a super-simple pool containing at most two items; useful because we primarily use btrees in a two-tier hierarchy
+ // so a single thread local item would be insufficient, but an arbitrary length queue too much
+ public static class TinyPool<V>
+ {
+ final Thread thread;
+ Object val1, val2, val3;
+
+ public TinyPool()
+ {
+ this.thread = Thread.currentThread();
+ }
+
+ public void offer(V value)
+ {
+ if (Thread.currentThread() == thread)
+ offerSafe(value);
+ }
+ private void offerSafe(V value)
+ {
+ if (val1 == null) val1 = value;
+ else if (val2 == null) val2 = value;
+ else if (val3 == null) val3 = value;
+ }
+ public V poll()
+ {
+ Object result;
+ if (val1 != null)
+ {
+ result = val1;
+ val1 = null;
+ }
+ else if (val2 != null)
+ {
+ result = val2;
+ val2 = null;
+ }
+ else if (val3 != null)
+ {
+ result = val3;
+ val3 = null;
+ }
+ else result = null;
+ return (V) result;
+ }
+ }
+
+ public void offer(V value)
+ {
+ get().offer(value);
+ }
+
+ public V poll()
+ {
+ return get().poll();
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/TreeCursor.java b/accord-core/src/main/java/accord/utils/btree/TreeCursor.java
new file mode 100644
index 0000000..48ed8fb
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/TreeCursor.java
@@ -0,0 +1,269 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package accord.utils.btree;
+
+import java.util.Arrays;
+import java.util.Comparator;
+
+import static accord.utils.btree.BTree.*;
+
+/**
+ * Supports two basic operations for moving around a BTree, either forwards or backwards:
+ * moveOne(), and seekTo()
+ *
+ * These two methods, along with movement to the start/end, permit us to construct any desired
+ * movement around a btree, without much cognitive burden.
+ *
+ * This TreeCursor is (and has its methods) package private. This is to avoid polluting the BTreeSearchIterator
+ * that extends it, and uses its functionality. If this class is useful for wider consumption, a public extension
+ * class can be provided, that just makes all of its methods public.
+ */
+class TreeCursor<K> extends NodeCursor<K>
+{
+ // TODO: spend some time optimising compiler inlining decisions: many of these methods have only one primary call-site
+
+ NodeCursor<K> cur;
+
+ TreeCursor(Comparator<? super K> comparator, Object[] node)
+ {
+ super(node, null, comparator);
+ }
+
+ /**
+ * Move the cursor to either the first or last item in the btree
+ * @param start true if should move to the first item; false moves to the last
+ */
+ void reset(boolean start)
+ {
+ cur = root();
+ root().inChild = false;
+ // this is a corrupt position, but we ensure we never use it except to start our search from
+ root().position = start ? -1 : getKeyEnd(root().node);
+ }
+
+ /**
+ * move the Cursor one item, either forwards or backwards
+ * @param forwards direction of travel
+ * @return false iff the cursor is exhausted in the direction of travel
+ */
+ int moveOne(boolean forwards)
+ {
+ NodeCursor<K> cur = this.cur;
+ if (cur.isLeaf())
+ {
+ // if we're a leaf, we try to step forwards inside ourselves
+ if (cur.advanceLeafNode(forwards))
+ return cur.globalLeafIndex();
+
+ // if we fail, we just find our bounding parent
+ this.cur = cur = moveOutOfLeaf(forwards, cur, root());
+ return cur.globalIndex();
+ }
+
+ // otherwise we descend directly into our next child
+ if (forwards)
+ ++cur.position;
+ cur = cur.descend();
+
+ // and go to its first item
+ NodeCursor<K> next;
+ while ( null != (next = cur.descendToFirstChild(forwards)) )
+ cur = next;
+
+ this.cur = cur;
+ return cur.globalLeafIndex();
+ }
+
+ /**
+ * seeks from the current position, forwards or backwards, for the provided key
+ * while the direction could be inferred (or ignored), it is required so that (e.g.) we do not infinitely loop on bad inputs
+ * if there is no such key, it moves to the key that would naturally follow/succeed it (i.e. it behaves as ceil when ascending; floor when descending)
+ */
+ boolean seekTo(K key, boolean forwards, boolean skipOne)
+ {
+ NodeCursor<K> cur = this.cur;
+
+ /**
+ * decide if we will "try one" value by itself, as a sequential access;
+ * we actually *require* that we try the "current key" for any node before we call seekInNode on it.
+ *
+ * if we are already on a value, we just check it irregardless of if it is a leaf or not;
+ * if we are not, we have already excluded it (as we have consumed it), so:
+ * if we are on a branch we consider that good enough;
+ * otherwise, we move onwards one, and we try the new value
+ *
+ */
+ boolean tryOne = !skipOne;
+ if ((!tryOne & cur.isLeaf()) && !(tryOne = (cur.advanceLeafNode(forwards) || (cur = moveOutOfLeaf(forwards, cur, null)) != null)))
+ {
+ // we moved out of the tree; return out-of-bounds
+ this.cur = root();
+ return false;
+ }
+
+ if (tryOne)
+ {
+ // we're presently on a value we can (and *must*) cheaply test
+ K test = cur.value();
+
+ int cmp;
+ if (key == test) cmp = 0; // check object identity first, since we utilise that in some places and it's very cheap
+ else cmp = comparator.compare(test, key); // order of provision matters for asymmetric comparators
+ if (forwards ? cmp >= 0 : cmp <= 0)
+ {
+ // we've either matched, or excluded the value from being present
+ this.cur = cur;
+ return cmp == 0;
+ }
+ }
+
+ // if we failed to match with the cheap test, first look to see if we're even in the correct sub-tree
+ while (cur != root())
+ {
+ NodeCursor<K> bound = cur.boundIterator(forwards);
+ if (bound == null)
+ break; // we're all that's left
+
+ int cmpbound = comparator.compare(bound.bound(forwards), key); // order of provision matters for asymmetric comparators
+ if (forwards ? cmpbound > 0 : cmpbound < 0)
+ break; // already in correct sub-tree
+
+ // bound is on-or-before target, so ascend to that bound and continue looking upwards
+ cur = bound;
+ cur.safeAdvanceIntoBranchFromChild(forwards);
+ if (cmpbound == 0) // it was an exact match, so terminate here
+ {
+ this.cur = cur;
+ return true;
+ }
+ }
+
+ // we must now be able to find our target in the sub-tree rooted at cur
+ boolean match;
+ while (!(match = cur.seekInNode(key, forwards)) && !cur.isLeaf())
+ {
+ cur = cur.descend();
+ cur.position = forwards ? -1 : getKeyEnd(cur.node);
+ }
+
+ if (!match)
+ cur = ensureValidLocation(forwards, cur);
+
+ this.cur = cur;
+ assert !cur.inChild;
+ return match;
+ }
+
+ /**
+ * ensures a leaf node we have seeked in, is not positioned outside of its bounds,
+ * by moving us into its parents (if any); if it is the root, we're permitted to be out-of-bounds
+ * as this indicates exhaustion
+ */
+ private NodeCursor<K> ensureValidLocation(boolean forwards, NodeCursor<K> cur)
+ {
+ assert cur.isLeaf();
+ int position = cur.position;
+ // if we're out of bounds of the leaf, move once in direction of travel
+ if ((position < 0) | (position >= getLeafKeyEnd(cur.node)))
+ cur = moveOutOfLeaf(forwards, cur, root());
+ return cur;
+ }
+
+ /**
+ * move out of a leaf node that is currently out of (its own) bounds
+ * @return null if we're now out-of-bounds of the whole tree
+ */
+ private <K> NodeCursor<K> moveOutOfLeaf(boolean forwards, NodeCursor<K> cur, NodeCursor<K> ifFail)
+ {
+ while (true)
+ {
+ cur = cur.parent;
+ if (cur == null)
+ {
+ root().inChild = false;
+ return ifFail;
+ }
+ if (cur.advanceIntoBranchFromChild(forwards))
+ break;
+ }
+ cur.inChild = false;
+ return cur;
+ }
+
+ /**
+ * resets the cursor and seeks to the specified position; does not assume locality or take advantage of the cursor's current position
+ */
+ void seekTo(int index)
+ {
+ if ((index < 0) | (index >= BTree.size(rootNode())))
+ {
+ if ((index < -1) | (index > BTree.size(rootNode())))
+ throw new IndexOutOfBoundsException(index + " not in range [0.." + BTree.size(rootNode()) + ")");
+ reset(index == -1);
+ return;
+ }
+
+ NodeCursor<K> cur = root();
+ assert cur.nodeOffset == 0;
+ while (true)
+ {
+ int relativeIndex = index - cur.nodeOffset; // index within subtree rooted at cur
+ Object[] node = cur.node;
+
+ if (cur.isLeaf())
+ {
+ assert relativeIndex < getLeafKeyEnd(node);
+ cur.position = relativeIndex;
+ this.cur = cur;
+ return;
+ }
+
+ int[] sizeMap = getSizeMap(node);
+ int boundary = Arrays.binarySearch(sizeMap, relativeIndex);
+ if (boundary >= 0)
+ {
+ // exact match, in this branch node
+ assert boundary < sizeMap.length - 1;
+ cur.position = boundary;
+ cur.inChild = false;
+ this.cur = cur;
+ return;
+ }
+
+ cur.inChild = true;
+ cur.position = -1 -boundary;
+ cur = cur.descend();
+ }
+ }
+
+ private NodeCursor<K> root()
+ {
+ return this;
+ }
+
+ Object[] rootNode()
+ {
+ return this.node;
+ }
+
+ K currentValue()
+ {
+ return cur.value();
+ }
+}
diff --git a/accord-core/src/main/java/accord/utils/btree/UpdateFunction.java b/accord-core/src/main/java/accord/utils/btree/UpdateFunction.java
new file mode 100644
index 0000000..d6fe704
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/btree/UpdateFunction.java
@@ -0,0 +1,83 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package accord.utils.btree;
+
+import java.util.function.BiFunction;
+
+/**
+ * An interface defining the method to be applied to the existing and replacing object in a BTree. The objects returned
+ * by the methods will be the object that need to be stored in the BTree.
+ */
+public interface UpdateFunction<K, V>
+{
+ /**
+ * Computes the value that should be inserted in the BTree.
+ *
+ * @param insert the update value
+ * @return the value that should be inserted in the BTree
+ */
+ V insert(K insert);
+
+ /**
+ * Computes the result of merging the existing value with the one from the update.
+ *
+ * @param replacing the value in the original tree we have matched
+ * @param update the value in the updating collection that matched
+ * @return the value to insert into the new tree
+ */
+ V merge(V replacing, K update);
+
+ final class Simple<V> implements UpdateFunction<V, V>
+ {
+ private final BiFunction<V, V, V> wrapped;
+ public Simple(BiFunction<V, V, V> wrapped)
+ {
+ this.wrapped = wrapped;
+ }
+
+ @Override
+ public V insert(V v)
+ {
+ return v;
+ }
+
+ @Override
+ public V merge(V replacing, V update)
+ {
+ return wrapped.apply(replacing, update);
+ }
+
+ public static <V> Simple<V> of(BiFunction<V, V, V> f)
+ {
+ return new Simple<>(f);
+ }
+
+ Simple<V> flip()
+ {
+ return of((a, b) -> wrapped.apply(b, a));
+ }
+ }
+
+ static final Simple<Object> noOp = Simple.of((a, b) -> a);
+
+ public static <K> UpdateFunction<K, K> noOp()
+ {
+ return (UpdateFunction<K, K>) noOp;
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org