www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Iterating over containers of immutable objects

reply Justin Johansson <no spam.com> writes:
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.

Thanks
Justin Johansson
Jun 29 2010
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 29 Jun 2010 17:07:40 -0400, Justin Johansson <no 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
Jun 29 2010
parent reply Justin Johansson <no spam.com> writes:
Steven Schveighoffer wrote:
 On Tue, 29 Jun 2010 17:07:40 -0400, Justin Johansson <no 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.

Thanks, Justin
Jun 29 2010
parent reply Justin Johansson <no spam.com> writes:
Steven Schveighoffer wrote:
 On Tue, 29 Jun 2010 18:42:18 -0400, Justin Johansson <no spam.com> wrote:
 
 Steven Schveighoffer wrote:

 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()) // line 37 { ... }

Sorry that does not compile, dunno if it should I'm using the latest D2. test.d(37): expression expected, not 'auto' test.d(37): found 'bar' when expecting ')' test.d(37): found '=' instead of statement test.d(41): unrecognized declaration JJ
Jun 29 2010
parent reply Jesse Phillips <jessekphillips+D gmail.com> writes:
Justin Johansson Wrote:

 Steven Schveighoffer wrote:
 while(auto bar = iter.next())	// line 37
 {
   ...
 }

Sorry that does not compile, dunno if it should I'm using the latest D2.

I believe it needs to be written: T bar; while(bar = iter.next()) { .... }
Jun 29 2010
parent Justin Johansson <no spam.com> writes:
Jesse Phillips wrote:
 Justin Johansson Wrote:
 
 Steven Schveighoffer wrote:
 while(auto bar = iter.next())	// line 37
 {
   ...
 }

the latest D2.

I believe it needs to be written: T bar; while(bar = iter.next()) { .... }

Yes it would be like you say if it were not for the immutable disposition of the type T. Rereading from the start of this thread would explain this point. Cheers, JJ
Jun 30 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 29 Jun 2010 18:42:18 -0400, Justin Johansson <no spam.com> wrote:

 Steven Schveighoffer wrote:
 On Tue, 29 Jun 2010 17:07:40 -0400, Justin Johansson <no 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.

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
Jun 29 2010
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 29 Jun 2010 19:08:13 -0400, Justin Johansson <no spam.com> wrote:

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

 Steven Schveighoffer wrote:

 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.

while(auto bar = iter.next()) // line 37 { ... }

Sorry that does not compile, dunno if it should I'm using the latest D2. test.d(37): expression expected, not 'auto' test.d(37): found 'bar' when expecting ')' test.d(37): found '=' instead of statement test.d(41): unrecognized declaration

Hm... a common idiom to deal with whether an object casts to a type is this: if(auto c = cast(C)obj) { // use c } I wonder why while doesn't work... Walter? -Steve
Jul 01 2010