/*  pdnmesh - a 2D finite element solver
    Copyright (C) 2001-2005 Sarod Yatawatta <sarod@users.sf.net>  
  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.
  
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
  
  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  $Id: rbt.c,v 1.11 2005/04/18 08:30:00 sarod Exp $
*/

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

/* generic RBT */

#include <stdio.h>
#include <stdlib.h> /* for malloc */
#include "types.h"

/* sentinel */
#ifndef NIL 
#define NIL &sentinel
RBT_node_type sentinel={NIL,NIL,0,rbtBLACK,0};
#endif /* NIL */

/* intialize tree */
int
RBT_init(RBT_tree *t, int (*comp_EQ) (const void *rec1, const void *rec2),
		int (*comp_LT) (const void *rec1, const void *rec2),
	        void (*print_record) (const void *rec),
					void (*free_record)(void *rec))
{
 t->root=NIL;
 t->comp_EQ=comp_EQ;
 t->comp_LT=comp_LT;
 t->print_record=print_record;
 t->free_record=free_record;

 return(RBT_STATUS_OK);
}

/* local rotation routines */
/* rotate node x to left */
static void
rotate_left(RBT_node_type *x,RBT_tree *t) 
{
 
  RBT_node_type *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 {
   t->root=y;
  }

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

/* rotate node x to right */
static void 
rotate_right(RBT_node_type *x,RBT_tree *t) {

    RBT_node_type *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 {
        t->root = y;
    }

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

/* rebalance after insertion of x */
static void 
insert_fixup(RBT_node_type *x,RBT_tree *t) {


    /* check Red-Black properties */
    while (x != t->root && x->parent->color == rbtRED) {
        /* we have a violation */
        if (x->parent == x->parent->parent->left) {
            RBT_node_type *y = x->parent->parent->right;
            if (y->color == rbtRED) {

                /* uncle is rbtRED */
                x->parent->color = rbtBLACK;
                y->color = rbtBLACK;
                x->parent->parent->color = rbtRED;
                x = x->parent->parent;
            } else {

                /* uncle is rbtBLACK */
                if (x == x->parent->right) {
                    /* make x a left child */
                    x = x->parent;
                    rotate_left(x,t);
                }

                /* recolor and rotate */
                x->parent->color = rbtBLACK;
                x->parent->parent->color = rbtRED;
                rotate_right(x->parent->parent,t);
            }
        } else {

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

                /* uncle is rbtRED */
                x->parent->color = rbtBLACK;
                y->color = rbtBLACK;
                x->parent->parent->color = rbtRED;
                x = x->parent->parent;
            } else {

                /* uncle is rbtBLACK */
                if (x == x->parent->left) {
                    x = x->parent;
                    rotate_right(x,t);
                }
                x->parent->color = rbtBLACK;
                x->parent->parent->color = rbtRED;
                rotate_left(x->parent->parent,t);
            }
        }
    }
    t->root->color = rbtBLACK;
}

/* insert data record */
int 
RBT_insert(void *rec, RBT_tree *t) {
    RBT_node_type *current, *parent, *x;

    /* find future parent */
    current = t->root;
    parent = 0;
    while (current != NIL) {
        if (t->comp_EQ(rec, current->rec)) 
            return(RBT_STATUS_KEY_FOUND);
        parent = current;
        current = t->comp_LT(rec, current->rec) ?
            current->left : current->right;
    }

    /* setup new node */
    if ((x =(RBT_node_type *)malloc(sizeof(*x))) == 0)
    {  
       fprintf(stderr,"%s: %d: no free memory",__FILE__,__LINE__);
       exit(1);
    }
    x->parent = parent;
    x->left = NIL;
    x->right = NIL;
    x->color = rbtRED;
    x->rec=rec; /* fixme - use memcpy */

    /* insert node in tree */
    if(parent) {
        if(t->comp_LT(rec, parent->rec))
            parent->left = x;
        else
            parent->right = x;
    } else {
        t->root = x;
    }

    insert_fixup(x,t);

    return(RBT_STATUS_OK);
}

/* delete fixing -local */
static void 
delete_fixup(RBT_node_type *x,RBT_tree *t) {

    while (x != t->root && x->color == rbtBLACK) {
        if (x == x->parent->left) {
            RBT_node_type *w = x->parent->right;
            if (w->color == rbtRED) {
                w->color = rbtBLACK;
                x->parent->color = rbtRED;
                rotate_left(x->parent,t);
                w = x->parent->right;
            }
            if (w->left->color == rbtBLACK && w->right->color == rbtBLACK) {
                w->color = rbtRED;
                x = x->parent;
            } else {
                if (w->right->color == rbtBLACK) {
                    w->left->color = rbtBLACK;
                    w->color = rbtRED;
                    rotate_right(w,t);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = rbtBLACK;
                w->right->color = rbtBLACK;
                rotate_left(x->parent,t);
                x = t->root;
            }
        } else {
            RBT_node_type *w = x->parent->left;
            if (w->color == rbtRED) {
                w->color = rbtBLACK;
                x->parent->color = rbtRED;
                rotate_right(x->parent,t);
                w = x->parent->left;
            }
            if (w->right->color == rbtBLACK && w->left->color == rbtBLACK) {
                w->color = rbtRED;
                x = x->parent;
            } else {
                if (w->left->color == rbtBLACK) {
                    w->right->color = rbtBLACK;
                    w->color = rbtRED;
                    rotate_left(w,t);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = rbtBLACK;
                w->left->color = rbtBLACK;
                rotate_right(x->parent,t);
                x = t->root;
            }
        }
    }
    x->color = rbtBLACK;
}

/* deletion routine */
int 
RBT_delete(void * rec,RBT_tree *t) {
    RBT_node_type *x, *y, *z;

    /* find node in tree */
    z = t->root;
    while(z != NIL) {
        if(t->comp_EQ(rec, z->rec)) 
            break;
        else
            z = t->comp_LT(rec, z->rec) ? z->left : z->right;
    }
    if (z == NIL) return(RBT_STATUS_KEY_NOT_FOUND); /* not found */

    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
        t->root = x;

    if (y != z) {
        z->rec = y->rec;
    }


    if (y->color == rbtBLACK)
        delete_fixup(x,t);

    free(y);
    return(RBT_STATUS_OK);
}

/* search RBT for the record */
/* rec will point to the actual record if found */
void *
RBT_find(void *rec, RBT_tree *t) 
{

    RBT_node_type *current = t->root;
    while(current != NIL) {
        if(t->comp_EQ(rec, current->rec)) {
            /*rec = current->rec;
            return(RBT_STATUS_KEY_FOUND); */
						return((void*)current->rec);
        } else {
            current = t->comp_LT(rec, current->rec) ?
                current->left : current->right;
        }
    }
    /*return(RBT_STATUS_KEY_NOT_FOUND); */
		return(0);
}

/* local visit */
static void 
visit_node(RBT_node_type *n,RBT_tree *t)
{
  if ( n != NIL ){
    visit_node(n->left,t);
    t->print_record(n->rec);
    visit_node(n->right,t);
  }
}

/* traverse tree */
void
RBT_traverse(RBT_tree *t) 
{
 visit_node(t->root,t);
}


/* local free */
static void
free_local(RBT_node_type *n,RBT_tree *t)
{
 if ( n!=NIL ) {
		free_local(n->left,t);
		free_local(n->right,t);
		t->free_record(n->rec);
	  free(n);
    n=NIL;
 }
}
/* free memory used by a  tree */
/* makes t=NIL */
void
RBT_free(RBT_tree *t)
{
 free_local(t->root,t);
 t->root=NIL;
}