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 }
283