aboutsummaryrefslogtreecommitdiff
path: root/mesalib/src/glu/sgi/libnurbs/nurbtess/searchTree.cc
diff options
context:
space:
mode:
Diffstat (limited to 'mesalib/src/glu/sgi/libnurbs/nurbtess/searchTree.cc')
-rw-r--r--mesalib/src/glu/sgi/libnurbs/nurbtess/searchTree.cc282
1 files changed, 282 insertions, 0 deletions
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 <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;
+ }
+}