Aleph::DynSetTree< Key, Tree, Compare > Class Template Reference

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

#include <tpl_dynSetTree.H>

Inherits LocateFunctions< Container, Type >, FunctionalMethods< Container, T >, GenericItems< Container, T >, EqualToMethod< Container >, and StlAlephIterator< SetName >.

Inherited by Aleph::DynMapTree< Key, Type, Avl_Tree, Aleph::less< Key > >, Aleph::DynMapTree< Key, Type, BinTree, Aleph::less< Key > >, Aleph::DynMapTree< Key, Type, Rand_Tree, Aleph::less< Key > >, Aleph::DynMapTree< Key, Type, Rb_Tree, Aleph::less< Key > >, Aleph::DynMapTree< Key, Type, Splay_Tree, Aleph::less< Key > >, Aleph::DynMapTree< Key, Type, Treap, Aleph::less< Key > >, Aleph::DynMapTree< Key, Type, Treap_Rk, Aleph::less< Key > >, Aleph::DynMapTree< Key, Operation >, Aleph::DynMapTree< Key, ValueType >, Aleph::DynMapTree< void *, Flow_Type >, Aleph::DynMapTree< Aleph::Array< size_t >, double, Aleph::Avl_Tree, Grevlex_Order >, Aleph::DynMapTree< size_t, double >, Aleph::DynMapTree< Node *, Node *, Treap >, Aleph::DynMapTree< std::string, Huffman_Node *, Treap_Vtl >, Aleph::DynMapTree< std::string, BitArray, Treap_Vtl >, Aleph::DynMapTree< Node *, Node * >, Aleph::DynMapTree< Arc *, Arc * >, Aleph::DynMapTree< Node *, Distance_Type >, Aleph::DynMapTree< Node *, size_t >, Aleph::DynMapTree< Arc *, size_t >, Aleph::DynMapTree< Pair_Key, Arc * >, Aleph::DynMapTree< Node *, Cost_Type >, Aleph::DynMapTree< Node *, Arc * >, Aleph::DynMapTree< Event::EventId, TimeoutQueue::Event * >, Aleph::DynSetAvlTree< std::pair< int, int > >, Aleph::DynSetAvlTree< Relation_T::Pair, Relation_T::Cmp >, Aleph::DynSetRandTree< GT_Node * >, Aleph::Arcs_Index< GT, Compare, Tree, SA >, Aleph::DynMapTree< Key, Data, Tree, Compare >, Aleph::DynSetAvlRkTree< Key, Compare >, Aleph::DynSetAvlTree< Key, Compare >, Aleph::DynSetBinTree< Key, Compare >, Aleph::DynSetHtdRbRkTree< Key, Compare >, Aleph::DynSetHtdRbTree< Key, Compare >, Aleph::DynSetRandTree< Key, Compare >, Aleph::DynSetRbRkTree< Key, Compare >, Aleph::DynSetRbTree< Key, Compare >, Aleph::DynSetSplayRkTree< Key, Compare >, Aleph::DynSetSplayTree< Key, Compare >, Aleph::DynSetTdRbRkTree< Key, Compare >, Aleph::DynSetTdRbTree< Key, Compare >, Aleph::DynSetTreap< Key, Compare >, Aleph::DynSetTreapRk< Key, Compare >, and Aleph::Nodes_Index< GT, Compare, Tree, SN >.

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
void	clear ()
	Empties the container.
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
	Checks if a key exists in the set.
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 the 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 criterion.
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() const that accepts rvalues.
template<class Operation >
Type *	find_ptr (Operation &&operation) noexcept(operation_is_noexcept< Operation >())
	Overload of find_ptr() 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 criterion.
template<class Operation >
size_t	find_index (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of find_index() 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 criterion.
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 >())
	Overload of find_item() that accepts rvalues.
template<class Operation >
std::tuple< bool, Type >	find_item (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of find_item() const that accepts rvalues.
template<class Operation >
bool	contains_if (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Test if an item satisfying a criterion is present in the container.
bool	contains (const Type &item) const
	Test if an item is present in the container using equality.
Public Member Functions inherited from FunctionalMethods< Container, T >
template<typename ... Args>
void	emplace (Args &&... args)
	Appends a new element into the container by constructing it in-place with the given args.
template<typename ... Args>
void	emplace_end (Args &&... args)
template<typename ... Args>
void	emplace_ins (Args &&... args)
	Insert a new element into the container by constructing it in-place with the given args.
template<typename ... Args>
size_t	ninsert (Args ... args)
	Insert n variadic items.
template<typename ... Args>
size_t	nappend (Args ... args)
	Append n variadic items.
template<class Operation >
void	for_each (Operation &operation)
	Traverse all the container and performs an operation on each element.
template<class Operation >
void	for_each (Operation &operation) const
	Const overload of for_each(Operation&).
template<class Operation >
void	for_each (Operation &&operation) const
	Overload of for_each() const that accepts rvalues.
template<class Operation >
void	for_each (Operation &&operation)
	Overload of for_each() that accepts rvalues.
template<class Operation >
void	each (Operation &operation)
	Alias of for_each(Operation&).
template<class Operation >
void	each (Operation &operation) const
	Const alias of for_each(Operation&).
template<class Operation >
void	each (Operation &&operation) const
	Const alias of each() that accepts rvalues.
template<class Operation >
void	each (Operation &&operation)
	Alias of each() that accepts rvalues.
template<class Operation >
void	each (size_t pos, const size_t slice, Operation &operation) const
	Traverse the container starting at pos taking one item every slice, performing a mutable operation on each visited element.
template<class Operation >
void	each (const size_t pos, const size_t slice, Operation &&operation) const
template<class Operation >
void	mutable_for_each (Operation &operation)
	Apply a mutable operation to each element of the container.
template<class Operation >
void	mutable_for_each (Operation &&operation)
template<class Operation >
bool	all (Operation &operation) const
	Check if all the elements of the container satisfy a condition.
template<class Operation >
bool	all (Operation &&operation) const
	Overload of all() that accepts rvalues.
template<class Operation >
bool	exists (Operation &op) const
	Test for existence in the container of an element satisfying a criterion.
template<class Operation >
bool	exists (Operation &&op) const
	Overload of exists() that accepts rvalues.
template<typename __T = T, class Operation = Aleph::Dft_Map_Op<T, __T>>
Aleph::DynList< __T >	maps (Operation &op) const
	Map the elements of the container.
template<typename __T = T, class Operation = Aleph::Dft_Map_Op<__T, __T>>
Aleph::DynList< __T >	maps (Operation &&op) const
	Overload of maps() that accepts rvalues.
template<typename __T = T, class Prop , class Operation >
Aleph::DynList< __T >	maps_if (Prop prop, Operation &op) const
	Conditional mapping of the elements of the container.
template<typename __T = T, class Prop , class Operation >
Aleph::DynList< __T >	maps_if (Prop prop, Operation &&op) const
	Overload of maps_if() that accepts rvalues.
Aleph::DynList< T >	to_dynlist () const
	Convert container to DynList.
std::vector< T >	to_vector () const
	Convert container to std::vector.
template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	foldl (const __T &init, Op &op) const
	Fold the elements of the container to a specific result.
template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	foldl (const __T &init, Op &&op=Op()) const
	Overload of foldl() that accepts rvalues.
template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	fold_left (const __T &init, Op &op) const
	Alias for foldl with the same accumulator type.
template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	fold_left (const __T &init, Op &&op=Op()) const
	Overload of fold_left() that accepts rvalues.
template<class Operation >
T	fold (const T &init, Operation &operation) const
	Simplified version of foldl() where the folded type is the same type of elements stored in the container.
template<class Operation >
T	fold (const T &init, Operation &&operation) const
	Overload of fold() that accepts rvalues.
template<class Operation >
Aleph::DynList< T >	filter (Operation &operation) const
	Filter the elements of a container according to a matching criterion.
template<class Operation >
Aleph::DynList< T >	filter (Operation &&operation) const
	Overload of filter() that accepts rvalues.
template<class Operation >
Aleph::DynList< const T * >	ptr_filter (Operation &operation) const
	Filter the elements of a container according to a matching criterion and return a pointer to the matched items in the container.
template<class Operation >
Aleph::DynList< const T * >	ptr_filter (Operation &&operation) const
	Overload of ptr_filter() that accepts rvalues.
template<class Operation >
Aleph::DynList< std::tuple< T, size_t > >	pfilter (Operation &operation) const
	Filter the elements of a container according to a matching criterion and determine its positions respect to the traversal of container.
template<class Operation >
Aleph::DynList< std::tuple< T, size_t > >	pfilter (Operation &&operation) const
	Overload of pfilter() that accepts rvalues.
template<class Operation >
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &op) const
	Exclusive partition of container according to a filter criterion.
template<class Operation >
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &&op) const
	Overload of partition() that accepts rvalues.
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (size_t n) const
	Exclusive partition of container in the nth item.
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	split_half () const
	Split the container into two halves by alternating elements.
template<class Operation >
std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &op) const
	Exclusive partition of container according to a filter criterion.
template<class Operation >
std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &&op) const
	Overload of tpartition() that accepts rvalues.
size_t	length () const noexcept
	Count the number of elements of a container.
Aleph::DynList< T >	rev () const
	Return a list with the elements of container in reverse order respect to its traversal order.
Aleph::DynList< T >	take (const size_t n) const
	Return a list with the first n elements seen in the container during its traversal.
Aleph::DynList< T >	take (size_t i, const size_t j, const size_t step=1) const
	Return a list with elements seen in the container between i and j position respect to its traversal.
Aleph::DynList< T >	drop (const size_t n) const
	Drop the first n elements seen in the container during its traversal.
void	mutable_drop (const size_t n)
	Drop the first n elements seen from container.
Public Member Functions inherited from GenericItems< Container, T >
Aleph::DynList< T >	items () const
	Return a list of all the elements of a container sorted by traversal order.
Aleph::DynList< T >	keys () const
Public Member Functions inherited from 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>>
requires StrictWeakOrder<Compare, Key> && BSTPolicy<Tree<Key, Compare>, 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 << " ";

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 270 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 491 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 493 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 280 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 489 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 282 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 511 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 518 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 527 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 536 of file tpl_dynSetTree.H.

References Aleph::copyRec(), Aleph::divide_and_conquer_partition_dp(), 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 551 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 551 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 551 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 553 of file tpl_dynSetTree.H.

References Aleph::divide_and_conquer_partition_dp(), 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 620 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 714 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 626 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 785 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 693 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 1149 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 466 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 473 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 682 of file tpl_dynSetTree.H.

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

Referenced by Aleph::hopcroft_karp_matching(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::insert_arc(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::insert_node(), main(), 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 687 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 1032 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 1040 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 454 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 447 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 440 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 433 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 413 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 406 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 392 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 377 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 399 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 385 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 427 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 420 of file tpl_dynSetTree.H.

References l, and r.

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

clear()

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

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

inline

Empties the container.

Exceptions

none

See also

empty()

Definition at line 584 of file tpl_dynSetTree.H.

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

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

Checks if a key exists in the set.

Parameters

[in]

key

key to search for.

Returns

true if key is present, false otherwise.

Exceptions

none

Definition at line 907 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(), Aleph::k_shortest_paths_detail::Filtered_Show_Arc< GT, SA >::operator()(), Aleph::k_shortest_paths_detail::shortest_path_filtered(), 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 772 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 778 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 850 of file tpl_dynSetTree.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::DynSetTree< Key, Tree, Compare >::free_node(), 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 560 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::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_adjacency(), 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::DynSetTree< Key, Tree, Compare >::clear(), Aleph::AHMapping< Key, ValueType >::clear(), Aleph::Huffman_Encoder_Engine::clear_build_state(), Aleph::Network_Simplex< Net >::init_structures(), Aleph::DynSetTree< Key, Tree, Compare >::operator=(), Aleph::DynSetTree< Key, Tree, Compare >::operator=(), reset_huffman_btreepic_state(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::sort_arcs(), and test_DynSet().

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 891 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 926 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(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::remove_from_graph(), and Aleph::validate_nonplanar_certificate().

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 950 of file tpl_dynSetTree.H.

References ah_domain_error_if_constexpr, Aleph::DynSetTree< Key, Tree, Compare >::call_find_position(), Aleph::divide_and_conquer_partition_dp(), 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 1072 of file tpl_dynSetTree.H.

References Aleph::divide_and_conquer_partition_dp(), 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 1271 of file tpl_dynSetTree.H.

References Aleph::divide_and_conquer_partition_dp().

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 1254 of file tpl_dynSetTree.H.

References Aleph::divide_and_conquer_partition_dp(), 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 1318 of file tpl_dynSetTree.H.

References Aleph::divide_and_conquer_partition_dp().

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 1301 of file tpl_dynSetTree.H.

References Aleph::divide_and_conquer_partition_dp(), 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 1224 of file tpl_dynSetTree.H.

References Aleph::divide_and_conquer_partition_dp().

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 1207 of file tpl_dynSetTree.H.

References Aleph::divide_and_conquer_partition_dp(), 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 480 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 >::__insert(), Aleph::DynSetTree< Key, Tree, Compare >::__insert_dup(), Aleph::DynSetTree< Key, Tree, Compare >::__search_or_insert(), Aleph::DynSetTree< Key, Tree, Compare >::del(), Aleph::DynSetTree< Key, Tree, Compare >::insert(), Aleph::DynSetTree< Key, Tree, Compare >::insert(), Aleph::DynSetTree< Key, Tree, Compare >::remove(), and Aleph::DynSetTree< Key, Tree, Compare >::remove_pos().

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 1017 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 1001 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 1064 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 1014 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 1056 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 1054 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 896 of file tpl_dynSetTree.H.

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

Referenced by insert_n_random_items_in_set(), TEST(), TEST(), TEST(), test_DynSet(), 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 1067 of file tpl_dynSetTree.H.

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

Referenced by test(), and 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 656 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::__insert(), Aleph::DynSetTree< Key, Tree, Compare >::alloc_node(), Aleph::divide_and_conquer_partition_dp(), and Aleph::DynSetTree< Key, Tree, Compare >::free_node().

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::append(), Aleph::DynMapTree< Key, Data, Tree, Compare >::append(), Aleph::DynMapTree< Key, Data, Tree, Compare >::append(), Aleph::DynSetTree< Key, Tree, Compare >::append(), Aleph::DynMapTree< Key, Data, Tree, Compare >::append(), Aleph::DynMapTree< Key, Data, Tree, Compare >::append(), Aleph::MonotonePolygonTriangulation::build_faces_from_diagonals(), count_distinct_colors(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::create_nodes_and_initialize_arc_index(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::create_nodes_and_initialize_arc_index(), create_table(), Aleph::MonotonePolygonTriangulation::decompose_to_monotone_faces(), demonstrate_basic_operations(), demonstrate_functional_features(), demonstrate_ranked_operations(), demonstrate_tree_types(), Aleph::Net_Graph< NodeT, ArcT >::disconnect_arc(), Aleph::dsatur_coloring(), Aleph::greedy_coloring(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::init(), Aleph::Arcs_Index< GT, Compare, Tree, SA >::init(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph(), Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph(), Aleph::Arcs_Index< GT, Compare, Tree, SA >::insert_in_graph(), insert_n_random_items_in_set(), main(), Aleph::min_cut(), Aleph::nonplanar_certificate_to_dot(), Aleph::nonplanar_certificate_to_gexf(), Aleph::nonplanar_certificate_to_graphml(), Aleph::Init_P< GT >::operator()(), Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::post_dominance_frontiers(), Aleph::DynSetTree< Key, Tree, Compare >::put(), Aleph::DynSetTree< Key, Tree, Compare >::put(), Aleph::Net_Graph< NodeT, ArcT >::register_node(), Aleph::Net_Graph< NodeT, ArcT >::remove_arc(), Aleph::set_unify(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), test_DynSet(), Aleph::to_DynSetTree(), Aleph::GeomBowyerWatsonUtils::toggle_edge(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::update_parity_after_arc_insertion(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::update_parity_after_arc_insertion(), Aleph::vector_to_DynSetTree(), verify_bipartition(), Aleph::welsh_powell_coloring(), and Aleph::yen_k_shortest_paths().

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 669 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::__insert(), Aleph::DynSetTree< Key, Tree, Compare >::alloc_node(), Aleph::divide_and_conquer_partition_dp(), and Aleph::DynSetTree< Key, Tree, Compare >::free_node().

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 801 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 806 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 1049 of file tpl_dynSetTree.H.

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

Referenced by test(), and 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 1023 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(), 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 1354 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 1005 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 992 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 1134 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 586 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 592 of file tpl_dynSetTree.H.

References Aleph::copyRec(), Aleph::divide_and_conquer_partition_dp(), Aleph::DynSetTree< Key, Tree, Compare >::empty(), 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 608 of file tpl_dynSetTree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::DynSetTree< Key, Tree, Compare >::empty(), 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 1144 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 1139 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 1090 of file tpl_dynSetTree.H.

References ah_domain_error_if_constexpr, Aleph::DynSetTree< Key, Tree, Compare >::call_position(), Aleph::divide_and_conquer_partition_dp(), 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 811 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 816 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 828 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(), test_DynSet(), Aleph::GeomBowyerWatsonUtils::toggle_edge(), 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 870 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::divide_and_conquer_partition_dp(), Aleph::DynSetTree< Key, Tree, Compare >::free_node(), KEY, 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 980 of file tpl_dynSetTree.H.

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

Referenced by Aleph::MonotonePolygonTriangulation::build_faces_from_diagonals(), 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(), test_DynSet(), Aleph::GeomBowyerWatsonUtils::toggle_edge(), 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 748 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 753 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 1104 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(), Aleph::divide_and_conquer_partition_dp(), 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 1119 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(), Aleph::divide_and_conquer_partition_dp(), 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 1020 of file tpl_dynSetTree.H.

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

Referenced by adjust_nodes(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::build_reverse_mappings(), count_distinct_colors(), demo_tree_backends(), demo_word_frequency(), Aleph::dsatur_coloring(), Aleph::Net_Graph< NodeT, ArcT >::is_single_sink(), Aleph::Net_Graph< NodeT, ArcT >::is_single_source(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::make_eulerian(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::make_eulerian(), Aleph::Net_Graph< NodeT, ArcT >::make_super_sink(), Aleph::Net_Graph< NodeT, ArcT >::make_super_source(), Aleph::min_cut(), Aleph::planar_dual_metadata(), Aleph::settree_to_Array(), Aleph::settree_to_vector(), AHDispatcher< Key, Operation >::size(), Aleph::AHMapping< Key, ValueType >::size(), Aleph::solve_circulation(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), test(), test_DynSet(), TEST_F(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), Aleph::Net_Graph< NodeT, ArcT >::unmake_super_sink(), Aleph::Net_Graph< NodeT, ArcT >::unmake_super_source(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::verify_tables(), and Aleph::welsh_powell_coloring().

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 1395 of file tpl_dynSetTree.H.

References Aleph::compute_cardinality_rec(), Aleph::divide_and_conquer_partition_dp(), l, Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, r, 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 1449 of file tpl_dynSetTree.H.

References Aleph::compute_cardinality_rec(), l, Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, r, 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 1420 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(), Aleph::divide_and_conquer_partition_dp(), l, Aleph::DynSetTree< Key, Tree, Compare >::num_nodes, r, and Aleph::DynSetTree< Key, Tree, Compare >::tree.

Referenced by TEST(), 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 500 of file tpl_dynSetTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::arena_allocator, Aleph::divide_and_conquer_partition_dp(), 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 1507 of file tpl_dynSetTree.H.

References Aleph::divide_and_conquer_partition_dp().

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 1522 of file tpl_dynSetTree.H.

References Aleph::divide_and_conquer_partition_dp().

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)

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 1498 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 1513 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 1026 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 1154 of file tpl_dynSetTree.H.

References Aleph::and, Aleph::check_bst(), 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 464 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 460 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 463 of file tpl_dynSetTree.H.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::DynSetTree(), Aleph::DynSetTree< Key, Tree, Compare >::__contains_or_insert(), Aleph::DynSetTree< Key, Tree, Compare >::__insert(), Aleph::DynSetTree< Key, Tree, Compare >::__insert_dup(), Aleph::DynSetTree< Key, Tree, Compare >::__search_or_insert(), Aleph::DynSetTree< Key, Tree, Compare >::del(), Aleph::DynSetTree< Key, Tree, Compare >::empty(), Aleph::DynSetTree< Key, Tree, Compare >::find_position(), Aleph::DynSetTree< Key, Tree, Compare >::get_root(), Aleph::DynSetTree< Key, Tree, Compare >::is_empty(), Aleph::DynSetTree< Key, Tree, Compare >::join(), Aleph::DynSetTree< Key, Tree, Compare >::join_dup(), Aleph::DynSetTree< Key, Tree, Compare >::max(), Aleph::DynSetTree< Key, Tree, Compare >::min(), Aleph::DynSetTree< Key, Tree, Compare >::operator=(), Aleph::DynSetTree< Key, Tree, Compare >::remove(), Aleph::DynSetTree< Key, Tree, Compare >::remove_pos(), Aleph::DynSetTree< Key, Tree, Compare >::select(), Aleph::DynSetTree< Key, Tree, Compare >::select(), Aleph::DynSetTree< Key, Tree, Compare >::size(), Aleph::DynSetTree< Key, Tree, Compare >::split_key(), Aleph::DynSetTree< Key, Tree, Compare >::split_key_dup(), Aleph::DynSetTree< Key, Tree, Compare >::split_pos(), and Aleph::DynSetTree< Key, Tree, Compare >::swap().

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 462 of file tpl_dynSetTree.H.

Referenced by Aleph::DynSetTree< Key, Tree, Compare >::DynSetTree(), Aleph::DynSetTree< Key, Tree, Compare >::__contains_or_insert(), Aleph::DynSetTree< Key, Tree, Compare >::__insert(), Aleph::DynSetTree< Key, Tree, Compare >::__insert_dup(), Aleph::DynSetTree< Key, Tree, Compare >::__search_or_insert(), Aleph::DynSetTree< Key, Tree, Compare >::del(), Aleph::DynSetTree< Key, Tree, Compare >::empty(), Aleph::DynSetTree< Key, Tree, Compare >::find(), Aleph::DynSetTree< Key, Tree, Compare >::find_position(), Aleph::DynSetTree< Key, Tree, Compare >::for_each_in_preorder(), Aleph::DynSetTree< Key, Tree, Compare >::for_each_inorder(), Aleph::DynSetTree< Key, Tree, Compare >::for_each_postorder(), Aleph::DynSetTree< Key, Tree, Compare >::for_each_preorder(), Aleph::DynSetTree< Key, Tree, Compare >::get_root(), Aleph::DynSetTree< Key, Tree, Compare >::get_root_node(), Aleph::DynSetTree< Key, Tree, Compare >::height(), Aleph::DynSetTree< Key, Tree, Compare >::internal_path_length(), Aleph::DynSetTree< Key, Tree, Compare >::join(), Aleph::DynSetTree< Key, Tree, Compare >::join_dup(), Aleph::DynSetTree< Key, Tree, Compare >::max(), Aleph::DynSetTree< Key, Tree, Compare >::min(), Aleph::DynSetTree< Key, Tree, Compare >::operator=(), Aleph::DynSetTree< Key, Tree, Compare >::position(), Aleph::DynSetTree< Key, Tree, Compare >::remove(), Aleph::DynSetTree< Key, Tree, Compare >::remove_pos(), Aleph::DynSetTree< Key, Tree, Compare >::search(), Aleph::DynSetTree< Key, Tree, Compare >::select(), Aleph::DynSetTree< Key, Tree, Compare >::select(), Aleph::DynSetTree< Key, Tree, Compare >::split_key(), Aleph::DynSetTree< Key, Tree, Compare >::split_key_dup(), Aleph::DynSetTree< Key, Tree, Compare >::split_pos(), Aleph::DynSetTree< Key, Tree, Compare >::swap(), Aleph::DynSetTree< Key, Tree, Compare >::traverse(), Aleph::DynSetTree< Key, Tree, Compare >::traverse(), and Aleph::DynSetTree< Key, Tree, Compare >::verify().

---

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

• tpl_dynSetTree.H