Iterators for D

[Daniel Keep]

Bill Baxter wrote:
> Daniel Keep wrote:
>>
>> Walter Bright wrote:
>>> Sean Kelly wrote:
>>>> Since D has slicing, the argument for using iterators to define the
>>>> boundaries of a range of randomly accessible elements seems kind of
>>>> small to me.  ie.
>>>>
>>>>     sort( a.begin, a.begin + 5 ); // sort the first 5 elements
>>>> or
>>>>     sort( a[0 .. 5] );
>>>>
>>>> I find the second to be cleaner to look at.  But I'm undecided whether
>>>> we'd lose any power or flexibility by not bothering with random access
>>>> iterators.
>>> Hmm, instead of 'pointers as iterators', have 'arrays as iterators'.
>>> That definitely sounds like a good area to explore.
>>
>> Hang on; aren't we back to where we are *right now*?
> 
> Close, but right now we don't have a good way to iterate over multiple
> things at once.
>   for(i,j; i.hasNext()&&j.hasNext(); i++,j++)
>   {
>      // do something with current values of i and j
>   }
> 
> Or as you say to stop iteration or a generic way to return a pointer to
> a particular spot in a container.
> 
>> About the only thing this *doesn't* cover are bi-directional iterators
>> (say, iterating back and forth over an infinite series).
> 
>> [intersting stuff about generators and D]
> 
> If generators can handle the above cases *AND* do it with code that
> simple to create and use *AND* do all that as efficiently as for loops,
> then it sounds great to me.  My impression was that any sort of
> opApply/coroutine thing in D was not going to be so efficient.
> 
> --bb

Well, as I said, once you have your sequence expressed as a coroutine,
writing hasNext() and getCurrent() is trivial.  Once you have that,
iterating multiple things in lockstep is also trivial:

> class zip : Generator!(Tuple!(T1,T2))
> {
>     // ...
>     Generator!(T1) seq1;
>     Generator!(T2) seq2;
>     // ...
>     void run()
>     {
>         while( seq1.hasNext && seq2.hasNext )
>             yield(new Tuple!(T1,T2)(seq1.next,seq2.next));
>     }
>     // ...
> }

Or something to that effect :P

As for efficiency, I'm not sure how to go about testing that so that the
results mean anything.  I'm sure my current implementation could be made
faster, but I don't know how.

Just for loose comparison, the game EVE Online has the record for the
most number of people simultaneously online on a single server at once.
 And it's servers are built using coroutines running in *Python*.

I suppose the bottleneck (if it is one) is how fast you can do
user-space context switches.  Which is basically a function call, moving
the base of the stack, and switching over stuff like the exception
handling registers.  Or somesuch... Mikola Lysenko wrote StackThreads;
my attempt only mostly worked :P

	-- Daniel

-- 
Unlike Knuth, I have neither proven or tried the above; it may not even
make sense.

v2sw5+8Yhw5ln4+5pr6OFPma8u6+7Lw4Tm6+7l6+7D
i28a2Xs3MSr2e4/6+7t4TNSMb6HTOp5en5g6RAHCP  http://hackerkey.com/