/*****************************************************************************
 * File:	tree.c
 *
 * Author:	Rhett "Jonzy" Jones
 *		jonzy@cc.utah.edu
 *
 * Date:	February 27, 1993
 *
 * Modified:	March 6, 1993, by Rhett "Jonzy" Jones
 * 		to support positions, by adding InList() and BuildList().
 *		Also altered CreateBranch(), BuildTree(), and PrintTree().
 *
 *		March 9, 1993, by Rhett "Jonzy" Jones.
 *		Modified BuildList() and added DestroyList(), and
 *		NumberOfListNodes().
 *
 *		March 10, 1993, by Rhett "Jonzy" Jones.
 *		Added BinarySearch(), LessOrEqual(), and NumberOfLeafs().
 *
 *		March 13, 1993, by Rhett "Jonzy" Jones.
 *		Modified PrintTree(), so we can also print the host tree
 *		in a more readable format, and added LongestStr2tab() and
 *		PrintHostTree().
 *
 *		March 16, 1993, by Rhett "Jonzy" Jones.
 *		Changed the type returned by BinarySearch() from a short
 *		to a long.  Oops.
 *
 * Description:	Contains list, tree and binary tree routines.
 *
 * Routines:	 	short    InList(TreeType *node,long where);
 *			void	 DestroyList(ListType *list);
 *		static	void     BuildList(TreeType *node,long where);
 *		static	short	 LessOrEqual(char *a,char *b);
 *			long	 BinarySearch(char *what2Find,Element *data,long size);
 *			long	 NumberOfLeafs(TreeType *node);
 *		static	short    WhatDirection(char *s1,char *s2);
 *			TreeType *WhatBranch(TreeType *node,char *word);
 *		static	TreeType *CreateBranch(char *word,long where);
 *			void     BuildTree(TreeType **root,char *word,long where);
 *			long	 NumberOfListNodes(ListType *positions);
 *		static	int	 LongestStr2tab(Tree *node);
 *		static	void	 PrintHostTree(Tree *node,int maxHostLen);
 *			void     PrintTree(TreeType *node,int hostTree);
 *
 * Bugs:	No known bugs.
 *
 * Copyright:	Copyright 1993, University of Utah Computer Center.
 *		This source may be freely distributed as long as this copyright
 * 		notice remains intact, and is in no way used for any monetary
 * 		gain, by any institution, business, person, or persons.
 *
 ****************************************************************************/

#include <stdio.h>
#ifdef NEXT
#	include <libc.h>
#else
#	include <stdlib.h>
#endif
#include <string.h>
#include "tree.h"

#define GOLEFT		-1
#define GORITE		1
#define THISONE		0
#define MAX(a,b)	((a) > (b)) ? (a) : (b)

static short	limb = 0;		/* What limb do we insert on? */
       TreeType	*root = NIL;		/* The root of the tree. */
static TreeType	*lastNode = NIL;	/* The last tree node we looked at. */
static ListType	*lastList = NIL;	/* The last list node we looked at. */

/*****************************************************************************
 * InList return true if 'where' is already in the list of the tree nodes.
 * Otherwise if returns false.
 ****************************************************************************/
short InList(node,where)
	TreeType	*node;		/* The tree node we looking at. */
	long		where;		/* Index we are looking for. */
{	ListType	*positions;	/* List with the indexes. */

	for (positions = node->positions; positions; positions = positions->next)
		{
		lastList = positions;
		if (positions->where == where)
			return(1);
		}
	return(0);

}	/* InList */

/*****************************************************************************
 * DestroyList destroys the list 'list' by freeing up the memory occupied by
 * the enter list.
 ****************************************************************************/
void DestroyList(list)
	ListType	*list;	/* The list to destroy. */
{	ListType	*node;	/* The node to free up. */

	while (list)
		{
		node = list;
		list = list->next;
		free(node);
		}

}	/* DestroyList */

/*****************************************************************************
 * BuildList returns the head of a list which gets built.  Each node contains
 * 'where' and gets appended to the end of the list.
 ****************************************************************************/
ListType *BuildList(node,where)
	ListType	*node;		/* The tree node we looking at. */
	long		where;		/* Index we are looking for. */
{	ListType	*positions;	/* List with the positions. */

	if (positions = (ListType *)malloc(sizeof(ListType)))
		{
		positions->where = where;
		positions->next = NIL;
		if (!node)
			return(lastList = positions);
		else
			{
			lastList->next = positions;
			lastList = positions;
			return(node);
			}
		}
	else
		fprintf(stderr,"error: BuildList could not get memory for the index.\n");

}	/* BuildList */

/*****************************************************************************
 * LessOrEqual returns true if string 'a' is less than or equal to string 'b'.
 ****************************************************************************/
static short LessOrEqual(a,b)
	char	*a,	/* The first string we a comparing. */
		*b;	/* The other string we a comparing. */
{
	return(strcmp(a,b) <= 0);

}	/* LessOrEqual */

/*****************************************************************************
 * BinarySearch returns the position in 'data' where 'what2Find' exists or
 * should exist.  The search is done when 'leftBound' is greater than  or
 * equal to 'rightBounds'.
 ****************************************************************************/
long BinarySearch(what2Find,data,size)
	char	*what2Find;	/* The string we are looking for. */
	Element	*data;		/* An array of strings in sorted order. */
	long	size;		/* The number of elements in 'data'. */
{	long	leftBounds,	/* The left side of the search. */
		rightBounds,	/* The right side of the search. */
		midPoint;	/* The mid-point of the search. */

	/* Start the bounds as the entire array. */
	leftBounds = 0;
	rightBounds = size - 1;

	/* Keep finding the center of the bounds until the bounds converge. */
	while (leftBounds < rightBounds)
		if (LessOrEqual(what2Find,data[midPoint = (leftBounds + rightBounds) / 2].word))
			rightBounds = midPoint;
		else
			leftBounds = midPoint + 1;

	if (!strcmp(what2Find,data[leftBounds].word))
		return(leftBounds);
	else
		return(-1);

}	/* BinarySearch */

/*****************************************************************************
 * NumberOfLeafs returns the nuber of the leaves contained in the tree 'node'.
 ****************************************************************************/
long NumberOfLeafs(node)
	TreeType	*node;		/* The node to have printed. */
{
	if (!node)
		return(0);
	else
		return(1 + NumberOfLeafs(node->left) + NumberOfLeafs(node->right));

}	/* NumberOfLeafs */

/*****************************************************************************
 * WhatDirection returns GOLEFT if 's1' is less than 's2', returns GORITE if
 * if 's1' is greater than 's2', or returns THISONE if 's1' is the same as
 * 's2'.
 ****************************************************************************/
static short WhatDirection(s1,s2)
	char	*s1,			/* String contained in the leaf. */
		*s2;			/* String we are looking for. */
{	short	direction;		/* What direction do we look? */

	if ((direction = strcmp(s1,s2)) < 0)
		return(GOLEFT);
	else if (direction > 0)
		return(GORITE);
	else
		return(THISONE);

}	/* WhatDirection */

/*****************************************************************************
 * WhatBranch returns the limb of the tree containing 'word'.  This routine
 * also assigns to 'limb' the direction we are looking in the tree and assigns
 * to 'lastNode' the last node encountered.  These assignments are done to
 * speed the time required when building the tree.
 ****************************************************************************/
TreeType *WhatBranch(node,word)
	TreeType	*node;		/* The node we are looking at. */
	char		*word;		/* The string we are looking for. */
{
	if (!node)		/* Insert at last position. */
		return(node);
	else switch (WhatDirection(word,node->word))
		{
		case GOLEFT:
			limb = GOLEFT;
			lastNode = node;
			return(WhatBranch(node->left,word));
		case GORITE:
			limb = GORITE;
			lastNode = node;
			return(WhatBranch(node->right,word));
		case THISONE:
			return(node);
		default:
			fprintf(stderr,"warning: WhatBranch encountered bad default.\n");
		}

}	/* WhatBranch */

/*****************************************************************************
 * CreateBranch returns a node in the tree containing 'word'.
 ****************************************************************************/
static TreeType *CreateBranch(word,where)
	char		*word;		/* The string to put in this node. */
	long		where;		/* Index of the line the word is from. */
{	TreeType	*node;		/* The node we are creating. */
	ListType	*positions;	/* List with the positions. */

	if (node = (TreeType *)malloc(sizeof(TreeType)))
		if (node->word = (char *)malloc(strlen(word) + 1))
			{
			node->left = node->right = NIL;
			strcpy(node->word,word);
			if (where < 0)
				node->positions = NIL;
			else if (positions = (ListType *)malloc(sizeof(ListType)))
				{
				positions->where = where;
				positions->next = NIL;
				node->positions = positions;
				}
			else
				{
				free(node->word);
				free(node);
				node = NIL;
				fprintf(stderr,"error: CreateBranch could not get memory for the index.\n");
				}
			}
		else
			{
			free(node);
			node = NIL;
			fprintf(stderr,"error: CreateBranch could not get memory for the word [%s].\n",word);
			}
	else
		fprintf(stderr,"error: CreateBranch could not get memory for the node.\n");

	return(node);

}	/* CreateBranch */

/*****************************************************************************
 * BuildTree adds to the tree pointed to by 'root'.  No node will be added
 * to the tree if 'word' already exists in the tree.
 ****************************************************************************/
void BuildTree(root,word,where)
	TreeType	**root;		/* Root of the tree to build. */
	char		*word;		/* The string to put in the tree. */
	long		where;		/* Index of the line the word is from. */
{	TreeType	*node;		/* The node we are adding. */

	if (!*root)
		*root = CreateBranch(word,where);
	else if (!(node = WhatBranch(*root,word)))
		{
		node = CreateBranch(word,where);
		switch (limb)
			{
			case GOLEFT:
				lastNode->left = node;
				break;
			case GORITE:
				lastNode->right = node;
				break;
			default:
				fprintf(stderr,"warning: BuildTree encountered bad default.\n");
			}
		}
	else if (where >= 0)			/* Tree has a list in it. */
		if (!InList(node,where))	/* word is already in the tree. */
			node->positions = BuildList(node->positions,where);
	/* else both word and where are already in the tree. */

}	/* BuildTree */

/*****************************************************************************
 * NumberOfListNodes returns the number of nodes contained in the list
 * 'positions'.
 ****************************************************************************/
long NumberOfListNodes(positions)
	ListType	*positions;	/* List with the indexes. */
{	long		num;		/* The number of nodes found. */

	for (num = 0; positions; positions = positions->next)
		num++;
	return(num);

}	/* NumberOfListNodes */

/*****************************************************************************
 * LongestStr2tab returns the greatest number of characters prior to the tab
 * character within the tree pointed to by 'node'.  This routine is used to
 * give a formated output of the host and port contained at a given node.
 ****************************************************************************/
static int LongestStr2tab(node)
	TreeType	*node;		/* The tree we are looking at. */
{	static int	maxLen = 0;	/* Maximum length encountered. */
	int		leftLen,	/* The max len found on the left side. */
			riteLen;	/* The max len found on the right side. */

	if (!node)
		return(maxLen);
	else
		{
		leftLen = LongestStr2tab(node->left);
		riteLen = LongestStr2tab(node->right);
		maxLen  = MAX(maxLen,leftLen);
		maxLen  = MAX(maxLen,riteLen);
		maxLen  = MAX(maxLen,strchr(node->word,'\t') - node->word);
		return(maxLen);
		}

}	/* LongestStr2tab */

/*****************************************************************************
 * PrintHostTree is the routine that actualy prints the contents of the tree
 * pointed to by 'node'.  This routine prints the contents of the node such
 * that the hostname will get printed followed by the port, where the port
 * for all lines will be lined up.
 ****************************************************************************/
static void PrintHostTree(node,maxHostLen)
	TreeType	*node;		/* The node to have printed. */
	int		maxHostLen;	/* Max chars to a tab. */
{	int		len2tab;	/* Num chars to the the tab. */
	char		*tab,		/* Position of the tab. */
			*hStr,		/* The host string. */
			*pStr;		/* The port string. */

	if (!node)
		return;
	else
		{
		PrintHostTree(node->left,maxHostLen);

		/* Break the string up into the host and port parts. */
		hStr = node->word;
		len2tab = (tab = strchr(hStr,'\t')) - hStr;
		*tab = '\0';
		pStr = tab + 1;

		if (maxHostLen)
			fprintf(stdout,"%*.*s\t%8s\n",-maxHostLen,maxHostLen,hStr,pStr);
		else
			fprintf(stdout,"%s\n",hStr);

		/* Restore the information in case we want to use it again. */
		*tab = '\t';

		PrintHostTree(node->right,maxHostLen);
		}

}	/* PrintHostTree */

/*****************************************************************************
 * PrintTree is the routine that actualy prints the contents of the tree
 * pointed to by 'node'.  This routine prints the contents of the node such
 * that the hostname will get printed followed by the port, where the port
 * for all lines will be lined up.
 ****************************************************************************/
void PrintTree(node,hostTree)
	TreeType	*node;		/* The node to have printed. */
	int		hostTree;	/* Are we printing the host tree? */
{	ListType	*positions;	/* List with the positions. */
	short		strLen;		/* Length of a nodes word. */
	long		numPositions;	/* The number of positions. */

	if (hostTree)
		PrintHostTree(node,(hostTree == 2) ? LongestStr2tab(node) : 0);
	else if (!node)
		return;
	else
		{
		PrintTree(node->left,hostTree);
		fprintf(stdout,"%d\t%s",strLen = strlen(node->word) + 1,node->word);
		fprintf(stdout,"\t%ld",numPositions = NumberOfListNodes(node->positions));
		for (positions = node->positions; positions; positions = positions->next)
			fprintf(stdout,"\t%ld", positions->where);
		fprintf(stdout,"\n");
		PrintTree(node->right,hostTree);
		}

}	/* PrintTree */

