Iterators for D

Daniel Keep daniel.keep.lists at gmail.com
Tue Nov 7 18:16:15 PST 2006



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*?

Things that need random access override opIndex and opIndexAssign.

Things which you can take a range of values from override opSlice and
opSliceAssign.

Things that require lock-step iteration override opApply, or supply a
function that returns a delegate that "runs" a foreach loop.

About the only thing this *doesn't* cover are bi-directional iterators
(say, iterating back and forth over an infinite series).

I know some people want to be able to stop iteration and resume it, but
couldn't that be solved by making opApply return a generator like what
Python does?  Those things are written the same way as a current opApply
(sans all the return value from the delegate stuff), and can be advanced
manually.

I know this can be done.  I wrote the coroutine module for StackThreads
a while back, and one of the *very first* things I did was implement
generic generators.  The base generator class essentially just
implemented opApply switching over to the coroutine every time it needed
the next value.  Here's a port of Python's range() function (well, the
one and zero argument versions :P):

> class
> range : Generator!(uint)
> {
>     // These just let you use range() or range(n)
>     static
>     range
>     opCall()
>     {
>         return range(uint.max);
>     }
>
>     static
>     range
>     opCall(uint limit)
>     {
>         return new range(limit);
>     }
>
> protected:
>     uint limit;
>
>     // Or you can use new range(n)
>     this(uint limit)
>     {
>         this.limit = limit;
>         super();
>     }
>
>     // Where the magic happens.
>     override
>     uint
>     run()
>     {
>         uint i = 0;
>         while( i < limit )
>             yield(i++);    // yield in D: *very* sexy
>
>         StopGenerator();   // throws an exception, imitating what
>                            // Python does to stop an iterator.
>     }
> }

Now, from that, we can implement opApply AND next/current in the base
class.  Going with coroutines kills both the opApply and forward
iterator birds with one stone.

As for bi-directional iterators... I actually can't think of anywhere
I'd use them.  I just keep thinking "I could just use random access to
the same end".  Python's never suffered from not having them...

Anyway, just some random thoughts.  Haven't had coffee yet :3

	-- 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/



More information about the Digitalmars-d mailing list