Re: [boost] [itl] Preview 4 of the Interval Template Library

Subject: Re: [boost] [itl] Preview 4 of the Interval Template Library
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2009-03-05 16:52:03

2009/3/5 Phil Endecott <spam_from_boost_dev_at_[hidden]>:
> 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_itl.introduction.interval_combining_styles

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