479 lines
15 KiB
JavaScript
479 lines
15 KiB
JavaScript
|
"use strict";
|
||
|
|
(function rbtree_js() {
|
||
|
|
|
||
|
|
var moduleName = "lib/bintrees/index";
|
||
|
|
|
||
|
|
var defineArray = [];
|
||
|
|
|
||
|
|
define(moduleName, defineArray, function rbtree_module() {
|
||
|
|
var require = function(name) {
|
||
|
|
var fn = require.m[name];
|
||
|
|
if (fn.mod) {
|
||
|
|
return fn.mod.exports;
|
||
|
|
}
|
||
|
|
|
||
|
|
var mod = fn.mod = { exports: {} };
|
||
|
|
fn(mod, mod.exports);
|
||
|
|
return mod.exports;
|
||
|
|
};
|
||
|
|
|
||
|
|
require.m = {};
|
||
|
|
require.m['./treebase'] = function(module, exports) {
|
||
|
|
|
||
|
|
function TreeBase() {}
|
||
|
|
|
||
|
|
// removes all nodes from the tree
|
||
|
|
TreeBase.prototype.clear = function() {
|
||
|
|
this._root = null;
|
||
|
|
this.size = 0;
|
||
|
|
};
|
||
|
|
|
||
|
|
// returns node data if found, null otherwise
|
||
|
|
TreeBase.prototype.find = function(data) {
|
||
|
|
var res = this._root;
|
||
|
|
|
||
|
|
while(res !== null) {
|
||
|
|
var c = this._comparator(data, res.data);
|
||
|
|
if(c === 0) {
|
||
|
|
return res.data;
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
res = res.get_child(c > 0);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return null;
|
||
|
|
};
|
||
|
|
|
||
|
|
// returns iterator to node if found, null otherwise
|
||
|
|
TreeBase.prototype.findIter = function(data) {
|
||
|
|
var res = this._root;
|
||
|
|
var iter = this.iterator();
|
||
|
|
|
||
|
|
while(res !== null) {
|
||
|
|
var c = this._comparator(data, res.data);
|
||
|
|
if(c === 0) {
|
||
|
|
iter._cursor = res;
|
||
|
|
return iter;
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
iter._ancestors.push(res);
|
||
|
|
res = res.get_child(c > 0);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return null;
|
||
|
|
};
|
||
|
|
|
||
|
|
// Returns an iterator to the tree node at or immediately after the item
|
||
|
|
TreeBase.prototype.lowerBound = function(item) {
|
||
|
|
var cur = this._root;
|
||
|
|
var iter = this.iterator();
|
||
|
|
var cmp = this._comparator;
|
||
|
|
|
||
|
|
while(cur !== null) {
|
||
|
|
var c = cmp(item, cur.data);
|
||
|
|
if(c === 0) {
|
||
|
|
iter._cursor = cur;
|
||
|
|
return iter;
|
||
|
|
}
|
||
|
|
iter._ancestors.push(cur);
|
||
|
|
cur = cur.get_child(c > 0);
|
||
|
|
}
|
||
|
|
|
||
|
|
for(var i=iter._ancestors.length - 1; i >= 0; --i) {
|
||
|
|
cur = iter._ancestors[i];
|
||
|
|
if(cmp(item, cur.data) < 0) {
|
||
|
|
iter._cursor = cur;
|
||
|
|
iter._ancestors.length = i;
|
||
|
|
return iter;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
iter._ancestors.length = 0;
|
||
|
|
return iter;
|
||
|
|
};
|
||
|
|
|
||
|
|
// Returns an iterator to the tree node immediately after the item
|
||
|
|
TreeBase.prototype.upperBound = function(item) {
|
||
|
|
var iter = this.lowerBound(item);
|
||
|
|
var cmp = this._comparator;
|
||
|
|
|
||
|
|
while(iter.data() !== null && cmp(iter.data(), item) === 0) {
|
||
|
|
iter.next();
|
||
|
|
}
|
||
|
|
|
||
|
|
return iter;
|
||
|
|
};
|
||
|
|
|
||
|
|
// returns null if tree is empty
|
||
|
|
TreeBase.prototype.min = function() {
|
||
|
|
var res = this._root;
|
||
|
|
if(res === null) {
|
||
|
|
return null;
|
||
|
|
}
|
||
|
|
|
||
|
|
while(res.left !== null) {
|
||
|
|
res = res.left;
|
||
|
|
}
|
||
|
|
|
||
|
|
return res.data;
|
||
|
|
};
|
||
|
|
|
||
|
|
// returns null if tree is empty
|
||
|
|
TreeBase.prototype.max = function() {
|
||
|
|
var res = this._root;
|
||
|
|
if(res === null) {
|
||
|
|
return null;
|
||
|
|
}
|
||
|
|
|
||
|
|
while(res.right !== null) {
|
||
|
|
res = res.right;
|
||
|
|
}
|
||
|
|
|
||
|
|
return res.data;
|
||
|
|
};
|
||
|
|
|
||
|
|
// returns a null iterator
|
||
|
|
// call next() or prev() to point to an element
|
||
|
|
TreeBase.prototype.iterator = function() {
|
||
|
|
return new Iterator(this);
|
||
|
|
};
|
||
|
|
|
||
|
|
// calls cb on each node's data, in order
|
||
|
|
TreeBase.prototype.each = function(cb) {
|
||
|
|
var it=this.iterator(), data;
|
||
|
|
while((data = it.next()) !== null) {
|
||
|
|
cb(data);
|
||
|
|
}
|
||
|
|
};
|
||
|
|
|
||
|
|
// calls cb on each node's data, in reverse order
|
||
|
|
TreeBase.prototype.reach = function(cb) {
|
||
|
|
var it=this.iterator(), data;
|
||
|
|
while((data = it.prev()) !== null) {
|
||
|
|
cb(data);
|
||
|
|
}
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
function Iterator(tree) {
|
||
|
|
this._tree = tree;
|
||
|
|
this._ancestors = [];
|
||
|
|
this._cursor = null;
|
||
|
|
}
|
||
|
|
|
||
|
|
Iterator.prototype.data = function() {
|
||
|
|
return this._cursor !== null ? this._cursor.data : null;
|
||
|
|
};
|
||
|
|
|
||
|
|
// if null-iterator, returns first node
|
||
|
|
// otherwise, returns next node
|
||
|
|
Iterator.prototype.next = function() {
|
||
|
|
if(this._cursor === null) {
|
||
|
|
var root = this._tree._root;
|
||
|
|
if(root !== null) {
|
||
|
|
this._minNode(root);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
if(this._cursor.right === null) {
|
||
|
|
// no greater node in subtree, go up to parent
|
||
|
|
// if coming from a right child, continue up the stack
|
||
|
|
var save;
|
||
|
|
do {
|
||
|
|
save = this._cursor;
|
||
|
|
if(this._ancestors.length) {
|
||
|
|
this._cursor = this._ancestors.pop();
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
this._cursor = null;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
} while(this._cursor.right === save);
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
// get the next node from the subtree
|
||
|
|
this._ancestors.push(this._cursor);
|
||
|
|
this._minNode(this._cursor.right);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return this._cursor !== null ? this._cursor.data : null;
|
||
|
|
};
|
||
|
|
|
||
|
|
// if null-iterator, returns last node
|
||
|
|
// otherwise, returns previous node
|
||
|
|
Iterator.prototype.prev = function() {
|
||
|
|
if(this._cursor === null) {
|
||
|
|
var root = this._tree._root;
|
||
|
|
if(root !== null) {
|
||
|
|
this._maxNode(root);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
if(this._cursor.left === null) {
|
||
|
|
var save;
|
||
|
|
do {
|
||
|
|
save = this._cursor;
|
||
|
|
if(this._ancestors.length) {
|
||
|
|
this._cursor = this._ancestors.pop();
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
this._cursor = null;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
} while(this._cursor.left === save);
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
this._ancestors.push(this._cursor);
|
||
|
|
this._maxNode(this._cursor.left);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return this._cursor !== null ? this._cursor.data : null;
|
||
|
|
};
|
||
|
|
|
||
|
|
Iterator.prototype._minNode = function(start) {
|
||
|
|
while(start.left !== null) {
|
||
|
|
this._ancestors.push(start);
|
||
|
|
start = start.left;
|
||
|
|
}
|
||
|
|
this._cursor = start;
|
||
|
|
};
|
||
|
|
|
||
|
|
Iterator.prototype._maxNode = function(start) {
|
||
|
|
while(start.right !== null) {
|
||
|
|
this._ancestors.push(start);
|
||
|
|
start = start.right;
|
||
|
|
}
|
||
|
|
this._cursor = start;
|
||
|
|
};
|
||
|
|
|
||
|
|
module.exports = TreeBase;
|
||
|
|
|
||
|
|
};
|
||
|
|
require.m['__main__'] = function(module, exports) {
|
||
|
|
|
||
|
|
var TreeBase = require('./treebase');
|
||
|
|
|
||
|
|
function Node(data) {
|
||
|
|
this.data = data;
|
||
|
|
this.left = null;
|
||
|
|
this.right = null;
|
||
|
|
this.red = true;
|
||
|
|
}
|
||
|
|
|
||
|
|
Node.prototype.get_child = function(dir) {
|
||
|
|
return dir ? this.right : this.left;
|
||
|
|
};
|
||
|
|
|
||
|
|
Node.prototype.set_child = function(dir, val) {
|
||
|
|
if(dir) {
|
||
|
|
this.right = val;
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
this.left = val;
|
||
|
|
}
|
||
|
|
};
|
||
|
|
|
||
|
|
function RBTree(comparator) {
|
||
|
|
this._root = null;
|
||
|
|
this._comparator = comparator;
|
||
|
|
this.size = 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
RBTree.prototype = new TreeBase();
|
||
|
|
|
||
|
|
// returns true if inserted, false if duplicate
|
||
|
|
RBTree.prototype.insert = function(data) {
|
||
|
|
var ret = false;
|
||
|
|
|
||
|
|
if(this._root === null) {
|
||
|
|
// empty tree
|
||
|
|
this._root = new Node(data);
|
||
|
|
ret = true;
|
||
|
|
this.size++;
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
var head = new Node(undefined); // fake tree root
|
||
|
|
|
||
|
|
var dir = 0;
|
||
|
|
var last = 0;
|
||
|
|
|
||
|
|
// setup
|
||
|
|
var gp = null; // grandparent
|
||
|
|
var ggp = head; // grand-grand-parent
|
||
|
|
var p = null; // parent
|
||
|
|
var node = this._root;
|
||
|
|
ggp.right = this._root;
|
||
|
|
|
||
|
|
// search down
|
||
|
|
while(true) {
|
||
|
|
if(node === null) {
|
||
|
|
// insert new node at the bottom
|
||
|
|
node = new Node(data);
|
||
|
|
p.set_child(dir, node);
|
||
|
|
ret = true;
|
||
|
|
this.size++;
|
||
|
|
}
|
||
|
|
else if(is_red(node.left) && is_red(node.right)) {
|
||
|
|
// color flip
|
||
|
|
node.red = true;
|
||
|
|
node.left.red = false;
|
||
|
|
node.right.red = false;
|
||
|
|
}
|
||
|
|
|
||
|
|
// fix red violation
|
||
|
|
if(is_red(node) && is_red(p)) {
|
||
|
|
var dir2 = ggp.right === gp;
|
||
|
|
|
||
|
|
if(node === p.get_child(last)) {
|
||
|
|
ggp.set_child(dir2, single_rotate(gp, !last));
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
ggp.set_child(dir2, double_rotate(gp, !last));
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
var cmp = this._comparator(node.data, data);
|
||
|
|
|
||
|
|
// stop if found
|
||
|
|
if(cmp === 0) {
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
|
||
|
|
last = dir;
|
||
|
|
dir = cmp < 0;
|
||
|
|
|
||
|
|
// update helpers
|
||
|
|
if(gp !== null) {
|
||
|
|
ggp = gp;
|
||
|
|
}
|
||
|
|
gp = p;
|
||
|
|
p = node;
|
||
|
|
node = node.get_child(dir);
|
||
|
|
}
|
||
|
|
|
||
|
|
// update root
|
||
|
|
this._root = head.right;
|
||
|
|
}
|
||
|
|
|
||
|
|
// make root black
|
||
|
|
this._root.red = false;
|
||
|
|
|
||
|
|
return ret;
|
||
|
|
};
|
||
|
|
|
||
|
|
// returns true if removed, false if not found
|
||
|
|
RBTree.prototype.remove = function(data) {
|
||
|
|
if(this._root === null) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
var head = new Node(undefined); // fake tree root
|
||
|
|
var node = head;
|
||
|
|
node.right = this._root;
|
||
|
|
var p = null; // parent
|
||
|
|
var gp = null; // grand parent
|
||
|
|
var found = null; // found item
|
||
|
|
var dir = 1;
|
||
|
|
|
||
|
|
while(node.get_child(dir) !== null) {
|
||
|
|
var last = dir;
|
||
|
|
|
||
|
|
// update helpers
|
||
|
|
gp = p;
|
||
|
|
p = node;
|
||
|
|
node = node.get_child(dir);
|
||
|
|
|
||
|
|
var cmp = this._comparator(data, node.data);
|
||
|
|
|
||
|
|
dir = cmp > 0;
|
||
|
|
|
||
|
|
// save found node
|
||
|
|
if(cmp === 0) {
|
||
|
|
found = node;
|
||
|
|
}
|
||
|
|
|
||
|
|
// push the red node down
|
||
|
|
if(!is_red(node) && !is_red(node.get_child(dir))) {
|
||
|
|
if(is_red(node.get_child(!dir))) {
|
||
|
|
var sr = single_rotate(node, dir);
|
||
|
|
p.set_child(last, sr);
|
||
|
|
p = sr;
|
||
|
|
}
|
||
|
|
else if(!is_red(node.get_child(!dir))) {
|
||
|
|
var sibling = p.get_child(!last);
|
||
|
|
if(sibling !== null) {
|
||
|
|
if(!is_red(sibling.get_child(!last)) && !is_red(sibling.get_child(last))) {
|
||
|
|
// color flip
|
||
|
|
p.red = false;
|
||
|
|
sibling.red = true;
|
||
|
|
node.red = true;
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
var dir2 = gp.right === p;
|
||
|
|
|
||
|
|
if(is_red(sibling.get_child(last))) {
|
||
|
|
gp.set_child(dir2, double_rotate(p, last));
|
||
|
|
}
|
||
|
|
else if(is_red(sibling.get_child(!last))) {
|
||
|
|
gp.set_child(dir2, single_rotate(p, last));
|
||
|
|
}
|
||
|
|
|
||
|
|
// ensure correct coloring
|
||
|
|
var gpc = gp.get_child(dir2);
|
||
|
|
gpc.red = true;
|
||
|
|
node.red = true;
|
||
|
|
gpc.left.red = false;
|
||
|
|
gpc.right.red = false;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// replace and remove if found
|
||
|
|
if(found !== null) {
|
||
|
|
found.data = node.data;
|
||
|
|
p.set_child(p.right === node, node.get_child(node.left === null));
|
||
|
|
this.size--;
|
||
|
|
}
|
||
|
|
|
||
|
|
// update root and make it black
|
||
|
|
this._root = head.right;
|
||
|
|
if(this._root !== null) {
|
||
|
|
this._root.red = false;
|
||
|
|
}
|
||
|
|
|
||
|
|
return found !== null;
|
||
|
|
};
|
||
|
|
|
||
|
|
function is_red(node) {
|
||
|
|
return node !== null && node.red;
|
||
|
|
}
|
||
|
|
|
||
|
|
function single_rotate(root, dir) {
|
||
|
|
var save = root.get_child(!dir);
|
||
|
|
|
||
|
|
root.set_child(!dir, save.get_child(dir));
|
||
|
|
save.set_child(dir, root);
|
||
|
|
|
||
|
|
root.red = true;
|
||
|
|
save.red = false;
|
||
|
|
|
||
|
|
return save;
|
||
|
|
}
|
||
|
|
|
||
|
|
function double_rotate(root, dir) {
|
||
|
|
root.set_child(!dir, single_rotate(root.get_child(!dir), !dir));
|
||
|
|
return single_rotate(root, dir);
|
||
|
|
}
|
||
|
|
|
||
|
|
module.exports = RBTree;
|
||
|
|
};
|
||
|
|
return {
|
||
|
|
RBTree: require('__main__')
|
||
|
|
};
|
||
|
|
});
|
||
|
|
})();
|