ekg/intervaltree

a minimal C++ interval tree implementation

intervaltree

Overview

An interval tree can be used to efficiently find a set of numeric intervals overlapping or containing another interval.

This library provides a basic implementation of an interval tree using C++ templates, allowing the insertion of arbitrary types into the tree.

Usage

Add #include "IntervalTree.h" to the source files in which you will use the interval tree.

To make an IntervalTree to contain objects of class T, use:

vector<Interval<T> > intervals;
T a, b, c;
intervals.push_back(Interval<T>(2, 10, a));
intervals.push_back(Interval<T>(3, 4, b));
intervals.push_back(Interval<T>(20, 100, c));
IntervalTree<T> tree;
tree = IntervalTree<T>(intervals);

Now, it's possible to query the tree and obtain a set of intervals which are contained within the start and stop coordinates.

vector<Interval<T> > results;
tree.findContained(start, stop, results);
cout << "found " << results.size() << " overlapping intervals" << endl;

The function IntervalTree::findOverlapping provides a method to find all those intervals which are contained or partially overlap the interval (start, stop).

Author: Erik Garrison [email protected]

License: MIT

intervaltree's Issues

why not visit items "in-order"?

the find* and visit* methods should return intervals "in-order" (i.e. left tree Intervals -> current vector Intervals -> right tree Intervals). This would guarantee the returned Intervals are sorted by start position when the stored Intervals are non-overlapping. Also, it would be nice to have an iterator interface over the tree which would allow users to use some common algorithms more efficiently than having to first create a vector. They could also modify the values stored in the IntervalTree rather than just copying them.

https://github.com/ekg/intervaltree/blob/master/IntervalTree.h#L166-L178

Documentation is incorrect

The example in the README:

  vector<Interval<T> > intervals;
  T a, b, c;
  intervals.push_back(Interval<T>(2, 10, a));
  intervals.push_back(Interval<T>(3, 4, b));
  intervals.push_back(Interval<T>(20, 100, c));
  IntervalTree<T> tree;
  tree = IntervalTree<T>(intervals);

doesn't compile.

E.g. wrap it in a function as follows, and try compiling:

template<typename T>
void foo() {
  vector<Interval<T> > intervals;
  T a, b, c;
  intervals.push_back(Interval<T>(2, 10, a));
  intervals.push_back(Interval<T>(3, 4, b));
  intervals.push_back(Interval<T>(20, 100, c));
  IntervalTree<T> tree;
  tree = IntervalTree<T>(intervals);
}

Problems include:

• the Interval and IntervalTree templates take two parameters, not one - Interval<T> and IntervalTree<T> are not correct. (Presumably it should be something like Interval<size_t, T> etc., like in interval_tree_test.cpp.

• the call to the constructor doesn't compile. If you call foo<bool>() and compile, you'll get errors along the lines of (summarizing):

  error: no matching conversion for functional-style cast from 'vector<Interval<size_t, bool> >' (aka 'vector<Interval<unsigned long, bool> >') to 'IntervalTree<size_t, bool>' (aka 'IntervalTree<unsigned long, bool>')
  
  // ...
  
  ./intervaltree/IntervalTree.h:92:5: note: candidate constructor not viable: no known conversion from 'vector<Interval<size_t, bool> >' (aka 'vector<Interval<unsigned long, bool> >') to 'IntervalTree<unsigned long, bool>::interval_vector &&' (aka 'vector<Interval<unsigned long, bool> > &&') for 1st argument
  

From the interval_tree_test.cpp test file, it looks like the constructor now takes an initializer list.

Not initializing `center` member variable in Constructor

In the first branch, when intervals < bucket size, the center private variable is not initialized.

intervaltree/IntervalTree.h

Lines 90 to 106 in 8fc4be9

	IntervalTree<T,K>(
	intervalVector& ivals,
	std::size_t depth = 16,
	std::size_t minbucket = 64,
	K leftextent = 0,
	K rightextent = 0,
	std::size_t maxbucket = 512
	)
	: left(nullptr)
	, right(nullptr)
	{
	--depth;
	IntervalStartSorter<T,K> intervalStartSorter;
	if (depth == 0 || (ivals.size() < minbucket && ivals.size() < maxbucket)) {
	std::sort(ivals.begin(), ivals.end(), intervalStartSorter);
	intervals = ivals;

Added some prints in the code. As an example, when given 7 intervals:

IVALS SIZE: 7
IV: Interval(99291, 99295): 1
IV: Interval(99317, 99655): 1
IV: Interval(99317, 99548): 1
IV: Interval(99328, 99435): 1
IV: Interval(99351, 99380): 1
IV: Interval(99417, 99546): 1
IV: Interval(99483, 99673): 1


CENTER IS: 844424930131969

...

IVALS SIZE: 10
IV: Interval(97007, 97087): 1
IV: Interval(97008, 97164): 1
IV: Interval(97009, 97389): 1
IV: Interval(97020, 97180): 1
IV: Interval(97049, 97124): 1
IV: Interval(97115, 97305): 1
IV: Interval(97120, 97241): 1
IV: Interval(97209, 97226): 1
IV: Interval(97228, 97412): 1
IV: Interval(97298, 97332): 1


CENTER IS: 1

Information in README outdated

The code presented in the README no longer reflects how the software is mean to be called, with all the changes to the templates it now requires two arguments and it's unclear how to call everything.

Versioned & tagged release?

Thanks!

Add support for dynamic interval tree

For example, insert/erase functions

minbucket maxbucket?

What is the point of the minbucket and maxbucket constructor parameters? Seems like there could just be one parameter maxbucket and if the user wants to max out the depth they could just use std::numeric_limitsstd::size_t::max()?

https://github.com/ekg/intervaltree/blob/master/IntervalTree.h#L115

errors during compilation

I get errors during compilation with gcc < 6.0 (gcc >=6.0 and clang++ are fine).

C:/Rtools/mingw_32/bin/g++  -std=c++0x -I"c:/R/include" -DNDEBUG -I../inst/include   -I"c:/RLibrary/Rcpp/include" -I"c:/RLibrary/BH/include" -I"c:/RLibrary/dplyr/include" -I"d:/Comp
In file included from ../inst/include/valr.h:6:0,
                 from RcppExports.cpp:4:
../inst/include/IntervalTree.h: In constructor 'IntervalTree<T, K>::IntervalTree(IntervalTree<T, K>::intervalVector&, std::size_t, std::size_t, K, K, std::size_t)':
../inst/include/IntervalTree.h:148:37: error: use of 'this' in a constant expression
                 if (interval.stop < center) {
                                     ^
../inst/include/IntervalTree.h:148:30: error: parse error in template argument list
                 if (interval.stop < center) {
                              ^
make: *** [RcppExports.o] Error 1

Any ideas? Might be related to #16?