From a0c4815433ccd57322f4f7703ca35e9ccfa59250 Mon Sep 17 00:00:00 2001 From: marha Date: Thu, 8 Oct 2009 13:15:52 +0000 Subject: Added MesaLib-7.6 --- .../src/glu/sgi/libnurbs/nurbtess/searchTree.cc | 282 +++++++++++++++++++++ 1 file changed, 282 insertions(+) create mode 100644 mesalib/src/glu/sgi/libnurbs/nurbtess/searchTree.cc (limited to 'mesalib/src/glu/sgi/libnurbs/nurbtess/searchTree.cc') diff --git a/mesalib/src/glu/sgi/libnurbs/nurbtess/searchTree.cc b/mesalib/src/glu/sgi/libnurbs/nurbtess/searchTree.cc new file mode 100644 index 000000000..1865755a4 --- /dev/null +++ b/mesalib/src/glu/sgi/libnurbs/nurbtess/searchTree.cc @@ -0,0 +1,282 @@ +/* +** 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. +** +*/ +/* +*/ + +#include +#include +#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; + } +} -- cgit v1.2.3