Aleph::Dlink Class Reference

#include <dlink.H>

Inheritance diagram for Aleph::Dlink:

Collaboration diagram for Aleph::Dlink:

Classes
class	Iterator

Public Member Functions
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
	Dlink () noexcept
	Initialize a node or an empty list.
	Dlink (const Dlink &l) noexcept
void	swap (Dlink *link) noexcept
void	swap (Dlink &l) noexcept
	Dlink (Dlink &&l) noexcept
Dlink &	operator= (const Dlink &l) noexcept
Dlink &	operator= (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.

Protected Attributes
Dlink *	prev
Dlink *	next

Detailed Description

Double link of a node belonging to a double circular linked list with header node.

This class implements many operations on double circular linked list with header node.

See also

Macros_Dlink Dlink::Iterator Dnode Dlist DynDlist

Constructor & Destructor Documentation

Dlink() [1/2]

Aleph::Dlink::Dlink ( const Dlink &  l )

inlinenoexcept

Copy constructor. Be very careful because if l contains items, then these will be lost

Here is the call graph for this function:

Dlink() [2/2]

Aleph::Dlink::Dlink ( Dlink &&  l )

inlinenoexcept

Construct a new list with the items of l moved.

This constructor takes a rvalue reference l to a list and moves it in constant time to this

Parameters

[in]

l

rvalue reference to the to be moved

Here is the call graph for this function:

Member Function Documentation

append()

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

inlinenoexcept

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 )

inlinenoexcept

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 )

inlinenoexcept

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 )

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

cut_list()

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

inlinenoexcept

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 ( )

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

init()

void Aleph::Dlink::init ( )

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

Here is the caller graph for this function:

insert()

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

inlinenoexcept

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 )

inlinenoexcept

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:

operator=() [1/2]

Dlink& Aleph::Dlink::operator= ( const Dlink &  l )

inlinenoexcept

Copy assignation

Warning

Be very careful with the possibility of this has items, because these will be lost

Parameters

[in]

l

link to be copied

Here is the call graph for this function:

operator=() [2/2]

Dlink& Aleph::Dlink::operator= ( Dlink &&  l )

inlinenoexcept

Move assignation

Assign a rvalue list to this without copying.

Note

Since l is rvalue reference, take care of that if you are interested in to avoid the copy. So, if you have a lvalue reference to a list, use std::move(), upon your responsability, if and only if you are absolutely sure that the list will not be needed after.

Parameters

[in]

rvalue

reference to list to be copied

Here is the call graph for this function:

pop()

Dlink* Aleph::Dlink::pop ( )

inline

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 )

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

remove_all_and_delete()

void Aleph::Dlink::remove_all_and_delete ( )

inlinenoexcept

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 ( )

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

Here is the caller graph for this function:

remove_first_ne()

Dlink* Aleph::Dlink::remove_first_ne ( )

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

Here is the caller graph for this function:

remove_last()

Dlink* Aleph::Dlink::remove_last ( )

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

Here is the caller graph for this function:

remove_last_ne()

Dlink* Aleph::Dlink::remove_last_ne ( )

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

remove_next()

Dlink* Aleph::Dlink::remove_next ( )

inlinenoexcept

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 ( )

inlinenoexcept

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 ( )

inlinenoexcept

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 ( )

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

Here is the caller graph for this function:

reverse_list()

size_t Aleph::Dlink::reverse_list ( )

inlinenoexcept

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 )

inline

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 )

inline

Analogous to rotate_left() but to right

Here is the call graph for this function:

splice()

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

inlinenoexcept

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  )

inlinenoexcept

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 )

inlinenoexcept

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 )

inlinenoexcept

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 ( )

inline

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 )

inlinenoexcept

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