Re: std::map<> or std::set<> as interval search tree
on Sun Aug 31 2008, Rune Allnor <allnor-AT-tele.ntnu.no> wrote:
Hi all.
I have an application where the set of real numbers is divided into
a finite number of intervals (view with fixed-width font):
------------+---------+--------+---------+--------
a x b c d
Given a number x I would like to find the interval which contains x.
Searching for the interval is more efficient when a search tree
data structure is used, which is why I want to use std::map<>
or std::set<>. These implement tree-structures and if at all
possible, I would avoid to implement a tree from scratch myself.
However, both std::map and std::set will return an 'invalid' code
unless an item with the exact value of the search argument is
contained in the tree.
So given a number x, a < x < b, how do I implement the structure
such that a call to exists() returns a pointer to the interval
[a,b>? The pointer itself might be the value (or index or iterator) of
one of the end intervals; it has to be something that uniquely
identifies the interval where x belongs.
Note that I need to be able to locate numbers outside the present
limits, such that x < a returns some code indicating [-inf,a>
and a value x > d returns a value indicating [d,inf>.
Any suggestions?
There's something called an "interval tree." IIRC it stores each
interval by its start position and annotates each node additionally with
the maximum end position of all its descendant nodes. I implemented one
years ago with minor modifications of STLPort's rbtree implementation
that underlay its associative containers. Ah, yes:
http://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
On the other hand, that's allows overlapping intervals, and it looks
like your example doesn't have overlaps. If not, you could use one of
the std associative containers (or a sorted vector) with a key that is
the beginning of each interval, and use upper_bound to find the position
where x falls in the sequence. I leave dealing with the endpoints as an
exercise for the reader ;-)
--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]