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)