/*
   This file was derived from the libwww code, version 2.15, from CERN.
   A number of modifications have been made by Spyglass.

   eric@spyglass.com
 */
/*                  Binary Tree for sorting things
   **                  ==============================
   **                      Author: Arthur Secret
   **
   **       4 March 94: Bug fixed in the balancing procedure
   **
 */

#include "all.h"

#define MAXIMUM(a,b) ((a)>(b)?(a):(b))

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 = (HTBTree *) GTR_MALLOC(sizeof(HTBTree));
	if (tree != NULL)
	{
		tree->compare = comp;
		tree->top = NULL;
	}
	return tree;
}




PRIVATE void HTBTElement_free(HTBTElement * element)
	/**********************************************************
    ** This void will 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);
		GTR_FREE(element);
	}
}

PUBLIC void HTBTree_free(HTBTree * tree)
	/**************************************************************
    ** This void will free the memory allocated for the whole tree
    */
{
	HTBTElement_free(tree->top);
	GTR_FREE(tree);
}




PRIVATE void HTBTElementAndObject_free(HTBTElement * element)
	/**********************************************************
    ** This void will 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);
		GTR_FREE(element->object);
		GTR_FREE(element);
	}
}

PUBLIC void HTBTreeAndObject_free(HTBTree * tree)
	/**************************************************************
    ** This void will free the memory allocated for the whole tree
    */
{
	HTBTElementAndObject_free(tree->top);
	GTR_FREE(tree);
}


/* TODO: The memory handling here might be a little unreliable in extreme
   low-memory conditions.  I recommend we just nuke this entire file and
   replace the BTree with a flat list, since it's only used for reading
   FTP directories anyway. - JLS */

PUBLIC void HTBTree_add(HTBTree * tree, void *object)
	/**********************************************************************
    ** 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
    */
{
	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)
	{
		tree->top = (HTBTElement *) GTR_MALLOC(sizeof(HTBTElement));
		if (tree->top != NULL)
		{
			XX_DMsg(DBG_WWW, ("HTBTree_add: can't allocate tree->top\n"));

			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
			XX_DMsg(DBG_WWW, ("HTBTree_add: can't allocate tree->top\n"));
	}
	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;
					father_of_element->left = (HTBTElement *) GTR_MALLOC(sizeof(HTBTElement));
					if (father_of_element->left != NULL)
					{
						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;
					}
					else
						XX_DMsg(DBG_WWW, ("HTBTree_add: can't allocate father_of_element->left\n"));
				}
			}
			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;
					father_of_element->right =
						(HTBTElement *) GTR_MALLOC(sizeof(HTBTElement));
					if (father_of_element->right != NULL)
					{
						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;
					}
					else
						XX_DMsg(DBG_WWW, ("HTBTree_add: can't allocate father_of_element->right\n"));
				}
			}
		}
		/*
		   ** 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
		 */
		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 (4 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  -  AS */
						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
							 */
							father_of_forefather->right = added_element;
							father_of_element->left = added_element->right;
							added_element->right = father_of_element;
						}
						added_element->up = father_of_forefather;
					}
					else
					{
						/*
						   **
						   **               1                       2
						   ** When tree   2   3        becomes    4    1
						   **            4 5                          5 3
						   **
						   ** 1 is used to show that it is the top of the tree    
						 */
						added_element->up = NULL;
						father_of_element->left = added_element->right;
						added_element->right = father_of_element;
					}
					father_of_element->up = added_element;
					if (father_of_element->left != NULL)
						father_of_element->left->up = father_of_element;
				}
				else
				{
					added_element = father_of_element->right;
					father_of_element->right_depth = added_element->left_depth;
					added_element->left_depth = 1 +
						MAXIMUM(father_of_element->right_depth,
								father_of_element->left_depth);
					if (father_of_element->up != NULL)
						/* Bug fixed in March 94  -  AS */
					{
						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;
							}
							father_of_forefather = father_of_forefather->up;
							forefather_of_element = forefather_of_element->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                       6
							   ** When tree   5   6        becomes    4    8
							   **                7 8                 5 7
							   **
							   ** 3 is used to show that it may not be the top of the
							   ** tree.
							 */
							father_of_forefather->left = added_element;
							father_of_element->right = added_element->left;
							added_element->left = father_of_element;
						}
						if (father_of_forefather->right == father_of_element)
						{
							/*
							   **           3                      3
							   **               4                       6
							   ** When tree   5   6        becomes    4    8
							   **                7 8                 5 7
							   **
							   ** 3 is used to show that it may not be the top of the
							   ** tree
							 */
							father_of_forefather->right = added_element;
							father_of_element->right = added_element->left;
							added_element->left = father_of_element;
						}
						added_element->up = father_of_forefather;
					}
					else
					{
						/*
						   **
						   **               1                       3
						   ** When tree   2   3        becomes    1    5
						   **                4 5                 2 4
						   **
						   ** 1 is used to show that it is the top of the tree.
						 */
						added_element->up = NULL;
						father_of_element->right = added_element->left;
						added_element->left = father_of_element;
					}
					father_of_element->up = added_element;
					if (father_of_element->right != NULL)
						father_of_element->right->up = father_of_element;
				}
			}
		}
		while (father_of_element->up != NULL)
		{
			father_of_element = father_of_element->up;
		}
		tree->top = father_of_element;
	}
}



PUBLIC HTBTElement *HTBTree_next(HTBTree * tree, HTBTElement * ele)
	/**************************************************************************
    ** this function returns a pointer to the leftmost element if ele is NULL,
    ** and to the next object to the right otherways.
    ** If no elements left, returns a pointer to NULL.
    */
{
	HTBTElement *father_of_element;
	HTBTElement *father_of_forefather;

	if (ele == NULL)
	{
		father_of_element = tree->top;
		if (father_of_element != NULL)
			while (father_of_element->left != NULL)
				father_of_element = father_of_element->left;
	}
	else
	{
		father_of_element = ele;
		if (father_of_element->right != NULL)
		{
			father_of_element = father_of_element->right;
			while (father_of_element->left != NULL)
				father_of_element = father_of_element->left;
		}
		else
		{
			father_of_forefather = father_of_element->up;
			while (father_of_forefather &&
				   (father_of_forefather->right == father_of_element))
			{
				father_of_element = father_of_forefather;
				father_of_forefather = father_of_element->up;
			}
			father_of_element = father_of_forefather;
		}
	}
#ifdef BTREE_TRACE
	/* The option -DBTREE_TRACE will give much more information
	   ** about the way the process is running, for debugging matters
	 */
	if (father_of_element != NULL)
	{
		printf("\nObject = %s\t", (char *) father_of_element->object);
		if (father_of_element->up != NULL)
			printf("Objet du pere = %s\n",
				   (char *) father_of_element->up->object);
		else
			printf("Pas de Pere\n");
		if (father_of_element->left != NULL)
			printf("Objet du fils gauche = %s\t",
				   (char *) father_of_element->left->object);
		else
			printf("Pas de fils gauche\t");
		if (father_of_element->right != NULL)
			printf("Objet du fils droit = %s\n",
				   (char *) father_of_element->right->object);
		else
			printf("Pas de fils droit\n");
		printf("Profondeur gauche = %i\t", father_of_element->left_depth);
		printf("Profondeur droite = %i\n", father_of_element->right_depth);
		printf("      **************\n");
	}
#endif
	return father_of_element;
}


#ifdef TEST
main()
	/******************************************************
    ** This is just a test to show how to handle HTBTree.c
    */
{
	HTBTree *tree;
	HTBTElement *next_element;

	tree = HTBTree_new((HTComparer) strcasecmp);
	HTBTree_add(tree, "hypertext");
	HTBTree_add(tree, "Addressing");
	HTBTree_add(tree, "X11");
	HTBTree_add(tree, "Tools");
	HTBTree_add(tree, "Proposal.wn");
	HTBTree_add(tree, "Protocols");
	HTBTree_add(tree, "NeXT");
	HTBTree_add(tree, "Daemon");
	HTBTree_add(tree, "Test");
	HTBTree_add(tree, "Administration");
	HTBTree_add(tree, "LineMode");
	HTBTree_add(tree, "DesignIssues");
	HTBTree_add(tree, "MarkUp");
	HTBTree_add(tree, "Macintosh");
	HTBTree_add(tree, "Proposal.rtf.wn");
	HTBTree_add(tree, "FIND");
	HTBTree_add(tree, "Paper");
	HTBTree_add(tree, "Tcl");
	HTBTree_add(tree, "Talks");
	HTBTree_add(tree, "Architecture");
	HTBTree_add(tree, "VMSHelp");
	HTBTree_add(tree, "Provider");
	HTBTree_add(tree, "Archive");
	HTBTree_add(tree, "SLAC");
	HTBTree_add(tree, "Project");
	HTBTree_add(tree, "News");
	HTBTree_add(tree, "Viola");
	HTBTree_add(tree, "Users");
	HTBTree_add(tree, "FAQ");
	HTBTree_add(tree, "WorkingNotes");
	HTBTree_add(tree, "Windows");
	HTBTree_add(tree, "FineWWW");
	HTBTree_add(tree, "Frame");
	HTBTree_add(tree, "XMosaic");
	HTBTree_add(tree, "People");
	HTBTree_add(tree, "All");
	HTBTree_add(tree, "Curses");
	HTBTree_add(tree, "Erwise");
	HTBTree_add(tree, "Carl");
	HTBTree_add(tree, "MidasWWW");
	HTBTree_add(tree, "XPM");
	HTBTree_add(tree, "MailRobot");
	HTBTree_add(tree, "Illustrations");
	HTBTree_add(tree, "VMClient");
	HTBTree_add(tree, "XPA");
	HTBTree_add(tree, "Clients.html");
	HTBTree_add(tree, "Library");
	HTBTree_add(tree, "CERNLIB_Distribution");
	HTBTree_add(tree, "libHTML");
	HTBTree_add(tree, "WindowsPC");
	HTBTree_add(tree, "tkWWW");
	HTBTree_add(tree, "tk2.3");
	HTBTree_add(tree, "CVS-RCS");
	HTBTree_add(tree, "DecnetSockets");
	HTBTree_add(tree, "SGMLStream");
	HTBTree_add(tree, "NextStep");
	HTBTree_add(tree, "CVSRepository_old");
	HTBTree_add(tree, "ArthurSecret");
	HTBTree_add(tree, "CVSROOT");
	HTBTree_add(tree, "HytelnetGate");
	HTBTree_add(tree, "cern.www.new.src");
	HTBTree_add(tree, "Conditions");
	HTBTree_add(tree, "HTMLGate");
	HTBTree_add(tree, "Makefile");
	HTBTree_add(tree, "Newsgroups.html");
	HTBTree_add(tree, "People.html");
	HTBTree_add(tree, "Bugs.html");
	HTBTree_add(tree, "Summary.html");
	HTBTree_add(tree, "zDesignIssues.wn");
	HTBTree_add(tree, "HT.draw");
	HTBTree_add(tree, "HTandCERN.wn");
	HTBTree_add(tree, "Ideas.wn");
	HTBTree_add(tree, "MarkUp.wn");
	HTBTree_add(tree, "Proposal.html");
	HTBTree_add(tree, "SearchPanel.draw");
	HTBTree_add(tree, "Comments.wn");
	HTBTree_add(tree, "Xanadu.html");
	HTBTree_add(tree, "Storinglinks.html");
	HTBTree_add(tree, "TheW3Book.html");
	HTBTree_add(tree, "Talk_Feb-91.html");
	HTBTree_add(tree, "JFosterEntry.txt");
	HTBTree_add(tree, "Summary.txt");
	HTBTree_add(tree, "Bibliography.html");
	HTBTree_add(tree, "HTandCern.txt");
	HTBTree_add(tree, "Talk.draw");
	HTBTree_add(tree, "zDesignNotes.html");
	HTBTree_add(tree, "Link.html");
	HTBTree_add(tree, "Status.html");
	HTBTree_add(tree, "http.txt");
	HTBTree_add(tree, "People.html~");
	HTBTree_add(tree, "TAGS");
	HTBTree_add(tree, "summary.txt");
	HTBTree_add(tree, "Technical.html");
	HTBTree_add(tree, "Terms.html");
	HTBTree_add(tree, "JANETAccess.html");
	HTBTree_add(tree, "People.txt");
	HTBTree_add(tree, "README.txt");
	HTBTree_add(tree, "CodingStandards.html");
	HTBTree_add(tree, "Copyright.txt");
	HTBTree_add(tree, "Status_old.html");
	HTBTree_add(tree, "patches~");
	HTBTree_add(tree, "RelatedProducts.html");
	HTBTree_add(tree, "Implementation");
	HTBTree_add(tree, "History.html");
	HTBTree_add(tree, "Makefile.bak");
	HTBTree_add(tree, "Makefile.old");
	HTBTree_add(tree, "Policy.html");
	HTBTree_add(tree, "WhatIs.html");
	HTBTree_add(tree, "TheProject.html");
	HTBTree_add(tree, "Notation.html");
	HTBTree_add(tree, "Helping.html");
	HTBTree_add(tree, "Cyber-WWW.sit.Hqx");
	HTBTree_add(tree, "Glossary.html");
	HTBTree_add(tree, "maketags.html");
	HTBTree_add(tree, "IntroCS.html");
	HTBTree_add(tree, "Contrib");
	HTBTree_add(tree, "Help.html");
	HTBTree_add(tree, "CodeManagExec");
	HTBTree_add(tree, "HT-0.1draz");
	HTBTree_add(tree, "Cello");
	HTBTree_add(tree, "TOPUB");
	HTBTree_add(tree, "BUILD");
	HTBTree_add(tree, "BUILDALL");
	HTBTree_add(tree, "Lynx");
	HTBTree_add(tree, "ArthurLibrary");
	HTBTree_add(tree, "RashtyClient");
	HTBTree_add(tree, "#History.html#");
	HTBTree_add(tree, "PerlServers");
	HTBTree_add(tree, "modules");
	HTBTree_add(tree, "NCSA_httpd");
	HTBTree_add(tree, "MAIL2HTML");
	HTBTree_add(tree, "core");
	HTBTree_add(tree, "EmacsWWW");
#ifdef BTREE_TRACE
	printf("\nTreeTopObject=%s\n\n", tree->top->object);
#endif
	next_element = HTBTree_next(tree, NULL);
	while (next_element != NULL)
	{
#ifndef BTREE_TRACE
		printf("The next element is %s\n", next_element->object);
#endif
		next_element = HTBTree_next(tree, next_element);
	}
	HTBTree_free(tree);
}


#endif
