Iterating over containers of immutable objects

[Steven Schveighoffer]

On Tue, 29 Jun 2010 18:42:18 -0400, Justin Johansson <no at spam.com> wrote:

> Steven Schveighoffer wrote:
>> On Tue, 29 Jun 2010 17:07:40 -0400, Justin Johansson <no at spam.com>  
>> wrote:
>>
>>> To cut to the chase, what is the idiomatic code for iterating
>>> over a container of immutable objects when the container provides
>>> a "getIterator" method?
>>>
>>> Alternatively, how can the following code be written
>>> (1) to not use a break statement and,
>>> (2) with casting away immutability.
>>>
>>> Specifically my question is about assigning to an
>>> immutable loop variable and not wanting to get
>>> into any discussion about iterators and ranges per
>>> se (unless relevant to the first bit).
>>>
>>>
>>> // A class reprenting some abstract immutable item
>>> immutable abstract class Bar
>>> {
>>> }
>>>
>>> // A container of Bar immutable objects
>>> abstract class BarContainer
>>> {
>>>     BarIterator getIterator();
>>> }
>>>
>>> // An interface for iterating over the
>>> // immutable Bar objects in a BarContainer
>>> interface BarIterator
>>> {
>>>     immutable(Bar) next();
>>> }
>>>
>>> void testBarIterator( BarContainer barContainer)
>>> {
>>>     auto iter = barContainer.getIterator();
>>>
>>>     while (true) {
>>>        auto bar = iter.next();
>>>
>>>        if (bar is null)
>>>           break;
>>>
>>>        // process the bar item
>>>        // ...
>>>     }
>>> }
>>>
>>>
>>> So far so good, but having the break statement doesn't
>>> seem all that clean.  My next try appeals better in style
>>> to me but it doesn't compile, yielding
>>>
>>> Error: variable test.testBarIterator2.bar cannot modify immutable
>>>
>>> void testBarIterator2( BarContainer barContainer)
>>> {
>>>     auto iter = barContainer.getIterator();
>>>     immutable Bar bar;
>>>
>>>     while ((bar = iter.next()) !is null) {    // error line
>>>        // process the bar item
>>>        // ...
>>>     }
>>> }
>>>
>>>
>>> Probably I've missed something but the answer alludes me.
>>   You missed your old friend opApply :)
>>  interface BarIterator
>> {
>>    int opApply(int delegate(ref immutable(Bar)) dg);
>> }
>>  void testBarIterator(BarContainer barContainer)
>> {
>>    foreach(bar; barContainer.getIterator())
>>    {
>>       // process the bar item
>>    }
>> }
>>  But this is an indirect response to your question.  The real problem  
>> is lack of tail-const support for classes.  You can use Rebindable in  
>> std.typecons to get a rebindable const or immutable class reference.   
>> IIRC, it's severely out of date (still uses opDot), but that's what we  
>> got.
>>  -Steve
>
> On first sight your opApply solution looks really cool but upon
> closer examination this solution breaks the concept of the iterator
> idiom, i.e. that one can suspend the iteration and pull items
> on demand.  As it is, turning the iterator interface into something
> that requires a foreach to drive it means that you are pushing out
> all the items at once.

Well, you need not process all the items, but you are right that you can't  
"suspend and come back" to where you left off.  I'm not sure what your  
true goal is, so I can't really comment on whether it makes sense to do  
that.  Most of the time you want to iterate all the items, or at least up  
until some point.

Ranges are probably a better fit for such an idiom, but ranges don't work  
well as reference types.

> There is another solution which requires introducing an extra virtual
> method (and associated cost thereof) namely "hasNext" to the iterator
> interface.  This allows pulling a single item (if it exists) out of
> the iterator on demand.

Duh... I just thought of this too:

while(auto bar = iter.next())
{
   ...
}

>
>  > The real problem is lack of tail-const support for classes.
> Can you see this problem being solved over the near horizon?

I think Rebindable can be fixed to use alias this and can be updated to  
use other goodies that have been added since its creation.  Rebindable or  
something like it is going to be the solution.  I tried many times to get  
Walter to allow some sort of tail-const for classes, but he does not think  
it can be solved.  I think it can, but I agree that the solutions are not  
very pretty.

With a little more compiler help, a library struct like Rebindable can be  
as good as a builtin tail-const reference.  I think we are beyond the  
reach of a pretty solution.

-Steve