reactos/dll/win32/glu32/libnurbs/nurbtess/searchTree.cc

   1 /*
   2 ** License Applicability. Except to the extent portions of this file are
   3 ** made subject to an alternative license as permitted in the SGI Free
   4 ** Software License B, Version 1.1 (the "License"), the contents of this
   5 ** file are subject only to the provisions of the License. You may not use
   6 ** this file except in compliance with the License. You may obtain a copy
   7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
   8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
   9 **
  10 ** http://oss.sgi.com/projects/FreeB
  11 **
  12 ** Note that, as provided in the License, the Software is distributed on an
  13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
  14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
  15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
  16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
  17 **
  18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
  19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
  20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
  21 ** Copyright in any portions created by third parties is as indicated
  22 ** elsewhere herein. All Rights Reserved.
  23 **
  24 ** Additional Notice Provisions: The application programming interfaces
  25 ** established by SGI in conjunction with the Original Code are The
  26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
  27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
  28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
  29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
  30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
  31 ** published by SGI, but has not been independently verified as being
  32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
  33 **
  34 ** $Date$ $Revision: 1.1 $
  35 */
  36 /*
  37 ** $Header: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/glu32/libnurbs/nurbtess/searchTree.cc,v 1.1 2004/02/02 16:39:15 navaraf Exp $
  38 */
  39
  40 #include <stdlib.h>
  41 #include <stdio.h>
  42 #include "zlassert.h"
  43
  44 #include "searchTree.h"
  45
  46 #define max(a,b) ((a>b)? a:b)
  47
  48 treeNode* TreeNodeMake(void *key)
  49 {
  50   treeNode *ret = (treeNode*) malloc(sizeof(treeNode));
  51   assert(ret);
  52   ret->key = key;
  53   ret->parent = NULL;
  54   ret->left = NULL;
  55   ret->right = NULL;
  56   return ret;
  57 }
  58
  59 void TreeNodeDeleteSingleNode(treeNode* node)
  60 {
  61   free(node);
  62 }
  63
  64 void TreeNodeDeleteWholeTree(treeNode* node)
  65 {
  66   if(node == NULL) return;
  67   TreeNodeDeleteWholeTree(node->left);
  68   TreeNodeDeleteWholeTree(node->right);
  69   TreeNodeDeleteSingleNode(node);
  70 }
  71
  72 void TreeNodePrint(treeNode* node,
  73                    void (*keyPrint) (void*))
  74 {
  75   if(node ==NULL) return;
  76   TreeNodePrint(node->left, keyPrint);
  77   keyPrint(node->key);
  78   TreeNodePrint(node->right, keyPrint);
  79 }
  80
  81 int TreeNodeDepth(treeNode* root)
  82 {
  83   if(root == NULL) return 0;
  84   else{
  85     int leftdepth = TreeNodeDepth(root->left);
  86     int rightdepth = TreeNodeDepth(root->right);
  87     return 1 + max(leftdepth, rightdepth);
  88   }
  89 }
  90
  91 /*return the node with the key.
  92  *NULL is returned if not found
  93  */
  94 treeNode* TreeNodeFind(treeNode* tree, void* key,
  95                        int (*compkey) (void*, void*))
  96 {
  97   if(tree == NULL)
  98     return NULL;
  99   if(key == tree->key)
 100     return tree;
 101   else if(compkey(key, tree->key) < 0)
 102     return TreeNodeFind(tree->left, key, compkey);
 103   else
 104     return TreeNodeFind(tree->right, key, compkey);
 105 }
 106
 107
 108 treeNode* TreeNodeInsert(treeNode* root, treeNode* newnode,
 109                     int (*compkey) (void *, void *))
 110 {
 111   treeNode *y = NULL;
 112   treeNode *x = root;
 113   /*going down the tree from the root.
 114    *x traces the path, y is the parent of x.
 115    */
 116   while (x != NULL){
 117     y = x;
 118     if(compkey(newnode->key,x->key) < 0) /*if newnode < x*/
 119       x = x->left;
 120     else
 121       x = x->right;
 122   }
 123
 124   /*now y has the property that
 125    * if newnode < y, then y->left is NULL
 126    * if newnode > y, then y->right is NULL.
 127    *So we want to isnert newnode to be the child of y
 128    */
 129   newnode->parent = y;
 130   if(y == NULL)
 131     return newnode;
 132   else if( compkey(newnode->key, y->key) <0)
 133     {
 134       y->left = newnode;
 135     }
 136   else
 137     {
 138       y->right = newnode;
 139     }
 140
 141   return root;
 142 }
 143
 144 treeNode* TreeNodeDeleteSingleNode(treeNode* tree, treeNode* node)
 145 {
 146   treeNode* y;
 147   treeNode* x;
 148   treeNode* ret;
 149   if(node==NULL) return tree;
 150
 151   if(node->left == NULL || node->right == NULL) {
 152
 153     y = node;
 154     if(y->left != NULL)
 155       x = y->left;
 156     else
 157       x = y->right;
 158
 159     if( x != NULL)
 160       x->parent = y->parent;
 161
 162     if(y->parent == NULL) /*y is the root which has at most one child x*/
 163       ret = x;
 164     else /*y is not the root*/
 165       {
 166         if(y == y->parent->left)
 167           y->parent->left = x;
 168         else
 169           y->parent->right = x;
 170         ret =  tree;
 171       }
 172   }
 173   else { /*node has two children*/
 174
 175      y = TreeNodeSuccessor(node);
 176      assert(y->left == NULL);
 177
 178      if(y == node->right) /*y is the right child if node*/
 179        {
 180          y->parent = node->parent;
 181          y->left = node->left;
 182          node->left->parent = y;
 183
 184        }
 185      else  /*y != node->right*/
 186        {
 187          x = y->right;
 188          if(x!= NULL)
 189            x->parent = y->parent;
 190
 191          assert(y->parent != NULL);
 192          if(y == y->parent->left)
 193            y->parent->left = x;
 194          else
 195            y->parent->right = x;
 196          /*move y to the position of node*/
 197          y->parent = node->parent;
 198          y->left = node->left;
 199          y->right = node->right;
 200          node->left->parent = y;
 201          node->right->parent = y;
 202        }
 203     if(node->parent != NULL) {
 204       if(node->parent->left == node)
 205         node->parent->left = y;
 206       else
 207         node->parent->right = y;
 208       ret = tree; /*the root if the tree doesn't change*/
 209     }
 210     else /*node->parent is NULL: node is the root*/
 211       ret = y;
 212   }
 213
 214   /*finally free the node, and return the new root*/
 215   TreeNodeDeleteSingleNode(node);
 216   return ret;
 217 }
 218
 219
 220 /*the minimum node in the tree rooted by node
 221  */
 222 treeNode* TreeNodeMinimum(treeNode* node)
 223 {
 224   treeNode* temp = node;
 225   if(temp == NULL) return NULL;
 226   while(temp->left != NULL) {
 227     temp = temp->left;
 228   }
 229   return temp;
 230 }
 231
 232 /*the maximum node in the tree rooted by node
 233  */
 234 treeNode* TreeNodeMaximum(treeNode* node)
 235 {
 236   treeNode* temp = node;
 237   if(temp == NULL) return NULL;
 238   while(temp->right != NULL) {
 239     temp = temp->right;
 240   }
 241   return temp;
 242 }
 243
 244 /*return the first node (in sorted order) which is to the right of this node
 245  */
 246 treeNode* TreeNodeSuccessor(treeNode* node)
 247 {
 248   if(node == NULL) return NULL;
 249   if(node->right != NULL)
 250     return TreeNodeMinimum(node->right);
 251   else{ /*node->right is NULL*/
 252
 253     /*find the first right-ancestor*/
 254     treeNode *y = node->parent;
 255     treeNode* x = node;
 256     while(y != NULL && x == y->right) /*if y is a left parent of x*/
 257       {
 258
 259         x = y;
 260         y = y->parent;
 261       }
 262     return y;
 263   }
 264 }
 265
 266 /*return the first node (in sorted order) which is to the left of this node
 267  */
 268 treeNode* TreeNodePredecessor(treeNode* node)
 269 {
 270   if(node == NULL) return NULL;
 271   if(node->left != NULL)
 272     return TreeNodeMaximum(node->left);
 273   else{ /*node->left is NULL*/
 274     /*find the first left-ancestor*/
 275     treeNode *y = node->parent;
 276     treeNode *x = node;
 277     while(y != NULL && x == y->left) /*if y is a right parent of x*/
 278       {
 279         x = y;
 280         y = y->parent;
 281       }
 282     return y;
 283   }
 284 }