/* glpavl.c (binary search tree) */

/***********************************************************************

*  This code is part of GLPK (GNU Linear Programming Kit).

*

*  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,

*  2009, 2010 Andrew Makhorin, Department for Applied Informatics,

*  Moscow Aviation Institute, Moscow, Russia. All rights reserved.

*  E-mail: <mao@gnu.org>.

*

*  GLPK 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 3 of the License, or

*  (at your option) any later version.

*

*  GLPK 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 GLPK. If not, see <http://www.gnu.org/licenses/>.

***********************************************************************/

#include "glpavl.h"

AVL *avl_create_tree(int (*fcmp)(void *info, const void *key1,

      const void *key2), void *info)

{     /* create AVL tree */

      AVL *tree;

      tree = xmalloc(sizeof(AVL));

      tree->pool = dmp_create_pool();

      tree->root = NULL;

      tree->fcmp = fcmp;

      tree->info = info;

      tree->size = 0;

      tree->height = 0;

      return tree;

}

int avl_strcmp(void *info, const void *key1, const void *key2)

{     /* compare character string keys */

      xassert(info == info);

      return strcmp(key1, key2);

}

static AVLNODE *rotate_subtree(AVL *tree, AVLNODE *node);

AVLNODE *avl_insert_node(AVL *tree, const void *key)

{     /* insert new node into AVL tree */

      AVLNODE *p, *q, *r;

      short int flag;

      /* find an appropriate point for insertion */

      p = NULL; q = tree->root;

      while (q != NULL)

      {  p = q;

         if (tree->fcmp(tree->info, key, p->key) <= 0)

         {  flag = 0;

            q = p->left;

            p->rank++;

         }

         else

         {  flag = 1;

            q = p->right;

         }

      }

      /* create new node and insert it into the tree */

      r = dmp_get_atom(tree->pool, sizeof(AVLNODE));

      r->key = key; r->type = 0; r->link = NULL;

      r->rank = 1; r->up = p;

      r->flag = (short int)(p == NULL ? 0 : flag);

      r->bal = 0; r->left = NULL; r->right = NULL;

      tree->size++;

      if (p == NULL)

         tree->root = r;

      else

         if (flag == 0) p->left = r; else p->right = r;

      /* go upstairs to the root and correct all subtrees affected by

         insertion */

      while (p != NULL)

      {  if (flag == 0)

         {  /* the height of the left subtree of [p] is increased */

            if (p->bal > 0)

            {  p->bal = 0;

               break;

            }

            if (p->bal < 0)

            {  rotate_subtree(tree, p);

               break;

            }

            p->bal = -1; flag = p->flag; p = p->up;

         }

         else

         {  /* the height of the right subtree of [p] is increased */

            if (p->bal < 0)

            {  p->bal = 0;

               break;

            }

            if (p->bal > 0)

            {  rotate_subtree(tree, p);

               break;

            }

            p->bal = +1; flag = p->flag; p = p->up;

         }

      }

      /* if the root has been reached, the height of the entire tree is

         increased */

      if (p == NULL) tree->height++;

      return r;

}

void avl_set_node_type(AVLNODE *node, int type)

{     /* assign the type field of specified node */

      node->type = type;

      return;

}

void avl_set_node_link(AVLNODE *node, void *link)

{     /* assign the link field of specified node */

      node->link = link;

      return;

}

AVLNODE *avl_find_node(AVL *tree, const void *key)

{     /* find node in AVL tree */

      AVLNODE *p;

      int c;

      p = tree->root;

      while (p != NULL)

      {  c = tree->fcmp(tree->info, key, p->key);

         if (c == 0) break;

         p = (c < 0 ? p->left : p->right);

      }

      return p;

}

int avl_get_node_type(AVLNODE *node)

{     /* retrieve the type field of specified node */

      return node->type;

}

void *avl_get_node_link(AVLNODE *node)

{     /* retrieve the link field of specified node */

      return node->link;

}

static AVLNODE *find_next_node(AVL *tree, AVLNODE *node)

{     /* find next node in AVL tree */

      AVLNODE *p, *q;

      if (tree->root == NULL) return NULL;

      p = node;

      q = (p == NULL ? tree->root : p->right);

      if (q == NULL)

      {  /* go upstairs from the left subtree */

         for (;;)

         {  q = p->up;

            if (q == NULL) break;

            if (p->flag == 0) break;

            p = q;

         }

      }

      else

      {  /* go downstairs into the right subtree */

         for (;;)

         {  p = q->left;

            if (p == NULL) break;

            q = p;

         }

      }

      return q;

}

void avl_delete_node(AVL *tree, AVLNODE *node)

{     /* delete specified node from AVL tree */

      AVLNODE *f, *p, *q, *r, *s, *x, *y;

      short int flag;

      p = node;

      /* if both subtrees of the specified node are non-empty, the node

         should be interchanged with the next one, at least one subtree

         of which is always empty */

      if (p->left == NULL || p->right == NULL) goto skip;

      f = p->up; q = p->left;

      r = find_next_node(tree, p); s = r->right;

      if (p->right == r)

      {  if (f == NULL)

            tree->root = r;

         else

            if (p->flag == 0) f->left = r; else f->right = r;

         r->rank = p->rank; r->up = f;

         r->flag = p->flag; r->bal = p->bal;

         r->left = q; r->right = p;

         q->up = r;

         p->rank = 1; p->up = r; p->flag = 1;

         p->bal = (short int)(s == NULL ? 0 : +1);

         p->left = NULL; p->right = s;

         if (s != NULL) s->up = p;

      }

      else

      {  x = p->right; y = r->up;

         if (f == NULL)

            tree->root = r;

         else

            if (p->flag == 0) f->left = r; else f->right = r;

         r->rank = p->rank; r->up = f;

         r->flag = p->flag; r->bal = p->bal;

         r->left = q; r->right = x;

         q->up = r; x->up = r; y->left = p;

         p->rank = 1; p->up = y; p->flag = 0;

         p->bal = (short int)(s == NULL ? 0 : +1);

         p->left = NULL; p->right = s;

         if (s != NULL) s->up = p;

      }

skip: /* now the specified node [p] has at least one empty subtree;

         go upstairs to the root and adjust the rank field of all nodes

         affected by deletion */

      q = p; f = q->up;

      while (f != NULL)

      {  if (q->flag == 0) f->rank--;

         q = f; f = q->up;

      }

      /* delete the specified node from the tree */

      f = p->up; flag = p->flag;

      q = p->left != NULL ? p->left : p->right;

      if (f == NULL)

         tree->root = q;

      else

         if (flag == 0) f->left = q; else f->right = q;

      if (q != NULL) q->up = f, q->flag = flag;

      tree->size--;

      /* go upstairs to the root and correct all subtrees affected by

         deletion */

      while (f != NULL)

      {  if (flag == 0)

         {  /* the height of the left subtree of [f] is decreased */

            if (f->bal == 0)

            {  f->bal = +1;

               break;

            }

            if (f->bal < 0)

               f->bal = 0;

            else

            {  f = rotate_subtree(tree, f);

               if (f->bal < 0) break;

            }

            flag = f->flag; f = f->up;

         }

         else

         {  /* the height of the right subtree of [f] is decreased */

            if (f->bal == 0)

            {  f->bal = -1;

               break;

            }

            if (f->bal > 0)

               f->bal = 0;

            else

            {  f = rotate_subtree(tree, f);

               if (f->bal > 0) break;

            }

            flag = f->flag; f = f->up;

         }

      }

      /* if the root has been reached, the height of the entire tree is

         decreased */

      if (f == NULL) tree->height--;

      /* returns the deleted node to the memory pool */

      dmp_free_atom(tree->pool, p, sizeof(AVLNODE));

      return;

}

static AVLNODE *rotate_subtree(AVL *tree, AVLNODE *node)

{     /* restore balance of AVL subtree */

      AVLNODE *f, *p, *q, *r, *x, *y;

      xassert(node != NULL);

      p = node;

      if (p->bal < 0)

      {  /* perform negative (left) rotation */

         f = p->up; q = p->left; r = q->right;

         if (q->bal <= 0)

         {  /* perform single negative rotation */

            if (f == NULL)

               tree->root = q;

            else

               if (p->flag == 0) f->left = q; else f->right = q;

            p->rank -= q->rank;

            q->up = f; q->flag = p->flag; q->bal++; q->right = p;

            p->up = q; p->flag = 1;

            p->bal = (short int)(-q->bal); p->left = r;

            if (r != NULL) r->up = p, r->flag = 0;

            node = q;

         }

         else

         {  /* perform double negative rotation */

            x = r->left; y = r->right;

            if (f == NULL)

               tree->root = r;

            else

               if (p->flag == 0) f->left = r; else f->right = r;

            p->rank -= (q->rank + r->rank);

            r->rank += q->rank;

            p->bal = (short int)(r->bal >= 0 ? 0 : +1);

            q->bal = (short int)(r->bal <= 0 ? 0 : -1);

            r->up = f; r->flag = p->flag; r->bal = 0;

            r->left = q; r->right = p;

            p->up = r; p->flag = 1; p->left = y;

            q->up = r; q->flag = 0; q->right = x;

            if (x != NULL) x->up = q, x->flag = 1;

            if (y != NULL) y->up = p, y->flag = 0;

            node = r;

         }

      }

      else

      {  /* perform positive (right) rotation */

         f = p->up; q = p->right; r = q->left;

         if (q->bal >= 0)

         {  /* perform single positive rotation */

            if (f == NULL)

               tree->root = q;

            else

               if (p->flag == 0) f->left = q; else f->right = q;

            q->rank += p->rank;

            q->up = f; q->flag = p->flag; q->bal--; q->left = p;

            p->up = q; p->flag = 0;

            p->bal = (short int)(-q->bal); p->right = r;

            if (r != NULL) r->up = p, r->flag = 1;

            node = q;

         }

         else

         {  /* perform double positive rotation */

            x = r->left; y = r->right;

            if (f == NULL)

               tree->root = r;

            else

               if (p->flag == 0) f->left = r; else f->right = r;

            q->rank -= r->rank;

            r->rank += p->rank;

            p->bal = (short int)(r->bal <= 0 ? 0 : -1);

            q->bal = (short int)(r->bal >= 0 ? 0 : +1);

            r->up = f; r->flag = p->flag; r->bal = 0;

            r->left = p; r->right = q;

            p->up = r; p->flag = 0; p->right = x;

            q->up = r; q->flag = 1; q->left = y;

            if (x != NULL) x->up = p, x->flag = 1;

            if (y != NULL) y->up = q, y->flag = 0;

            node = r;

         }

      }

      return node;

}

void avl_delete_tree(AVL *tree)

{     /* delete AVL tree */

      dmp_delete_pool(tree->pool);

      xfree(tree);

      return;

}

/* eof */