svn merge ^/branches/released . --username marha

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;
+  }
+}