View mode: basic / threaded / horizontal-split · Log in · Help
June 15, 2012
Getting a range over a const Container
Hi,

I have a const std.container object (e.g., a const(Array!int)) of which
I'd like to have a range which can traverse that container having
read-only access. This does not seem to be possible with opSlice(). Is
there an alternative?

Best regards,

Matthias
July 19, 2012
Re: Getting a range over a const Container
Hi all,

it's been a while since this question, and I don't know how to solve
it either.  The following code passes all the test using the last
version of dmd (2.059).

import std.container, std.algorithm;

//non const case
void assertequal(T)(SList!(T) l, int[] r) {
   assert(equal(l[], r));
}

//const case
void const_assertequal(T)(const SList!(T) l, int[] r) {
   assert(equal(l[], r));
}

unittest{
   SList!(int) l;
   l.insertFront(2);
   l.insertFront(1);
   assertequal (l,   [1,2]);
   assert(!__traits(compiles, const_assertequal(l, [1,2])));
}

The conflict with the last assertion is that opSplice can't be
applied to const.  So, I looked at the container module, and made a
minimal example of a list myself (emulating SList).

struct List {
   struct Node {
       Node* next;
       int val;
   }

   private Node* first;

   struct Range {
//sorry about "actual", it should have been current
       private Node* actual;
       this(Node* first) {actual = first;}
       @property front() {return actual.val;}
       @property empty() const {return !actual;}
       void popFront() {assert(!empty); actual = actual.next;}
       Range save() {return this;}
   }
   unittest{static assert(isForwardRange!(Range));}

   void add(int v) {
       Node * next = first;
       first = new Node;
       first.val = v;
       first.next = next;
   }

   Range opSlice() {
       return Range(first);
   }

}

void assertequal(L : List)(L l, int[] r) {
   assert(equal(l[], r));
}

void assertequal_const(L : List)(L l, int[] r) {
   assert(equal(l[], r));
}

unittest{
   List l;
   l.add(2);
   l.add(1);
   assert(equal(l[], [1,2]));
   assertequal (l,   [1,2]);
   assert(!__traits(compiles, const_assertequal(l, [1,2])));
}

As far as I know, the problem comes with the transitivity of const.
In assertequal_const, l.first has type const(Node*), thus it can't
be converted to Node* in Range's constructor.  I can't manage to
find a workaround here, because l.first will always have type
const(Node*), but for traversing the list I require to copy l.first
into some node, say actual, whose type is Node* so that I can move
it doing actual = actual.next.  I would be happy to do

actual = cast(Node*)(l.first)
actual = actual.next;

but that code is suppose to be undefined, isn't it?
(http://dlang.org/const3.html : Removing Immutable With A Cast).

So, my question is how can I (correctly) traverse a const SList,
const DList, etc?

Best,
Francisco.
PS: sorry for the long mail.
July 19, 2012
Re: Getting a range over a const Container
On Thursday, July 19, 2012 04:39:26 Francisco Soulignac wrote:
> So, my question is how can I (correctly) traverse a const SList,
> const DList, etc?

Right now? I'm pretty sure that that's impossible. Hopefully that will change, 
but getting const and ranges to work together can be rather difficult, and 
std.container needs more work in that regard.

- Jonathan M Davis
July 19, 2012
Re: Getting a range over a const Container
On 07/19/12 06:39, Francisco Soulignac wrote:
> it's been a while since this question, and I don't know how to solve
> it either.  The following code passes all the test using the last
> version of dmd (2.059).
> 
> import std.container, std.algorithm;
> 
> //non const case
> void assertequal(T)(SList!(T) l, int[] r) {
>     assert(equal(l[], r));
> }
> 
> //const case
> void const_assertequal(T)(const SList!(T) l, int[] r) {
>     assert(equal(l[], r));
> }
> 
> unittest{
>     SList!(int) l;
>     l.insertFront(2);
>     l.insertFront(1);
>     assertequal (l,   [1,2]);
>     assert(!__traits(compiles, const_assertequal(l, [1,2])));
> }
> 
> The conflict with the last assertion is that opSplice can't be
> applied to const.  So, I looked at the container module, and made a
> minimal example of a list myself (emulating SList).
> 
> struct List {
>     struct Node {
>         Node* next;
>         int val;
>     }
> 
>     private Node* first;
> 
>     struct Range {
> //sorry about "actual", it should have been current
>         private Node* actual;
>         this(Node* first) {actual = first;}
>         @property front() {return actual.val;}
>         @property empty() const {return !actual;}
>         void popFront() {assert(!empty); actual = actual.next;}
>         Range save() {return this;}
>     }
>     unittest{static assert(isForwardRange!(Range));}
> 
>     void add(int v) {
>         Node * next = first;
>         first = new Node;
>         first.val = v;
>         first.next = next;
>     }
> 
>     Range opSlice() {
>         return Range(first);
>     }
> 
> }
> 
> void assertequal(L : List)(L l, int[] r) {
>     assert(equal(l[], r));
> }
> 
> void assertequal_const(L : List)(L l, int[] r) {
>     assert(equal(l[], r));
> }
> 
> unittest{
>     List l;
>     l.add(2);
>     l.add(1);
>     assert(equal(l[], [1,2]));
>     assertequal (l,   [1,2]);
>     assert(!__traits(compiles, const_assertequal(l, [1,2])));
> }
> 
> As far as I know, the problem comes with the transitivity of const.
> In assertequal_const, l.first has type const(Node*), thus it can't
> be converted to Node* in Range's constructor.  I can't manage to
> find a workaround here, because l.first will always have type
> const(Node*), but for traversing the list I require to copy l.first
> into some node, say actual, whose type is Node* so that I can move
> it doing actual = actual.next.  I would be happy to do
> 
> actual = cast(Node*)(l.first)
> actual = actual.next;
> 
> but that code is suppose to be undefined, isn't it?
> (http://dlang.org/const3.html : Removing Immutable With A Cast).
> 
> So, my question is how can I (correctly) traverse a const SList,
> const DList, etc?

  import std.algorithm, std.range;

  struct List {
      static struct Node {
          Node* next;
          int val;
      }

      private Node* first;

      static struct Range(E) {
          private E* current;
          this(FE:const E)(FE* first) {current = first;}
          @property front() {return current.val;}
          @property empty() const {return !current;}
          void popFront() {assert(!empty); current = current.next;}
          @property Range save() {return this;}
      }
      static assert(isForwardRange!(Range!Node));

      void add(int v) {
          Node * next = first;
          first = new Node;
          first.val = v;
          first.next = next;
       }

      Range!Node opSlice() { return Range!Node(first); }
      Range!(const Node) opSlice() const { return Range!(const Node)(first); }
  }

  void assertequal(L : List)(L l, int[] r) {
      assert(equal(l[], r));
  }

  void assertequal_const(L : List)(const L l, int[] r) {
      assert(equal(l[], r));
  }

  void main() {
      List l;
      l.add(2);
      l.add(1);
      assert(equal(l[], [1,2]));
      assertequal (l,   [1,2]);
      assertequal_const(l, [1,2]);
  }

artur
July 19, 2012
Re: Getting a range over a const Container
On 07/19/2012 06:44 AM, Jonathan M Davis wrote:
> On Thursday, July 19, 2012 04:39:26 Francisco Soulignac wrote:
>> So, my question is how can I (correctly) traverse a const SList,
>> const DList, etc?
> 
> Right now? I'm pretty sure that that's impossible. Hopefully that will change, 
> but getting const and ranges to work together can be rather difficult, and 
> std.container needs more work in that regard.

Well it doesn't work yet. But in principle it could since we can always
copy a const pointer to a non-const one to const data:

Node* actual; // but 'this' is const and hence the type is const(Node*)

const(Node)* i_will_traverse = actual;

Best regards,

Matthias
July 20, 2012
Re: Getting a range over a const Container
On 07/19/2012 02:51 AM, Artur Skawina wrote:
>         Range!Node opSlice() { return Range!Node(first); }
>         Range!(const Node) opSlice() const { return Range!(const Node)(first); }


anyone mind cluing me in on why this is possible?
July 20, 2012
Re: Getting a range over a const Container
On 07/19/2012 06:09 PM, Ellery Newcomer wrote:
> On 07/19/2012 02:51 AM, Artur Skawina wrote:
>> Range!Node opSlice() { return Range!Node(first); }
>> Range!(const Node) opSlice() const { return Range!(const Node)(first); }
>
>
> anyone mind cluing me in on why this is possible?

It is the same as in C++. Considering the hidden non-const this and 
const this parameters, one of the member functions is a better match for 
each call:

import std.stdio;

struct S
{
    void foo(string name)
    {
        writeln("Called on ", name);
        assert(typeid(this) == typeid(S));
    }

    void foo(string name) const
    {
        writeln("Called on ", name);
        assert(typeid(this) == typeid(const S));
    }
}

void main()
{
    auto a = S();
    const b = S();

    a.foo("a");    // matches non-const foo()
    b.foo("b");    // matches const foo()
}

The output:

Called on a
Called on b

Ali
July 20, 2012
Re: Getting a range over a const Container
On 07/19/2012 06:16 PM, Ali Çehreli wrote:
> On 07/19/2012 06:09 PM, Ellery Newcomer wrote:
>> On 07/19/2012 02:51 AM, Artur Skawina wrote:
>>> Range!Node opSlice() { return Range!Node(first); }
>>> Range!(const Node) opSlice() const { return Range!(const Node)(first); }
>>
>>
>> anyone mind cluing me in on why this is possible?
>
> It is the same as in C++. Considering the hidden non-const this and
> const this parameters, one of the member functions is a better match for
> each call:

Ha ha! The output is worthless when both functions print the same thing. :)

This is better:

import std.stdio;

struct S
{
    void foo(string name)
    {
        writeln("non-const foo called on ", name);
        assert(typeid(this) == typeid(S));
    }

    void foo(string name) const
    {
        writeln("const foo called on ", name);
        assert(typeid(this) == typeid(const S));
    }
}

void main()
{
    auto a = S();
    const b = S();

    a.foo("a");    // matches non-const foo()
    b.foo("b");    // matches const foo()
}

Now the output is different:

non-const foo called on a
const foo called on b

Ali
July 20, 2012
Re: Getting a range over a const Container
On 07/19/2012 06:18 PM, Ali Çehreli wrote:
>
> Now the output is different:
>
> non-const foo called on a
> const foo called on b
>
> Ali


cool beans, thanks.
July 21, 2012
Re: Getting a range over a const Container
On 07/19/2012 06:09 PM, Ellery Newcomer wrote:
> On 07/19/2012 02:51 AM, Artur Skawina wrote:
>>         Range!Node opSlice() { return Range!Node(first); }
>>         Range!(const Node) opSlice() const { return Range!(const
>> Node)(first); }


it looks like you could almost merge these two into one using inout, but 
I'm not sure what you do about selecting the return type.
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home