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

Subject: Re: [boost] [itl] Preview 4 of the Interval Template Library
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-03-05 05:11:29

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.