#include <stdlib.h>
#include <stdio.h>

extern FILE *myLog;

#include "bintree.h"

#define RED   0
#define BLACK 1

/* node datastructure for the BinTree, should not be used directly */
typedef struct t_btnode {
   struct t_btnode *parent;   /* parent of the current node                  */
   struct t_btnode *child[2]; /* children of the current node, 0 will be     **
                              **  less than the current node based on the    **
                              **  icomp function, and 1 will be greater than **
                              **  the current node based on the icomp        **
                              **  function                                   */
   int color;                 /* "color" of the node (for red-black          **
                              **  implementation)                            */
   void *val;                 /* the value that the node holds, also used    **
                              **  for insertion, deletion, and searching     */
} bt_Node;

/* BinTree data structure, members should never be accessed directly */
struct bintree_t {
   const void *curval;                     /* the last value searched for    */
   bt_Node *cur;                           /* the last node matching the     **
                                           **  last value searched for       */
   int (*icomp)(const void*, const void*); /* insertion comparison function  */
   int (*fcomp)(const void*, const void*); /* search comparison function     */
   void (*freeVal)(void*);                 /* value free function            */
   bt_Node *head;                          /* root node of the tree          */
   bt_Node *first;                         /* first (smallest) node based on **
                                           **  insertion comparison function */
   bt_Node *last;                          /* last (largest) node based on   **
                                           **  insertion comparison function */
   unsigned int length;                    /* number of nodes in the tree    */
};

/* rfree- recursive free function (no longer recursive 3/27/05) */
static void rfree(bt_Node *root, void (*freeVal)(void*));

/* initNode- function to initialize a node for insertion into a tree */
static bt_Node *initNode(void *val);

/* rfind- recursive find function (no longer recursive 3/27/05) */
static bt_Node *rfind(bt_Node *root, const void *val,
                      int (*comp)(const void*, const void*));

/* rinsert- recursive insertion function (no longer recursive 3/27/05) */
static int rinsert(bt_Node *root, bt_Node *nn,
                   int (*comp)(const void*, const void*));

/* clearCurrent- function to clear the last item searched for */
static void clearCurrent(BinTree *bt);

/* rotate- rotates nodes to fix reb-black tree violations
**         node->parent and node->parent->parent should both be non-NULL.
**         returns the node that replaced node->parent->parent (will be either
**         node or node->parent before the call)
*/
static void rotate(bt_Node *node);

/* isBlack- returns non-zero if the node is colored black or is NULL,
**          returns zero otherwise
*/
static int isBlack(bt_Node *node);

/* delCheck- shuffles the tree for a delete as necessary. Fallthrough should
**           be the value the function last returned as it indicates a
**           situation where the previous level could not be reshuffled
*/
static int delCheck(bt_Node *node, int fallthrough, int dir);

/* traverse- returns the next node in ascending/descending order if
**           dir is 1/0 or NULL if none
*/
static bt_Node *traverse(const BinTree *bt, bt_Node *from, int dir);

/* defComp- used only if the provided insert comparison leaves 2 values
**          equal
*/
static int defComp(const void *a, const void *b);

//#ifdef DEBUG
#define BLACKDEPTH     -1
#define DOUBLERED      -2
#define BADORDER       -3
#define AMBIBUOUSORDER -4

/* checkCond- recursive debugging function to check that the binary tree is as
**            expected
*/
static int checkCond(bt_Node *bt, int cnt,
                     int(*comp)(const void*, const void*));

static int findAddr(bt_Node *bt, const void *addr);

/* bt_checkCond- debugging function to check that the binary tree is as
**               expected
*/
int bt_checkCond(BinTree *tree) {
   if(tree == NULL) return 0;
   return checkCond(tree->head, 0, tree->icomp);
}

int bt_findAddr(BinTree *tree, const void *addr) {
   if(tree == NULL) return 0;
   return findAddr(tree->head, addr);
}

static int findAddr(bt_Node *bt, const void *addr) {
   if(bt == NULL) return 0;
   if(bt == addr) return 1;
   return (findAddr(bt->child[0], addr) || findAddr(bt->child[1], addr));
}

static int checkCond(bt_Node *bt, int cnt,
                     int(*comp)(const void*, const void*)) {
   int l, r;
   if(bt == NULL) return cnt;
   if(!isBlack(bt) && !isBlack(bt->parent)) return DOUBLERED;
   if(bt->parent != NULL) {
      l = comp(bt->val, bt->parent->val);
      r = comp(bt->parent->val, bt->val);
      if(l != -r) return -4;
      if(bt == bt->parent->child[0] && l >= 0) return BADORDER;
      if(bt == bt->parent->child[1] && l <= 0) return BADORDER;
   }
   cnt+= isBlack(bt);
   if((l = checkCond(bt->child[0], cnt, comp)) < 0) return l;
   if((r = checkCond(bt->child[1], cnt, comp)) < 0) return r;
   if(l == r) return l;
   else return BLACKDEPTH;
}
//#endif

BinTree *initBinTree(int (*icomp)(const void*, const void*),
                     int (*fcomp)(const void*, const void*),
                     void (*freeVal)(void*)) {
   BinTree *newbt;

   if(icomp == NULL || fcomp == NULL) {
      return NULL;
   }
   if((newbt = (BinTree *)malloc(sizeof(BinTree))) == NULL) {
      return NULL;
   }

   newbt->icomp = icomp;
   newbt->fcomp = fcomp;
   newbt->freeVal = freeVal;
   newbt->head = NULL;
   newbt->cur = NULL;
   newbt->curval = NULL;
   newbt->length = 0;
   newbt->first = NULL;
   newbt->last = NULL;
   return newbt;
}

void freeBinTree(BinTree *bt) {
   if(bt == NULL) return;

   if(bt->head != NULL) {
      rfree(bt->head, bt->freeVal);
      bt->head = NULL;
   }
}

unsigned int bt_getLength(const BinTree *bt) {
   if(bt == NULL) return 0;
   return bt->length;
}

const void *bt_getFirst(BinTree *bt) {
   if(bt == NULL || bt->first == NULL) return NULL;
   bt->cur = bt->first;
   return bt->first->val;
}

const void *bt_getLast(BinTree *bt) {
   if(bt == NULL || bt->last == NULL) return NULL;
   bt->cur = bt->last;
   return bt->last->val;
}

const void *bt_getNext(BinTree *bt) {
   if(bt == NULL || bt->cur == NULL) return NULL;
   bt->cur = traverse(bt, bt->cur, 1);
   bt->curval = (bt->cur == NULL)?(NULL):(bt->cur->val);
   return bt->curval;
}

const void *bt_getCurrent(BinTree *bt) {
   if(bt == NULL || bt->cur == NULL) return NULL;
   return bt->cur->val;
}

const void *bt_getPrev(BinTree *bt) {
   if(bt == NULL || bt->cur == NULL) return NULL;
   bt->cur = traverse(bt, bt->cur, 0);
   bt->curval = (bt->cur == NULL)?(NULL):(bt->cur->val);
   return bt->curval;
}

const void *bt_findVal(BinTree *bt, const void *val) {
   if(bt == NULL || bt->length == 0) return NULL;

   if(val != NULL) {
      bt->curval = val;
      bt->cur = rfind(bt->head, val, bt->fcomp);
      if(bt->cur != NULL) return bt->cur->val;
   } else if(bt->curval != NULL) {
      const void *val = bt->curval;
      bt_Node *tmp;
      if(bt->cur->child[1] != NULL) {
         tmp = rfind(bt->cur->child[1], val, bt->fcomp);
         if(tmp != NULL) {
            bt->cur = tmp;
            return bt->cur->val;
         }
      }
      if((tmp = bt->cur->parent) != NULL) {
         if(bt->fcomp(val, tmp->val) == 0) {
            bt->cur = tmp;
            return bt->cur->val;
         }
      }
   } else if(bt->cur != NULL) {
      return bt_getNext(bt);
   }
   clearCurrent(bt);

   return NULL;
}

int bt_deleteFirst(BinTree *bt) {
   if(bt == NULL || bt->first == NULL) return -1;
   return bt_deleteVal(bt, bt->first->val);
}

int bt_deleteLast(BinTree *bt) {
   if(bt == NULL || bt->last == NULL) return -1;
   return bt_deleteVal(bt, bt->last->val);
}

int bt_deleteCurrent(BinTree *bt) {
   if(bt == NULL || bt->cur == NULL) return -1;
   return bt_deleteVal(bt, bt->cur->val);
}

int bt_deleteVal(BinTree *bt, const void *val) {
   bt_Node *tmp, *last = NULL;
   int fallthrough = 0;
   int me, dir;

   if(bt == NULL || bt->head == NULL) return -1;
   tmp = bt->head;
   me = bt->icomp(val, tmp->val);
   dir = (me > 0);
   if(isBlack(tmp->child[0]) && isBlack(tmp->child[1])) {
      tmp->color = RED;
   } else {
      fallthrough = 1;
   }
   if(me == 0) {
      last = tmp;
   } else {
      tmp = tmp->child[dir];
   }

   while(tmp != NULL && last == NULL) {
      me = bt->icomp(val, tmp->val);
      fallthrough = delCheck(tmp, fallthrough, dir);
      dir = (me > 0);
#ifdef DEBUG
{ int ret;
while(bt->head->parent != NULL) bt->head = bt->head->parent;
if((ret = bt_checkCond(bt)) < 0) {
   fprintf(myLog, "inconsistency in tree %d %d\n", ret, __LINE__);
   fflush(myLog);
fprintf(stderr, "exiting\n");
   exit(1);
}
}
#endif
      if(me == 0) {
         last = tmp;
      } else {
         tmp = tmp->child[dir];
      }
   }

   if(last != NULL) {
      int dir = 0;
      bt_Node *rep = last->child[0];

      if(bt->length > 1) {
         if(bt->cur == last) clearCurrent(bt);
         if(bt->first == last) bt->first = traverse(bt, bt->first, 1);
         if(bt->last == last) bt->last = traverse(bt, bt->last, 0);
      } else {
         clearCurrent(bt);
         bt->first = NULL;
         bt->last = NULL;
      }

      if(rep != NULL) {
         tmp = rep;
         while(tmp != NULL) {
            fallthrough = delCheck(tmp, fallthrough, dir);

#ifdef DEBUG
{ int ret;
while(bt->head->parent != NULL) bt->head = bt->head->parent;
if((ret = bt_checkCond(bt)) < 0) {
   fprintf(myLog, "inconsistency in tree %d %d\n", ret, __LINE__);
   fflush(myLog);
fprintf(stderr, "exiting\n");
   exit(1);
}
}
#endif
            rep = tmp;
            tmp = tmp->child[1];
            dir = 1;
         }
         if(rep == last->child[0]) {
            last->child[0] = NULL;
         } else {
            rep->parent->child[1] = NULL;
         }
      } else {
         rep = last->child[1];
         last->child[1] = NULL;
      }
      if(last->parent != NULL) {
         last->parent->child[(last == last->parent->child[1])] = rep;
      } else {
         bt->head = rep;
      }
      if(rep != NULL) {
         rep->parent = last->parent;
         rep->child[0] = last->child[0];
         rep->child[1] = last->child[1];
         rep->color = last->color;
      }
      if(bt->freeVal) {
         bt->freeVal(last->val);
      }
#ifdef DEBUG
if(bt_findAddr(bt, last)) {
   fprintf(myLog, "deleted address still in tree...\n");
   fflush(myLog);
fprintf(stderr, "exiting\n");
   exit(1);
}
#endif
      free(last);

      if(bt->head != NULL) {
         while(bt->head->parent != NULL) bt->head = bt->head->parent;
         bt->head->color = BLACK;
      }

      bt->length--;
#ifdef DEBUG
{ int ret;
if((ret = bt_checkCond(bt)) < 0) {
   fprintf(myLog, "inconsistency in tree %d %d\n", ret, __LINE__);
   fflush(myLog);
fprintf(stderr, "exiting\n");
   exit(1);
}
}
#endif
      return 0;
   }

   if(bt->head != NULL) {
      while(bt->head->parent != NULL) bt->head = bt->head->parent;
      bt->head->color = BLACK;
   }

#ifdef DEBUG
{ int ret;
if((ret = bt_checkCond(bt)) < 0) {
   fprintf(myLog, "inconsistency in tree %d %d\n", ret, __LINE__);
   fflush(myLog);
fprintf(stderr, "exiting\n");
   exit(1);
}
}
#endif
   return -2;
}

int bt_insertVal(BinTree *bt, void *val) {
   bt_Node *nn;

   if(bt == NULL) return -1;
   if((nn = initNode(val)) == NULL) {
      return -3;
   }

#ifdef DEBUG
if(bt_findAddr(bt, nn)) {
   fprintf(myLog, "allocated address already in tree...\n");
   fflush(myLog);
fprintf(stderr, "exiting\n");
   exit(1);
}
#endif
   if(bt->head == NULL) {
      bt->head = nn;
      bt->first = nn;
      bt->last = nn;
      bt->length++;
#ifdef DEBUG
{ int ret;
if((ret = bt_checkCond(bt)) < 0) {
   fprintf(myLog, "inconsistency in tree %d %d\n", ret, __LINE__);
   fflush(myLog);
fprintf(stderr, "exiting\n");
   exit(1);
}
}
#endif
      return 0;
   } else {
      int ret;
      if((ret = rinsert(bt->head, nn, bt->icomp)) < 0) {
#ifdef DEBUG
{ int ret;
while(bt->head->parent != NULL) {
   bt->head = bt->head->parent;
}
if((ret = bt_checkCond(bt)) < 0) {
   fprintf(myLog, "inconsistency in tree %d %d\n", ret, __LINE__);
   fflush(myLog);
fprintf(stderr, "exiting\n");
   exit(1);
}
}
#endif
         return ret;
      }
      if(bt->icomp(val, bt->first->val) < 0) {
         bt->first = nn;
      } else if(bt->icomp(bt->last->val, val) < 0) {
         bt->last = nn;
      }
      while(bt->head->parent != NULL) {
         bt->head = bt->head->parent;
      }
   }
#ifdef DEBUG
{ int ret;
if((ret = bt_checkCond(bt)) < 0) {
   fprintf(myLog, "inconsistency in tree %d %d\n", ret, __LINE__);
   fflush(myLog);
fprintf(stderr, "exiting\n");
   exit(1);
}
}
#endif
   bt->head->color = BLACK;
   bt->length++;

#ifdef DEBUG
{ int ret;
if((ret = bt_checkCond(bt)) < 0) {
   fprintf(myLog, "inconsistency in tree %d %d\n", ret, __LINE__);
   fflush(myLog);
fprintf(stderr, "exiting\n");
   exit(1);
}
}
#endif
   return 0;
}

/***************** private functions ******************/

static void rfree(bt_Node *root, void (*freeVal)(void*)) {
   bt_Node *tmp = root;
   while(tmp != NULL) {
      if(tmp->child[0] != NULL) {
         tmp = tmp->child[0];
      } else if(tmp->child[1] != NULL) {
         tmp = tmp->child[1];
      } else {
         bt_Node *last = tmp;
         tmp = tmp->parent;
         if(tmp != NULL) tmp->child[(last == tmp->child[1])] = NULL;
         if(freeVal != NULL) freeVal(last->val);
         free(last);
      }
   }
}

static bt_Node *initNode(void *val) {
   bt_Node *nn = (bt_Node *)malloc(sizeof(bt_Node));
   
   if(nn == NULL) return NULL;
   nn->val = val;
   nn->parent = NULL;
   nn->child[0] = NULL;
   nn->child[1] = NULL;
   nn->color = RED;

   return nn;
}

static bt_Node *rfind(bt_Node *root, const void *val,
                      int (*comp)(const void*, const void*)) {
   bt_Node *tmp = root, *last = NULL;

   while(tmp != NULL) {
      int me = comp(val, tmp->val);
      if(me == 0) {
         last = tmp;
         tmp = tmp->child[0];
      } else if(last == NULL) {
         tmp = tmp->child[(me > 0)];
      } else {
         tmp = NULL;
      }
   }
   return last;
}

static int rinsert(bt_Node *root, bt_Node *nn,
                   int (*comp)(const void*, const void*)) {
   bt_Node *tmp = root;
   int dir, inserted = 0;

   while(inserted == 0) {
      int sort = comp(nn->val, tmp->val);
      /* check for duplicate value* */
      if(sort == 0 && (sort = defComp(nn->val, tmp->val)) == 0) return -2;
      if(!isBlack(tmp->child[0]) && !isBlack(tmp->child[1])) {
         bt_Node *parent = tmp->parent;

         tmp->color = RED;
         tmp->child[0]->color = BLACK;
         tmp->child[1]->color = BLACK;
         if(parent != NULL && parent->color == RED) {
            if(parent->parent == NULL) {
               parent->color = BLACK;
            } else {
               rotate(tmp);
            }
         }
      }
#ifdef DEBUG
{ int ret;
if((ret = checkCond(root, 0, comp)) < 0) {
   fprintf(myLog, "inconsistency in tree %d %d\n", ret, __LINE__);
   fflush(myLog);
fprintf(stderr, "exiting\n");
   exit(1);
}
}
#endif
      dir = (sort > 0);
      if(tmp->child[dir] == NULL) {
         tmp->child[dir] = nn;
         nn->parent = tmp;
         inserted = 1;
      } else {
         tmp = tmp->child[dir];
      }
   }
   if(tmp->color == RED) {
      if(tmp->parent == NULL) {
         tmp->color = BLACK;
      } else {
         rotate(nn);
      }
#ifdef DEBUG
{ int ret;
if((ret = checkCond(root, 0, comp)) < 0) {
   fprintf(myLog, "inconsistency in tree %d %d\n", ret, __LINE__);
   fflush(myLog);
fprintf(stderr, "exiting\n");
   exit(1);
}
}
#endif
   }
   return 0;
}

static void clearCurrent(BinTree *bt) {
   bt->cur = NULL;
   bt->curval = NULL;
}

static void rotate(bt_Node *node) {
   bt_Node *p = node->parent;
   bt_Node *gp = p->parent;
   bt_Node *ggp = gp->parent;
   bt_Node *head;
   int dir, hColor = gp->color;

   dir = (p == gp->child[1]);
   gp->color = 1 - hColor;

   if(node == p->child[dir]) {
      head = p;
   } else {
      head = node;

      p->child[1-dir] = node->child[dir];
      if(p->child[1-dir] != NULL) {
         p->child[1-dir]->parent = p;
      }
      node->child[dir] = p;
      p->parent = node;
   }
   gp->child[dir] = head->child[1-dir];
   head->child[1-dir] = gp;
   if(gp->child[dir] != NULL) {
      gp->child[dir]->parent = gp;
   }

   gp->parent = head;
   head->parent = ggp;
   head->color = hColor;
   if(ggp != NULL) ggp->child[(gp == ggp->child[1])] = head;
}

static int isBlack(bt_Node *node) {
   return node == NULL || node->color == BLACK;
}

static int delCheck(bt_Node *node, int fallthrough, int dir) {
   bt_Node *p = node->parent, *sib = p->child[1-dir];

   if(node->color == RED) return 0;

   if(fallthrough) {
      p->child[1-dir] = sib->child[dir];
      p->child[1-dir]->parent = p;
      sib->parent = p->parent;
      sib->child[dir] = p;
      if(p->parent != NULL) p->parent->child[(p == p->parent->child[1])] = sib;
      p->parent = sib;
      sib->color = BLACK;
      p->color = RED;
      sib = p->child[1-dir];
   }

   if(isBlack(node->child[0]) && isBlack(node->child[1])) {
      if(!isBlack(sib->child[0])) {
         rotate(sib->child[0]);
         if(dir == 1) sib->child[0]->color = BLACK;
      } else if(!isBlack(sib->child[1])) {
         rotate(sib->child[1]);
         if(dir == 0) sib->child[1]->color = BLACK;
      } else {
         node->parent->color = BLACK;
         sib->color = RED;
      }
      node->color = RED;

      return 0;
   }

   return 1;
}

static bt_Node *traverse(const BinTree *bt, bt_Node *from, int dir) {
   bt_Node *tmp = from->child[dir];
   if(tmp != NULL) {
      while(tmp->child[1-dir] != NULL) tmp = tmp->child[1-dir];
      return tmp;
   }

   if(from == ((dir == 1)?(bt->last):(bt->first))) return NULL;

   tmp = from;
   while(tmp == tmp->parent->child[dir]) tmp = tmp->parent;
   return tmp->parent;
}

static int defComp(const void *a, const void *b) {
   if(a < b) return -1;
   if(a > b) return 1;
   return 0;
}
