#include <tpl_dynSetTree.H>

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

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

Public Types
using	Node = typename Tree< Key, Compare >::Node

using	Tree_Type = Tree< Key, Compare >

typedef DynSetTree	Set_Type

typedef Key	Item_Type

typedef Key	Key_Type

using	iterator = StlIterator< SetName >

using	const_iterator = StlConstIterator< SetName >

Public Member Functions
void	swap (DynSetTree &dset)

	DynSetTree (Compare cmp=Compare())
	Instancia un conjunto dinÃ¡mico.

	DynSetTree (const DynSetTree &srcTree)
	Instancia un conjunto dinÃ¡mico copia de srcTree.

	Special_Ctors (DynSetTree, Key)

	DynSetTree (DynSetTree &&srcTree)

void	empty ()
	Elimina todos los elementos del conjunto.

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

DynSetTree &	operator= (const DynSetTree &srcTree)
	Asigna a this el conjunto dinÃ¡mico srcTree.

DynSetTree &	operator= (DynSetTree &&srcTree)
	Asigna a this el conjunto dinÃ¡mico srcTree.

virtual	~DynSetTree ()
	Destructor; todos los elementos son liberados.

Key *	insert (const Key &key)

Key *	insert (Key &&key)

Key *	append (const Key &key)

Key *	append (Key &&key)

Key *	search_or_insert (const Key &key)

Key *	search_or_insert (Key &&key)

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

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)

Key	del (const Key &key)

Key	remove_pos (const size_t i)

bool	exist (const Key &key) const
	Retorna true si key pertenece al conjunto dinÃ¡mico.

bool	has (const Key &key) const

bool	contains (const Key &key) const

Key &	find (const Key &key) const

std::pair< int, Key * >	find_position (const Key &key) const

Key *	search (const Key &key) const

const Key &	min () const

const Key &	get_first () const

const Key &	max () const

const Key &	get_last () const

const Key &	get () const
	SinÃ³nimo de max.

const size_t &	size () const
	Retorna la cardinalidad del conjunto.

bool	is_empty () const
	Retorna true si el conjunto estÃ¡ vacÃo.

size_t	internal_path_length () const

Node *	get_root_node () const

const Key &	get_root () const

const Key &	get_item () const
	Retorna un elemento cualquiera del conjunto.

size_t	height () const
	Calcula y retorna la altura del Ã¡rbol binario de bÃºsqueda.

template<class Op >
void	for_each_in_preorder (void(visitFct)(Node , int, int))

long	position (const Key &key) const

Key &	select (const size_t &i)

const Key &	select (const size_t &i) const

Key &	operator() (const size_t &i)

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

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

Key &	access (const size_t &i)

bool	verify ()

template<class Key_Op >
void	for_each_preorder (Key_Op &key_op) const

template<class Key_Op >
void	for_each_preorder (Key_Op &&key_op=Key_Op()) const

template<class Key_Op >
void	for_each_inorder (Key_Op &key_op) const

template<class Key_Op >
void	for_each_inorder (Key_Op &&key_op=Key_Op()) const

template<class Key_Op >
void	for_each_postorder (Key_Op &key_op)

template<class Key_Op >
void	for_each_postorder (Key_Op &&key_op=Key_Op())

DynSetTree &	join (DynSetTree &t, DynSetTree &dup)

DynSetTree &	join (DynSetTree &t, DynSetTree &&dup=DynSetTree())

DynSetTree &	join_dup (DynSetTree &t)

bool	split_key (const Key &key, DynSetTree &l, DynSetTree &r)

void	split_pos (const size_t pos, DynSetTree &l, DynSetTree &r)

void	split_key_dup (const Key &key, DynSetTree &l, DynSetTree &r)

template<class Operation >
bool	traverse (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

auto	get_it () const

auto	get_it (size_t pos) const

auto	get_itor () const

Key &	nth_ne (const size_t n) noexcept

const Key &	nth_ne (const size_t n) const noexcept

Key &	nth (const size_t n)

const Key &	nth (const size_t n) const

Key *	find_ptr (Operation &operation) noexcept(noexcept(operation))

const Key *	find_ptr (Operation &operation) const noexcept(noexcept(operation))

const Key *	find_ptr (Operation &&operation) const noexcept(noexcept(operation))

Key *	find_ptr (Operation &&operation) noexcept(noexcept(operation))

size_t	find_index (Operation &operation) const noexcept(noexcept(operation))

size_t	find_index (Operation &&operation) const noexcept(noexcept(operation))

std::tuple< bool, Key >	find_item (Operation &operation) noexcept(noexcept(operation))

std::tuple< bool, Key >	find_item (Operation &operation) const noexcept(noexcept(operation))

std::tuple< bool, Key >	find_item (Operation &&operation) noexcept(noexcept(operation))

std::tuple< bool, Key >	find_item (Operation &&operation) const noexcept(noexcept(operation))

void	emplace (Args &&... args)

void	emplace_end (Args &&... args)

void	emplace_ins (Args &&... args)

size_t	ninsert (Args ... args)

size_t	nappend (Args ... args)

void	for_each (Operation &operation) noexcept(noexcept(operation))

void	for_each (Operation &operation) const noexcept(noexcept(operation))

void	for_each (Operation &&operation) const noexcept(noexcept(operation))

void	for_each (Operation &&operation) noexcept(noexcept(operation))

void	each (Operation &operation) noexcept(noexcept(operation))

void	each (Operation &operation) const noexcept(noexcept(operation))

void	each (Operation &&operation) const noexcept(noexcept(operation))

void	each (Operation &&operation) noexcept(noexcept(operation))

void	each (size_t pos, size_t slice, Operation &operation) const

void	each (size_t pos, size_t slice, Operation &&operation) const

void	mutable_for_each (Operation &operation) noexcept(noexcept(operation))

void	mutable_for_each (Operation &&operation) noexcept(noexcept(operation))

bool	all (Operation &operation) const noexcept(noexcept(operation))

bool	all (Operation &&operation) const noexcept(noexcept(operation))

bool	exists (Operation &op) const noexcept(noexcept(op))

bool	exists (Operation &&op) const noexcept(noexcept(op))

DynList< __T >	maps (Operation &op) const

DynList< __T >	maps (Operation &&op) const

DynList< __T >	maps_if (Prop prop, Operation &op) const

DynList< __T >	maps_if (Prop prop, Operation &&op) const

DynList< Key >	to_dynlist () const

__T	foldl (const __T &init, Op &op) const noexcept(noexcept(op))

__T	foldl (const __T &init, Op &&op=Op()) const noexcept(noexcept(op))

Key	fold (const Key &init, Operation &operation) const noexcept(noexcept(operation))

Key	fold (const Key &init, Operation &&operation) const noexcept(noexcept(operation))

DynList< Key >	filter (Operation &operation) const

DynList< Key >	filter (Operation &&operation) const

DynList< const Key *>	ptr_filter (Operation &operation) const

DynList< const Key *>	ptr_filter (Operation &&operation) const

DynList< std::tuple< Key, size_t > >	pfilter (Operation &operation) const

DynList< std::tuple< Key, size_t > >	pfilter (Operation &&operation) const

std::pair< DynList< Key >, DynList< Key > >	partition (Operation &op) const

std::pair< DynList< Key >, DynList< Key > >	partition (Operation &&op) const

std::pair< DynList< Key >, DynList< Key > >	partition (size_t n) const

std::tuple< DynList< Key >, DynList< Key > >	tpartition (Operation &op) const

std::tuple< DynList< Key >, DynList< Key > >	tpartition (Operation &&op) const

size_t	length () const noexcept

DynList< Key >	rev () const

DynList< Key >	take (const size_t n) const

DynList< Key >	take (size_t i, size_t j, size_t step=1) const

DynList< Key >	drop (const size_t n) const

void	mutable_drop (size_t n)

DynList< T >	items () const

DynList< T >	keys () const

bool	equal_to (const DynSetTree< Key, Tree, Compare > &r) const noexcept

bool	operator== (const DynSetTree< Key, Tree, Compare > &r) const noexcept

bool	operator!= (const DynSetTree< Key, Tree, Compare > &r) const noexcept
	Negation of are_equal()

iterator	begin () noexcept

const_iterator	begin () const noexcept

iterator	end () noexcept

const_iterator	end () const noexcept

const_iterator	cbegin () const noexcept

const_iterator	cbegin () noexcept

const_iterator	cend () const noexcept

const_iterator	cend () noexcept

Detailed Description

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

Conjunto dinÃ¡mico de elementos de tipo genÃ©rico T implementado mediante una clase de Ã¡rboles binarios.

DynSetTree define una tabla de elementos de tipo Key que estÃ¡ instrumentada con la clase de Ã¡rbol binario de bÃºsqueda Tree<Key> y ordenado mediante el criterio Compare()().

Member Typedef Documentation

◆ 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

Tipo de nodo binario empleado por el Ã¡rbol binario de bÃºsqueda interno.

Member Function Documentation

◆ all() [1/2]

bool Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::all ( Operation & operation ) const

inlinenoexceptinherited

Check if all the elements of container satisfy a condition.

all(operation) checks if for each element item of container operation(item) returns true.

This method has complexity $O(n)$ in average and worst case.

Parameters

[in] operation to be used as condition

Returns: true if all the elements satisfy the criteria: false otherwise.

Exceptions

anything that could throw operation

◆ all() [2/2]

bool Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::all ( Operation && operation ) const

inlinenoexceptinherited

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

◆ 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

◆ drop()

DynList<Key > Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::drop ( const size_t n ) const

inlineinherited

Drop the first n elements seen in the container during its traversal.

The complexity of this method is $O(N)$ where N always is the number of elements of container.

Returns: A DynList<T> having the remainder elements according to traversal order.

Exceptions

bad_alloc if there is no enough memory or out_of_range if n is greater or equal than N (the number of elements in the container).

◆ each() [1/6]

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::each ( Operation & operation )

inlinenoexceptinherited

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

◆ each() [2/6]

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::each ( Operation & operation ) const

inlinenoexceptinherited

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

◆ each() [3/6]

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::each ( Operation && operation ) const

inlinenoexceptinherited

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

◆ each() [4/6]

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::each ( Operation && operation )

inlinenoexceptinherited

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

◆ each() [5/6]

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::each	(	size_t	pos,
		size_t	slice,
		Operation &	operation
	)		const

inlineinherited

Traverse all the container and performs a mutable operation on each element.

mutable_for_each(operation) traverses the container and on each element item is performed operation(item).

operation could have the following signature:

void operation(T & item)

Be very careful with the fact that this method allows to modify the elements themselves, what could badly alter the internal state of container. This would be the case for heaps, binary trees and hash tables.

Parameters

[in] <tt>operation</tt> to be done on each element.

Returns: an reference to this

Exceptions

anything that can throw operation

◆ each() [6/6]

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::each	(	size_t	pos,
		size_t	slice,
		Operation &&	operation
	)		const

inlineinherited

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

◆ emplace()

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::emplace ( Args &&... args )

inlineinherited

Appends a new element into the container by constructing it in-place with the given args.

emplace(args) tries to match a constructor T(args). If this exists, then this is constructed in-place and directly forwarded to the method append() of container. If all on the container and T` is adequately done, then the object is constructed once time, successively forwarded and at its target place in the container is moved, avoiding thus unnecessary copies.

Note: The semantic of append depends of container. In general, this has some sense for lists and arrays and it means insertion at the end of sequence. On other type of container append() is equivalent to insert().

Parameters

[in] args variadic arguments list

Exceptions

bad_alloc if there is no enough memory

◆ emplace_end()

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::emplace_end ( Args &&... args )

inlineinherited

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

◆ emplace_ins()

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::emplace_ins ( Args &&... args )

inlineinherited

Insert a new element into the container by constructing it in-place with the given args.

emplace_ins(args) tries to match a constructor T(args). If this exists, then this is constructed in-place and directly forwarded to the method insert() of container. If all on the container and T` is adequately done, then the object is constructed once time, successively forwarded and finally, at its target place in the container, is moved, avoiding thus unnecessary copies.

Note: The semantic of insert() depends of container. In general, this has some sense for lists and arrays and it means insertion at the beginning of sequence. On other type of container append() is equivalent to insert().

Parameters

[in] args variadic arguments list

Exceptions

bad_alloc if there is no enough memory

◆ equal_to()

bool Aleph::EqualToMethod< DynSetTree< Key, Tree, Compare > >::equal_to ( const DynSetTree< Key, Tree, Compare > & r ) const

inlinenoexceptinherited

Test if elements of this are exactly contained in another container.

This method serves for testing if two containers contain the same elements. First, the container sizes are tested for equality. If they have the same size, then the testing is done by traversing this. Each seen element is searched in the another container with the method search(). So the container r must export the search() method, which frequently is the case for containers oriented to fast retrieval.

Warning: On some container, concretely DynList, the size is computed, not retrieved. So take in account this fact.

Parameters

[in] r container on which the searches will be performed.

Returns: true if the container have the same size and all the elements of this are present in r

◆ exists() [1/2]

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

inlinenoexceptinherited

Test for existence in the container of an element satisfying a criteria.

exists(op) returns true if it exists any element item in container for which op(item) return true.

This method has complexity $O(n)$ in average and worst case.

Parameters

[in] op operation for testing existence

Returns: true if it exists an item for which op return true; false otherwise.

Exceptions

anything that could throw op

◆ exists() [2/2]

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

inlinenoexceptinherited

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

◆ filter() [1/2]

DynList<Key > Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::filter ( Operation & operation ) const

inlineinherited

Filter the elements of a container according to a matching criteria.

This method builds a dynamic list with copies of items of container matching a criteria defined by operation, which should have the following signature:

bool operation(const T & item)

If operation return true then item matches the criteria; otherwise, operation must return false.

For example, if the container has integer, the the following code snippet would return a list containing the items greater than 100:

c.filter([] (auto item) { return item > 100; });

Parameters

[in] operation defining the flter criteria

Returns: a DynList<T> with the matched elements.

Exceptions

anything that could throw operation or bad_alloc if there is no enough memory

◆ filter() [2/2]

DynList<Key > Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::filter ( Operation && operation ) const

inlineinherited

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

◆ 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

Retorna una referencia modificable a un elemento dentro del conjunto.

find(key) busca la clave key en el conjunto y retorna una referencia modificable hacia el valor contenido en el conjunto.

Parameters

[in] key clave a buscar.

Returns: referencia modificable a la clave key contenida dentro del conjunto.

Exceptions

domain_error si key no estÃ¡ dentro del conjunto.

Note: TÃ©ngase sumo cuidado con alterar el orden de bÃºsqueda, pues la referencia es modificable.

Here is the caller graph for this function:

◆ find_index() [1/2]

size_t Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::find_index ( Operation & operation ) const

inlinenoexceptinherited

Find the position of an item in the container according to a searching criteria.

find_index(operation) traverses the container and on each item perform operation(item). If the result of operation is true, then the traversal is stopped and the position of the current item (which mathes operation) is returned.

operation must have the following signature:

bool operation(const typename Container::Item_Type & item)

Warning: Frequent use of this method will definitively degrade the performance. Try not to use this method inside loops. In general, if you falls in this situation, the consider your design and use a faster approach.

Parameters

[in] <tt>operation</tt> to be performed on each item for matching a searching criteria.

Returns: the last seen position. If the item is not found, then the number of items is returned.

◆ find_index() [2/2]

size_t Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::find_index ( Operation && operation ) const

inlinenoexceptinherited

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

◆ find_item() [1/4]

std::tuple<bool, Key > Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::find_item ( Operation & operation )

inlinenoexceptinherited

Safe sequential searching of an item matching a criteria.

find_item(operation) traverses the container and on each item perform operation(item). If the result of operation is true, then the traversal is stopped and duple containg a copy of found item is returned.

The method is said safe because returns a copy of item.

operation must have the following signature:

bool operation(const typename Container::Item_Type & item)

Parameters

[in] <tt>operation</tt> to be used as searching criteria

Returns: a duple tuple<bool, Type>. The first field indicates if the item was found and the second contains a copy of found item. If no item is found, then the first field is false and the second is the result of default constructor on the type stored in the container.

◆ find_item() [2/4]

std::tuple<bool, Key > Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::find_item ( Operation & operation ) const

inlinenoexceptinherited

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

◆ find_item() [3/4]

std::tuple<bool, Key > Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::find_item ( Operation && operation )

inlinenoexceptinherited

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

◆ find_item() [4/4]

std::tuple<bool, Key > Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::find_item ( Operation && operation ) const

inlinenoexceptinherited

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

◆ find_position()

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

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

inline

Retorna la posiciÃ³n infija (ordenada) de la clave key o lo que seria su posiciÃ³n de pertenecer al Ã¡rbol.

find_position(key) busca en el Ã¡rbol extendido la clave key (lo cual toma tiempo $O(\lg n)$ ) y retorna la posiciÃ³n infija del nodo que contiene la clave.

Parameters

[in] key clave a buscar y a determinar posiciÃ³n infija.

Returns: posiciÃ³n infija de la clave key dentro del conjunto ordenado si Ã©sta se encuentra o, de lo contrario, la posiciÃ³n donde se encontrarÃa de pertenecer al Ã¡rbol.

Warning: SÃ³lo funciona si el Ã¡rbol maneja rangos.

◆ find_ptr() [1/4]

Key * Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::find_ptr ( Operation & operation )

inlinenoexceptinherited

Find a pointer to an item in the container according to a searching criteria.

find_ptr(operation) traverses the container and on each item perform operation(item). If the result of operation is true, then the traversal is stopped and a pointer to the current item (which mathes operation) is returned.

operation must have the following signature:

bool operation(const typename Container::Item_Type & item)

Warning: Frequent use of this method will definitively degrade the performance. Try not to use this method inside loops. In general, if you falls in thie situation, the consider your design and to use an faster approach.

Parameters

[in] <tt>operation</tt> to be performed on each item for matching a searching criteria.

Returns: a valid pointer to an item if this was found or nullptr otherwise.

◆ find_ptr() [2/4]

const Key * Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::find_ptr ( Operation & operation ) const

inlinenoexceptinherited

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

◆ find_ptr() [3/4]

const Key * Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::find_ptr ( Operation && operation ) const

inlinenoexceptinherited

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

◆ find_ptr() [4/4]

Key * Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::find_ptr ( Operation && operation )

inlinenoexceptinherited

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

◆ fold() [1/2]

Key Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::fold	(	const Key &	init,
		Operation &	operation
	)		const

inlinenoexceptinherited

Simplified version of foldl() where the folded type is the same type of elements stored in the container.

See also: foldl(const __T & init, Op & op)

◆ fold() [2/2]

Key Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::fold	(	const Key &	init,
		Operation &&	operation
	)		const

inlinenoexceptinherited

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

◆ foldl() [1/2]

__T Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::foldl	(	const __T &	init,
		Op &	op
	)		const

inlinenoexceptinherited

Fold the elements of the container to a specific result.

foldl(init, op) set an internal variable acc of type __T to init value. Then it traverses the container and on each item it performs:

acc = op(acc, op(acc, item);

So acc serves as a sort of accumulator.

op should have the following signature:

__T op(__T acc, const T & item);

Since foldl is overloaded with several operation structures, there is a certain flexibility with the parameter qualifiers. You could, for example, to declare acc and/or item by value.

The method is a template. The first template parameter __T specifies the final folded type. By default, this type is T (the type of elements stored in the container). The second parameter is the operation. If the folded type is the same than T (the type of item stored), the you can simply write a foldl(). For example, if the container stores integer, in order to determine the maximum of all elements you could do:

c.foldl(std::numeric_limits<int>::min(), [] (int acc, int item)
  {
    return std::min(acc, item);
  });

When the folded type is different than T, then you must specify the folded type as template parameter. For example, if you want to compute the sum of inversed elements, the you could do it as follows:

c.template foldl<double>(0, [] (double acc, int item)
  {
    return acu + 1.0/item;
  });

Parameters

[in]	init	initial value of folded value (or accumulator).
[in]	op	operation to be performed on each item and used for folding.

Returns: the final folded computation.

Exceptions

anything that could throw op

◆ foldl() [2/2]

__T Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::foldl	(	const __T &	init,
		Op &&	op = `Op()`
	)		const

inlinenoexceptinherited

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

◆ for_each() [1/4]

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::for_each ( Operation & operation )

inlinenoexceptinherited

Traverse all the container and performs an operation on each element.

for_each(operation) traverses the container and on each element item is performed operation(item).

operation must have the following signature:

void operation(const T & item)

Overloadings of this method allow that that the signature can be lightly different; for example, remove the reference or the const.

Parameters

[in] <tt>operation</tt> to be done on each element.

Returns: an reference to this

Exceptions

anything that can throw operation

◆ for_each() [2/4]

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::for_each ( Operation & operation ) const

inlinenoexceptinherited

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

◆ for_each() [3/4]

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::for_each ( Operation && operation ) const

inlinenoexceptinherited

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

◆ for_each() [4/4]

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::for_each ( Operation && operation )

inlinenoexceptinherited

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

◆ 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

EfectÃºa un recorrido prefijo sobre todas los nodos del Ã¡rbol e invoca la operaciÃ³n visitFct en cada visita

◆ 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 ) const

inline

EfectÃºa un recorrido infijo sobre todas las claves del conjunto e invoca la operacion Op.

Op(p) tiene la siguiente estructura:

struct Key_Op
{
  // atributos de estado que se deseen mantener
  Key_Op(...) // constructor opcional si es necesario inicializar
  {
    // inicializaciÃ³n
  }
  void operator () (const Key & key)
  {
    // operaciÃ³n sobre clave key
  }
};

Parameters

[in] key_op operaciÃ³n a ejecutar sobre cada clave

See also: For_Each_In_Order

◆ 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 = 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.

◆ 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 )

inline

EfectÃºa un recorrido sufijo sobre todas las claves del conjunto e invoca la operacion Op.

Op(p) tiene la siguiente estructura:

struct Key_Op
{
  // atributos de estado que se deseen mantener
  Key_Op(...) // constructor opcional si es necesario inicializar
  {
    // inicializaciÃ³n
  }
  void operator () (const Key & key)
  {
    // operaciÃ³n sobre clave key
  }
};

Parameters

[in] key_op operaciÃ³n a ejecutar sobre cada clave

See also: For_Each_Postorder

◆ 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 = Key_Op() )

inline

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

◆ 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 ) const

inline

EfectÃºa un recorrido prefijo sobre todas las claves del conjunto e invoca la operacion Op.

Op(p) tiene la siguiente estructura:

struct Key_Op
{
  // atributos de estado que se deseen mantener
  Key_Op(...) // constructor opcional si es necesario inicializar
  {
    // inicializaciÃ³n
  }
  void operator () (const Key & key)
  {
    // operaciÃ³n sobre clave key
  }
};

Parameters

[in] key_op operaciÃ³n a ejecutar sobre cada clave

See also: For_Each_Preorder

◆ 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 = 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.

◆ 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

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

Here is the caller graph for this function:

◆ get_it() [1/2]

auto Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::get_it ( ) const

inlineinherited

Return an properly initialized iterator positioned at the first item on the container

◆ get_it() [2/2]

auto Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::get_it ( size_t pos ) const

inlineinherited

Return an properly initialized iterator positioned at the pos item on the container

◆ get_itor()

auto Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::get_itor ( ) const

inlineinherited

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

◆ 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

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

◆ insert()

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

Inserta una clave en el conjunto dinÃ¡mico.

Inserta la clave key en el conjunto dinÃ¡mico.

Parameters

[in] key clave a insertar.

Returns: puntero a la clave insertada si Ã©sta no estÃ¡ dentro del Ã¡rbol; nullptr de lo contrario.

Here is the caller graph for this function:

◆ 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

Calcula y retorna la longitud del camino interno del Ã¡rbol binario de bÃºsqueda.

◆ items()

template<class Container, typename T>

DynList<T> Aleph::GenericItems< Container, T >::items ( ) const

inlineinherited

Return a list of all the elements of a container sorted by traversal order.

Returns: a DynList<T> containing all the elements of the container

Exceptions

bad_alloc if there is no enough memory

◆ 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.

◆ keys()

template<class Container, typename T>

DynList<T> Aleph::GenericItems< Container, T >::keys ( ) const

inlineinherited

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

Here is the caller graph for this function:

◆ length()

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

inlinenoexceptinherited

Count the number of elements of a container.

This method counts the number of elements stored in the container.

Note: Take in account that this method computes; it does not retrieve. Consequently it always takes . However, for many containers this number is already stored and retrievable in through the methos size()

Returns: the number of elements stored in the container.

◆ maps() [1/2]

DynList<__T> Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::maps ( Operation & op ) const

inlineinherited

Map the elements of the container.

maps(op) produces a dynamic list resulting of mapping of each element of container item to the result of operation op(item).

maps() is a template method which receives as template parameters the type __T, which is the type of target or range of mapping, and the transforming operation. By default __T is the same type of the elements stored in the container.

operation should have the following signature:

__T operation(const T & item)

So, operation(item) performs a transformation of item towards the type __T.

If __T ==T`, which is common and by default, then you could specify a mapping without need of template specification. For example, if the container has integer values, the a mapping of item multiplied by 4 could be very simply written as follows:

c.maps([] (int item) { return 4*i; });

In contrast, if the range type is different than the domain type, then it is necessary to specify the template keyword in the method call. For example, if the range is double and you want to return the elements divided by 4, the could do as follows:

c.template maps<double>([] (int item) { return 1.0*item/4; });

Parameters

[in] op operation to be performed in order to do the transformation on an item

Returns: a `DynList<__T> object containing the mapped items. The order of resulting list is the same than the order of visit of the iterator for the container.

Exceptions

anything that could throw op or bad_alloc if there is no enough memory

◆ maps() [2/2]

DynList<__T> Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::maps ( Operation && op ) const

inlineinherited

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

◆ maps_if() [1/2]

DynList<__T> Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::maps_if	(	Prop	prop,
		Operation &	op
	)		const

inlineinherited

Conditional mapping of the elements of the container.

maps_if(prop, op) traverses each item of container, on each item it tests the proposition prop. If this last is true, then the item is mapped through the function op(item).

Parameters

[in]	op	operation to be perfomed in order to do the transformation on an `item`.
[in]	prop	a lambda returning a `bool` which perform the logical test.

Returns: a `DynList<__T> object containing the mapped items. The order of resulting list is the same than the order of visit of the iterator for the container.

Exceptions

anything that could throw op or bad_alloc if there is no enough memory

◆ maps_if() [2/2]

DynList<__T> Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::maps_if	(	Prop	prop,
		Operation &&	op
	)		const

inlineinherited

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

◆ max()

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

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

inline

Retorna la mayor clave contenida en el conjunto segÃºn el criterio de comparaciÃ³n dado.

Here is the caller graph for this function:

◆ min()

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

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

inline

Retorna la menor clave contenida en el conjunto segÃºn el criterio de comparaciÃ³n dado.

Here is the caller graph for this function:

◆ mutable_drop()

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::mutable_drop ( size_t n )

inlineinherited

Drop the first n elements seen from container.

The complexity of this method is $O(N)$ where N always is the number of elements of container.

Exceptions

out_of_range if n is greater or equal than N (the number of elements in the container).

◆ mutable_for_each()

void Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::mutable_for_each ( Operation && operation )

inlinenoexceptinherited

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

◆ nappend()

size_t Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::nappend ( Args ... args )

inlineinherited

Append n variadic items

Parameters

[in] args items to be appended

Returns: the number of appended items

◆ ninsert()

size_t Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::ninsert ( Args ... args )

inlineinherited

Insert n variadic items

Parameters

[in] args items to be inserted

Returns: the number of inserted items

◆ nth() [1/2]

Key & Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::nth ( const size_t n )

inlineinherited

Return the n-th item of container.

The notion of ordinal depends of type of container. On list, probably will be the insertion order. On binary search trees will be the nth smaller item. On hash tables will be pseudo random.

Warning: Frequent use of this method will definitively degrade the performance. Try not to use this method inside loops. In general, if you falls in this situation, then consider your design and to use an faster approach.

Parameters

[in] n the nth item to find

Returns: a valid reference to the item into the container.

Exceptions

out_of_range if n is greater or equal that the size of container.

◆ nth() [2/2]

const Key & Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::nth ( const size_t n ) const

inlineinherited

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

◆ nth_ne()

const Key & Aleph::LocateFunctions< DynSetTree< Key, Tree, Compare > , Key >::nth_ne ( const size_t n ) const

inlinenoexceptinherited

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

◆ operator==()

bool Aleph::EqualToMethod< DynSetTree< Key, Tree, Compare > >::operator== ( const DynSetTree< Key, Tree, Compare > & r ) const

inlinenoexceptinherited

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

◆ partition() [1/3]

std::pair<DynList<Key >, DynList<Key > > Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::partition ( Operation & op ) const

inlineinherited

Exclusive partition of container according to a filter criteria.

partition(op) traverses the container and filters its elements according to the filter criteria defined by op. The filtered elements are copied to a first list and the not filtered ones to a second list. When all the container is traversed, a pair containing these lists is returned.

The op requirements are the same than for filter().

Parameters

[in] op operation instrumenting the filter criteria

Returns: a std::pair<DynList<T>, DynList<T>>.firstcontains the filtered elements andsecondthe non-filtered ones. \throw anything that could throw op orbad_alloc` if there is no enough memory

See also: filter()

◆ partition() [2/3]

std::pair<DynList<Key >, DynList<Key > > Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::partition ( Operation && op ) const

inlineinherited

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

◆ partition() [3/3]

std::pair<DynList<Key >, DynList<Key > > Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::partition ( size_t n ) const

inlineinherited

Exclusive partition of container in the nth item

partition(n) traverses the container and produces a pair of lists. The first one contains the first n elements and the second one the this->size() - n remaining elements.

Parameters

[in] n the first n items of the first list

Exceptions

anything that could throw op or bad_alloc if there is no enough memory

◆ pfilter() [1/2]

DynList<std::tuple<Key , size_t> > Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::pfilter ( Operation & operation ) const

inlineinherited

Filter the elements of a container according to a matching criteria and determine its positions respect to the traversal of container.

pfilter(operation) is very similar to filter(), but instead of building a list of filtered elements, it builds a list of pairs with form (item, pos), where item is a copy of filtered element and pos is its position respect to the traversal order. The position is relative to the container type.

The pair is defined with a tuple:

std::tuple<T, size_t>

Parameters

[in] operation that defines the filter criteria

Returns: a DynList

Exceptions

bad_alloc if there is no enough memory

See also: filter(Operation & operation)

◆ pfilter() [2/2]

DynList<std::tuple<Key , size_t> > Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::pfilter ( Operation && operation ) const

inlineinherited

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

◆ 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

Retorna la posiciÃ³n infija (ordenada) de la clave key.

position(key) busca en el treap extendido la clave key (lo cual toma tiempo $O(\lg n)$ ) y retorna la posiciÃ³n infija del nodo que contiene la clave.

Parameters

[in] key clave a buscar y a determinar posiciÃ³n infija.

Returns: posiciÃ³n infija de la clave key dentro del conjunto ordenado si la clave se encuentra; -1 de lo contrario

Warning: SÃ³lo funciona si el Ã¡rbol maneja rangos.

◆ ptr_filter()

DynList<const Key *> Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::ptr_filter ( Operation & operation ) const

inlineinherited

Filter the elements of a container according to a matching criteria an return pointer to the matched items in the container.

This method builds a dynamic list with stores pointers to the items of matching a criteria defined by operation, which should have the followgin signature:

bool operation(const T & item)

If operation return true then item matches the criteria; otherwise, operation must return false.

For example, if the container has integer, the the following code snippet would return a list containing the items greater than 100:

c.ptr_filter([] (auto item) { return item > 100; });

Parameters

[in] operation defining the flter criteria

Returns: a DynList<const T*> with the pointers to the matched elements.

Exceptions

anything that could throw operation or bad_alloc if there is no enough memory

◆ 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

Elimina una clave del conjunto dinÃ¡mico.

remove(key) busca la clave key del conjunto y la elimina.

Parameters

[in] key clave a eliminar

Returns: nÃºmero de elementos que tiene el conjunto.

Here is the caller graph for this function:

◆ 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

Elimina una clave del conjunto dinÃ¡mico.

remove(key) busca la clave key del conjunto y la elimina.

Parameters

[in] key clave a eliminar

Returns: nÃºmero de elementos que tiene el conjunto.

◆ rev()

DynList<Key > Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::rev ( ) const

inlineinherited

Return a list with the elements of container in reverse order respect to its traversal order.

Returns: a DynList<T> inversely ordered accordirg to the traversal order.

Exceptions

bad_alloc if there is no enough memory

◆ 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

Busca un elemento en el conjunto.

search(key) busca la clave key en el conjunto. Si el elemento se encuentra en el conjunto, entonces se retorna un puntero al valor contenido en el conjunto; de lo contrario se retrona nullptr.

Parameters

[in] key clave a buscar.

Here is the caller graph for this function:

◆ 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 ( const Key & key )

inline

Busca la clave key en el Ã¡rbol binario de bÃºsqueda o lo inserta en caso de no encontrarse.

search_or_insert(key) busca en el Ã¡rbol binario un nodo cuya clave sea KEY(p). Si la clave se encuentra, entonces se retorna un puntero a ella; de lo contrario se inserta key en el Ã¡rbol binario de bÃºsqueda this.

Parameters

[in] key la clave a buscar o insertar.

Returns: puntero a la clave dentro del Ã¡rbol

Here is the caller graph for this function:

◆ select()

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

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

inline

Parameters

[in] i posiciÃ³n deseada

Returns: referencia a la i-esima clave insertada en el conjunto

Here is the caller graph for this function:

◆ 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

Particiona el Ã¡rbol binario de bÃºsqueda segÃºn una clave.

split_key(key,l,r) particiona, segÃºn la clave key, el Ã¡rbol binario de bÃºsqueda this en dos Ã¡rboles l y r. Luego de la operaciÃ³n el Ã¡rbol this deviene vacÃo, l contiene todas las claves menores que key y r las mayores.

Parameters

[in]	key	clave de particiÃ³n.
[out]	l	Ã¡rbol con las claves menores que key.
[out]	r	Ã¡rbol con las claves mayores que key.

Returns: true si key no estÃ¡ dentro del Ã¡rbol binario; en cuyo caso la particiÃ³n fue hecha exitosamente. De lo contrario, si key se encuentra dentro del Ã¡rbol, el Ã¡rbol no se particiona y el resultado es false.

◆ 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

Particiona el Ã¡rbol binario de bÃºsqueda segÃºn una clave que puede estar presente en el Ã¡rbol.

split_dup(key,l,r) particiona, segÃºn la clave key, el Ã¡rbol binario de bÃºsqueda this en dos Ã¡rboles l y r. Luego de la operaciÃ³n el Ã¡rbol this deviene vacÃo, l contiene todas las claves menores que key y r las mayores o iguales.

Parameters

[in]	key	clave de particiÃ³n.
[out]	l	Ã¡rbol con las claves menores que key.
[out]	r	Ã¡rbol con las claves mayores o iguales que key.

◆ 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

Particiona el Ã¡rbol binario de bÃºsqueda segÃºn una posiciÃ³n infija.

split_pos(pos,l,r) particiona Ã¡rbol binario de bÃºsqueda this en dos Ã¡rboles l y r. Luego de la operaciÃ³n el Ã¡rbol this deviene vacÃo, l contiene las pos primeras claves y r las restantes.

Parameters

[in]	pos	posiciÃ³n de particiÃ³n
[out]	l	Ã¡rbol con las claves entre intervalo [0,pos]
[out]	r	Ã¡rbol con las claves en el intervalo (pos,N), donde N es el nÃºmero de claves

◆ 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 )

inline

Intercambia todos los elementos del treap this con el treap tree en tiempo contante (y extremadamente rÃ¡pido).

Parameters

[in] tree el treap a intercambiar con this

Here is the caller graph for this function:

◆ take() [1/2]

DynList<Key > Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::take ( const size_t n ) const

inlineinherited

Return a list with the first n elements seen in the container during its traversal.

The complexity of this method is $O(n)$ where n can be less than the number of elements of container.

Returns: A DynList<T> having the first n elements according to its traversal order.

Exceptions

bad_alloc if there is no enough memory or out_of_range if n is greater or equal than the number of elements in the container.

◆ take() [2/2]

DynList<Key > Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::take	(	size_t	i,
		size_t	j,
		size_t	step = `1`
	)		const

inlineinherited

Return a list with elements seen in the container between i and j position respect to its traversal.

The complexity of this method is $O(n)$ where n can be less than the number of elements of container.

Returns: A DynList<T> having the first n elements according to its traversal order.

Exceptions

bad_alloc if there is no enough memory or out_of_range if n is greater or equal than the number of elements in the container.

◆ tpartition() [1/2]

std::tuple<DynList<Key >, DynList<Key > > Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::tpartition ( Operation & op ) const

inlineinherited

Exclusive partition of container according to a filter criteria.

This methos has exactly the same semantic than partition(Operation & op), excepts than instead of returning a std::pair it returns a std::tuple.

Parameters

[in] op operation instrumenting the filter criteria

Returns: a std::tuple<DynList<T>, DynList<T>>.firstcontains the filteres elements andsecondthe non-filtered ones. \throw anything that could throw op orbad_alloc` if there is no enough memory

See also: partition(Operation & op)

◆ tpartition() [2/2]

std::tuple<DynList<Key >, DynList<Key > > Aleph::FunctionalMethods< DynSetTree< Key, Tree, Compare > , Key >::tpartition ( Operation && op ) const

inlineinherited

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

◆ traverse()

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 the routine advance and so on

Parameters

[in] operation

Returns: true if all items are traversed; false otherwise

Here is the caller graph for this function:

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

tpl_dynSetTree.H

Public Types

Public Member Functions

Detailed Description

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

Member Typedef Documentation

◆ Node

Member Function Documentation

◆ all() [1/2]

◆ all() [2/2]

◆ del()

◆ drop()

◆ each() [1/6]

◆ each() [2/6]

◆ each() [3/6]

◆ each() [4/6]

◆ each() [5/6]

◆ each() [6/6]

◆ emplace()

◆ emplace_end()

◆ emplace_ins()

◆ equal_to()

◆ exists() [1/2]

◆ exists() [2/2]

◆ filter() [1/2]

◆ filter() [2/2]

◆ find()

◆ find_index() [1/2]

◆ find_index() [2/2]

◆ find_item() [1/4]

◆ find_item() [2/4]

◆ find_item() [3/4]

◆ find_item() [4/4]

◆ find_position()

◆ find_ptr() [1/4]

◆ find_ptr() [2/4]

◆ find_ptr() [3/4]

◆ find_ptr() [4/4]

◆ fold() [1/2]

◆ fold() [2/2]

◆ foldl() [1/2]

◆ foldl() [2/2]

◆ for_each() [1/4]

◆ for_each() [2/4]

◆ for_each() [3/4]

◆ for_each() [4/4]

◆ for_each_in_preorder()

◆ for_each_inorder() [1/2]

◆ for_each_inorder() [2/2]

◆ for_each_postorder() [1/2]

◆ for_each_postorder() [2/2]

◆ for_each_preorder() [1/2]

◆ for_each_preorder() [2/2]

◆ get_first()

◆ get_it() [1/2]

◆ get_it() [2/2]

◆ get_itor()

◆ get_last()

◆ insert()

◆ internal_path_length()

◆ items()

◆ join()

◆ keys()

◆ length()

◆ maps() [1/2]

◆ maps() [2/2]

◆ maps_if() [1/2]

◆ maps_if() [2/2]

◆ max()

◆ min()

◆ mutable_drop()

◆ mutable_for_each()

◆ nappend()

◆ ninsert()

◆ nth() [1/2]

◆ nth() [2/2]

◆ nth_ne()

◆ operator==()

◆ partition() [1/3]

◆ partition() [2/3]

◆ partition() [3/3]

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