Path: utzoo!mnetor!uunet!tektronix!zeus!teklds!daniels
From: daniels@teklds.TEK.COM (Scott Daniels)
Newsgroups: comp.lang.misc
Subject: Re: iteration/traversion
Message-ID: <2942@teklds.TEK.COM>
Date: 21 Mar 88 18:35:17 GMT
References: <2827@enea.se> <1557@pasteur.Berkeley.Edu> <3764@bloom-beacon.MIT.EDU> <1130@PT.CS.CMU.EDU> <3864@bloom-beacon.MIT.EDU> <Mar.20.14.47.03.1988.1079@athos.rutgers.edu>
Reply-To: daniels@teklds.UUCP (Scott Daniels)
Organization: Tektronix, Inc., Beaverton, OR.
Lines: 53

In article <Mar.20.14.47.03.1988.1079@athos.rutgers.edu> 
	gaynor@athos.rutgers.edu (Silver) writes (on iterators):
>F(Type) - The desired function to apply to elements of type.
>iterator(Type) - a function that returns the next valid element of
>	 Type according to some rule, if one exists; null otherwise
>traverser(Type) - a function that evaluates F(T), for every iteration of Type
>Supplying a function to the traverser is equivalent to:
>    while (T = iterator(Type)) do F(T)
>
In my experience of writing many similar functions, it helps to provide an
argument to pass along with the iterated type:

F(Type,Arg) - The desired function to apply to elements of type.
iterator(Type) - a function that returns the next valid element of
	 Type according to some rule, if one exists; null otherwise
traverser(Type,Arg) - a function that evaluates F(T,Arg), for every T
Supplying a function to the traverser is equivalent to:
	while (T = iterator(Type)) do F(T,Arg)

This allows one to avoid using globals to communicate with F (The arg can 
always be the address of a collection of information if more than one is 
needed)

>I can't count the number of traversals I've written like this:
>/****************************************************************\
>* preorder: apply F to every subtree of T, ordered by a preorder *
>*	    traversal						 *
>\****************************************************************/
>preorder(tree T, function F(tree))
>  if T, F(T)
>	preorder(left(T), F)
>	preorder(right(T), F)

/* preorder: apply F to every subtree of T, (preorder traversal) */
preorder( T, F, Arg )
 struct tree *T;
 void (*F)();
 void *Arg;
{
 for( ; NULL != T;T = T->right ) { F(T,Arg); preorder(T->left, F,Arg); }
}

/* preprint: print tree T in preorder to a file */
preprint( tree, file )
 FILE *f;
{
 void fprintNode();

 if( NULL == f ) f = stdout;
 preorder( T, fprintNode, f );
}

-Scott Daniels	(daniels@teklds.UUCP)