[boost] Interval Trees & ICL

Subject: [boost] Interval Trees & ICL
From: Bruce Adams (tortoise_74_at_[hidden])
Date: 2010-12-14 13:26:22

Hi,
    I have been working on a problem for which a suitable solution is an 
efficient container of intervals. 

The two main candidates would be something like to boost::split_interval_set or 
a centred interval tree
(along the lines of http://en.wikipedia.org/wiki/Interval_tree). 
It seems to me that the characteristics of an interval tree differ sufficiently 
from the containers defined in ICL that they might make a useful addition.
For the case where there is a potentially large number of overlapping intervals 
a split_interval_set will be less efficient
than an interval tree. In the worst case intervals would be split down to unit 
size.
Searching the archives I see there was some discussion of interval trees in the 
context of ICL but the additional of an interval tree
container did not, as far as I can tell, come up (perhaps because it should 
first appear in a boost release before there is any consideration
of adding to it?). I have a few questions:

1. Is there a specific name for the data structures provided by the ICL?

I have searched the literature and cannot find any mention of sets that split or 
combine intervals this way.
It is either a genuinely novel concept, which I find difficult to believe, or I 
haven't used the correct search terms (interval, extent or segment).
Either way, I would like to update wikipedia appropriately to help other lost 
souls.

2. Are there any compelling reasons why interval trees are less useful than the 
containers provided by the ICL?

3. Perhaps based on the answer to 2. Would interval trees be a sensible addition 
to the ICL?

4. Are there any other classes of interval container worthy of mention?

Regards,

Bruce.