{-------------------------------------------------------------}
{			IXWALK.PAS			      }
{Copyright (C) 1986 David E. Cortesi--see notice in IXMAIN.PAS.}
{							      }
{ This include file contains the code for tree-walking.  The  }
{ "term recall" feature of the program (see IX.DOC) works by  }
{ finding the lexically-least term matching some argument,    }
{ and performing an in-order walk of the tree from that point.}
{ During output we walk all nodes of all trees. 	      }
{ The usual algorithm for a walk is recursive (see J&W 11.5), }
{ which is not convenient for this program.  During output,   }
{ there will be walks going on in main and subtrees, so the   }
{ walk position is remembered in a dynamic record.	      }
{ History:						      }
{ initial code 6/2/86					      }
{-------------------------------------------------------------}

{------ push node T onto the walk-stack for later use ---------}
procedure wpush(t : tree; var w : walk);
begin
    if (w.top < maxdepth) then begin
	w.top := w.top + 1;
	w.stack[w.top] := t
    end
end;

{------ pop the top node of the walk-stack --------------------}
function wpop(var w : walk) : tree;
begin
    if (w.top > 0) then begin
	wpop := w.stack[w.top];
	w.top := w.top - 1
    end
    else wpop := nil
end;

{------ initialize to walk a tree T by clearing the stack ----}
{------ and pointing to the top node, then descending to the -}
{------ lowest, leftmost node and returning it	--------------}
function initwalk(t : tree; var w : walk) : tree;
var p : tree;
begin
    w.top := 0;
    p := t;
    while (p <> nil) do begin
	wpush(p,w);
	p := p^.cnodes[left]
    end;
    w.curr := wpop(w);
    initwalk := w.curr
end;

{------ step to the next node of a tree in lexical order. ----}
{------ return that next node as result, and save it as the --}
{------ current step.  Return nil at end of tree. ------------}
function wstep(var w : walk) : tree;
var wleft : boolean;
begin
    wleft := false; { have handled w.curr and its left subtree}
    if (w.curr <> nil) then begin
	if (w.curr^.cnodes[right] <> nil) then begin
	    { it has a right subtree, so enter it and.. }
	    w.curr := w.curr^.cnodes[right];
	    wleft := true { ..then plunge down again }
	end
	else { nowhere to go but up } w.curr := wpop(w)
    end;
    if (wleft) then { plunge down to the left }
	while (w.curr^.cnodes[left] <> nil) do begin
	    wpush(w.curr,w);
	    w.curr := w.curr^.cnodes[left]
	end;
    wstep := w.curr
end;

{------ Given a partial term (upcased) in D and a tree T, -----}
{------ set up so that a series of WSTEP calls will return all }
{------ nodes initially equal to A.  Return the first such, or }
{------ nil if the tree is null or has no terms matching A. ---}
function setscan(t : tree; var d : str; var w : walk) : tree;
var
    p : tree;
    r : relation;
    quit : boolean;
begin
    if (t = nil) then setscan := nil	{ no matches possible  }
    else begin
	{ first, find any part-equal node at all }
	p := t;
	repeat
	    r := stbcmpa(d,p^.dict);
	    case r of
		less : p := p^.cnodes[left];
		more : p := p^.cnodes[right];
		equal : ;
	    end
	until (r = equal) or (p = nil);
	if (r <> equal) then setscan := nil { no match a-tall }
	else begin
	    {-- node P is the highest match, none above it in
	    the tree match, but there may be lesser and greater
	    matches in its left and right children.  Set up to
	    walk the tree of which P is the root.  InitWalk will
	    return the least leaf of P and walking from
	    there to the first match to A will give the least
	    match to A (which may be the one in P) --}
	    p := initwalk(p,w);
	    repeat
		r := stbcmpa(d,p^.dict);
		if (r <> equal) then p := wstep(w)
	    until (r = equal);
	    setscan := p
	end
    end
end;
:= stbcmpa(d,p^.dict);
		if (r <> equal) then p := wstep(w)
	    until (r = equa