{-------------------------------------------------------------}
{ routines for tree-walking.  These routines abstract the     }
{ idea of an in-order tour of the tree into a single record.  }
{ The usual algorithm for a walk is recursive (see J&W 11.5), }
{ which is not convenient for this program.		      }
{-------------------------------------------------------------}

procedure initwalk(t:pnode; var w:treewalk);
   { initialize for a walk over the given tree }
   begin
       w.current := t;	       { start at the top node,       }
       w.goneleft := false;    { ..but descend left first off }
       w.top := 0	       { stack is empty 	      }
   end;

procedure push(pn: pnode; var w: treewalk);
   { push a given node onto the walk-stack }
   begin
       if w.top<maxdepth then begin
	   w.top := w.top+1;
	   w.stack[w.top] := pn
       end
   end;

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

function treestep(var w:treewalk) : pnode;
   { step to the next node in lexical order in a tree.
       return that node as result, and save it in the walk
       record as "current."  Return nil if end of tree.       }
   var t : pnode;
   begin
       t := w.current;
       repeat
	   if not w.goneleft then begin { descend to the left }
	       if t<> nil then
		   while t^.lson<>nil do begin
		       push(t,w);
		       t := t^.lson
		   end;
	       w.goneleft := true { t^ a left-leaf of tree }
	   end
	   else { been down; have handled current; go up/right}
	       if t<> nil then
		   if t^.rson <> nil then begin
		       t := t^.rson;	    { jog right, then }
		       w.goneleft := false  { drop down again }
		   end
		   else { nowhere to go but up }
		       t := pop(w)
       until w.goneleft; { repeats when we jog right }
       w.current := t;
       treestep := t
   end;

function setscan(tree: pnode; var w: treewalk; var a: str)
						: pnode;
   { given a partial term "a," a tree "tree," and a tree-
   walk record "w," set up w so that a series of calls on
   function treestep will return all the nodes that are
   initially equal to a in ascending order.  If there are
   none such, return nil.  This function sets up for Term
   Recall when the escape key is pressed during input.

   The algorithm is to find the matching term that is
   highest in the tree, then use treestep to find the
   lexically-least node under that term (which may not be
   a match) and then to treestep to the first match.}

   var ua : str;
       p,t : pnode;
       r : relation;
       quit : boolean;
   begin
       stucase(a,ua);
       initwalk(tree,w);
       t := tree;
       if t=nil then setscan := nil  { no matches possible    }
       else begin
	   { step 1 is to find any part-equal node at all     }
	   quit := false;
	   repeat
	       r := sxcomp(ua,t^.uref);
	       case r of
		   less : if t^.lson<>nil then t := t^.lson
					  else quit := true;
		   more : if t^.rson<>nil then t := t^.rson
					  else quit := true;
		   equal : quit := true
	       end
	   until quit;
	   { If we have a match, it may not be the least one.
	     If this node has a left-son, there can be lesser
	     matches (and nonmatches) down that branch. }
	   if r<>equal then setscan := nil { no match a-tall  }
	   else begin
	       w.current := t;
	       if t^.lson=nil then w.goneleft := true
	       else begin { zoom down in tree }
		   w.goneleft := false;
		   repeat
		       t := treestep(w);
		       r := sxcomp(ua,t^.uref)
		   until r=equal
	       end;
	       setscan := t
	   end
       end
   end;
p(w);