content: /*
   * 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 org.apache.cassandra.utils.btree;
  
  import java.util.*;
  import java.util.function.BiConsumer;
  import java.util.function.BiFunction;
  import java.util.function.Consumer;
  import java.util.function.Function;
  
  import javax.annotation.Nullable;
  
  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 accord.utils.Invariants;
  import org.apache.cassandra.utils.BiLongAccumulator;
  import org.apache.cassandra.utils.BulkIterator;
  import org.apache.cassandra.utils.LongAccumulator;
  import org.apache.cassandra.utils.ObjectSizes;
  import org.apache.cassandra.utils.PeekingSearchIterator;
  import org.apache.cassandra.utils.btree.IntervalBTree.IntervalMaxIndex;
  import org.apache.cassandra.utils.caching.TinyThreadLocalPool;
  
  import static java.lang.Math.max;
  import static java.lang.Math.min;
  import static org.apache.cassandra.config.CassandraRelevantProperties.BTREE_BRANCH_SHIFT;
  import static org.apache.cassandra.utils.btree.BTree.Dir.ASC;
  
  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[&lt;V1.key], child[&lt;V2.key], ..., child[&lt; 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 = BTREE_BRANCH_SHIFT.getInt();
  
      /**
       * _DO NOT_ attempt to modify this field directly. Instead, use BRANCH_SHIFT above instead, as branch factor
       * should _always_ be a power of 2.
       */
      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;
      public static final long STOP_SENTINEL_VALUE = Long.MAX_VALUE;
  
      // 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);
      private static final long[] PERFECT_DENSE_SIZE_ON_HEAP = sizeOnHeapOfPerfectTrees(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 };
      }
  
      /** @deprecated See CASSANDRA-15510 */
      @Deprecated(since = "4.0")
      public static <C, K extends C, V extends C> Object[] build(Collection<K> source)
      {
          return build(source, UpdateFunction.noOp());
      }
  
      /** @deprecated See CASSANDRA-15510 */
      @Deprecated(since = "4.0")
      public static <C, K extends C, V extends C> Object[] build(Collection<K> source, UpdateFunction<K, V> updateF)
      {
          return build(BulkIterator.of(source.iterator()), source.size(), updateF);
      }
  
      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);
      }
  
      public static Object[] unsafeAllocateNonEmptyLeaf(int size)
      {
          Invariants.requireArgument(size > 0, "size should be non-zero");
          Invariants.requireArgument(size <= MAX_KEYS, "size (%s) should be no more than %s", size, MAX_KEYS);
          return new Object[size | 1];
      }
  
      /**
       * 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))
          {
              updateF.onAllocatedOnHeap(ObjectSizes.sizeOfReferenceArray(values.length));
              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;
          if (!isSimple(updateF))
              updateF.onAllocatedOnHeap(ObjectSizes.sizeOfArray(branch) + ObjectSizes.sizeOfArray(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);
          updateF.onAllocatedOnHeap(PERFECT_DENSE_SIZE_ON_HEAP[height]);
          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);
              updateF.onAllocatedOnHeap(sizeOnHeapOf(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);
              updateF.onAllocatedOnHeap(sizeOnHeapOf(merged) - sizeOnHeapOf(toUpdate));
              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);
  
              // TODO (expected): support IntervalMaxIndex
              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, 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, 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 = sizeMap(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 = sizeMap(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 = sizeMap(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 lookupSizeMap(Object[] branchNode, int index)
      {
          return sizeMap(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 sizeMap(tree)[(length / 2) - 1];
      }
  
      public static long sizeOfStructureOnHeap(Object[] tree)
      {
          if (tree == EMPTY_LEAF)
              return 0;
  
          long size = ObjectSizes.sizeOfArray(tree);
          if (isLeaf(tree))
              return size;
          for (int i = getChildStart(tree); i < getChildEnd(tree); i++)
              size += sizeOfStructureOnHeap((Object[]) tree[i]);
          return size;
      }
  
      /**
       * 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(sizeMap(branch)));
          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 = sizeMap(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);
      }
  
      private static boolean isStopSentinel(long v)
      {
          return v == STOP_SENTINEL_VALUE;
      }
  
      private static <V, A> long accumulateLeaf(Object[] btree, BiLongAccumulator<A, V> accumulator, A arg, Comparator<V> comparator, V from, long initialValue)
      {
          Preconditions.checkArgument(isLeaf(btree));
          long value = initialValue;
          int limit = getLeafKeyEnd(btree);
  
          int startIdx = 0;
          if (from != null)
          {
              int i = find(btree, from, comparator);
              boolean isExact = i >= 0;
              startIdx = isExact ? i : (-1 - i);
          }
  
          for (int i = startIdx; i < limit; i++)
          {
              value = accumulator.apply(arg, (V) btree[i], value);
  
              if (isStopSentinel(value))
                  break;
          }
          return value;
      }
  
      /**
       * Walk the btree and accumulate a long value using the supplied accumulator function. Iteration will stop if the
       * accumulator function returns the sentinel value {@link #STOP_SENTINEL_VALUE}
       * <p>
       * If the optional from argument is not null, iteration will start from that value (or the one after it's insertion
       * point if an exact match isn't found)
       */
      public static <V, A> long accumulate(Object[] btree, BiLongAccumulator<A, V> accumulator, A arg, Comparator<V> comparator, V from, long initialValue)
      {
          if (isLeaf(btree))
              return accumulateLeaf(btree, accumulator, arg, comparator, from, initialValue);
  
          long value = initialValue;
          int childOffset = getChildStart(btree);
  
          int startChild = 0;
          if (from != null)
          {
              int i = find(btree, from, comparator);
              boolean isExact = i >= 0;
  
              startChild = isExact ? i + 1 : -1 - i;
  
              if (isExact)
              {
                  value = accumulator.apply(arg, (V) btree[i], value);
                  if (isStopSentinel(value))
                      return value;
                  from = null;
              }
          }
  
          int limit = btree.length - 1 - childOffset;
          for (int i = startChild; i < limit; i++)
          {
              value = accumulate((Object[]) btree[childOffset + i], accumulator, arg, comparator, from, value);
  
              if (isStopSentinel(value))
                  break;
  
              if (i < childOffset)
              {
                  value = accumulator.apply(arg, (V) btree[i], value);
                  // stop if a sentinel stop value was returned
                  if (isStopSentinel(value))
                      break;
              }
  
              if (from != null)
                  from = null;
          }
          return value;
      }
  
      public static <V> long accumulate(Object[] btree, LongAccumulator<V> accumulator, Comparator<V> comparator, V from, long initialValue)
      {
          return accumulate(btree, LongAccumulator::apply, accumulator, comparator, from, initialValue);
      }
  
      public static <V> long accumulate(Object[] btree, LongAccumulator<V> accumulator, long initialValue)
      {
          return accumulate(btree, accumulator, null, null, initialValue);
      }
  
      public static <V, A> long accumulate(Object[] btree, BiLongAccumulator<A, V> accumulator, A arg, long initialValue)
      {
          return accumulate(btree, accumulator, arg, null, null, initialValue);
      }
  
      /**
       * 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);
      }
  
      /**
       * Compute the size-in-bytes of full trees of cardinality {@code branchFactor^height - 1}
       */
      private static long[] sizeOnHeapOfPerfectTrees(int branchShift)
      {
          long[] result = new long[heightAtSize2n(Integer.MAX_VALUE, branchShift)];
          int branchFactor = 1 << branchShift;
          result[0] = branchFactor - 1;
          for (int i = 1; i < result.length; ++i)
              result[i] = sizeOnHeapOfPerfectTree(i + 1, branchFactor);
          return result;
      }
  
      /**
       * Compute the size-in-bytes of a full tree of cardinality {@code branchFactor^height - 1}
       * TODO: test
       */
      private static long sizeOnHeapOfPerfectTree(int height, int branchShift)
      {
          int branchFactor = 1 << branchShift;
          long branchSize = ObjectSizes.sizeOfReferenceArray(branchFactor * 2);
          int branchCount = height == 2 ? 1 : 2 + treeSize2n(height - 2, branchShift);
          long leafSize = ObjectSizes.sizeOfReferenceArray((branchFactor - 1) | 1);
          int leafCount = 1 + treeSize2n(height - 1, branchShift);
          return (branchSize * branchCount) + (leafSize * leafCount);
      }
  
      /**
       * @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 sizeMap(branch)[(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)
      {
          Object map = branch[branch.length - 1];
          if (map.getClass() == int[].class)
              return (int[])map;
  
          return ((IntervalMaxIndex)map).sizeMap;
      }
  
      public static long sizeOnHeapOf(Object[] tree)
      {
          if (isEmpty(tree))
              return 0;
  
          long size = ObjectSizes.sizeOfArray(tree);
          if (isLeaf(tree))
              return size;
          for (int i = childOffset(tree); i < childEndOffset(tree); i++)
              size += sizeOnHeapOf((Object[]) tree[i]);
          size += ObjectSizes.sizeOfArray(sizeMap(tree)); // may overcount, since we share size maps
          return size;
      }
  
      private static long sizeOnHeapOfLeaf(Object[] tree)
      {
          if (isEmpty(tree))
              return 0;
  
          return ObjectSizes.sizeOfArray(tree);
      }
  
      // 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.
       */
      static abstract class LeafOrBranchBuilder
      {
          final int height;
          final LeafOrBranchBuilder child;
          BranchBuilder parent;
  
          @Nullable Object[] sourceNode;
  
          /**
           * 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;
          }
  
          void setSourceNode(Object[] sourceNode)
          {
              this.sourceNode = sourceNode;
          }
  
          void clearSourceNode()
          {
              this.sourceNode = null;
          }
  
          /**
           * 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}
           */
          public final boolean isEmpty()
          {
              return count == 0 && savedNextKey == null;
          }
  
          abstract void initialiseCopy(Object[] unode);
  
          /**
           * 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(BranchBuilder propagateTo);
  
          abstract void addKey(Object key);
  
          /**
           * 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(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 = allocateParent();
              if (!parent.inUse) initParent();
              return parent;
          }
  
          BranchBuilder allocateParent()
          {
              return new BranchBuilder(this);
          }
  
          void initParent()
          {
              parent.inUse = true;
          }
  
          /**
           * 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
      {
          long allocated;
  
          LeafBuilder()
          {
              super(null);
              buffer = new Object[MAX_KEYS];
          }
  
          /**
           * Add {@code nextKey} to the buffer, overflowing if necessary
           */
          @Override
          final void addKey(Object nextKey)
          {
              if (count == MAX_KEYS)
                  overflow(nextKey);
              else
                  buffer[count++] = nextKey;
          }
  
          final void setSourceNode(Object[] sourceNode)
          {
              super.setSourceNode(sourceNode);
          }
  
          final void clearSourceNode()
          {
              super.clearSourceNode();
          }
  
          /**
           * 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;
              }
          }
  
          void initialiseCopy(Object[] copy)
          {
              Invariants.require(isEmpty());
              setSourceNode(copy);
              count = sizeOfLeaf(copy);
              System.arraycopy(copy, 0, buffer, 0, count);
          }
  
          /**
           * 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);
              if (allocated >= 0)
                  allocated += ObjectSizes.sizeOfReferenceArray(newPredecessorCount | 1);
              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
              if (allocated >= 0)
                  allocated += ObjectSizes.sizeOfReferenceArray(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(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() && sourceNode != null && count == sizeOfLeaf(sourceNode) && areIdentical(buffer, 0, sourceNode, 0, count))
              {
                  // we have exactly the same contents as the original node, so reuse it
                  Invariants.require(sourceNode != null);
                  leaf = sourceNode;
                  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();
                  if (allocated >= 0 && sizeOfLeaf > 0)
                      allocated += ObjectSizes.sizeOfReferenceArray(sizeOfLeaf | 1) - (sourceNode == null ? 0 : sizeOnHeapOfLeaf(sourceNode));
              }
  
              count = 0;
              clearSourceNode();
              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;
              if (sourceNode != null
                  && count == sizeOfLeaf(sourceNode)
                  && areIdentical(buffer, 0, sourceNode, 0, count))
              {
                  newLeaf = sourceNode;
              }
              else
              {
                  newLeaf = new Object[count | 1];
                  System.arraycopy(buffer, 0, newLeaf, 0, count);
              }
              count = 0;
              clearSourceNode();
              return newLeaf;
          }
      }
  
      static class BranchBuilder extends LeafOrBranchBuilder
      {
          final LeafBuilder leaf;
          boolean hasRightChild;
  
          /**
           * 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
           */
          @Override
          final void addKey(Object key)
          {
              Invariants.require(hasRightChild);
              hasRightChild = false;
              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.
           */
          final void addChild(Object[] child, int sizeOfChild)
          {
              Invariants.require(child != null);
              Invariants.require(!hasRightChild);
              buffer[MAX_KEYS + count] = child;
              hasRightChild = true;
              recordSizeOfChild(sizeOfChild);
          }
  
          void recordSizeOfChild(int sizeOfChild)
          {
              if (sizes != null)
                  sizes[count] = sizeOfChild;
          }
  
          final void initialiseCopy(Object[] copy)
          {
              Invariants.require(isEmpty());
              setSourceNode(copy);
              count = shallowSizeOfBranch(copy);
              hasRightChild = true;
              System.arraycopy(copy, 0, buffer, 0, count);
              System.arraycopy(copy, count, buffer, MAX_KEYS, count + 1);
          }
  
          /**
           * See {@link BranchBuilder#addChild(Object[], int)}
           */
          final 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}
           */
          final void addChildAndNextKey(Object[] newChild, int newChildSize, Object nextKey)
          {
              addChild(newChild, newChildSize);
              addKey(nextKey);
          }
  
          /**
           * Invoked when we want to add a key to the leaf buffer, but it is full
           */
          final void propagateOverflow()
          {
              // propagate the leaf we have saved in leaf().savedBuffer
              if (leaf.allocated >= 0)
                  leaf.allocated += ObjectSizes.sizeOfReferenceArray(2 * (1 + MAX_KEYS));
              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)
          {
              Invariants.require(!hasRightChild);
  
              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);
              if (leaf.allocated >= 0)
                  leaf.allocated += ObjectSizes.sizeOfReferenceArray(2 * (1 + 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);
              // TODO (desired): handle/copy IntervalMaxIndex
              int[] sizeMap = sizeMap(pred);
              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(BranchBuilder propagateTo)
          {
              Invariants.require(hasRightChild);
              int sizeOfBranch;
              Object[] branch;
              if (mustRedistribute())
              {
                  branch = redistributeOverflowAndDrain();
                  sizeOfBranch = sizeOfBranch(branch);
              }
              else
              {
                  Object[] unode = sourceNode;
                  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.
                      Invariants.require(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;
              hasRightChild = false;
              clearSourceNode();
              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()
          {
              Invariants.require(hasRightChild);
              assert !hasOverflow();
              if (count == 0)
              {
                  clearSourceNode();
                  hasRightChild = false;
                  return (Object[]) buffer[MAX_KEYS];
              }
  
              Object[] branch;
              if (sourceNode != null
                  && count == shallowSizeOfBranch(sourceNode)
                  && areIdentical(buffer, 0, sourceNode, 0, count)
                  && areIdentical(buffer, MAX_KEYS, sourceNode, count, count + 1))
              {
                  branch = sourceNode;
              }
              else
              {
                  branch = new Object[2 * (count + 1)];
                  if (count == MAX_KEYS)
                  {
                      Object[] tmp = buffer;
                      buffer = branch;
                      branch = tmp;
                  }
                  else
                  {
                      System.arraycopy(buffer, 0, branch, 0, count);
                      System.arraycopy(buffer, MAX_KEYS, branch, count, count + 1);
                  }
                  setDrainSizeMap(null, -1, branch, count);
              }
  
              count = 0;
              hasRightChild = false;
              clearSourceNode();
              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)
          {
              Invariants.require(!hasRightChild);
              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)
          {
              Invariants.require(!hasRightChild);
              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]);
          }
  
          void reset()
          {
              Arrays.fill(buffer, null);
              count = 0;
              hasRightChild = false;
              inUse = false;
              clearSourceNode();
          }
      }
  
      /**
       * 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<>();
          TinyThreadLocalPool.TinyPool pool;
  
          FastBuilder()
          {
              allocated = -1;
          } // 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();
              if (pool != null)
              {
                  pool.offer(this);
                  pool = null;
              }
          }
  
          @Override
          public void reset()
          {
              Arrays.fill(leaf().buffer, null);
              leaf().count = 0;
              BranchBuilder branch = leaf().parent;
              while (branch != null && branch.inUse)
              {
                  branch.reset();
                  branch = branch.parent;
              }
          }
  
          public boolean validateEmpty()
          {
              LeafOrBranchBuilder cur = leaf();
              boolean hasOnlyNulls = true;
              while (hasOnlyNulls && cur != null)
              {
                  hasOnlyNulls = hasOnlyNulls(cur.buffer) && hasOnlyNulls(cur.savedBuffer) && cur.savedNextKey == null;
                  cur = cur.parent;
              }
              return hasOnlyNulls;
          }
  
          private static boolean hasOnlyNulls(Object[] buffer)
          {
              if (buffer == null)
                  return true;
  
              for (int i = 0 ; i < buffer.length ; ++i)
              {
                  if (buffer[i] != null)
                      return false;
              }
              return true;
          }
      }
  
      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)
              {
                  branch.count = 0;
                  branch.hasRightChild = false;
                  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;
              }
              Invariants.require(branch == null || (branch.count == 0 && !branch.hasRightChild));
          }
  
          /**
           * 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.
       */
      static class Updater<Compare, Existing extends Compare, Insert extends Compare> extends AbstractUpdater implements AutoCloseable
      {
          static final TinyThreadLocalPool<Updater> POOL = new TinyThreadLocalPool<>();
          TinyThreadLocalPool.TinyPool 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;
              this.allocated = isSimple(updateF) ? -1 : 0;
              int leafDepth = BTree.depth(update) - 1;
              LeafOrBranchBuilder builder = leaf();
              Invariants.require(builder.isEmpty());
              for (int i = 0; i < leafDepth; ++i)
              {
                  BranchBuilder branch = builder.ensureParent();
                  Invariants.require(builder.isEmpty() && !branch.hasRightChild);
                  builder = branch;
              }
  
              Insert ik = this.insert.next();
              ik = updateRecursive(ik, update, null, builder);
              assert ik == null;
              Object[] result = builder.completeBuild();
  
              if (allocated > 0)
                  updateF.onAllocatedOnHeap(allocated);
  
              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;
                      childBuilder.setSourceNode(childUNode);
                      ik = updateRecursive(ik, childUNode, nextUKey, childBuilder);
                      childBuilder.drainAndPropagate(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();
              comparator = null;
              updateF = null;
          }
      }
  
      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.
       */
      static abstract class AbstractSeekingTransformer<I, O> extends AbstractUpdater implements AutoCloseable
      {
          /**
           * An iterator over the tree we are updating
           */
          final SimpleTreeIterator update = new SimpleTreeIterator();
  
          AbstractSeekingTransformer()
          {
              allocated = -1;
              ensureParent();
              parent.inUse = false;
          }
  
          abstract O apply(I in);
  
          LeafOrBranchBuilder initRoot(Object[] root)
          {
              int height = this.update.initToRoot(root);
              LeafOrBranchBuilder level = leaf();
              Invariants.require(level.isEmpty());
              for (int d = 1; d < height; ++d)
              {
                  BranchBuilder branch = level.ensureParent();
                  Invariants.require(branch.isEmpty() && !branch.hasRightChild);
                  level = branch;
              }
              level.setSourceNode(root);
              return level;
          }
  
          // for branch nodes, can seek to usz+1 indicating we should ascend
          abstract int seekInBranch(Object[] unode, int upos, int usz);
          // transform the leaf - false means we should directly propagate the leaf to its parent
          protected abstract boolean transformLeaf(Object[] unode, int upos, int usz);
  
          /**
           * 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
           */
          Object[] apply(Object[] root)
          {
              LeafOrBranchBuilder level = initRoot(root);
              Object[] unode = update.node();
              int upos = update.position(), usz = shallowSize(unode);
  
              descend: while (true)
              {
                  // navigate to the highest level that may need transforming
                  if (level == leaf())
                  {
                      Invariants.require(level.sourceNode == unode);
                      if (transformLeaf(unode, upos, usz)) upos = usz;
                      else
                      {
                          if (!update.ascendToParent())
                              return unode;
  
                          markUsed(parent).addChild(unode, usz);
                          level.clearSourceNode();
                          level = level.parent;
                          unode = update.node();
                          upos = update.position();
                          usz = shallowSizeOfBranch(unode);
                      }
                  }
                  else
                  {
                      BranchBuilder branch = (BranchBuilder) level;
                      int pos = seekInBranch(unode, upos, usz);
                      if (pos < 0)
                      {
                          pos = -1 -pos;
                          boolean done = pos > usz;
                          if (done)
                              pos = usz;
  
                          if (pos > upos)
                          {
                              branch.copyPreceding(unode, usz, upos, pos - upos);
                              upos = pos;
                          }
  
                          update.descend(unode, upos, usz);
                          unode = update.node();
                          upos = update.position();
                          usz = shallowSize(unode);
                          level = level.child;
                          level.setSourceNode(unode);
                          continue;
                      }
                      else
                      {
                          if (pos > upos)
                          {
                              branch.copyPreceding(unode, usz, upos, pos - upos);
                              upos = pos;
                          }
                      }
                      Invariants.require(branch.child.isEmpty());
                      branch.addChild((Object[]) unode[usz + upos]);
                  }
  
                  LeafOrBranchBuilder incomplete = level;
                  while (upos >= usz)
                  {
                      if (!update.ascendToParent())
                          return finishAndDrain(level);
  
                      unode = update.node();
                      upos = update.position();
                      usz = shallowSizeOfBranch(unode);
  
                      if (incomplete == level && finish(level))
                          incomplete = level.parent;
                      level = level.parent;
                  }
  
                  O next = apply((I) unode[upos++]);
                  if (next == null)
                  {
                      // next has been filtered, so look for the (unfiltered) successor node
                      successor: while (true)
                      {
                          level = descend(level, leaf(), unode, upos, usz);
                          unode = update.node();
                          upos = update.position();
                          usz = sizeOfLeaf(unode);
  
                          while (upos < usz)
                          {
                              if (null != (next = apply((I)unode[upos++])))
                                  break successor;
                          }
  
                          do
                          {
                              if (!update.ascendToParent())
                                  return finishAndDrain(level);
  
                              unode = update.node();
                              upos = update.position();
                              usz = shallowSizeOfBranch(unode);
                              level = level.parent;
                          } while (upos >= usz);
  
                          next = apply((I) unode[upos++]);
                          if (next != null)
                              break;
                      }
                  }
  
                  incomplete.addKey(next);
                  if (level.height > incomplete.height)
                  {
                      level = descend(level, incomplete, unode, upos, usz);
                      unode = update.node();
                      upos = update.position();
                      usz = shallowSize(unode);
                  }
              }
          }
  
          LeafOrBranchBuilder descend(LeafOrBranchBuilder from, LeafOrBranchBuilder to, Object[] unode, int upos, int usz)
          {
              while (update.height() > to.height)
              {
                  update.descend(unode, upos, usz);
                  unode = update.node();
                  upos = update.position();
                  usz = shallowSize(unode);
                  from = from.child;
                  from.setSourceNode(unode);
              }
              return to;
          }
  
          /**
           * 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.
           */
          final boolean finish(LeafOrBranchBuilder level)
          {
              if (!level.isSufficient())
                  return false;
  
              level.drainAndPropagate(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.
           */
          final Object[] finishAndDrain(LeafOrBranchBuilder root)
          {
              if (root == leaf())
                  return root.completeBuild();
  
              BranchBuilder branch = (BranchBuilder) root;
              // the logic after this loop expects that all builders are populated and have the same number of keys as children
              // so this loop simply checks to see if we can build without any rebalancing,
              // stopping at the first balanced (hasRightChild) and sufficient for building branch.
              // Otherwise it un
              while (true)
              {
                  if (branch.hasRightChild)
                  {
                      for (LeafOrBranchBuilder child = branch.child ; child != null ; child = child.child)
                          Invariants.require(child.isEmpty());
  
                      boolean isSufficient = true;
                      for (BranchBuilder b = branch ; b != root && isSufficient ; b = b.parent)
                          isSufficient = b.isSufficient();
  
                      if (isSufficient)
                      {
                          for (BranchBuilder b = branch ; b != root ; b = b.parent)
                              b.drainAndPropagate(b.parent);
                          return root.completeBuild();
                      }
                      else
                      {
                          while (true)
                          {
                              Object[] rightChild = (Object[]) branch.buffer[MAX_KEYS + branch.count];
                              branch.hasRightChild = false;
                              branch.child.initialiseCopy(rightChild);
  
                              if (branch.child == leaf())
                                  break;
                              branch = (BranchBuilder) branch.child;
                          }
                      }
                      break;
                  }
  
                  if (branch.child == leaf())
                      break;
  
                  branch = (BranchBuilder) branch.child;
              }
  
              LeafOrBranchBuilder level = leaf();
              while (true)
              {
                  BranchBuilder parent = nonEmptyParentMaybeSteal(level);
                  if (parent != null && !level.isSufficient())
                  {
                      Object[] result = stealAndMaybeRepropagate(level, parent);
                      if (result != null)
                          return result;
                  }
                  else
                  {
                      Object[] result = level.drainAndPropagate(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 logically 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(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()
          {
              super.reset();
              update.reset();
          }
      }
  
      /**
       * Implement set subtraction/difference using a modified version of the Transformer logic
       *
       * TODO (desired): merge with Transformer
       */
      static abstract class AbstractSubtraction<K, T extends K> extends AbstractSeekingTransformer<T, T> implements AutoCloseable
      {
          /**
           * An iterator over the tree we are updating
           */
          PeekingSearchIterator<K, ? extends K> remove;
          Comparator<K> comparator;
  
          Object[] subtract(Object[] update, PeekingSearchIterator<K, ? extends K> remove)
          {
              this.remove = remove;
              return apply(update);
          }
  
          Object[] subtract(Object[] update, Object[] remove)
          {
              return subtract(update, slice(remove, comparator, ASC));
          }
  
          @Override
          T apply(T v)
          {
              return remove.next(v) == null ? v : null;
          }
  
          @Override
          int seekInBranch(Object[] unode, int upos, int usz)
          {
              if (!remove.hasNext())
                  return -1 - (1 + usz);
  
              K next = remove.peek();
              int i = exponentialSearch(comparator, unode, upos, usz, next);
              if (i == -1 - usz)
              {
                  // if we sort after the last key in the branch, we may need to descend into the right-most child
                  // but, for all branches besides the root we can try to look at a parent node to decide this.
                  // we only look at the direct parent, and if we are its right-most child already, we just assume we must descend
                  int pdepth = update.depth - 1;
                  if (pdepth >= 0)
                  {
                      Object[] pnode = update.nodes[pdepth];
                      int ppos = update.positions[pdepth];
                      if (ppos < shallowSizeOfBranch(pnode) && comparator.compare(next, (K)pnode[ppos]) >= 0)
                      {
                          // increase our result index to point to *after* the last child;
                          // (it's an inequality binary search semantic answer, so will be negated)
                          --i;
                      }
                  }
              }
              return i;
          }
  
          @Override
          protected boolean transformLeaf(Object[] unode, int upos, int usz)
          {
              int prev = upos;
              if (remove.hasNext())
              {
                  while (true)
                  {
                      // fast path - buffer is empty and input unconsumed, so may be able to propagate original
                      upos = exponentialSearch(comparator, unode, upos, usz, remove.peek());
                      if (upos < 0)
                      {
                          upos = -1 - upos;
                          if (upos == usz)
                              break;
                          remove.next();
                          if (remove.hasNext()) continue;
                          else break;
                      }
  
                      leaf().copy(unode, prev, upos - prev);
                      ++upos;
                      prev = upos;
                      remove.next();
                      if (!remove.hasNext())
                          break;
                  }
              }
  
              if (prev == 0 && leaf().isEmpty())
                  // if input is unmodified by transformation, propagate the input node
                  return false;
  
              leaf().copy(unode, prev, usz - prev);
              return true;
          }
  
          @Override
          public void close()
          {
              reset();
          }
  
          @Override
          void reset()
          {
              super.reset();
              remove = null;
              comparator = null;
          }
      }
  
      private static abstract class AbstractTransformer<I, O> extends AbstractSeekingTransformer<I, O>
      {
          @Override
          final int seekInBranch(Object[] unode, int upos, int usz)
          {
              return -1 - upos;
          }
  
          protected final boolean transformLeaf(Object[] unode, int upos, int usz)
          {
              if (leaf().count == 0)
              {
                  while (upos < usz)
                  {
                      O v = apply((I) unode[upos++]);
                      leaf().maybeAddKeyNoOverflow(v);
                  }
              }
              else
              {
                  while (upos < usz)
                  {
                      O v = apply((I) unode[upos++]);
                      leaf().maybeAddKey(v);
                  }
              }
              return true;
          }
      }
  
      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 initToLeaf(Object[] tree)
          {
              init(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;
          }
  
          int initToRoot(Object[] tree)
          {
              init(tree);
              positions[0] = 0;
              leafDepth = depth = 0;
              while (!isLeaf(tree))
              {
                  tree = (Object[]) tree[shallowSizeOfBranch(tree)];
                  ++leafDepth;
              }
              return leafDepth + 1;
          }
  
          int height()
          {
              return 1 + leafDepth - 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][];
              }
              nodes[0] = tree;
          }
  
          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;
              }
          }
  
          // return true iff entered leaf depth
          boolean descend(Object[] node, int pos, int sz)
          {
              positions[depth] = pos;
              ++depth;
              nodes[depth] = (Object[]) node[sz + pos];
              positions[depth] = 0;
              return depth == leafDepth;
          }
  
          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);
              }
          }
      }
  }
  