
Boost : 
Subject: Re: [boost] Interval Trees & ICL
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 20101216 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 redblack 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 noninterval 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 btree[2].
But how to do it? I've used a few of my insomniac braincycles
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 quarterplane 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 Zcurve method [3] to do this efficiently for some years now and it
works well. The idea is that you bitwiseinterleave 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++ redblack 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/Zorder_(curve)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk