Aleph-w  1.5a.2
Biblioteca general de algoritmos y estructuras de datos
 Todo Clases Archivos Funciones Variables 'typedefs' Enumeraciones Amigas Grupos Páginas
Métodos públicos | Lista de todos los miembros
Referencia de la plantilla de la Clase Aleph::Nodes_Index< GT, Compare, Tree, SN >
Grafos.

#include <tpl_graph_indexes.H>

+ Diagrama de herencias de Aleph::Nodes_Index< GT, Compare, Tree, SN >
+ Diagrama de colaboración para Aleph::Nodes_Index< GT, Compare, Tree, SN >:

Métodos públicos

 Nodes_Index (GT &_g, Compare &cmp, SN &_sn)
 
 Nodes_Index (GT &_g, Compare &&cmp=Compare(), SN &&_sn=SN())
 
GT_Node * insert_in_graph (GT_Node *p)
 
GT_Node * search_or_insert_in_graph (GT_Node *p)
 
GT_Node * insert_in_graph (const GT_Node_Info &info)
 
GT_Node * search_or_insert_in_graph (const GT_Node_Info &info)
 
GT_Node * insert_in_graph (const GT_Node_Info &&info=GT_Node_Info())
 
GT_Node * search (GT_Node *p)
 
GT_Node * search (const GT_Node_Info &info)
 
void remove_from_graph (GT_Node *p) throw (std::exception, std::domain_error)
 
 Nodes_Index (GT &_g, Compare &cmp, SN &_sn)
 
 Nodes_Index (GT &_g, Compare &&cmp=Compare(), SN &&_sn=SN())
 
GT_Node * insert_in_graph (GT_Node *p)
 
GT_Node * insert_in_graph (const GT_Node_Info &info)
 
GT_Node * insert_in_graph (const GT_Node_Info &&info=GT_Node_Info())
 
GT_Node * search (GT_Node *p)
 
GT_Node * search (const GT_Node_Info &info)
 
void remove_from_graph (GT_Node *p) throw (std::exception, std::domain_error)
 
- Métodos públicos heredados desde Aleph::DynSetTree< Tree, GT::Node *, Compare >
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< Tree > &list)
 
 DynSetTree (DynSetTree &&srcTree)
 
void empty ()
 Elimina todos los elementos del conjunto.
 
DynSetTree & operator= (const DynList< Tree > &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.
 
Tree * insert (const Tree &key)
 
Tree * insert (Tree &&key)
 
Tree * append (const Tree &key)
 
Tree * append (Tree &&key)
 
Tree * search_or_insert (const Tree &key)
 
Tree * search_or_insert (Tree &&key)
 
Tree * insert_dup (const Tree &key)
 
Tree * insert_dup (Tree &&key)
 
Tree * put (const Tree &key)
 Seudo sinonimo de insert; no retorna ningún valor.
 
Tree * put (Tree &&key)
 
size_t remove (const Tree &key)
 
bool exist (const Tree &key) const
 Retorna true si key pertenece al conjunto dinámico.
 
bool has (const Tree &key) const
 
bool contains (const Tree &key) const
 
Tree & find (const Tree &key) throw (std::exception, std::domain_error)
 
std::pair< int, Tree * > find_position (const Tree &key) const
 
Tree * search (const Tree &key) const throw (std::exception, std::domain_error)
 
const Tree & min () const
 
const Tree & get_first ()
 
const Tree & max () const
 
const Tree & get_last ()
 
const Tree & 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 Tree & get_root () const
 
size_t height () const
 Calcula y retorna la altura del árbol binario de búsqueda.
 
void for_each_in_preorder (void(*visitFct)(Node *, int, int))
 
long position (const Tree &key) const
 
Tree & select (const size_t &i)
 
const Tree & select (const size_t &i) const
 
Tree & operator() (const size_t &i)
 
Tree & access (const size_t &i)
 
bool verify ()
 
void for_each_preorder (Key_Op &key_op)
 
void for_each_preorder (Key_Op &&key_op=Key_Op())
 
void for_each_inorder (Key_Op &key_op)
 
void for_each_inorder (Key_Op &&key_op=Key_Op())
 
void for_each_postorder (Key_Op &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 Tree &key, DynSetTree &l, DynSetTree &r)
 
void split_pos (const size_t pos, DynSetTree &l, DynSetTree &r)
 
void split_key_dup (const Tree &key, DynSetTree &l, DynSetTree &r)
 
bool traverse (Operation &op)
 
bool traverse (Operation &&op=Operation())
 
bool traverse (Operation &op) const
 
bool traverse (Operation &&op=Operation()) const
 
 Functional_Methods (Tree)
 
 Generic_Keys (Tree)
 
 Equal_To_Method (DynSetTree)
 
- Métodos públicos heredados desde Aleph::DynSetTree< GT::Node *, Tree, Compare >
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< GT::Node * > &list)
 
 DynSetTree (DynSetTree &&srcTree)
 
void empty ()
 Elimina todos los elementos del conjunto.
 
DynSetTree & operator= (const DynList< GT::Node * > &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.
 
GT::Node ** insert (const GT::Node *&key)
 
GT::Node ** insert (GT::Node *&&key)
 
GT::Node ** append (const GT::Node *&key)
 
GT::Node ** append (GT::Node *&&key)
 
GT::Node ** search_or_insert (const GT::Node *&key)
 
GT::Node ** search_or_insert (GT::Node *&&key)
 
GT::Node ** insert_dup (const GT::Node *&key)
 
GT::Node ** insert_dup (GT::Node *&&key)
 
GT::Node ** put (const GT::Node *&key)
 Seudo sinonimo de insert; no retorna ningún valor.
 
GT::Node ** put (GT::Node *&&key)
 
size_t remove (const GT::Node *&key)
 
bool exist (const GT::Node *&key) const
 Retorna true si key pertenece al conjunto dinámico.
 
bool has (const GT::Node *&key) const
 
bool contains (const GT::Node *&key) const
 
GT::Node *& find (const GT::Node *&key) throw (std::exception, std::domain_error)
 
std::pair< int, GT::Node ** > find_position (const GT::Node *&key) const
 
GT::Node ** search (const GT::Node *&key) const throw (std::exception, std::domain_error)
 
const GT::Node *& min () const
 
const GT::Node *& get_first ()
 
const GT::Node *& max () const
 
const GT::Node *& get_last ()
 
const GT::Node *& 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 GT::Node *& get_root () const
 
size_t height () const
 Calcula y retorna la altura del árbol binario de búsqueda.
 
void for_each_in_preorder (void(*visitFct)(Node *, int, int))
 
long position (const GT::Node *&key) const
 
GT::Node *& select (const size_t &i)
 
const GT::Node *& select (const size_t &i) const
 
GT::Node *& operator() (const size_t &i)
 
GT::Node *& access (const size_t &i)
 
bool verify ()
 
void for_each_preorder (Key_Op &key_op)
 
void for_each_preorder (Key_Op &&key_op=Key_Op())
 
void for_each_inorder (Key_Op &key_op)
 
void for_each_inorder (Key_Op &&key_op=Key_Op())
 
void for_each_postorder (Key_Op &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 GT::Node *&key, DynSetTree &l, DynSetTree &r)
 
void split_pos (const size_t pos, DynSetTree &l, DynSetTree &r)
 
void split_key_dup (const GT::Node *&key, DynSetTree &l, DynSetTree &r)
 
bool traverse (Operation &op)
 
bool traverse (Operation &&op=Operation())
 
bool traverse (Operation &op) const
 
bool traverse (Operation &&op=Operation()) const
 
 Functional_Methods (GT::Node *)
 
 Generic_Keys (GT::Node *)
 
 Equal_To_Method (DynSetTree)
 

Otros miembros heredados

- Tipos públicos heredados desde Aleph::DynSetTree< Tree, GT::Node *, Compare >
typedef GT::Node *< Tree,
Compare >::Node 		Node
 
typedef DynSetTree Set_Type
 
typedef Tree Item_Type
 
typedef Tree Key_Type
 
- Tipos públicos heredados desde Aleph::DynSetTree< GT::Node *, Tree, Compare >
typedef Tree< GT::Node
*, Compare >::Node 		Node
 
typedef DynSetTree Set_Type
 
typedef GT::Node * Item_Type
 
typedef GT::Node * Key_Type
 

Descripción detallada

template<class GT, class Compare = Dft_Node_Cmp<GT>, template< typename, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>
class Aleph::Nodes_Index< GT, Compare, Tree, SN >

Construye un índice de nodos para su rápida búsqueda y recuperación.

IndexNode indiza los nodos de un grafo según un clave dada definida por el usuario.

La clase recibe los siguientes parámetros tipo:

  1. GT: el tipo de grafo basado en List_Graph.
  2. Compare: clase de comparación para la clave de indización. El contrato de esta clase es intrumentar el operador () así:
    template <class GT>
    struct Dft_Node_Cmp
    {
    bool
    operator () (typename GT::Node * p1, typename GT::Node * p2) const
    {
    // acceso a los nodos y comparación según el campo deseado
    }
    };
    IndexNode recibe esta clase por omisión programada para comparar el valor retornado por get_info() sobre cada nodo. Para ello, el operador < del tipo GT::Node_Type debe estar implementado.
  3. SN: clase filtro para el iterador de nodos en caso de que se construya
  4. Tree: el tipo de árbol binario de búsqueda usado internamente para indizar las claves. Por omisión se usan treaps.
Ver también
IndexArc Index_Graph
Autor
Leandro Rabindranath León (lrleon en ula punto ve)
Alejandro Mujica (aledrums en gmail punto com)

Documentación de las funciones miembro

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< typename, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>
GT_Node* Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph ( GT_Node *  p)
inline

Inserta el nodo p en el grafo y luego en el índice

Parámetros
[in]punteroal nodo que se quiere insertar.
Devuelve
puntero al nodo insertado.

Hace referencia a Aleph::DynSetTree< GT::Node *, Tree, Compare >::insert().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< typename, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>
GT_Node* Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph ( GT_Node *  p)
inline

Inserta el nodo p en el grafo y luego en el índice

Parámetros
[in]punteroal nodo que se quiere insertar.
Devuelve
puntero al nodo insertado.

Hace referencia a Aleph::DynSetTree< GT::Node *, Tree, Compare >::insert().

Referenciado por Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph().

+ Gráfico de llamadas para esta función:

+ Gráfico de llamadas a esta función:

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< typename, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>
GT_Node* Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph ( const GT_Node_Info &  info)
inline

Crea un nuevo nodo con contenido genérico info, lo inserta en el grafo y luego en el índice

Parámetros
[in]infoContenido asociado al nuevo nodo.
Devuelve
puntero al nodo
Excepciones
bad_allocsi no hay suficiente memoria

Hace referencia a Aleph::DynSetTree< GT::Node *, Tree, Compare >::insert().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< typename, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>
GT_Node* Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph ( const GT_Node_Info &&  info = GT_Node_Info())
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.

Hace referencia a Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< typename, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>
GT_Node* Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph ( const GT_Node_Info &  info)
inline

Crea un nuevo nodo con contenido genérico info, lo inserta en el grafo y luego en el índice

Parámetros
[in]infoContenido asociado al nuevo nodo.
Devuelve
puntero al nodo
Excepciones
bad_allocsi no hay suficiente memoria

Hace referencia a Aleph::DynSetTree< GT::Node *, Tree, Compare >::insert().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< typename, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>
GT_Node* Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph ( const GT_Node_Info &&  info = GT_Node_Info())
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.

Hace referencia a Aleph::Nodes_Index< GT, Compare, Tree, SN >::insert_in_graph().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< typename, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>
void Aleph::Nodes_Index< GT, Compare, Tree, SN >::remove_from_graph ( GT_Node *  p)
throw (std::exception,
std::domain_error
)
inline

Elimina el nodo p del grafo y del ìndice.

Parámetros
[in]ppuntero al nodo a eliminar
Excepciones
domain_errorsi el nodo no està insertado en el índice (lo que posiblemente signifique que tampoco en el grafo).

Hace referencia a Aleph::DynSetTree< GT::Node *, Tree, Compare >::find().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< typename, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>
void Aleph::Nodes_Index< GT, Compare, Tree, SN >::remove_from_graph ( GT_Node *  p)
throw (std::exception,
std::domain_error
)
inline

Elimina el nodo p del grafo y del ìndice.

Parámetros
[in]ppuntero al nodo a eliminar
Excepciones
domain_errorsi el nodo no està insertado en el índice (lo que posiblemente signifique que tampoco en el grafo).

Hace referencia a Aleph::DynSetTree< GT_Node *, Tree, Compare >::find() y Aleph::DynSetTree< GT_Node *, Tree, Compare >::remove().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< typename, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>
GT_Node* Aleph::Nodes_Index< GT, Compare, Tree, SN >::search ( GT_Node *  p)
inline

Busca un nodo según el contenido de p.

Tome en cuenta que el criterio de búsqueda está determinado por la clase parámetro de comparación Compare.

Parámetros
[in]pel nodo cuya información se desea buscar.
Devuelve
puntero al nodo si es encontrado o nulo de lo contrario.

Hace referencia a Aleph::DynSetTree< GT_Node *, Tree, Compare >::search().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< typename, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>
GT_Node* Aleph::Nodes_Index< GT, Compare, Tree, SN >::search ( GT_Node *  p)
inline

Busca un nodo según el contenido de p.

Tome en cuenta que el criterio de búsqueda está determinado por la clase parámetro de comparación Compare.

Parámetros
[in]pel nodo cuya información se desea buscar.
Devuelve
puntero al nodo si es encontrado o nulo de lo contrario.

Hace referencia a Aleph::DynSetTree< GT_Node *, Tree, Compare >::search().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< typename, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>
GT_Node* Aleph::Nodes_Index< GT, Compare, Tree, SN >::search_or_insert_in_graph ( GT_Node *  p)
inline

Busca en el índice al nodo p y lo retorna, si no existe lo inserta tanto en el índice como en el grafo.

Parámetros
[in]punteroal nodo que se quiere buscar o insertar.
Devuelve
puntero al nodo encontrado o insertado.

Hace referencia a Aleph::DynSetTree< GT::Node *, Tree, Compare >::search_or_insert().

+ Gráfico de llamadas para esta función:

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< typename, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>
GT_Node* Aleph::Nodes_Index< GT, Compare, Tree, SN >::search_or_insert_in_graph ( const GT_Node_Info &  info)
inline

Busca en el índice un nodo con contenido genérico info, si no existe lo inserta en el grafo y luego en el índice

Parámetros
[in]infoContenido asociado al nodo que se quiere encontrar o insertar.
Devuelve
puntero al nodo encontrado o insertado-
Excepciones
bad_allocsi no hay suficiente memoria

Hace referencia a Aleph::DynSetTree< GT::Node *, Tree, Compare >::search_or_insert().

+ Gráfico de llamadas para esta función:

La documentación para esta clase fue generada a partir de los siguientes ficheros:
Leandro Rabindranath León