Implement QuadTree or Octree in C ++

Question

I am going to write a KDTree boilerplate implementation that should now only work as Quadtree or Octree for the BarnesHut implementation.

The decisive point here is the design, I would like to indicate the number of dimensions where the tree is defined as a template parameter, and then just declare some common methods that automatically behave correctly (I think you need a special specialization of the template at that time).

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

Does anyone have any design ideas? I would like to avoid inheritance, because it limits me to dynamic memory allocation, not static allocations.

Here N may 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 dimensions, octree has 8 nodes but 3 dimensions, i.e. number of nodes 2^dimension . Can I indicate this using a metaprogramming pattern? I would like to keep the numbers 4 and 8 in order to speed up the loop.

Thanks!

Answer 1

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

Answer 2

If you use a C ++ 11 compiler that supports constexpr , you can write a constexpr pow to execute at runtime.