Compile time data structure

[H. S. Teoh]

On Thu, Sep 19, 2013 at 09:12:10PM +0200, Marek Janukowicz wrote:
> Ali Çehreli wrote:
[...]
> > As far as I know, static foreach is only for tuples (or TypeTuples).
> > If you can generate the AA as a tuple, then the foreach will be
> > evaluated at compile time.
> 
> I read your articles about tuples and templates and it all now makes
> more sense (why is your book not linked on dlang.org? It is much
> better stuff for beginners than official D docs). However, there is
> still one thing I struggle with: how do I create a tuple at compile
> time if I'm getting information I want to put into it in a foreach?
> All the examples I found create a tuple with all it's attributes
> available, while I get mine in an iterative manner...
[...]

Hmm. That's a hard one. How do you generate your attributes? My first
impression -- though I could be wrong -- is that you can't modify a type
tuple dynamically, that is, once created, a tuple can't be changed, you
can only make new tuples out of it. So first, you'd have to factor out
your generated attributes so that they can be generated by, for example,
instantiating a template with an integer index argument.

For example, say you define a template like this:

	template GenerateElement(int i) {
		// This is just an example, the point is that the
		// template returns something different depending on the
		// index i.
		static if (i==0)
			alias GenerateElement = byte;
		else static if (i==1)
			alias GenerateElement = short;
		else static if (i==2)
			alias GenerateElement = int;
		else static if (i==3)
			alias GenerateElement = float;
		else static if (i==4)
			alias GenerateElement = double;
		else static assert(0, "i is out of range");
	}

Then say you want to assemble a tuple out of a given set of indices, so
that, for example, MakeTupleFromIndices!(0,2,3) would return (byte, int,
float), and MakeTupleFromIndices!(1,4) would return (short, double). You
would then write it like this:

	template MakeTupleFromIndices(indices...) {
		alias MakeTupleFromIndices =
			TypeTuple!(GenerateElement!(indices[0]),
				MakeTupleFromIndices!(indices[1..$]));
	}

	static assert(is(MakeTupleFromIndices!(0, 2, 4) ==
			TypeTuple!(byte, int, double)));

This is a recursive template that assembles the final tuple
piece-by-piece. Each piece is looked up by instantiating
GenerateElement, which you can adapt to do whatever it is you need to do
to determine the desired type.

Once you have the TypeTuple, you can then use it to create Tuples of the
desired type:

	// Same as saying: alias Tuple1 = Tuple!(int, int, float);
	alias Tuple1 = Tuple!(MakeTupleFromIndices!(2, 2, 3));
	Tuple1 t1 = tuple(1, 2, 1.0);
	Tuple1 t2 = tuple(0, 1, 5.5);

	// Same as saying: alias Tuple2 = Tuple!(double, byte);
	alias Tuple2 = Tuple!(MakeTupleFromIndices!(4, 0));
	Tuple2 u1 = tuple(3.14159, 0xff);
	Tuple2 u2 = tuple(1.61803, 0xfe);

Of course, if you want to generate the values at compile-time as well,
then you'll have to use value tuples (which are actually the same as
TypeTuples -- the compiler built-in tuples can contain both types and
values, so "TypeTuple" is actually a misnomer). The most obvious way is
to use recursive templates in the same way as above to assemble the
tuple piecemeal, for example:

	template EvenNumbers(int n) {
		static if (n==1)
			alias EvenNumbers = TypeTuple!(n*2);
		else
			// This takes advantage of auto-expansion of
			// tuples.
			alias EvenNumbers =
				TypeTuple!(EvenNumbers!(n-1), n*2);
	}

	// Prints: tuple(2, 4, 6, 8, 10)
	pragma(msg, EvenNumbers!5);

Hope this helps.


T

-- 
Those who've learned LaTeX swear by it. Those who are learning LaTeX swear at it. -- Pete Bleackley