Doubly linked circular list node. More...

#include <dlink.H>

Inheritance diagram for Aleph::Dlink:

Collaboration diagram for Aleph::Dlink:

Classes
class	Iterator
	Iterator on `Dlink` lists. More...

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
	Copy constructor.

void	swap (Dlink *link) noexcept
	Swap `this` with list whose header is `link`.

void	swap (Dlink &l) noexcept
	Swap `this` with list whose header is `l`.

	Dlink (Dlink &&l) noexcept
	Construct a new list with the items of l moved.

Dlink &	operator= (const Dlink &l) noexcept
	Copy assignation.

Dlink &	operator= (Dlink &&l) noexcept
	Move assignation.

void	reset () noexcept
	Reset `this`

void	init () noexcept

constexpr bool	is_empty () const noexcept
	Return `true` if `this` (as header node) is empty.

constexpr bool	is_unitarian () const noexcept
	Return `true` if `this` (as header node) has exactly one element.

constexpr bool	is_unitarian_or_empty () const noexcept
	Return `true` if `this` (as header node) has zero or one element.

void	insert (Dlink *node) noexcept
	Insert `node` after `this`.

void	push (Dlink *node) noexcept

void	append (Dlink *node) noexcept
	Insert `node` before `this`.

Dlink *&	get_next () const noexcept
	Return the link that is after `this`

Dlink *&	get_prev () const noexcept
	Return the link that is before `this`

constexpr Dlink *&	get_first_ne () const noexcept
	If `this` is a header node, it return the first node of `this`

constexpr Dlink *&	get_last_ne () const noexcept
	If `this` is a header node, it return the last node of `this`

constexpr Dlink *&	get_first () const noexcept
	If `this` is a header node, it return the first node of `this`

constexpr Dlink *&	get_last () const noexcept
	If `this` is a header node, it return the last node of `this`

void	wrap_header (Dlink *l) noexcept
	Wrap a header to a list (without header).

void	insert_list (Dlink *head) noexcept
	Insert the list `head` before `this`

void	append_list (Dlink *head) noexcept
	Insert the list `head` after `this`

void	splice (Dlink *l) noexcept
	Insert a list `l` without header node after the node `this`.

void	concat_list (Dlink *head) noexcept
	Concatenate list `head` to list `this`

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
	Remove the item that is before `this`

Dlink *	remove_next () noexcept
	Remove the item that is after `this`

Dlink *	remove_last_ne () noexcept

Dlink *	remove_first_ne () noexcept

Dlink *	remove_last () noexcept

Dlink *	remove_first () noexcept

Dlink *	top () const

Dlink *	pop ()

size_t	reverse_list () noexcept
	Reverse the list.

size_t	reverse () noexcept

size_t	split_list_ne (Dlink &l, Dlink &r) noexcept
	Split `this` in the middle in two lists.

size_t	split_list (Dlink &l, Dlink &r) noexcept

Dlink	cut_list (Dlink *link) noexcept
	Cut `this` from `link`.

void	remove_all_and_delete () noexcept
	Remove and free memory for all the items of list.

void	rotate_left (size_t n)
	Rotate to left the list n positions.

void	rotate_right (size_t n)
	Analogous to rotate_left() but to right.

bool	check ()
	Return `true` if the list is consistent.

Protected Attributes
Dlink *	prev

Dlink *	next

Detailed Description

Doubly linked circular list node.

Dlink is the fundamental building block for doubly linked circular lists in Aleph-w. Each node contains pointers to its previous and next neighbors, forming a circular structure. An empty list consists of a single sentinel node pointing to itself.

This class provides low-level operations for manipulating the list structure. For a higher-level interface with data storage, see Dnode and DynDlist.

Design Principles:

Circular structure: last->next == first, first->prev == last
Sentinel node: empty list has sentinel->next == sentinel
Intrusive design: nodes can be embedded in other structures

Complexity:

Insert/remove at known position: O(1)
Concatenate two lists: O(1)
Split list: O(1)
Traverse: O(n)

Example:: Dlink header; // sentinel node

Dlink node1, node2, node3;

header.insert_next(&node1); // Insert after header

node1.insert_next(&node2); // Insert after node1

header.insert_prev(&node3); // Insert before header (at end)

// Traverse forward

for (auto it = header.get_next(); it != &header; it = it->get_next())

process(it);

Aleph::Dlink
Doubly linked circular list node.
Definition dlink.H:100

Aleph::Dlink::get_next
Dlink *& get_next() const noexcept
Return the link that is after this
Definition dlink.H:295

Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693

See also: Dnode Node with embedded data.; DynDlist High-level dynamic doubly linked list.; Dlink::Iterator Bidirectional iterator for Dlink lists.

Definition at line 99 of file dlink.H.

Constructor & Destructor Documentation

◆ Dlink() [1/3]

Aleph::Dlink::Dlink ( )

inlinenoexcept

Initialize a node or an empty list.

Definition at line 118 of file dlink.H.

References is_empty(), and Aleph::maps().

◆ Dlink() [2/3]

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

inlinenoexcept

Copy constructor.

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

Definition at line 122 of file dlink.H.

References Aleph::HTList::is_empty(), l, and reset().

◆ Dlink() [3/3]

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

Definition at line 188 of file dlink.H.

References l, and swap().

Member Function Documentation

◆ append()

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

inlinenoexcept

Insert node before this.

Parameters

[in] node pointer to an empty node (it must not be inserted in another list)

Definition at line 282 of file dlink.H.

References Aleph::maps(), next, and prev.

Referenced by List_of_5_nodes::List_of_5_nodes(), Aleph::DynDlist< T >::__append(), Polygon::add_vertex(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::connect_arc(), Polygon::copy_points(), cut_list(), Aleph::dlink_random_search(), Aleph::dlink_random_select(), Aleph::Find_Eulerian_Path< GT, SN, SA >::find_node_sequence(), Aleph::GenLhashTable< Key, BucketType, Cmp >::insert(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::insert(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::Tree_Node< T >::insert_left_sibling(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::insert_node(), Aleph::insert_sorted(), Aleph::quicksort(), rotate_left(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_or_insert(), Aleph::selection_sort(), DlinkRotationTest::SetUp(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::try_insert_arc().

◆ 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

Definition at line 383 of file dlink.H.

References next, prev, and reset().

Referenced by Aleph::DynDlist< T >::__append(), and TEST_F().

◆ check()

bool Aleph::Dlink::check ( )

inline

Return true if the list is consistent.

Definition at line 883 of file dlink.H.

References get_next(), get_prev(), and Aleph::maps().

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ concat_list() [1/2]

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

inlinenoexcept

Definition at line 437 of file dlink.H.

References concat_list().

◆ concat_list() [2/2]

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

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 416 of file dlink.H.

References is_empty(), Aleph::maps(), next, prev, reset(), and swap().

Referenced by concat_list(), Aleph::dlink_random_search(), Aleph::dlink_random_select(), Aleph::quicksort(), and TEST().

◆ 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

Definition at line 613 of file dlink.H.

References append(), del(), is_empty(), Aleph::HTList::is_empty(), Aleph::maps(), next, prev, and swap().

Referenced by Aleph::Tree_Node< T >::insert_left_sibling(), Aleph::Tree_Node< T >::insert_leftmost_child(), TEST_F(), TEST_F(), and TEST_F().

◆ del()

Aleph::Dlink::del ( )

inlinenoexcept

Remove this from the list. this must not be a header node.

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 443 of file dlink.H.

References Aleph::maps(), next, prev, and reset().

Referenced by cut_list(), Aleph::Dlink::Iterator::del(), Aleph::DynDlist< T >::Iterator::del(), Aleph::Dlink::Iterator::del_ne(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::disconnect_arc(), erase(), Aleph::Tree_Node< T >::insert_left_sibling(), Aleph::Tree_Node< T >::insert_leftmost_child(), Aleph::DynDlist< T >::remove(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_arc(), and TEST().

◆ erase()

void Aleph::Dlink::erase ( )

inlinenoexcept

Definition at line 454 of file dlink.H.

References del().

◆ get_first()

constexpr Dlink *& Aleph::Dlink::get_first ( ) const

inlineconstexprnoexcept

If this is a header node, it return the first node of this

Definition at line 315 of file dlink.H.

References next.

Referenced by Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::get_first_arc(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::get_first_node(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ get_first_ne()

constexpr Dlink *& Aleph::Dlink::get_first_ne ( ) const

inlineconstexprnoexcept

If this is a header node, it return the first node of this

Definition at line 309 of file dlink.H.

References next.

◆ get_last()

constexpr Dlink *& Aleph::Dlink::get_last ( ) const

inlineconstexprnoexcept

If this is a header node, it return the last node of this

Definition at line 318 of file dlink.H.

References prev.

Referenced by TEST(), TEST(), TEST(), TEST_F(), TEST_F(), and TEST_F().

◆ get_last_ne()

constexpr Dlink *& Aleph::Dlink::get_last_ne ( ) const

inlineconstexprnoexcept

If this is a header node, it return the last node of this

Definition at line 312 of file dlink.H.

References prev.

◆ get_next()

Aleph::Dlink::get_next ( ) const

inlinenoexcept

Return the link that is after this

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 295 of file dlink.H.

References Aleph::maps(), next, and prev.

Referenced by check(), Polygon::get_first_vertex(), Polygon::get_next_vertex(), Aleph::Tree_Node< T >::lower_link(), Aleph::Dlink::Iterator::next_ne(), Vertex::next_vertex(), Aleph::Dlink::Iterator::reset_first(), Aleph::Tree_Node< T >::right_link(), TEST_F(), TEST_F(), and top().

◆ get_prev()

Dlink *& Aleph::Dlink::get_prev ( ) const

inlinenoexcept

Return the link that is before this

Definition at line 302 of file dlink.H.

References Aleph::maps(), next, and prev.

Referenced by check(), Polygon::get_last_vertex(), Polygon::get_prev_vertex(), Aleph::Tree_Node< T >::left_link(), Aleph::Dlink::Iterator::prev_ne(), Vertex::prev_vertex(), Aleph::Dlink::Iterator::reset_last(), TEST_F(), TEST_F(), and Aleph::Tree_Node< T >::upper_link().

◆ init()

void Aleph::Dlink::init ( )

inlinenoexcept

Definition at line 240 of file dlink.H.

References reset().

Referenced by Aleph::Graph_Anode< Node_Info >::Graph_Anode(), Aleph::Graph_Anode< Node_Info >::Graph_Anode(), Aleph::Graph_Anode< Node_Info >::Graph_Anode(), Aleph::Graph_Anode< Node_Info >::Graph_Anode(), Aleph::Graph_Anode< Node_Info >::Graph_Anode(), and TEST_F().

◆ insert()

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

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 259 of file dlink.H.

References Aleph::maps(), next, and prev.

Referenced by List_of_5_nodes::List_of_5_nodes(), Aleph::DynDlist< T >::__insert(), Aleph::GraphCopyWithMapping< GT, Tree >::build_copy(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::insert_arc(), Aleph::Tree_Node< T >::insert_left_sibling(), Aleph::Tree_Node< T >::insert_leftmost_child(), Aleph::Tree_Node< T >::insert_right_sibling(), push(), rotate_right(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), and Aleph::Test_Single_Graph< GT, SN, SA >::test_node().

◆ 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

Definition at line 361 of file dlink.H.

References next, prev, and reset().

Referenced by Aleph::DynDlist< T >::__insert(), and splice().

◆ is_empty()

constexpr bool Aleph::Dlink::is_empty ( ) const

inlineconstexprnoexcept

Return true if this (as header node) is empty.

Definition at line 246 of file dlink.H.

References Aleph::maps(), next, and prev.

Referenced by Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::Array_Graph(), Dlink(), Aleph::DynDlist< T >::DynDlist(), Polygon::Vertex_Iterator::Vertex_Iterator(), Eepic_Plane::~Eepic_Plane(), Aleph::DynDlist< T >::Iterator::append_list(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::clear(), concat_list(), cut_list(), Polygon::delete_points(), demo_cut_nodes(), demo_fixing_vulnerabilities(), demo_network_vulnerability(), Aleph::dlink_random_search(), Aleph::dlink_random_select(), Aleph::DynDlist< T >::empty(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty(), Aleph::Dnode< T >::get_first(), Aleph::DynDlist< T >::get_first(), Polygon::get_first_vertex(), Aleph::Dnode< T >::get_last(), Aleph::DynDlist< T >::get_last(), Polygon::get_last_vertex(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::insert(), Aleph::DynDlist< T >::Iterator::insert_list(), Aleph::Dlink::Iterator::is_in_first(), Aleph::Dlink::Iterator::is_last(), Aleph::GenLhashTable< Key, BucketType, Cmp >::Iterator::locate_next_available_entry(), Aleph::GenLhashTable< Key, BucketType, Cmp >::Iterator::locate_next_available_entry_ne(), Aleph::GenLhashTable< Key, BucketType, Cmp >::Iterator::locate_prev_available_entry(), Aleph::GenLhashTable< Key, BucketType, Cmp >::Iterator::locate_prev_available_entry_ne(), Vertex::next_vertex(), operator=(), pop(), Vertex::prev_vertex(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::print(), Aleph::quicksort(), remove_all_and_delete(), Aleph::Dnode< T >::remove_first(), Aleph::DynDlist< T >::remove_first(), Aleph::Dnode< T >::remove_last(), Aleph::DynDlist< T >::remove_last(), remove_next(), remove_prev(), reverse_list(), rotate_left(), rotate_right(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search_or_insert(), Aleph::selection_sort(), splice(), Aleph::DynDlist< T >::split_list(), split_list_ne(), swap(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), top(), and wrap_header().

◆ is_unitarian()

constexpr bool Aleph::Dlink::is_unitarian ( ) const

inlineconstexprnoexcept

Return true if this (as header node) has exactly one element.

Definition at line 249 of file dlink.H.

References Aleph::maps(), next, and prev.

Referenced by Vertex::next_vertex(), Vertex::prev_vertex(), TEST(), TEST(), TEST(), TEST(), and TEST_F().

◆ is_unitarian_or_empty()

constexpr bool Aleph::Dlink::is_unitarian_or_empty ( ) const

inlineconstexprnoexcept

Return true if this (as header node) has zero or one element.

Definition at line 252 of file dlink.H.

References next, and prev.

Referenced by Polygon::Segment_Iterator::Segment_Iterator(), Polygon::get_first_segment(), Polygon::get_last_segment(), Aleph::quicksort(), TEST(), TEST(), and TEST().

◆ 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

Definition at line 200 of file dlink.H.

References is_empty(), Aleph::HTList::is_empty(), l, Aleph::maps(), next, and prev.

◆ operator=() [2/2]

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

inlinenoexcept

Move assignation.

Assign a rvalue list to this without copying.

Parameters

[in] l rvalue reference to the list to move from.

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.

Definition at line 222 of file dlink.H.

References l, and swap().

◆ pop()

Dlink * Aleph::Dlink::pop ( )

inline

Definition at line 530 of file dlink.H.

References ah_underflow_error_if, is_empty(), and remove_next().

Referenced by TEST().

◆ push()

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

inlinenoexcept

Definition at line 272 of file dlink.H.

References insert().

Referenced by TEST().

◆ 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.

Definition at line 835 of file dlink.H.

References is_empty(), Aleph::maps(), and remove_next().

◆ remove_first()

Dlink * Aleph::Dlink::remove_first ( )

inlinenoexcept

Definition at line 517 of file dlink.H.

References remove_next().

Referenced by Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::clear(), rotate_left(), TEST(), TEST(), TEST(), and TEST().

◆ remove_first_ne()

Dlink * Aleph::Dlink::remove_first_ne ( )

inlinenoexcept

Definition at line 505 of file dlink.H.

References remove_next().

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty().

◆ remove_last()

Dlink * Aleph::Dlink::remove_last ( )

inlinenoexcept

Definition at line 511 of file dlink.H.

References remove_prev().

Referenced by rotate_right(), TEST(), and TEST().

◆ remove_last_ne()

Dlink * Aleph::Dlink::remove_last_ne ( )

inlinenoexcept

Definition at line 499 of file dlink.H.

References remove_prev().

◆ remove_next()

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.

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 488 of file dlink.H.

References is_empty(), Aleph::maps(), and next.

Referenced by List_of_5_nodes::~List_of_5_nodes(), Polygon::delete_points(), Aleph::dlink_random_search(), Aleph::dlink_random_select(), pop(), Aleph::quicksort(), remove_all_and_delete(), remove_first(), remove_first_ne(), Aleph::Dnode< T >::remove_first_ne(), Aleph::Dnode< T >::remove_next(), reverse_list(), and split_list_ne().

◆ remove_prev()

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.

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 467 of file dlink.H.

References is_empty(), Aleph::maps(), and prev.

Referenced by remove_last(), remove_last_ne(), Aleph::Dnode< T >::remove_last_ne(), Aleph::Dnode< T >::remove_prev(), and split_list_ne().

◆ reset()

Aleph::Dlink::reset ( )

inlinenoexcept

Reset this

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

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 234 of file dlink.H.

References next, and prev.

Referenced by Dlink(), append_list(), concat_list(), del(), init(), insert_list(), swap(), and TEST_F().

◆ reverse()

size_t Aleph::Dlink::reverse ( )

inlinenoexcept

Definition at line 556 of file dlink.H.

References reverse_list().

Referenced by Aleph::DynDlist< T >::reverse().

◆ reverse_list()

Aleph::Dlink::reverse_list ( )

inlinenoexcept

Reverse the list.

Returns: the number of items that has the list

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 540 of file dlink.H.

References Aleph::DynList< T >::insert(), is_empty(), Aleph::maps(), remove_next(), and swap().

Referenced by reverse(), TEST(), TEST(), TEST(), and TEST().

◆ 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

Definition at line 855 of file dlink.H.

References ah_domain_error, append(), is_empty(), and remove_first().

Referenced by TEST(), TEST(), TEST(), and TEST_F().

◆ rotate_right()

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

inline

Analogous to rotate_left() but to right.

Definition at line 869 of file dlink.H.

References ah_domain_error, insert(), is_empty(), and remove_last().

Referenced by TEST(), and TEST_F().

◆ 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

Definition at line 399 of file dlink.H.

References insert_list(), is_empty(), l, Aleph::maps(), and wrap_header().

◆ split_list()

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

inlinenoexcept

Definition at line 589 of file dlink.H.

References l, and split_list_ne().

Referenced by Aleph::DynDlist< T >::split_list_ne(), TEST(), TEST(), and TEST().

◆ 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 and r must be empty before calling this method.

Parameters

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

Returns: total number of nodes of both lists (which is the same number of nodes that this had before the split)

Definition at line 571 of file dlink.H.

References Aleph::DynList< T >::append(), Aleph::count(), is_empty(), Aleph::HTList::is_empty(), l, Aleph::maps(), remove_next(), and remove_prev().

Referenced by split_list().

◆ swap() [1/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

Definition at line 176 of file dlink.H.

References l, and swap().

◆ swap() [2/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

Definition at line 137 of file dlink.H.

References is_empty(), Aleph::HTList::is_empty(), Aleph::maps(), next, prev, and reset().

Referenced by Dlink(), Polygon::Polygon(), concat_list(), cut_list(), Aleph::dlink_random_search(), operator=(), Polygon::operator=(), reverse_list(), Aleph::selection_sort(), Aleph::Array_Graph< __Graph_Node, __Graph_Arc >::swap(), swap(), Aleph::Dnode< T >::swap(), Aleph::DynDlist< T >::swap(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::swap(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::swap(), Aleph::Net_Graph< NodeT, ArcT >::swap(), TEST(), TEST(), and TEST_F().

◆ to_data() [1/2]

template<typename T >

const T & Aleph::Dlink::to_data ( ) const

noexcept

Definition at line 322 of file tpl_dnode.H.

References Aleph::maps().

◆ to_data() [2/2]

template<typename T >

T & Aleph::Dlink::to_data ( )

noexcept

Definition at line 317 of file tpl_dnode.H.

References Aleph::maps().

Referenced by TEST().

◆ to_dnode() [1/2]

template<typename T >

const Dnode< T > * Aleph::Dlink::to_dnode ( ) const

noexcept

Definition at line 312 of file tpl_dnode.H.

◆ to_dnode() [2/2]

template<typename T >

Dnode< T > * Aleph::Dlink::to_dnode ( )

noexcept

Definition at line 307 of file tpl_dnode.H.

Referenced by TEST().

◆ top()

Dlink * Aleph::Dlink::top ( ) const

inline

Definition at line 523 of file dlink.H.

References ah_underflow_error_if, get_next(), and is_empty().

Referenced by TEST().

◆ 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

Definition at line 345 of file dlink.H.

References Aleph::DynList< T >::append(), is_empty(), l, and Aleph::maps().

Referenced by splice().

Member Data Documentation

◆ next

Dlink* Aleph::Dlink::next

mutableprotected

Definition at line 104 of file dlink.H.

Referenced by append(), append_list(), concat_list(), cut_list(), del(), get_first(), get_first_ne(), get_next(), Aleph::Dnode< T >::get_next(), get_prev(), insert(), insert_list(), is_empty(), Aleph::Dlink::Iterator::is_in_first(), is_unitarian(), is_unitarian_or_empty(), operator=(), remove_next(), reset(), and swap().

◆ prev

Dlink* Aleph::Dlink::prev

mutableprotected

Definition at line 103 of file dlink.H.

Referenced by append(), append_list(), concat_list(), cut_list(), del(), get_last(), get_last_ne(), get_next(), get_prev(), Aleph::Dnode< T >::get_prev(), insert(), insert_list(), is_empty(), Aleph::Dlink::Iterator::is_last(), is_unitarian(), is_unitarian_or_empty(), operator=(), remove_prev(), reset(), and swap().

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

Classes

Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Dlink() [1/3]

◆ Dlink() [2/3]

◆ Dlink() [3/3]

Member Function Documentation

◆ append()

◆ append_list()

◆ check()

◆ concat_list() [1/2]

◆ concat_list() [2/2]

◆ cut_list()

◆ del()

◆ erase()

◆ get_first()

◆ get_first_ne()

◆ get_last()

◆ get_last_ne()

◆ get_next()

◆ get_prev()

◆ init()

◆ insert()

◆ insert_list()

◆ is_empty()

◆ is_unitarian()

◆ is_unitarian_or_empty()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ pop()

◆ push()

◆ remove_all_and_delete()

◆ remove_first()

◆ remove_first_ne()

◆ remove_last()

◆ remove_last_ne()

◆ remove_next()

◆ remove_prev()

◆ reset()

◆ reverse()

◆ reverse_list()

◆ rotate_left()

◆ rotate_right()

◆ splice()

◆ split_list()

◆ split_list_ne()

◆ swap() [1/2]

◆ swap() [2/2]

◆ to_data() [1/2]

◆ to_data() [2/2]

◆ to_dnode() [1/2]

◆ to_dnode() [2/2]

◆ top()

◆ wrap_header()

Member Data Documentation

◆ next

◆ prev