B-Tree with better performance

/* An implementation of B-Tree. It has tree methods add, remove, findGE,
 * findLT, iteratorGE, @@iterator, size, clear, and toString. Ported from
 * Open Data Structures by Pat Morin. Includes a short demonstration of
 * those methods.
 * This script includes the performance improvements described in Morin
 * Exercise 14..7. Search for ##perf## to skip to the relevant additions
 * and modifications.
 */

/** A list of blocks used to simulate external memory storage. credit: Morin BlockStore.java. */
class BlockStore {
  constructor() {
    this.blocks = new Array();  // array of BTNode's
    this.free = new Array();    // array of indexes of available blocks
  }

  /** placeBlock() Allocate a new block and return its index.
   * @param {BTNode} block the new block
   * @returns {number} the index of the newly allocated block
   */
  placeBlock(block) {
    var ndx;
    if (this.free.length > 0) { ndx = this.free.pop(); }
    else { ndx = this.blocks.length; }
    this.blocks[ndx] = block;
    return ndx;
  }

  /** freeBlock() Free a block, adding its index to the free list.
   * @param {number} ndx the block index to free
   */
  freeBlock(ndx) {
    this.blocks[ndx] = undefined;
    this.free.push(ndx);
  }

  /** readBlock() Read a block.
   * @param {number} ndx the index of the block to read
   * @returns {BTNode} the block
   */
  readBlock(ndx) {
    return this.blocks[ndx];
  }

  /** writeBlock() Write a block.
   * @param {number} ndx the index of the block
   * @param {BTNode} block the block
   */
  writeBlock(ndx, block) {
    this.blocks[ndx] = block;
  }

  clear() {
    this.blocks.length = 0;
    this.free.length = 0;
  }
}

/** Properties of a BTree. */
class BTProps {
  bkSz;     // block size
  hfBS;     // half of block size
  bkSr;     // block store
  rootNdx;  // index of the root node
  numEl;    // number of elements stored in the tree
  compare;  // comparator function
}

/** findIt() Find the index at which a value should be inserted into an
 *  undefined-padded sorted array. credit: Morin BTree.java.
 * @param {Array} array the sorted array (padded with undefined entries)
 * @param {any} value the value to search for
 * @param {function} comparator function taking (any, any) and returning -1, 0, or 1
 * @returns index or (-index - 1) if array[index] equals value
 */
function findIt(array, value, comparator) {
  var lo = 0, hi = array.length;
  while (hi != lo) {
    var mid = Math.floor((hi + lo) / 2);
    var cmp;
    if (array[mid] == undefined) { cmp = -1; }
    else { cmp = comparator(value, array[mid]); }
    if (cmp < 0) {
      hi = mid;      // look in first half
    } else if (cmp > 0) {
      lo = mid + 1;    // look in second half
    } else {
      return -mid - 1; // found it
    }
  }
  return lo;
}

/** A node in a BTree, or a block in a BlockStore. Has an array of up to bkSz
 *  keys and up to (bkSz + 1) children. credit: Morin BTree.java Node.
 */
class BTNode {
  index;    // this block's index
  keys;     // array of any
  children; // array of indexes of the children of this block (if any)
  bp;   // BTProps
  /** constructor()
   * @param {BTProps} bp properties of the BTree
   */
  constructor(bp) {
    this.bp = bp;
    this.keys = new Array(this.bp.bkSz);
    this.children = new Array(this.bp.bkSz + 1);
    this.children.fill(-1);
    this.index = bp.bkSr.placeBlock(this);
  }

  /** isLeaf()
   * @returns {boolean}
   */
  isLeaf() {
    return this.children[0] < 0;
  }

  /** isFull() Test if this block is full (contains bkSz keys).
   * @returns {boolean} true if the block is full
   */
  isFull() {
    return this.keys[this.keys.length - 1] != undefined;
  }

  /** size() Count the number of keys in this block, using binary search.
   * @returns {number} the number of keys in this block
   */
  size() {
    var lo = 0, hi = this.keys.length;
    while (hi != lo) {
      var mid = Math.floor((hi + lo) / 2);
      if (this.keys[mid] == undefined) { hi = mid; }
      else { lo = mid + 1; }
    }
    return lo;
  }

  /** add() Add a value to this block.
   * @param {any} value the value to add
   * @param {number} cIndex the index of the child associated with value
   * @param {boolean} cFlag true if cIndex of this key, false if cIndex of next key ##perf##
   * @returns {boolean} true on success or false if value was not added
   */
  add(value, cIndex, cFlag) {
    var i = findIt(this.keys, value, this.bp.compare);
    if (i < 0) { return false; }
    if (i < this.keys.length - 1) {
      this.keys = this.keys.copyWithin(i + 1, i, this.bp.bkSz - 1);
    }
    this.keys[i] = value;
    if (i < this.keys.length - 1) {
      if (cFlag) {
        this.children = this.children.copyWithin(i + 1, i, this.bp.bkSz);
      } else {
        this.children = this.children.copyWithin(i + 2, i + 1, this.bp.bkSz);
      }
    }
    if (cFlag) { this.children[i] = cIndex; }
    else { this.children[i + 1] = cIndex; }
    return true;
  }

  /** remove() Remove value at given index from this block. Does not affect
   *  this block's children.
   * @param {number} index the index of the element to remove
   * @returns {any} the value of the element removed
   */
  remove(index) {
    var value = this.keys[index];
    this.keys = this.keys.copyWithin(index, index + 1, this.keys.length);
    this.keys[this.keys.length - 1] = undefined;
    return value;
  }

  /** split() Split this node into two nodes.
   * @returns {BTNode} the newly created block, which has the larger keys
   */
  split() {
    var block = new BTNode(this.bp);
    var mid = this.bp.hfBS;
    var larger = this.keys.slice(mid);
    block.keys.splice(0, larger.length, ...larger);
    this.keys.fill(undefined, mid);
    larger = this.children.slice(mid + 1);
    block.children.splice(0, larger.length, ...larger);
    this.children.fill(-1, mid + 1);
    this.bp.bkSr.writeBlock(this.index, this);
    return block;
  }

  /** toString()
   * @returns {string} this node as a string
   */
  toString() {
    var str = "[" + this.index + "][";
    for (var i = 0; i < this.bp.bkSz; i++) {
      str += "(";
      if (this.children[i] < 0) { str += "."; }
      else { str += this.children[i]; }
      str += ")";
      if (this.keys[i] == undefined) { str += "_"; }
      else { str += this.keys[i]; }
    }
    str += "(";
    if (this.children[this.bp.bkSz] < 0) { str += "."; }
    else { str += this.children[this.bp.bkSz]; }
    str += ")]";
    return str;
  }
}

/** Iterator of BTree. credit: Morin BTree.java. */
class BTIterator {
  #nodeSk;   // stack of BTNode's
  #indexSk;  // stack of indexes
  bp;   // BTProps
  /** #iterator() Iterator will contain all elements. */
  #iterator() {
    var cur = this.bp.rootNdx;
    do {
      var block = this.bp.bkSr.readBlock(cur);
      this.#nodeSk.push(block);
      this.#indexSk.push(0);
      cur = block.children[0];
    } while (cur >= 0);
  }

  #advance() {
    var block = this.#nodeSk[this.#nodeSk.length - 1];
    var i = this.#indexSk[this.#indexSk.length - 1];
    if (block.isLeaf()) { // this is a leaf, walk up
      while (this.#nodeSk.length > 0 && i == block.size()) {
        this.#nodeSk.pop();
        this.#indexSk.pop();
        if (this.#nodeSk.length > 0) {
          block = this.#nodeSk[this.#nodeSk.length - 1];
          i = this.#indexSk[this.#indexSk.length - 1];
        }
      }
    } else { // this is an internal node, walk down
      var cur = block.children[i];
      do {
        block = this.bp.bkSr.readBlock(cur);
        this.#nodeSk.push(block);
        this.#indexSk.push(0);
        cur = block.children[0];
      } while (cur >= 0);
    }
  }

  /** constructor() Create an iterator starting with the smallest element in the
   *  tree that is greater than or equal to value. If value is undefined, create
   *  an iterator starting with the smallest element in the tree.
   * @param {BTProps} bp properties of the BTree
   * @param {any} value the value
   */
  constructor(bp, value) {
    this.#nodeSk = new Array();
    this.#indexSk = new Array();
    this.bp = bp;

    if (this.bp.numEl == 0) { return; }
    if (value == undefined) {
      this.#iterator();
    } else {
      var block, i, cur = this.bp.rootNdx;
      do {
        block = this.bp.bkSr.readBlock(cur);
        i = findIt(block.keys, value, this.bp.compare);
        this.#nodeSk.push(block);
        if (i < 0) {  // found the value, add its index and stop
          this.#indexSk.push(-(i + 1));
          return;
        }
        this.#indexSk.push(i);  // add index of smallest value
        cur = block.children[i];
      } while (cur >= 0);
      if (i == block.size()) { this.#advance(); }
    }
  }

  /** hasNext()
   * @returns {boolean}
   */
  hasNext() {
    return this.#nodeSk.length > 0;
  }

  /** next()
   * @returns {any}
   */
  next() {
    var block = this.#nodeSk[this.#nodeSk.length - 1];
    var i = this.#indexSk[this.#indexSk.length - 1];
    var value = block.keys[i++];
    this.#indexSk[this.#indexSk.length - 1] = i;
    this.#advance();
    return value;
  }
}

/** A simple string buffer. */
class StringBuffer {
  str = "";
}

/** A sorted set. credit: Morin SSet.java, BTree.java. */
class BTree {
  /** constructor()
   * @param {number} blockSize maximum number of keys of a node
   * @param {function} comparator function taking (any, any) and returning -1, 0, or 1
   */
  constructor(blockSize, comparator) {
    this.bp = new BTProps();
    blockSize += 1 - (blockSize % 2); // an odd number
    this.bp.bkSz = blockSize;
    this.bp.hfBS = Math.floor(blockSize / 2);
    this.bp.bkSr = new BlockStore();
    this.bp.numEl = 0;
    this.bp.rootNdx = (new BTNode(this.bp)).index;
    this.bp.compare = comparator;
  }

  /** #redist() A new node will be created and nodes H and J will be redistributed. ##perf##
   * @param {BTNode} block the parent of H and J
   * @param {number} h the index h in block.children
   * @param {BTNode} bkH the left sibling of J
   * @param {BTNode} bkJ the right sibling of H
   * @param {number} sizeJ size of node J
   */
  #redist(block, h, bkH, bkJ, sizeJ) {
    var bkI = new BTNode(this.bp);
    var sizeH = bkH.size(), sizeI = 0;
    var numH = sizeH, numJ = sizeJ, shift;
    // calculate the numbers of keys to shift out of H and out of J
    if (numH > numJ) {  // H to I
      shift = Math.floor(numH / 2);
      numH -= shift;
      if (shift - numJ > 1) { // I to J
        numJ += Math.floor((numJ + shift) / 2) - numJ;
      } else if (numJ - shift > 1) {  // J to I
        numJ -= Math.floor((shift + numJ) / 2) - shift;
      }
    } else {  // J to I
      shift = Math.floor(numJ / 2);
      numJ -= shift;
      if (shift - numH > 1) {  // I to H
        numH += Math.floor((numH + shift) / 2) - numH;
      } else if (numH - shift > 1) { // H to I
        numH -= Math.floor((shift + numH) / 2) - shift;
      }
    }
    var sftH = sizeH - numH, sftJ = sizeJ - numJ;
    if (sftH > 0) {
      // move keys and children out of H and into I (and parent)
      bkI.keys[sftH - 1] = block.keys[h];
      block.keys[h] = bkH.keys[sizeH - sftH];
      var larger = bkH.keys.slice(sizeH - sftH + 1, sizeH);
      bkI.keys.splice(0, larger.length, ...larger);
      bkH.keys.fill(undefined, sizeH - sftH, sizeH);
      larger = bkH.children.slice(sizeH - sftH + 1, sizeH + 1);
      bkI.children.splice(0, larger.length, ...larger);
      bkH.children.fill(-1, sizeH - sftH + 1, sizeH + 1);
      // update size I
      sizeI += sftH;
    }
    if (sftJ > 0) {
      // shift keys and children from J to I
      var smaller = bkJ.keys.slice(0, sftJ - 1);
      bkI.keys.splice(sizeI, smaller.length, ...smaller);
      smaller = bkJ.children.slice(0, sftJ);
      bkI.children.splice(sizeI, smaller.length, ...smaller);
      var value = bkJ.keys[sftJ - 1];
      // delete keys and children from J
      bkJ.keys = bkJ.keys.copyWithin(0, sftJ, this.bp.bkSz);
      bkJ.keys.fill(undefined, sizeJ - sftJ, this.bp.bkSz);
      bkJ.children = bkJ.children.copyWithin(0, sftJ, this.bp.bkSz + 1);
      bkJ.children.fill(-1, sizeJ - sftJ + 1, this.bp.bkSz + 1);
      // add node I to parent
      block.add(value, bkI.index, true);
    } else {
      // add node I to parent
      block.add(bkI.remove(sizeI - 1), bkI.index, true);
    }
    this.bp.bkSr.writeBlock(bkI.index, bkI);
  }

  /** #addRecursive() Use recursion to add a value to the i'th child of block,
   *  or recursively add a value to root if block is undefined. ##perf##
   *  If that node is split by this operation then the return value is the
   *  BTNode that was created when node was split.
   * @param {any} value the element to add
   * @param {BTNode} block the parent of node I, or undefined to start at root
   * @param {number} i the index i in block.children
   * @returns {BTNode} a new node that was created when node was split, or
   *            undefined if node was not split
   */
  #addRecursive(value, block, i) {
    var bkI;  // BTNode
    if (block == undefined) { // root
      bkI = this.bp.bkSr.readBlock(this.bp.rootNdx);
    } else {  // non-root
      bkI = this.bp.bkSr.readBlock(block.children[i]);
    }
    var k = findIt(bkI.keys, value, this.bp.compare);
    if (k < 0) { throw new Error("duplicate value"); }
    if (bkI.children[k] < 0) { // leaf node, just add it
      bkI.add(value, -1, false);
      this.bp.bkSr.writeBlock(bkI.index, bkI);
    } else {
      var newBk = this.#addRecursive(value, bkI, k);
      if (newBk != undefined) {  // child was split, newBk is new child
        value = newBk.remove(0);
        this.bp.bkSr.writeBlock(newBk.index, newBk);
        bkI.add(value, newBk.index, false);
        this.bp.bkSr.writeBlock(bkI.index, bkI);
      }
    }
    if (bkI.isFull() && block != undefined) { // overfull non-root node
      if (block.children[i + 1] >= 0) {  // look right
        var bkJ = this.bp.bkSr.readBlock(block.children[i + 1]);
        var sizeJ = bkJ.size();
        if (sizeJ <= this.bp.hfBS + 1) {  // J can borrow from I
          this.#shiftLtoR(block, i, bkI, bkJ);
        } else if (block.size() < this.bp.bkSz - 1) {  // redist. with new node
          this.#redist(block, i, bkI, bkJ, sizeJ);
        } else {
          return bkI.split();
        }
      } else {
        return bkI.split();
      }
    } else if (bkI.isFull()) {  // overfull root node
      return bkI.split();
    }
    return undefined;
  }

  /** add() Add a value to this tree.
   * @param {any} value the element to add
   * @returns {boolean} true if value was added, or false if value was already
   *            in the set or value is undefined
   */
  add(value) {
    if (value == undefined) {
      console.error("BTree.add() undefined value");
      return false;
    }
    var block;  // BTNode
    try {
      block = this.#addRecursive(value, undefined, -1); // ##perf##
    } catch (err) {
      console.error("BTree.add() " + err.message);
      return false;
    }
    if (block != undefined) {   // root was split, make new root
      var newRoot = new BTNode(this.bp);
      value = block.remove(0);
      this.bp.bkSr.writeBlock(block.index, block);
      newRoot.children[0] = this.bp.rootNdx;
      newRoot.keys[0] = value;
      newRoot.children[1] = block.index;
      this.bp.rootNdx = newRoot.index;
      this.bp.bkSr.writeBlock(this.bp.rootNdx, newRoot);
    }
    this.bp.numEl++;
    return true;
  }

  /** #merge() Node H will absorb node I.
   * @param {BTNode} block the parent of H and I
   * @param {number} h the index h in block.children
   * @param {BTNode} bkH the left sibling of I
   * @param {BTNode} bkI the right sibling of H
   */
  #merge(block, h, bkH, bkI) {
    if (bkH.index != block.children[h]) { throw new Error("assert: H mismatch"); }
    if (bkI.index != block.children[h + 1]) { throw new Error("assert: I mismatch"); }
    var sizeI = bkI.size();
    var sizeH = bkH.size();
    // copy keys from I to H
    var smaller = bkI.keys.slice(0, sizeI);
    bkH.keys.splice(sizeH + 1, smaller.length, ...smaller);
    smaller = bkI.children.slice(0, sizeI + 1);
    bkH.children.splice(sizeH + 1, smaller.length, ...smaller);
    // add key to H and remove it from block
    bkH.keys[sizeH] = block.keys[h];
    block.keys = block.keys.copyWithin(h, h + 1, this.bp.bkSz);
    block.keys[this.bp.bkSz - 1] = undefined;
    block.children = block.children.copyWithin(h + 1, h + 2, this.bp.bkSz + 1);
    block.children[this.bp.bkSz] = -1;
    this.bp.bkSr.freeBlock(bkI.index);
  }

  /** #redist2() Nodes H, I and J will be redistributed. ##perf##
   * @param {BTNode} block the parent of H, I and J
   * @param {number} i the index i in block.children
   * @param {BTNode} bkH the left sibling of I
   * @param {BTNode} bkI the right sibling of H and left sibling of J
   * @param {BTNode} bkJ the right sibling of I
   * @param {number} sizeH size of node H
   * @param {number} sizeJ size of node J
   */
  #redist2(block, i, bkH, bkI, bkJ, sizeH, sizeJ) {
    if (sizeH > sizeJ) {  // H to I
      this.#shiftLtoR(block, i - 1, bkH, bkI);
      var sizeI = bkI.size();
      if (sizeI - sizeJ > 1) { // I to J
        this.#shiftLtoR(block, i, bkI, bkJ);
      } else if (sizeJ - sizeI > 1) {  // J to I
        this.#shiftRtoL(block, i, bkJ, bkI);
      }
    } else {  // J to I
      this.#shiftRtoL(block, i, bkJ, bkI);
      var sizeI = bkI.size();
      if (sizeI - sizeH > 1) {  // I to H
        this.#shiftRtoL(block, i - 1, bkI, bkH);
      } else if (sizeH - sizeI > 1) { // H to I
        this.#shiftLtoR(block, i - 1, bkH, bkI);
      }
    }
  }

  /** #merge2() Nodes H and/or J will absorb node I. ##perf##
   * @param {BTNode} block the parent of H, I and J
   * @param {number} i the index i in block.children
   * @param {BTNode} bkH the left sibling of I
   * @param {BTNode} bkI the right sibling of H and left sibling of J
   * @param {BTNode} bkJ the right sibling of I
   * @param {number} sizeH size of node H
   * @param {number} sizeI size of node I
   * @param {number} sizeJ size of node J
   */
  #merge2(block, i, bkH, bkI, bkJ, sizeH, sizeI, sizeJ) {
    var numH = sizeH, numI = sizeI + 1, numJ = sizeJ;
    // calculate the numbers of keys to shift to H and to J
    var shift = Math.abs(numH - numJ);
    if (shift > 0) {
      if (shift > numI) { shift = numI; }
      if (numH < numJ) { numH += shift; }
      else { numJ += shift; }
      numI -= shift;
    }
    if (numI > 0) {
      shift = Math.floor(numI / 2);
      numH += shift;
      numJ += shift;
      if (numI % 2 == 1) {
        if (numH < numJ) { numH++; }
        else { numJ++; }
      }
    }
    var sftH = numH - sizeH, sftJ = numJ - sizeJ;
    if (sftJ > 0) {
      // make space for new keys in J
      bkJ.keys = bkJ.keys.copyWithin(sftJ, 0, sizeJ);
      bkJ.children = bkJ.children.copyWithin(sftJ, 0, sizeJ + 1);
      // move keys and children out of I and into J (and parent)
      bkJ.keys[sftJ - 1] = block.keys[i];
      block.keys[i] = bkI.keys[sizeI - sftJ];
      var larger = bkI.keys.slice(sizeI - sftJ + 1, sizeI);
      bkJ.keys.splice(0, larger.length, ...larger);
      bkI.keys.fill(undefined, sizeI - sftJ, sizeI);
      larger = bkI.children.slice(sizeI - sftJ + 1, sizeI + 1);
      bkJ.children.splice(0, larger.length, ...larger);
      bkI.children.fill(-1, sizeI - sftJ + 1, sizeI + 1);
      if (sftH > 0) {  // H will absorb I
        this.#merge(block, i - 1, bkH, bkI);
      } else {  // remove node I from block
        block.keys = block.keys.copyWithin(i, i + 1, this.bp.bkSz);
        block.keys[this.bp.bkSz - 1] = undefined;
        block.children = block.children.copyWithin(i + 1, i + 2, this.bp.bkSz + 1);
        block.children[this.bp.bkSz] = -1;
        this.bp.bkSr.freeBlock(bkI.index);
      }
    } else {  // H will absorb I
      this.#merge(block, i - 1, bkH, bkI);
    }
  }

  /** #shiftRtoL() Shift keys from node J into node I.
   * @param {BTNode} block the parent of J and I
   * @param {number} i the index i in block.children
   * @param {BTNode} bkJ the right sibling of I
   * @param {BTNode} bkI the left sibling of J
   */
  #shiftRtoL(block, i, bkJ, bkI) {
    var sizeI = bkI.size();
    var sizeJ = bkJ.size();
    var shift = Math.floor((sizeI + sizeJ) / 2) - sizeI;  // num. keys to shift from J to I
    // shift keys and children from J to I
    bkI.keys[sizeI] = block.keys[i];
    var smaller = bkJ.keys.slice(0, shift - 1);
    bkI.keys.splice(sizeI + 1, smaller.length, ...smaller);
    smaller = bkJ.children.slice(0, shift);
    bkI.children.splice(sizeI + 1, smaller.length, ...smaller);
    block.keys[i] = bkJ.keys[shift - 1];
    // delete keys and children from J
    bkJ.keys = bkJ.keys.copyWithin(0, shift, this.bp.bkSz);
    bkJ.keys.fill(undefined, sizeJ - shift, this.bp.bkSz);
    bkJ.children = bkJ.children.copyWithin(0, shift, this.bp.bkSz + 1);
    bkJ.children.fill(-1, sizeJ - shift + 1, this.bp.bkSz + 1);
  }

  /** #checkUnderflowZero() Check if an underflow has occured in the i'th
   *  child of block and, if so, fix it.
   * @param {BTNode} block block to check
   * @param {number} i the index i in block.children
   */
  #checkUnderflowZero(block, i) {
    var bkI = this.bp.bkSr.readBlock(block.children[i]);  // i'th child of block
    if (bkI.size() < this.bp.hfBS - 1) {  // underflow at I
      var bkJ = this.bp.bkSr.readBlock(block.children[i + 1]); // J right of I
      if (bkJ.size() > this.bp.hfBS) { // I can borrow from J
        this.#shiftRtoL(block, i, bkJ, bkI);
      } else { // I will absorb J
        this.#merge(block, i, bkI, bkJ);
        block.children[i] = bkI.index;
      }
    }
  }

  /** #shiftLtoR() Shift keys from node H into node I.
   * @param {BTNode} block the parent of H and I
   * @param {number} h the index h in block.children
   * @param {BTNode} bkH the left sibling of I
   * @param {BTNode} bkI the right sibling of H
   */
  #shiftLtoR(block, h, bkH, bkI) {
    var sizeI = bkI.size();
    var sizeH = bkH.size();
    var shift = Math.floor((sizeI + sizeH) / 2) - sizeI;  // num. keys to shift from H to I
    // make space for new keys in I
    bkI.keys = bkI.keys.copyWithin(shift, 0, sizeI);
    bkI.children = bkI.children.copyWithin(shift, 0, sizeI + 1);
    // move keys and children out of H and into I (and parent)
    bkI.keys[shift - 1] = block.keys[h];
    block.keys[h] = bkH.keys[sizeH - shift];
    var larger = bkH.keys.slice(sizeH - shift + 1, sizeH);
    bkI.keys.splice(0, larger.length, ...larger);
    bkH.keys.fill(undefined, sizeH - shift, sizeH);
    larger = bkH.children.slice(sizeH - shift + 1, sizeH + 1);
    bkI.children.splice(0, larger.length, ...larger);
    bkH.children.fill(-1, sizeH - shift + 1, sizeH + 1);
  }

  /** #checkUnderflowNonZero() Check if an underflow has occured in the i'th
   *  child of block and, if so, fix it.
   * @param {BTNode} block block to check
   * @param {number} i the index i in block.children
   */
  #checkUnderflowNonZero(block, i) {
    var bkI = this.bp.bkSr.readBlock(block.children[i]);  // i'th child of block
    if (bkI.size() < this.bp.hfBS - 1) {  // underflow at I
      var bkH = this.bp.bkSr.readBlock(block.children[i - 1]); // H left of I
      if (block.children[i + 1] >= 0) {  // look right ##perf##
        var bkJ = this.bp.bkSr.readBlock(block.children[i + 1]);  // J right of I
        var sizeH = bkH.size(), sizeI = bkI.size(), sizeJ = bkJ.size();
        if (sizeH + sizeI + sizeJ >= 3 * this.bp.hfBS) {
          this.#redist2(block, i, bkH, bkI, bkJ, sizeH, sizeJ);
        } else {
          this.#merge2(block, i, bkH, bkI, bkJ, sizeH, sizeI, sizeJ);
        }
      } else if (bkH.size() > this.bp.hfBS) {  // I can borrow from H
        this.#shiftLtoR(block, i - 1, bkH, bkI);
      } else {  // H will absorb I
        this.#merge(block, i - 1, bkH, bkI);
      }
    }
  }

  /** #checkUnderflow() Check if an underflow has occurred in the i'th child
   *  of block and, if so, fix it by borrowing from or merging with a sibling.
   * @param {BTNode} block block to check
   * @param {number} i the index i in block.children
   */
  #checkUnderflow(block, i) {
    if (block.children[i] < 0) { return; }
    if (i == 0) {
      this.#checkUnderflowZero(block, i); // use block's right sibling
    } else {
      this.#checkUnderflowNonZero(block, i);
    }
  }

  /** #removeSmallest() Remove the smallest value in the subtree rooted at the
   *  node with index.
   * @param {number} index the index of a subtree
   * @returns {any} the value that was removed
   */
  #removeSmallest(index) {
    var block = this.bp.bkSr.readBlock(index);
    if (block.isLeaf()) { return block.remove(0); }
    var left = this.#removeSmallest(block.children[0]);
    this.#checkUnderflow(block, 0);
    return left;
  }

  /** #removeRecursive() Remove the value from the subtree rooted at the node with index.
   * @param {any} value the value to remove
   * @param {number} index the index of the subtree to remove value from
   * @returns {boolean} true if value was removed and false otherwise
   */
  #removeRecursive(value, index) {
    if (index < 0) { return false; }  // didn't find it
    var block = this.bp.bkSr.readBlock(index);
    var i = findIt(block.keys, value, this.bp.compare);
    if (i < 0) { // found it
      i = -(i + 1);
      if (block.isLeaf()) {
        block.remove(i);
      } else {
        block.keys[i] = this.#removeSmallest(block.children[i + 1]);
        this.#checkUnderflow(block, i + 1);
      }
      return true;
    } else if (this.#removeRecursive(value, block.children[i])) {
      this.#checkUnderflow(block, i);
      return true;
    }
    return false;
  }

  /** remove() Remove a value from this tree.
   * @param {any} value the value
   * @returns {boolean} true if value was removed and false if value
   *            was not removed (because value was not present)
   */
  remove(value) {
    if (this.#removeRecursive(value, this.bp.rootNdx)) {
      this.bp.numEl--;
      var rootBk = this.bp.bkSr.readBlock(this.bp.rootNdx);
      if (rootBk.size() == 0 && this.bp.numEl > 0) { // root has only one child
        this.bp.rootNdx = rootBk.children[0];
      }
      return true;
    }
    return false;
  }

  /** findGE() Find the smallest element in the tree that is greater than or equal
   *  to value. If value is undefined, return the smallest element in the tree.
   * @param {any} value the value
   * @returns {any} the smallest element in the tree that is greater than or equal to
   *            value or undefined if no such element exists. If value is undefined
   *            then the smallest element in the tree
   */
  findGE(value) {
    var last = undefined;
    var cur = this.bp.rootNdx;
    while (cur >= 0) {
      var block = this.bp.bkSr.readBlock(cur);
      var i = findIt(block.keys, value, this.bp.compare);
      if (i < 0) { return block.keys[-(i + 1)]; } // found it
      if (block.keys[i] != undefined) { last = block.keys[i]; }
      cur = block.children[i];
    }
    return last;
  }

  /** findLT() Find the largest element in the tree that is less than value.
   *  If value is undefined, return the smallest element in the tree.
   * @param {any} value the value
   * @returns {any} the largest element in the tree that is less than value. If
   *          value is undefined then the smallest element in the tree
   */
  findLT(value) {
    var last = undefined;
    var cur = this.bp.rootNdx;
    while (cur >= 0) {
      var block = this.bp.bkSr.readBlock(cur);
      var i = findIt(block.keys, value, this.bp.compare);
      if (i < 0) { i = -(i + 1); }
      if (i > 0) { last = block.keys[i - 1]; }
      cur = block.children[i];
    }
    return last;
  }

  /** comparator()
   * @returns {function} the comparator of this tree's elements
   */
  comparator() {
    return this.bp.compare;
  }

  /** iteratorGE() Get an iterator of this tree starting with the smallest element
   *  in the tree that is greater than or equal to value. If value is undefined,
   *  returns iterator starting with the smallest element in the tree.
   * @param {any} value the value
   * @returns {BTIterator} iterator starting with the smallest element in the
   *              tree that is greater than or equal to value. If value is undefined,
   *              iterator starting with the smallest element in the tree.
   */
  iteratorGE(value) {
    return new BTIterator(this.bp, value);
  }

  /** @@iterator() Get an iterator of this tree. */
  *[Symbol.iterator]() {
    var iter = new BTIterator(this.bp, undefined);
    while (iter.hasNext()) {
      yield iter.next();
    }
  }

  /** size()
   * @returns {number} the number of elements in this tree
   */
  size() {
    return this.bp.numEl;
  }

  /** clear() Remove all elements from this tree. */
  clear() {
    this.bp.numEl = 0;
    this.bp.bkSr.clear();
    this.bp.rootNdx = (new BTNode(this.bp)).index;
  }

  /** #toString() Converts a tree to a string using recursion.
   * @param {number} index index of block
   * @param {StringBuffer} sBuf string buffer
   */
  #toString(index, sBuf) {
    if (index < 0) { return; }
    var block = this.bp.bkSr.readBlock(index);
    var i = 0;
    while(i < this.bp.bkSz && block.keys[i] != undefined) {
      this.#toString(block.children[i], sBuf);
      sBuf.str += block.keys[i++] + ", ";
    }
    this.#toString(block.children[i], sBuf);
  }

  /** toString() Converts this tree to a string.
   * @returns {string} this tree as a string
   */
  toString() {
    if (this.bp.numEl == 0) { return ""; }
    var sBuf = new StringBuffer();
    this.#toString(this.bp.rootNdx, sBuf);
    return sBuf.str.slice(0, sBuf.str.length - 2);
  }

  /** toString2()
   * @returns {string} in-order values formatted as array
   */
  toString2() {
    return JSON.stringify([...this]);
  }

  /** #toString3() Converts a tree to a string using recursion.
   * @param {number} index index of block
   * @param {number} depth depth of block
   * @param {StringBuffer} sBuf string buffer
   */
  #toString3(index, depth, sBuf) {
    if (index < 0) { return; }
    var block = this.bp.bkSr.readBlock(index);
    var i = 0;
    while(i < this.bp.bkSz && block.keys[i] != undefined) {
      this.#toString3(block.children[i], depth + 1, sBuf);
      sBuf.str += '\n' + " ".repeat(depth + 1) + block.keys[i++];
    }
    this.#toString3(block.children[i], depth + 1, sBuf);
  }

  /** toString3() Converts this tree (with depth) to a string.
   * @returns {string} this tree as a string
   */
  toString3() {
    if (this.bp.numEl == 0) { return ""; }
    var sBuf = new StringBuffer();
    this.#toString3(this.bp.rootNdx, 0, sBuf);
    return "tree with depth" + sBuf.str;
  }

  /** blocksToString()
   * @returns {string} this tree's blocks as a string
   */
  blocksToString() {
    var str = "blocks";
    for (var i = 0; i < this.bp.bkSr.blocks.length; i++) {
      if (this.bp.bkSr.blocks[i] != undefined) {
        if (i == this.bp.rootNdx) { str += "{root}"; }
        str += this.bp.bkSr.blocks[i].toString();
        if (i + 1 < this.bp.bkSr.blocks.length && this.bp.bkSr.blocks[i + 1] != undefined) {
          str += ",";
        }
      }
    }
    //str += "\nfree" + JSON.stringify([...this.bp.bkSr.free]);
    return str;
  }
}

/** compare() Compare values. This will work for string and number types.
 * @param {any} a a value
 * @param {any} b another value
 * @returns {number} -1 if a < b, 0 if a == b, 1 if a > b
 */
function compare(a, b) {
  if (a < b) { return -1; }
  else if (a > b) { return 1; }
  return 0;
}

/** assertSets() Assert that sizes and values of tree and set are equal.
 * @param {BTree} aTree a tree
 * @param {Set} aSet a set
 */
function assertSets(aTree, aSet) {
  if (aTree.size() == aSet.size) {
    var i = 0, setVals = Array.from(aSet).sort(compare);
    for (const tVal of aTree) {
      if (compare(tVal, setVals[i]) != 0) {
        throw new Error("assert: value mismatch");
      }
      i++;
    }
  } else {
    throw new Error("assert: size mismatch");
  }
}


var natoValues = ["alpha", "bravo", "charlie", "delta", "echo", "foxtrot", "golf", "hotel",
                  "india", "juliet", "kilo", "lima", "mike", "november", "oscar", "papa",
                  "quebec", "romeo", "sierra", "tango", "uniform"];
var wuValues = ["adams", "boston", "chicago", "denver", "easy", "frank", "george", "henry",
                "ida", "john", "king", "lincoln", "mary", "new york", "ocean", "peter",
                "queen", "roger", "sugar", "thomas", "union"];
var bTree = new BTree(15, compare);
var valuesSet = new Set();
var midNV = Math.floor(natoValues.length / 2);

for (var i = 0; i < natoValues.length; i++) {
  bTree.add(natoValues[i]);
  valuesSet.add(natoValues[i]);
}
console.log("--added " + natoValues.length + " nato phonetics--");
assertSets(bTree, valuesSet);

console.log(bTree.toString());

console.log("findGE(" + JSON.stringify(wuValues[0]) + ") = " + bTree.findGE(wuValues[0]));
console.log("size = " + bTree.size());

for (var i = wuValues.length - 1; i >= 0; i--) {
  bTree.add(wuValues[i]);
  valuesSet.add(wuValues[i]);
}
console.log("--added (in reverse order) " + wuValues.length + " western union phonetics--");
assertSets(bTree, valuesSet);

console.log(bTree.toString2());

console.log("findGE(" + JSON.stringify(wuValues[0]) + ") = " + bTree.findGE(wuValues[0]));
console.log("findLT(" + JSON.stringify(natoValues[midNV]) + ") = " + bTree.findLT(natoValues[midNV]));
console.log("size = " + bTree.size());

for (var i = 0; i < midNV; i++) {
  bTree.remove(natoValues[i]);
  valuesSet.delete(natoValues[i]);
}
console.log("--removed first " + midNV + " nato phonetics--");
assertSets(bTree, valuesSet);

console.log(bTree.toString());

console.log("findLT(" + JSON.stringify(wuValues[0]) + ") = " + bTree.findLT(wuValues[0]));
console.log("findLT(" + JSON.stringify(natoValues[midNV]) + ") = " + bTree.findLT(natoValues[midNV]));
console.log("findGE(\"victor\") = " + bTree.findGE("victor"));
var str = "";
var iter = bTree.iteratorGE(natoValues[midNV]);
while (iter.hasNext()) {
  str += iter.next()
  if (iter.hasNext()) { str += ", "; }
}
console.log("iteratorGE(" + JSON.stringify(natoValues[midNV]) + ") = " + str);
console.log("size = " + bTree.size());

console.log(bTree.toString3());

bTree.clear();
valuesSet.clear();
console.log("--clear--");
console.log(bTree.toString2());

/** @version 1.0a */