Passing arguments a template parameters vs. function parameters

Craig Dillabaugh cdillaba at cg.scs.carleton.ca
Tue Jun 11 13:46:31 PDT 2013


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


More information about the Digitalmars-d-learn mailing list