Re: [boost] Interval Trees & ICL

Subject: Re: [boost] Interval Trees & ICL
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2010-12-16 15:02:23

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

Hi everyone,

Bruce's post got me thinking about this problem again.  Of course an 
interval tree, such as one based on a red-black tree as Dave suggests, 
would be a fantastic thing to have in Boost [1].  However something I 
think would be even better would be some sort of "interval adaptor" 
that would allow some existing non-interval container to be efficiently 
adapted to store intervals.  This could be used on top of a std::map, 
but the reason why I'd like it is that it could also be used with 
something like Beman's proposed b-tree[2].

But how to do it?  I've used a few of my insomniac brain-cycles 
thinking about this, and I may have finally come up with a solution.  
My idea is to consider an interval (low,high) as a point in a 2D 
plain.  Then, a query to find all of the intervals overlapping (a,b) is 
the same as the query to find all the points in the quarter-plane where 
low<b and high>a.

Any 2D data structure could be used to store these (e.g. quadtrees 
etc), but the aim here is to adapt a 1D data structure.  I have used 
the Z-curve method [3] to do this efficiently for some years now and it 
works well.  The idea is that you bitwise-interleave the two values and 
use this as the key.  You can then iterate over all points in a 
rectangle by iterating over all points in the 1D range between the 
interleaved bottom left and top right corner values.  A restriction is 
that the types must be suitable for this bitwise interleaving, i.e. 
floating point types don't work.

It's unlikely that I am the first to think of this, but I've not found 
yet any references.  Perhaps I'm searching for the wrong things.

Any thoughts anyone?

Regards,  Phil.

[1] For the record, there is a C++ red-black interval tree here:
http://cs.montana.edu/~bohannan
Boost people probably wouldn't find this useful in its present form, 
but it could be useful for study.

[2] http://mysite.verizon.net/beman/btree/index.html

[3] http://en.wikipedia.org/wiki/Z-order_(curve)