www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - RedBlackTree thin wrapper initialization

reply "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
next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling parent "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