Path: utzoo!mnetor!uunet!husc6!tut.cis.ohio-state.edu!bloom-beacon!athena.mit.edu!peter
From: peter@athena.mit.edu (Peter J Desnoyers)
Newsgroups: comp.lang.misc
Subject: Re: Iterators (was Re: From Modula to Oberon)
Message-ID: <3985@bloom-beacon.MIT.EDU>
Date: 24 Mar 88 05:11:01 GMT
References: <2827@enea.se> <1557@pasteur.Berkeley.Edu> <3764@bloom-beacon.MIT.EDU> <22162@bbn.COM> <1139@PT.CS.CMU.EDU> <1147@jenny.cl.cam.ac.uk>
Sender: daemon@bloom-beacon.MIT.EDU
Reply-To: peter@athena.mit.edu (Peter J Desnoyers)
Organization: Massachusetts Institute of Technology
Lines: 59
Keywords: CLU iterators traversers
Summary: real iterators in C

[]
Since we've spent a lot of time explaining how you can iterate through
multi-element data objects in C or similar languages by using a
'traversing function' that applies a function to each element, I might
as well point out that you can (even though I cringe at the thought)
write a 'real' iterator in C. Contrast the methods used in the
following code fragments:

Iterators:
/* calculate n, sum x, sum x^^2 */
for (leaf = iter( tree, &s); leaf != NULL; leaf = iter( tree, &s)) {
    sum += leaf->size;
    sum_squared += leaf->size * leaf->size; 
    n++; }

/* yield successive elements from a tree */
iter( tree_node * t, stack ** s) {
    tree_node * tmp;

    if (* s == NULL) {
        * s = malloc( lots-o-space);
	push( *s, t); }

    if (* s is empty) {
        free( *s);
	* s = NULL;
	return (NULL); }

    for (tmp = pop( *s); !tmp->leaf; tmp = tmp->left)
      push( *s, tmp->right);
    return( tmp);
}

When done with 'traversing functions' [Is there a proper name for
these things? Please let me know if there is.] the code looks like
this: 

/* define function to be applied */
f( tree_node * t, int * sum, int * sum_squared, int * n) {
    * sum += t->size; ...}

/* apply it */
iter( tree, f, &sum, &sum_squared, &n);

/* traverser function: */
iter( tree, function, varargs stuff...) {
    if (tree->leaf)
      (*function)(leaf, varargs stuff...);
    else {
      iter( tree->right, function, ...);
      iter( tree->left, function, ...); } }


I'm not sure if this proves anything - I think the first makes more
sense, especially if I don't have to write the iterator and it runs on
a fast machine :-).


				Peter Desnoyers