interval range tree datastructure c++

Question

I have a requirement where I have to update the color of a graphical frontend based on some attribute value.The attribute value has different ranges ....say -30 to -45, -60 to -80 and so on.....So, I needed a datastaructure where I could store these ranges(prefill them)....And When I do determine the point , I would like to know the range in which this point falls either in O(1) Time or O(logN) time....So, My Query would consist of a single point and the output should be a unique range containing that point...

I am confused between range trees and segment trees....i want to build the tree on top of c++ stl map.

I'm not sure, if I understand what you want. Can you give a simple example? — MikeMB, Jan 20 '15 at 19:56
possible duplicate of [How to find if a point is within a set of intervals?](http://stackoverflow.com/questions/10130701/how-to-find-if-a-point-is-within-a-set-of-intervals) — Michal Hosala, Jan 20 '15 at 19:59
The ranges Would be say 30-45, 45-70,70-85.....And I read an attribute value....Now I want to know which interval(range) this attribute belongs to? — basav, Jan 20 '15 at 20:00

Ashot · Accepted Answer · 2015-01-20T20:10:56.350

6

What you need is called interval tree. http://en.wikipedia.org/wiki/Interval_tree. Unfortunately you can't use std::set<> to get O(log N) insert, remove and query, because tree node needs to contain additional data. You can read about them here http://syedwaqarahmad.webs.com/documents/t.cormen-_introduction_to_algorithms_3rd_edition.pdf chapter 14.3.

Instead you can use boost. It has interval container library.

http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html

edited Jan 20 '15 at 20:10

answered Jan 20 '15 at 19:56

Ashot

10,807
14
66
117

Interval tree uses an interval as input and gives the overlapping intervals as output??Correct me if i am wrong – basav Jan 20 '15 at 20:05
Exactly, if you give a point (interval where left and right are equal) then you will get intervals that contain the point – Ashot Jan 20 '15 at 20:07
Ok.got it now....So, even when you insert, there is no concept of single point...Everything is based on intervals...Thanks. – basav Jan 20 '15 at 20:11

score 1 · Answer 2 · answered Jan 20 '15 at 19:57

1

Maybe this library can help you: https://github.com/ekg/intervaltree

answered Jan 20 '15 at 19:57

Philipp Claßen

41,306
31
146
239

score 1 · Answer 3 · answered Jan 20 '15 at 20:21

1

If I understand you correctly, you can du this quite easily with std::set:

#include <iostream>
#include <set>


struct Interval {
    int min;
    int max;
};

struct ComInt {
    bool operator()(const Interval& lhs, const Interval& rhs){
        return lhs.max < rhs.min;
    }
};

std::set<Interval, ComInt> intervals = { { -10, -5 }, { -4, 4 }, { 5, 10 } };


int main() {
    int point = 3;
    Interval tmp = { point, point };

    auto result=intervals.find(tmp);
    if (result != intervals.end()) {

        std::cout << "Min:" << result->min << " - Max:" << result->max << std::endl;
    } else {
        std::cout << "No matching Interval found" << std::endl;
    }
}

of course you should build a wrapper class around it

answered Jan 20 '15 at 20:21

MikeMB

20,029
9
57
102

this would be helpful for small number of intervals....It's definitely a handy solution...But What if I have a large number of intervals??I think the time complexity would result into O(n)... – basav Jan 20 '15 at 20:30
@basav: I don't think so, because std::set itself is usually implemented as a tree (set::find has logarithmic complexity) – MikeMB Jan 20 '15 at 20:33
Looked it up...It does guarantee a constant time complexit and in all likelihood be implemented as a RB Tree.. I will give it a try using std::set...I have around 100 intervals....Will try out both solutions.Thanks. – basav Jan 20 '15 at 20:37
@basav: If you have only 100 elements, a linear search on a vector might actually be even faster – MikeMB Jan 20 '15 at 20:39
Ya, but I would want the code to be scalable...Hence the extra effort to make it scalable.Not sure this fact matters but the compiler is pretty old too...it's not c++11 compliant. – basav Jan 20 '15 at 20:42
@basav: Then you are right of course (one should always measure anyway). If you have time to implement and test all three variants, I'd really like to see, where the break even point is. – MikeMB Jan 20 '15 at 21:05
I donot have that much time at workplace...But I will definitely do it in my own time and update the results by this weekend...I will update it here. – basav Jan 20 '15 at 21:07

interval range tree datastructure c++

3 Answers3

Linked