Scapegoat tree with better performance

/* An implementation of scapegoat tree. It has tree methods add, remove,
 * findLE, findEQ, findGE, toArray, size, and clear. Ported from Open
 * Data Structures by Pat Morin. Includes a short demonstration of those
 * methods showing traversals of modified tree.
 * This version has better performing tree methods add and remove by way
 * of Morin Exercise 8..6.
 */

/** A node. */
class Vertex {
  /** constructor() credit: Morin 6.1. */
  constructor() {
    this.value;  // any
    this.left;   // Vertex ref
    this.right;  // Vertex ref
    this.parent; // Vertex ref
    this.numV;   // number of vertices in this subtree
    this.bSeen;  // boolean
  }
}

/** A sorted set. */
class ScapegoatTree {
  #nil; #root; #compare; #oeNV;
  /** constructor() credit: Morin BinaryTree.java, BinarySearchTree.java, ScapegoatTree.java.
   * @param {function} comparator function taking (any, any) and returning -1, 0, or 1
   */
  constructor(comparator) {
    this.#nil = new Vertex();  // vertex used as null
    this.#nil.numV = 0;
    this.#root = this.#nil;  // root vertex
    this.#compare = comparator;
    this.#oeNV = 0;  // an overestimate of this.#root.numV
  }

  /** #newVertex() credit: Morin BinaryTree.java, BinarySearchTree.java.
   * @param {any} value value used to order the tree
   * @returns {Vertex} a new vertex
   */
  #newVertex(value) {
    var vertex = new Vertex();
    vertex.value = value;
    vertex.left = this.#nil;
    vertex.right = this.#nil;
    vertex.parent = this.#nil;
    vertex.bSeen = false;
    return vertex;
  }

  /** #buildBalanced() A recursive helper that builds a perfectly balanced
   *  subtree out of array[i], ..., array[i + vxSz - 1]. credit: Morin 8.
   * @param {Array} array array of Vertex's
   * @param {number} i the index i in array
   * @param {number} vxSz vertex size
   * @returns {Vertex} the root of the newly created subtree
   */
  #buildBalanced(array, i, vxSz) {
    if (vxSz == 0) { return this.#nil; }
    var hfVS = Math.floor(vxSz / 2);
    array[i + hfVS].left = this.#buildBalanced(array, i, hfVS);
    if (array[i + hfVS].left != this.#nil) {
      array[i + hfVS].left.parent = array[i + hfVS];
    }
    array[i + hfVS].right = this.#buildBalanced(array, i + hfVS + 1, vxSz - hfVS - 1);
    if (array[i + hfVS].right != this.#nil) {
      array[i + hfVS].right.parent = array[i + hfVS];
    }
    array[i + hfVS].numV = vxSz;
    return array[i + hfVS];
  }

  /** #packIntoArray() A recursive helper that packs the subtree rooted at given
   *  vertex into array[i], ..., array[i + size(vertex) - 1]. credit: Morin 8.
   * @param {Vertex} vertex root of subtree
   * @param {boolean} flag pack vertex if false or value if true
   * @param {Array} array array of Vertex's if !flag or any if flag
   * @param {number} i the index i in array
   * @returns {number} size(vertex)
   */
  #packIntoArray(vertex, flag, array, i) {
    if (vertex == this.#nil) { return i; }
    i = this.#packIntoArray(vertex.left, flag, array, i);
    if (flag) { array[i++] = vertex.value; }
    else { array[i++] = vertex; }
    return this.#packIntoArray(vertex.right, flag, array, i);
  }

  /** #sizeOfV() Get vertex size. credit: Morin 6.1.1.
   * @param {Vertex} vertex vertex to calculate size for
   * @returns {number} size of given vertex
   */
  #sizeOfV(vertex) {
    if (vertex == this.#nil) { return 0; }
    return 1 + this.#sizeOfV(vertex.left) + this.#sizeOfV(vertex.right);
  }

  /** #rebuild() credit: Morin 8.
   * @param {Vertex} vertex root of subtree
   */
  #rebuild(vertex) {
    var p = vertex.parent;
    var array = new Array(vertex.numV);  // of Vertex's
    this.#packIntoArray(vertex, false, array, 0);
    if (p == this.#nil) {
      this.#root = this.#buildBalanced(array, 0, vertex.numV);
      this.#root.parent = this.#nil;
    } else if (p.right == vertex) {
      p.right = this.#buildBalanced(array, 0, vertex.numV);
      p.right.parent = p;
    } else {
      p.left = this.#buildBalanced(array, 0, vertex.numV);
      p.left.parent = p;
    }
  }

  /** toArray()
   * @returns {Array} array of in-order values
   */
  toArray() {
    var array = new Array(this.#root.numV);  // of any
    this.#packIntoArray(this.#root, true, array, 0);
    return array;
  }

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

  /** #addWithDepth() Do a normal BinarySearchTree insertion, but return the
   *  depth of the newly inserted vertex. credit: Morin ScapegoatTree.java.
   * @param {Vertex} vertex vertex to add
   * @returns {number} the depth of the newly inserted vertex, or -1 if
   *              the vertex was not inserted
   */
  #addWithDepth(vertex) {
    var cur = this.#root;
    if (cur == this.#nil) {
      this.#root = vertex;
      this.#oeNV++;
      return 0;
    }
    var done = false;
    var depth = 0;
    do {
      var res = this.#compare(vertex.value, cur.value);
      if (res < 0) {
        if (cur.left == this.#nil) {
          cur.left = vertex;
          vertex.parent = cur;
          done = true;
        }
        cur = cur.left;
      } else if (res > 0) {
        if (cur.right == this.#nil) {
          cur.right = vertex;
          vertex.parent = cur;
          done = true;
        }
        cur = cur.right;
      } else {
        return -1;
      }
      depth++;
    } while (!done);
    // traverse up the tree, incrementing num. vertices
    while (cur != this.#root) {
      cur = cur.parent;
      cur.numV++;
    }
    this.#oeNV++;
    return depth;
  }

  /** log32() Compute the ceiling of log_{3 / 2}(oeNV). credit: Morin ScapegoatTree.java.
   * @param {number} oeNV overestimate of num. vertices
   * @returns {number} the ceiling of log_{3 / 2}(oeNV)
   */
  static log32(oeNV) {
    const log23 = 2.4663034623764317;
    return Math.ceil(log23 * Math.log(oeNV));
  }

  /** add() credit: Morin 8.1.
   * @param {any} value value to add
   * @returns {boolean} success?
   */
  add(value) {
    var vertex = this.#newVertex(value);
    vertex.numV = 1;
    var depth = this.#addWithDepth(vertex); // get depth of inserted vertex
    if (depth > ScapegoatTree.log32(this.#oeNV)) {  // depth exceeded, find scapegoat
      var cur = vertex.parent;
      while (3 * cur.numV <= 2 * cur.parent.numV) {
        cur = cur.parent;
      }
      this.#rebuild(cur.parent);
    }
    return depth >= 0;
  }

  /** #splice() credit: Morin 6.2.3.
   * @param {Vertex} vertex vertex to splice
   */
  #splice(vertex) {
    var cur, prev;
    if (vertex.left != this.#nil) {
      cur = vertex.left;
    } else {
      cur = vertex.right;
    }
    if (vertex == this.#root) {
      if (cur == vertex.left && vertex.right != this.#nil) {
        cur.numV += vertex.right.numV;
      }
      this.#root = cur;
      prev = this.#nil;
    } else {
      prev = vertex.parent;
      if (prev.left == vertex) {
        prev.left = cur;
      } else {
        prev.right = cur;
      }
      // traverse up the tree, decrementing num. vertices
      var p = vertex.parent;
      do {
        p.numV--;
        p = p.parent;
      } while (p != this.#nil);
    }
    if (cur != this.#nil) {
      cur.parent = prev;
    }
  }

  /** #rmVert() Remove the given vertex from the binary search tree.
   *  credit: Morin 6.2.3.
   * @param {Vertex} vertex vertex to remove
   */
  #rmVert(vertex) {
    if (vertex.left == this.#nil || vertex.right == this.#nil) {
      this.#splice(vertex);
    } else {
      var cur = vertex.right;
      while (cur.left != this.#nil) { cur = cur.left; }
      vertex.value = cur.value;
      this.#splice(cur);
    }
  }

  /** #findLast() credit: Morin 6.2.2.
   * @param {any} value value for comparison
   * @returns {Vertex} last vertex found on path for value
   */
  #findLast(value) {
    var cur = this.#root, prev = this.#nil;
    while (cur != this.#nil) {
      prev = cur;
      var res = this.#compare(value, cur.value);
      if (res < 0) { cur = cur.left; }
      else if (res > 0) { cur = cur.right; }
      else { return cur; }
    }
    return prev;
  }

  /** rmVal() credit: Morin BinarySearchTree.java.
   * @param {any} value value to remove
   * @returns {boolean} success?
   */
  #rmVal(value) {
    var vertex = this.#findLast(value);
    if (vertex != this.#nil && this.#compare(value, vertex.value) == 0) {
      this.#rmVert(vertex);
      return true;
    }
    return false;
  }

  /** remove() credit: Morin 8.1.
   * @param {any} value value to remove
   * @returns {boolean} success?
   */
  remove(value) {
    if (this.#rmVal(value)) {
      if (2 * this.#root.numV < this.#oeNV) {
        this.#rebuild(this.#root);
        this.#oeNV = this.#root.numV;
      }
      return true;
    }
    return false;
  }

  /** findEQ() Find an equal value. credit: Morin 6.2.1.
   * @param {any} value value to find
   * @returns {any} value if found, undefined if not found
   */
  findEQ(value) {
    var cur = this.#root;
    while (cur != this.#nil) {
      var res = this.#compare(value, cur.value);
      if (res < 0) { cur = cur.left; }
      else if (res > 0) { cur = cur.right; }
      else { return cur.value; }
    }
    return undefined;
  }

  /** #findGEVertex() credit: Morin BinarySearchTree.java.
   * @param {any} value value to find
   * @returns {Vertex} last vertex found on path for value
   */
  #findGEVertex(value) {
    var cur = this.#root, last = this.#nil;
    while (cur != this.#nil) {
      var res = this.#compare(value, cur.value);
      if (res < 0) {
        last = cur;
        cur = cur.left;
      } else if (res > 0) {
        cur = cur.right;
      } else {
        return cur;
      }
    }
    return last;
  }

  /** findGE() Find smallest value in tree greater than or equal to given value, or undefined
   * if no such value. Or, if given value is undefined then the smallest value in tree.
   * credit: Morin BinarySearchTree.java, SSet.java.
   * @param {any} value value to find
   * @returns {any} smallest value in tree greater than or equal to given value, or undefined if no
   *               such value. Or, if given value is undefined then the smallest value in tree.
   */
  findGE(value) {
    if (value == undefined) {  // find the minimum value
      var cur = this.#root;
      if (cur == this.#nil) { return undefined; }
      while (cur.left != this.#nil) {
        cur = cur.left;
      }
      return cur.value;
    }
    var cur = this.#findGEVertex(value);
    if (cur == this.#nil) { return undefined; }
    return cur.value;
  }

  /** #findLEVertex() credit: Morin BinarySearchTree.java.
   * @param {any} value value to find
   * @returns {Vertex} last vertex found on path for value
   */
  #findLEVertex(value) {
    var cur = this.#root, last = this.#nil;
    while (cur != this.#nil) {
      var res = this.#compare(value, cur.value);
      if (res < 0) {
        cur = cur.left;
      } else if (res > 0) {
        last = cur;
        cur = cur.right;
      } else {
        return cur;
      }
    }
    return last;
  }

  /** findLE() Find largest value in tree less than or equal to given value, or undefined
   * if no such value. Or, if given value is undefined then the largest value in tree.
   * credit: Morin BinarySearchTree.java findLT [sic].
   * @param {any} value value to find
   * @returns {any} largest value in tree less than or equal to given value, or undefined if no
   *               such value. Or, if given value is undefined then the largest value in tree.
   */
  findLE(value) {
    if (value == undefined) {  // find the maximum value
      var cur = this.#root;
      if (cur == this.#nil) { return undefined; }
      while (cur.right != this.#nil) {
        cur = cur.right;
      }
      return cur.value;
    }
    var cur = this.#findLEVertex(value);
    if (cur == this.#nil) { return undefined; }
    return cur.value;
  }

  /** #depth() Get vertex depth. credit: Morin 6.1.
   * @param {Vertex} vertex vertex to calculate depth for
   * @returns {number} depth of given vertex
   */
  #depth(vertex) {
    var count = 0;
    while (vertex != this.#root) {
      vertex = vertex.parent;
      count++;
    }
    return count;
  }

  /** size3() Get tree size.
   * @returns {number} size of tree
   */
  size3() {
    return this.#sizeOfV(this.#root);
  }

  verify() {
    if (this.size3() != this.#root.numV) {
      throw new Error("verify: size is incorrect");
    } else if (2 * this.#root.numV < this.#oeNV) {
      throw new Error("verify: overestimate is too high");
    } else if (this.height() > ScapegoatTree.log32(this.#oeNV)) {
      throw new Error("verify: tree is too tall");
    }
  }

  /** size() Get tree size. credit: Morin BinarySearchTree.java.
   * @returns {number} size of tree
   */
  size() {
    return this.#root.numV;
  }

  /** clear() credit: Morin BinaryTree.java, BinarySearchTree.java. */
  clear() {
    this.#root = this.#nil;
  }

  /** #heightOfV() Get vertex height. credit: Morin 6.1.1.
   * @param {Vertex} vertex vertex to calculate height for
   * @returns {number} height of given vertex, or -1 if nil vertex
   */
  #heightOfV(vertex) {
    if (vertex == this.#nil) { return -1; }
    return 1 + Math.max(this.#heightOfV(vertex.left), this.#heightOfV(vertex.right));
  }

  /** height() Get tree height.
   * @returns {number} height of root, or -1 if nil root
   */
  height() {
    return this.#heightOfV(this.#root);
  }

  /** #formatVertices()
   * @param {boolean} flag if true, append additional vertex info
   * @param {Vertex[]} vertices vertices in this tree
   * @returns {string} vertices formatted as tree
   */
  #formatVertices(flag, vertices) {
    var retVertices = "";
    for (var i = 0; i < vertices.length; i++) {
      retVertices += '\n' + " ".repeat(this.#depth(vertices[i]) + 1) + vertices[i].value;
      if (flag) {
        var height = this.#heightOfV(vertices[i]);
        retVertices += "  height=" + height + "  size=" + vertices[i].numV;
        if (vertices[i].parent != this.#nil) {
          retVertices += "  parent=" + vertices[i].parent.value;
        }
      }
    }
    return retVertices;
  }

  /** #traverseInner() Inner depth-first traverse. credit: Morin 6.1.2.
   * @param {Vertex} vertex vertex to traverse
   * @param {Vertex[]} dfVertices discovered vertices
   */
  #traverseInner(vertex, dfVertices) {
    if (vertex == this.#nil) { return; }
    vertex.bSeen = true;
    if (!vertex.left.bSeen) {
      vertex.left.bSeen = true;
      this.#traverseInner(vertex.left, dfVertices);
    }
    if (!vertex.right.bSeen) {
      vertex.right.bSeen = true;
      this.#traverseInner(vertex.right, dfVertices);
    }
    dfVertices.unshift(vertex);
  }

  /** traverse() Depth-first traverse.
   * @returns {string} vertices formatted as tree
   */
  traverse() {
    var dfVertices = [];
    this.#traverseInner(this.#root, dfVertices);
    this.bfTraverse(false);
    return "depth-first traverse" + this.#formatVertices(false, dfVertices);
  }

  /** traverse2() Depth-first traverse. credit: Morin 6.1.2.
   * @returns {string} vertices formatted as tree
   */
  traverse2() {
    var dfVertices = [];
    var cur = this.#root, prev = this.#nil, next;
    while (cur != this.#nil) {
      if (prev == cur.parent) {
        if (cur.left != this.#nil) { next = cur.left; }
        else if (cur.right != this.#nil) { next = cur.right; }
        else { next = cur.parent; }
      } else if (prev == cur.left) {
        if (cur.right != this.#nil) { next = cur.right; }
        else { next = cur.parent; }
      } else {
        next = cur.parent;
      }
      prev = cur;
      if (!cur.bSeen) {
        dfVertices.push(cur);
        cur.bSeen = true;
      }
      cur = next;
    }
    this.bfTraverse(false);
    return "depth-first traverse #2" + this.#formatVertices(false, dfVertices);
  }

  /** bfTraverse() Breadth-first traverse. credit: Morin 6.1.2.
   * @param {boolean} flag true: set bSeen, false: unset bSeen
   * @returns {string} vertices formatted as tree
   */
  bfTraverse(flag) {
    var bfVertices = [];
    var queue = [];  // queue of Vertex's
    if (this.#root != this.#nil) {
      queue.push(this.#root);
      this.#root.bSeen = flag;
    }
    while (queue.length > 0) {
      var vertex = queue.shift();
      if (flag) { bfVertices.push(vertex); }
      if (vertex.left != this.#nil) {
        if (flag) {
          if (!vertex.left.bSeen) {
            queue.push(vertex.left);
            vertex.left.bSeen = flag;
          }
        } else {
          queue.push(vertex.left);
          vertex.left.bSeen = flag;
        }
      }
      if (vertex.right != this.#nil) {
        if (flag) {
          if (!vertex.right.bSeen) {
            queue.push(vertex.right);
            vertex.right.bSeen = flag;
          }
        } else {
          queue.push(vertex.right);
          vertex.right.bSeen = flag;
        }
      }
    }
    if (flag) { this.bfTraverse(false); }
    return "breadth-first traverse" + this.#formatVertices(true, bfVertices);
  }

  /** size2() Get tree size. credit: Morin 6.1.2.
   * @returns {number} size of tree
   */
  size2() {
    var cur = this.#root, prev = this.#nil, next;
    var count = 0;
    while (cur != this.#nil) {
      if (prev == cur.parent) {
        count++;
        if (cur.left != this.#nil) { next = cur.left; }
        else if (cur.right != this.#nil) { next = cur.right; }
        else { next = cur.parent; }
      } else if (prev == cur.left) {
        if (cur.right != this.#nil) { next = cur.right; }
        else { next = cur.parent; }
      } else {
        next = cur.parent;
      }
      prev = cur;
      cur = next;
    }
    return count;
  }
}

/** 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 {ScapegoatTree} aTree a tree
 * @param {Set} aSet a set
 */
function assertSets(aTree, aSet) {
  if (aTree.size() == aSet.size) {
    var arrVals = aTree.toArray(), setVals = Array.from(aSet).sort(compare);
    for (var i = 0; i < arrVals.length; i++) {
      if (compare(arrVals[i], setVals[i]) != 0) {
        throw new Error("assert: value mismatch");
      }
    }
  } 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 sgTree = new ScapegoatTree(compare);
var valuesSet = new Set();
var midNV = Math.floor(natoValues.length / 2);

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

console.log(sgTree.traverse());

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

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

console.log(sgTree.traverse());

console.log("findEQ(" + JSON.stringify(wuValues[0]) + ") = " + sgTree.findEQ(wuValues[0]));
console.log("findLE(" + JSON.stringify(natoValues[0]) + ") = " + sgTree.findLE(natoValues[0]));
console.log("minimum = " + sgTree.findGE(undefined) + ", maximum = " + sgTree.findLE(undefined));
console.log("size = " + sgTree.size() + ", size #2 = " + sgTree.size2() + ", size #3 = " + sgTree.size3());
console.log("height = " + sgTree.height());

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

console.log(sgTree.traverse2());

console.log("findEQ(" + JSON.stringify(natoValues[0]) + ") = " + sgTree.findEQ(natoValues[0]));
console.log("findLE(" + JSON.stringify(natoValues[midNV]) + ") = " + sgTree.findLE(natoValues[midNV]));
console.log("findGE(" + JSON.stringify(natoValues[0]) + ") = " + sgTree.findGE(natoValues[0]));

console.log(sgTree.bfTraverse(true));

console.log("toString = " + sgTree.toString());
sgTree.clear();
valuesSet.clear();
console.log("--clear--");
console.log("toString = " + sgTree.toString());

/** @version 1.0c */