digitalmars.D - RedBlackTree thin wrapper initialization

BlackEdder (22/22) May 28 2014 I'm trying to write a thin wrapper around redblacktree, but it

Chris (12/35) May 28 2014 Have you tried

Rene Zwanenburg (12/54) May 28 2014 Ninja'd ;)

Chris (4/64) May 28 2014 Tell me about it, I'm in the process of alias'ing my template

Rene Zwanenburg (17/40) May 28 2014 The problem is the initialization of A.tree. Short answer, move

Edwin van Leeuwen (11/27) May 28 2014 Thank you for the reply. Does this mean I should never initialize

Rene Zwanenburg (64/74) May 28 2014 It's the same for any class.

Edwin van Leeuwen (3/78) May 29 2014 Thank you very much for the clear description! That cleared

"BlackEdder" <edder tkwsping.nl> writes:

I'm trying to write a thin wrapper around redblacktree, but it 
seems every object of the class shares the same copy of 
redblacktree. Am I doing something wrong or is this a bug.

Minimal code example:

import std.array;
import std.container;
import std.stdio;

class A {
     auto tree = new RedBlackTree!string();
}

unittest {
     auto a = new A();
     a.tree.insert( "a" );
     auto b = new A();
     writeln( "Should be empty, but is: ", b.tree.array );
     writeln( "Should be empty, but has length: ", b.tree.length );
}

Which results in the following output:
$ rdmd -unittest rbt.d
Should be empty, but is: ["a"]
Should be empty, but has length: 1


I'm using dmd 2.0.65.

May 28 2014

"Chris" <wendlec tcd.ie> writes:

On Wednesday, 28 May 2014 at 07:13:37 UTC, BlackEdder wrote:
 I'm trying to write a thin wrapper around redblacktree, but it 
 seems every object of the class shares the same copy of 
 redblacktree. Am I doing something wrong or is this a bug.

 Minimal code example:

 import std.array;
 import std.container;
 import std.stdio;

 class A {
     auto tree = new RedBlackTree!string();
 }

 unittest {
     auto a = new A();
     a.tree.insert( "a" );
     auto b = new A();
     writeln( "Should be empty, but is: ", b.tree.array );
     writeln( "Should be empty, but has length: ", b.tree.length 
 );
 }

 Which results in the following output:
 $ rdmd -unittest rbt.d
 Should be empty, but is: ["a"]
 Should be empty, but has length: 1


 I'm using dmd 2.0.65.

Have you tried

class A {
   RedBlackTree!(string) tree;
   this() {
     tree = new RedBlackTree!string();
   }
}

Maybe in your implementation all instances of class A share the 
same underlying instance RedBlackTree, or class RedBlackTree was 
designed as a singleton (which would seem odd to me).

PS This question would be better suited for the "D learn" forum.

May 28 2014

"Rene Zwanenburg" <renezwanenburg gmail.com> writes:

On Wednesday, 28 May 2014 at 08:37:14 UTC, Chris wrote:
 On Wednesday, 28 May 2014 at 07:13:37 UTC, BlackEdder wrote:
 I'm trying to write a thin wrapper around redblacktree, but it 
 seems every object of the class shares the same copy of 
 redblacktree. Am I doing something wrong or is this a bug.

 Minimal code example:

 import std.array;
 import std.container;
 import std.stdio;

 class A {
    auto tree = new RedBlackTree!string();
 }

 unittest {
    auto a = new A();
    a.tree.insert( "a" );
    auto b = new A();
    writeln( "Should be empty, but is: ", b.tree.array );
    writeln( "Should be empty, but has length: ", b.tree.length 
 );
 }

 Which results in the following output:
 $ rdmd -unittest rbt.d
 Should be empty, but is: ["a"]
 Should be empty, but has length: 1


 I'm using dmd 2.0.65.

 Have you tried

 class A {
   RedBlackTree!(string) tree;
   this() {
     tree = new RedBlackTree!string();
   }
 }

 Maybe in your implementation all instances of class A share the 
 same underlying instance RedBlackTree, or class RedBlackTree 
 was designed as a singleton (which would seem odd to me).

 PS This question would be better suited for the "D learn" forum.

Ninja'd ;)

Also, if you want to avoid repeating long type names an alias can 
help:

class A
{
   alias TreeType = RedBlackTree!string;

   TreeType tree;

   // etc etc.
}

In this case it isn't too bad but some template instantiations 
can get fairly long.

May 28 2014

"Chris" <wendlec tcd.ie> writes:

On Wednesday, 28 May 2014 at 08:49:42 UTC, Rene Zwanenburg wrote:
 On Wednesday, 28 May 2014 at 08:37:14 UTC, Chris wrote:
 On Wednesday, 28 May 2014 at 07:13:37 UTC, BlackEdder wrote:
 I'm trying to write a thin wrapper around redblacktree, but 
 it seems every object of the class shares the same copy of 
 redblacktree. Am I doing something wrong or is this a bug.

 Minimal code example:

 import std.array;
 import std.container;
 import std.stdio;

 class A {
   auto tree = new RedBlackTree!string();
 }

 unittest {
   auto a = new A();
   a.tree.insert( "a" );
   auto b = new A();
   writeln( "Should be empty, but is: ", b.tree.array );
   writeln( "Should be empty, but has length: ", b.tree.length 
 );
 }

 Which results in the following output:
 $ rdmd -unittest rbt.d
 Should be empty, but is: ["a"]
 Should be empty, but has length: 1


 I'm using dmd 2.0.65.

 Have you tried

 class A {
  RedBlackTree!(string) tree;
  this() {
    tree = new RedBlackTree!string();
  }
 }

 Maybe in your implementation all instances of class A share 
 the same underlying instance RedBlackTree, or class 
 RedBlackTree was designed as a singleton (which would seem odd 
 to me).

 PS This question would be better suited for the "D learn" 
 forum.

 Ninja'd ;)

 Also, if you want to avoid repeating long type names an alias 
 can help:

 class A
 {
   alias TreeType = RedBlackTree!string;

   TreeType tree;

   // etc etc.
 }

 In this case it isn't too bad but some template instantiations 
 can get fairly long.

Tell me about it, I'm in the process of alias'ing my template 
types, cos I've really long type instantiations now like

type = Type!(Type2!(Type3!(int, string), string))();

May 28 2014

"Rene Zwanenburg" <renezwanenburg gmail.com> writes:

On Wednesday, 28 May 2014 at 07:13:37 UTC, BlackEdder wrote:
 I'm trying to write a thin wrapper around redblacktree, but it 
 seems every object of the class shares the same copy of 
 redblacktree. Am I doing something wrong or is this a bug.

 Minimal code example:

 import std.array;
 import std.container;
 import std.stdio;

 class A {
     auto tree = new RedBlackTree!string();
 }

 unittest {
     auto a = new A();
     a.tree.insert( "a" );
     auto b = new A();
     writeln( "Should be empty, but is: ", b.tree.array );
     writeln( "Should be empty, but has length: ", b.tree.length 
 );
 }

 Which results in the following output:
 $ rdmd -unittest rbt.d
 Should be empty, but is: ["a"]
 Should be empty, but has length: 1


 I'm using dmd 2.0.65.

The problem is the initialization of A.tree. Short answer, move 
it to a constructor and it should work.

Now what I think is going on: default values for member fields 
must be known at compile time. This is why structs can do 
something like

struct S
{
   int i = 5;
}

while they're not allowed to define a default constructor.

So it appears the tree is instantiated at compile time and stored 
somewhere, and the reference to that instance is used as the 
default value for A.tree. I didn't know this was possible to do 
with reference type members, and perhaps it should be disallowed. 
This is highly counter intuitive behavior esp. for people coming 
from Java.

May 28 2014

"Edwin van Leeuwen" <edder tkwsping.nl> writes:

On Wednesday, 28 May 2014 at 08:46:30 UTC, Rene Zwanenburg wrote:
 The problem is the initialization of A.tree. Short answer, move 
 it to a constructor and it should work.

 Now what I think is going on: default values for member fields 
 must be known at compile time. This is why structs can do 
 something like

 struct S
 {
   int i = 5;
 }

 while they're not allowed to define a default constructor.

 So it appears the tree is instantiated at compile time and 
 stored somewhere, and the reference to that instance is used as 
 the default value for A.tree. I didn't know this was possible 
 to do with reference type members, and perhaps it should be 
 disallowed. This is highly counter intuitive behavior esp. for 
 people coming from Java.

Thank you for the reply. Does this mean I should never initialize 
classes/objects like that or is it more specific to RBT?

I guess structs have the same problem with classes/objects? That 
makes struct that hold objects quite awkward to use, since you 
can't define a default constructor for structs.

struct S
{
     auto tree = new RedBlackTree!string();
}



PS Sorry for not posting this to the learn forum.

May 28 2014

"Rene Zwanenburg" <renezwanenburg gmail.com> writes:

On Wednesday, 28 May 2014 at 09:37:55 UTC, Edwin van Leeuwen 
wrote:
 Thank you for the reply. Does this mean I should never 
 initialize classes/objects like that or is it more specific to 
 RBT?

It's the same for any class.

 I guess structs have the same problem with classes/objects?

That's right.

 That makes struct that hold objects quite awkward to use, since 
 you can't define a default constructor for structs.

 struct S
 {
     auto tree = new RedBlackTree!string();
 }

There is a workaround for struct default construction. First let 
me describe the way D initialization works:

Every type, built in or user defined, has an init value. For ints 
this is 0, floats NaN, and so on. User defined types have their 
init value stored in the corresponding TypeInfo, for example [0], 
[1].

When initializing a value type the space is already reserved, 
either on the stack or on the heap inside a dynamic array. All 
the runtime does is memcpy the init value of that type to the 
right location.

When new-ing a class the GC first allocates some space on the 
heap. Then it copies the init value to that location, just like 
with a value type. Finally it calls a constructor on the newly 
allocated object.

When declaring a field in your struct or class and assign a 
default value to it, it ends up in the init value for your type. 
For example:

class C
{
   int i = uniform(0, 10); // Uniform random number
}

The generated random value will end up in C's init value and thus 
be the same for every instance. Generating the number in a 
constructor will of course result in a fresh random number for 
every instance.

The reason initialization works this way is, as I understand it, 
both safety and speed. The memcpy will never fail, so if you 
successfully allocated the space for something it will _always_ 
be properly initialized. And since the init value of everything 
is known at compile time the init values of composite types 
contain the init values of all contained fields. In other words, 
no matter how complex your type, it will always be initialized 
with a single memcpy.

Now, a workaround for struct default constructors is to use 
static opCall:

struct S
{
   int i;

    disable this(); // Disable default initialization. See the 
comment in [1]

   private this(int i)
   {
     this.i = i;
   }

   static auto opCall()
   {
     return S(uniform(0, 10));
   }
}

void main()
{
   S s; // Should not compile. No init value for S
   auto s = S(); // Calls S.opCall
}

I hope my ramblings make it a bit more clear what is happening 
instead of confusing the hell out of you ;). I didn't try any of 
this code so there may be some typos.


[0]https://github.com/D-Programming-Language/druntime/blob/master/src/object_.d#L844
[1] 
https://github.com/D-Programming-Language/druntime/blob/master/src/object_.d#L1060

May 28 2014

"Edwin van Leeuwen" <edder tkwsping.nl> writes:

On Wednesday, 28 May 2014 at 16:25:40 UTC, Rene Zwanenburg wrote:
 On Wednesday, 28 May 2014 at 09:37:55 UTC, Edwin van Leeuwen 
 wrote:
 Thank you for the reply. Does this mean I should never 
 initialize classes/objects like that or is it more specific to 
 RBT?

 It's the same for any class.

 I guess structs have the same problem with classes/objects?

 That's right.

 That makes struct that hold objects quite awkward to use, 
 since you can't define a default constructor for structs.

 struct S
 {
    auto tree = new RedBlackTree!string();
 }

 There is a workaround for struct default construction. First 
 let me describe the way D initialization works:

 Every type, built in or user defined, has an init value. For 
 ints this is 0, floats NaN, and so on. User defined types have 
 their init value stored in the corresponding TypeInfo, for 
 example [0], [1].

 When initializing a value type the space is already reserved, 
 either on the stack or on the heap inside a dynamic array. All 
 the runtime does is memcpy the init value of that type to the 
 right location.

 When new-ing a class the GC first allocates some space on the 
 heap. Then it copies the init value to that location, just like 
 with a value type. Finally it calls a constructor on the newly 
 allocated object.

 When declaring a field in your struct or class and assign a 
 default value to it, it ends up in the init value for your 
 type. For example:

 class C
 {
   int i = uniform(0, 10); // Uniform random number
 }

 The generated random value will end up in C's init value and 
 thus be the same for every instance. Generating the number in a 
 constructor will of course result in a fresh random number for 
 every instance.

 The reason initialization works this way is, as I understand 
 it, both safety and speed. The memcpy will never fail, so if 
 you successfully allocated the space for something it will 
 _always_ be properly initialized. And since the init value of 
 everything is known at compile time the init values of 
 composite types contain the init values of all contained 
 fields. In other words, no matter how complex your type, it 
 will always be initialized with a single memcpy.

 Now, a workaround for struct default constructors is to use 
 static opCall:

 struct S
 {
   int i;

    disable this(); // Disable default initialization. See the 
 comment in [1]

   private this(int i)
   {
     this.i = i;
   }

   static auto opCall()
   {
     return S(uniform(0, 10));
   }
 }

 void main()
 {
   S s; // Should not compile. No init value for S
   auto s = S(); // Calls S.opCall
 }

 I hope my ramblings make it a bit more clear what is happening 
 instead of confusing the hell out of you ;). I didn't try any 
 of this code so there may be some typos.


 [0]https://github.com/D-Programming-Language/druntime/blob/master/src/object_.d#L844
 [1] 
 https://github.com/D-Programming-Language/druntime/blob/master/src/object_.d#L1060

Thank you very much for the clear description! That cleared 
things up a lot.

May 29 2014

D Programming

C/C++ Programming

Other

digitalmars.D - RedBlackTree thin wrapper initialization