2009/3/5 Phil Endecott <spam_from_boost_dev@chezphil.org>:
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.
Yes, different. Itl containers use std::set and and std::map as implementing containers. Sorry, I should have mentioned that in my post: A section about the implementation and it's complexity is one of the important things that is still missing from the documentation. I will do that next. Itl's interval containers are different from interval trees. The most important difference is, that interval trees store all intervals that are inserted into them while itl interval containers only stores the resulting collection of non overlapping intervals. see http://herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/index.html#boost_... So intervals in itl interval containers do never overlap. But you can compute the overlap count of a set of intervals as aggregation result using an interval_map.
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
Roughly ... Time complexity of insert depends on the size of the inserted interval. Worst case is O(n lg(n)), if the inserted interval overlaps with all intervals in the container. For small intervals complexity approaches that of inserting singleton intervals: O(lg(n)) Lookup of an element is O(lg(n)). Lookup for intervals is not implemented, but an interval container can be intersected with an interval to obtain the result as intersection which has a worst case time complexity of O(n lg(n)). Again efficiency is much better here, and for other operations on interval containers, if the interval size is relatively small compared to the enclosing interval of the container and approaches O(lg(n)) then.
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?
you could implement that via an interval_map<float, itl::set<ItemPtr> > item_map; But I admit this would work far less efficient than an interval tree, specifically if the inserted intervals are all of similar size. Joachim