Computer Graphics & Visualization @ufrj.br
Public
Edited
May 20, 2023
45 forks
1 star
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 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;
}
}
}
/* 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.NIL);
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--;
}
} 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}}`;
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.