Aleph::DynSetAvlTree< Key, Compare > Class Template Reference

Dynamic set implemented using AVL binary search trees of type Avl_Tree<Key>. More...

#include <tpl_dynSetTree.H>

Inheritance diagram for Aleph::DynSetAvlTree< Key, Compare >:

Collaboration diagram for Aleph::DynSetAvlTree< Key, Compare >:

Public Types
using	Base = DynSetTree< Key, Avl_Tree, Compare >
Public Types inherited from Aleph::DynSetTree< Key, Tree, Compare >
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 >

Additional Inherited Members
Public Member Functions inherited from Aleph::DynSetTree< Key, Tree, Compare >
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.
Related Symbols inherited from FunctionalMethods< Container, T >
	each
	each
	each

Detailed Description

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

Dynamic set implemented using AVL binary search trees of type Avl_Tree<Key>.

See also

DynSetTree DynMapTree Avl_Tree<Key>

Definition at line 1548 of file tpl_dynSetTree.H.

Member Typedef Documentation

Base

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

using Aleph::DynSetAvlTree< Key, Compare >::Base = DynSetTree<Key, Avl_Tree, Compare>

Definition at line 1551 of file tpl_dynSetTree.H.

---

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

• tpl_dynSetTree.H