Re: std::map<> or std::set<> as interval search tree
On Aug 31, 11:58 pm, Rune Allnor <all...@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.
Here is a sketch:
~/src/test $ cat test.cpp
#include <set>
#include <cstdio>
struct interval
{
double start, end; // [start, end]
interval(double s, double e) : start(s), end(e) {}
};
bool operator<(interval const& a, interval const& b)
{
return a.start < b.start;
}
typedef std::set<interval> interval_set;
interval const* find(interval_set const& s, double point)
{
interval_set::const_iterator i = s.lower_bound(interval(point,
point));
if(i == s.end() || point < i->start) {
if(i == s.begin())
return NULL;
--i;
return point <= i->end && point >= i->start ? &*i : NULL;
}
return &*i;
}
void check(interval_set const& s, double point)
{
if(interval const* i = find(s, point))
printf("%f belongs to [%f,%f]\n", point, i->start, i->end);
else
printf("%f does not belong to any interval\n", point);
}
int main()
{
interval_set s;
s.insert(interval(0, 1));
s.insert(interval(3, 4));
for(double i = -1; i < 5; i += .5)
check(s, i);
}
~/src/test $ g++ -Wall -Wextra -o test test.cpp
~/src/test $ ./test
-1.000000 does not belong to any interval
-0.500000 does not belong to any interval
0.000000 belongs to [0.000000,1.000000]
0.500000 belongs to [0.000000,1.000000]
1.000000 belongs to [0.000000,1.000000]
1.500000 does not belong to any interval
2.000000 does not belong to any interval
2.500000 does not belong to any interval
3.000000 belongs to [3.000000,4.000000]
3.500000 belongs to [3.000000,4.000000]
4.000000 belongs to [3.000000,4.000000]
4.500000 does not belong to any interval
--
Max
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]