www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How to construct a tree data structure with differently static nodes

reply data pulverizer <data.pulverizer gmail.com> writes:
Hi all,

I am trying to construct a tree data structure composed of 
differently (statically) typed nodes. The basic case is a binary 
tree. So you have a node like:

```
struct Node(T)
{
   T value;
   Node* next;
   Node* prev;
}

void main()
{
   auto x = Node!(int)(2);
   auto y = Node!(double)(3.2);
   x.next = &y; //gives error
}
```
Error: cannot implicitly convert expression & y of type 
Node!double* to Node!int*

So implicity Node!(T) will produce an object with prev, and next 
type Node!(T)*. But once I give them different types:

```
struct Node(T, P, N)
{
   T value;
   Node!(P...)* prev;
   Node!(N...)* next;
}
```

I can no longer specify the types at all, they become circularly 
referenced. Would appreciate the solution to this.

Many thanks.
Nov 22 2020
next sibling parent reply Max Haughton <maxhaton gmail.com> writes:
On Monday, 23 November 2020 at 01:20:04 UTC, data pulverizer 
wrote:

 Hi all,

 I am trying to construct a tree data structure composed of 
 differently (statically) typed nodes. The basic case is a 
 binary tree. So you have a node like:

 ```
 struct Node(T)
 {
   T value;
   Node* next;
   Node* prev;
 }

 void main()
 {
   auto x = Node!(int)(2);
   auto y = Node!(double)(3.2);
   x.next = &y; //gives error
 }
 ```
 Error: cannot implicitly convert expression & y of type 
 Node!double* to Node!int*

 So implicity Node!(T) will produce an object with prev, and 
 next type Node!(T)*. But once I give them different types:

 ```
 struct Node(T, P, N)
 {
   T value;
   Node!(P...)* prev;
   Node!(N...)* next;
 }
 ```

 I can no longer specify the types at all, they become 
 circularly referenced. Would appreciate the solution to this.

 Many thanks.


If you want to keep things simple, use OOP (classes).

If you need to use structs, the "sumtype" may be just what you 
need (it's a bit more lightweight than std.algebraic in the 
standard library). If you want to implement this yourself then 
you need to write something called a tagged union.
Nov 22 2020
parent data pulverizer <data.pulverizer gmail.com> writes:
On Monday, 23 November 2020 at 01:24:54 UTC, Max Haughton wrote:

 If you want to keep things simple, use OOP (classes).

 If you need to use structs, the "sumtype" may be just what you 
 need (it's a bit more lightweight than std.algebraic in the 
 standard library). If you want to implement this yourself then 
 you need to write something called a tagged union.


I'm looking for a data structure that is fully specified at 
compile time and statically dispatched rather than dynamically 
dispatched like OOP and so forth.
Nov 22 2020
prev sibling parent data pulverizer <data.pulverizer gmail.com> writes:
On Monday, 23 November 2020 at 01:20:04 UTC, data pulverizer 
wrote:

 Hi all,

 I am trying to construct a tree data structure composed of 
 differently (statically) typed nodes. The basic case is a 
 binary tree. So you have a node like:

 ```
 struct Node(T)
 {
   T value;
   Node* next;
   Node* prev;
 }

 void main()
 {
   auto x = Node!(int)(2);
   auto y = Node!(double)(3.2);
   x.next = &y; //gives error
 }
 ```
 Error: cannot implicitly convert expression & y of type 
 Node!double* to Node!int*

 So implicity Node!(T) will produce an object with prev, and 
 next type Node!(T)*. But once I give them different types:

 ```
 struct Node(T, P, N)
 {
   T value;
   Node!(P...)* prev;
   Node!(N...)* next;
 }
 ```

 I can no longer specify the types at all, they become 
 circularly referenced. Would appreciate the solution to this.

 Many thanks.


p.s. Something equivalent can be built using tuples but it's less 
convenient to write code for.
Nov 22 2020