www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Mimicing Python list of list

reply Dandyvica <dandyvica gmail.com> writes:
Hi all,

I'm trying to find out a solution to implement a generic tree or 
array container whose nodes
can either be elements or a subtree (or sub-array).

Pretty much like you can do in Python:

l = [1, 2, [1, 2, 3], 4]

l is a list of (integers or list of integers).

Any idea on how to do that?

Thanks.
Oct 26 2015
parent reply Meta <jared771 gmail.com> writes:
On Monday, 26 October 2015 at 18:46:45 UTC, Dandyvica wrote:

 Hi all,

 I'm trying to find out a solution to implement a generic tree 
 or array container whose nodes
 can either be elements or a subtree (or sub-array).

 Pretty much like you can do in Python:

 l = [1, 2, [1, 2, 3], 4]

 l is a list of (integers or list of integers).

 Any idea on how to do that?

 Thanks.


It's a bit more involved than in Python as D is not a dynamically 
typed language.

import std.typecons;
import std.stdio;

struct Tree(T)
{
	T payload;
	Tree!T[] children;
}

Tree!T tree(T)(T payload, Tree!T[] children...)
{
	return Tree!T(payload, children.dup);
}

//Convenience overload because typeof(null)
//does not implicitly convert to Tree!T[]
Tree!T tree(T)(T payload, typeof(null))
{
	return Tree!T(payload, null);
}

void printTree(T)(Tree!T tree)
{
	writeln(tree.payload);
	foreach (child; tree.children)
	{
		printTree(child);
	}
}

void main()
{
	auto intTree = tree(0,
		           tree(1,
		               tree(2)),
			   tree(3,
			       tree(4,
			           tree(5))),
			   tree(6,
			       tree(7)));

	printTree(intTree);
}

Otherwise, you an use std.variant.Variant or 
std.variant.Algebraic.
Oct 26 2015
parent reply Dandyvica <dandyvica gmail.com> writes:
On Monday, 26 October 2015 at 19:26:08 UTC, Meta wrote:

 On Monday, 26 October 2015 at 18:46:45 UTC, Dandyvica wrote:

 Hi all,

 I'm trying to find out a solution to implement a generic tree 
 or array container whose nodes
 can either be elements or a subtree (or sub-array).

 Pretty much like you can do in Python:

 l = [1, 2, [1, 2, 3], 4]

 l is a list of (integers or list of integers).

 Any idea on how to do that?

 Thanks.


 It's a bit more involved than in Python as D is not a 
 dynamically typed language.

 import std.typecons;
 import std.stdio;

 struct Tree(T)
 {
 	T payload;
 	Tree!T[] children;
 }

 Tree!T tree(T)(T payload, Tree!T[] children...)
 {
 	return Tree!T(payload, children.dup);
 }

 //Convenience overload because typeof(null)
 //does not implicitly convert to Tree!T[]
 Tree!T tree(T)(T payload, typeof(null))
 {
 	return Tree!T(payload, null);
 }

 void printTree(T)(Tree!T tree)
 {
 	writeln(tree.payload);
 	foreach (child; tree.children)
 	{
 		printTree(child);
 	}
 }

 void main()
 {
 	auto intTree = tree(0,
 		           tree(1,
 		               tree(2)),
 			   tree(3,
 			       tree(4,
 			           tree(5))),
 			   tree(6,
 			       tree(7)));

 	printTree(intTree);
 }

 Otherwise, you an use std.variant.Variant or 
 std.variant.Algebraic.


Thanks Meta, great idea.

But does I'd like to have something like dynamic arrays and be 
able to do this:

class A(T) { T _v; this(T v) { _v = v; }  }

auto myContainer = MyContainerArray!(A!int)();

myContainer ~= new A!int(1);
myContainer ~= new A!int(2);

auto myInnerContainer = MyContainerArray!(A!int)();
myInnerContainer ~= new A!int(3);
myInnerContainer ~= new A!int(4);

myContainer ~= myInnerContainer;
myContainer ~= new A!int(5);

I don't know if your implementation allows this?
Oct 26 2015
parent Meta <jared771 gmail.com> writes:
On Monday, 26 October 2015 at 20:53:18 UTC, Dandyvica wrote:

 Thanks Meta, great idea.

 But does I'd like to have something like dynamic arrays and be 
 able to do this:

 class A(T) { T _v; this(T v) { _v = v; }  }

 auto myContainer = MyContainerArray!(A!int)();

 myContainer ~= new A!int(1);
 myContainer ~= new A!int(2);

 auto myInnerContainer = MyContainerArray!(A!int)();
 myInnerContainer ~= new A!int(3);
 myInnerContainer ~= new A!int(4);

 myContainer ~= myInnerContainer;
 myContainer ~= new A!int(5);

 I don't know if your implementation allows this?


There is a Red Black Tree implement in std.container.rbtree 
(http://dlang.org/phobos/std_container_rbtree.html). I'm not sure 
if it supports the concatenation operator or not, though.
Oct 26 2015