src/SkipList.js

import assert from 'assert';
import Node from './Node.js';
import keys from './keys.js';
import iter from './iter.js';
import downMost from './downMost.js';
import searchTopMost from './searchTopMost.js';
import bottomMostPredecessor from './bottomMostPredecessor.js';
import deleteFromTopMost from './deleteFromTopMost.js';
import insertFromBottomMostPredecessor from './insertFromBottomMostPredecessor.js';
import makeQuasiRandom from './makeQuasiRandom.js';
import makeBottomLevel from './makeBottomLevel.js';
 
/**
 * @param {Number} p Promotion probability in (0,1).
 * @param {Function} compare
 * @param {Node} head
 */
export default function SkipList(p, compare, head = new Node()) {
	this.head = head; // Sentinel node
	this.p = p;
	this.compare = compare;
}
 
SkipList.prototype.add = function (key) {
	const node = bottomMostPredecessor(this.compare, this.head, key);
	const pred = insertFromBottomMostPredecessor(this.p, node, key);
	if (pred.left === null && pred.up === null) this.head = pred;
};
 
SkipList.prototype.get = function (key) {
	const node = searchTopMost(this.compare, this.head, key);
	return node === null ? null : node.key;
};
 
SkipList.prototype.has = function (key) {
	return searchTopMost(this.compare, this.head, key) !== null;
};
 
SkipList.prototype.remove = function (key) {
	const node = searchTopMost(this.compare, this.head, key);
	if (node === null) return false;
 
	deleteFromTopMost(node);
	return true;
};
 
SkipList.prototype._predecessor = function (key) {
	return bottomMostPredecessor(this.compare, this.head, key);
};
 
SkipList.prototype.levelOne = function () {
	return downMost(this.head);
};
 
SkipList.prototype.levels = function () {
	assert(this.head !== null);
	let k = 0;
	let current = this.head;
	do {
		++k;
		current = current.down;
	} while (current !== null);
 
	return k;
};
 
SkipList.prototype.keys = function () {
	const level = this.levelOne();
	return keys(level);
};
 
SkipList.prototype.values = function () {
	return this.keys();
};
 
SkipList.prototype[Symbol.iterator] = function () {
	return this.keys();
};
 
SkipList.prototype.range = function* (left, right) {
	const pred = this._predecessor(left);
	for (const node of iter(pred)) {
		if (this.compare(node.key, right) >= 0) break;
		yield node.key;
	}
};
 
SkipList.from = (compare, iterable, p = 1 / 2) => {
	if (p === 1 / 2) {
		const bottomLevelHead = makeBottomLevel(compare, iterable);
		const head = makeQuasiRandom(p, bottomLevelHead);
		return new SkipList(p, compare, head);
	}
 
	const list = new SkipList(p, compare);
	for (const key of iterable) list.add(key);
	return list;
};