Hi Joachim, Joachim Faulhaber wrote:
I am happy to announce that the Interval Template Library (Boost.Itl) converges to a state, that conforms the standards of the boost libraries. It now contains substantial test suites and almost complete quickbook documentation. I hope it will soon be mature for a formal review after a last round of feedback and subsequent improvements.
I have an application for which I have been considering implementing an interval tree (i.e. http://en.wikipedia.org/wiki/Interval_tree). A quick look at your docs does not reveal the implementation that you are using, but I have the impression that it's something different. Can you comment on the complexity / efficiency of whatever you're doing compared to a traditional interval tree? I.e. complexity for insert and lookup, storage required, number of bytes of overhead per element etc. To make that concrete, say I have N items and for each I store one pointer indexed by an interval of floats. How much space is needed, and how much time is needed to find the M items that (partially) overlap some interval? Sorry if this is in the docs somewhere but I couldn't find it. Cheers, Phil.