src/glu/sgi/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 */
  35 /*
  36 */
  37
  38 #include <stdlib.h>
  39 #include <stdio.h>
  40 #include "zlassert.h"
  41
  42 #include "searchTree.h"
  43
  44 #define max(a,b) ((a>b)? a:b)
  45
  46 treeNode* TreeNodeMake(void *key)
  47 {
  48   treeNode *ret = (treeNode*) malloc(sizeof(treeNode));
  49   assert(ret);
  50   ret->key = key;
  51   ret->parent = NULL;
  52   ret->left = NULL;
  53   ret->right = NULL;
  54   return ret;
  55 }
  56
  57 void TreeNodeDeleteSingleNode(treeNode* node)
  58 {
  59   free(node);
  60 }
  61
  62 void TreeNodeDeleteWholeTree(treeNode* node)
  63 {
  64   if(node == NULL) return;
  65   TreeNodeDeleteWholeTree(node->left);
  66   TreeNodeDeleteWholeTree(node->right);
  67   TreeNodeDeleteSingleNode(node);
  68 }
  69
  70 void TreeNodePrint(treeNode* node,
  71                    void (*keyPrint) (void*))
  72 {
  73   if(node ==NULL) return;
  74   TreeNodePrint(node->left, keyPrint);
  75   keyPrint(node->key);
  76   TreeNodePrint(node->right, keyPrint);
  77 }
  78
  79 int TreeNodeDepth(treeNode* root)
  80 {
  81   if(root == NULL) return 0;
  82   else{
  83     int leftdepth = TreeNodeDepth(root->left);
  84     int rightdepth = TreeNodeDepth(root->right);
  85     return 1 + max(leftdepth, rightdepth);
  86   }
  87 }
  88
  89 /*return the node with the key.
  90  *NULL is returned if not found
  91  */
  92 treeNode* TreeNodeFind(treeNode* tree, void* key,
  93                        int (*compkey) (void*, void*))
  94 {
  95   if(tree == NULL)
  96     return NULL;
  97   if(key == tree->key)
  98     return tree;
  99   else if(compkey(key, tree->key) < 0)
 100     return TreeNodeFind(tree->left, key, compkey);
 101   else
 102     return TreeNodeFind(tree->right, key, compkey);
 103 }
 104
 105
 106 treeNode* TreeNodeInsert(treeNode* root, treeNode* newnode,
 107                     int (*compkey) (void *, void *))
 108 {
 109   treeNode *y = NULL;
 110   treeNode *x = root;
 111   /*going down the tree from the root.
 112    *x traces the path, y is the parent of x.
 113    */
 114   while (x != NULL){
 115     y = x;
 116     if(compkey(newnode->key,x->key) < 0) /*if newnode < x*/
 117       x = x->left;
 118     else
 119       x = x->right;
 120   }
 121
 122   /*now y has the property that
 123    * if newnode < y, then y->left is NULL
 124    * if newnode > y, then y->right is NULL.
 125    *So we want to isnert newnode to be the child of y
 126    */
 127   newnode->parent = y;
 128   if(y == NULL)
 129     return newnode;
 130   else if( compkey(newnode->key, y->key) <0)
 131     {
 132       y->left = newnode;
 133     }
 134   else
 135     {
 136       y->right = newnode;
 137     }
 138
 139   return root;
 140 }
 141
 142 treeNode* TreeNodeDeleteSingleNode(treeNode* tree, treeNode* node)
 143 {
 144   treeNode* y;
 145   treeNode* x;
 146   treeNode* ret;
 147   if(node==NULL) return tree;
 148
 149   if(node->left == NULL || node->right == NULL) {
 150
 151     y = node;
 152     if(y->left != NULL)
 153       x = y->left;
 154     else
 155       x = y->right;
 156
 157     if( x != NULL)
 158       x->parent = y->parent;
 159
 160     if(y->parent == NULL) /*y is the root which has at most one child x*/
 161       ret = x;
 162     else /*y is not the root*/
 163       {
 164         if(y == y->parent->left)
 165           y->parent->left = x;
 166         else
 167           y->parent->right = x;
 168         ret =  tree;
 169       }
 170   }
 171   else { /*node has two children*/
 172
 173      y = TreeNodeSuccessor(node);
 174      assert(y->left == NULL);
 175
 176      if(y == node->right) /*y is the right child if node*/
 177        {
 178          y->parent = node->parent;
 179          y->left = node->left;
 180          node->left->parent = y;
 181
 182        }
 183      else  /*y != node->right*/
 184        {
 185          x = y->right;
 186          if(x!= NULL)
 187            x->parent = y->parent;
 188
 189          assert(y->parent != NULL);
 190          if(y == y->parent->left)
 191            y->parent->left = x;
 192          else
 193            y->parent->right = x;
 194          /*move y to the position of node*/
 195          y->parent = node->parent;
 196          y->left = node->left;
 197          y->right = node->right;
 198          node->left->parent = y;
 199          node->right->parent = y;
 200        }
 201     if(node->parent != NULL) {
 202       if(node->parent->left == node)
 203         node->parent->left = y;
 204       else
 205         node->parent->right = y;
 206       ret = tree; /*the root if the tree doesn't change*/
 207     }
 208     else /*node->parent is NULL: node is the root*/
 209       ret = y;
 210   }
 211
 212   /*finally free the node, and return the new root*/
 213   TreeNodeDeleteSingleNode(node);
 214   return ret;
 215 }
 216
 217
 218 /*the minimum node in the tree rooted by node
 219  */
 220 treeNode* TreeNodeMinimum(treeNode* node)
 221 {
 222   treeNode* temp = node;
 223   if(temp == NULL) return NULL;
 224   while(temp->left != NULL) {
 225     temp = temp->left;
 226   }
 227   return temp;
 228 }
 229
 230 /*the maximum node in the tree rooted by node
 231  */
 232 treeNode* TreeNodeMaximum(treeNode* node)
 233 {
 234   treeNode* temp = node;
 235   if(temp == NULL) return NULL;
 236   while(temp->right != NULL) {
 237     temp = temp->right;
 238   }
 239   return temp;
 240 }
 241
 242 /*return the first node (in sorted order) which is to the right of this node
 243  */
 244 treeNode* TreeNodeSuccessor(treeNode* node)
 245 {
 246   if(node == NULL) return NULL;
 247   if(node->right != NULL)
 248     return TreeNodeMinimum(node->right);
 249   else{ /*node->right is NULL*/
 250
 251     /*find the first right-ancestor*/
 252     treeNode *y = node->parent;
 253     treeNode* x = node;
 254     while(y != NULL && x == y->right) /*if y is a left parent of x*/
 255       {
 256
 257         x = y;
 258         y = y->parent;
 259       }
 260     return y;
 261   }
 262 }
 263
 264 /*return the first node (in sorted order) which is to the left of this node
 265  */
 266 treeNode* TreeNodePredecessor(treeNode* node)
 267 {
 268   if(node == NULL) return NULL;
 269   if(node->left != NULL)
 270     return TreeNodeMaximum(node->left);
 271   else{ /*node->left is NULL*/
 272     /*find the first left-ancestor*/
 273     treeNode *y = node->parent;
 274     treeNode *x = node;
 275     while(y != NULL && x == y->left) /*if y is a right parent of x*/
 276       {
 277         x = y;
 278         y = y->parent;
 279       }
 280     return y;
 281   }
 282 }