/*****************************************************************************
 * File:	tree.h
 *
 * Author:	Rhett "Jonzy" Jones
 *		jonzy@cc.utah.edu
 *
 * Date:	February 27, 1993
 *
 * Modifed:	March 6, 1993, by Rhett "Jonzy" Jones.
 *		to support positions.
 *
 *		March 10, 1993, by Rhett "Jonzy" Jones.
 *		Added the typedef for Element, and prototypes for
 *		BinarySearch() and NumberOfLeafs().
 *
 *		March 13, 1993, by Rhett "Jonzy" Jones.
 *		Altered the prototype for PrintTree() to now have the
 *		'hostTree' flag.
 *
 *		March 16, 1993, by Rhett "Jonzy" Jones.
 *		BinarySearch() now returns a long instead of a short.
 *
 * Description:	Header file for use with "tree.c".  Simply defines a type,
 *		prototypes a few routines, and declares a variable as
 *		extern.
 *
 * 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.
 *
 ****************************************************************************/

#define NIL		(void *)0L

typedef struct lNode { long		where;		/* The position for a word. */
		       struct lNode	*next;		/* Next position for a word. */
		     } ListType;

typedef struct tNode { char		*word;		/* A word from the display str. */
		       ListType		*positions;	/* List of positions. */
		       struct tNode	*left,		/* Left side of the tree. */
					*right;		/* Right side of the tree. */
		     } TreeType;

typedef struct { char			*word;		/* The word. */
		 ListType		*positions;	/* List of file positions. */
	       } Element;

/* The following are declared or defined in "tree.c". */
extern short	InList(TreeType *node,long where);
extern void	DestroyList(ListType *list);
extern ListType	*BuildList(ListType *node,long where);
extern long	BinarySearch(char *what2Find,Element *data,long size);
extern long	NumberOfLeafs(TreeType *node);
extern TreeType	*WhatBranch(TreeType *node,char *word);
extern void	BuildTree(TreeType **root,char *word,long where);
extern long	NumberOfListNodes(ListType *positions);
extern void	PrintTree(TreeType *node,int hostTree);

extern TreeType	*root;			/* The root of the tree. */
