A C++ header only interval tree implementation.
A C++ header only interval tree implementation, which takes a red black tree as its base to inhibit degeneration to linked lists.
// #include <interval-tree/draw.hpp> // to draw tree. this is not header only anymore.
#include <interval-tree/interval_tree.hpp>
int main()
{
using namespace lib_interval_tree;
// interval_tree <interval <int>>;
interval_tree_t <int> tree;
tree.insert(make_safe_interval<int>(21, 16)); // make_safe_interval swaps low and high if not in right order.
tree.insert({8, 9});
tree.insert({25, 30});
tree.insert({5, 8});
tree.insert({15, 23});
tree.insert({17, 19});
tree.insert({26, 26});
tree.insert({0, 3});
tree.insert({6, 10});
tree.insert({19, 20});
tree.deoverlap();
for (auto const& i : tree)
{
std::cout << "[" << i.low() << ", " << i.high() << "]\n";
}
}
Having googletest (find here on github) installed / built is a requirement to run the tests. Create a build folder, navigate there, run cmake and build the tree-tests target. You might have to adapt the linker line for gtest, if you built it yourself and didn't install it into your system. If you want to generate the pretty drawings, install cairo, pull the submodule and pass INT_TREE_DRAW_EXAMPLES=on to the cmake command line to generate a drawings/make_drawings executeable.
Creates an interval where the borders are sorted so the lower border is the first one.
Adds an interval into the tree.
ival
An intervalReturns: An iterator to the inserted element.
Inserts an interval into the tree if no other interval overlaps it. Otherwise merge the interval with the one being overlapped.
ival
An intervalexclusive
Exclude borders from overlap check. Defaults to false.mergeSetOverlapping
If the result of interval::join is a collection of intervals, shall each be inserted with more overlap searches? Defaults to falseReturns: An iterator to the inserted element.
Removes the interval given by iterator from the tree. (does not invalidate iterators).
iter
A valid non-end iteratorReturns: An iterator to the next element.
Returns the amount of nodes in the tree.
Returns: The amount of tree nodes.
Finds the first interval in the interval tree that has an exact match. WARNING: There is no special handling for floats.
ival
The interval to find.Returns: An iterator to the found element, or std::end(tree).
Finds the first interval in the interval tree that has the following statement evaluate to true: compare(interval_in_tree, ival); Allows for propper float comparisons.
ival
The interval to find.compare
The compare function to compare intervals with. Function is called like so: compare(interval_in_tree, ival).Returns: An iterator to the found element, or std::end(tree).
Find all intervals in the tree matching ival.
ival
The interval to find.on_find
A function of type bool(iterator) that is called when an interval was found.
Return true to continue, false to preemptively abort search.tree.insert({3, 7});
tree.insert({3, 7});
tree.insert({8, 9});
tree.find_all({3, 7}, [](auto iter) /* iter will be const_iterator if tree is const */ {
// will find all intervals that are exactly {3,7} here.
return true; // continue
});
Returns: An iterator to the found element, or std::end(tree).
Find all intervals in the tree that the compare function returns true for.
ival
The interval to find.compare
The compare function to compare intervals with. Function is called like so: compare(interval_in_tree, ival).on_find
A function of type bool(iterator) that is called when an interval was found.
Return true to continue, false to preemptively abort search.Returns: An iterator to the found element, or std::end(tree).
Finds the next exact match EXCLUDING from in the subtree originating from "from". You cannot find all matches this way, use find_all for that.
from
The iterator to start from. (including this iterator!)ival
The interval to find.Returns: An iterator to the found element, or std::end(tree).
Finds the next exact match EXCLUDING from in the subtree originating from "from". You cannot find all matches this way, use find_all for that.
from
The iterator to start from (including this iterator!)ival
The interval to find.compare
The compare function to compare intervals with. Function is called like so: compare(interval_in_tree, ival).Returns: An iterator to the found element, or std::end(tree).
Finds the first interval in the interval tree that overlaps the given interval.
ival
The interval to find an overlap for.exclusive
Exclude borders from overlap check. Defaults to false.Returns: An iterator to the found element, or std::end(tree).
Finds all intervals in the interval tree that overlaps the given interval.
ival
The interval to find an overlap for.on_find
A function of type bool(iterator) that is called when an interval was found.
Return true to continue, false to preemptively abort search.exclusive
Exclude borders from overlap check. Defaults to false.tree.insert({0, 5});
tree.insert({5, 10});
tree.insert({10, 15});
tree.overlap_find_all({5, 5}, [](auto iter) /* iter will be const_iterator if tree is const */ {
// called with {0, 5} and {5, 10} in unspecified order.
return true; // continue
});
Returns: An iterator to the found element, or std::end(tree).
Finds the next interval in the subtree originating in ival that overlaps the given interval. You cannot find all matches this way, use overlap_find_all for that.
ival
The interval to find an overlap for.exclusive
Exclude borders from overlap check. Defaults to false.Returns: An iterator to the found element, or std::end(tree).
Merges all overlapping intervals within the tree. After calling deoverlap, the tree will only contain disjoint intervals.
Returns: *this
Same as deoverlap, but not inplace
Removes all intervals from ival
and produces a tree that contains the remaining intervals.
The tree must be deoverlapped, or the result is undefined.
ival
is expected to encompass the entire interval range.
Returns: A new interval_tree containing the gaps.
Same as punch(interval_type const& ival), but with ival = [lowest_lower_bound, highest_upper_bound], resulting in only the gaps between existing intervals.
Returns whether or not the tree is empty.
Returns: Is this tree empty?
Returns the iterator of the interval with the lowest lower_bound.
Returns: begin iterator.
Returns a past the end iterator.
Returns: past the end iterator.
Returns the const_iterator of the interval with the lowest lower_bound.
Returns: begin iterator.
Returns a past the end const_iterator.
Returns: past the end const_iterator.
You can implement your own interval if you provide all the same functions.
The underlying interval numerical type
The interval kind. You dont need to provides this typedef in your interval class.
Comparison operator.
Comparison operator.
Lower bound.
Upper bound.
Overlap these bounds with this interval (closed)?
Overlap these bounds with this interval excluding borders?
Like overlaps with lower and upper bound.
Like overlaps with lower and upper bound.
Is the value within the interval (closed)?
Is the interval within the interval?
Calculates the distance between the two intervals. Overlapping intervals have 0 distance.
Returns high - low.
Joins 2 intervals and whatever is inbetween.