{==============================================================}
{			IXTREE.PAS			       }
{Copyright (C) 1986 David E. Cortesi--see notice in IXMAIN.PAS.}
{							       }
{ This include-file contains declarations and code related to  }
{ the implementation of nested trees of index terms.  A tree   }
{ is a network of dynamically-allocated nodes in the structure }
{ of a binary tree.  Terms are only inserted to the tree, no   }
{ deletions are supported.  However, the tree is kept balanced }
{ under insertions using a recursive method of my own.	 This  }
{ dynamic rebalancing keeps the tree optimal (time to locate a }
{ node is never worse than log2 N) regardless of the order in  }
{ which terms are entered.  This in turn permits loading of the}
{ tree directly from a previous index text file, even though   }
{ the terms in an index document are in ascending sequence.    }
{							       }
{ Each tree node represents one index term. The term itself is }
{ stored two ways, as typed and in dictionary-comparison form, }
{ a form that compares "Half Way" equal to "halfway".  A node  }
{ anchors a sorted chain of page-numbers, and may hold the root}
{ of an independent sub-tree of sub-terms. The tree is ordered }
{ so that all terms in cnodes[left] are less than, and all in  }
{ cnodes[right] are greater, than this term.		       }
{ History:						       }
{  fix bug that caused loop/crash when adding C to tree with   }
{  items A,B,D,E,F -- 11/2/86				       }
{==============================================================}

{------ create a new tree node to hold the term in string A ---}
{------ and its dictionary form, string D, returing address ---}
function makenode(var a, d : str) : tree;
var	t : tree;
begin
    new(t);
    with t^ do begin
	cnodes[left] := nil;
	cnodes[right] := nil;
	cdepth[left] := 0;
	cdepth[right] := 0;
	subtree := nil;
	stput(a,term);
	stput(d,dict);
	pages := nil;
    end;
    makenode := t
end;

{------ return the depth of tree T: one more than the larger --}
{------ of the depths of its children -------------------------}
function depthof(t: tree):tdepth;
begin
    with t^ do
	if (cdepth[left] > cdepth[right]) then
	    depthof := 1 + cdepth[left]
	else
	    depthof := 1 + cdepth[right]
end;
{------ look for the term in string A in the tree T. Return ---}
{------ the addr of the found node, or NIL if not found. This--}
{------ routine is quick because nonrecursive. ----------------}
function lookup(var d: str; {in} t : tree) : tree;
var	p : tree; r : relation;
begin
    p := t;
    if (p <> nil) then
	repeat
	    r := stbcmpx(d,p^.dict);
	    case r of
		less: p := p^.cnodes[left];
		equal: ;
		more: p := p^.cnodes[right];
	    end
	until ((r = equal) or (p = nil));
    lookup := p
end;

{------ insert the tree N into the tree T.  this is used when -}
{------ a term was not found by lookup and must be put into  --}
{------ the tree as a node.  The result of the function is NOT-}
{------ the inserted node, but the NEW TOP NODE of the tree ---}
{------ after rebalancing it: either T or its n-side child. ---}
function tinsert( n, {into} t : tree) : tree;
var	s,o : sides; p,q : tree;
begin
    if (t = nil) then tinsert := n
    else begin
	s := right; { assume adding in increasing order }
	o := left;
	if (sbbcmpx(n^.dict,t^.dict) = less) then
	    begin s := left; o := right end;
	with t^ do begin
	    cnodes[s] := tinsert(n,cnodes[s]);
	    cdepth[s] := depthof(cnodes[s]);
	    if (1 < (cdepth[s]-cdepth[o]))
 {tree is unbalanced toward side s but there's no point in }
 {attempting balance at the current level when subtree s   }
 {is itself in perfect balance -- defer to higher level    }
 {unless subtree s is unbalanced and might improve.	   }
	      and (cnodes[s]^.cdepth[left] <>
			    cnodes[s]^.cdepth[right]) then begin
 {rebalance tree by snipping off the parent at this level  }
 {and its side-o subtree and reinserting that tree into its}
 {former child, subtree s.				   }
		p := cnodes[s];
		cnodes[s] := nil;
		cdepth[s] := 0;
		p := tinsert(t, {into} p)
	    end
	    else p := t
	end;
	tinsert := p
    end
end;

{------ look for term A in tree T and, if it isn't found, put -}
{------ it there, rebalancing the tree as needed.  Return -----}
{------ the address of the node found or inserted.  -----------}
function insert(var a: str; {into} var t : tree) : tree;
var d: str; p: tree;
begin
    stucase(a,d);
    p := lookup(d,t);
    if (p = nil) then begin {insert it}
	p := makenode(a,d);
	t := tinsert(p,t)
    end;
    insert := p
end;
kup(d,t);
    if (p = nil) then begin {insert it}
	p := 