Dynamic set backed by balanced binary search trees with automatic memory management. More...

#include <tpl_dynSetTree.H>

Inheritance diagram for Aleph::DynSetTree< Key, Tree, Compare >:

Collaboration diagram for Aleph::DynSetTree< Key, Tree, Compare >:

Classes
struct	Has_Range_Methods

struct	Iterator

struct	Node_Op

Public Types
using	Node = typename Tree< Key, Compare >::Node
	Type of binary node used by the binary search tree internal.

using	Tree_Type = Tree< Key, Compare >

typedef DynSetTree	Set_Type

typedef Key	Item_Type

typedef Key	Key_Type

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

using	const_iterator = StlConstIterator< SetName >

Public Member Functions
void	swap (DynSetTree &dset) noexcept(noexcept(tree.swap(dset.tree)) and noexcept(std::swap(num_nodes, dset.num_nodes)) and noexcept(std::swap(arena_allocator, dset.arena_allocator)))
	Exchange all elements of this set with dset in constant time (and extremely fast).

	DynSetTree (const Compare &cmp=Compare())
	Instantiate a dynamic set.

	DynSetTree (const char *base_addr, const size_t &sz, const Compare &cmp=Compare())
	Instantiate a dynamic set using an arena allocator with external buffer.

	DynSetTree (const size_t &arena_sz, const Compare &cmp=Compare())
	Instantiate a dynamic set using an arena allocator with dynamic buffer.

	DynSetTree (const DynSetTree &srcTree)
	instantiates a dynamic copy of srcTree

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

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

	DynSetTree (std::initializer_list< Key > l)

	DynSetTree (DynSetTree &&srcTree) noexcept

void	empty ()
	remove all elements from the set

DynSetTree &	operator= (const DynList< Key > &list)

DynSetTree &	operator= (const DynSetTree &srcTree)
	assigns this to the dynamic array srctree

DynSetTree &	operator= (DynSetTree &&srcTree) noexcept
	Assigns the dynamic set srcTree to this.

virtual	~DynSetTree ()
	Destroyer; all elements are released.

Key *	insert (const Key &key)
	Inserts a key into the dynamic set.

Key *	insert (Key &&key)

Key *	append (const Key &key)

Key *	append (Key &&key)

Key *	search_or_insert (const Key &key)
	Look for the key in the binary search tree or inserts it if it is not found.

Key *	search_or_insert (Key &&key)

std::pair< Key *, bool >	contains_or_insert (const Key &key)

std::pair< Key *, bool >	contains_or_insert (Key &&key)

Key *	insert_dup (const Key &key)

Key *	insert_dup (Key &&key)

Key *	put (const Key &key)

Key *	put (Key &&key)

size_t	remove (const Key &key)
	Removes a key from the dynamic set.

Key	del (const Key &key)
	Deletes `key` and returns a full copy of stored key.

Key	remove_pos (const size_t i)
	Removes a key from the dynamic set.

bool	exist (const Key &key) const
	Returns true if key belongs to the dynamic set.

bool	has (const Key &key) const

bool	contains (const Key &key) const

Key &	find (const Key &key) const
	Returns a modifiable reference to an element within the set.

std::pair< long, Key * >	find_position (const Key &key) const
	Returns the infix (ordinate) position of the key key or whatever It would be your position of belonging to the tree.

Key *	search (const Key &key) const
	Find an element in the set.

const Key &	min () const
	Returns the smallest key contained in the set according to the criterion comparison given.

const Key &	get_first () const

const Key &	max () const
	Returns the largest key contained in the set according to the criteria comparison given.

const Key &	get_last () const

const Key &	get () const
	Synonym of max.

const size_t &	size () const
	Returns the cardinality of the set.

bool	is_empty () const
	returns true if the set is empty

bool	uses_arena () const noexcept
	Returns true if the set is using an arena allocator.

size_t	arena_allocated_size () const noexcept
	Returns the allocated size from the arena (0 if not using arena)

size_t	arena_available_size () const noexcept
	Returns the available size in the arena (0 if not using arena)

size_t	internal_path_length () const
	Calculates and returns the length of the internal path of the tree search binary.

Node *	get_root_node () const

const Key &	get_root () const

const Key &	get_item () const
	Returns any element of the set.

size_t	height () const
	Calculates and returns the height of the binary search tree.

template<class Op >
void	for_each_in_preorder (void(visitFct)(Node , int, int))
	Performs a prefix traversal over all nodes in the tree and invokes the `visitFct` operation on each visit.

long	position (const Key &key) const
	Returns the infix (ordered) position of the key.

Key &	select (size_t i)
	Returns the ith node in infix position.

const Key &	select (size_t i) const

Key &	operator() (size_t i)

const Key &	operator[] (const Key &key) const

const Key &	operator[] (const Key &key)

Key &	access (size_t i)

bool	verify () const

template<class Key_Op >
void	for_each_preorder (Key_Op &key_op) const
	Performs a prefix traversal over all keys in the set and invokes operation Op.

template<class Key_Op >
void	for_each_preorder (Key_Op &&key_op=Key_Op()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Performs a preorder traversal over all keys using a temporary operation object.

template<class Key_Op >
void	for_each_inorder (Key_Op &key_op) const
	Performs an infix traversal over all keys in the set and invokes operation Op.

template<class Key_Op >
void	for_each_inorder (Key_Op &&key_op=Key_Op()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Performs an infix traversal over all keys using a temporary operation object.

template<class Key_Op >
void	for_each_postorder (Key_Op &key_op) const
	Performs a postfix traversal over all keys in the set and invokes operation Op.

template<class Key_Op >
void	for_each_postorder (Key_Op &&key_op=Key_Op()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Performs a postorder traversal over all keys using a temporary operation object.

DynSetTree &	join (DynSetTree &t, DynSetTree &dup)
	Union of two binary search trees.

DynSetTree &	join (DynSetTree &t, DynSetTree &&dup=DynSetTree())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Union of two binary search trees using a move-constructed duplicate tree.

DynSetTree &	join_dup (DynSetTree &t)
	Union of two binary search trees.

bool	split_key (const Key &key, DynSetTree &l, DynSetTree &r)
	Partitions the binary search tree based on a key.

void	split_pos (const size_t pos, DynSetTree &l, DynSetTree &r)
	Partitions the binary search tree based on an infix position.

void	split_key_dup (const Key &key, DynSetTree &l, DynSetTree &r)
	Partitions the binary search tree based on a key that may be present in the tree.

template<class Operation >
bool	traverse (Operation &op)
	Traverse all the set of pairs and for each key executes the operation op.

template<class Operation >
bool	traverse (Operation &&op=Operation())

template<class Operation >
bool	traverse (Operation &op) const

template<class Operation >
bool	traverse (Operation &&op=Operation()) const

Public Member Functions inherited from LocateFunctions< Container, Type >
auto	get_it () const
	Return a properly initialized iterator positioned at the first item on the container.

auto	get_it (const size_t pos) const
	Return a properly initialized iterator positioned at the `pos` item on the container.

auto	get_itor () const
	Alias of `get_it()`.

Type &	nth_ne (const size_t n) noexcept
	Return the n‑th element without bounds checking.

const Type &	nth_ne (const size_t n) const noexcept
	Const overload of `nth_ne(size_t)`.

Type &	nth (const size_t n)
	Return the n-th item of container.

const Type &	nth (const size_t n) const
	Const overload of `nth(size_t)`.

template<class Operation >
Type *	find_ptr (Operation &operation) noexcept(operation_is_noexcept< Operation >())
	Find a pointer to an item in the container according to a searching criteria.

template<class Operation >
const Type *	find_ptr (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
	Const overload of `find_ptr(Operation&)`.

template<class Operation >
const Type *	find_ptr (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of `find_ptr(Operation&) const` that accepts rvalues.

template<class Operation >
Type *	find_ptr (Operation &&operation) noexcept(operation_is_noexcept< Operation >())
	Overload of `find_ptr(Operation&)` that accepts rvalues.

template<class Operation >
size_t	find_index (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
	Find the position of an item in the container according to a searching criteria.

template<class Operation >
size_t	find_index (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of `find_index(Operation&)` that accepts rvalues.

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &operation) noexcept(operation_is_noexcept< Operation >())
	Safe sequential searching of an item matching a criteria.

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &operation) const noexcept(operation_is_noexcept< Operation >())

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &&operation) noexcept(operation_is_noexcept< Operation >())

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())

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(Operation&) const` that accepts rvalues.

template<class Operation >
void	for_each (Operation &&operation)
	Overload of `for_each(Operation&)` 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 `for_each(Operation&)` that accepts rvalues.

template<class Operation >
void	each (Operation &&operation)
	Alias of `for_each(Operation&)` 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)

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

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

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

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

template<class Operation >
bool	exists (Operation &&op) const
	Overload of `exists(Operation&)` 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(Operation&)` 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(Prop, Operation&)` 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(const __T&, Op&)` 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(const __T&, Op&)` 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(const T&, Operation&)` that accepts rvalues.

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

template<class Operation >
Aleph::DynList< T >	filter (Operation &&operation) const
	Overload of `filter(Operation&)` 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 criteria 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(Operation&)` 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 criteria 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(Operation&)` 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 criteria.

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

template<class Operation >
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 criteria.

template<class Operation >
std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &&op) const
	Overload of `tpartition(Operation&)` 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 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 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
Node *	alloc_node (const Key &key)

Node *	alloc_node (Key &&key)

void	free_node (Node *p)

Key *	__insert (Node *p)

Key *	__search_or_insert (Node *p)

std::pair< Node *, bool >	__contains_or_insert (Node *p)

Key *	__insert_dup (Node *q)

Static Private Member Functions
template<typename T >
static auto	call_select (const T &t, const size_t i, int) -> decltype(t.select(i))

template<typename T >
static auto	call_select_nc (T &t, const size_t i, int) -> decltype(t.select(i))

template<typename T >
static Node *	call_select (const T &, const size_t,...)

template<typename T >
static Node *	call_select_nc (T &, const size_t,...)

template<typename T >
static auto	call_remove_pos (T &t, const size_t i, int) -> decltype(t.remove_pos(i))

template<typename T >
static Node *	call_remove_pos (T &, const size_t,...)

template<typename T >
static auto	call_split_pos (T &t, const size_t pos, T &l, T &r, int) -> decltype(t.split_pos(pos, l, r), void())

template<typename T >
static void	call_split_pos (T &, const size_t, T &, T &,...)

template<typename T >
static auto	call_position (const T &t, const Key &key, int) -> decltype(t.position(key))

template<typename T >
static std::pair< long, Node * >	call_position (const T &, const Key &,...)

template<typename T >
static auto	call_find_position (const T &t, const Key &key, int) -> decltype(t.find_position(key))

template<typename T >
static std::pair< long, Node * >	call_find_position (const T &, const Key &,...)

Private Attributes
Tree< Key, Compare >	tree

size_t	num_nodes

std::unique_ptr< ArenaTreeAllocator< Node > >	arena_allocator

Static Private Attributes
static constexpr size_t	dim = 13

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

	each

	each

Detailed Description

template<typename Key, template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>
class Aleph::DynSetTree< Key, Tree, Compare >

Dynamic set backed by balanced binary search trees with automatic memory management.

DynSetTree<Key, Tree, Compare> is a high-level dynamic set container that uses any of several balanced BST implementations (AVL, Red-Black, Treap, Splay, etc.) to maintain a sorted collection of unique keys.

Unlike the low-level tree classes (e.g., Avl_Tree, Rb_Tree), DynSetTree automatically manages node memory, provides rich functional operations (map, filter, fold), and offers an STL-compatible interface.

Template Parameters

Key	The type of keys stored in the set.
Tree	The underlying tree implementation template (default: Avl_Tree). Can be Avl_Tree, Rb_Tree, Treap, TreapRk, Splay_Tree, Rand_Tree.
Compare	Comparison functor for ordering keys (default: Aleph::less<Key>).

Complexity (depends on Tree type):

Search: O(log n) average/worst (AVL, RB); O(log n) amortized (Splay); O(log n) expected (Treap, Rand)
Insert: O(log n) with same characteristics as search
Delete: O(log n) with same characteristics as search
size(): O(1) - maintained by counter
Ranked operations (if Tree supports them, e.g., TreapRk, Avl_Tree_Rk): O(log n)

Supported Tree Types:

Avl_Tree: Strictest balance, O(log n) worst-case, more rotations
Rb_Tree: Relaxed balance, O(log n) worst-case, fewer rotations
Treap: Randomized, O(log n) expected, simple implementation
TreapRk: Treap with rank (indexed access), O(log n) expected
Splay_Tree: Self-adjusting, O(log n) amortized, cache-friendly
Rand_Tree: Randomized tree, O(log n) expected
BinTree: Unbalanced (for testing/comparison, not recommended)

Key Features:

Automatic node memory management (RAII)
STL-compatible iterators and interface
Rich functional operations (map, filter, fold, zip, etc.)
Support for ranked operations (if underlying tree supports them)
Duplicate handling variants (insert vs insert_dup)
Split/join operations
Set operations (union, intersection, difference)

Example:: // AVL-backed set (default)

DynSetTree<int> avl_set = {5, 2, 8, 1, 9};

// Red-Black backed set

DynSetTree<int, Rb_Tree> rb_set;

rb_set.insert(42);

rb_set.insert(17);

// Treap with rank (supports indexed access)

DynSetTree<std::string, TreapRk> ranked_set;

ranked_set.insert("apple");

ranked_set.insert("banana");

ranked_set.insert("cherry");

auto second = ranked_set.select(1); // Get element at index 1

// Functional operations

auto doubled = avl_set.maps<int>([](int x) { return x * 2; });

int sum = avl_set.foldl(0, [](int acc, int x) { return acc + x; });

// STL compatibility

for (const auto& key : avl_set)

std::cout << key << " ";

Aleph::DynSetTree
Dynamic set backed by balanced binary search trees with automatic memory management.
Definition tpl_dynSetTree.H:273

Aleph::DynSetTree::insert
Key * insert(const Key &key)
Inserts a key into the dynamic set.
Definition tpl_dynSetTree.H:646

FunctionalMethods::maps
Aleph::DynList< __T > maps(Operation &op) const
Map the elements of the container.
Definition ah-dry.H:904

std
STL namespace.

Ranked Operations:

If the underlying tree supports rank (TreapRk, Avl_Tree_Rk, etc.), additional operations become available:

select(i): Get the i-th smallest element, O(log n)
position(key): Get the rank/position of a key, O(log n)
remove_pos(i): Remove element at position i, O(log n)

Note: Keys must be unique. For duplicate support, use insert_dup().; The tree is automatically balanced according to the Tree policy.; Memory is automatically managed - nodes are freed on destruction.

See also: Avl_Tree Low-level AVL tree (manual memory management).; Rb_Tree Low-level Red-Black tree (manual memory management).; TreapRk Low-level Treap with rank (manual memory management).; FunctionalMethods Inherited functional operations.

Definition at line 267 of file tpl_dynSetTree.H.

Member Typedef Documentation

◆ Item_Type

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

typedef Key Aleph::DynSetTree< Key, Tree, Compare >::Item_Type

Definition at line 488 of file tpl_dynSetTree.H.

◆ Key_Type

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

typedef Key Aleph::DynSetTree< Key, Tree, Compare >::Key_Type

Definition at line 490 of file tpl_dynSetTree.H.

◆ Node

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

using Aleph::DynSetTree< Key, Tree, Compare >::Node = typename Tree<Key, Compare>::Node

Type of binary node used by the binary search tree internal.

Definition at line 277 of file tpl_dynSetTree.H.

◆ Set_Type

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

typedef DynSetTree Aleph::DynSetTree< Key, Tree, Compare >::Set_Type

Definition at line 486 of file tpl_dynSetTree.H.

◆ Tree_Type

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

using Aleph::DynSetTree< Key, Tree, Compare >::Tree_Type = Tree<Key, Compare>

Definition at line 279 of file tpl_dynSetTree.H.

Constructor & Destructor Documentation

◆ DynSetTree() [1/8]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Aleph::DynSetTree< Key, Tree, Compare >::DynSetTree ( const Compare & cmp = Compare() )

inline

Instantiate a dynamic set.

Definition at line 508 of file tpl_dynSetTree.H.

◆ DynSetTree() [2/8]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Aleph::DynSetTree< Key, Tree, Compare >::DynSetTree	(	const char *	base_addr,
		const size_t &	sz,
		const Compare &	cmp = `Compare()`
	)

inline

Instantiate a dynamic set using an arena allocator with external buffer.

Definition at line 515 of file tpl_dynSetTree.H.

◆ DynSetTree() [3/8]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Aleph::DynSetTree< Key, Tree, Compare >::DynSetTree	(	const size_t &	arena_sz,
		const Compare &	cmp = `Compare()`
	)

inlineexplicit

Instantiate a dynamic set using an arena allocator with dynamic buffer.

Definition at line 524 of file tpl_dynSetTree.H.

◆ DynSetTree() [4/8]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Aleph::DynSetTree< Key, Tree, Compare >::DynSetTree ( const DynSetTree< Key, Tree, Compare > & srcTree )

inline

instantiates a dynamic copy of srcTree

Definition at line 533 of file tpl_dynSetTree.H.

References Aleph::copyRec(), FunctionalMethods< Container, T >::maps(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

◆ DynSetTree() [5/8]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<template< typename > class List>

Aleph::DynSetTree< Key, Tree, Compare >::DynSetTree ( const List< Key > & l )

inline

Definition at line 548 of file tpl_dynSetTree.H.

◆ DynSetTree() [6/8]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<class It >

Aleph::DynSetTree< Key, Tree, Compare >::DynSetTree	(	It	b,
		It	e
	)

inline

Definition at line 548 of file tpl_dynSetTree.H.

◆ DynSetTree() [7/8]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Aleph::DynSetTree< Key, Tree, Compare >::DynSetTree ( std::initializer_list< Key > l )

inline

Definition at line 548 of file tpl_dynSetTree.H.

◆ DynSetTree() [8/8]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Aleph::DynSetTree< Key, Tree, Compare >::DynSetTree ( DynSetTree< Key, Tree, Compare > && srcTree )

inlinenoexcept

Definition at line 550 of file tpl_dynSetTree.H.

References FunctionalMethods< Container, T >::maps(), and Aleph::DynSetTree< Key, Tree, Compare >::swap().

◆ ~DynSetTree()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

virtual Aleph::DynSetTree< Key, Tree, Compare >::~DynSetTree ( )

inlinevirtual

Destroyer; all elements are released.

Definition at line 610 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::empty().

Member Function Documentation

◆ __contains_or_insert()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

std::pair< Node *, bool > Aleph::DynSetTree< Key, Tree, Compare >::__contains_or_insert ( Node * p )

inlineprivate

Definition at line 704 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::free_node(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::contains_or_insert(), and Aleph::DynSetTree< Key, Tree, Compare >::contains_or_insert().

◆ __insert()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::__insert ( Node * p )

inlineprivate

Definition at line 616 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::free_node(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::insert(), and Aleph::DynSetTree< Key, Tree, Compare >::insert().

◆ __insert_dup()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::__insert_dup ( Node * q )

inlineprivate

Definition at line 775 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::free_node(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::insert_dup(), and Aleph::DynSetTree< Key, Tree, Compare >::insert_dup().

◆ __search_or_insert()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::__search_or_insert ( Node * p )

inlineprivate

Definition at line 683 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::free_node(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::search_or_insert(), and Aleph::DynSetTree< Key, Tree, Compare >::search_or_insert().

◆ access()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key & Aleph::DynSetTree< Key, Tree, Compare >::access ( size_t i )

inline

Definition at line 1133 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::select().

Referenced by TEST().

◆ alloc_node() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Node * Aleph::DynSetTree< Key, Tree, Compare >::alloc_node ( const Key & key )

inlineprivate

Definition at line 463 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::arena_allocator.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::contains_or_insert(), Aleph::DynSetTree< Key, Tree, Compare >::contains_or_insert(), Aleph::DynSetTree< Key, Tree, Compare >::insert(), Aleph::DynSetTree< Key, Tree, Compare >::insert(), Aleph::DynSetTree< Key, Tree, Compare >::insert_dup(), Aleph::DynSetTree< Key, Tree, Compare >::insert_dup(), Aleph::DynSetTree< Key, Tree, Compare >::search_or_insert(), and Aleph::DynSetTree< Key, Tree, Compare >::search_or_insert().

◆ alloc_node() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Node * Aleph::DynSetTree< Key, Tree, Compare >::alloc_node ( Key && key )

inlineprivate

Definition at line 470 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::arena_allocator.

◆ append() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::append ( const Key & key )

inline

Definition at line 672 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::insert().

Referenced by Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::insert_arc(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::insert_node(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::sort_arcs(), TYPED_TEST(), and TYPED_TEST().

◆ append() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::append ( Key && key )

inline

Definition at line 677 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::insert().

◆ arena_allocated_size()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

size_t Aleph::DynSetTree< Key, Tree, Compare >::arena_allocated_size ( ) const

inlinenoexcept

Returns the allocated size from the arena (0 if not using arena)

Definition at line 1016 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::arena_allocator.

Referenced by TEST().

◆ arena_available_size()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

size_t Aleph::DynSetTree< Key, Tree, Compare >::arena_available_size ( ) const

inlinenoexcept

Returns the available size in the arena (0 if not using arena)

Definition at line 1024 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::arena_allocator.

Referenced by TEST().

◆ call_find_position() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<typename T >

static std::pair< long, Node * > Aleph::DynSetTree< Key, Tree, Compare >::call_find_position	(	const T &	,
		const Key &	,
			...
	)

inlinestaticprivate

Definition at line 451 of file tpl_dynSetTree.H.

References ah_domain_error.

◆ call_find_position() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<typename T >

static auto Aleph::DynSetTree< Key, Tree, Compare >::call_find_position	(	const T &	t,
		const Key &	key,
		int
	)		-> decltype(t.find_position(key))

inlinestaticprivate

Definition at line 444 of file tpl_dynSetTree.H.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::find_position().

◆ call_position() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<typename T >

static std::pair< long, Node * > Aleph::DynSetTree< Key, Tree, Compare >::call_position	(	const T &	,
		const Key &	,
			...
	)

inlinestaticprivate

Definition at line 437 of file tpl_dynSetTree.H.

References ah_domain_error.

◆ call_position() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<typename T >

static auto Aleph::DynSetTree< Key, Tree, Compare >::call_position	(	const T &	t,
		const Key &	key,
		int
	)		-> decltype(t.position(key))

inlinestaticprivate

Definition at line 430 of file tpl_dynSetTree.H.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::position().

◆ call_remove_pos() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<typename T >

static Node * Aleph::DynSetTree< Key, Tree, Compare >::call_remove_pos	(	T &	,
		const size_t	,
			...
	)

inlinestaticprivate

Definition at line 410 of file tpl_dynSetTree.H.

References ah_domain_error.

◆ call_remove_pos() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<typename T >

static auto Aleph::DynSetTree< Key, Tree, Compare >::call_remove_pos	(	T &	t,
		const size_t	i,
		int
	)		-> decltype(t.remove_pos(i))

inlinestaticprivate

Definition at line 403 of file tpl_dynSetTree.H.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::remove_pos().

◆ call_select() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<typename T >

static Node * Aleph::DynSetTree< Key, Tree, Compare >::call_select	(	const T &	,
		const size_t	,
			...
	)

inlinestaticprivate

Definition at line 389 of file tpl_dynSetTree.H.

References ah_domain_error.

◆ call_select() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<typename T >

static auto Aleph::DynSetTree< Key, Tree, Compare >::call_select	(	const T &	t,
		const size_t	i,
		int
	)		-> decltype(t.select(i))

inlinestaticprivate

Definition at line 374 of file tpl_dynSetTree.H.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::select().

◆ call_select_nc() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<typename T >

static Node * Aleph::DynSetTree< Key, Tree, Compare >::call_select_nc	(	T &	,
		const size_t	,
			...
	)

inlinestaticprivate

Definition at line 396 of file tpl_dynSetTree.H.

References ah_domain_error.

◆ call_select_nc() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<typename T >

static auto Aleph::DynSetTree< Key, Tree, Compare >::call_select_nc	(	T &	t,
		const size_t	i,
		int
	)		-> decltype(t.select(i))

inlinestaticprivate

Definition at line 382 of file tpl_dynSetTree.H.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::select().

◆ call_split_pos() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<typename T >

static void Aleph::DynSetTree< Key, Tree, Compare >::call_split_pos	(	T &	,
		const size_t	,
		T &	,
		T &	,
			...
	)

inlinestaticprivate

Definition at line 424 of file tpl_dynSetTree.H.

References ah_domain_error.

◆ call_split_pos() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<typename T >

static auto Aleph::DynSetTree< Key, Tree, Compare >::call_split_pos	(	T &	t,
		const size_t	pos,
		T &	l,
		T &	r,
		int
	)		-> decltype(t.split_pos(pos, l, r), void())

inlinestaticprivate

Definition at line 417 of file tpl_dynSetTree.H.

References l.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::split_pos().

◆ contains()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

bool Aleph::DynSetTree< Key, Tree, Compare >::contains ( const Key & key ) const

inline

Definition at line 891 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::exist().

Referenced by Aleph::Net_Graph< NodeT, ArcT >::is_sink(), Aleph::Net_Graph< NodeT, ArcT >::is_source(), Aleph::min_cut(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TYPED_TEST(), and TYPED_TEST().

◆ contains_or_insert() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

std::pair< Key *, bool > Aleph::DynSetTree< Key, Tree, Compare >::contains_or_insert ( const Key & key )

inline

Definition at line 762 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::__contains_or_insert(), and Aleph::DynSetTree< Key, Tree, Compare >::alloc_node().

Referenced by TYPED_TEST().

◆ contains_or_insert() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

std::pair< Key *, bool > Aleph::DynSetTree< Key, Tree, Compare >::contains_or_insert ( Key && key )

inline

Definition at line 768 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::__contains_or_insert(), and Aleph::DynSetTree< Key, Tree, Compare >::alloc_node().

◆ del()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key Aleph::DynSetTree< Key, Tree, Compare >::del ( const Key & key )

inline

Deletes key and returns a full copy of stored key.

This method is intended to be used with compound keys, by example pairs, whose searching is done by a particular member of compound data.

Parameters

[in] key key to be removed

Returns: a full copy of stored key

Exceptions

domain_error if the key is not found in the set

Definition at line 840 of file tpl_dynSetTree.H.

References ah_domain_error_if, Aleph::DynSetTree< Key, Tree, Compare >::free_node(), FunctionalMethods< Container, T >::maps(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynMapTree< Key, Data, Tree, Compare >::remove(), Aleph::DynMapTree< Key, Data, Tree, Compare >::remove(), and Aleph::DynMapTree< Key, Data, Tree, Compare >::remove_key().

◆ empty()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

void Aleph::DynSetTree< Key, Tree, Compare >::empty ( )

inline

remove all elements from the set

Definition at line 557 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::arena_allocator, Aleph::callKeyDestructorsRec(), Aleph::destroyRec(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::~DynSetTree(), Aleph::Huffman_Encoder_Engine::build_encoding_map(), Aleph::MCF_Graph< NodeT, ArcT >::build_node_index(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::build_reverse_mappings(), Aleph::AHMapping< Key, ValueType >::clear(), Aleph::Huffman_Encoder_Engine::clear_build_state(), Aleph::compute_min_cut(), Aleph::Network_Simplex< Net >::init_structures(), Aleph::DynSetTree< Key, Tree, Compare >::operator=(), Aleph::DynSetTree< Key, Tree, Compare >::operator=(), reset_huffman_btreepic_state(), and Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::sort_arcs().

◆ exist()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

bool Aleph::DynSetTree< Key, Tree, Compare >::exist ( const Key & key ) const

inline

Returns true if key belongs to the dynamic set.

Definition at line 881 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::search().

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::contains(), Aleph::DynSetTree< Key, Tree, Compare >::has(), and TYPED_TEST().

◆ find()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key & Aleph::DynSetTree< Key, Tree, Compare >::find ( const Key & key ) const

inline

Returns a modifiable reference to an element within the set.

find(key) looks for the key key in the set and returns a modifiable reference to the value contained in the set.

Parameters

[in] key key to search for.

Returns: modifiable reference to the key contained within of the set.

Exceptions

domain_error if key is not within the set.

Note: Be very careful with altering the search order, since the reference is modifiable.

Definition at line 910 of file tpl_dynSetTree.H.

References ah_domain_error_if, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::DynSetTree< Key, Tree, Compare >::operator[](), Aleph::Arcs_Index< GT, Compare, Tree, SA >::remove_from_graph(), and Aleph::Nodes_Index< GT, Compare, Tree, SN >::remove_from_graph().

◆ find_position()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

std::pair< long, Key * > Aleph::DynSetTree< Key, Tree, Compare >::find_position ( const Key & key ) const

inline

Returns the infix (ordinate) position of the key key or whatever It would be your position of belonging to the tree.

find_position(key) searches the extended tree for the key key (which takes time \(O(\lg n)\)) and returns the position infix of the node containing the key.

Parameters

[in] key key to search for and determine infix position.

Returns: infix position of the key within the set ordered if it is found or, otherwise, the position where it would be if it belonged to the tree.

Warning: It only works if the tree handles ranges.

Definition at line 934 of file tpl_dynSetTree.H.

References ah_domain_error_if_constexpr, Aleph::DynSetTree< Key, Tree, Compare >::call_find_position(), FunctionalMethods< Container, T >::maps(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by TEST(), and TEST().

◆ for_each_in_preorder()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<class Op >

void Aleph::DynSetTree< Key, Tree, Compare >::for_each_in_preorder ( void(*)(Node *, int, int) visitFct )

inline

Performs a prefix traversal over all nodes in the tree and invokes the visitFct operation on each visit.

Definition at line 1056 of file tpl_dynSetTree.H.

References FunctionalMethods< Container, T >::maps(), Aleph::preOrderRec(), root(), and Aleph::DynSetTree< Key, Tree, Compare >::tree.

◆ for_each_inorder() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<class Key_Op >

void Aleph::DynSetTree< Key, Tree, Compare >::for_each_inorder ( Key_Op && key_op = Key_Op() ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Performs an infix traversal over all keys using a temporary operation object.

Template Parameters

Key_Op Operation type (default-constructible).

Parameters

[in] key_op Operation to execute on each key (default-constructed if not provided).

Definition at line 1255 of file tpl_dynSetTree.H.

References FunctionalMethods< Container, T >::maps().

◆ for_each_inorder() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<class Key_Op >

void Aleph::DynSetTree< Key, Tree, Compare >::for_each_inorder ( Key_Op & key_op ) const

inline

Performs an infix traversal over all keys in the set and invokes operation Op.

Op(p) has the following structure:

struct Key_Op
{
// state attributes to maintain
 
Key_Op(...) // optional constructor if initialization is needed
{
// initialization
}
 
void operator () (const Key & key)
{
// operation on key
}
};

Parameters

[in] key_op operation to execute on each key

See also: For_Each_In_Order

Definition at line 1238 of file tpl_dynSetTree.H.

References FunctionalMethods< Container, T >::maps(), root(), and Aleph::DynSetTree< Key, Tree, Compare >::tree.

◆ for_each_postorder() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<class Key_Op >

void Aleph::DynSetTree< Key, Tree, Compare >::for_each_postorder ( Key_Op && key_op = Key_Op() ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Performs a postorder traversal over all keys using a temporary operation object.

Template Parameters

Key_Op Operation type (default-constructible).

Parameters

[in] key_op Operation to execute on each key (default-constructed if not provided).

Definition at line 1302 of file tpl_dynSetTree.H.

References FunctionalMethods< Container, T >::maps().

◆ for_each_postorder() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<class Key_Op >

void Aleph::DynSetTree< Key, Tree, Compare >::for_each_postorder ( Key_Op & key_op ) const

inline

Performs a postfix traversal over all keys in the set and invokes operation Op.

Op(p) has the following structure:

struct Key_Op
{
// state attributes to maintain
 
Key_Op(...) // optional constructor if initialization is needed
{
// initialization
}
 
void operator () (const Key & key)
{
// operation on key
}
};

Parameters

[in] key_op operation to execute on each key

See also: For_Each_Postorder

Definition at line 1285 of file tpl_dynSetTree.H.

References FunctionalMethods< Container, T >::maps(), root(), and Aleph::DynSetTree< Key, Tree, Compare >::tree.

◆ for_each_preorder() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<class Key_Op >

void Aleph::DynSetTree< Key, Tree, Compare >::for_each_preorder ( Key_Op && key_op = Key_Op() ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Performs a preorder traversal over all keys using a temporary operation object.

Template Parameters

Key_Op Operation type (default-constructible).

Parameters

[in] key_op Operation to execute on each key (default-constructed if not provided).

Definition at line 1208 of file tpl_dynSetTree.H.

References FunctionalMethods< Container, T >::maps().

◆ for_each_preorder() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<class Key_Op >

void Aleph::DynSetTree< Key, Tree, Compare >::for_each_preorder ( Key_Op & key_op ) const

inline

Performs a prefix traversal over all keys in the set and invokes operation Op.

Op(p) has the following structure:

struct Key_Op
{
// state attributes to maintain
 
Key_Op(...) // optional constructor if initialization is needed
{
// initialization
}
 
void operator () (const Key & key)
{
// operation on key
}
};

Parameters

[in] key_op operation to execute on each key

See also: For_Each_Preorder

Definition at line 1191 of file tpl_dynSetTree.H.

References FunctionalMethods< Container, T >::maps(), root(), and Aleph::DynSetTree< Key, Tree, Compare >::tree.

◆ free_node()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

void Aleph::DynSetTree< Key, Tree, Compare >::free_node ( Node * p )

inlineprivate

Definition at line 477 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::arena_allocator.

◆ get()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

const Key & Aleph::DynSetTree< Key, Tree, Compare >::get ( ) const

inline

Synonym of max.

Definition at line 1001 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::max().

Referenced by TEST(), and TYPED_TEST().

◆ get_first()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

const Key & Aleph::DynSetTree< Key, Tree, Compare >::get_first ( ) const

inline

Definition at line 985 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::min().

Referenced by Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::get_first_arc(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::get_first_node(), TEST(), and TYPED_TEST().

◆ get_item()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

const Key & Aleph::DynSetTree< Key, Tree, Compare >::get_item ( ) const

inline

Returns any element of the set.

Definition at line 1048 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::get_root().

Referenced by Aleph::Net_Graph< NodeT, ArcT >::get_sink(), Aleph::Net_Graph< NodeT, ArcT >::get_source(), TEST(), TYPED_TEST(), Aleph::Net_Graph< NodeT, ArcT >::unmake_super_sink(), and Aleph::Net_Graph< NodeT, ArcT >::unmake_super_source().

◆ get_last()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

const Key & Aleph::DynSetTree< Key, Tree, Compare >::get_last ( ) const

inline

Definition at line 998 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::max().

Referenced by TEST(), and TYPED_TEST().

◆ get_root()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

const Key & Aleph::DynSetTree< Key, Tree, Compare >::get_root ( ) const

inline

Definition at line 1040 of file tpl_dynSetTree.H.

References ah_domain_error_if, KEY, Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::get_item(), and TEST().

◆ get_root_node()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Node * Aleph::DynSetTree< Key, Tree, Compare >::get_root_node ( ) const

inline

Definition at line 1038 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by demonstrate_tree_types(), and TYPED_TEST().

◆ has()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

bool Aleph::DynSetTree< Key, Tree, Compare >::has ( const Key & key ) const

inline

Definition at line 886 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::exist().

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

◆ height()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

size_t Aleph::DynSetTree< Key, Tree, Compare >::height ( ) const

inline

Calculates and returns the height of the binary search tree.

Definition at line 1051 of file tpl_dynSetTree.H.

References Aleph::computeHeightRec(), and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by TYPED_TEST().

◆ insert() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::insert ( const Key & key )

inline

Inserts a key into the dynamic set.

Inserts the key into the dynamic set.

Parameters

[in] key key to insert.

Returns: pointer to the inserted key if it is not inside of the tree; nullptr otherwise.

Definition at line 646 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::__insert(), Aleph::DynSetTree< Key, Tree, Compare >::alloc_node(), Aleph::DynSetTree< Key, Tree, Compare >::free_node(), and FunctionalMethods< Container, T >::maps().

◆ insert() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::insert ( Key && key )

inline

Definition at line 659 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::__insert(), Aleph::DynSetTree< Key, Tree, Compare >::alloc_node(), Aleph::DynSetTree< Key, Tree, Compare >::free_node(), and FunctionalMethods< Container, T >::maps().

◆ insert_dup() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::insert_dup ( const Key & key )

inline

Definition at line 791 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::__insert_dup(), and Aleph::DynSetTree< Key, Tree, Compare >::alloc_node().

Referenced by insert_dup_traversal_test(), and TYPED_TEST().

◆ insert_dup() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::insert_dup ( Key && key )

inline

Definition at line 796 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::__insert_dup(), and Aleph::DynSetTree< Key, Tree, Compare >::alloc_node().

◆ internal_path_length()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

size_t Aleph::DynSetTree< Key, Tree, Compare >::internal_path_length ( ) const

inline

Calculates and returns the length of the internal path of the tree search binary.

Definition at line 1033 of file tpl_dynSetTree.H.

References Aleph::internal_path_length(), and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by TYPED_TEST().

◆ is_empty()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

bool Aleph::DynSetTree< Key, Tree, Compare >::is_empty ( ) const

inline

returns true if the set is empty

Definition at line 1007 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::num_nodes.

Referenced by Aleph::Net_Graph< NodeT, ArcT >::check_network(), Aleph::Net_Graph< NodeT, ArcT >::flow_value(), AHDispatcher< Key, Operation >::is_empty(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TYPED_TEST(), and TYPED_TEST().

◆ join()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

DynSetTree & Aleph::DynSetTree< Key, Tree, Compare >::join	(	DynSetTree< Key, Tree, Compare > &	t,
		DynSetTree< Key, Tree, Compare > &&	dup = `DynSetTree< Key, Tree, Compare >()`
	)

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Union of two binary search trees using a move-constructed duplicate tree.

Parameters

[in]	t	Binary search tree to join with this.
[in]	dup	Binary search tree with duplicate keys (move-constructed, default empty).

Returns: Reference to this tree.

Note: After the call, tree t becomes empty and this becomes the union of both trees.

Definition at line 1338 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::join().

◆ max()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Aleph::DynSetTree< Key, Tree, Compare >::max ( ) const

inline

Returns the largest key contained in the set according to the criteria comparison given.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 989 of file tpl_dynSetTree.H.

References ah_domain_error_if, Aleph::find_max(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::get(), Aleph::DynSetTree< Key, Tree, Compare >::get_last(), TEST(), TEST(), TEST(), TEST(), and TYPED_TEST().

◆ min()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Aleph::DynSetTree< Key, Tree, Compare >::min ( ) const

inline

Returns the smallest key contained in the set according to the criterion comparison given.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 976 of file tpl_dynSetTree.H.

References ah_domain_error_if, Aleph::find_min(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::get_first(), TEST(), TEST(), TEST(), TEST(), and TYPED_TEST().

◆ operator()()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key & Aleph::DynSetTree< Key, Tree, Compare >::operator() ( size_t i )

inline

Definition at line 1118 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::select().

◆ operator=() [1/3]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

DynSetTree & Aleph::DynSetTree< Key, Tree, Compare >::operator= ( const DynList< Key > & list )

inline

Definition at line 576 of file tpl_dynSetTree.H.

◆ operator=() [2/3]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

DynSetTree & Aleph::DynSetTree< Key, Tree, Compare >::operator= ( const DynSetTree< Key, Tree, Compare > & srcTree )

inline

assigns this to the dynamic array srctree

Definition at line 582 of file tpl_dynSetTree.H.

References Aleph::copyRec(), Aleph::DynSetTree< Key, Tree, Compare >::empty(), FunctionalMethods< Container, T >::maps(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

◆ operator=() [3/3]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

DynSetTree & Aleph::DynSetTree< Key, Tree, Compare >::operator= ( DynSetTree< Key, Tree, Compare > && srcTree )

inlinenoexcept

Assigns the dynamic set srcTree to this.

Definition at line 598 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::empty(), FunctionalMethods< Container, T >::maps(), and Aleph::DynSetTree< Key, Tree, Compare >::swap().

◆ operator[]() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

const Key & Aleph::DynSetTree< Key, Tree, Compare >::operator[] ( const Key & key )

inline

Definition at line 1128 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::search_or_insert().

◆ operator[]() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

const Key & Aleph::DynSetTree< Key, Tree, Compare >::operator[] ( const Key & key ) const

inline

Definition at line 1123 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::find().

◆ position()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

long Aleph::DynSetTree< Key, Tree, Compare >::position ( const Key & key ) const

inline

Returns the infix (ordered) position of the key.

position(key) searches the tree for the key (which takes time \(O(\lg n)\)) and returns the infix position of the node containing the key.

Parameters

[in] key key to search for and determine infix position.

Returns: infix position of the key within the set sorted if key found; -1 otherwise

Warning: It only works if the tree handles ranges.

Definition at line 1074 of file tpl_dynSetTree.H.

References ah_domain_error_if_constexpr, Aleph::DynSetTree< Key, Tree, Compare >::call_position(), FunctionalMethods< Container, T >::maps(), and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by TEST(), and TEST().

◆ put() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::put ( const Key & key )

inline

Definition at line 801 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::insert().

Referenced by TYPED_TEST(), and TYPED_TEST().

◆ put() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::put ( Key && key )

inline

Definition at line 806 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::insert().

◆ remove()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

size_t Aleph::DynSetTree< Key, Tree, Compare >::remove ( const Key & key )

inline

Removes a key from the dynamic set.

remove(key) finds the key in the set and removes it.

Parameters

[in] key key to delete

Returns: number of elements that the set has.

Definition at line 818 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::free_node(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::Net_Graph< NodeT, ArcT >::connect_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::register_node(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::remove_arc(), Aleph::Arcs_Index< GT, Compare, Tree, SA >::remove_from_graph(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::remove_from_graph(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::remove_node(), Aleph::Net_Graph< NodeT, ArcT >::remove_node(), TEST(), TEST(), TEST(), TEST(), TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::update_parity_after_arc_insertion(), and Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::update_parity_after_arc_insertion().

◆ remove_pos()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key Aleph::DynSetTree< Key, Tree, Compare >::remove_pos ( const size_t i )

inline

Removes a key from the dynamic set.

Returns: number of elements that the set has.

Definition at line 860 of file tpl_dynSetTree.H.

References ah_domain_error_if_constexpr, ah_logic_error_if, ah_out_of_range_error_if, Aleph::DynSetTree< Key, Tree, Compare >::call_remove_pos(), Aleph::DynSetTree< Key, Tree, Compare >::free_node(), KEY, FunctionalMethods< Container, T >::maps(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

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

◆ search()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::search ( const Key & key ) const

inline

Find an element in the set.

search(key) searches for the key key in the set. If he element is found in the set, then a pointer to the value contained in the set; otherwise nullptr is returned.

Parameters

[in] key key to search for.

Returns: pointer to the element in the set if it is found in it; nullptr of the opposite.

Note: Be very careful with altering the search order, because through the pointer the key is modifiable.

Definition at line 964 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by demonstrate_tree_types(), Aleph::DynSetTree< Key, Tree, Compare >::exist(), Aleph::Init_P< GT >::operator()(), Aleph::DynMapTree< Key, Data, Tree, Compare >::search(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::search(), Aleph::Arcs_Index< GT, Compare, Tree, SA >::search(), Aleph::DynMapTree< Key, Data, Tree, Compare >::search(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::update_parity_after_arc_insertion(), and Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::verify_tables().

◆ search_or_insert() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::search_or_insert ( const Key & key )

inline

Look for the key in the binary search tree or inserts it if it is not found.

search_or_insert(key) searches the binary tree for a node whose key is KEY(p). If the key is finds, then a pointer to it is returned; of what Otherwise key is inserted into the binary tree of search this.

Parameters

[in] key the key to search or insert.

Returns: pointer to the key inside the tree

Definition at line 738 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::__search_or_insert(), and Aleph::DynSetTree< Key, Tree, Compare >::alloc_node().

Referenced by Aleph::DynMapTree< Key, Data, Tree, Compare >::operator[](), Aleph::DynSetTree< Key, Tree, Compare >::operator[](), Aleph::DynMapTree< Key, Data, Tree, Compare >::operator[](), Aleph::Nodes_Index< GT, Compare, Tree, SN >::search_or_insert_in_graph(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::search_or_insert_in_graph(), TEST(), and TYPED_TEST().

◆ search_or_insert() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::search_or_insert ( Key && key )

inline

Definition at line 743 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::__search_or_insert(), and Aleph::DynSetTree< Key, Tree, Compare >::alloc_node().

◆ select() [1/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key & Aleph::DynSetTree< Key, Tree, Compare >::select ( size_t i )

inline

Returns the ith node in infix position.

Parameters

[in] i desired position

Returns: reference to the ith key inserted into the set

Definition at line 1088 of file tpl_dynSetTree.H.

References ah_domain_error_if_constexpr, ah_logic_error_if, ah_out_of_range_error_if, Aleph::DynSetTree< Key, Tree, Compare >::call_select_nc(), FunctionalMethods< Container, T >::maps(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::access(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::make_eulerian(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::make_eulerian(), Aleph::DynSetTree< Key, Tree, Compare >::operator()(), TEST(), TEST(), TEST(), and TEST().

◆ select() [2/2]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

const Key & Aleph::DynSetTree< Key, Tree, Compare >::select ( size_t i ) const

inline

Definition at line 1103 of file tpl_dynSetTree.H.

References ah_domain_error_if_constexpr, ah_logic_error_if, ah_out_of_range_error_if, Aleph::DynSetTree< Key, Tree, Compare >::call_select(), FunctionalMethods< Container, T >::maps(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

◆ size()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

const size_t & Aleph::DynSetTree< Key, Tree, Compare >::size ( ) const

inline

Returns the cardinality of the set.

Definition at line 1004 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::num_nodes.

◆ split_key()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

bool Aleph::DynSetTree< Key, Tree, Compare >::split_key	(	const Key &	key,
		DynSetTree< Key, Tree, Compare > &	l,
		DynSetTree< Key, Tree, Compare > &	r
	)

inline

Partitions the binary search tree based on a key.

split_key(key,l,r) partitions, according to the key key, the binary search tree this in two trees l and r. After the operation the tree this becomes empty, l contains all keys less than key and r the major ones.

Parameters

[in]	key	partition key.
[out]	l	tree with keys less than key.
[out]	r	tree with keys greater than key.

Returns: true if key is not inside the binary tree; in which case the partition was done successfully. Otherwise, yes key is located inside the tree, the tree is not partitioned and the result is false.

Definition at line 1379 of file tpl_dynSetTree.H.

References Aleph::compute_cardinality_rec(), l, FunctionalMethods< Container, T >::maps(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

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

◆ split_key_dup()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

void Aleph::DynSetTree< Key, Tree, Compare >::split_key_dup	(	const Key &	key,
		DynSetTree< Key, Tree, Compare > &	l,
		DynSetTree< Key, Tree, Compare > &	r
	)

inline

Partitions the binary search tree based on a key that may be present in the tree.

split_key_dup(key,l,r) partitions, according to key, the binary search tree this into two trees l and r. After the operation, tree this becomes empty, l contains all keys less than key and r contains keys greater than or equal to key.

Parameters

[in]	key	partition key.
[out]	l	tree with keys less than key.
[out]	r	tree with keys greater than or equal to key.

Definition at line 1433 of file tpl_dynSetTree.H.

References Aleph::compute_cardinality_rec(), l, Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by TEST(), and TEST().

◆ split_pos()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

void Aleph::DynSetTree< Key, Tree, Compare >::split_pos	(	const size_t	pos,
		DynSetTree< Key, Tree, Compare > &	l,
		DynSetTree< Key, Tree, Compare > &	r
	)

inline

Partitions the binary search tree based on an infix position.

split_pos(pos,l,r) partitions the binary search tree this into two trees l and r. After the operation, tree this becomes empty, l contains the first pos+1 keys and r the remaining ones.

Parameters

[in]	pos	partition position
[out]	l	tree with keys in interval [0,pos]
[out]	r	tree with keys in interval (pos,N), where N is the number of keys

Definition at line 1404 of file tpl_dynSetTree.H.

References ah_domain_error_if_constexpr, ah_out_of_range_error_if, Aleph::DynSetTree< Key, Tree, Compare >::call_split_pos(), Aleph::compute_cardinality_rec(), l, FunctionalMethods< Container, T >::maps(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by TEST(), and TEST().

◆ swap()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

void Aleph::DynSetTree< Key, Tree, Compare >::swap ( DynSetTree< Key, Tree, Compare > & dset )

inlinenoexcept

Exchange all elements of this set with dset in constant time (and extremely fast).

Parameters

[in] dset the set to exchange with this

Definition at line 497 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::arena_allocator, FunctionalMethods< Container, T >::maps(), Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::DynSetTree(), Aleph::DynSetTree< Key, Tree, Compare >::operator=(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::swap(), and Aleph::Net_Graph< NodeT, ArcT >::swap().

◆ traverse() [1/4]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<class Operation >

bool Aleph::DynSetTree< Key, Tree, Compare >::traverse ( Operation && op = Operation() )

inline

Definition at line 1491 of file tpl_dynSetTree.H.

References FunctionalMethods< Container, T >::maps().

◆ traverse() [2/4]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<class Operation >

bool Aleph::DynSetTree< Key, Tree, Compare >::traverse ( Operation && op = Operation() ) const

inline

Definition at line 1506 of file tpl_dynSetTree.H.

References FunctionalMethods< Container, T >::maps().

◆ traverse() [3/4]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<class Operation >

bool Aleph::DynSetTree< Key, Tree, Compare >::traverse ( Operation & op )

inline

Traverse all the set of pairs and for each key executes the operation op.

Operation must have the signature

bool operation(T & item)

Aleph::T

std::decay_t< typename HeadC::Item_Type > T

Definition ah-zip.H:107

If

operation()

returns false then the traversal is aborted; otherwise the routine advance and so on

Parameters

[in] op operation to execute for each key

Returns: true if all items are traversed; false otherwise

Definition at line 1482 of file tpl_dynSetTree.H.

References Aleph::traverse(), and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by TYPED_TEST().

◆ traverse() [4/4]

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

template<class Operation >

bool Aleph::DynSetTree< Key, Tree, Compare >::traverse ( Operation & op ) const

inline

Definition at line 1497 of file tpl_dynSetTree.H.

References Aleph::traverse(), and Aleph::DynSetTree< Key, Tree, Compare >::tree.

◆ uses_arena()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

bool Aleph::DynSetTree< Key, Tree, Compare >::uses_arena ( ) const

inlinenoexcept

Returns true if the set is using an arena allocator.

Definition at line 1010 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::arena_allocator.

◆ verify()

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

bool Aleph::DynSetTree< Key, Tree, Compare >::verify ( ) const

inline

Definition at line 1138 of file tpl_dynSetTree.H.

References Aleph::check_bst(), FunctionalMethods< Container, T >::maps(), and Aleph::DynSetTree< Key, Tree, Compare >::tree.

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

Member Data Documentation

◆ arena_allocator

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

std::unique_ptr<ArenaTreeAllocator<Node> > Aleph::DynSetTree< Key, Tree, Compare >::arena_allocator

private

Definition at line 461 of file tpl_dynSetTree.H.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::alloc_node(), Aleph::DynSetTree< Key, Tree, Compare >::alloc_node(), Aleph::DynSetTree< Key, Tree, Compare >::arena_allocated_size(), Aleph::DynSetTree< Key, Tree, Compare >::arena_available_size(), Aleph::DynSetTree< Key, Tree, Compare >::empty(), Aleph::DynSetTree< Key, Tree, Compare >::free_node(), Aleph::DynSetTree< Key, Tree, Compare >::swap(), and Aleph::DynSetTree< Key, Tree, Compare >::uses_arena().

◆ dim

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

constexpr size_t Aleph::DynSetTree< Key, Tree, Compare >::dim = 13

staticconstexprprivate

Definition at line 457 of file tpl_dynSetTree.H.

◆ num_nodes

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

size_t Aleph::DynSetTree< Key, Tree, Compare >::num_nodes

private

Definition at line 460 of file tpl_dynSetTree.H.

◆ tree

template<typename Key , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Tree<Key, Compare> Aleph::DynSetTree< Key, Tree, Compare >::tree

mutableprivate

Definition at line 459 of file tpl_dynSetTree.H.

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

tpl_dynSetTree.H

Classes

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Item_Type

◆ Key_Type

◆ Node

◆ Set_Type

◆ Tree_Type

Constructor & Destructor Documentation

◆ DynSetTree() [1/8]

◆ DynSetTree() [2/8]

◆ DynSetTree() [3/8]

◆ DynSetTree() [4/8]

◆ DynSetTree() [5/8]

◆ DynSetTree() [6/8]

◆ DynSetTree() [7/8]

◆ DynSetTree() [8/8]

◆ ~DynSetTree()

Member Function Documentation

◆ __contains_or_insert()

◆ __insert()

◆ __insert_dup()

◆ __search_or_insert()

◆ access()

◆ alloc_node() [1/2]

◆ alloc_node() [2/2]

◆ append() [1/2]

◆ append() [2/2]

◆ arena_allocated_size()

◆ arena_available_size()

◆ call_find_position() [1/2]

◆ call_find_position() [2/2]

◆ call_position() [1/2]

◆ call_position() [2/2]

◆ call_remove_pos() [1/2]

◆ call_remove_pos() [2/2]

◆ call_select() [1/2]

◆ call_select() [2/2]

◆ call_select_nc() [1/2]

◆ call_select_nc() [2/2]

◆ call_split_pos() [1/2]

◆ call_split_pos() [2/2]

◆ contains()

◆ contains_or_insert() [1/2]

◆ contains_or_insert() [2/2]

◆ del()

◆ empty()

◆ exist()

◆ find()

◆ find_position()

◆ for_each_in_preorder()

◆ for_each_inorder() [1/2]

◆ for_each_inorder() [2/2]

◆ for_each_postorder() [1/2]

◆ for_each_postorder() [2/2]

◆ for_each_preorder() [1/2]

◆ for_each_preorder() [2/2]

◆ free_node()

◆ get()

◆ get_first()

◆ get_item()

◆ get_last()

◆ get_root()

◆ get_root_node()

◆ has()

◆ height()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_dup() [1/2]

◆ insert_dup() [2/2]

◆ internal_path_length()

◆ is_empty()

◆ join()