+++ /dev/null
-/*
-** 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;
- }
-}
projects / mesa.git / blobdiff