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

Dynamic set implemented using splay trees with rank support of type Splay_Tree_Rk<Key>. More...

#include <tpl_dynSetTree.H>

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

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

Classes
class	Iterator

Public Types
using	Base = DynSetTree< Key, Splay_Tree_Rk, 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
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 > requires Aleph::PredicateWith<Operation &, Type &>
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 > requires Aleph::PredicateWith<Operation &, Type &>
const Type *	find_ptr (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
	Const overload of find_ptr(Operation&).
template<class Operation > requires Aleph::PredicateWith<Operation &, Type &>
const Type *	find_ptr (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of find_ptr() const that accepts rvalues.
template<class Operation > requires Aleph::PredicateWith<Operation &, Type &>
Type *	find_ptr (Operation &&operation) noexcept(operation_is_noexcept< Operation >())
	Overload of find_ptr() that accepts rvalues.
template<class Operation > requires Aleph::PredicateWith<Operation &, const Type &>
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 > requires Aleph::PredicateWith<Operation &, const Type &>
size_t	find_index (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of find_index() that accepts rvalues.
template<class Operation > requires Aleph::PredicateWith<Operation &, Type &>
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 > requires Aleph::PredicateWith<Operation &, Type &>
std::tuple< bool, Type >	find_item (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
template<class Operation > requires Aleph::PredicateWith<Operation &, Type &>
std::tuple< bool, Type >	find_item (Operation &&operation) noexcept(operation_is_noexcept< Operation >())
	Overload of find_item() that accepts rvalues.
template<class Operation > requires Aleph::PredicateWith<Operation &, Type &>
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 > requires Aleph::PredicateWith<Operation &, Type &>
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 > requires Aleph::CallableWith<Operation &, const T &>
void	for_each (Operation &operation)
	Traverse all the container and performs an operation on each element.
template<class Operation > requires Aleph::CallableWith<Operation &, const T &>
void	for_each (Operation &operation) const
	Const overload of for_each(Operation&).
template<class Operation > requires Aleph::CallableWith<Operation &, const T &>
void	for_each (Operation &&operation) const
	Overload of for_each() const that accepts rvalues.
template<class Operation > requires Aleph::CallableWith<Operation &, const T &>
void	for_each (Operation &&operation)
	Overload of for_each() that accepts rvalues.
template<class Operation > requires Aleph::CallableWith<Operation &, const T &>
void	each (Operation &operation)
	Alias of for_each(Operation&).
template<class Operation > requires Aleph::CallableWith<Operation &, const T &>
void	each (Operation &operation) const
	Const alias of for_each(Operation&).
template<class Operation > requires Aleph::CallableWith<Operation &, const T &>
void	each (Operation &&operation) const
	Const alias of each() that accepts rvalues.
template<class Operation > requires Aleph::CallableWith<Operation &, const T &>
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 > requires Aleph::CallableWith<Operation &, T &>
void	mutable_for_each (Operation &operation)
	Apply a mutable operation to each element of the container.
template<class Operation > requires Aleph::CallableWith<Operation &, T &>
void	mutable_for_each (Operation &&operation)
template<class Operation > requires requires(const typename Aleph::concepts_detail::defer<Container, Operation>::type &c, Operation &op) { { c.traverse(op) } -> std::convertible_to<bool>; }
bool	all (Operation &operation) const
	Check if all the elements of the container satisfy a condition.
template<class Operation > requires requires(const typename Aleph::concepts_detail::defer<Container, Operation>::type &c, Operation &op) { { c.traverse(op) } -> std::convertible_to<bool>; }
bool	all (Operation &&operation) const
	Overload of all() that accepts rvalues.
template<class Operation > requires Aleph::PredicateWith<Operation &, const T &>
bool	exists (Operation &op) const
	Test for existence in the container of an element satisfying a criterion.
template<class Operation > requires Aleph::PredicateWith<Operation &, const T &>
bool	exists (Operation &&op) const
	Overload of exists() that accepts rvalues.
template<typename __T = T, class Operation = Aleph::Dft_Map_Op<T, __T>> requires requires(Aleph::DynList<__T> &l, Operation &op, const T &item) { l.append(op(item)); }
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>> requires requires(Aleph::DynList<__T> &l, Operation &op, const T &item) { l.append(op(item)); }
Aleph::DynList< __T >	maps (Operation &&op) const
	Overload of maps() that accepts rvalues.
Aleph::DynList< __T >	maps_if (Prop prop, Operation &op) const
Aleph::DynList< __T >	maps_if (Prop prop, Operation &&op) const
template<typename __T = T, class Operation = Aleph::Dft_Map_Op<T, __T>> requires requires(Aleph::DynList<__T> &l, Operation &op, const T &item) { l.append(op(item)); }
Aleph::DynList< __T >	map (Operation &op) const
	Synonym of maps().
template<typename __T = T, class Operation = Aleph::Dft_Map_Op<__T, __T>> requires requires(Aleph::DynList<__T> &l, Operation &op, const T &item) { l.append(op(item)); }
Aleph::DynList< __T >	map (Operation &&op) const
	Overload of map() that accepts rvalues.
Aleph::DynList< __T >	map_if (Prop prop, Operation &op) const
Aleph::DynList< __T >	map_if (Prop prop, Operation &&op) const
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>> requires requires(__T &acc, Op &op, const T &item) { acc = op(acc, item); }
__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>> requires requires(__T &acc, Op &op, const T &item) { acc = op(acc, item); }
__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>> requires requires(__T &acc, Op &op, const T &item) { acc = op(acc, item); }
__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>> requires requires(__T &acc, Op &op, const T &item) { acc = op(acc, item); }
__T	fold_left (const __T &init, Op &&op=Op()) const
	Overload of fold_left() that accepts rvalues.
template<class Operation > requires requires(T &acc, Operation &op, const T &item) { acc = op(acc, item); }
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 > requires requires(T &acc, Operation &op, const T &item) { acc = op(acc, item); }
T	fold (const T &init, Operation &&operation) const
	Overload of fold() that accepts rvalues.
template<class Operation > requires Aleph::PredicateWith<Operation &, const T &>
Aleph::DynList< T >	filter (Operation &operation) const
	Filter the elements of a container according to a matching criterion.
template<class Operation > requires Aleph::PredicateWith<Operation &, const T &>
Aleph::DynList< T >	filter (Operation &&operation) const
	Overload of filter() that accepts rvalues.
template<class Operation > requires Aleph::PredicateWith<Operation &, const T &>
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 > requires Aleph::PredicateWith<Operation &, const T &>
Aleph::DynList< const T * >	ptr_filter (Operation &&operation) const
	Overload of ptr_filter() that accepts rvalues.
template<class Operation > requires Aleph::PredicateWith<Operation &, const T &>
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 > requires Aleph::PredicateWith<Operation &, const T &>
Aleph::DynList< std::tuple< T, size_t > >	pfilter (Operation &&operation) const
	Overload of pfilter() that accepts rvalues.
template<class Operation > requires Aleph::PredicateWith<Operation &, const T &>
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &op) const
	Exclusive partition of container according to a filter criterion.
template<class Operation > requires Aleph::PredicateWith<Operation &, const T &>
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 > requires Aleph::PredicateWith<Operation &, const T &>
std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &op) const
	Exclusive partition of container according to a filter criterion.
template<class Operation > requires Aleph::PredicateWith<Operation &, const T &>
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.
Public Attributes inherited from FunctionalMethods< Container, T >
template<typename __T = T, class Prop , class Operation > requires (Aleph::DynList<__T> &l, Operation &op, const T &item)
	and { l.append(op(item))
	Conditional mapping of the elements of the container.
Related Symbols inherited from FunctionalMethods< Container, T >
	each
	each
	each

Detailed Description

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

Dynamic set implemented using splay trees with rank support of type Splay_Tree_Rk<Key>.

Splay trees are self-adjusting BSTs that move recently accessed elements to the root, providing amortized O(log n) for all operations. Frequently accessed elements have faster access times.

This extended version maintains subtree counts for O(log n) rank operations (select, position).

See also

DynSetTree DynMapTree Splay_Tree_Rk<Key> DynSetSplayTree

Definition at line 1531 of file tpl_dynSetTree.H.

Member Typedef Documentation

Base

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

using Aleph::DynSetSplayRkTree< Key, Compare >::Base = DynSetTree<Key, Splay_Tree_Rk, Compare>

Definition at line 1534 of file tpl_dynSetTree.H.

---

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

• tpl_dynSetTree.H