foreach vs. iterators

[BCS]

Sean Kelly wrote:
> Walter Bright wrote:
> 
>> Sean Kelly wrote:
>>
>>> I think I agree, but for the sake of argument, how would D handle 
>>> 'find'  operations on sequences that don't support opIndex?  At some 
>>> point, a generalizable bookmark is almost necessary for a faithful 
>>> implementation of some C++ algorithms.  Also, many of these 
>>> algorithms also require iteration across two sequences 
>>> simultaneously, which doesn't map very cleanly into foreach.  
>>> Consider a substring-style find operation (std::search), for example, 
>>> where both the pattern and target types do not support opIndex or 
>>> opSlice.  I might argue that it's a bit silly or unrealistic to 
>>> desire such an operation, but the C++ algorithm library does support it.
>>
>>
>> I think the target types will have to support opIndex or opSlice.
> 
> 
> Forgive me for resurrecting a horribly battered equine, but I was 
> thinking about this a bit tonight and I've decided that foreach, 
> foreach_reverse, and array operations are not a sufficient general 
> substitute for C++ iterators.
> 
> For example, let's say I want to compute the set union of two sorted 
> ranges, one of size M, the other of size N.  By iterating across the two 
> ranges simultaneously is is easy to see that the complexity for the 
> operation will be max(M,N).  In C++ this is easily accomplished using 
> forward iterators, and the ranges can be anything from arrays to SQL 
> result sets.
> 
> In D however, there is no way to iterate across multiple ranges 
> simultaneously using foreach, so opIndex must be used instead.  With 
> containers that have a constant-time lookup cost this isn't a big deal, 
> but what if these containers are binary trees?  The complexity for such 
> an operation would be M(log(M)) + N(log(N)).
> 
>  From this it seems clear that foreach is not sufficiently adaptable to 
> meet the needs of all sequential algorithms and opIndex is not a 
> reasonable substitute for all cases where foreach may not be used.  What 
> alternatives do we have?  So far, iterator variants are all I've been 
> able to come up with.
> 
> 
> Sean

I have created a monster!!!


// a class that can iterate over it's contents and another
// iterator's contents in order

class Foo
{

	// return an iterator
  int delegate(int delegate(inout U))
        opApplyWith(int delegate(inout U) t)
  {
	// make a class to form delegate
   auto ret = new class
   {
	// context
    int delegate(inout U) t;

	// iterator
    int ret(int delegate(inout U) dg)
    {
     int i=0;
	// loop on other
     foreach(inout U u, t)
     {
	// sub loop on self
      while(i<sortedUs.length && sortedUs[i] < u)
       if(int r = dg(sortedUs[i++])) return r;
      if(int r = dg(u)) return r;
     }

    }
   };
	// set context
   ret.t = t;
	// return it
   return &ret.ret;
  }

	// loop on self only
  int opApply(int delegate(inout U) dg)
  {
   foreach(inout U u, sortedUs)
   {
    if(int r = dg(sortedUs[i++])) return r;
   }
  }

	// data for class
  U[] sortedUs;
}

	// use it.
int main()
{
  Foo f1, f2;
  foreach(U u; f1.opApplyWith(&f2.opApply))
  {
   use(u);
  }
}