High-level interval tree with automatic memory management. More...

#include <tpl_interval_tree.H>

Inheritance diagram for Aleph::DynIntervalTree< T, Compare >:

Collaboration diagram for Aleph::DynIntervalTree< T, Compare >:

Classes
class	Iterator
	Inorder iterator yielding Interval<T> keys. More...

Public Types
using	Key = Interval< T >

using	Item_Type = Key

using	Key_Type = Key

using	Node = typename Interval_Tree< T, Compare >::Node

using	Tree = Interval_Tree< T, Compare >

Public Types inherited from StlAlephIterator< SetName >
using	iterator = StlIterator< SetName >

using	const_iterator = StlConstIterator< SetName >

Public Member Functions
	DynIntervalTree (const Compare &cmp=Compare())
	Default constructor.

	DynIntervalTree (const unsigned long seed, const Compare &cmp=Compare())
	Construct with explicit seed for the internal RNG.

	DynIntervalTree (const DynIntervalTree &src)
	Copy constructor.

	DynIntervalTree (DynIntervalTree &&src)
	Move constructor.

DynIntervalTree &	operator= (const DynIntervalTree &src)
	Copy assignment.

DynIntervalTree &	operator= (DynIntervalTree &&src) noexcept(noexcept(std::declval< Tree & >().swap(std::declval< Tree & >())))
	Move assignment.

	~DynIntervalTree ()
	Destructor.

void	swap (DynIntervalTree &other) noexcept(noexcept(std::declval< Tree & >().swap(std::declval< Tree & >())))
	Swap state with another tree in O(1).

template<template< typename > class List>
	DynIntervalTree (const List< Key > &l)

template<class It >
	DynIntervalTree (It b, It e)

	DynIntervalTree (std::initializer_list< Key > l)

Key &	insert (const Key &iv)
	Insert an interval (unique).

Key &	insert (Key &&iv)
	Insert an interval (move version, unique).

Key &	insert (const T &lo, const T &hi)
	Insert an interval given endpoints (unique).

Key &	insert_dup (const Key &iv)
	Insert interval, allowing duplicates.

Key &	append (const Key &iv)
	Append an interval (alias for insert_dup).

bool	remove (const Key &iv)
	Remove an interval from the tree.

bool	remove (const T &lo, const T &hi)
	Remove an interval given endpoints.

const Key *	search (const Key &iv) const noexcept
	Search for an exact interval.

const Key *	overlap_search (const Key &query) const
	Find any interval overlapping `query`.

const Key *	overlap_search (const T &lo, const T &hi) const
	Overload of overlap_search() using endpoints.

template<class Op >
void	all_overlaps (const Key &query, Op &&op) const
	Apply op to every overlapping interval.

DynList< Key >	find_all_overlaps (const Key &query) const
	Find all overlapping intervals.

DynList< Key >	find_all_overlaps (const T &lo, const T &hi) const
	Overload of find_all_overlaps() using endpoints.

template<class Op >
void	stab (const T &p, Op &&op) const
	Apply op to every interval containing point p.

DynList< Key >	find_stab (const T &p) const
	Find all intervals containing point p.

size_t	size () const noexcept
	Return the number of intervals in the tree.

bool	is_empty () const noexcept
	Return true if the tree contains no intervals.

bool	empty () const noexcept
	Return true if the tree contains no intervals (STL compatible).

bool	verify () const
	Verify all tree invariants (BST, Treap, MaxEndpoint).

template<class Operation >
bool	traverse (Operation &op)
	Traverse all intervals in inorder (sorted by low endpoint).

template<class Operation >
bool	traverse (Operation &&op=Operation())
	Overload of traverse() for rvalue callbacks.

template<class Operation >
bool	traverse (Operation &op) const
	Const overload of traverse().

template<class Operation >
bool	traverse (Operation &&op=Operation()) const
	Const rvalue overload of traverse().

Public Member Functions inherited from EqualToMethod< Container >
bool	equal_to (const Container &r) const noexcept
	Test if elements of `this` are exactly contained in another container.

bool	operator== (const Container &r) const noexcept

bool	operator!= (const Container &r) const noexcept
	Negation of equal_to()

Public Member Functions inherited from FunctionalMethods< Container, T >
template<typename ... Args>
void	emplace (Args &&... args)
	Appends a new element into the container by constructing it in-place with the given args.

template<typename ... Args>
void	emplace_end (Args &&... args)

template<typename ... Args>
void	emplace_ins (Args &&... args)
	Insert a new element into the container by constructing it in-place with the given args.

template<typename ... Args>
size_t	ninsert (Args ... args)
	Insert n variadic items.

template<typename ... Args>
size_t	nappend (Args ... args)
	Append n variadic items.

template<class Operation >
void	for_each (Operation &operation)
	Traverse all the container and performs an operation on each element.

template<class Operation >
void	for_each (Operation &operation) const
	Const overload of `for_each(Operation&)`.

template<class Operation >
void	for_each (Operation &&operation) const
	Overload of for_each() const that accepts rvalues.

template<class Operation >
void	for_each (Operation &&operation)
	Overload of for_each() that accepts rvalues.

template<class Operation >
void	each (Operation &operation)
	Alias of `for_each(Operation&)`.

template<class Operation >
void	each (Operation &operation) const
	Const alias of `for_each(Operation&)`.

template<class Operation >
void	each (Operation &&operation) const
	Const alias of each() that accepts rvalues.

template<class Operation >
void	each (Operation &&operation)
	Alias of each() that accepts rvalues.

template<class Operation >
void	each (size_t pos, const size_t slice, Operation &operation) const
	Traverse the container starting at `pos` taking one item every `slice`, performing a mutable operation on each visited element.

template<class Operation >
void	each (const size_t pos, const size_t slice, Operation &&operation) const

template<class Operation >
void	mutable_for_each (Operation &operation)
	Apply a mutable operation to each element of the container.

template<class Operation >
void	mutable_for_each (Operation &&operation)

template<class Operation >
bool	all (Operation &operation) const
	Check if all the elements of the container satisfy a condition.

template<class Operation >
bool	all (Operation &&operation) const
	Overload of all() that accepts rvalues.

template<class Operation >
bool	exists (Operation &op) const
	Test for existence in the container of an element satisfying a criterion.

template<class Operation >
bool	exists (Operation &&op) const
	Overload of exists() that accepts rvalues.

template<typename __T = T, class Operation = Aleph::Dft_Map_Op<T, __T>>
Aleph::DynList< __T >	maps (Operation &op) const
	Map the elements of the container.

template<typename __T = T, class Operation = Aleph::Dft_Map_Op<__T, __T>>
Aleph::DynList< __T >	maps (Operation &&op) const
	Overload of maps() that accepts rvalues.

template<typename __T = T, class Prop , class Operation >
Aleph::DynList< __T >	maps_if (Prop prop, Operation &op) const
	Conditional mapping of the elements of the container.

template<typename __T = T, class Prop , class Operation >
Aleph::DynList< __T >	maps_if (Prop prop, Operation &&op) const
	Overload of maps_if() that accepts rvalues.

Aleph::DynList< T >	to_dynlist () const
	Convert container to DynList.

std::vector< T >	to_vector () const
	Convert container to std::vector.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	foldl (const __T &init, Op &op) const
	Fold the elements of the container to a specific result.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	foldl (const __T &init, Op &&op=Op()) const
	Overload of foldl() that accepts rvalues.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	fold_left (const __T &init, Op &op) const
	Alias for foldl with the same accumulator type.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	fold_left (const __T &init, Op &&op=Op()) const
	Overload of fold_left() that accepts rvalues.

template<class Operation >
T	fold (const T &init, Operation &operation) const
	Simplified version of foldl() where the folded type is the same type of elements stored in the container.

template<class Operation >
T	fold (const T &init, Operation &&operation) const
	Overload of fold() that accepts rvalues.

template<class Operation >
Aleph::DynList< T >	filter (Operation &operation) const
	Filter the elements of a container according to a matching criterion.

template<class Operation >
Aleph::DynList< T >	filter (Operation &&operation) const
	Overload of filter() that accepts rvalues.

template<class Operation >
Aleph::DynList< const T * >	ptr_filter (Operation &operation) const
	Filter the elements of a container according to a matching criterion and return a pointer to the matched items in the container.

template<class Operation >
Aleph::DynList< const T * >	ptr_filter (Operation &&operation) const
	Overload of ptr_filter() that accepts rvalues.

template<class Operation >
Aleph::DynList< std::tuple< T, size_t > >	pfilter (Operation &operation) const
	Filter the elements of a container according to a matching criterion and determine its positions respect to the traversal of container.

template<class Operation >
Aleph::DynList< std::tuple< T, size_t > >	pfilter (Operation &&operation) const
	Overload of pfilter() that accepts rvalues.

template<class Operation >
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &op) const
	Exclusive partition of container according to a filter criterion.

template<class Operation >
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &&op) const
	Overload of partition() that accepts rvalues.

std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (size_t n) const
	Exclusive partition of container in the nth item.

std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	split_half () const
	Split the container into two halves by alternating elements.

template<class Operation >
std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &op) const
	Exclusive partition of container according to a filter criterion.

template<class Operation >
std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &&op) const
	Overload of tpartition() that accepts rvalues.

size_t	length () const noexcept
	Count the number of elements of a container.

Aleph::DynList< T >	rev () const
	Return a list with the elements of container in reverse order respect to its traversal order.

Aleph::DynList< T >	take (const size_t n) const
	Return a list with the first n elements seen in the container during its traversal.

Aleph::DynList< T >	take (size_t i, const size_t j, const size_t step=1) const
	Return a list with elements seen in the container between i and j position respect to its traversal.

Aleph::DynList< T >	drop (const size_t n) const
	Drop the first n elements seen in the container during its traversal.

void	mutable_drop (const size_t n)
	Drop the first n elements seen from container.

Public Member Functions inherited from GenericItems< Container, T >
Aleph::DynList< T >	items () const
	Return a list of all the elements of a container sorted by traversal order.

Aleph::DynList< T >	keys () const

Public Member Functions inherited from StlAlephIterator< SetName >
iterator	begin () noexcept
	Return an STL-compatible iterator to the first element.

iterator	end () noexcept
	Return an STL-compatible end iterator.

const_iterator	begin () const noexcept
	Return a const iterator to the first element.

const_iterator	end () const noexcept
	Return a const end iterator.

const_iterator	cbegin () const noexcept
	Return a const iterator to the first element.

const_iterator	cend () const noexcept
	Return a const end iterator.

Private Member Functions
void	copy_from (const DynIntervalTree &src)

void	destroy_tree ()

Private Attributes
Tree	tree

Additional Inherited Members
Related Symbols inherited from FunctionalMethods< Container, T >
	each

	each

	each

Detailed Description

template<typename T, class Compare = Aleph::less<T>>
requires StrictWeakOrder<Compare, T>
class Aleph::DynIntervalTree< T, Compare >

High-level interval tree with automatic memory management.

DynIntervalTree<T> wraps Interval_Tree<T> and provides:

Automatic new/delete for nodes
CRTP mixins for functional methods
Validation on insert (low <= high)
Copy/move semantics

Template Parameters

T	Endpoint type.
Compare	Comparison functor for endpoints.

Example:: DynIntervalTree<int> tree;

tree.insert(Interval<int>(1, 5));

tree.insert(3, 10);

// Find any overlap with [4, 7]

auto result = tree.overlap_search({4, 7});

// Find all intervals containing point 6

auto hits = tree.find_stab(6);

Aleph::DynIntervalTree
High-level interval tree with automatic memory management.
Definition tpl_interval_tree.H:1035

Aleph::DynIntervalTree::tree
Tree tree
Definition tpl_interval_tree.H:1044

Aleph::Gen_Interval_Tree::insert
Node * insert(Node *root, Node *p)
Definition tpl_interval_tree.H:573

Aleph::Gen_Interval_Tree::overlap_search
const Node * overlap_search(const Key &query) const
Find any interval that overlaps with query (CLRS algorithm).
Definition tpl_interval_tree.H:878

Aleph::Gen_Interval_Tree::find_stab
DynList< Key > find_stab(const T &p) const
Find all intervals containing point p.
Definition tpl_interval_tree.H:940

Aleph::Interval
Closed interval [low, high].
Definition tpl_interval_tree.H:91

Definition at line 1030 of file tpl_interval_tree.H.

Member Typedef Documentation

◆ Item_Type

template<typename T , class Compare = Aleph::less<T>>

using Aleph::DynIntervalTree< T, Compare >::Item_Type = Key

Definition at line 1038 of file tpl_interval_tree.H.

◆ Key

template<typename T , class Compare = Aleph::less<T>>

using Aleph::DynIntervalTree< T, Compare >::Key = Interval<T>

Definition at line 1037 of file tpl_interval_tree.H.

◆ Key_Type

template<typename T , class Compare = Aleph::less<T>>

using Aleph::DynIntervalTree< T, Compare >::Key_Type = Key

Definition at line 1039 of file tpl_interval_tree.H.

◆ Node

template<typename T , class Compare = Aleph::less<T>>

using Aleph::DynIntervalTree< T, Compare >::Node = typename Interval_Tree<T, Compare>::Node

Definition at line 1040 of file tpl_interval_tree.H.

◆ Tree

template<typename T , class Compare = Aleph::less<T>>

using Aleph::DynIntervalTree< T, Compare >::Tree = Interval_Tree<T, Compare>

Definition at line 1041 of file tpl_interval_tree.H.

Constructor & Destructor Documentation

◆ DynIntervalTree() [1/7]

template<typename T , class Compare = Aleph::less<T>>

Aleph::DynIntervalTree< T, Compare >::DynIntervalTree ( const Compare & cmp = Compare() )

inline

Default constructor.

Parameters

[in] cmp Comparison functor for endpoints.

Definition at line 1061 of file tpl_interval_tree.H.

◆ DynIntervalTree() [2/7]

template<typename T , class Compare = Aleph::less<T>>

Aleph::DynIntervalTree< T, Compare >::DynIntervalTree	(	const unsigned long	seed,
		const Compare &	cmp = `Compare()`
	)

inline

Construct with explicit seed for the internal RNG.

Parameters

[in]	seed	Random seed.
[in]	cmp	Comparison functor for endpoints.

Definition at line 1067 of file tpl_interval_tree.H.

◆ DynIntervalTree() [3/7]

template<typename T , class Compare = Aleph::less<T>>

Aleph::DynIntervalTree< T, Compare >::DynIntervalTree ( const DynIntervalTree< T, Compare > & src )

inline

Copy constructor.

Parameters

[in] src Source tree to copy from.

Definition at line 1074 of file tpl_interval_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::endpoint_comp(), Aleph::DynIntervalTree< T, Compare >::swap(), and Aleph::DynIntervalTree< T, Compare >::tree.

◆ DynIntervalTree() [4/7]

template<typename T , class Compare = Aleph::less<T>>

Aleph::DynIntervalTree< T, Compare >::DynIntervalTree ( DynIntervalTree< T, Compare > && src )

inline

Move constructor.

Not declared noexcept because the initializer tree(src.tree.endpoint_comp()) constructs a new Tree, which allocates a GSL RNG via gsl_rng_alloc and copies the comparator — both can throw.

Parameters

[in,out] src Source tree to move from.

Definition at line 1091 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::swap(), and Aleph::DynIntervalTree< T, Compare >::tree.

◆ ~DynIntervalTree()

template<typename T , class Compare = Aleph::less<T>>

Aleph::DynIntervalTree< T, Compare >::~DynIntervalTree ( )

inline

Destructor.

Definition at line 1125 of file tpl_interval_tree.H.

References Aleph::DynIntervalTree< T, Compare >::destroy_tree().

◆ DynIntervalTree() [5/7]

template<typename T , class Compare = Aleph::less<T>>

template<template< typename > class List>

Aleph::DynIntervalTree< T, Compare >::DynIntervalTree ( const List< Key > & l )

inline

Definition at line 1136 of file tpl_interval_tree.H.

◆ DynIntervalTree() [6/7]

template<typename T , class Compare = Aleph::less<T>>

template<class It >

Aleph::DynIntervalTree< T, Compare >::DynIntervalTree	(	It	b,
		It	e
	)

inline

Definition at line 1136 of file tpl_interval_tree.H.

◆ DynIntervalTree() [7/7]

template<typename T , class Compare = Aleph::less<T>>

Aleph::DynIntervalTree< T, Compare >::DynIntervalTree ( std::initializer_list< Key > l )

inline

Definition at line 1136 of file tpl_interval_tree.H.

Member Function Documentation

◆ all_overlaps()

template<typename T , class Compare = Aleph::less<T>>

template<class Op >

void Aleph::DynIntervalTree< T, Compare >::all_overlaps	(	const Key &	query,
		Op &&	op
	)		const

inline

Apply op to every overlapping interval.

Template Parameters

Op	Callable with signature `void(const Key&)`.

Parameters

[in]	query	the query interval.
[in]	op	callable to invoke for each overlap.

Exceptions

Any	exception thrown by `op`.

Definition at line 1279 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::all_overlaps(), and Aleph::DynIntervalTree< T, Compare >::tree.

◆ append()

template<typename T , class Compare = Aleph::less<T>>

Key & Aleph::DynIntervalTree< T, Compare >::append ( const Key & iv )

inline

Append an interval (alias for insert_dup).

Parameters

[in] iv the interval to append.

Returns: reference to the stored key.

Exceptions

std::domain_error if iv.low > iv.high.

Definition at line 1210 of file tpl_interval_tree.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::DynIntervalTree< T, Compare >::insert_dup().

Referenced by Aleph::DynIntervalTree< T, Compare >::copy_from().

◆ copy_from()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::DynIntervalTree< T, Compare >::copy_from ( const DynIntervalTree< T, Compare > & src )

inlineprivate

Definition at line 1046 of file tpl_interval_tree.H.

References Aleph::DynIntervalTree< T, Compare >::append(), Aleph::divide_and_conquer_partition_dp(), and FunctionalMethods< Container, T >::for_each().

◆ destroy_tree()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::DynIntervalTree< T, Compare >::destroy_tree ( )

inlineprivate

Definition at line 1051 of file tpl_interval_tree.H.

References Aleph::destroyRec(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::getRoot(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::reset_num_nodes(), and Aleph::DynIntervalTree< T, Compare >::tree.

Referenced by Aleph::DynIntervalTree< T, Compare >::~DynIntervalTree(), and Aleph::DynIntervalTree< T, Compare >::operator=().

◆ empty()

template<typename T , class Compare = Aleph::less<T>>

bool Aleph::DynIntervalTree< T, Compare >::empty ( ) const

inlinenoexcept

Return true if the tree contains no intervals (STL compatible).

Returns: true if empty.

Exceptions

none

Definition at line 1342 of file tpl_interval_tree.H.

References Aleph::DynIntervalTree< T, Compare >::is_empty().

◆ find_all_overlaps() [1/2]

template<typename T , class Compare = Aleph::less<T>>

DynList< Key > Aleph::DynIntervalTree< T, Compare >::find_all_overlaps ( const Key & query ) const

inline

Find all overlapping intervals.

Parameters

[in] query the query interval.

Returns: DynList containing all overlapping intervals.

Definition at line 1289 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::find_all_overlaps(), and Aleph::DynIntervalTree< T, Compare >::tree.

Referenced by Aleph::DynIntervalTree< T, Compare >::find_all_overlaps(), segment_intersection(), and TEST().

◆ find_all_overlaps() [2/2]

template<typename T , class Compare = Aleph::less<T>>

DynList< Key > Aleph::DynIntervalTree< T, Compare >::find_all_overlaps	(	const T &	lo,
		const T &	hi
	)		const

inline

Overload of find_all_overlaps() using endpoints.

Parameters

[in]	lo	lower endpoint.
[in]	hi	upper endpoint.

Returns: DynList of overlapping intervals.

Definition at line 1299 of file tpl_interval_tree.H.

References Aleph::DynIntervalTree< T, Compare >::find_all_overlaps().

◆ find_stab()

template<typename T , class Compare = Aleph::less<T>>

DynList< Key > Aleph::DynIntervalTree< T, Compare >::find_stab ( const T & p ) const

inline

Find all intervals containing point p.

Parameters

[in] p query point.

Returns: DynList of intervals containing p.

Definition at line 1321 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::find_stab(), and Aleph::DynIntervalTree< T, Compare >::tree.

◆ insert() [1/3]

template<typename T , class Compare = Aleph::less<T>>

Key & Aleph::DynIntervalTree< T, Compare >::insert ( const Key & iv )

inline

Insert an interval (unique).

Parameters

[in] iv the interval to insert.

Returns: reference to the key stored in the tree.

Exceptions

std::domain_error if iv.low > iv.high (invalid interval) or if the interval already exists in the tree.

Definition at line 1145 of file tpl_interval_tree.H.

References ah_domain_error, ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::endpoint_comp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), KEY, and Aleph::DynIntervalTree< T, Compare >::tree.

Referenced by Aleph::DynIntervalTree< T, Compare >::insert(), meeting_scheduler(), TEST(), TEST(), TEST(), and TEST_F().

◆ insert() [2/3]

template<typename T , class Compare = Aleph::less<T>>

Key & Aleph::DynIntervalTree< T, Compare >::insert	(	const T &	lo,
		const T &	hi
	)

inline

Insert an interval given endpoints (unique).

Parameters

[in]	lo	lower endpoint.
[in]	hi	upper endpoint.

Returns: reference to the key stored in the tree.

Exceptions

std::domain_error if lo > hi or if the interval already exists.

Definition at line 1185 of file tpl_interval_tree.H.

References Aleph::DynIntervalTree< T, Compare >::insert().

◆ insert() [3/3]

template<typename T , class Compare = Aleph::less<T>>

Key & Aleph::DynIntervalTree< T, Compare >::insert ( Key && iv )

inline

Insert an interval (move version, unique).

Parameters

[in,out] iv the interval to insert.

Returns: reference to the key stored in the tree.

Exceptions

std::domain_error if iv.low > iv.high (invalid interval) or if the interval already exists in the tree.

Definition at line 1165 of file tpl_interval_tree.H.

References ah_domain_error, ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::endpoint_comp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), KEY, and Aleph::DynIntervalTree< T, Compare >::tree.

◆ insert_dup()

template<typename T , class Compare = Aleph::less<T>>

Key & Aleph::DynIntervalTree< T, Compare >::insert_dup ( const Key & iv )

inline

Insert interval, allowing duplicates.

Parameters

[in] iv the interval to insert.

Returns: reference to the stored key.

Exceptions

std::domain_error if iv.low > iv.high.

Definition at line 1196 of file tpl_interval_tree.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::endpoint_comp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup(), KEY, and Aleph::DynIntervalTree< T, Compare >::tree.

Referenced by Aleph::DynIntervalTree< T, Compare >::append(), segment_intersection(), TEST(), and TEST().

◆ is_empty()

template<typename T , class Compare = Aleph::less<T>>

bool Aleph::DynIntervalTree< T, Compare >::is_empty ( ) const

inlinenoexcept

Return true if the tree contains no intervals.

Returns: true if empty.

Exceptions

none

Definition at line 1336 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::is_empty(), and Aleph::DynIntervalTree< T, Compare >::tree.

Referenced by Aleph::DynIntervalTree< T, Compare >::empty().

◆ operator=() [1/2]

template<typename T , class Compare = Aleph::less<T>>

DynIntervalTree & Aleph::DynIntervalTree< T, Compare >::operator= ( const DynIntervalTree< T, Compare > & src )

inline

Copy assignment.

Parameters

[in] src Source tree to copy from.

Returns: Reference to this tree.

Definition at line 1101 of file tpl_interval_tree.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::DynIntervalTree< T, Compare >::swap().

◆ operator=() [2/2]

template<typename T , class Compare = Aleph::less<T>>

DynIntervalTree & Aleph::DynIntervalTree< T, Compare >::operator= ( DynIntervalTree< T, Compare > && src )

inlinenoexcept

Move assignment.

Parameters

[in,out] src Source tree to move from.

Returns: Reference to this tree.

Definition at line 1114 of file tpl_interval_tree.H.

References Aleph::DynIntervalTree< T, Compare >::destroy_tree(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::swap(), and Aleph::DynIntervalTree< T, Compare >::tree.

◆ overlap_search() [1/2]

template<typename T , class Compare = Aleph::less<T>>

const Key * Aleph::DynIntervalTree< T, Compare >::overlap_search ( const Key & query ) const

inline

Find any interval overlapping query.

Parameters

[in] query the query interval.

Returns: pointer to an overlapping interval, or nullptr if none.

Complexity: O(log n) expected.

Definition at line 1255 of file tpl_interval_tree.H.

References KEY, Aleph::Gen_Interval_Tree< NodeType, T, Compare >::overlap_search(), and Aleph::DynIntervalTree< T, Compare >::tree.

Referenced by Aleph::DynIntervalTree< T, Compare >::overlap_search(), TEST(), TEST(), and TEST().

◆ overlap_search() [2/2]

template<typename T , class Compare = Aleph::less<T>>

const Key * Aleph::DynIntervalTree< T, Compare >::overlap_search	(	const T &	lo,
		const T &	hi
	)		const

inline

Overload of overlap_search() using endpoints.

Parameters

[in]	lo	lower endpoint.
[in]	hi	upper endpoint.

Returns: pointer to an overlapping interval, or nullptr.

Definition at line 1266 of file tpl_interval_tree.H.

References Aleph::DynIntervalTree< T, Compare >::overlap_search().

◆ remove() [1/2]

template<typename T , class Compare = Aleph::less<T>>

bool Aleph::DynIntervalTree< T, Compare >::remove ( const Key & iv )

inline

Remove an interval from the tree.

Parameters

[in] iv the interval to remove.

Returns: true if removed, false if not found.

Definition at line 1217 of file tpl_interval_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::remove(), and Aleph::DynIntervalTree< T, Compare >::tree.

Referenced by Aleph::DynIntervalTree< T, Compare >::remove(), and TEST().

◆ remove() [2/2]

template<typename T , class Compare = Aleph::less<T>>

bool Aleph::DynIntervalTree< T, Compare >::remove	(	const T &	lo,
		const T &	hi
	)

inline

Remove an interval given endpoints.

Parameters

[in]	lo	lower endpoint.
[in]	hi	upper endpoint.

Returns: true if removed, false if not found.

Definition at line 1232 of file tpl_interval_tree.H.

References Aleph::DynIntervalTree< T, Compare >::remove().

◆ search()

template<typename T , class Compare = Aleph::less<T>>

const Key * Aleph::DynIntervalTree< T, Compare >::search ( const Key & iv ) const

inlinenoexcept

Search for an exact interval.

Parameters

[in] iv interval to search.

Returns: pointer to the stored interval if found, nullptr otherwise.

Exceptions

none

Definition at line 1243 of file tpl_interval_tree.H.

References Aleph::divide_and_conquer_partition_dp(), KEY, Aleph::Gen_Interval_Tree< NodeType, T, Compare >::search(), and Aleph::DynIntervalTree< T, Compare >::tree.

Referenced by TEST().

◆ size()

template<typename T , class Compare = Aleph::less<T>>

size_t Aleph::DynIntervalTree< T, Compare >::size ( ) const

inlinenoexcept

Return the number of intervals in the tree.

Returns: number of nodes.

Exceptions

none

Definition at line 1330 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::size(), and Aleph::DynIntervalTree< T, Compare >::tree.

Referenced by TEST(), TEST(), TEST(), and TEST_F().

◆ stab()

template<typename T , class Compare = Aleph::less<T>>

template<class Op >

void Aleph::DynIntervalTree< T, Compare >::stab	(	const T &	p,
		Op &&	op
	)		const

inline

Apply op to every interval containing point p.

Template Parameters

Op	Callable with signature `void(const Key&)`.

Parameters

[in]	p	query point.
[in]	op	callable to invoke for each containing interval.

Exceptions

May	throw if the provided callback throws.

Definition at line 1312 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::stab(), and Aleph::DynIntervalTree< T, Compare >::tree.

◆ swap()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::DynIntervalTree< T, Compare >::swap ( DynIntervalTree< T, Compare > & other )

inlinenoexcept

Swap state with another tree in O(1).

Parameters

[in,out] other The other tree.

Definition at line 1130 of file tpl_interval_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::swap(), and Aleph::DynIntervalTree< T, Compare >::tree.

Referenced by Aleph::DynIntervalTree< T, Compare >::DynIntervalTree(), and Aleph::DynIntervalTree< T, Compare >::operator=().

◆ traverse() [1/4]

template<typename T , class Compare = Aleph::less<T>>

template<class Operation >

bool Aleph::DynIntervalTree< T, Compare >::traverse ( Operation && op = Operation() )

inline

Overload of traverse() for rvalue callbacks.

Template Parameters

Operation callable with signature bool(const Key&).

Parameters

[in] op callable to perform on each interval.

Returns: true if all items were traversed.

Exceptions

anything that op throws.

Definition at line 1374 of file tpl_interval_tree.H.

References Aleph::divide_and_conquer_partition_dp().

◆ traverse() [2/4]

template<typename T , class Compare = Aleph::less<T>>

template<class Operation >

bool Aleph::DynIntervalTree< T, Compare >::traverse ( Operation && op = Operation() ) const

inline

Const rvalue overload of traverse().

Template Parameters

Operation callable with signature bool(const Key&).

Parameters

[in] op callable to perform on each interval.

Returns: true if all items were traversed.

Exceptions

anything that op throws.

Definition at line 1401 of file tpl_interval_tree.H.

References Aleph::divide_and_conquer_partition_dp().

◆ traverse() [3/4]

template<typename T , class Compare = Aleph::less<T>>

template<class Operation >

bool Aleph::DynIntervalTree< T, Compare >::traverse ( Operation & op )

inline

Traverse all intervals in inorder (sorted by low endpoint).

If op returns false, traversal stops early.

Template Parameters

Operation callable with signature bool(const Key&).

Parameters

[in] op callable to perform on each interval.

Returns: true if all items were traversed.

Exceptions

anything that op throws.

Definition at line 1359 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::getRoot(), Aleph::traverse(), and Aleph::DynIntervalTree< T, Compare >::tree.

◆ traverse() [4/4]

template<typename T , class Compare = Aleph::less<T>>

template<class Operation >

bool Aleph::DynIntervalTree< T, Compare >::traverse ( Operation & op ) const

inline

Const overload of traverse().

Template Parameters

Operation callable with signature bool(const Key&).

Parameters

[in] op callable to perform on each interval.

Returns: true if all items were traversed.

Exceptions

anything that op throws.

Definition at line 1386 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::getRoot(), Aleph::traverse(), and Aleph::DynIntervalTree< T, Compare >::tree.

◆ verify()

template<typename T , class Compare = Aleph::less<T>>

bool Aleph::DynIntervalTree< T, Compare >::verify ( ) const

inline

Verify all tree invariants (BST, Treap, MaxEndpoint).

Returns: true if valid.

Definition at line 1347 of file tpl_interval_tree.H.

References Aleph::DynIntervalTree< T, Compare >::tree, and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::verify().

Referenced by segment_intersection(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST_F().

Member Data Documentation

◆ tree

template<typename T , class Compare = Aleph::less<T>>

Tree Aleph::DynIntervalTree< T, Compare >::tree

private

Definition at line 1044 of file tpl_interval_tree.H.

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

tpl_interval_tree.H

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Item_Type

◆ Key

◆ Key_Type

◆ Node

◆ Tree

Constructor & Destructor Documentation

◆ DynIntervalTree() [1/7]

◆ DynIntervalTree() [2/7]

◆ DynIntervalTree() [3/7]

◆ DynIntervalTree() [4/7]

◆ ~DynIntervalTree()

◆ DynIntervalTree() [5/7]

◆ DynIntervalTree() [6/7]

◆ DynIntervalTree() [7/7]

Member Function Documentation

◆ all_overlaps()

◆ append()

◆ copy_from()

◆ destroy_tree()

◆ empty()

◆ find_all_overlaps() [1/2]

◆ find_all_overlaps() [2/2]

◆ find_stab()

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ insert_dup()

◆ is_empty()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ overlap_search() [1/2]

◆ overlap_search() [2/2]

◆ remove() [1/2]

◆ remove() [2/2]

◆ search()

◆ size()

◆ stab()

◆ swap()

◆ traverse() [1/4]

◆ traverse() [2/4]

◆ traverse() [3/4]

◆ traverse() [4/4]

◆ verify()

Member Data Documentation

◆ tree