Iterating over containers of immutable objects

[Justin Johansson]

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.

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.

// 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
{
    bool hasNext();

    immutable(Bar) next();
}

void testBarIterator( BarContainer barContainer)
{
    auto iter = barContainer.getIterator();

    // Look Ma, no break statement

    while (iter.hasNext()) {
       auto bar = iter.next();

       // process the bar item
       // ...
    }
}

You sound a bit apprehensive about Rebindable in std.typecons
so perhaps I will not go there.

Maybe living with the single method next() iterator interface
(which signals end of iteration by returning null) together with
use of a break statement in a while loop is not so bad afterall;
anything else will probably have a performance penalty.

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

Thanks, Justin