#include <genesis/utils/containers/interval_tree/fwd.hpp>
Interval tree that enables storing and querying intervals, each containing some data.
The implementation takes a red black tree as its base to inhibit degeneration to linked lists. It is based on intervaltree, which is published under the CC01.0 License (Creative Commons Zero v1.0 Universal); see our Acknowledgements for further details, and see Interval, IntervalTreeNode, and IntervalTreeIterator for the other classes based on the original code.
Public Member Functions  
IntervalTree ()  
IntervalTree (IntervalTree &&)=default  
IntervalTree (IntervalTree const &other)  
~IntervalTree ()  
iterator  begin () 
const_iterator  begin () const 
const_iterator  cbegin () const 
const_iterator  cend () const 
void  clear () 
Remove all nodes from this tree. More...  
bool  empty () const noexcept 
Return wether or not the tree is empty. More...  
iterator  end () 
const_iterator  end () const 
iterator  erase (iterator iter) 
Erase the element pointed to be iter. More...  
iterator  find (interval_type const &ival) 
Find the first exact match. More...  
const_iterator  find (interval_type const &ival) const 
Find the first exact match. More...  
template<typename CompareFunctionT >  
iterator  find (interval_type const &ival, CompareFunctionT const &compare) 
Find the first exact match. More...  
template<typename CompareFunctionT >  
const_iterator  find (interval_type const &ival, CompareFunctionT const &compare) const 
Find the first exact match. More...  
template<typename FunctionT >  
void  find_all (interval_type const &ival, FunctionT const &on_find) 
Find all exact matches and execute a function for each of them. More...  
template<typename FunctionT >  
void  find_all (interval_type const &ival, FunctionT const &on_find) const 
Find all exact matches and execute a function for each of them. More...  
template<typename FunctionT , typename CompareFunctionT >  
void  find_all (interval_type const &ival, FunctionT const &on_find, CompareFunctionT const &compare) 
Find all exact matches and execute a function for each of them. More...  
template<typename FunctionT , typename CompareFunctionT >  
void  find_all (interval_type const &ival, FunctionT const &on_find, CompareFunctionT const &compare) const 
Find all exact matches and execute a function for each of them. More...  
iterator  find_next_in_subtree (iterator from, interval_type const &ival) 
Find the next exact match EXCLUDING from. More...  
const_iterator  find_next_in_subtree (iterator from, interval_type const &ival) const 
template<typename CompareFunctionT >  
iterator  find_next_in_subtree (iterator from, interval_type const &ival, CompareFunctionT const &compare) 
Find the next exact match EXCLUDING from. More...  
template<typename CompareFunctionT >  
const_iterator  find_next_in_subtree (iterator from, interval_type const &ival, CompareFunctionT const &compare) const 
IntervalTree &  flatten () 
Flatten the tree. More...  
IntervalTree  flatten_copy () 
Flatten the tree, but returns it as a copy. More...  
numerical_type  highest () const 
Return the highest high value of the contained Intervals. More...  
iterator  insert (interval_type &&ival) 
Insert an Interval into the tree. More...  
iterator  insert (interval_type const &ival) 
Insert an Interval into the tree. More...  
iterator  insert_overlap (interval_type const &ival, bool exclusive=false) 
Insert an interval into the tree if no other interval overlaps it. Otherwise merge the interval with the being overlapped. More...  
iterator  insert_overlap (interval_type const &ival, data_type &&data, bool exclusive=false) 
Insert an interval into the tree if no other interval overlaps it. Otherwise merge the interval with the being overlapped, and use data for this interval. More...  
iterator  insert_overlap (interval_type const &ival, data_type const &data, bool exclusive=false) 
Insert an interval into the tree if no other interval overlaps it. Otherwise merge the interval with the being overlapped, and use data for this interval. More...  
numerical_type  lowest () const 
Return the lowest low value of the contained Intervals. More...  
IntervalTree &  operator= (IntervalTree &&)=default 
IntervalTree &  operator= (IntervalTree const &other) 
iterator  overlap_find (interval_type const &ival, bool exclusive=false) 
Find the first interval that overlaps with ival. More...  
const_iterator  overlap_find (interval_type const &ival, bool exclusive=false) const 
iterator  overlap_find (numerical_type position) 
Find the first interval that overlaps with the given position. More...  
const_iterator  overlap_find (numerical_type position) const 
Find the first interval that overlaps with the given position. More...  
template<typename FunctionT >  
void  overlap_find_all (interval_type const &ival, FunctionT const &on_find, bool exclusive=false) 
Find all intervals that overlap with a given interval. More...  
template<typename FunctionT >  
void  overlap_find_all (interval_type const &ival, FunctionT const &on_find, bool exclusive=false) const 
template<typename FunctionT >  
void  overlap_find_all (numerical_type position, FunctionT const &on_find) 
Find all intervals that overlap with a given position. More...  
template<typename FunctionT >  
void  overlap_find_all (numerical_type position, FunctionT const &on_find) const 
Find all intervals that overlap with a given position. More...  
const_iterator  overlap_find_next_in_subtree (const_iterator from, interval_type const &ival, bool exclusive=false) const 
iterator  overlap_find_next_in_subtree (iterator from, interval_type const &ival, bool exclusive=false) 
Find the next interval that overlaps with ival. More...  
IntervalTree  punch () const 
Create an interval tree that contains all gaps between the intervals as intervals. More...  
IntervalTree  punch (interval_type const &ival) const 
Create an interval tree that contains all gaps between the intervals as intervals. More...  
iterator  root () 
Return the root node from this tree. More...  
const_iterator  root () const 
Return the root node from this tree. More...  
size_t  size () const 
Return the size of the object, that is, the number of Intervals contained. More...  
Public Types  
using  const_iterator = IntervalTreeIterator< node_type, true > 
using  data_type = DataType 
using  interval_kind = IntervalKind 
using  interval_type = Interval< DataType, NumericalType, IntervalKind > 
using  iterator = IntervalTreeIterator< node_type, false > 
using  node_type = IntervalTreeNode< DataType, NumericalType, IntervalKind > 
using  numerical_type = NumericalType 
using  self_type = tree_type 
using  tree_type = IntervalTree< DataType, NumericalType, IntervalKind > 
Public Attributes  
friend  IntervalTreeIterator< node_type, false > 
friend  IntervalTreeIterator< node_type, true > 

inline 
Definition at line 106 of file interval_tree.hpp.

inline 
Definition at line 111 of file interval_tree.hpp.

inline 
Definition at line 116 of file interval_tree.hpp.

default 

inline 
Definition at line 229 of file interval_tree.hpp.

inline 
Definition at line 249 of file interval_tree.hpp.

inline 
Definition at line 239 of file interval_tree.hpp.

inline 
Definition at line 244 of file interval_tree.hpp.

inline 
Remove all nodes from this tree.
Definition at line 617 of file interval_tree.hpp.

inlinenoexcept 
Return wether or not the tree is empty.
Definition at line 156 of file interval_tree.hpp.

inline 
Definition at line 234 of file interval_tree.hpp.

inline 
Definition at line 254 of file interval_tree.hpp.
Erase the element pointed to be iter.
Definition at line 746 of file interval_tree.hpp.

inline 
Find the first exact match.
ival  The interval to find an exact match for within the tree. 
Definition at line 298 of file interval_tree.hpp.

inline 
Find the first exact match.
ival  The interval to find an exact match for within the tree. 
Definition at line 313 of file interval_tree.hpp.

inline 
Find the first exact match.
ival  The interval to find an exact match for within the tree. 
compare  A comparison function to use. 
Definition at line 270 of file interval_tree.hpp.

inline 
Find the first exact match.
ival  The interval to find an exact match for within the tree. 
compare  A comparison function to use. 
Definition at line 285 of file interval_tree.hpp.

inline 
Find all exact matches and execute a function for each of them.
Definition at line 361 of file interval_tree.hpp.

inline 
Find all exact matches and execute a function for each of them.
Definition at line 376 of file interval_tree.hpp.

inline 
Find all exact matches and execute a function for each of them.
Definition at line 331 of file interval_tree.hpp.

inline 
Find all exact matches and execute a function for each of them.
Definition at line 346 of file interval_tree.hpp.

inline 
Find the next exact match EXCLUDING from.
from  The iterator to search from, EXCLUSIVE! 
ival  The interval to find an exact match for within the tree. 
Definition at line 428 of file interval_tree.hpp.

inline 
Definition at line 439 of file interval_tree.hpp.

inline 
Find the next exact match EXCLUDING from.
from  The iterator to search from EXCLUSIVE! 
ival  The interval to find an exact match for within the tree. 
compare  A comparison function to use. 
Definition at line 399 of file interval_tree.hpp.

inline 
Definition at line 411 of file interval_tree.hpp.

inline 
Flatten the tree.
Merges all overlapping intervals by erasing overlapping intervals and reinserting the merged interval. All resulting interval data is default constructed, and all data in the current intervals is lost.
Definition at line 812 of file interval_tree.hpp.

inline 
Flatten the tree, but returns it as a copy.
Definition at line 821 of file interval_tree.hpp.

inline 
Return the highest high value of the contained Intervals.
This is the rightmost position of all intervals.
Definition at line 195 of file interval_tree.hpp.

inline 
Insert an Interval into the tree.
Copies the interval.
Definition at line 639 of file interval_tree.hpp.

inline 
Insert an Interval into the tree.
Moves the interval.
Definition at line 679 of file interval_tree.hpp.

inline 
Insert an interval into the tree if no other interval overlaps it. Otherwise merge the interval with the being overlapped.
ival  The interval 
exclusive  Exclude borders. 
Definition at line 691 of file interval_tree.hpp.

inline 
Insert an interval into the tree if no other interval overlaps it. Otherwise merge the interval with the being overlapped, and use data
for this interval.
ival  The interval 
data  The data to be used if a new interval is created. 
exclusive  Exclude borders. 
Definition at line 717 of file interval_tree.hpp.

inline 
Insert an interval into the tree if no other interval overlaps it. Otherwise merge the interval with the being overlapped, and use data
for this interval.
ival  The interval 
data  The data to be used if a new interval is created. 
exclusive  Exclude borders. 
Definition at line 704 of file interval_tree.hpp.

inline 
Return the lowest low value of the contained Intervals.
This is the leftmost position of all intervals.
Definition at line 182 of file interval_tree.hpp.

default 

inline 
Definition at line 125 of file interval_tree.hpp.

inline 
Find the first interval that overlaps with ival.
ival  The interval to find an overlap for within the tree. 
exclusive  Exclude edges? 
Definition at line 460 of file interval_tree.hpp.

inline 
Definition at line 472 of file interval_tree.hpp.

inline 
Find the first interval that overlaps with the given position.
Definition at line 487 of file interval_tree.hpp.

inline 
Find the first interval that overlaps with the given position.
Definition at line 496 of file interval_tree.hpp.

inline 
Find all intervals that overlap with a given interval.
ival  The interval to find an overlap for within the tree. 
on_find  Functional to run for each found interval. 
exclusive  Exclude edges? 
Definition at line 514 of file interval_tree.hpp.

inline 
Definition at line 534 of file interval_tree.hpp.

inline 
Find all intervals that overlap with a given position.
Definition at line 557 of file interval_tree.hpp.

inline 
Find all intervals that overlap with a given position.
Definition at line 569 of file interval_tree.hpp.

inline 
Definition at line 599 of file interval_tree.hpp.

inline 
Find the next interval that overlaps with ival.
from  The iterator to start from, EXCLUSIVE! 
ival  The interval to find an overlap for within the tree. 
exclusive  Exclude edges? 
Definition at line 588 of file interval_tree.hpp.

inline 
Create an interval tree that contains all gaps between the intervals as intervals.
Only works with flattened trees, that is, trees without overlapping intervals. This is equivalent to the other punch overload with ival = [tree_lowest, tree_highest]
Definition at line 836 of file interval_tree.hpp.

inline 
Create an interval tree that contains all gaps between the intervals as intervals.
Only works with flattened trees, that is, trees without overlapping intervals. Removes all intervals from the given interval and produces a tree that contains the remaining intervals.
Definition at line 853 of file interval_tree.hpp.

inline 
Return the root node from this tree.
Definition at line 164 of file interval_tree.hpp.

inline 
Return the root node from this tree.
Definition at line 172 of file interval_tree.hpp.

inline 
Return the size of the object, that is, the number of Intervals contained.
Definition at line 148 of file interval_tree.hpp.
using const_iterator = IntervalTreeIterator<node_type, true> 
Definition at line 97 of file interval_tree.hpp.
using data_type = DataType 
Definition at line 86 of file interval_tree.hpp.
using interval_kind = IntervalKind 
Definition at line 88 of file interval_tree.hpp.
using interval_type = Interval<DataType, NumericalType, IntervalKind> 
Definition at line 90 of file interval_tree.hpp.
using iterator = IntervalTreeIterator<node_type, false> 
Definition at line 96 of file interval_tree.hpp.
using node_type = IntervalTreeNode<DataType, NumericalType, IntervalKind> 
Definition at line 91 of file interval_tree.hpp.
using numerical_type = NumericalType 
Definition at line 87 of file interval_tree.hpp.
Definition at line 94 of file interval_tree.hpp.
using tree_type = IntervalTree<DataType, NumericalType, IntervalKind> 
Definition at line 92 of file interval_tree.hpp.
friend IntervalTreeIterator< node_type, false > 
Definition at line 99 of file interval_tree.hpp.
friend IntervalTreeIterator< node_type, true > 
Definition at line 100 of file interval_tree.hpp.