Boost logo

Boost :

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:
Boost people probably wouldn't find this useful in its present form,
but it could be useful for study.



Boost list run by bdawes at, gregod at, cpdaniel at, john at