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>>; // closed by default
// interval_tree<interval<int, open>>;
// interval_tree<interval<int, closed>>;
// interval_tree<interval<int, left_open>>;
// interval_tree<interval<int, right_open>>;
// interval_tree<interval<int, closed_adjacent>>; // counts adjacent intervals as overlapping
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";
}
// dynamic has some logic overhead.
interval_tree<interval<int, dynamic>> dynamicIntervals;
dynamicIntervals.insert({0, 1, interval_border::closed, interval_border::open});
dynamicIntervals.insert({7, 5, interval_border::open, interval_border::closed_adjacent});
}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.
Some features of this library require the presence of an optional type. If you are using C++17 and up, it will be std::optional. Otherwise you can specify INTERVAL_TREE_HAVE_BOOST_OPTIONAL to use boost::optional. And if neither, a reduced version of optional is provided in the library, not perfectly exchangeable with std::optional, but sufficient for the library to work.
This draws a dot graph of the tree:
#include <interval-tree/interval_tree.hpp>
#include <interval-tree/dot_graph.hpp>
int main()
{
using namespace lib_interval_tree;
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});
draw_dot_graph(
std::cout,
tree,
{
// digraph or graph?
.digraph = true,
// graph name
.name = "G",
// extra node attributes
.extra_node_attributes = {"color=red"},
// extra graph statements
.extra_statements = {"rankdir=LR"},
// put space after comma of interval label? (a,b) vs (a, b)
.space_after_comma = false,
// left brace override enabled if not 0, otherwise determined from interval kind
.left_brace = '\0',
// right brace override enabled if not 0, otherwise determined from interval kind
.right_brace = '\0',
// edge attributes
.edge_attributes = {"color=blue"},
// indent characters
.indent = "\t",
}
);
}Creates an interval where the borders are sorted so the lower border is the first one.
Draws a dot graph of the interval tree to the output stream. Options are:
- digraph: bool
- name: std::string
- extra_node_attributes: std::vector<std::string>
- extra_statements: std::vector<std::string>
- space_after_comma: bool
- left_brace: char (0 = ignored, std::optional is c++17)
- right_brace: char (0 = ignored, std::optional is c++17)
- edge_attributes: std::vector<std::string>
- indent: std::string
- interval-tree
- How an interval tree looks like:
- Example
- Compile & Run Testing
- Draw Dot Graph
- Free Functions
- Members of IntervalTree
- iterator insert(interval_type const& ival)
- iterator insert_overlap(interval_type const& ival, bool, bool)
- iterator erase(iterator iter)
- size_type size() const
- (const)iterator find(interval_type const& ival)
- (const)iterator find(interval_type const& ival, CompareFunctionT const& compare)
- (const)iterator find_all(interval_type const& ival, OnFindFunctionT const& on_find)
- (const)iterator find_all(interval_type const& ival, OnFindFunctionT const& on_find, CompareFunctionT const& compare)
- (const)iterator find_next_in_subtree(iterator from, interval_type const& ival)
- (const)iterator find_next_in_subtree(iterator from, interval_type const& ival, CompareFunctionT const& compare)
- (const)iterator overlap_find(interval_type const& ival, bool exclusive)
- (const)iterator overlap_find_all(interval_type const& ival, OnFindFunctionT const& on_find, bool exclusive)
- (const)iterator overlap_find_next_in_subtree(interval_type const& ival, bool exclusive)
- interval_tree& deoverlap()
- After deoverlap
- interval_tree deoverlap_copy()
- interval_tree punch(interval_type const& ival)
- Before punching (closed intervals)
- After punching (with [-10, 60])
- interval_tree punch()
- bool empty() const noexcept
- iterator begin()
- iterator end()
- iterator cbegin()
- iterator cend()
- reverse_iterator rbegin()
- reverse_iterator rend()
- reverse_iterator crbegin()
- reverse_iterator crend()
- void erase_range(interval_type const& ival)
- void erase_range(interval_type const& ival, bool retainSlices)
- Members of Interval
- using value_type
- using interval_kind
- friend bool operator==(interval const& lhs, interval const& other)
- friend bool operator!=(interval const& lhs, interval const& other)
- value_type low() const
- value_type high() const
- DEPRECATED bool overlaps(value_type l, value_type h) const
- bool overlaps_exclusive(value_type l, value_type h) const
- bool overlaps(interval const& other) const
- bool overlaps_exclusive(interval const& other) const
- bool within(value_type value) const
- bool within(interval const& other) const
- value_type operator-(interval const& other) const
- value_type size() const
- interval join(interval const& other) const
- slice_type slice(interval c AB6E onst& other) const
Adds an interval into the tree.
ivalAn interval
Returns: 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.
ivalAn intervalexclusiveExclude borders from overlap check. Defaults to false.recursiveIf the result of interval::join is a collection of intervals, shall each be inserted with more overlap searches? If the result is a single interval, shall it be inserted via insert_overlap or insert? Defaults to false. recursive=true picks insert_overlap. Also be careful to not produce overlapping merge sets when doing recursive insertion, or it will recurse endlessly.
Returns: An iterator to the inserted element.
Removes the interval given by iterator from the tree. (does not invalidate iterators).
iterA valid non-end iterator
Returns: 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.
ivalThe 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.
ivalThe interval to find.compareThe 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.
ivalThe interval to find.on_findA 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).
(const)iterator find_all(interval_type const& ival, OnFindFunctionT const& on_find, CompareFunctionT const& compare)
Find all intervals in the tree that the compare function returns true for.
ivalThe interval to find.compareThe compare function to compare intervals with. Function is called like so: compare(interval_in_tree, ival).on_findA 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.
fromThe iterator to start from. (including this iterator!)ivalThe interval to find.
Returns: An iterator to the found element, or std::end(tree).
(const)iterator find_next_in_subtree(iterator from, interval_type const& ival, CompareFunctionT const& compare)
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.
fromThe iterator to start from (including this iterator!)ivalThe interval to find.compareThe 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.
ivalThe interval to find an overlap for.exclusiveExclude borders from overlap check. Defaults to false.
Returns: An iterator to the found element, or std::end(tree).
(const)iterator overlap_find_all(interval_type const& ival, OnFindFunctionT const& on_find, bool exclusive)
Finds all intervals in the interval tree that overlaps the given interval.
ivalThe interval to find an overlap for.on_findA function of type bool(iterator) that is called when an interval was found. Return true to continue, false to preemptively abort search.exclusiveExclude 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.
ivalThe interval to find an overlap for.exclusiveExclude 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
Cuts the intervals of the tree out of the given interval. Like a cookie cutter cuts out of dough. This will return a new interval_tree containing the gaps between the intervals in the tree and the given interval. Closed adjacent intervals are treated as exclusive on the borders. [0,5]a[6,10]a will not produce another interval between 5 and 6 as they are considered within the intervals and nothing fits inbetween. Regular closed intervals will not behave like this, so [0,5][6,10] will produce a new interval [5,6]. Open intervals with integral numbers will also not produce the gap (5, 6), because (5, 6) is empty for integers, not for floats.
IMPORTANT! The tree must be deoverlapped, or the result is undefined.
ival can be any subrange of the tree, including encompassing the whole tree.
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.
Returns the iterator of the interval with the highest lower_bound.
Returns: rbegin iterator.
Returns a past the end iterator in reverse.
Returns: past the end iterator.
Returns the const_iterator of the interval with the highest lower_bound.
Returns: begin iterator.
Returns a past the end const_iterator in reverse.
Returns: past the end const_iterator.
Removes all intervals overlapping ival from the tree
Removes all intervals overlapping ival from the tree, but retains the overlap beyond the erase interval.
You can implement your own interval if you provide the same functions, except (slice, operator-, size, operator!=).
There are 6 types of intervals:
- open: (a, b)
- left_open: (a, b]
- right_open: [a, b)
- closed: [a, b]
- closed_adjacent: [a, b] (counts adjacent intervals as overlapping)
- dynamic: Can be any of the above, depending on the input. Not supported for floating point.
Which can be picked with the second template parameter of interval:
lib_interval_tree::interval<int, lib_interval_tree::open>
- Members of Interval
- using value_type
- using interval_kind
- friend bool operator==(interval const& lhs, interval const& other)
- friend bool operator!=(interval const& lhs, interval const& other)
- value_type low() const
- value_type high() const
- DEPRECATED bool overlaps(value_type l, value_type h) const
- bool overlaps_exclusive(value_type l, value_type h) const
- bool overlaps(interval const& other) const
- bool overlaps_exclusive(interval const& other) const
- bool within(value_type value) const
- bool within(interval const& other) const
- value_type operator-(interval const& other) const
- value_type size() const
- interval join(interval const& other) const
- slice_type slice(interval const& other) const
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? Is deprecated because the overlapping does not work with the dynamic interval type.
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?
Is the interval within the interval?
Calculates the distance between the two intervals. Overlapping intervals have 0 distance.
Returns The amount of elements in the interval when integral, or the distance between the 2 bounds when floating point.
Joins 2 intervals and whatever is inbetween.
Removes other from this interval returning what is remaining. The range of other going beyond the range of this is ignored. Returns a struct with 2 members: left_slice and right_slice.
[ this interval ]
[left][other][right]
When the intervals are closed_adjacent, adjacent results are differenty by 1. [0, 9].slice([5, 19]) => left: [0, 4], right: nullopt