#include <genesis/utils/containers/interval_tree/fwd.hpp>

Detailed Description

template<typename DataType = EmptyIntervalData, typename NumericalType = DefaultIntervalNumericalType, typename IntervalKind = IntervalClosed>
class genesis::utils::IntervalTree< DataType, NumericalType, IntervalKind >

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 interval-tree, which is published under the CC0-1.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.

Definition at line 45 of file fwd.hpp.

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 >

Constructor & Destructor Documentation

◆ IntervalTree() [1/3]

IntervalTree ( )

inline

Definition at line 106 of file interval_tree.hpp.

◆ ~IntervalTree()

~IntervalTree ( )

inline

Definition at line 111 of file interval_tree.hpp.

◆ IntervalTree() [2/3]

IntervalTree ( IntervalTree< DataType, NumericalType, IntervalKind > const & other )

inline

Definition at line 116 of file interval_tree.hpp.

◆ IntervalTree() [3/3]

IntervalTree ( IntervalTree< DataType, NumericalType, IntervalKind > && )

default

Member Function Documentation

◆ begin() [1/2]

iterator begin ( )

inline

Definition at line 229 of file interval_tree.hpp.

◆ begin() [2/2]

const_iterator begin ( ) const

inline

Definition at line 249 of file interval_tree.hpp.

◆ cbegin()

const_iterator cbegin ( ) const

inline

Definition at line 239 of file interval_tree.hpp.

◆ cend()

const_iterator cend ( ) const

inline

Definition at line 244 of file interval_tree.hpp.

◆ clear()

void clear ( )

inline

Remove all nodes from this tree.

Definition at line 617 of file interval_tree.hpp.

◆ empty()

bool empty ( ) const

inlinenoexcept

Return wether or not the tree is empty.

Definition at line 156 of file interval_tree.hpp.

◆ end() [1/2]

iterator end ( )

inline

Definition at line 234 of file interval_tree.hpp.

◆ end() [2/2]

const_iterator end ( ) const

inline

Definition at line 254 of file interval_tree.hpp.

◆ erase()

iterator erase ( iterator iter )

inline

Erase the element pointed to be iter.

Definition at line 746 of file interval_tree.hpp.

◆ find() [1/4]

iterator find ( interval_type const & ival )

inline

Find the first exact match.

Parameters

ival	The interval to find an exact match for within the tree.

Definition at line 298 of file interval_tree.hpp.

◆ find() [2/4]

const_iterator find ( interval_type const & ival ) const

inline

Find the first exact match.

Parameters

ival	The interval to find an exact match for within the tree.

Definition at line 313 of file interval_tree.hpp.

◆ find() [3/4]

iterator find	(	interval_type const &	ival,
		CompareFunctionT const &	compare
	)

inline

Find the first exact match.

Parameters

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.

◆ find() [4/4]

const_iterator find	(	interval_type const &	ival,
		CompareFunctionT const &	compare
	)		const

inline

Find the first exact match.

Parameters

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.

◆ find_all() [1/4]

void find_all	(	interval_type const &	ival,
		FunctionT const &	on_find
	)

inline

Find all exact matches and execute a function for each of them.

Definition at line 361 of file interval_tree.hpp.

◆ find_all() [2/4]

void find_all	(	interval_type const &	ival,
		FunctionT const &	on_find
	)		const

inline

Find all exact matches and execute a function for each of them.

Definition at line 376 of file interval_tree.hpp.

◆ find_all() [3/4]

void find_all	(	interval_type const &	ival,
		FunctionT const &	on_find,
		CompareFunctionT const &	compare
	)

inline

Find all exact matches and execute a function for each of them.

Definition at line 331 of file interval_tree.hpp.

◆ find_all() [4/4]

void find_all	(	interval_type const &	ival,
		FunctionT const &	on_find,
		CompareFunctionT const &	compare
	)		const

inline

Find all exact matches and execute a function for each of them.

Definition at line 346 of file interval_tree.hpp.

◆ find_next_in_subtree() [1/4]

iterator find_next_in_subtree	(	iterator	from,
		interval_type const &	ival
	)

inline

Find the next exact match EXCLUDING from.

Parameters

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.

◆ find_next_in_subtree() [2/4]

const_iterator find_next_in_subtree	(	iterator	from,
		interval_type const &	ival
	)		const

inline

Definition at line 439 of file interval_tree.hpp.

◆ find_next_in_subtree() [3/4]

iterator find_next_in_subtree	(	iterator	from,
		interval_type const &	ival,
		CompareFunctionT const &	compare
	)

inline

Find the next exact match EXCLUDING from.

Parameters

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.

◆ find_next_in_subtree() [4/4]

const_iterator find_next_in_subtree	(	iterator	from,
		interval_type const &	ival,
		CompareFunctionT const &	compare
	)		const

inline

Definition at line 411 of file interval_tree.hpp.

◆ flatten()

IntervalTree& flatten ( )

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.

◆ flatten_copy()

IntervalTree flatten_copy ( )

inline

Flatten the tree, but returns it as a copy.

Definition at line 821 of file interval_tree.hpp.

◆ highest()

numerical_type highest ( ) const

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.

◆ insert() [1/2]

iterator insert ( interval_type && ival )

inline

Insert an Interval into the tree.

Copies the interval.

Definition at line 639 of file interval_tree.hpp.

◆ insert() [2/2]

iterator insert ( interval_type const & ival )

inline

Insert an Interval into the tree.

Moves the interval.

Definition at line 679 of file interval_tree.hpp.

◆ insert_overlap() [1/3]

iterator insert_overlap	(	interval_type const &	ival,
		bool	exclusive = `false`
	)

inline

Insert an interval into the tree if no other interval overlaps it. Otherwise merge the interval with the being overlapped.

Parameters

ival	The interval
exclusive	Exclude borders.

Definition at line 691 of file interval_tree.hpp.

◆ insert_overlap() [2/3]

iterator insert_overlap	(	interval_type const &	ival,
		data_type &&	data,
		bool	exclusive = `false`
	)

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.

Parameters

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.

◆ insert_overlap() [3/3]

iterator insert_overlap	(	interval_type const &	ival,
		data_type const &	data,
		bool	exclusive = `false`
	)

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.

Parameters

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.

◆ lowest()

numerical_type lowest ( ) const

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.

◆ operator=() [1/2]

IntervalTree& operator= ( IntervalTree< DataType, NumericalType, IntervalKind > && )

default

◆ operator=() [2/2]

IntervalTree& operator= ( IntervalTree< DataType, NumericalType, IntervalKind > const & other )

inline

Definition at line 125 of file interval_tree.hpp.

◆ overlap_find() [1/4]

iterator overlap_find	(	interval_type const &	ival,
		bool	exclusive = `false`
	)

inline

Find the first interval that overlaps with ival.

Parameters

ival	The interval to find an overlap for within the tree.
exclusive	Exclude edges?

Definition at line 460 of file interval_tree.hpp.

◆ overlap_find() [2/4]

const_iterator overlap_find	(	interval_type const &	ival,
		bool	exclusive = `false`
	)		const

inline

Definition at line 472 of file interval_tree.hpp.

◆ overlap_find() [3/4]

iterator overlap_find ( numerical_type position )

inline

Find the first interval that overlaps with the given position.

Definition at line 487 of file interval_tree.hpp.

◆ overlap_find() [4/4]

const_iterator overlap_find ( numerical_type position ) const

inline

Find the first interval that overlaps with the given position.

Definition at line 496 of file interval_tree.hpp.

◆ overlap_find_all() [1/4]

void overlap_find_all	(	interval_type const &	ival,
		FunctionT const &	on_find,
		bool	exclusive = `false`
	)

inline

Find all intervals that overlap with a given interval.

Parameters

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.

◆ overlap_find_all() [2/4]

void overlap_find_all	(	interval_type const &	ival,
		FunctionT const &	on_find,
		bool	exclusive = `false`
	)		const

inline

Definition at line 534 of file interval_tree.hpp.

◆ overlap_find_all() [3/4]

void overlap_find_all	(	numerical_type	position,
		FunctionT const &	on_find
	)

inline

Find all intervals that overlap with a given position.

Definition at line 557 of file interval_tree.hpp.

◆ overlap_find_all() [4/4]

void overlap_find_all	(	numerical_type	position,
		FunctionT const &	on_find
	)		const

inline

Find all intervals that overlap with a given position.

Definition at line 569 of file interval_tree.hpp.

◆ overlap_find_next_in_subtree() [1/2]

const_iterator overlap_find_next_in_subtree	(	const_iterator	from,
		interval_type const &	ival,
		bool	exclusive = `false`
	)		const

inline

Definition at line 599 of file interval_tree.hpp.

◆ overlap_find_next_in_subtree() [2/2]

iterator overlap_find_next_in_subtree	(	iterator	from,
		interval_type const &	ival,
		bool	exclusive = `false`
	)

inline

Find the next interval that overlaps with ival.

Parameters

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.

◆ punch() [1/2]

IntervalTree punch ( ) const

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.

◆ punch() [2/2]

IntervalTree punch ( interval_type const & ival ) const

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.

◆ root() [1/2]

iterator root ( )

inline

Return the root node from this tree.

Definition at line 164 of file interval_tree.hpp.

◆ root() [2/2]

const_iterator root ( ) const

inline

Return the root node from this tree.

Definition at line 172 of file interval_tree.hpp.

◆ size()

size_t size ( ) const

inline

Return the size of the object, that is, the number of Intervals contained.

Definition at line 148 of file interval_tree.hpp.

Member Typedef Documentation

◆ const_iterator

using const_iterator = IntervalTreeIterator<node_type, true>

Definition at line 97 of file interval_tree.hpp.

◆ data_type

using data_type = DataType

Definition at line 86 of file interval_tree.hpp.

◆ interval_kind

using interval_kind = IntervalKind

Definition at line 88 of file interval_tree.hpp.

◆ interval_type

using interval_type = Interval<DataType, NumericalType, IntervalKind>

Definition at line 90 of file interval_tree.hpp.

◆ iterator

using iterator = IntervalTreeIterator<node_type, false>

Definition at line 96 of file interval_tree.hpp.

◆ node_type

using node_type = IntervalTreeNode<DataType, NumericalType, IntervalKind>

Definition at line 91 of file interval_tree.hpp.

◆ numerical_type

using numerical_type = NumericalType

Definition at line 87 of file interval_tree.hpp.

◆ self_type

using self_type = tree_type

Definition at line 94 of file interval_tree.hpp.

◆ tree_type

using tree_type = IntervalTree<DataType, NumericalType, IntervalKind>

Definition at line 92 of file interval_tree.hpp.

Member Data Documentation

◆ IntervalTreeIterator< node_type, false >

friend IntervalTreeIterator< node_type, false >

Definition at line 99 of file interval_tree.hpp.

◆ IntervalTreeIterator< node_type, true >

friend IntervalTreeIterator< node_type, true >

Definition at line 100 of file interval_tree.hpp.

The documentation for this class was generated from the following files:

Detailed Description

template<typename DataType = EmptyIntervalData, typename NumericalType = DefaultIntervalNumericalType, typename IntervalKind = IntervalClosed> class genesis::utils::IntervalTree< DataType, NumericalType, IntervalKind >

Public Member Functions

Public Types

Public Attributes

Constructor & Destructor Documentation

◆ IntervalTree() [1/3]

◆ ~IntervalTree()

◆ IntervalTree() [2/3]

◆ IntervalTree() [3/3]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ clear()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase()

◆ find() [1/4]

◆ find() [2/4]

◆ find() [3/4]

◆ find() [4/4]

◆ find_all() [1/4]

◆ find_all() [2/4]

◆ find_all() [3/4]

◆ find_all() [4/4]

◆ find_next_in_subtree() [1/4]

◆ find_next_in_subtree() [2/4]

◆ find_next_in_subtree() [3/4]

◆ find_next_in_subtree() [4/4]

◆ flatten()

◆ flatten_copy()

◆ highest()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_overlap() [1/3]

◆ insert_overlap() [2/3]

◆ insert_overlap() [3/3]

◆ lowest()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ overlap_find() [1/4]

◆ overlap_find() [2/4]

◆ overlap_find() [3/4]

◆ overlap_find() [4/4]

◆ overlap_find_all() [1/4]

◆ overlap_find_all() [2/4]

◆ overlap_find_all() [3/4]

◆ overlap_find_all() [4/4]

◆ overlap_find_next_in_subtree() [1/2]

◆ overlap_find_next_in_subtree() [2/2]

◆ punch() [1/2]

◆ punch() [2/2]

◆ root() [1/2]

◆ root() [2/2]

◆ size()

Member Typedef Documentation

◆ const_iterator

◆ data_type

◆ interval_kind

◆ interval_type

◆ iterator

◆ node_type

◆ numerical_type

◆ self_type

◆ tree_type

Member Data Documentation

◆ IntervalTreeIterator< node_type, false >

◆ IntervalTreeIterator< node_type, true >

template<typename DataType = EmptyIntervalData, typename NumericalType = DefaultIntervalNumericalType, typename IntervalKind = IntervalClosed>
class genesis::utils::IntervalTree< DataType, NumericalType, IntervalKind >