/*								      HTBTree.c**	BINARY TREE FOR SORTING THINGS****	(c) COPYRIGHT MIT 1995.**	Please first read the full copyright statement in the file COPYRIGH.**	@(#) $Id: HTBTree.c,v 2.25 1999/01/19 11:41:11 frystyk Exp $**** Authors:**	Arthur Secret****	4 March 94: Bug fixed in the balancing procedure***//* Library include files */#include "wwwsys.h"#include "HTUtils.h"#include "HTBTree.h"#define MAXIMUM(a,b) ((a)>(b)?(a):(b))struct _HTBTree_element {    void			*object;	/* User object */    struct _HTBTree_element	*up;    struct _HTBTree_element	*left;    int				left_depth;    struct _HTBTree_element	*right;    int				right_depth;};struct _HTBTree {    HTComparer *		compare;    struct _HTBTree_element *	top;   };PUBLIC void * HTBTree_object (HTBTElement * element){    return element ? element->object : NULL;}PUBLIC HTBTree * HTBTree_new (HTComparer * comp)    /*********************************************************    ** This function returns an HTBTree with memory allocated     ** for it when given a mean to compare things    */{    HTBTree * tree;    if ((tree = (HTBTree  *) HT_CALLOC(1, sizeof(HTBTree))) == NULL)        HT_OUTOFMEM("HTBTree_new");    tree->compare = comp;    tree->top = NULL;    return tree;}PRIVATE void HTBTElement_free (HTBTElement*  element)    /**********************************************************    ** This void will HT_FREE the memory allocated for one element    */{    if (element) {        if (element->left != NULL)    HTBTElement_free(element->left);	if (element->right != NULL)    HTBTElement_free(element->right);	HT_FREE(element);    }}PUBLIC void HTBTree_free (HTBTree*  tree)    /**************************************************************    ** This void will HT_FREE the memory allocated for the whole tree    */{    HTBTElement_free(tree->top);    HT_FREE(tree);}PRIVATE void HTBTElementAndObject_free (HTBTElement*  element)    /**********************************************************    ** This void will HT_FREE the memory allocated for one element    */{    if (element) {     /* Just in case nothing was in the tree anyway */        if (element->left != NULL)    HTBTElementAndObject_free(element->left);	if (element->right != NULL)    	    HTBTElementAndObject_free(element->right);	HT_FREE(element->object);	HT_FREE(element);    }}PUBLIC void HTBTreeAndObject_free (HTBTree*  tree)    /**************************************************************    ** This void will HT_FREE the memory allocated for the whole tree    */{    HTBTElementAndObject_free(tree->top);    HT_FREE(tree);}/*** This void is the core of HTBTree.c . It will**       1/ add a new element to the tree at the right place**          so that the tree remains sorted**       2/ balance the tree to be as fast as possible when reading it*/PUBLIC void HTBTree_add (HTBTree * tree, void * object){    HTBTElement * father_of_element;    HTBTElement * added_element;    HTBTElement * forefather_of_element;    HTBTElement * father_of_forefather;    BOOL father_found,top_found;    int depth,depth2,corrections;        /* father_of_element is a pointer to the structure that is the father of the        ** new object "object".        ** added_element is a pointer to the structure that contains or will contain         ** the new object "object".        ** father_of_forefather and forefather_of_element are pointers that are used        ** to modify the depths of upper elements, when needed.        **        ** father_found indicates by a value NO when the future father of "object"         ** is found.        ** top_found indicates by a value NO when, in case of a difference of depths        **  < 2, the top of the tree is encountered and forbids any further try to        ** balance the tree.        ** corrections is an integer used to avoid infinite loops in cases        ** such as:        **        **             3                        3        **          4                              4        **           5                            5        **        ** 3 is used here to show that it need not be the top of the tree.        */    /*    ** 1/ Adding of the element to the binary tree    */    if (tree->top == NULL)    {        if ((tree->top = (HTBTElement  *) HT_MALLOC(sizeof(HTBTElement))) == NULL)            HT_OUTOFMEM("HTBTree_add");        tree->top->up = NULL;        tree->top->object = object;        tree->top->left = NULL;        tree->top->left_depth = 0;        tree->top->right = NULL;        tree->top->right_depth = 0;    }    else    {           father_found = YES;        father_of_element = tree->top;        added_element = NULL;        father_of_forefather = NULL;        forefather_of_element = NULL;              while (father_found)        {            if (tree->compare(object,father_of_element->object)<0)	    {                if (father_of_element->left != NULL)                    father_of_element = father_of_element->left;                else 	        {                    father_found = NO;                    if ((father_of_element->left = (HTBTElement  *) HT_MALLOC(sizeof(HTBTElement))) == NULL)                        HT_OUTOFMEM("HTBTree_add");                    added_element = father_of_element->left;                    added_element->up = father_of_element;                    added_element->object = object;                    added_element->left = NULL;                    added_element->left_depth = 0;                    added_element->right = NULL;                    added_element->right_depth = 0;                }   	    }            if (tree->compare(object,father_of_element->object)>=0)            {                if (father_of_element->right != NULL)                     father_of_element = father_of_element->right;                else                 {                      father_found = NO;                    if ((father_of_element->right = (HTBTElement  *) HT_MALLOC(sizeof(HTBTElement))) == NULL)                        HT_OUTOFMEM("father_of_element->right ");                    added_element = father_of_element->right;                    added_element->up = father_of_element;                    added_element->object = object;                    added_element->left = NULL;                    added_element->left_depth = 0;                    added_element->right = NULL;                    added_element->right_depth = 0;           	        }            }	}            /*            ** Changing of all depths that need to be changed            */        father_of_forefather = father_of_element;        forefather_of_element = added_element;        do        {            if (father_of_forefather->left == forefather_of_element)            {                depth = father_of_forefather->left_depth;                father_of_forefather->left_depth = 1                             + MAXIMUM(forefather_of_element->right_depth,                                  forefather_of_element->left_depth);                depth2 = father_of_forefather->left_depth;            }            else	    {                depth = father_of_forefather->right_depth;                father_of_forefather->right_depth = 1                            + MAXIMUM(forefather_of_element->right_depth,                                  forefather_of_element->left_depth);                depth2 = father_of_forefather->right_depth;            }            forefather_of_element = father_of_forefather;            father_of_forefather = father_of_forefather->up;        } while ((depth != depth2) && (father_of_forefather != NULL));                    /*            ** 2/ Balancing the binary tree, if necessary	    ** Bugs in this part have been fixed in March 94  -  AS            */        top_found = YES;        corrections = 0;        while ((top_found) && (corrections < 7))        {            if ((abs(father_of_element->left_depth                      - father_of_element->right_depth)) < 2)	    {                if (father_of_element->up != NULL)                     father_of_element = father_of_element->up;                else top_found = NO;	    }            else 	    {                /* We start the process of balancing */                corrections = corrections + 1;                    /*                     ** corrections is an integer used to avoid infinite                     ** loops in cases such as:                    **                    **             3                        3                    **          4                              4                    **           5                            5                    **                    ** 3 is used to show that it need not be the top of the tree		    ** But let's avoid these two exceptions anyhow 		    ** with the two following conditions (March 94 - AS)                    */		if ((father_of_element->left == NULL) 		    && (father_of_element->right->right == NULL) 		    && (father_of_element->right->left->left == NULL) 		    && (father_of_element->right->left->right == NULL)) 		    corrections = 7;		if ((father_of_element->right == NULL) 		    && (father_of_element->left->left == NULL) 		    && (father_of_element->left->right->right == NULL) 		    && (father_of_element->left->right->left == NULL))		    corrections = 7;                 if (father_of_element->left_depth > father_of_element->right_depth)	        {                    added_element = father_of_element->left;                    father_of_element->left_depth = added_element->right_depth;                    added_element->right_depth = 1                                    + MAXIMUM(father_of_element->right_depth,                                          father_of_element->left_depth);                    if (father_of_element->up != NULL)		    {			/* Bug fixed in March 94  */			BOOL first_time;                        father_of_forefather = father_of_element->up;                        forefather_of_element = added_element;			first_time = YES;                        do                         {                            if (father_of_forefather->left                                 == forefather_of_element->up)                              {				  depth = father_of_forefather->left_depth;				  if (first_time)				  {				      father_of_forefather->left_depth = 1					  + MAXIMUM(forefather_of_element->left_depth,						  forefather_of_element->right_depth);					first_time = NO;				   }				   else				       father_of_forefather->left_depth = 1					   + MAXIMUM(forefather_of_element->up->left_depth,					      forefather_of_element->up->right_depth);                                depth2 = father_of_forefather->left_depth;			    }                            else			    {                                depth = father_of_forefather->right_depth;				if (first_time)				{				    father_of_forefather->right_depth = 1				      + MAXIMUM(forefather_of_element->left_depth,					       forefather_of_element->right_depth);				    first_time = NO;				}								else				    father_of_forefather->right_depth = 1				      + MAXIMUM(forefather_of_element->up->left_depth,					   forefather_of_element->up->right_depth);                                depth2 = father_of_forefather->right_depth;			    }                            forefather_of_element = forefather_of_element->up;                            father_of_forefather = father_of_forefather->up;			} while ((depth != depth2) && 				 (father_of_forefather != NULL));                        father_of_forefather = father_of_element->up;                        if (father_of_forefather->left == father_of_element)	                {                            /*                            **                   3                       3                            **               4                       5                            ** When tree   5   6        becomes    7    4                            **            7 8                          8 6                            **                            ** 3 is used to show that it may not be the top of the                            ** tree.                            */                             father_of_forefather->left = added_element;                            father_of_element->left = added_element->right;                            added_element->right = father_of_element;                        }                        if (father_of_forefather->right == father_of_element)		        {                            /*                            **          3                       3                            **               4                       5                            ** When tree   5   6        becomes    7    4                            **            7 8                          8 6                            **                            ** 3 is used to show that it may not be the top of the                            ** tree                            */