diff options
author | Matt Turner <[email protected]> | 2012-08-23 16:39:20 -0700 |
---|---|---|
committer | Matt Turner <[email protected]> | 2012-08-31 10:58:15 -0700 |
commit | b95d598323540ecb6dbbdcf00bbb5cf3fb22a78c (patch) | |
tree | 519a3ebf1c359bb08bf01a657e4d1f9bc3c33bf2 /src/glu/sgi/libnurbs/nurbtess/searchTree.cc | |
parent | 6a7dea93fa70d670a5954e47a47075a2703209d4 (diff) |
Remove libGLU
It's been moved to its own repository, found at
http://cgit.freedesktop.org/mesa/glu/
Acked-by: Kenneth Graunke <[email protected]>
Diffstat (limited to 'src/glu/sgi/libnurbs/nurbtess/searchTree.cc')
-rw-r--r-- | src/glu/sgi/libnurbs/nurbtess/searchTree.cc | 282 |
1 files changed, 0 insertions, 282 deletions
diff --git a/src/glu/sgi/libnurbs/nurbtess/searchTree.cc b/src/glu/sgi/libnurbs/nurbtess/searchTree.cc deleted file mode 100644 index 1865755a484..00000000000 --- a/src/glu/sgi/libnurbs/nurbtess/searchTree.cc +++ /dev/null @@ -1,282 +0,0 @@ -/* -** 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 <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; - } -} |