I have a function makeTree() that builds a binary tree of BaseNode:

	class BaseNode {
		BaseNode* left, right;
	}
	BaseNode makeTree() {
		auto node = new BaseNode(...);
		...
		return node;
	}

But I want to have the option of creating the tree with derived class nodes instead of BaseNode.  One option is to pass a factory function to makeTree():

	BaseNode makeBaseNode() { return new BaseNode(...); }
	BaseNode makeTree(BaseNode function() makeNode = makeBaseNode) {
		auto node = makeNode();
		...
		return node;
	}

	auto tree1 = makeTree(); // tree of BaseNodes

	class Derived : BaseNode { ... }
	auto tree2 = makeTree(() => new Derived); // tree of Derived nodes

So far so good.  But now I want to iterate over the trees, and I'd like to be able to use information in the Derived node directly. But since makeTree() returns BaseNode, the only way I can get at the Derived nodes is to cast every node to Derived.  Furthermore, casting to Derived does not change the types of .left and .right, so this cast has to be done *every time*.

The other way to do this is to templatize:

	typeof(makeNode()) makeTree(Node)(Node function() makeNode)
		if (is(Node : BaseNode))
	{
		auto node = makeNode();
		...
		return node;
	}
	auto tree1 = makeTree!(() => new BaseNode);
	auto tree2 = makeTree!(() => new Derived);

This works, and returns a tree of BaseNode by default, or a tree of Derived if invoked with makeTree!Derived().  However, it's not an elegant solution, because it causes template bloat: makeTree is instantiated every time I want a new node type, even though the function body essentially doesn't even care what type the node is as long as it derived from BaseNode.

Is there a template equivalent of inout functions, where you basically say "the return type depends on the template parameter, but otherwise the function body is identical, so don't bother creating a new instantiation, just reuse the same function body"?


T

-- 
Only boring people get bored. -- JM

On Tuesday, 24 December 2019 at 19:52:44 UTC, H. S. Teoh wrote:
> So far so good.  But now I want to iterate over the trees, and I'd like to be able to use information in the Derived node directly.

How about using a visitor pattern to iterate over the nodes? That's how I'd solve it in a OOP context.

On Tuesday, 24 December 2019 at 19:52:44 UTC, H. S. Teoh wrote:
> But I want to have the option of creating the tree with derived class nodes instead of BaseNode.  One option is to pass a factory function to makeTree():
>
> 	BaseNode makeBaseNode() { return new BaseNode(...); }

You can also, if this is in the class, make it virtual and have the child classes return instances of themselves when overriding.

> Is there a template equivalent of inout functions, where you basically say "the return type depends on the template parameter, but otherwise the function body is identical, so don't bother creating a new instantiation, just reuse the same function body"?

But this is easy enough with traditional function techniques:

private void populate(Base b) { /* guts that only need to know base; most your makeTree function */ }

public T make(T)() {
   auto t = new T();
   populate(t);
   return t;
}


So now the templated section is reduced to really just the constructor call... and realistically the compiler can pretty easily inline that as well.

No cast, minimal duplication, easy to use on the outside.

(tbh i think sometimes we get so excited about D's cool features that we forget about the simple options we have too!)


speaking of cool features though


void populate(Object o) {
        import std.stdio;
        writeln(o);
}

// the lazy here....
T make(T)(lazy T t) {
        populate(t);
        return t;
}

class Foo {}

void main() {
        // means the new Foo down there is automatically lambdaized
        auto tree = make(new Foo);
}


which might be kinda fun.

On 12/24/19 2:52 PM, H. S. Teoh wrote:
> I have a function makeTree() that builds a binary tree of BaseNode:
> 
> 	class BaseNode {
> 		BaseNode* left, right;
> 	}
> 	BaseNode makeTree() {
> 		auto node = new BaseNode(...);
> 		...
> 		return node;
> 	}
> 
> But I want to have the option of creating the tree with derived class
> nodes instead of BaseNode.  One option is to pass a factory function to
> makeTree():
> 
> 	BaseNode makeBaseNode() { return new BaseNode(...); }
> 	BaseNode makeTree(BaseNode function() makeNode = makeBaseNode) {
> 		auto node = makeNode();
> 		...
> 		return node;
> 	}
> 
> 	auto tree1 = makeTree(); // tree of BaseNodes
> 
> 	class Derived : BaseNode { ... }
> 	auto tree2 = makeTree(() => new Derived); // tree of Derived nodes
> 
> So far so good.  But now I want to iterate over the trees, and I'd like
> to be able to use information in the Derived node directly. But since
> makeTree() returns BaseNode, the only way I can get at the Derived nodes
> is to cast every node to Derived.  Furthermore, casting to Derived does
> not change the types of .left and .right, so this cast has to be done
> *every time*.

If you *know* all the types are the same, you can use reinterpret casting instead of downcasting, which basically will avoid the runtime checks.

e.g.:

auto realNode = cast(Derived)(cast(void*)node);

Now, aside from that, D does support covariance on virtual functions. Which can make things more pleasant

So...

class BaseNode
{
   BaseNode _left;
   BaseNode _right;
   BaseNode left() { return _left; }
   BaseNode right() { return _right; }
}

class Derived : BaseNode
{
   override Derived left() { return cast(Derived)cast(void*)_left; }
   override Derived right() { return cast(Derived)cast(void*)_right; }
}

Now, if you know you have a Derived, the left and right properties turn into Derived as well.

-Steve

On 12/24/19 3:15 PM, Adam D. Ruppe wrote:
> // the lazy here....
> T make(T)(lazy T t) {
>          populate(t);
>          return t;
> }
> 
> class Foo {}
> 
> void main() {
>          // means the new Foo down there is automatically lambdaized
>          auto tree = make(new Foo);
> }

I see a bug ;)

-Steve

On Thursday, 26 December 2019 at 17:11:24 UTC, Steven Schveighoffer wrote:
> I see a bug ;)

oops indeed. but still