Skiplist with demo

/* An implementation of skiplist. It has list methods get, set, add, absorb,
 * remove, truncate, getNdx, @@iterator, size, clear, and toString. Ported
 * from Open Data Structures by Pat Morin. Includes a short demonstration of
 * those methods.
 * Note: absorb (Morin Exercise 4..12) and truncate (Morin Exercise 4..11)
 * are non-standard and have time complexity slightly higher than O(log n).
 */

/** Node in a skiplist. credit: Morin SkiplistList.java. */
class SLNode {
  /** constructor()
   * @param {any} val a value
   * @param {number} ht height of this node
   */
  constructor(val, ht) {
    this.val = val;
    this.nx = new Array(ht + 1);  // of SLNode
    this.len = new Array(ht + 1);  // of number
  }

  /** height()
   * @returns {number} the height of this node
   */
  height() {
    return this.nx.length - 1;
  }
}

/** Properties of a skiplist. */
class SLProps {
  sl; // the SkiplistList
  sn; // the SLNode on the left side of the skiplist
}

/** Iterator of skiplist. credit: Morin SkiplistList.java. */
class SLIterator {
  #node; // SLNode
  #i;  // number
  #rm; // boolean
  /** constructor() Create an iterator that takes O(log n) time per step.
   * @param {SLProps} sp properties of the skiplist
   */
  constructor(sp) {
    this.sp = sp;
    this.#node = sp.sn;
    this.#i = -1;
    this.#rm = false;
  }

  /** hasNext()
   * @returns {boolean}
   */
  hasNext() {
    return this.#node.nx[0] != undefined;
  }

  /** next()
   * @returns {any}
   */
  next() {
    if (this.#node.nx[0] == undefined) { throw new Error("no such element"); }
    this.#node = this.#node.nx[0];
    this.#i++;
    this.#rm = true;
    return this.#node.val;
  }

  remove() {
    if (!this.#rm) { throw new Error("illegal state"); }
    this.sp.sl.remove(this.#i);
    this.#i--;
    this.#rm = false;
  }
}

/** rand() Generate random number x such that 0 <= x < num.
 * @param {number} num upper bound (exclusive)
 * @returns {number}
 */
function rand(num) {
  return Math.floor(Math.random() * num);
}

/** A skiplist where all the standard operations take O(log n) time.
 *  credit: Morin SkiplistList.java.
 */
class SkiplistList {
  constructor() {
    this.nEl = 0;  // the number of elements stored in the skiplist
    this.sn = new SLNode(undefined, 32);
    this.maxHt = 0; // the maximum height of any element
    this.sp = new SLProps();
    this.sp.sn = this.sn;
    this.sp.sl = this;
  }

  /** #findPred() Find the node that precedes list index i in the skiplist.
   * @param {number} i the index i
   * @returns {SLNode} the predecessor of the node at index i or the final
   *              node if i exceeds size() - 1.
   */
  #findPred(i) {
    var node = this.sn; // SLNode
    var ht = this.maxHt;
    var j = -1;   // index of the current node in list 0
    while (ht >= 0) {
      while (node.nx[ht] != undefined && j + node.len[ht] < i) {
        j += node.len[ht];
        node = node.nx[ht];
      }
      ht--;
    }
    return node;
  }

  /** get()
   * @param {number} i the index i
   * @returns {any} value at index i
   */
  get(i) {
    if (i < 0 || i > this.nEl - 1) { throw new Error("index out of bounds"); }
    return this.#findPred(i).nx[0].val;
  }

  /** set()
   * @param {number} i the index i
   * @param {any} val value to store at index i
   * @returns {any} previous value at index i
   */
  set(i, val) {
    if (i < 0 || i > this.nEl - 1) { throw new Error("index out of bounds"); }
    var node = this.#findPred(i).nx[0]; // SLNode
    var old = node.val;
    node.val = val;
    return old;
  }

  /** #add() Insert a new node into the skiplist.
   * @param {number} i the index of the new node
   * @param {SLNode} nwNd the node to insert
   * @returns {SLNode} the node that precedes nwNd in the skiplist
   */
  #add(i, nwNd) {
    var node = this.sn;
    var newHt = nwNd.height();
    var ht = this.maxHt;
    var j = -1; // index of node
    while (ht >= 0) {
      while (node.nx[ht] != undefined && j + node.len[ht] < i) {
        j += node.len[ht];
        node = node.nx[ht];
      }
      node.len[ht]++; // accounts for new node in list 0
      if (ht <= newHt) {
        nwNd.nx[ht] = node.nx[ht];
        node.nx[ht] = nwNd;
        nwNd.len[ht] = node.len[ht] - (i - j);
        node.len[ht] = i - j;
      }
      ht--;
    }
    this.nEl++;
    return node;
  }

  /** #pickHeight() Simulate repeatedly tossing a coin until it comes up tails.
   * @returns {number} the number of coin tosses - 1 (max 32)
   */
  #pickHeight() {
    var z = rand(Number.MAX_SAFE_INTEGER);
    var k = 0, m = 1;
    while ((z & m) != 0) {
      k++;
      m = m << 1;
    }
    return k;
  }

  /** add() Insert a value into the skiplist.
   * @param {number} i the index of the new node
   * @param {any} val the value to insert
   */
  add(i, val) {
    if (i < 0 || i > this.nEl) { throw new Error("index out of bounds"); }
    var nwNd = new SLNode(val, this.#pickHeight());
    if (nwNd.height() > this.maxHt) { this.maxHt = nwNd.height(); }
    this.#add(i, nwNd);
  }

  /** absorb() Append another skiplist to this skiplist, leaving the other
   *  skiplist empty.
   * @param {SkiplistList} aSL skiplist to absorb
   */
  absorb(aSL) {
    var node = this.sn;
    var ht = this.maxHt;
    var j = -1;
    while (ht >= 0) {
      if (ht > 0 && ht <= aSL.maxHt) {
        if (node.nx[ht] == undefined) {
          node.nx[ht] = aSL.sn.nx[ht];
          aSL.sn.nx[ht] = undefined;
          node.len[ht] = aSL.sn.len[ht] + this.nEl - (j + 1);
          aSL.sn.len[ht] = 0;
          ht--;
        } else {
          while (node.nx[ht] != undefined) {
            j += node.len[ht];
            node = node.nx[ht];
          }
        }
      } else {
        while (node.nx[ht] != undefined) {
          j += node.len[ht];
          node = node.nx[ht];
        }
        ht--;
      }
    }
    node.nx[0] = aSL.sn.nx[0];
    aSL.sn.nx[0] = undefined;
    node.len[0] = aSL.sn.len[0];
    aSL.sn.len[0] = 0;
    if (this.maxHt < aSL.maxHt) {
      for (ht = this.maxHt + 1; ht > 0 && ht <= aSL.maxHt; ht++) {
        this.maxHt++;
        this.sn.nx[this.maxHt] = aSL.sn.nx[ht];
        aSL.sn.nx[ht] = undefined;
        this.sn.len[this.maxHt] = aSL.sn.len[ht] + this.nEl;
        aSL.sn.len[ht] = 0;
      }
    }
    this.nEl += aSL.nEl;
    aSL.maxHt = 0;
    aSL.nEl = 0;
  }

  /** remove() Remove a node from the skiplist.
   * @param {number} i the index i
   * @returns {any} the value removed
   */
  remove(i) {
    if (i < 0 || i > this.nEl - 1) { throw new Error("index out of bounds"); }
    var val = undefined;
    var node = this.sn;
    var ht = this.maxHt;
    var j = -1; // index of node
    while (ht >= 0) {
      while (node.nx[ht] != undefined && j + node.len[ht] < i) {
        j += node.len[ht];
        node = node.nx[ht];
      }
      node.len[ht]--;  // for the node we are removing
      if (j + node.len[ht] + 1 == i && node.nx[ht] != undefined) {
        val = node.nx[ht].val;
        node.len[ht] += node.nx[ht].len[ht];
        node.nx[ht] = node.nx[ht].nx[ht];
        if (node == this.sn && node.nx[ht] == undefined) { this.maxHt--; }
      }
      ht--;
    }
    this.nEl--;
    return val;
  }

  /** truncate() Truncate this skiplist so that it contains elements sl[0..i - 1]
   *  and return a new skiplist with elements sl[i..size() - 1].
   * @param {number} i the index i
   * @returns {SkiplistList} skiplist with elements sl[i..size() - 1]
   */
  truncate(i) {
    if (i < 0 || i > this.nEl - 1) { throw new Error("index out of bounds"); }
    var nwL = new SkiplistList();
    var node = this.sn;
    var ht = this.maxHt;
    var j = -1;
    while (ht >= 0) {
      while (node.nx[ht] != undefined && j + node.len[ht] < i) {
        j += node.len[ht];
        node = node.nx[ht];
      }
      if (node == this.sn && node.len[ht] > i) {
        node.len[ht] -= i;
        nwL.sn.nx.copyWithin(1, 0);
        nwL.sn.nx[0] = node.nx[this.maxHt];
        node.nx[this.maxHt] = undefined;
        nwL.sn.len.copyWithin(1, 0);
        nwL.sn.len[0] = node.len[this.maxHt];
        node.len[this.maxHt] = 0;
        nwL.maxHt++;
        this.maxHt--;
      } else if (j == i - 1) {
        nwL.sn.nx.copyWithin(1, 0);
        nwL.sn.nx[0] = node.nx.pop();
        nwL.sn.len.copyWithin(1, 0);
        nwL.sn.len[0] = node.len.pop();
        nwL.maxHt++;
      } else if (j + node.len[ht] >= i) {
        node.nx.pop();
        node.len.pop();
      }
      ht--;
    }
    nwL.nEl = this.nEl - i;
    this.nEl = i;
    return nwL;
  }

  /** getNdx() Get the list index of a value.
   * @param {any} val value to find
   * @returns {number} index if found, -1 if not found
   */
  getNdx(val) {
    var node = this.sn, i = -1;
    while (node.nx[0] != undefined) {
      node = node.nx[0];
      i++;
      if (node.val == val) { return i; }
    }
    return -1;
  }

  /** @@iterator() Get an iterator of this list. */
  *[Symbol.iterator]() {
    var iter = new SLIterator(this.sp);
    while (iter.hasNext()) { yield iter.next(); }
  }

  /** size()
   * @returns {number} the number of elements in this list
   */
  size() {
    return this.nEl;
  }

  /** clear() Remove all elements from this list. */
  clear() {
    this.sn.nx.fill(undefined, 0, this.maxHt + 1);
    this.sn.len.fill(0, 0, this.maxHt + 1);
    this.maxHt = 0;
    this.nEl = 0;
  }

  /** toString()
   * @returns {string} list values formatted as array
   */
  toString() {
    return JSON.stringify([...this]);
  }
}

/** 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;
}

/** swap() Swap values at list indexes i and j in the skiplist.
 *  credit: Morin Algorithms.java.
 * @param {SkiplistList} sl the skiplist
 * @param {number} i the index i
 * @param {number} j the index j
 */
function swap(sl, i, j) {
  var val = sl.set(i, sl.get(j));
  sl.set(j, val);
}

/** quickSort() Run quicksort on the sublist sl[i], ...,sl[i + num - 1].
 *  credit: Morin Algorithms.java.
 * @param {SkiplistList} sl the skiplist
 * @param {number} i the index to start sort from
 * @param {number} num the number of elements to sort
 */
function quickSort(sl, i, num) {
  if (num <= 1) { return; }
  var val = sl.get(i + rand(num));
  var p = i - 1, j = i, q = i + num;
  // sl[i..p] < val, sl[p + 1..q - 1] == val, sl[q..i + num - 1] > val
  while (j < q) {
    var cmp = compare(sl.get(j), val);
    if (cmp < 0) {        // move to beginning of list
      swap(sl, j++, ++p);
    } else if (cmp > 0) { // move to end of list
      swap(sl, j, --q);
    } else {              // keep in the middle
      j++;
    }
  }
  quickSort(sl, i, p - i + 1);
  quickSort(sl, q, num - (q - i));
}

/** assertSL() Assert that sizes and values of list and array are equal.
 * @param {SkiplistList} sl the skiplist
 * @param {Array} arr the array
 */
function assertSL(sl, arr) {
  if (sl.size() == arr.length) {
    var i = 0;
    for (const val of sl) {
      if (compare(val, arr[i]) != 0) { throw new Error("assert: value mismatch"); }
      i++;
    }
  } else {
    throw new Error("assert: size mismatch");
  }
}


var sL = new SkiplistList(), aSL = new SkiplistList();
var num = 100, nVals = new Array(), midNV = Math.floor(num / 2);

for (var i = 0; i < midNV; i++) {   // add at end
  nVals[i] = rand(num * 10);
  aSL.add(i, nVals[i]);
}
console.log("--added " + midNV + " random numbers--");
for (var i = midNV; i < num; i++) { // add at front
  nVals.unshift(rand(num * 10));
  sL.add(0, nVals[0]);
}
sL.absorb(aSL);
console.log("--absorbed " + (num - midNV) + " random numbers--");
console.log(sL.toString());
assertSL(sL, nVals);

console.log("getNdx(" + (num * 10) + ") = " + sL.getNdx(num * 10));
var val = sL.get(midNV);
console.log("getNdx(" + val + ") = " + sL.getNdx(val));

nVals.sort(compare);
quickSort(sL, 0, sL.size());
console.log("--sorted " + num + " numbers using quicksort--");
assertSL(sL, nVals);
console.log(sL.toString());

var front = sL.get(0), mid = sL.get(midNV), end = sL.get(num - 1);
console.log("getNdx(" + front + ") = " + sL.getNdx(front));
console.log("getNdx(" + end + ") = " + sL.getNdx(end));

sL.remove(sL.size() - 1);
sL.remove(midNV);
sL.remove(0);
nVals = nVals.slice(1, midNV).concat(nVals.slice(midNV + 1, num - 1));
console.log("--removed end, middle, and front numbers (" + end + ", " + mid + ", " + front + ")--");
assertSL(sL, nVals);
console.log(sL.toString());
console.log("size = " + sL.size());

var rmL = sL.truncate(Math.floor(sL.size() / 2));
console.log("--truncated at middle--");
console.log("sl = " + sL.toString());
console.log("rm = " + rmL.toString());

sL.clear();
console.log("--clear--");
console.log("sl = " + sL.toString());

/** @version 1.0d */