[ACCEPTED]-C++ - interval tree implementation-interval-tree

Accepted answer

Score: 22

I had exactly the same need. I couldn't 7 find any suitable (simple, modern, portable) implementations, so 6 I used a python implementation by Brent Pedersen as a guide and wrote a barebones 5 C++ version. The IntervalTree behaves like a standard 4 STL container, with some caveats due to 3 its simplicity (no iterators, for instance). You 2 use it like this ("T" is an arbitrary 1 type):

vector<Interval<T> > intervals;
// ... make intervals!
IntervalTree<T> tree(intervals);

And you query it like this:

vector<Interval<T> > results;
tree.findContained(start, stop, results);
// results now contains Intervals which are fully contained in the query interval
results.clear();
tree.findOverlapping(start, stop, results);
// results now contains Intervals which overlap the query interval

Score: 15

Boost-like ? Boost ICL!

The Boost Interval Container Library

Score: 1

There appears to be one in the NCBI C++ Toolkit.

Jury's still out 4 on whether it's "good," though 3 (and even whether it's template-driven; I'm 2 still somewhat new to C++, so I'm not entirely 1 sure that it is, but I suspect as much).

Score: 1

I uploaded simple implementation of Interval 1 Tree to github: https://github.com/coolsoftware/ITree

Look class itree in itree.h.

Score: 0

if you don't mind translating a c# implementation 2 to c++, goto http://code.google.com/p/intervaltree/ .based on an avl self balancing 1 tree.

Source: stackoverflow.com

[ACCEPTED]-C++ - interval tree implementation-interval-tree

Data Structures... so how do I understand them?

Least Recently Used cache using C++

Sorting Coordinate Points c++

remove global variables in c++ program

ID data member in c++ class

In what circumstances lock free data structures are faster than lock based ones?

Modeling a pipeline in C++ with replaceable stages

Does any stl::set implementation not use a red-black tree?

Concatenating/Merging/Joining two AVL trees

Get random element and remove it