Possible to avoid downcasting?

[H. S. Teoh]

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