Referencia de la plantilla de la Clase Aleph::DynSetTree< Key, Tree, Compare >

#include <tpl_dynSetTree.H>

Clases
class	Iterator

Tipos públicos
typedef Tree< Key, Compare >::Node	Node
typedef DynSetTree	Set_Type
typedef Key	Item_Type
typedef Key	Key_Type

Métodos públicos
void	swap (DynSetTree &dset)
	DynSetTree (Compare &&cmp=Compare())
	Instancia un conjunto dinámico vacío.
	DynSetTree (Compare &cmp)
	DynSetTree (const DynSetTree &srcTree)
	Instancia un conjunto dinámico copia de srcTree.
	DynSetTree (const DynList< Key > &list)
	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)
Key *	insert_dup (const Key &key)
Key *	insert_dup (Key &&key)
Key *	put (const Key &key)
	Seudo sinonimo de insert; no retorna ningún valor.
Key *	put (Key &&key)
size_t	remove (const Key &key)
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) throw (std::exception, std::domain_error)
std::pair< int, Key * >	find_position (const Key &key) const
Key *	search (const Key &key) const throw (std::exception, std::domain_error)
const Key &	min () const
const Key &	get_first ()
const Key &	max () const
const Key &	get_last ()
const Key &	get ()
	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
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)
Key &	access (const size_t &i)
bool	verify ()
template<class Key_Op >
void	for_each_preorder (Key_Op &key_op)
template<class Key_Op >
void	for_each_preorder (Key_Op &&key_op=Key_Op())
template<class Key_Op >
void	for_each_inorder (Key_Op &key_op)
template<class Key_Op >
void	for_each_inorder (Key_Op &&key_op=Key_Op())
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
	Functional_Methods (Key)
	Generic_Keys (Key)
	Equal_To_Method (DynSetTree)

Descripción detallada

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()().

Documentación de los 'Typedef' miembros de la clase

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

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

Tipo de nodo binario empleado por el árbol binario de búsqueda interno.

Documentación de las funciones miembro

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 ) throw ( std::exception, std::domain_error )

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.

Parámetros

[in]

key

clave a buscar.

Devuelve

referencia modificable a la clave key contenida dentro del conjunto.

Excepciones

domain_error

si key no está dentro del conjunto.

Nota

Téngase sumo cuidado con alterar el orden de búsqueda, pues la referencia es modificable.

Referenciado por Aleph::DynMapTree< string, Huffman_Node *, Treap_Vtl >::find(), Aleph::IndexNode< GT, Compare, Tree >::remove_from_graph() y Aleph::Arcs_Index< GT, Compare, Tree, SA >::remove_from_graph().

Gráfico de llamadas a esta función:

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 ) y retorna la posición infija del nodo que contiene la clave.

Parámetros

[in]

key

clave a buscar y a determinar posición infija.

Devuelve

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.

Atención

Sólo funciona si el árbol maneja rangos.

Referenciado por Aleph::DynSetTree< Key, Tree, Compare >::Iterator::set_key().

Gráfico de llamadas a esta función:

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

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 )

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
  }
};

Parámetros

[in]

key_op

operación a ejecutar sobre cada clave

Ver también

For_Each_In_Order

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

inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

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
  }
};

Parámetros

[in]

key_op

operación a ejecutar sobre cada clave

Ver también

For_Each_Postorder

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

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

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 )

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
  }
};

Parámetros

[in]

key_op

operación a ejecutar sobre cada clave

Ver también

For_Each_Preorder

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

inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

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

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

inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

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

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

inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

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.

Parámetros

[in]

key

clave a insertar.

Devuelve

puntero a la clave insertada si ésta no está dentro del árbol; NULL de lo contrario.

Referenciado por Aleph::DynMapTree< string, Huffman_Node *, Treap_Vtl >::insert() y Aleph::DynSetTree< GT::Arc *, Tree, Compare >::put().

Gráfico de llamadas a esta función:

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.

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

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

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.

Referenciado por Aleph::DynSetTree< GT::Arc *, Tree, Compare >::get() y Aleph::DynSetTree< GT::Arc *, Tree, Compare >::get_last().

Gráfico de llamadas a esta función:

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.

Referenciado por Aleph::DynSetTree< GT::Arc *, Tree, Compare >::get_first().

Gráfico de llamadas a esta función:

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 ) y retorna la posición infija del nodo que contiene la clave.

Parámetros

[in]

key

clave a buscar y a determinar posición infija.

Devuelve

posición infija de la clave key dentro del conjunto ordenado si la clave se encuentra; -1 de lo contrario

Atención

Sólo funciona si el árbol maneja rangos.

Referenciado por Aleph::DynSetTree< Key, Tree, Compare >::Iterator::reset_to_key().

Gráfico de llamadas a esta función:

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.

Parámetros

[in]

key

clave a eliminar

Devuelve

número de elementos que tiene el conjunto.

Referenciado por Aleph::DynSetTree< Key, Tree, Compare >::Iterator::del(), Aleph::IndexArc< GT, Tree >::remove(), Aleph::IndexNode< GT, Compare, Tree >::remove(), Aleph::DynMapTree< string, Huffman_Node *, Treap_Vtl >::remove(), Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::remove_arc(), Aleph::IndexNode< GT, Compare, Tree >::remove_from_graph() y Aleph::Arcs_Index< GT, Compare, Tree, SA >::remove_from_graph().

Gráfico de llamadas a esta función:

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 throw ( std::exception, std::domain_error )

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

Parámetros

[in]

key

clave a buscar.

Devuelve

puntero al elemento en en el conjunto si éste se encuentra en el mismo; NULL de l contrario.

Nota

Téngase sumo cuidado con alterar el orden de búsqueda, pues a través del puntero la clave es modificable.

Referenciado por Aleph::DynSetTree< GT::Arc *, Tree, Compare >::exist(), Aleph::IndexArc< GT, Tree >::search(), Aleph::IndexNode< GT, Compare, Tree >::search(), Aleph::DynMapTree< string, Huffman_Node *, Treap_Vtl >::search(), Aleph::Arcs_Index< GT, Compare, Tree, SA >::search() y Aleph::DynMapTree< string, Huffman_Node *, Treap_Vtl >::test().

Gráfico de llamadas a esta función:

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.

Parámetros

[in]

key

la clave a buscar o insertar.

Devuelve

puntero a la clave dentro del árbol

Referenciado por Aleph::DynMapTree< string, Huffman_Node *, Treap_Vtl >::search_or_insert().

Gráfico de llamadas a esta función:

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

Retorna el i-ésimo nodo en posición infija

Parámetros

[in]

i

posición deseada

Devuelve

referencia a la i-esima clave insertada en el conjunto

Referenciado por Aleph::DynSetTree< Key, Tree, Compare >::Iterator::set_pos().

Gráfico de llamadas a esta función:

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.

Parámetros

[in]	key	clave de partición.
[out]	l	árbol con las claves menores que key.
[out]	r	árbol con las claves mayores que key.

Devuelve

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.

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.

Parámetros

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

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.

Parámetros

[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

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

Parámetros

[in]

tree

el treap a intercambiar con this

Referenciado por Aleph::DynSetTree< GT::Arc *, Tree, Compare >::operator=().

Gráfico de llamadas a esta función:

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 eah pair executes operation.

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

Parámetros

[in]

operation

Devuelve

true if all items are traversed; false otherwise

---

La documentación para esta clase fue generada a partir del siguiente fichero:

• tpl_dynSetTree.H