QuadTree or Octree templatized implementation in C++

Question

I'm going to write a templatized implementation of a KDTree, which for now should only work as Quadtree or Octree for a BarnesHut implementation.

The crucial point here is the design, I would like to specify the number of dimension where the tree is defined as template parameter and then simply declare some common methods, which automatically behave the correct way (I think some template specialization is needed then).

I would like to specialize the template in order to have 2^2 (quadtree) or 2^3 (octree) nodes.

Do someone have some design ideas? I would like to avoid inheritance because it constrains me to do dynamic memory allocation rather than static allocations.

Here N can be 2 or 3

template<int N>
class NTree
{
public:
    NTree<N>( const std::vector<Mass *> &);
    ~NTree<N>()
    {
       for (int i=0; i<pow(2,N); i++)
          delete nodes[i];
    }
 private:
    void insert<N>( Mass *m );
    NTree *nodes[pow(2,N)]; // is it possible in a templatized way?
};

Another problem is that quadtree has 4 nodes but 2 dimension, octree has 8 nodes, but 3 dimension, i.e. number of nodes is 2^dimension. Can I specify this via template-metaprogramming? I would like to keep the number 4 and 8 so the loop unroller can be faster.

Thank you!

Shipp

You are using the term "leaf" incorrectly, the correct term is "node". A "leaf" is a node without any children. – Coulometer

You are also mixing kdtrees and quad/octree incorrectly, they're not the same (i.e. a 2D-tree is not equal to a quadtree).. – Butler

Right, I simply want a n-ary tree which behaves like quadtree in 2D and octree in 3D, I'm editing the question. – Shipp

Answer 1

You can use 1 << N instead of pow(2, N). This works because 1 << N is a compile-time constant, whereas pow(2, N) is not a compile time constant (even though it will be evaluated at compile-time anyway).

Coulometer

Nice idea! thank you! Do you also think a templatized implementation of this kind is feasible or good? – Shipp

No. I think the template code will be more difficult to write and read than two separate implementations: one quadtree and one octree. It is unlikely that you will encounter N=2 since we have better data structures specialized for one-dimensional data, and N>3 is unlikely due to the exponential growth of the size of each node. – Coulometer

You're right, but I'm also using a templatized linear algebra library for vector and matrix operations (eigen), it seems is a matter of checking if N==2 or N==3, and then write the code consequently. I wanted to join the two implementations for maintenance purposes. I'll keep you informed – Shipp

Answer 2

If you are using a C++11 compiler that supports constexpr you could write yourself a constexpr-version of pow to do the calculation at runtime.

Nutria

Unfortunately I can't have such compiler, and some features of C++11 are still obscure to me :P – Shipp

You can do that in C++03 as well. A simple recursive template meta-function for integral powers is really easy to make. Bud if the base is always 2, you're far better off with bit shifting, as Dietrich Epp suggests. – Agathy