I was looking at D code for constructing kd-trees, the full code listing for which can be found here:
http://rosettacode.org/wiki/K-d_tree#Faster_Alternative_Version Of particular interest were the following functions: KdNode* makeTree(size_t dim, size_t i)(KdNode[] nodes) pure nothrow { if (!nodes.length) return null; auto n = findMedian!i(nodes); if (n != null) { enum i2 = (i + 1) % dim; immutable size_t nPos = n - nodes.ptr; n.left = makeTree!(dim, i2)(nodes[0 .. nPos]); n.right = makeTree!(dim, i2)(nodes[nPos + 1 .. $]); } return n; } // See QuickSelect method. KdNode* findMedian(size_t idx)(KdNode[] nodes) pure nothrow { auto start = nodes.ptr; auto end = &nodes[$ - 1] + 1; if (end <= start) return null; if (end == start + 1) return start; KdNode* md = start + (end - start) / 2; //clipped for sake of brevity. } A kd-tree is a search structure for storing multi-dimensional points. At each level it splits the input point set along a plane in one of the dimensions. In the code above this is the value pased as 'idx' to findMedian. findMedian finds the median point in the current dimension, and uses this to define the splitting plane for the points. At each level in the tree the splitting dimension is changed (which is what i/i2 is used for in makeTree()). If I had been coding this I would almost certainly have passed the splitting dimensions as a function parameter, since the compiler has to generate separate makeTree/findMedian functions for each dimension that i/idx takes in the program. So my question is, does anyone have any idea why the author may have used templates here. It was on Rosettacode so maybe they are just there to show off D's nice template abilities, but I am curious if in idiomatic D using templates this way is somehow superior to the function parameter method I would have tried. Cheers, Craig
