| /* |
| ** License Applicability. Except to the extent portions of this file are |
| ** made subject to an alternative license as permitted in the SGI Free |
| ** Software License B, Version 1.1 (the "License"), the contents of this |
| ** file are subject only to the provisions of the License. You may not use |
| ** this file except in compliance with the License. You may obtain a copy |
| ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 |
| ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: |
| ** |
| ** http://oss.sgi.com/projects/FreeB |
| ** |
| ** Note that, as provided in the License, the Software is distributed on an |
| ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS |
| ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND |
| ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A |
| ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. |
| ** |
| ** Original Code. The Original Code is: OpenGL Sample Implementation, |
| ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, |
| ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. |
| ** Copyright in any portions created by third parties is as indicated |
| ** elsewhere herein. All Rights Reserved. |
| ** |
| ** Additional Notice Provisions: The application programming interfaces |
| ** established by SGI in conjunction with the Original Code are The |
| ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released |
| ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version |
| ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X |
| ** Window System(R) (Version 1.3), released October 19, 1998. This software |
| ** was created using the OpenGL(R) version 1.2.1 Sample Implementation |
| ** published by SGI, but has not been independently verified as being |
| ** compliant with the OpenGL(R) version 1.2.1 Specification. |
| ** |
| ** $Date: 2012/03/29 17:22:17 $ $Revision: 1.1.1.1 $ |
| */ |
| /* |
| ** $Header: /cvs/bao-parsec/pkgs/libs/mesa/src/src/glu/sgi/libnurbs/nurbtess/searchTree.cc,v 1.1.1.1 2012/03/29 17:22:17 uid42307 Exp $ |
| */ |
| |
| #include <stdlib.h> |
| #include <stdio.h> |
| #include "zlassert.h" |
| |
| #include "searchTree.h" |
| |
| #define max(a,b) ((a>b)? a:b) |
| |
| treeNode* TreeNodeMake(void *key) |
| { |
| treeNode *ret = (treeNode*) malloc(sizeof(treeNode)); |
| assert(ret); |
| ret->key = key; |
| ret->parent = NULL; |
| ret->left = NULL; |
| ret->right = NULL; |
| return ret; |
| } |
| |
| void TreeNodeDeleteSingleNode(treeNode* node) |
| { |
| free(node); |
| } |
| |
| void TreeNodeDeleteWholeTree(treeNode* node) |
| { |
| if(node == NULL) return; |
| TreeNodeDeleteWholeTree(node->left); |
| TreeNodeDeleteWholeTree(node->right); |
| TreeNodeDeleteSingleNode(node); |
| } |
| |
| void TreeNodePrint(treeNode* node, |
| void (*keyPrint) (void*)) |
| { |
| if(node ==NULL) return; |
| TreeNodePrint(node->left, keyPrint); |
| keyPrint(node->key); |
| TreeNodePrint(node->right, keyPrint); |
| } |
| |
| int TreeNodeDepth(treeNode* root) |
| { |
| if(root == NULL) return 0; |
| else{ |
| int leftdepth = TreeNodeDepth(root->left); |
| int rightdepth = TreeNodeDepth(root->right); |
| return 1 + max(leftdepth, rightdepth); |
| } |
| } |
| |
| /*return the node with the key. |
| *NULL is returned if not found |
| */ |
| treeNode* TreeNodeFind(treeNode* tree, void* key, |
| int (*compkey) (void*, void*)) |
| { |
| if(tree == NULL) |
| return NULL; |
| if(key == tree->key) |
| return tree; |
| else if(compkey(key, tree->key) < 0) |
| return TreeNodeFind(tree->left, key, compkey); |
| else |
| return TreeNodeFind(tree->right, key, compkey); |
| } |
| |
| |
| treeNode* TreeNodeInsert(treeNode* root, treeNode* newnode, |
| int (*compkey) (void *, void *)) |
| { |
| treeNode *y = NULL; |
| treeNode *x = root; |
| /*going down the tree from the root. |
| *x traces the path, y is the parent of x. |
| */ |
| while (x != NULL){ |
| y = x; |
| if(compkey(newnode->key,x->key) < 0) /*if newnode < x*/ |
| x = x->left; |
| else |
| x = x->right; |
| } |
| |
| /*now y has the property that |
| * if newnode < y, then y->left is NULL |
| * if newnode > y, then y->right is NULL. |
| *So we want to isnert newnode to be the child of y |
| */ |
| newnode->parent = y; |
| if(y == NULL) |
| return newnode; |
| else if( compkey(newnode->key, y->key) <0) |
| { |
| y->left = newnode; |
| } |
| else |
| { |
| y->right = newnode; |
| } |
| |
| return root; |
| } |
| |
| treeNode* TreeNodeDeleteSingleNode(treeNode* tree, treeNode* node) |
| { |
| treeNode* y; |
| treeNode* x; |
| treeNode* ret; |
| if(node==NULL) return tree; |
| |
| if(node->left == NULL || node->right == NULL) { |
| |
| y = node; |
| if(y->left != NULL) |
| x = y->left; |
| else |
| x = y->right; |
| |
| if( x != NULL) |
| x->parent = y->parent; |
| |
| if(y->parent == NULL) /*y is the root which has at most one child x*/ |
| ret = x; |
| else /*y is not the root*/ |
| { |
| if(y == y->parent->left) |
| y->parent->left = x; |
| else |
| y->parent->right = x; |
| ret = tree; |
| } |
| } |
| else { /*node has two children*/ |
| |
| y = TreeNodeSuccessor(node); |
| assert(y->left == NULL); |
| |
| if(y == node->right) /*y is the right child if node*/ |
| { |
| y->parent = node->parent; |
| y->left = node->left; |
| node->left->parent = y; |
| |
| } |
| else /*y != node->right*/ |
| { |
| x = y->right; |
| if(x!= NULL) |
| x->parent = y->parent; |
| |
| assert(y->parent != NULL); |
| if(y == y->parent->left) |
| y->parent->left = x; |
| else |
| y->parent->right = x; |
| /*move y to the position of node*/ |
| y->parent = node->parent; |
| y->left = node->left; |
| y->right = node->right; |
| node->left->parent = y; |
| node->right->parent = y; |
| } |
| if(node->parent != NULL) { |
| if(node->parent->left == node) |
| node->parent->left = y; |
| else |
| node->parent->right = y; |
| ret = tree; /*the root if the tree doesn't change*/ |
| } |
| else /*node->parent is NULL: node is the root*/ |
| ret = y; |
| } |
| |
| /*finally free the node, and return the new root*/ |
| TreeNodeDeleteSingleNode(node); |
| return ret; |
| } |
| |
| |
| /*the minimum node in the tree rooted by node |
| */ |
| treeNode* TreeNodeMinimum(treeNode* node) |
| { |
| treeNode* temp = node; |
| if(temp == NULL) return NULL; |
| while(temp->left != NULL) { |
| temp = temp->left; |
| } |
| return temp; |
| } |
| |
| /*the maximum node in the tree rooted by node |
| */ |
| treeNode* TreeNodeMaximum(treeNode* node) |
| { |
| treeNode* temp = node; |
| if(temp == NULL) return NULL; |
| while(temp->right != NULL) { |
| temp = temp->right; |
| } |
| return temp; |
| } |
| |
| /*return the first node (in sorted order) which is to the right of this node |
| */ |
| treeNode* TreeNodeSuccessor(treeNode* node) |
| { |
| if(node == NULL) return NULL; |
| if(node->right != NULL) |
| return TreeNodeMinimum(node->right); |
| else{ /*node->right is NULL*/ |
| |
| /*find the first right-ancestor*/ |
| treeNode *y = node->parent; |
| treeNode* x = node; |
| while(y != NULL && x == y->right) /*if y is a left parent of x*/ |
| { |
| |
| x = y; |
| y = y->parent; |
| } |
| return y; |
| } |
| } |
| |
| /*return the first node (in sorted order) which is to the left of this node |
| */ |
| treeNode* TreeNodePredecessor(treeNode* node) |
| { |
| if(node == NULL) return NULL; |
| if(node->left != NULL) |
| return TreeNodeMaximum(node->left); |
| else{ /*node->left is NULL*/ |
| /*find the first left-ancestor*/ |
| treeNode *y = node->parent; |
| treeNode *x = node; |
| while(y != NULL && x == y->left) /*if y is a right parent of x*/ |
| { |
| x = y; |
| y = y->parent; |
| } |
| return y; |
| } |
| } |