Aleph::Gen_Interval_Tree< NodeType, T, Compare > Class Template Reference

Augmented treap storing intervals with overlap/stabbing queries. More...

#include <tpl_interval_tree.H>

Inheritance diagram for Aleph::Gen_Interval_Tree< NodeType, T, Compare >:

Collaboration diagram for Aleph::Gen_Interval_Tree< NodeType, T, Compare >:

Classes
struct	Iterator
	Inorder iterator over nodes. More...

Public Types
using	Key = Interval< T >
using	IntervalCmp = Interval_Less< T, Compare >
using	Node = NodeType< Key >

Public Member Functions
void	set_seed (const unsigned long seed) noexcept
	Set the random number generator seed.
IntervalCmp	key_comp () const noexcept
	Return the interval comparison functor (over Interval<T> keys)
const Compare &	endpoint_comp () const noexcept
	Return the endpoint comparison functor (const)
const Compare &	get_compare () const noexcept
	Backwards-compatible accessor for the endpoint comparator.
void	swap (Gen_Interval_Tree &tree) noexcept(noexcept(std::swap(tree_root, tree.tree_root)) and noexcept(std::swap(cmp, tree.cmp)) and noexcept(std::swap(r, tree.r)) and noexcept(std::swap(num_nodes, tree.num_nodes)))
	Swap all state with tree in O(1)
	Gen_Interval_Tree (const unsigned long seed, const Compare &_cmp=Compare())
	Construct with explicit seed and comparator.
	Gen_Interval_Tree (const Compare &_cmp=Compare())
	Construct with default seed (from system time).
	Gen_Interval_Tree (const Gen_Interval_Tree &)=delete
	Deleted copy constructor.
Gen_Interval_Tree &	operator= (const Gen_Interval_Tree &)=delete
	Deleted copy assignment.
	Gen_Interval_Tree (Gen_Interval_Tree &&)=delete
	Deleted move constructor.
Gen_Interval_Tree &	operator= (Gen_Interval_Tree &&)=delete
	Deleted move assignment.
	~Gen_Interval_Tree ()
gsl_rng *	gsl_rng_object () const noexcept
	Get a pointer to the GSL random number generator.
Node *&	getRoot () noexcept
	Return the tree's root.
const Node *	getRoot () const
	Return the tree's root (const)
size_t	size () const noexcept
	Return the number of nodes.
bool	is_empty () const noexcept
	Return true if the tree is empty.
void	reset_num_nodes () noexcept
	Reset the node count (used after manual tree destruction)
const Node *	search (const Key &key) const
	Search for an exact interval in the tree.
Node *	insert (Node *p)
	Insert a node (no duplicates).
Node *	insert_dup (Node *p)
	Insert a node (duplicates allowed).
Node *	remove (const Key &key)
	Remove an interval from the tree.
const Node *	overlap_search (const Key &query) const
	Find any interval that overlaps with query (CLRS algorithm).
template<class Op >
void	all_overlaps (const Key &query, Op &&op) const
	Apply op to every interval overlapping query.
DynList< Key >	find_all_overlaps (const Key &query) const
	Find all intervals overlapping query.
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.
bool	verify () const
	Verify BST, heap, and max_endpoint invariants.

Private Member Functions
void	init (const unsigned int seed)
Node *	insert (Node *root, Node *p)
Node *	insert_dup (Node *root, Node *p)
Node *	remove (Node *&root, const Key &key)

Static Private Member Functions
static void	update_max (Node *p, const Compare &cmp)
	Recalculate max_endpoint from node's own high and children.
static Node *	rotate_to_right_it (Node *p, const Compare &cmp)
	Rotate right with augmented field update.
static Node *	rotate_to_left_it (Node *p, const Compare &cmp)
	Rotate left with augmented field update.
static Node *	join_exclusive (Node *t1, Node *t2, const Compare &cmp)
template<class Op >
static void	all_overlaps (Node *root, const Key &query, Op &op, const Compare &cmp)
	Recursive: find all intervals overlapping query.
static bool	check_max (Node *root, const Compare &cmp)
	Verify max_endpoint invariant.
static size_t	count_nodes (Node *root) noexcept

Private Attributes
Node	head
Node *	head_ptr
Node *&	tree_root
gsl_rng *	r
Compare	cmp
size_t	num_nodes

Detailed Description

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

Augmented treap storing intervals with overlap/stabbing queries.

Gen_Interval_Tree is a standalone augmented treap that stores Interval<T> values and maintains a max_endpoint field in each node for efficient interval query pruning.

This is a low-level class managing raw node pointers. For automatic memory management, use DynIntervalTree.

Template Parameters

NodeType	Node template (Interval_Tree_Node or Interval_Tree_NodeVtl).
T	Endpoint type.
Compare	Comparison functor for endpoints.

Complexity:

• Insert: O(log n) expected
• Remove: O(log n) expected
• overlap_search: O(log n) expected
• all_overlaps: O(k log n) where k = number of results
• stab: O(k log n)

Definition at line 513 of file tpl_interval_tree.H.

Member Typedef Documentation

IntervalCmp

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

using Aleph::Gen_Interval_Tree< NodeType, T, Compare >::IntervalCmp = Interval_Less<T, Compare>

Definition at line 517 of file tpl_interval_tree.H.

Key

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

using Aleph::Gen_Interval_Tree< NodeType, T, Compare >::Key = Interval<T>

Definition at line 516 of file tpl_interval_tree.H.

Node

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

using Aleph::Gen_Interval_Tree< NodeType, T, Compare >::Node = NodeType<Key>

Definition at line 518 of file tpl_interval_tree.H.

Constructor & Destructor Documentation

Gen_Interval_Tree() [1/4]

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

Aleph::Gen_Interval_Tree< NodeType, T, Compare >::Gen_Interval_Tree ( const unsigned long  seed, const Compare &  _cmp = Compare()  )

inline

Construct with explicit seed and comparator.

Parameters

[in]	seed	Random seed.
[in]	_cmp	Comparison functor.

Exceptions

ah_bad_alloc_if

if random number generator allocation fails.

Definition at line 761 of file tpl_interval_tree.H.

References Aleph::init, and seed.

Gen_Interval_Tree() [2/4]

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

Aleph::Gen_Interval_Tree< NodeType, T, Compare >::Gen_Interval_Tree ( const Compare &  _cmp = Compare() )

inline

Construct with default seed (from system time).

Parameters

[in]

_cmp

Comparison functor.

Exceptions

ah_bad_alloc_if

if random number generator allocation fails.

Definition at line 773 of file tpl_interval_tree.H.

Gen_Interval_Tree() [3/4]

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

Aleph::Gen_Interval_Tree< NodeType, T, Compare >::Gen_Interval_Tree ( const Gen_Interval_Tree< NodeType, T, Compare > &  )

delete

Deleted copy constructor.

Gen_Interval_Tree() [4/4]

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

Aleph::Gen_Interval_Tree< NodeType, T, Compare >::Gen_Interval_Tree ( Gen_Interval_Tree< NodeType, T, Compare > &&  )

delete

Deleted move constructor.

~Gen_Interval_Tree()

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

Aleph::Gen_Interval_Tree< NodeType, T, Compare >::~Gen_Interval_Tree ( )

inline

Definition at line 788 of file tpl_interval_tree.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::r.

Member Function Documentation

all_overlaps() [1/2]

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

template<class Op >

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

inline

Apply op to every interval overlapping query.

Parameters

query	the query interval
op	callable with signature void(const Interval<T>&)

Complexity: O(k log n) where k = number of overlapping intervals

Definition at line 903 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::all_overlaps(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp, and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::tree_root.

all_overlaps() [2/2]

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

template<class Op >

static void Aleph::Gen_Interval_Tree< NodeType, T, Compare >::all_overlaps ( Node *  root, const Key &  query, Op &  op, const Compare &  cmp  )

inlinestaticprivate

Recursive: find all intervals overlapping query.

Definition at line 678 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::all_overlaps(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp, Aleph::Interval< T >::high, KEY, LLINK, Aleph::low(), Aleph::Interval< T >::low, Aleph::MAX_EP(), RLINK, and root().

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::all_overlaps(), Aleph::DynIntervalTree< T, Compare >::all_overlaps(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::all_overlaps(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::find_all_overlaps(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::stab().

check_max()

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

static bool Aleph::Gen_Interval_Tree< NodeType, T, Compare >::check_max ( Node *  root, const Compare &  cmp  )

inlinestaticprivate

Verify max_endpoint invariant.

Definition at line 704 of file tpl_interval_tree.H.

References Aleph::and, Aleph::Gen_Interval_Tree< NodeType, T, Compare >::check_max(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), KEY, LLINK, Aleph::MAX_EP(), RLINK, and root().

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::check_max(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::verify().

count_nodes()

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

static size_t Aleph::Gen_Interval_Tree< NodeType, T, Compare >::count_nodes ( Node *  root )

inlinestaticprivatenoexcept

Definition at line 723 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::count_nodes(), LLINK, RLINK, and root().

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::count_nodes(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::verify().

endpoint_comp()

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

const Compare & Aleph::Gen_Interval_Tree< NodeType, T, Compare >::endpoint_comp ( ) const

inlinenoexcept

Return the endpoint comparison functor (const)

Definition at line 738 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp.

Referenced by Aleph::DynIntervalTree< T, Compare >::DynIntervalTree(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::get_compare(), Aleph::DynIntervalTree< T, Compare >::insert(), Aleph::DynIntervalTree< T, Compare >::insert(), and Aleph::DynIntervalTree< T, Compare >::insert_dup().

find_all_overlaps()

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

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

inline

Find all intervals overlapping query.

Parameters

query

the query interval

Returns

DynList of overlapping intervals

Definition at line 913 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::all_overlaps(), Aleph::DynList< T >::append(), and Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::DynIntervalTree< T, Compare >::find_all_overlaps(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::find_stab().

find_stab()

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

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

inline

Find all intervals containing point p.

Parameters

p	the query point

Returns

DynList of intervals containing p

Definition at line 940 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::find_all_overlaps(), and Aleph::Interval< T >::point().

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

get_compare()

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

const Compare & Aleph::Gen_Interval_Tree< NodeType, T, Compare >::get_compare ( ) const

inlinenoexcept

Backwards-compatible accessor for the endpoint comparator.

Definition at line 741 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::endpoint_comp().

getRoot() [1/2]

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

const Node * Aleph::Gen_Interval_Tree< NodeType, T, Compare >::getRoot ( ) const

inline

Return the tree's root (const)

Definition at line 801 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::tree_root.

getRoot() [2/2]

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

Node *& Aleph::Gen_Interval_Tree< NodeType, T, Compare >::getRoot ( )

inlinenoexcept

Return the tree's root.

Definition at line 798 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::tree_root.

Referenced by Aleph::DynIntervalTree< T, Compare >::destroy_tree(), IntervalTreeRawTest::TearDown(), Aleph::DynIntervalTree< T, Compare >::traverse(), and Aleph::DynIntervalTree< T, Compare >::traverse().

gsl_rng_object()

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

gsl_rng * Aleph::Gen_Interval_Tree< NodeType, T, Compare >::gsl_rng_object ( ) const

inlinenoexcept

Get a pointer to the GSL random number generator.

Definition at line 795 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::r.

init()

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

void Aleph::Gen_Interval_Tree< NodeType, T, Compare >::init ( const unsigned int  seed )

inlineprivate

Definition at line 528 of file tpl_interval_tree.H.

References ah_bad_alloc_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::head_ptr, Aleph::Min_Priority, Aleph::PRIO(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::r, and seed.

insert() [1/2]

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

Node * Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert ( Node *  p )

inline

Insert a node (no duplicates).

Parameters

p	pointer to the node to insert

Returns

p if inserted, nullptr if duplicate

Definition at line 828 of file tpl_interval_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), KEY, Aleph::Gen_Interval_Tree< NodeType, T, Compare >::num_nodes, Aleph::PRIO(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::r, and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::tree_root.

insert() [2/2]

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

Node * Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert ( Node *  root, Node *  p  )

inlineprivate

Definition at line 573 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), KEY, LLINK, Aleph::PRIO(), RLINK, root(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::rotate_to_left_it(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::rotate_to_right_it(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::update_max().

Referenced by Aleph::DynIntervalTree< T, Compare >::insert(), Aleph::DynIntervalTree< T, Compare >::insert(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert().

insert_dup() [1/2]

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

Node * Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup ( Node *  p )

inline

Insert a node (duplicates allowed).

Parameters

p	pointer to the node to insert

Returns

the p pointer

Definition at line 846 of file tpl_interval_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup(), KEY, Aleph::Gen_Interval_Tree< NodeType, T, Compare >::num_nodes, Aleph::PRIO(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::r, and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::tree_root.

insert_dup() [2/2]

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

Node * Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup ( Node *  root, Node *  p  )

inlineprivate

Definition at line 608 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup(), KEY, LLINK, Aleph::PRIO(), RLINK, root(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::rotate_to_left_it(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::rotate_to_right_it(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::update_max().

Referenced by Aleph::DynIntervalTree< T, Compare >::insert_dup(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup().

is_empty()

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

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

inlinenoexcept

Return true if the tree is empty.

Definition at line 807 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::num_nodes.

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

join_exclusive()

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

static Node * Aleph::Gen_Interval_Tree< NodeType, T, Compare >::join_exclusive ( Node *  t1, Node *  t2, const Compare &  cmp  )

inlinestaticprivate

Definition at line 631 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::join_exclusive(), LLINK, Aleph::PRIO(), RLINK, and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::update_max().

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::join_exclusive(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::remove().

key_comp()

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

IntervalCmp Aleph::Gen_Interval_Tree< NodeType, T, Compare >::key_comp ( ) const

inlinenoexcept

Return the interval comparison functor (over Interval<T> keys)

Definition at line 735 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp.

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::search(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::verify().

operator=() [1/2]

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

Gen_Interval_Tree & Aleph::Gen_Interval_Tree< NodeType, T, Compare >::operator= ( const Gen_Interval_Tree< NodeType, T, Compare > &  )

delete

Deleted copy assignment.

operator=() [2/2]

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

Gen_Interval_Tree & Aleph::Gen_Interval_Tree< NodeType, T, Compare >::operator= ( Gen_Interval_Tree< NodeType, T, Compare > &&  )

delete

Deleted move assignment.

overlap_search()

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

const Node * Aleph::Gen_Interval_Tree< NodeType, T, Compare >::overlap_search ( const Key &  query ) const

inline

Find any interval that overlaps with query (CLRS algorithm).

Parameters

query

the query interval

Returns

pointer to a node whose interval overlaps query, or nullptr

Complexity: O(log n) expected

Definition at line 878 of file tpl_interval_tree.H.

References Aleph::and, Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), KEY, LLINK, Aleph::Interval< T >::low, Aleph::MAX_EP(), RLINK, and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::tree_root.

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

remove() [1/2]

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

Node * Aleph::Gen_Interval_Tree< NodeType, T, Compare >::remove ( const Key &  key )

inline

Remove an interval from the tree.

Parameters

key	the interval to remove

Returns

pointer to removed node if found, nullptr otherwise

Definition at line 861 of file tpl_interval_tree.H.

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

remove() [2/2]

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

Node * Aleph::Gen_Interval_Tree< NodeType, T, Compare >::remove ( Node *&  root, const Key &  key  )

inlineprivate

Definition at line 650 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::join_exclusive(), KEY, LLINK, Aleph::Gen_Interval_Tree< NodeType, T, Compare >::remove(), RLINK, root(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::update_max().

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

reset_num_nodes()

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

void Aleph::Gen_Interval_Tree< NodeType, T, Compare >::reset_num_nodes ( )

inlinenoexcept

Reset the node count (used after manual tree destruction)

Definition at line 810 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::num_nodes.

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

rotate_to_left_it()

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

static Node * Aleph::Gen_Interval_Tree< NodeType, T, Compare >::rotate_to_left_it ( Node *  p, const Compare &  cmp  )

inlinestaticprivate

Rotate left with augmented field update.

Definition at line 562 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), LLINK, RLINK, and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::update_max().

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup().

rotate_to_right_it()

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

static Node * Aleph::Gen_Interval_Tree< NodeType, T, Compare >::rotate_to_right_it ( Node *  p, const Compare &  cmp  )

inlinestaticprivate

Rotate right with augmented field update.

Definition at line 550 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), LLINK, RLINK, and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::update_max().

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup().

search()

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

const Node * Aleph::Gen_Interval_Tree< NodeType, T, Compare >::search ( const Key &  key ) const

inline

Search for an exact interval in the tree.

Parameters

key	the interval to search for

Returns

pointer to the node if found, nullptr otherwise

Definition at line 817 of file tpl_interval_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::key_comp(), Aleph::searchInBinTree(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::tree_root.

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

set_seed()

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

void Aleph::Gen_Interval_Tree< NodeType, T, Compare >::set_seed ( const unsigned long  seed )

inlinenoexcept

Set the random number generator seed.

Definition at line 732 of file tpl_interval_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::r, and seed.

Referenced by IntervalTreeRawTest::SetUp().

size()

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

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

inlinenoexcept

Return the number of nodes.

Definition at line 804 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::num_nodes.

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

stab()

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

template<class Op >

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

inline

Apply op to every interval containing point p.

Parameters

p	the query point
op	callable with signature void(const Interval<T>&)

Exceptions

May	throw if the provided callback throws.

Complexity: O(k log n)

Definition at line 929 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::all_overlaps(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Interval< T >::point().

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

swap()

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

void Aleph::Gen_Interval_Tree< NodeType, T, Compare >::swap ( Gen_Interval_Tree< NodeType, T, Compare > &  tree )

inlinenoexcept

Swap all state with tree in O(1)

Definition at line 744 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp, Aleph::Gen_Interval_Tree< NodeType, T, Compare >::num_nodes, Aleph::Gen_Interval_Tree< NodeType, T, Compare >::r, and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::tree_root.

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

update_max()

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

static void Aleph::Gen_Interval_Tree< NodeType, T, Compare >::update_max ( Node *  p, const Compare &  cmp  )

inlinestaticprivate

Recalculate max_endpoint from node's own high and children.

Definition at line 537 of file tpl_interval_tree.H.

References Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), KEY, LLINK, Aleph::MAX_EP(), and RLINK.

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::join_exclusive(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::remove(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::rotate_to_left_it(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::rotate_to_right_it().

verify()

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

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

inline

Verify BST, heap, and max_endpoint invariants.

Returns

true if all invariants hold

Definition at line 949 of file tpl_interval_tree.H.

References Aleph::check_bst(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::check_max(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp, Aleph::Gen_Interval_Tree< NodeType, T, Compare >::count_nodes(), Aleph::divide_and_conquer_partition_dp(), Aleph::is_treap(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::key_comp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::num_nodes, and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::tree_root.

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

Member Data Documentation

cmp

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

Compare Aleph::Gen_Interval_Tree< NodeType, T, Compare >::cmp

private

Definition at line 525 of file tpl_interval_tree.H.

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::all_overlaps(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::all_overlaps(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::check_max(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::endpoint_comp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::join_exclusive(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::key_comp(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::overlap_search(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::remove(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::rotate_to_left_it(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::rotate_to_right_it(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::swap(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::update_max(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::verify().

head

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

Node Aleph::Gen_Interval_Tree< NodeType, T, Compare >::head

private

Definition at line 521 of file tpl_interval_tree.H.

head_ptr

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

Node* Aleph::Gen_Interval_Tree< NodeType, T, Compare >::head_ptr

private

Definition at line 522 of file tpl_interval_tree.H.

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::init().

num_nodes

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

size_t Aleph::Gen_Interval_Tree< NodeType, T, Compare >::num_nodes

private

Definition at line 526 of file tpl_interval_tree.H.

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::is_empty(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::remove(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::reset_num_nodes(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::size(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::swap(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::verify().

r

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

gsl_rng* Aleph::Gen_Interval_Tree< NodeType, T, Compare >::r

private

Definition at line 524 of file tpl_interval_tree.H.

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::~Gen_Interval_Tree(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::gsl_rng_object(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::init(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::set_seed(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::swap().

tree_root

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

Node*& Aleph::Gen_Interval_Tree< NodeType, T, Compare >::tree_root

private

Definition at line 523 of file tpl_interval_tree.H.

Referenced by Aleph::Gen_Interval_Tree< NodeType, T, Compare >::all_overlaps(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::getRoot(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::getRoot(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::insert_dup(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::overlap_search(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::remove(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::search(), Aleph::Gen_Interval_Tree< NodeType, T, Compare >::swap(), and Aleph::Gen_Interval_Tree< NodeType, T, Compare >::verify().

---

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

• tpl_interval_tree.H