//<script type="text/javascript">//<script type="text/javascript">
//
// RBTree.js
//
// implementation of a red black tree

// 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;
	}
}

//</script>