I'm trying to find an efficient C++ interval tree implementation (mostly likely based on red black trees) without a viral or restrictive license. Any pointers to a clean lightweight standalone implementation? For the use case I have in mind, the set of intervals is known at the outset (there would be say a million) and I want to be able to quickly obtain a list of intervals that overlap a given interval. Thus the tree once built will not change -- just needs rapid queries.
I had exactly the same need. I couldn't find any suitable (simple, modern, portable) implementations, so I used a python implementation by Brent Pedersen as a guide and wrote a barebones C++ version. The IntervalTree behaves like a standard STL container, with some caveats due to its simplicity (no iterators, for instance). You use it like this ("T" is an arbitrary 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