function newArray(size, value=null) {
return new Array(size).fill(value)
}
class Node {
constructor(key, val, level, extra, NIL) {
this.key = key;
this.val = val;
this.extra = extra;
this.forward = NIL ? newArray(level, NIL) : null; // null array
}
}
class SkipList {
constructor(max_level = 6, p = 0.5) {
this.level = 1;
this.maxLevel = max_level;
this.p = p; // Growth probability
this.NIL = new Node(Infinity, null, max_level, 0, null);
this.header = new Node(-Infinity, null, max_level, 0, this.NIL); // Node(key, val, level, extra)
}
Insert(key, val) {
/* Insertion
*/
let update = newArray(this.maxLevel, this.NIL);
let prevNode = newArray(this.maxLevel, update)
let height = this.level
let x = this.header;
// Search
for (let i = this.level - 1; i >= 0; i--) {
while (x.forward[i].key < key) {
x = x.forward[i];
}
update[i] = x;
}
x = x.forward[0];
let extra = 0;
if (x.key == key) {
x.val = val;
} else {
let new_level = this.randomLevel();
if (new_level >= this.level) {
for (let i = this.level; i <= new_level; i++) {
update[i] = this.header;
}
this.level = new_level + 1;
}
// Create node to insert
x = new Node(key, val, new_level, extra, this.NIL);
for (let i = 0; i < new_level; i++) {
x.forward[i] = update[i].forward[i];
update[i].forward[i] = x;
}
// calculates the extra of the node inserted
let y = update[x.forward.length - 1].forward[0] //sucessor pelo menor nível do antecessor pelo maior nível do nó x
while (y != x) {
if (x.forward[0].forward > x.forward.length) {
x.forward[0].forward[0].extra += 1
}
x.extra += 1
y = y.forward[0]
}
// Fix extras
let z = update[0].forward[0].forward[0] //sucessor pelo menor nível do nó x
let a = x.forward.length // número de níveis do nó x
while (z.key != Infinity) {
if (z.key > x.key) {
if (z.forward.length > a) {
z.extra += 1
a = z.forward.length
} else if (update[0].forward[0].forward[z.forward.length - 1] == z) {
if (update[0].forward[0].forward[0] == z) {
z.extra = 0
} else if (x.forward.length == z.forward.length) {
z.extra -= x.extra
} else if (update[z.forward.length - 1] != update[0]){
z.extra = z.extra - x.extra + 1
}
}
}
z = z.forward[0]
}
this.NIL.extra += 1
}
}
/* Search
** The search is done by going forward on the topmost level possible.
*/
Search(key) {
let x = this.header;
for (let i = this.level - 1; i >= 0; i--) {
while (x.forward[i].key < key) {
x = x.forward[i];
}
}
x = x.forward[0];
if (x.key == key) {
return x.val;
} else {
return undefined;
}
}
Delete(key) {
/* Deletion
*/
let update = newArray(this.maxLevel, this.update);
let x = this.header;
// Search
for (let i = this.level - 1; i >= 0; i--) {
while (x.forward[i].key < key) {
x = x.forward[i];
}
update[i] = x;
}
x = x.forward[0];
if (x.key === key) {
// Fix pointers
for (let i = 0; i < this.level; i++) {
if (update[i].forward[i] != x) {
break;
} else {
update[i].forward[i] = x.forward[i];
}
}
while (
this.level > 1 &&
this.header.forward[this.level - 2] === this.NIL
) {
this.level--;
}
// Fix extras
let a = x.forward.length // número de níveis do nó x
let z = update[0].forward[0] // o sucessor pelo menor nível do antecessor pelo menor nível de x, que é o próprio x
while (z.key != Infinity) {
if (z.forward.length > a) {
z.extra -= 1
a = z.forward.length
} else if (x.forward.length == z.forward.length) {
z.extra += x.extra
} else if (x.forward.length > z.forward.length) {
if (update[z.forward.length - 1] != update[0]) {
z.extra += x.extra
}
}
z = z.forward[0]
}
this.NIL.extra -= 1
} else {
throw `Key Error: key '${key}' not found.`;
}
}
Order(key) {
let total = 0;
let x = this.header;
for (let i = this.level - 1; i >= 0; i--) {
while (x.forward[i].key < key) {
x = x.forward[i];
total += x.extra + 1;
}
}
return total;
}
toString() {
let s = "header";
let x = this.header;
while (x.forward[0] != this.NIL) {
x = x.forward[0];
s = s + ` -> [${x.key}|${x.val}]`;
}
return s + " -> NIL";
}
randomLevel() {
let level = 1;
while (Math.random() < this.p && level < this.maxLevel - 1) {
// biased coin toss
level++;
}
return level;
}
}
viewof sl = {
refresh;
let div = htl.html`<div>`;
let L = new SkipList();
div.append(dot`${graphViz(L)}`, htl.html`<h2>INSERTION`);
let keys = d3.shuffle(d3.range(1, 100)).slice(0, 8);
for (let key of keys) {
div.append(htl.html`<br>Inserting ${key}<br>`);
L.Insert(key, null);
div.append(dot`${graphViz(L)}`);
}
div.append(htl.html`<h2>ORDER STATISTICS<br>`);
for (let key of d3.shuffle(d3.range(1, 100)).slice(0, 8)) {
div.append(htl.html`<p>${L.Order(key)} keys smaller than ${key}.`);
}
div.append(htl.html`<h2>DELETION<br>`);
d3.shuffle(keys);
for (let key of keys) {
div.append(htl.html`<br>Deleting ${key}<br>`);
L.Delete(key);
div.append(dot`${graphViz(L)}`);
}
div.value = L;
return div;
}
graphViz = function (sl) {
let header = {
key: "H",
forward: [...sl.header.forward],
extra: sl.header.extra
};
let top = sl.level;
let keys = [];
for (let i = 0; i < top; i++) keys[i] = header.key;
header.forward.length = top;
let node;
let next = function () {
node = header.forward[0];
header.key = node.key;
if (node == sl.NIL || !node.forward) return;
for (let i = 0; i < node.forward.length; i++) {
if (node.forward[i] == null) throw "ERROR";
header.forward[i] = node.forward[i];
keys[i] = node.key;
}
};
let result = "";
let emitNode = function (node) {
let box = [
node.key == "H" ? "-∞" : node.key == Infinity ? "∞" : node.key
];
let n = top;
if (node.forward) n = node.forward.length;
box.push(`x:${node.extra}`);
for (let i = 0; i < n; i++) box.push(`<${i}>`);
result += `struct${node.key}[ label = "${box.join("|")}" ];\n`;
};
let emitLinks = function (node) {
let n = top;
if (node.forward) n = node.forward.length;
for (let i = 0; i < n; i++) {
result += `struct${keys[i]}:<${i}>->struct${node.key}:<${i}>;\n`;
}
};
node = header;
for (;;) {
emitNode(node);
if (node == sl.NIL || !node.forward) break;
next();
}
header = { key: "H", forward: [...sl.header.forward] };
for (let i = 0; i < top; i++) keys[i] = header.key;
for (;;) {
emitLinks(header.forward[0]);
next();
if (node == sl.NIL || !node.forward) break;
}
return `digraph{
rankdir=LR;
node [ shape=record margin=0 width=0.3 fontsize=12 ];
${result}}`;
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
