Aleph::Graph_Node< __Node_Info > Struct Template Reference

#include <tpl_graph.H>

Inheritance diagram for Aleph::Graph_Node< __Node_Info >:

Collaboration diagram for Aleph::Graph_Node< __Node_Info >:

Public Types
using	Base = GTNodeCommon< __Node_Info >
using	Node_Info = __Node_Info
using	Item_Type = __Node_Info
using	Node = GTNodeCommon
	Common alias for set types.
using	Node_Type = __Node_Info
	The node.

Public Member Functions
	Graph_Node (const Node_Info &info) noexcept
	The type of data stored in the node. More...
	Graph_Node (Node_Info &&info=Node_Info()) noexcept
	Graph_Node (const Graph_Node &node) noexcept
Graph_Node &	operator= (const Graph_Node &node) noexcept(std::is_nothrow_copy_assignable< Node_Info >::value)
	Graph_Node (Graph_Node *node) noexcept(std::is_nothrow_copy_assignable< Node_Info >::value)
template<typename T >
Dnode< T > *	to_dnode () noexcept
template<typename T >
const Dnode< T > *	to_dnode () const noexcept
template<typename T >
T &	to_data () noexcept
template<typename T >
const T &	to_data () const noexcept
void	swap (Dlink *link) noexcept
void	swap (Dlink &l) noexcept
void	reset () noexcept
void	init () noexcept
bool	is_empty () const noexcept
	Return true if this (as header node) is empty.
bool	is_unitarian () const noexcept
	Return true if this (as header node) has exactly one element.
bool	is_unitarian_or_empty () const noexcept
	Return true if this (as header node) has zeor or one element.
void	insert (Dlink *node) noexcept
void	push (Dlink *node) noexcept
void	append (Dlink *node) noexcept
Dlink *&	get_next () const noexcept
	Return the link that is after this
Dlink *&	get_prev () const noexcept
	Return the link that is before this
Dlink *&	get_first_ne () const noexcept
	If this is a header node, it return the first node of this
Dlink *&	get_last_ne () const noexcept
	If this is a header node, it return the last node of this
Dlink *&	get_first () const noexcept
	If this is a header node, it return the first node of this
Dlink *&	get_last () const noexcept
	If this is a header node, it return the last node of this
void	wrap_header (Dlink *l) noexcept
void	insert_list (Dlink *head) noexcept
void	append_list (Dlink *head) noexcept
void	splice (Dlink *l) noexcept
void	concat_list (Dlink *head) noexcept
void	concat_list (Dlink &head) noexcept
Dlink *	del () noexcept
	Remove this from the list. this must not be a header node.
void	erase () noexcept
Dlink *	remove_prev () noexcept
Dlink *	remove_next () noexcept
Dlink *	remove_last_ne () noexcept
Dlink *	remove_first_ne () noexcept
Dlink *	remove_last () noexcept
Dlink *	remove_first () noexcept
Dlink *	top ()
Dlink *	pop ()
size_t	reverse_list () noexcept
size_t	reverse () noexcept
size_t	split_list_ne (Dlink &l, Dlink &r) noexcept
size_t	split_list (Dlink &l, Dlink &r) noexcept
Dlink	cut_list (Dlink *link) noexcept
void	remove_all_and_delete () noexcept
void	rotate_left (size_t n)
void	rotate_right (size_t n)
bool	check ()
	Return true if the list is consistent.
__Node_Info &	get_info () noexcept
	Return a modifiable reference to the data contained in the node.
const __Node_Info &	get_info () const noexcept
	Return a constant reference to the data contained in the node.
unsigned int	state () const noexcept
	Return the state's value.
void	set_state (unsigned int s) noexcept
	Set the state to value s

Public Attributes
Dlink	arc_list
Graph_Attr	attrs
__Node_Info	node_info
size_t	num_arcs
	data associated to the node. Access it with get_info() More...

Protected Attributes
Dlink *	prev
Dlink *	next

Friends
class	GTNodeCommon< __Node_Info >
class	Arc_Node

Detailed Description

template<typename __Node_Info = Empty_Class>
struct Aleph::Graph_Node< __Node_Info >

Node belonging to a graph implemented with double linked adjacency list.

This class is used for defining a node of graph implemented with double linked adjacency lists.

Basically, there are three ways for defining the information to be stored in a node:

1. Specifying the data as template parameter of this class.
2. By inheriting from this class and in the derived class to define the data
3. Combination of two above

Note

The purpose of this class is only for specifiying the node of a graph. It is not intended for declaration. Use the internal node subclass instead. Although you could access data and function members of this class, at the exception of get_info() it is not advisable to use them. They are accessible for implementation purposes.

A node has three additional attributes: the control bits, the counter and the cookie.

See also

List_Graph List_Digraph Graph_Arc Bit_Fields

Constructor & Destructor Documentation

Graph_Node() [1/3]

template<typename __Node_Info = Empty_Class>

Aleph::Graph_Node< __Node_Info >::Graph_Node ( const Node_Info &  info )

inlinenoexcept

The type of data stored in the node.

Copy constructor.

Construct a node whose data is copied from info. The control attributes are reset.

Parameters

[in]

info

data to copy to the node

Note

The copy constructor of Node_Info must be defined

Here is the caller graph for this function:

Graph_Node() [2/3]

template<typename __Node_Info = Empty_Class>

Aleph::Graph_Node< __Node_Info >::Graph_Node ( Node_Info &&  info = Node_Info() )

inlinenoexcept

Move or rvalue constructor

Construct a node whose data is moved from info. The control attributes are reset.

Parameters

[in]

info

data to move to the node

Note

The move constructor of Node_Info must be defined

Graph_Node() [3/3]

template<typename __Node_Info = Empty_Class>

Aleph::Graph_Node< __Node_Info >::Graph_Node ( Graph_Node< __Node_Info > *  node )

inlinenoexcept

Constructor copia a partir de un puntero a nodo.

Crea un nodo y le asigna el valor node->get_info() como valor de la información contenida en el nodo.

Los valores de los bits de control y del contador son colocados en cero. El cookie es colocado en nullptr.

Parameters

[in]

node

puntero al nodo desde el cual se desea copiar el valor de información que se desea asignar al nodo recién creado.

Note

Debe estar definido el constructor copia de la clase Node_Info.

La instancia creada es un nodo distinto de node.

Member Function Documentation

append()

void Aleph::Dlink::append ( Dlink *  node )

inlinenoexceptinherited

Insert nodebefore this.

Parameters

[in]

node

pointer to an empty node (it must no be inserted in another list)

Here is the caller graph for this function:

append_list()

void Aleph::Dlink::append_list ( Dlink *  head )

inlinenoexceptinherited

Insert the list head after this

This method assumes that this is a node part of list; it is not the header node. On the other hand, head is the header node of an entire list. So, all the list head is entirely appended, in constant time, after the node this. After append, the list head becomes empty.

Parameters

[in]

head

header for the list to insert

Here is the call graph for this function:

Here is the caller graph for this function:

concat_list() [1/2]

void Aleph::Dlink::concat_list ( Dlink *  head )

inlinenoexceptinherited

Concatenate list head to list this

this and head are both header nodes of lists. concat_list(head) concatenates in constant time all the list head after this. After the concatenation head becomes empty.

Parameters

head	header node of list to concatenate

Here is the call graph for this function:

Here is the caller graph for this function:

concat_list() [2/2]

void Aleph::Dlink::concat_list ( Dlink &  head )

inlinenoexceptinherited

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 call graph for this function:

cut_list()

Dlink Aleph::Dlink::cut_list ( Dlink *  link )

inlinenoexceptinherited

Cut this from link.

cut_list(link) takes a valid link to an item of the list and on that link performs a cut; that is, all the items from link passes to a new list whose head is the return value.

The operation takes constant time.

Warning

Takes in account that the return value is Dlink object, not a pointer.

if link belongs to a list, then this one will be in an inconsistent state.

Parameters

[in]

link

pointer to the item from which the cut will be done

Returns

a Dlink header of a new list containing the items from link

Here is the call graph for this function:

Here is the caller graph for this function:

erase()

void Aleph::Dlink::erase ( )

inlinenoexceptinherited

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 call graph for this function:

init()

void Aleph::Dlink::init ( )

inlinenoexceptinherited

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 call graph for this function:

Here is the caller graph for this function:

insert()

void Aleph::Dlink::insert ( Dlink *  node )

inlinenoexceptinherited

Insert node after this.

Parameters

[in]

node

pointer to an empty node (it must not be linked to nothing

Here is the caller graph for this function:

insert_list()

void Aleph::Dlink::insert_list ( Dlink *  head )

inlinenoexceptinherited

Insert the list head before this

This method assumes that this is a node part of list; it is not the header node. On the other hand, head is the header node of an entire list. So, all the list head is entirely inserted, in constant time, before the node this. After insertion, the list head becomes empty.

Parameters

[in]

head

header for the list to insert

Here is the call graph for this function:

Here is the caller graph for this function:

pop()

Dlink* Aleph::Dlink::pop ( )

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 call graph for this function:

push()

void Aleph::Dlink::push ( Dlink *  node )

inlinenoexceptinherited

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 call graph for this function:

remove_all_and_delete()

void Aleph::Dlink::remove_all_and_delete ( )

inlinenoexceptinherited

Remove and free memory for all the items of list.

remove_all_and_delete() remove each item of the list and call to delete operator on the removed item. At the end of call, all the items were removed, all the memory freed qand the list emptied.

Warning

This method only has sense if the items of list were dynamically allocated with new. Although That is very frequently the case, there are some exceptions. So, be sure that the items were allocated with new operator.

Here is the call graph for this function:

Here is the caller graph for this function:

remove_first()

Dlink* Aleph::Dlink::remove_first ( )

inlinenoexceptinherited

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 call graph for this function:

Here is the caller graph for this function:

remove_first_ne()

Dlink* Aleph::Dlink::remove_first_ne ( )

inlinenoexceptinherited

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 call graph for this function:

Here is the caller graph for this function:

remove_last()

Dlink* Aleph::Dlink::remove_last ( )

inlinenoexceptinherited

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 call graph for this function:

Here is the caller graph for this function:

remove_last_ne()

Dlink* Aleph::Dlink::remove_last_ne ( )

inlinenoexceptinherited

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 call graph for this function:

remove_next()

Dlink* Aleph::Dlink::remove_next ( )

inlinenoexceptinherited

Remove the item that is after this

Remove the item successor of this.

Note

If this is a header node, then this method is equivalent to remove the first node.

Warning

The successor of this must not be a header node.

Returns

a pointer to the removed node.

Here is the call graph for this function:

Here is the caller graph for this function:

remove_prev()

Dlink* Aleph::Dlink::remove_prev ( )

inlinenoexceptinherited

Remove the item that is before this

Remove the item predecessor of this.

Note

If this is a header node, then this method is equivalent to remove the last node.

Warning

The predecessor of this must not be a header node.

Returns

a pointer to the removed node.

Here is the call graph for this function:

Here is the caller graph for this function:

reset()

void Aleph::Dlink::reset ( )

inlinenoexceptinherited

Reset this

reset() reinitialize the node to point to itself. So, all the context is lost. Use with care.

Here is the caller graph for this function:

reverse()

size_t Aleph::Dlink::reverse ( )

inlinenoexceptinherited

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 call graph for this function:

Here is the caller graph for this function:

reverse_list()

size_t Aleph::Dlink::reverse_list ( )

inlinenoexceptinherited

Reverse the list.

Returns

the number of items that has the list

Here is the call graph for this function:

Here is the caller graph for this function:

rotate_left()

void Aleph::Dlink::rotate_left ( size_t  n )

inlineinherited

Rotate to left the list n positions.

rotate_left(n) rotates the items to left n positions. For example, if the list is as follows:

l0, l1, l2, l3, l4, l5, l6, l7, l8, l9

Then rotate_left(4) produces the following state:

l4, l5, l6, l7, l8, l9, l0, l1, l2, l3

Parameters

[in]

n

the number of position to be rotated

Exceptions

domain_error

if list is empty

Here is the call graph for this function:

rotate_right()

void Aleph::Dlink::rotate_right ( size_t  n )

inlineinherited

Analogous to rotate_left() but to right

Here is the call graph for this function:

splice()

void Aleph::Dlink::splice ( Dlink *  l )

inlinenoexceptinherited

Insert a list l without header node after the node this.

Parameters

[in]

l

list without header node to be inserted after this

Here is the call graph for this function:

split_list_ne()

size_t Aleph::Dlink::split_list_ne ( Dlink &  l, Dlink &  r  )

inlinenoexceptinherited

Split this in the middle in two lists.

split_list(l, r) searches the middle of this an on this point cuts the list in two lists l and r respectively. After the operation, this becomes empty.

Note

l

Parameters

[out]	l	first n/2 items of this
[out]	r	last n/2 items of this

Returns

total number of nodes of both list (what is the same number of node that had this before the split

Here is the call graph for this function:

swap() [1/2]

void Aleph::Dlink::swap ( Dlink *  link )

inlinenoexceptinherited

Swap this with list whose header is link.

swap(link) swaps the content og this with all the content of the list pointed by link. The operation is performed in constant time independently of sizes of both lists.

Parameters

[in]

link

pointer to the list to be swapped

Here is the call graph for this function:

Here is the caller graph for this function:

swap() [2/2]

void Aleph::Dlink::swap ( Dlink &  l )

inlinenoexceptinherited

Swap this with list whose header is l.

swap(l) swaps the content og this with all the content of the list referenced by l. The operation is performed in constant time independently of sizes of both lists.

Parameters

[in]

l

list to be swapped with this

Here is the call graph for this function:

top()

Dlink* Aleph::Dlink::top ( )

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 call graph for this function:

wrap_header()

void Aleph::Dlink::wrap_header ( Dlink *  l )

inlinenoexceptinherited

Wrap a header to a list (without header).

Sometimes, especially for low level applications, you coult manage linked list without header nodes. In this case, in order to profit some operations expeting a list with header, you could "wrap" a temporal header and use the list and the operations of this class.

For example, suppose we have a list l without header node and we wish to insert it into a another list with a header node. In this case, we wrap a header to l as follows:

Dlink h;
h.wrap_header(l);

Now, if we have a node p of another list, we could insert l after p as follows:

p->insert_list(&h);

After this operation h becomes empty and the list l is inserted after the node p

Parameters

[in]

l

first node of a double and circular list without header node

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

attrs

Graph_Attr GTNodeCommon< __Node_Info >::attrs

inherited

Attributes of node

See also

Graph_Attr

num_arcs

size_t GTNodeCommon< __Node_Info >::num_arcs

inherited

data associated to the node. Access it with get_info()

Number of arcs.

If the graph is directed, then this field does not have much sense, since it counts the total of arcs (incoming and outcoming).

Warning

Don't modifiy this field (NEVER!). It is public in order to facilitate the implementation of some graph operations.

---

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

• tpl_graph.H