Aleph-w  1.5a.2
Biblioteca general de algoritmos y estructuras de datos
 Todo Clases Archivos Funciones Variables 'typedefs' Enumeraciones Amigas Grupos Páginas
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.
 
DynSetTreeoperator= (const DynList< Key > &list)
 
DynSetTreeoperator= (const DynSetTree &srcTree)
 Asigna a this el conjunto dinámico srcTree.
 
DynSetTreeoperator= (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
 
Nodeget_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())
 
DynSetTreejoin (DynSetTree &t, DynSetTree &dup)
 
DynSetTreejoin (DynSetTree &t, DynSetTree &&dup=DynSetTree())
 
DynSetTreejoin_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]keyclave a buscar.
Devuelve
referencia modificable a la clave key contenida dentro del conjunto.
Excepciones
domain_errorsi 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 $O(\lg n)$) y retorna la posición infija del nodo que contiene la clave.

Parámetros
[in]keyclave 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_opoperació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_opoperació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_opoperació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]keyclave 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 $O(\lg n)$) y retorna la posición infija del nodo que contiene la clave.

Parámetros
[in]keyclave 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]keyclave 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]keyclave 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]keyla 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]iposició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]keyclave 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]keyclave 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]posposició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]treeel 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:

Leandro Rabindranath León