GOPHERSPACE.DE - P H O X Y
gophering on sdf.org
//
//
// RBTree.js
// implementation of a red black tree
//
// Free Software Licence:
// This software is intended for free use for personal and comercial use.
// No Warranty:
// Because this software is licenced free of charge, there is no warranty
// expressed or implied for any code contained within this file.
// Guyon Roche



// logical xor of b1 and b2
function xor(b1,b2)
{
return (b1 && !b2) || (!b1 && b2);
}

function RBTree(less)
{
this.less = less;
this.clear();
}
RBTree.prototype.clear = function()
{
this.root = null;
this.nSize = 0;

// head and tail are sentinel nodes not stored in the tree
this.head = {item:"head",prev:null,bSentinel:true};
this.tail = {item:"tail",tail:null,bSentinel:true};
this.head.next = this.tail;
this.tail.prev = this.head;
}
RBTree.prototype.insert = function(value,hint)
{
var node = new RBTreeNode(value,this);

// account for size
if ( !this.nSize++ )
{
this.root = node;
node.listInsert(this.head,this.tail);
node.parent = null;
return node;
}

var pos = this.root;

// if hint exists, assume upper bound - 1
if ( hint && hint.bSentinel )
{
if ( hint === this.head ) hint = hint.next;
else if ( hint === this.tail ) hint = hint.prev;
else hint = null;
}
if ( hint && (hint.tree === this) ) pos = hint;

pos.insert(node, this.less);

node.balance();

// make root node black
this.root.bBlack = 1;

return node;
}

RBTree.prototype.remove = function(node)
{
// remove the node from the tree returning the node that follows.

// protect and serve
if ( node.tree !== this ) return this.tail;

// account for size
if ( --this.nSize == 0 )
{
this.root = null;
node.listRemove();
return this.tail;
}

var next = node.next;

// case 1: node has two children or is root
if ( !node.parent || (node.left.bNode && node.right.bNode) )
{
// find inorder predecessor (or successor) and swap values
// after deletion, value order will be preserved
var sub = node.prev;
if ( !sub )
{
sub = node.next;
next = node;
}
node.item = sub.item;
node = sub;
}

// node now has at most one child node

// remove node from linked list
node.listRemove();

// p is parent of node
var p = node.parent;

var bLeft = (node === p.left);

// c is child of node
var c = node.left.bNode ? node.left : node.right;

// move c into place
c.parent = node.parent;
if ( bLeft ) p.left = c; else p.right = c;

// node is red
if ( !node.bBlack )
{
// this is easy, colour c black and return
c.bBlack = 1;
return next;
}

// node is black, add to c and fix
c.bBlack++;

if ( c.bBlack > 1 ) c.fix();

return next;
}

//Returns an iterator to the first element in a set that with a key that is
//greater than a specified key.
RBTree.prototype.upper_bound = function(value)
{
if ( !this.root ) return this.tail;
return this.root.upper_bound(value,this.less);
}

//Returns an iterator to the first element in a map that with a key value that is 
//equal to or greater than that of a specified key.
RBTree.prototype.lower_bound = function(value)
{
if ( !this.root ) return this.tail;
else return this.root.lower_bound(value, this.less);
}


function RBTreeNode(value,tree)
{
this.item = value;
this.tree = tree;
this.bBlack = 0; // default
this.bNode = true;

// add left and right sentinel nodes
this.left = {parent:this,bBlack:1,bLeft:true,fix:RBTreeNode.prototype.fix};
this.right = {parent:this,bBlack:1,bLeft:false,fix:RBTreeNode.prototype.fix};
}
RBTreeNode.prototype.rightmost = function()
{
if ( this.right.bNode ) return this.right.rightmost();
else return this;
}
RBTreeNode.prototype.leftmost = function()
{
if ( this.left.bNode ) return this.left.leftmost();
else return this;
}
RBTreeNode.prototype.listInsert = function(prev,next)
{
this.prev = prev;
prev.next = this;

this.next = next;
next.prev = this;
}
RBTreeNode.prototype.listRemove = function()
{
this.next.prev = this.prev;
this.prev.next = this.next;
}
RBTreeNode.prototype.insertChild = function(prev,next,node)
{
node.parent = this;
node.listInsert(prev,next);
}
RBTreeNode.prototype.insert = function(node, less)
{
// simple binary insertion
if ( less.fn(node.item,this.item) )
{
if ( this.left.bNode ) this.left.insert(node,less);
else this.insertChild(this.prev,this,this.left = node);
}
else
{
if ( this.right.bNode ) this.right.insert(node,less);
else this.insertChild(this,this.next,this.right = node);
}
}
RBTreeNode.prototype.balance = function()
{
// walk up the tree preserving the red-black rules

// p is parent
var p = this.parent;

// case 1: this is root node or parent is black
if ( !p || (p.bBlack != 0) ) return;

// g is grand parent
var g = p.parent;

// case 1b: p is root node
if ( !g ) return;

// record whether we are the left child
var bLeft = (this === p.left);

// and whether parent is a left child
var bPLeft = (p === g.left);

// u is uncle
var u = (bPLeft ? g.right : g.left);

// case 2: parent is red, uncle is black
if ( u.bBlack != 0 )
{
if ( xor(bLeft,bPLeft) )
{
// case 2a: parent is different handed to this
this.rotate();
this.rotate();
}
else
{
// case 2b: parent is same handed as this
p.rotate();
}
return;
}

// case 3: parent is red, uncle is red
p.bBlack = 1;
u.bBlack = 1;
g.bBlack = 0;
g.balance();
}

RBTreeNode.prototype.rotate = function()
{
// p is parent
var p = this.parent;

// if this is root node, we can't rotate
if ( !p ) return;

// g is grand parent
var g = p.parent;

var bLeft = (this === p.left);

if ( bLeft )
{
p.left = this.right;
this.right.parent = p;
this.right = p;
}
else
{
p.right= this.left;
this.left.parent = p;
this.left = p;
}

// set parents
p.parent = this;
this.parent = g;
if ( g ) { if ( g.left === p ) g.left = this; else g.right = this; }
else this.tree.root = this;

// swap colours
var bBlack = p.bBlack;
p.bBlack = this.bBlack;
this.bBlack = bBlack;
}
RBTreeNode.prototype.fix = function()
{
// fix any colour inconsistancy

// p is parent
var p = this.parent;

if ( !p )
{
this.bBlack = 1;
return;
}

// s is sibling
var s = (this === p.left) ? p.right : p.left;

// case 1: black sibling with red child
if ( s.bBlack && s.bNode )
{
var n = null;
if ( !s.left.bBlack ) n = s.left;
else if ( !s.right.bBlack ) n = s.right;
if ( n )
{
// restructure
this.bBlack = 1;
n.bBlack = 1;
if ( !xor((s===p.left),(n===s.left)) )
{
// s and n same handed
s.rotate();
}
else
{
// s and n different handed
n.rotate();
n.rotate();
}
return;
}
}

// case 2: black sibling without (red) children
if ( s.bBlack )
{
// recolour
this.bBlack = 1;
s.bBlack = 0;
if ( ++p.bBlack > 1 ) p.fix();
return;
}

// case 3: red sibling --> adjustment
s.rotate();
this.fix();
}

//Returns node of the first element in a set that with a key that is
//greater than a specified key.
RBTreeNode.prototype.upper_bound = function(value,less)
{
if ( !less.fn(value,this.item) )
{
// value >= this.item
if ( this.right.bNode ) return this.right.upper_bound(value,less);
else return this.next;
}
else
{
// value < this.item
if ( this.left.bNode ) return this.left.upper_bound(value,less);
else return this;
}
}

//Returns node of the first element in a map that with a key value that is 
//equal to or greater than that of a specified key.
RBTreeNode.prototype.lower_bound = function(value,less)
{
if ( less.fn(this.item,value) )
{
// value > this.item
if ( this.right.bNode ) return this.right.lower_bound(value,less);
else return this.next;
}
else
{
// value <= this.item
if ( this.left.bNode ) return this.left.lower_bound(value,less);
else return this;
}
}

//