Re: std::map<> or std::set<> as interval search tree

From:

Maxim Yegorushkin <maxim.yegorushkin@gmail.com>

Newsgroups:

comp.lang.c++.moderated

Date:

Mon, 1 Sep 2008 13:45:44 CST

Message-ID:

<77929aa0-1e8c-4b6f-a833-70effbeeed69@f63g2000hsf.googlegroups.com>

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! ]