Builds an index of nodes for fast search and retrieval. More...

#include <tpl_indexNode.H>

Inheritance diagram for Aleph::IndexNode< GT, Compare, Tree, SN >:

Collaboration diagram for Aleph::IndexNode< GT, Compare, Tree, SN >:

Public Member Functions
GT_Node *	insert (GT_Node *p)
	Inserts the node p into the index.

GT_Node *	insert_in_graph (const GT_Node_Type &info)
	Creates a new node with generic content info, inserts it into the graph, and then into the index.

GT_Node *	insert_in_graph (GT_Node_Type &&info)

GT_Node *	search (GT_Node *p)
	Searches for a node based on the content of p.

GT_Node *	search (const GT_Node_Type &info)
	Searches for a node based on the info.

void	remove (GT_Node *p)
	Removes the node at address p from the index.

void	remove_from_graph (GT_Node *p)
	Removes the node p from the graph and the index.

void	clear_index ()
	Clears the index; all nodes are removed from it.

void	build_index ()
	Inserts all nodes from the graph into the index.

void	clear_graph ()
	Removes all nodes from the graph and the index.

	IndexNode (GT &__g, SN __sn=SN())
	Creates an index from the nodes inserted in the graph.

size_t	size () const
	Returns the number of items contained in the index.

Private Types
typedef GT::Node	GT_Node

typedef GT::Node_Type	GT_Node_Type

Private Member Functions
void	init ()

Private Attributes
DynSetTree< GT_Node *, Tree, Compare >	index

GT &	g

SN	sn

Detailed Description

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

Builds an index of nodes for fast search and retrieval.

IndexNode indexes the nodes of a graph according to a user-defined key.

Template Parameters

GT	The graph type, based on List_Graph.
Compare	The comparison class for the indexing key. The contract for this class is to implement the () operator as follows: template <class GT> struct Dft_Node_Cmp { bool operator () (typename GT::Node * p1, typename GT::Node * p2) const { // access nodes and compare based on the desired field } }; Aleph::Dft_Node_Cmp Default node comparison class for Nodes_Index. Definition tpl_graph_indexes.H:59 Aleph::Graph_Node< int > By default, IndexNode uses a class that compares the value returned by get_info() on each node. For this, the < operator of the GT::Node_Type must be implemented.
SN	The filter class for the node iterator, if one is constructed.
Tree	The binary search tree type used internally for indexing keys. By default, Treaps are used.

See also: IndexArc, Index_Graph

Author: Leandro Rabindranath León (lrleon at ula dot ve); Alejandro Mujica (aledrums at gmail dot com)

Definition at line 128 of file tpl_indexNode.H.

Member Typedef Documentation

◆ GT_Node

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

typedef GT::Node Aleph::IndexNode< GT, Compare, Tree, SN >::GT_Node

private

Definition at line 130 of file tpl_indexNode.H.

◆ GT_Node_Type

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

typedef GT::Node_Type Aleph::IndexNode< GT, Compare, Tree, SN >::GT_Node_Type

private

Definition at line 131 of file tpl_indexNode.H.

Constructor & Destructor Documentation

◆ IndexNode()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

Aleph::IndexNode< GT, Compare, Tree, SN >::IndexNode	(	GT &	__g,
		SN	__sn = `SN()`
	)

inline

Creates an index from the nodes inserted in the graph.

Parameters

__g	The graph.
__sn	A node filter object.

Exceptions

std::bad_alloc if there is not enough memory.

Definition at line 285 of file tpl_indexNode.H.

References Aleph::IndexNode< GT, Compare, Tree, SN >::init().

Member Function Documentation

◆ build_index()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

void Aleph::IndexNode< GT, Compare, Tree, SN >::build_index ( )

inline

Inserts all nodes from the graph into the index.

Definition at line 252 of file tpl_indexNode.H.

References Aleph::IndexNode< GT, Compare, Tree, SN >::g, Aleph::IndexNode< GT, Compare, Tree, SN >::insert(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::IndexNode< GT, Compare, Tree, SN >::search(), and Aleph::IndexNode< GT, Compare, Tree, SN >::sn.

◆ clear_graph()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

void Aleph::IndexNode< GT, Compare, Tree, SN >::clear_graph ( )

inline

Removes all nodes from the graph and the index.

Definition at line 263 of file tpl_indexNode.H.

References Aleph::clear_graph(), Aleph::IndexNode< GT, Compare, Tree, SN >::clear_index(), and Aleph::IndexNode< GT, Compare, Tree, SN >::g.

◆ clear_index()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

void Aleph::IndexNode< GT, Compare, Tree, SN >::clear_index ( )

inline

Clears the index; all nodes are removed from it.

Definition at line 246 of file tpl_indexNode.H.

References Aleph::IndexNode< GT, Compare, Tree, SN >::index.

Referenced by Aleph::IndexNode< GT, Compare, Tree, SN >::clear_graph().

◆ init()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

void Aleph::IndexNode< GT, Compare, Tree, SN >::init ( )

inlineprivate

Definition at line 271 of file tpl_indexNode.H.

References Aleph::IndexNode< GT, Compare, Tree, SN >::g, Aleph::IndexNode< GT, Compare, Tree, SN >::insert(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), and Aleph::IndexNode< GT, Compare, Tree, SN >::sn.

Referenced by Aleph::IndexNode< GT, Compare, Tree, SN >::IndexNode().

◆ insert()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

GT_Node * Aleph::IndexNode< GT, Compare, Tree, SN >::insert ( GT_Node * p )

inline

Inserts the node p into the index.

Parameters

p	Pointer to the node to be stored in the index.

Returns: A pointer to the inserted node.

Exceptions

std::bad_alloc if there is not enough memory.

Definition at line 146 of file tpl_indexNode.H.

References Aleph::IndexNode< GT, Compare, Tree, SN >::index.

Referenced by Aleph::IndexNode< GT, Compare, Tree, SN >::build_index(), Aleph::IndexNode< GT, Compare, Tree, SN >::init(), Aleph::IndexNode< GT, Compare, Tree, SN >::insert_in_graph(), and Aleph::IndexNode< GT, Compare, Tree, SN >::insert_in_graph().

◆ insert_in_graph() [1/2]

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

Aleph::IndexNode< GT, Compare, Tree, SN >::insert_in_graph ( const GT_Node_Type & info )

inline

Creates a new node with generic content info, inserts it into the graph, and then into the index.

Parameters

info	Content associated with the new node.

Returns: A pointer to the created node.

Exceptions

std::bad_alloc if there is not enough memory.

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

Definition at line 159 of file tpl_indexNode.H.

References Aleph::IndexNode< GT, Compare, Tree, SN >::g, Aleph::IndexNode< GT, Compare, Tree, SN >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node().

Referenced by main().

◆ insert_in_graph() [2/2]

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

GT_Node * Aleph::IndexNode< GT, Compare, Tree, SN >::insert_in_graph ( GT_Node_Type && info )

inline

Definition at line 176 of file tpl_indexNode.H.

References Aleph::IndexNode< GT, Compare, Tree, SN >::g, Aleph::IndexNode< GT, Compare, Tree, SN >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node().

◆ remove()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

void Aleph::IndexNode< GT, Compare, Tree, SN >::remove ( GT_Node * p )

inline

Removes the node at address p from the index.

Definition at line 227 of file tpl_indexNode.H.

References Aleph::IndexNode< GT, Compare, Tree, SN >::index.

◆ remove_from_graph()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

void Aleph::IndexNode< GT, Compare, Tree, SN >::remove_from_graph ( GT_Node * p )

inline

Removes the node p from the graph and the index.

Parameters

p	Pointer to the node to be removed.

Exceptions

std::domain_error if the node is not in the index (which likely means it's not in the graph either).

Definition at line 238 of file tpl_indexNode.H.

References Aleph::IndexNode< GT, Compare, Tree, SN >::g, Aleph::IndexNode< GT, Compare, Tree, SN >::index, and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node().

◆ search() [1/2]

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

GT_Node * Aleph::IndexNode< GT, Compare, Tree, SN >::search ( const GT_Node_Type & info )

inline

Searches for a node based on the info.

Note that the search criterion is determined by the Compare template parameter class.

Parameters

info	The information to search for.

Returns: A pointer to the node if found, or nullptr otherwise.

Definition at line 220 of file tpl_indexNode.H.

References Aleph::maps(), and Aleph::IndexNode< GT, Compare, Tree, SN >::search().

◆ search() [2/2]

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

GT_Node * Aleph::IndexNode< GT, Compare, Tree, SN >::search ( GT_Node * p )

inline

Searches for a node based on the content of p.

Note that the search criterion is determined by the Compare template parameter class.

Parameters

p	The node whose information is to be searched for.

Returns: A pointer to the node if found, or nullptr otherwise.

Definition at line 201 of file tpl_indexNode.H.

References Aleph::IndexNode< GT, Compare, Tree, SN >::index, and Aleph::maps().

Referenced by Aleph::IndexNode< GT, Compare, Tree, SN >::build_index(), and Aleph::IndexNode< GT, Compare, Tree, SN >::search().

◆ size()

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

size_t Aleph::IndexNode< GT, Compare, Tree, SN >::size ( ) const

inline

Returns the number of items contained in the index.

Definition at line 291 of file tpl_indexNode.H.

References Aleph::IndexNode< GT, Compare, Tree, SN >::index.

Member Data Documentation

◆ g

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

GT& Aleph::IndexNode< GT, Compare, Tree, SN >::g

private

Definition at line 135 of file tpl_indexNode.H.

Referenced by Aleph::IndexNode< GT, Compare, Tree, SN >::build_index(), Aleph::IndexNode< GT, Compare, Tree, SN >::clear_graph(), Aleph::IndexNode< GT, Compare, Tree, SN >::init(), Aleph::IndexNode< GT, Compare, Tree, SN >::insert_in_graph(), Aleph::IndexNode< GT, Compare, Tree, SN >::insert_in_graph(), and Aleph::IndexNode< GT, Compare, Tree, SN >::remove_from_graph().

◆ index

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

DynSetTree<GT_Node*, Tree, Compare> Aleph::IndexNode< GT, Compare, Tree, SN >::index

private

Definition at line 133 of file tpl_indexNode.H.

Referenced by Aleph::IndexNode< GT, Compare, Tree, SN >::clear_index(), Aleph::IndexNode< GT, Compare, Tree, SN >::insert(), Aleph::IndexNode< GT, Compare, Tree, SN >::remove(), Aleph::IndexNode< GT, Compare, Tree, SN >::remove_from_graph(), Aleph::IndexNode< GT, Compare, Tree, SN >::search(), and Aleph::IndexNode< GT, Compare, Tree, SN >::size().

◆ sn

template<class GT , class Compare = Dft_Node_Cmp<GT>, template< class, class > class Tree = Treap, class SN = Dft_Show_Node<GT>>

SN Aleph::IndexNode< GT, Compare, Tree, SN >::sn

private

Definition at line 136 of file tpl_indexNode.H.

Referenced by Aleph::IndexNode< GT, Compare, Tree, SN >::build_index(), and Aleph::IndexNode< GT, Compare, Tree, SN >::init().

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

tpl_indexNode.H

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ GT_Node

◆ GT_Node_Type

Constructor & Destructor Documentation

◆ IndexNode()

Member Function Documentation

◆ build_index()

◆ clear_graph()

◆ clear_index()

◆ init()

◆ insert()

◆ insert_in_graph() [1/2]

◆ insert_in_graph() [2/2]

◆ remove()

◆ remove_from_graph()

◆ search() [1/2]

◆ search() [2/2]

◆ size()

Member Data Documentation

◆ g

◆ index

◆ sn