/* 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 */