Boost logo

Boost :

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.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk