comparator = (a, b) => a - b
stubTrue = () => true
identity = T => T
class Tree {
constructor(options = {}) {
const { update, remove, compare, create } = {
update: identity,
remove: stubTrue,
compare: comparator,
create: node,
...options
};
this[s.del] = remove.bind(this);
this[s.up] = update.bind(this);
this[s.create] = create.bind(this);
this[s.comparator] = compare.bind(this);
this.root = null;
this.min = this.max = null;
this.length = 0;
this.insert = this.insert.bind(this);
this[s.insert] = this[s.insert].bind(this);
this.remove = this.remove.bind(this);
this[s.remove] = this[s.remove].bind(this);
this[s.new_left] = this[s.new_left].bind(this);
this[s.new_right] = this[s.new_right].bind(this);
this.forEach = this.forEach.bind(this);
}
[s.new_left](parent, value) {
const n = this[s.create](value);
this.length++;
const prev = parent.prev;
if (prev) {
n.prev = prev;
prev.next = n;
} else {
this.min = n;
}
parent.prev = n;
n.next = parent;
return n;
}
[s.new_right](parent, value) {
const n = this[s.create](value);
this.length++;
const next = parent.next;
if (next) {
n.next = next;
next.prev = n;
} else {
this.max = n;
}
parent.next = n;
n.prev = parent;
return n;
}
insert(value) {
this.root = this[s.insert](value, this.root);
}
[s.insert](X, T) {
if (nil(T)) {
const n = this[s.create](X);
this.length++;
this.min = n;
this.max = n;
return n;
}
const compare = this[s.comparator](X, T.value);
if (compare < 0) {
T.left = nil(T.left) ? this[s.new_left](T, X) : this[s.insert](X, T.left);
} else if (compare > 0) {
T.right = nil(T.right)
? this[s.new_right](T, X)
: this[s.insert](X, T.right);
} else {
this[s.up](X, T);
return T;
}
T = skew(T);
T = split(T);
return T;
}
remove(value) {
this.root = this[s.remove](value, this.root);
}
[s.remove](X, T) {
if (nil(T)) return T;
const compare = this[s.comparator](X, T.value);
if (compare < 0) {
T.left = this[s.remove](X, T.left);
} else if (compare > 0) {
T.right = this[s.remove](X, T.right);
} else {
// nothing has changed
if (!this[s.del](X, T)) return T;
if (leaf(T)) {
if (T.next) T.next.prev = T.prev;
else this.max = T.prev;
if (T.prev) T.prev.next = T.next;
else this.min = T.next;
this.length--;
return null;
}
if (nil(T.left)) {
const L = T.next;
console.assert(successor(T) === T.next, "big");
T.right = this[s.remove](L.value, T.right);
T.value = L.value;
} else {
const L = T.prev;
console.assert(predecessor(T) === T.prev, "smol");
T.left = this[s.remove](L.value, T.left);
T.value = L.value;
}
}
T = skew(decrease_level(T));
T.right = skew(T.right);
if (!nil(T.right)) T.right.right = skew(T.right.right);
T = split(T);
T.right = split(T.right);
return T;
}
[Symbol.iterator]() {
return dancingLinks(this.min);
}
forEach(callback) {
let tree = this.min;
while (true) {
if (nil(tree)) return;
if (callback(tree.value) === false) return false; // early exit
tree = tree.next;
}
}
}
function split(T) {
// if (nil(T)) return NIL; if (nil(T.right) || nil(T.right.right)) return T;
if (nil(T) || nil(T.right) || nil(T.right.right)) return T;
if (T.level === T.right.right.level) {
const R = T.right;
T.right = R.left;
R.left = T;
R.level += 1;
return R;
}
return T;
}
function skew(T) {
// if (nil(T)) return NIL; if (nil(T.left)) return T;
if (nil(T) || nil(T.left)) return T;
const L = T.left;
if (L.level === T.level) {
T.left = L.right;
L.right = T;
return L;
}
return T;
}
function decrease_level(T) {
const r_level = nil(T.right) ? 0 : T.right.level;
const l_level = nil(T.left) ? 0 : T.left.level;
const should_be = 1 + Math.min(l_level, r_level);
if (should_be < T.level) {
T.level = should_be;
if (should_be < r_level) {
T.right.level = should_be;
}
}
return T;
}
function successor(T) {
let next = T.right;
while (!nil(next.left)) next = next.left;
return next;
}
function predecessor(T) {
let prev = T.left;
while (!nil(prev.right)) prev = prev.right;
return prev;
}
function leaf(node) {
return nil(node.left) && nil(node.right);
}
nil = function(node) {
return node === null;
}
node = value => new Node(value)
class Node {
constructor(value) {
this.level = 1;
this.value = value;
this.left = this.right = null;
this.prev = this.next = null;
}
}
import { createTree } from "@stardisblue/vertical-tree"
data = convert(
randoms.length > 10000
? {
value: "tree view is disabled for +10000 values",
left: null,
right: null
}
: tr.root
)
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.
