Skip to content

a minimal C++ interval tree implementation

License

Notifications You must be signed in to change notification settings

PankajBhojwani/intervaltree

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

68 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

About

a minimal C++ interval tree implementation

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages

  • C++ 99.8%
  • Makefile 0.2%