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:
10 ** http://oss.sgi.com/projects/FreeB
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.
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.
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.
34 ** $Date$ $Revision: 1.1 $
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 $
44 #include "searchTree.h"
46 #define max(a,b) ((a>b)? a:b)
48 treeNode
* TreeNodeMake(void *key
)
50 treeNode
*ret
= (treeNode
*) malloc(sizeof(treeNode
));
59 void TreeNodeDeleteSingleNode(treeNode
* node
)
64 void TreeNodeDeleteWholeTree(treeNode
* node
)
66 if(node
== NULL
) return;
67 TreeNodeDeleteWholeTree(node
->left
);
68 TreeNodeDeleteWholeTree(node
->right
);
69 TreeNodeDeleteSingleNode(node
);
72 void TreeNodePrint(treeNode
* node
,
73 void (*keyPrint
) (void*))
75 if(node
==NULL
) return;
76 TreeNodePrint(node
->left
, keyPrint
);
78 TreeNodePrint(node
->right
, keyPrint
);
81 int TreeNodeDepth(treeNode
* root
)
83 if(root
== NULL
) return 0;
85 int leftdepth
= TreeNodeDepth(root
->left
);
86 int rightdepth
= TreeNodeDepth(root
->right
);
87 return 1 + max(leftdepth
, rightdepth
);
91 /*return the node with the key.
92 *NULL is returned if not found
94 treeNode
* TreeNodeFind(treeNode
* tree
, void* key
,
95 int (*compkey
) (void*, void*))
101 else if(compkey(key
, tree
->key
) < 0)
102 return TreeNodeFind(tree
->left
, key
, compkey
);
104 return TreeNodeFind(tree
->right
, key
, compkey
);
108 treeNode
* TreeNodeInsert(treeNode
* root
, treeNode
* newnode
,
109 int (*compkey
) (void *, void *))
113 /*going down the tree from the root.
114 *x traces the path, y is the parent of x.
118 if(compkey(newnode
->key
,x
->key
) < 0) /*if newnode < x*/
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
132 else if( compkey(newnode
->key
, y
->key
) <0)
144 treeNode
* TreeNodeDeleteSingleNode(treeNode
* tree
, treeNode
* node
)
149 if(node
==NULL
) return tree
;
151 if(node
->left
== NULL
|| node
->right
== NULL
) {
160 x
->parent
= y
->parent
;
162 if(y
->parent
== NULL
) /*y is the root which has at most one child x*/
164 else /*y is not the root*/
166 if(y
== y
->parent
->left
)
169 y
->parent
->right
= x
;
173 else { /*node has two children*/
175 y
= TreeNodeSuccessor(node
);
176 assert(y
->left
== NULL
);
178 if(y
== node
->right
) /*y is the right child if node*/
180 y
->parent
= node
->parent
;
181 y
->left
= node
->left
;
182 node
->left
->parent
= y
;
185 else /*y != node->right*/
189 x
->parent
= y
->parent
;
191 assert(y
->parent
!= NULL
);
192 if(y
== y
->parent
->left
)
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
;
203 if(node
->parent
!= NULL
) {
204 if(node
->parent
->left
== node
)
205 node
->parent
->left
= y
;
207 node
->parent
->right
= y
;
208 ret
= tree
; /*the root if the tree doesn't change*/
210 else /*node->parent is NULL: node is the root*/
214 /*finally free the node, and return the new root*/
215 TreeNodeDeleteSingleNode(node
);
220 /*the minimum node in the tree rooted by node
222 treeNode
* TreeNodeMinimum(treeNode
* node
)
224 treeNode
* temp
= node
;
225 if(temp
== NULL
) return NULL
;
226 while(temp
->left
!= NULL
) {
232 /*the maximum node in the tree rooted by node
234 treeNode
* TreeNodeMaximum(treeNode
* node
)
236 treeNode
* temp
= node
;
237 if(temp
== NULL
) return NULL
;
238 while(temp
->right
!= NULL
) {
244 /*return the first node (in sorted order) which is to the right of this node
246 treeNode
* TreeNodeSuccessor(treeNode
* node
)
248 if(node
== NULL
) return NULL
;
249 if(node
->right
!= NULL
)
250 return TreeNodeMinimum(node
->right
);
251 else{ /*node->right is NULL*/
253 /*find the first right-ancestor*/
254 treeNode
*y
= node
->parent
;
256 while(y
!= NULL
&& x
== y
->right
) /*if y is a left parent of x*/
266 /*return the first node (in sorted order) which is to the left of this node
268 treeNode
* TreeNodePredecessor(treeNode
* node
)
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
;
277 while(y
!= NULL
&& x
== y
->left
) /*if y is a right parent of x*/