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.

Answer 1

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

Answer 2

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

Answer 3

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