#include "copyright.h"
/****************************************************************** 
 *
 * rbclass.c --
 *
 *    Interval red-black tree. This is an augmented red-black tree
 *    which stores an "interval" in each node, and provides
 *    additional operations to find an overlapping interval and
 *    to "consolidate" the tree, i.e. to merge nodes with over-
 *    lapping intervals so that all intervals are disjoint.
 *
 *
 * Author : Dan Gunter
 *          ..with heavy use of the pseudocode provided in
 *          "Introduction to Algorithms" by Cormen, Leiserson, and
 *          Rivest.
 * Created: 23 Aug 1998
 *
 * $Author: mstoufer $
 * $Source: /home/g2/src/projects/NetLogger/src/nlv/rbclass.c,v $
 * $RCSfile: rbclass.c,v $
 * $Revision: 1.1.1.1 $
 * $Locker:  $
 * $Date: 2000/12/05 19:52:33 $
 *
 ****************************************************************** 
 */
static char rcsid[] = "$Id: rbclass.c,v 1.1.1.1 2000/12/05 19:52:33 mstoufer Exp $";

#include "rbclass.h"

/*========= DATA =====================================================*/


#define T Nlv_rb
struct Nlv_rb {
  Node *root;    /* root of Red-Black tree */
};
Node sentinel = { NIL, NIL, 0, BLACK, 0}; /* Null node (read-only) */

#define FILE_ERR_CODE 1500

/*========= FUNCTIONS ================================================*/

#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
#define compLT(a,b) (a.low < b.low)
#define compEQ(a,b) (a.low == b.low)
#define compIN(a,b) (a.low >= b.low && a.low <= b.high)
#define setMax(x)    do { if ( x != NIL && x->right != NIL ) \
  x->data.max = max(x->data.max,x->right->data.max); } while(0);
#define overlap(d1,d2) (!(d1.high < d2.low || d1.low > d2.high))
#define inSubtree(x,d) ((x)->data.max >= (d).low)

void  rotateLeft (T, Node *x);
void  rotateRight(T, Node *x);
void  insertFixup(T, Node *x);
void  deleteFixup(T, Node *x);
Node *findOverlap(T, Nlv_Interval ival);
Node *consolidateNode( T, Node *x, Nlv_Interval d );


/*
 *----------------------------------------------------------------------
 *
 * New -- Allocate new object.
 *
 * Calls:
 *
 * Algorithm:
 *
 *----------------------------------------------------------------------
 */

T Nlv_rbNew()
{
  T this = (T)malloc( sizeof (struct Nlv_rb));
  this->root     = NIL;
  return this;
}


/*
 *----------------------------------------------------------------------
 *
 * rotateLeft -- Rotate node 'x' to the left.
 *
 * Calls:
 *
 * Algorithm:
 *
 *----------------------------------------------------------------------
 */

void rotateLeft(T this, Node *x) 
{
    Node *y = x->right;

    /* establish x->right link */
    x->right = y->left;
    if (y->left != NIL)
      y->left->parent = x;

    /* establish y->parent link */
    if (y != NIL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    } else {
        this->root = y;
    }

    /* link x and y */
    y->left = x;
    if (x != NIL) x->parent = y;

    /* maintain 'max' information for smaller
     * subtree rooted at x
     */
    setMax( x );
}


/*
 *----------------------------------------------------------------------
 *
 * rotateRight -- Rotate node 'x' to the right.
 *
 * Calls:
 *
 * Algorithm:
 *
 *----------------------------------------------------------------------
 */

void rotateRight(T this, Node *x) 
{
    Node *y = x->left;

    /* establish x->left link */
    x->left = y->right;
    if (y->right != NIL) y->right->parent = x;

    /* establish y->parent link */
    if (y != NIL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;
    } else {
        this->root = y;
    }

    /* link x and y */
    y->right = x;
    if (x != NIL) x->parent = y;

    /* maintain 'max' information for smaller
     * subtree rooted at y
     */
    setMax( y );
}


/*
 *----------------------------------------------------------------------
 *
 * insertFixup -- Maintain RB-tree balance after inserting a node.
 *
 * Calls:
 *
 * Algorithm:
 *
 *----------------------------------------------------------------------
 */

void insertFixup(T this, Node *x) 
{
    /* check Red-Black properties */
    while (x != this->root && x->parent->color == RED) {
        /* we have a violation */
        if (x->parent == x->parent->parent->left) {
            Node *y = x->parent->parent->right;
            if (y->color == RED) {

                /* uncle is RED */
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                /* uncle is BLACK */
                if (x == x->parent->right) {
                    /* make x a left child */
                    x = x->parent;
                    rotateLeft(this, x);
                }

                /* recolor and rotate */
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateRight(this, x->parent->parent);
            }
        } else {

            /* mirror image of above code */
            Node *y = x->parent->parent->left;
            if (y->color == RED) {

                /* uncle is RED */
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                /* uncle is BLACK */
                if (x == x->parent->left) {
                    x = x->parent;
                    rotateRight(this, x);
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateLeft(this, x->parent->parent);
            }
        }
    }
    this->root->color = BLACK;
}


/*
 *----------------------------------------------------------------------
 *
 * insertNode -- Allocate node for data and insert into tree.
 *
 * Calls:
 *
 * Algorithm: If the node overlaps with an existing node, it should
 *            be merged with that node.
 *            Otherwise, find the proper spot and insert it.
 *
 *----------------------------------------------------------------------
 */

Node *Nlv_rbInsertNode(T this, Nlv_Interval data) 
{
  Node *current, *prev, *parent, *x;
  
  /* Does new data overlap current?
   * If so, consolidate.
   */
  if ( (x = findOverlap(this, data)) != NIL ) {
    x = consolidateNode( this, x, data );
    return( x );
  }

  /* find where node belongs */
  current = this->root;
  parent = 0;
  while (current != NIL) {
    parent = current;
    current = compLT(data, current->data) ?
      current->left : current->right;
  }
  
  /* setup new node */
  if ((x = malloc (sizeof(*x))) == 0) {
    printf ("insufficient memory (insertNode)\n");
    exit(1);
  }
  x->data = data;
  x->parent = parent;
  x->left = NIL;
  x->right = NIL;
  x->color = RED;
  
  /* insert node in tree */
  if(parent) {
    if(compLT(data, parent->data))
      parent->left = x;
    else {
      parent->right = x;
      /* Set maximum as long as we are in a right child */
      for ( prev = x, current = parent; current && prev == current->right; 
	    prev = current, current = current->parent )
	current->data.max = max( current->data.max, prev->data.max );
    }
  } else {
    this->root = x;
  }
  
  insertFixup(this, x);
  return(x);
}


/*
 *----------------------------------------------------------------------
 *
 * deleteFixup -- Maintain RB-tree balance after deleting node 'x'.
 *
 * Calls:
 *
 * Algorithm:
 *
 *----------------------------------------------------------------------
 */

void deleteFixup(T this, Node *x) 
{
  while (x != this->root && x->color == BLACK) {
    if (x == x->parent->left) {
      Node *w = x->parent->right;
      if (w->color == RED) {
	w->color = BLACK;
	x->parent->color = RED;
	rotateLeft (this, x->parent);
	w = x->parent->right;
      }
      if (w->left->color == BLACK && w->right->color == BLACK) {
	w->color = RED;
	x = x->parent;
      } else {
	if (w->right->color == BLACK) {
	  w->left->color = BLACK;
	  w->color = RED;
	  rotateRight (this, w);
	  w = x->parent->right;
	}
	w->color = x->parent->color;
	x->parent->color = BLACK;
	w->right->color = BLACK;
	rotateLeft (this, x->parent);
	x = this->root;
      }
    } else {
      Node *w = x->parent->left;
      if (w->color == RED) {
	w->color = BLACK;
	x->parent->color = RED;
	rotateRight (this, x->parent);
	w = x->parent->left;
      }
      if (w->right->color == BLACK && w->left->color == BLACK) {
	w->color = RED;
	x = x->parent;
      } else {
	if (w->left->color == BLACK) {
	  w->right->color = BLACK;
	  w->color = RED;
	  rotateLeft (this, w);
	  w = x->parent->left;
	}
	w->color = x->parent->color;
	x->parent->color = BLACK;
	w->left->color = BLACK;
	rotateRight (this, x->parent);
	x = this->root;
      }
    }
  }
  x->color = BLACK;
}


/*
 *----------------------------------------------------------------------
 *
 * deleteNode -- Delete node 'z' from a tree.
 *
 * Calls:
 *
 * Algorithm:
 *
 *----------------------------------------------------------------------
 */

void Nlv_rbDeleteNode(T this, Node *z) 
{
  Node *x, *y;

  if (!z || z == NIL) return;

  if (z->left == NIL || z->right == NIL) {
    /* y has a NIL node as a child */
    y = z;
  } else {
    /* find tree successor with a NIL node as a child */
    y = z->right;
    while (y->left != NIL) y = y->left;
  }
  
  /* x is y's only child */
  if (y->left != NIL)
    x = y->left;
  else
    x = y->right;
  
  /* remove y from the parent chain */
  x->parent = y->parent;
  if (y->parent)
    if (y == y->parent->left)
      y->parent->left = x;
    else
      y->parent->right = x;
  else
    this->root = x;
  
  if (y != z) z->data = y->data;
  
  if (y->color == BLACK)
    deleteFixup (this, x);
  
  free (y);
}


/*
 *----------------------------------------------------------------------
 *
 * findNode -- Find a node whose interval contains the low endpoint
 *             of data's interval.
 *
 * Calls: compIN, compLT
 *
 * Algorithm:
 *
 *----------------------------------------------------------------------
 */

Node *Nlv_rbFindNode(T this, Nlv_Interval data) 
{
  Node *current = this->root;

  while(current != NIL) {
    if (compIN(data, current->data))
      return (current);
    else
      current = compLT (data, current->data) ?
	current->left : current->right;
  }
  return(0);
}


/*
 *----------------------------------------------------------------------
 *
 * findOverlap -- Find an interval which overlaps with the
 *                'ival' argument. Return a pointer to this node,
 *                 or NIL.
 *
 * Calls: overlap, inSubtree
 *
 * Algorithm:
 *
 *----------------------------------------------------------------------
 */

Node *findOverlap( T this, Nlv_Interval ival)
{
  Node *x = this->root;

  while ( x != NIL && !overlap(x->data, ival) ) {
    if ( x->left != NIL && inSubtree(x->left, ival) )
      x = x->left;
    else
      x = x->right;
  }
  return x;
}


/*
 *----------------------------------------------------------------------
 *
 * consolidateNode -- Expand the range of node 'x' with the
 *                    data from 'd'. Then delete and reinsert the
 *                    node into the tree (which may cause another
 *                    call to "consolidate").
 *
 * Calls: expandInterval, deleteNode, insertNode
 *
 * Algorithm:
 *
 *----------------------------------------------------------------------
 */

Node *consolidateNode( T this, Node *x, Nlv_Interval d )
{
  Nlv_Interval copy;

  copy = x->data;
  Nlv_rbDeleteNode( this, x );
  copy.low  = min( d.low, copy.low );
  copy.high = max( d.high, copy.high );
  copy.max  = copy.high;
  return Nlv_rbInsertNode( this, copy );
}

/** Debugging hook **/

void Nlv_rbDumpInorder( T this, FILE *output )
{
  void inorder( Node *x, FILE *output);

  inorder(this->root,output);
}
void inorder( Node *x, FILE *output )
{
  if ( x == NIL )
    return;
  inorder( x->left, output );
  fprintf( output, "[%lf .. %lf]\n", x->data.low, x->data.high );
  inorder( x->right, output );
}
