Iterators for D

[Chris Nicholson-Sauls]

Knud Sørensen wrote:
> On Mon, 06 Nov 2006 12:46:01 -0800, Walter Bright wrote:
> 
> 
>>It's becoming increasingly obvious that D needs iterators. While opApply 
>>  is far better for some kinds of iteration (such as recursively 
>>traversing a directory), iterators are more efficient in some cases, and 
>>allow for things that opApply makes difficult.
>>
> 
> 
> What are those cases ? Maybe we can find a way to fix the problem with
> opApply.
> 

Mostly agreed.  For example, one case I seem to find mentioned a few times is providing 
depth-first versus breadth-first iteration on a tree -- supposedly this is hard to do with 
foreach/opApply.  While I do agree that opApply is not optimal (because you can't tell 
opApply which way you want to go) I thought this was part of the utility of the recent 
delegates-as-aggregates feature?  The following is just off the very top of my head, so it 
might not be ideal/perfect, but I do believe it provides this ability, using current D:

<code>
struct Tree(int B = 2, T) {
   version (Tree_NoWarnings) {}
   else {
     static if (B == 0) {
       static assert(false, "A tree with zero branches is just useless.");
     }
     else static if (B == 1) {
       static assert(false, "A tree with only one branch may as well be an array.");
     }
   }

   Tree*[B] children ;
   T        value    ;

   int walkDepth (int delegate(inout Tree!(T)) dlg) {
     int result ;

     foreach (x; children) {
       if (x && result = x.walkDepth(dlg)) {
         goto end;
       }
     }
     if (result = dlg(this)) {
       goto end;
     }

     end:
       return result;
   }

   int walkBreadth (int delegate(inout Tree!(T)) dlg) {
     int         result          ;
     Tree!(T)*[] gen    = [this] ,
                 next            ;

     while (gen.length) {
       foreach (x; gen) {
         if (result = dlg(x.value)) {
           goto end;
         }
         foreach (y; x.children) {
           if (y) {
             next ~= y;
           }
         }
       }
       gen = next.dup;
       next.length = 0;
     }

     end:
       return result;
   }
}

Tree!(2, int) binary_int_tree ;
// ...
foreach (node; &binary_int_tree.walkDepth) {
   // ...
}
foreach (node; &binary_int_tree.walkBreadth) {
   // ...
}
</code>

Unless I'm missing something entirely, I don't see any major utility in this case for 
having a seperate Iterator entity...

-- Chris Nicholson-Sauls