digitalmars.D - Iterating over containers of immutable objects

Justin Johansson (52/52) Jun 29 2010 To cut to the chase, what is the idiomatic code for iterating

Steven Schveighoffer (18/68) Jun 29 2010 You missed your old friend opApply :)

Justin Johansson (45/138) Jun 29 2010 On first sight your opApply solution looks really cool but upon

Steven Schveighoffer (23/124) Jun 29 2010 Well, you need not process all the items, but you are right that you can...

Justin Johansson (8/23) Jun 29 2010 Sorry that does not compile, dunno if it should I'm using

Jesse Phillips (6/14) Jun 29 2010 I believe it needs to be written:

Justin Johansson (5/22) Jun 30 2010 Yes it would be like you say if it were not for the immutable

Steven Schveighoffer (10/31) Jul 01 2010 Hm... a common idiom to deal with whether an object casts to a type is

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

"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

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.

Can you see this problem being solved over the near horizon?

Thanks, Justin

Jun 29 2010

"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.

   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

Jun 29 2010

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

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

Justin Johansson <no spam.com> writes:

Jesse Phillips wrote:
 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()) {
     ....
 }

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

"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.

  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


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

D Programming

C/C++ Programming

Other

digitalmars.D - Iterating over containers of immutable objects