Aleph::Dnode< T > Class Template Reference

#include <tpl_dnode.H>

Inheritance diagram for Aleph::Dnode< T >:

Collaboration diagram for Aleph::Dnode< T >:

Classes
class	Iterator

Public Types
using	key_type = T
	The data type.

Public Member Functions
Dnode< T > *&	get_next () const noexcept
	Return the next node to this
Dnode< T > *&	get_prev () const noexcept
	Return the previous node to this
Dnode< T > *	remove_prev () noexcept
	Remove the previous node to this; return its address.
Dnode< T > *	remove_next () noexcept
	Remove the next node to this; return its address.
Dnode< T > *&	get_first_ne () const noexcept
	Get the first node.
Dnode< T > *&	get_last_ne () const noexcept
	Get the last node.
Dnode< T > *&	get_first () const
	Get the first node.
Dnode< T > *&	get_last () const
	Get the last node.
Dnode< T > *	remove_last_ne () noexcept
	Remove the last node and return its address.
Dnode< T > *	remove_first_ne () noexcept
	Remove the first node and return its address.
Dnode< T > *	remove_last ()
	Remove the last node and return its address.
Dnode< T > *	remove_first ()
	Remove the first node and return its address.
	Dnode (const T &item) noexcept(noexcept(T(item)))
	Construct a node with a copy of item
	Dnode (T &&item) noexcept(noexcept(std::swap(data, item)))
	Construct a new node with the item moved.
Dnode &	swap (Dnode &p) noexcept(noexcept(std::swap(data, p.data)))
	Swap this with p
	Dnode (const Dnode &node) noexcept(std::is_nothrow_copy_assignable< T >::value)
	Copy constructor.
	Dnode (Dnode &&node) noexcept(noexcept(std::forward< T >(node.data)))
	Move constructor.
Dnode &	operator= (const Dnode &p) noexcept(std::is_nothrow_copy_assignable< T >::value)
	Copy assigment.
Dnode &	operator= (Dnode &&p) noexcept(std::is_nothrow_move_assignable< T >::value)
	Move asignment.
T &	get_data () noexcept
	Return a modifiable reference to the data contained in the node.
const T &	get_data () const noexcept
	Return a modifiable reference to the data contained in the node.
T &	get_key () noexcept
const T &	get_key () const noexcept
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
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 *	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.

Static Public Member Functions
static Dnode *	data_to_node (T &data) noexcept

Protected Attributes
Dlink *	prev
Dlink *	next

Detailed Description

template<typename T>
class Aleph::Dnode< T >

Node belonging to a double circular linked list with header node.

See also

Dnode::Iterator

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:

data_to_node()

template<typename T>

static Dnode* Aleph::Dnode< T >::data_to_node ( T &  data )

inlinestaticnoexcept

Given an reference to the data in the node, returns a pointer to the Dnode object that contains it.

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:

get_key() [1/2]

template<typename T>

T& Aleph::Dnode< T >::get_key ( )

inlinenoexcept

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

get_key() [2/2]

template<typename T>

const T& Aleph::Dnode< T >::get_key ( ) const

inlinenoexcept

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

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:

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:

---

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

• dlink.H
• tpl_dnode.H