//<script type="text/javascript">
//
// 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;
       }
}

//</script>

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.