Skip to content

Instantly share code, notes, and snippets.

@quoll
Created Apr 27, 2020
Embed
What would you like to do?
assert = require('assert');
const LEFT = -1;
const RIGHT = 1;
function other(side) {
return side == LEFT ? RIGHT : LEFT;
}
class Node {
constructor(transactionId, value) {
this.transactionId = transactionId;
this.value = value;
this.balance = 0;
this.children = [undefined, undefined];
}
updateChild(side, child) {
let index = side == LEFT ? 0 : 1;
this.children[index] = child;
return this;
}
setChild(side, child) {
this.updateChild(side, child);
this.balance = (this.balance === undefined) ? side : this.balance + side;
return this;
}
getChild(side) {
return this.children[side == LEFT ? 0 : 1];
}
getBalance() {
return this.balance;
}
setBalance(balance) {
this.balance = balance;
return this;
}
copyOnWrite(transactionId) {
if (this.transactionId === transactionId) {
return this;
} else {
let node = new Node(transactionId);
node.value = this.value;
node.balance = this.balance;
node.children = this.children.slice();
return node;
}
}
}
class Tree {
constructor(other = null) {
if (other === null) {
this.root = null;
this.nextTransaction = 0;
} else {
this.root = other.root;
this.nextTransaction = other.nextTransaction;
}
this.transactionRoot = null;
this.transactionId = null;
}
startTx() {
this.transactionId = this.nextTransaction++;
this.transactionRoot = this.root;
return this;
}
commitTx() {
var nextTree = new Tree(this);
this.transactionId = null;
nextTree.root = this.transactionRoot;
this.transactionRoot = null;
return nextTree;
}
rollbackTx() {
this.transactionId = null;
this.transactionRoot = null;
return this;
}
add(value) {
if (this.transactionId == null) {
throw "Update occurred outside of a transaction";
}
let node = new Node(this.transactionId, value);
if (this.transactionRoot === null) {
this.transactionRoot = node;
} else {
this.transactionRoot = this.insertNode(this.transactionRoot, node);
}
return this;
}
insertNode(node, newNode) {
let side = (newNode.value < node.value) ? LEFT : RIGHT;
node = node.copyOnWrite(this.transactionId);
if (node.getChild(side) === undefined) {
return node.setChild(side, newNode);
} else {
let childBalance = node.getChild(side).getBalance();
node.updateChild(side, this.insertNode(node.getChild(side), newNode));
// Did the child balance change from 0? Then it's deeper
if (childBalance == 0 && node.getChild(side).getBalance() != 0) {
node.setBalance(node.getBalance() + side);
}
}
if (Math.abs(node.getBalance()) == 2) {
return rebalance(node);
}
return node;
}
}
function rebalance(node) {
side = node.getBalance() < 0 ? LEFT : RIGHT;
if (side == node.getChild(side).getBalance()) {
return rebalanceSS(node, side);
} else {
return rebalanceSO(node, side);
}
}
function rebalanceSS(node, side) {
nodeS = node.getChild(side);
node.updateChild(side, nodeS.getChild(other(side)));
nodeS.updateChild(other(side), node);
node.setBalance(0);
nodeS.setBalance(0);
return nodeS;
}
function rebalanceSO(node, side) {
otherSide = other(side);
nodeS = node.getChild(side);
nodeSO = nodeS.getChild(otherSide);
node.updateChild(side, nodeSO.getChild(otherSide));
nodeS.updateChild(otherSide, nodeSO.getChild(side))
nodeSO.updateChild(otherSide, node);
nodeSO.updateChild(side, nodeS);
if (nodeSO.getBalance() == otherSide) {
node.getBalance(0);
nodeS.getBalance(side);
} else if (nodeSO.getBalance() == side) {
node.setBalance(otherSide);
nodeS.setBalance(0);
} else {
node.setBalance(0);
nodeS.setBalance(0);
}
nodeSO.setBalance(0);
return nodeSO;
}
function appendToArray(arr, node) {
if (node === undefined) {
return arr;
} else {
return appendToArray(appendToArray(arr, node.getChild(LEFT)).concat([node.value]), node.getChild(RIGHT));
}
}
function toArray(t) {
if (t.root == null) {
return [];
}
return appendToArray(appendToArray([], t.root.getChild(LEFT)).concat(t.root.value), t.root.getChild(RIGHT));
}
// user session
let digits =
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0,
2, 8, 8, 4, 1, 9, 7, 1, 6, 9, 3, 9, 9, 3, 7, 5, 1, 0, 5, 8, 2, 0, 9, 7, 4, 9, 4, 4, 5, 9, 2, 3, 0];
var pi = new Tree();
pi.startTx();
digits.slice(0, 33).forEach(d => pi.add(d));
var halfPi = pi.commitTx();
halfPi.startTx();
digits.slice(33).forEach(d => halfPi.add(d));
var fullPi = halfPi.commitTx();
assert(toArray(halfPi).join(',') === digits.slice(0, 33).sort().join(','));
assert(toArray(fullPi).join(',') === digits.sort().join(','));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment