C++ - interval tree implementation

Question

Does someone know any good interval tree implementation in C++?

Obviously, something template-driven, better in boost-like style.

And another question - if somebody tested, does a basic std::vector-based interval tree implementation with sorting can beat the generic interval tree (with O(lg) operations) in practice?

Erik Garrison · Answer 1 · 2011-11-04T19:43:05.170

22

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

edited Nov 04 '11 at 19:43

answered Nov 04 '11 at 19:09

Erik Garrison

1,697
1
14
13

Hi Erik thanks for pointing this. I am looking at your code and trying to relate to the theory (please bear in mind I am new to this.)`sanityIntervals.push_back(interval(60, 80, true));` and ` for (int i = 0; i < 10000; ++i) { intervals.push_back(randomInterval(100000, 1000, 100000 + 1, true)); }`. I have been looking at fork-event-join models with id,event pairing. Can you elaborate how did you come up with those numbers - 60,80,etc and what is bool value chosen object? Say I have a distributed system - one server and multiple clients, how can I utilize your code? – enthusiasticgeek Nov 30 '14 at 20:17
Unfortunately, the find functions return a copy of the internal iterator which means a copy operation is needed for every query operation. This is very slow in a large application. While the code works but it's slow. – ABCD Dec 22 '15 at 10:02
@SmallChess absolutely not. The whole point of returning by value in non flow-diverging functions such as this, is to be certain of NRVO (named return value optimization). Not to mention in some situations copy elision is flat mandatory by standard. – v.oddou Jun 25 '19 at 09:29

score 18 · Accepted Answer · answered Mar 23 '11 at 15:53

18

Boost-like ? Boost ICL!

The Boost Interval Container Library

answered Mar 23 '11 at 15:53

Matthieu M.

287,565
48
449
722

Hm, nice timing from `boost`. I though current version was 1.45 and I didn't know I was so lucky. Thanks – Yippie-Ki-Yay Mar 23 '11 at 15:54
@Yippie: just discovered it recently (by @ybungalobill I think) myself :) – Matthieu M. Mar 23 '11 at 16:34
If anyone knows why this answer has received one upvote and one downvote today after a few months of inactivity, I'd be really glad to learn about it! – Matthieu M. Nov 04 '11 at 20:52
17

I supplied a down vote, as the question is about interval trees, but this response only supplied a link to an interval container library in boost which doesn't have a query-tree implementation. [This message on the boost mailing list indicates this deficiency, but no solution has been provided as of this date.](http://lists.boost.org/Archives/boost/2010/12/174073.php) Of course, it seems the question author was satisfied with this response, so maybe I am just in need of a new question to reply to :) – Erik Garrison Nov 04 '11 at 22:35
@Erik: Thanks for the heads up! I admit I've never used Interval Trees (past the playground...) and I wrote them myself when reading the "Introduction to Algorithms". It's good to note that there are various needs in the manipulation. – Matthieu M. Nov 05 '11 at 14:43

score 2 · Answer 3 · answered Aug 16 '13 at 04:21

2

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

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

answered Aug 16 '13 at 04:21

ijoseph

6,505
4
26
26

score 1 · Answer 4 · answered Jan 24 '14 at 08:37

1

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

Look class itree in itree.h.

answered Jan 24 '14 at 08:37

Vitaly

56
8

score 0 · Answer 5 · answered Jul 25 '12 at 00:08

0

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

answered Jul 25 '12 at 00:08

cos

97
1

C++ - interval tree implementation

5 Answers5

Linked

Related