Practical additions to kdtree library

[Sylvain Bougerel]

> 2008/9/30 Prabhanjan Kambadur <pkambadu at indiana.edu>
>>
>> Dear Sylvain and Paul,
>>
>> Thank you for the interest. Just to clarify, I did not envision a KDTree
>> that would change dimensionality on the fly. The use case would be more
>> like:
>>
>> KDTree<MyCoordinateType> my_tree;
>> my_tree.set_dimension(3);
>> // use the tree
>> my_tree.wipe();
>> my_tree.set_dimension(5);
>> // use it again.
>>
>> Here, MyCoordinateType can be dynamically reconfigured. Of course, the
>> method names could be more fitting :-). The reason I mention this is because
>> we use the KDTree as a primary data structure in the library. We support
>> reconfiguring our library through a similar mechanism. Being a staunch
>> supporter of the generic programming paradigm, I am all for compile-time
>> polymorphism. At the same time, I have been convinced by the scientists we
>> work with at the IBM T J Watson Research Center that the dimensionality
>> really is a feature of the data set, and as such, should be a runtime
>> parameter (in this particular case at least).

I'm also convienced the dimensionality is a feature of the data set.
But, humm, generally the dimensionality of the data set is known at
compile time. However, I do understand why you need such a feature, or
rather why the scientist have requested it. Moreover, if we follow the
conversation, we can assume that you do have a lot of modification of
your data set.

This is a rather particular use case. Indeed, the first request of
this type I have seen. Well, there is two ways of approaching the
problem.

1. Creating a polymorphic wrapper for D in '[a, b]', and generating
all the necessary Kd-tree<D>. Not elegant, slower and bulky (lot's of
code generated), plus need 'a' and 'b' to be known.
2. Modifying the source code of the Kd-tree. The most elegant solution.

Funnily enough, I can't find anything that would do the job for you in
memory (without going through the hassle of a database).


>>
>> Actually, one could support setting the dimension both at compile-time and
>> at run-time. For example, one can imagine partial specialization of the
>> KDTree for a particular sentinel value of dimension.

Okay, supporting both implementation.

It's possible. But rather than a sentinel, I would prefer an explicit
name. Since some function will be shared, but not many, obviously,
both tree could stem from a sealed base class kdtree_base.

Something like a "mutable_kdtree" could be reconfigured on the fly.
There would not even be a need to "clean" the tree before actually...
another tree could be created from within the "dimension" method, all
the elements inserted, then both trees content would be swapped.

What do you think, Paul?