Dynamic doubly linked list with O(1) size and bidirectional access. More...

#include <tpl_dynDlist.H>

Inheritance diagram for Aleph::DynDlist< T >:

Collaboration diagram for Aleph::DynDlist< T >:

Classes
class	Iterator
	Iterator dynamic list. More...

Public Types
using	Set_Type = DynDlist
	The type of container.

using	Item_Type = T
	The type of element that stores the container.

using	Key_Type = T
	The type of element that stores the container.

Public Types inherited from Aleph::Dnode< T >
using	key_type = T
	The data type.

Public Types inherited from StlAlephIterator< SetName >
using	iterator = StlIterator< SetName >

using	const_iterator = StlConstIterator< SetName >

Public Member Functions
const size_t &	size () const noexcept
	Return the number of elements (constant time)

	DynDlist ()=default

template<template< typename > class List>
	DynDlist (const List< T > &l)

template<class It >
	DynDlist (It b, It e)

	DynDlist (std::initializer_list< T > l)

void	empty () noexcept
	Empty the list.

	~DynDlist ()
	Destructor.

T &	insert (const T &item)
	Insert a copy of item at the beginning of the list.

T &	insert (T &&item)
	Insert a moved item at the beginning of the list.

T &	append (const T &item)
	Append a copied item at the end of the list.

T &	append (T &&item)
	Append a moved item at the end of the list.

void	insert (const DynDlist &list)
	Insert all the elements of `list` before `this`.

void	insert (DynDlist &&list) noexcept

void	append (const DynDlist &list)
	Append all the elements of `list` after `this`.

void	append (DynDlist &&list) noexcept

T &	get_first_ne () const noexcept
	Return a modifiable reference to first item in the list.

T &	get_last_ne () const noexcept
	Return a modifiable reference to last item in the list.

T &	get_first () const
	Return a modifiable reference to first item in the list.

T &	get_last () const
	Return a modifiable reference to last item in the list.

T	remove_first_ne () noexcept
	Remove the first item of the list; return a copy of removed item.

T	remove_last_ne () noexcept
	Remove the last item of the list; return a copy of removed item.

T	remove_first ()
	Remove the first item of the list; return a copy of removed item.

T	remove_last ()
	Remove the last item of the list; return a copy of removed item.

T &	put (const T &item)

T &	put (T &&item)

T	get ()

T &	rear ()
	If `this` was treated as a queue, the it returns the most recently inserted item.

T &	front ()
	If `this` was treated as a queue, the it returns the most oldlest inserted item.

T &	push (const T &item)

T &	push (T &&item)

T	pop ()

T &	top () const

void	remove (T &data) noexcept
	Assuming that data is a reference to the item in the list, it removes the item.

void	erase (T &data) noexcept

void	swap (DynDlist &l) noexcept
	Swap in constant time all the items of `this` with all the items of `l` (very fast!)

void	split_list_ne (DynDlist &l, DynDlist &r) noexcept
	Split the list in two.

void	split_list (DynDlist &l, DynDlist &r)
	Split the list in two.

void	split (DynDlist &l, DynDlist &r)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. Alias for split_list.

DynDlist< T > &	operator= (const DynDlist &list)
	Assignment by copy.

	DynDlist (const DynDlist &list)
	Copy constructor; all items of `list` are copied.

	DynDlist (DynDlist< T > &&list) noexcept
	Move constructor; all items of `list` are moved.

DynDlist< T > &	operator= (DynDlist &&list) noexcept
	Assignment by moving.

T &	operator[] (const size_t n) const
	Return a modifiable reference to the i-th item of the list.

DynDlist &	reverse () noexcept

DynDlist &	rev () noexcept

DynDlist< T >	reverse () const
	Return a reversed copy of `this`

DynDlist< T >	rev () const

Public Member Functions inherited from Aleph::Dnode< T >
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 () noexcept

	Dnode (const T &item)
	Construct a node with a copy of `item`

	Dnode (T &&item)
	Construct a new node with the item moved.

Dnode &	swap (Dnode &p)
	Swap `this` with `p`

	Dnode (const Dnode &node)
	Copy constructor.

	Dnode (Dnode &&node) noexcept
	Move constructor.

Dnode &	operator= (const Dnode &p)
	Copy assigment.

Dnode &	operator= (Dnode &&p)
	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

Public Member Functions inherited from Aleph::Dlink
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.

Public Member Functions inherited from GenericTraverse< Container >
template<class Operation >
bool	traverse (Operation &operation) noexcept(traverse_is_noexcept< Operation >())
	Traverse the container via its iterator and performs a conditioned operation on each item.

template<class Operation >
bool	traverse (Operation &operation) const noexcept(traverse_is_noexcept< Operation >())
	Const overload of `traverse(Operation&)`.

template<class Operation >
bool	traverse (Operation &&operation) const noexcept(traverse_is_noexcept< Operation >())
	Overload of `traverse(Operation&) const` that accepts rvalues.

template<class Operation >
bool	traverse (Operation &&operation) noexcept(traverse_is_noexcept< Operation >())
	Overload of `traverse(Operation&)` that accepts rvalues.

Public Member Functions inherited from SpecialCtors< Container, T >
	SpecialCtors ()=default

	SpecialCtors (const SpecialCtors &)=default

	SpecialCtors (SpecialCtors &&) noexcept

SpecialCtors &	operator= (const SpecialCtors &)

SpecialCtors &	operator= (SpecialCtors &&) noexcept

	SpecialCtors (const Aleph::DynList< T > &l)
	Build the container by inserting all items of list `l`.

template<class It >
	SpecialCtors (It b, It e)
	Construct the container from a range of iterators.

	SpecialCtors (std::initializer_list< T > l)
	Construct the container from an initializer list.

Public Member Functions inherited from LocateFunctions< Container, Type >
auto	get_it () const
	Return a properly initialized iterator positioned at the first item on the container.

auto	get_it (const size_t pos) const
	Return a properly initialized iterator positioned at the `pos` item on the container.

auto	get_itor () const
	Alias of `get_it()`.

Type &	nth_ne (const size_t n) noexcept
	Return the n‑th element without bounds checking.

const Type &	nth_ne (const size_t n) const noexcept
	Const overload of `nth_ne(size_t)`.

Type &	nth (const size_t n)
	Return the n-th item of container.

const Type &	nth (const size_t n) const
	Const overload of `nth(size_t)`.

template<class Operation >
Type *	find_ptr (Operation &operation) noexcept(operation_is_noexcept< Operation >())
	Find a pointer to an item in the container according to a searching criteria.

template<class Operation >
const Type *	find_ptr (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
	Const overload of `find_ptr(Operation&)`.

template<class Operation >
const Type *	find_ptr (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of `find_ptr(Operation&) const` that accepts rvalues.

template<class Operation >
Type *	find_ptr (Operation &&operation) noexcept(operation_is_noexcept< Operation >())
	Overload of `find_ptr(Operation&)` that accepts rvalues.

template<class Operation >
size_t	find_index (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
	Find the position of an item in the container according to a searching criteria.

template<class Operation >
size_t	find_index (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of `find_index(Operation&)` that accepts rvalues.

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &operation) noexcept(operation_is_noexcept< Operation >())
	Safe sequential searching of an item matching a criteria.

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &operation) const noexcept(operation_is_noexcept< Operation >())

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &&operation) noexcept(operation_is_noexcept< Operation >())

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())

Public Member Functions inherited from FunctionalMethods< Container, T >
template<typename ... Args>
void	emplace (Args &&... args)
	Appends a new element into the container by constructing it in-place with the given args.

template<typename ... Args>
void	emplace_end (Args &&... args)

template<typename ... Args>
void	emplace_ins (Args &&... args)
	Insert a new element into the container by constructing it in-place with the given args.

template<typename ... Args>
size_t	ninsert (Args ... args)
	Insert n variadic items.

template<typename ... Args>
size_t	nappend (Args ... args)
	Append n variadic items.

template<class Operation >
void	for_each (Operation &operation)
	Traverse all the container and performs an operation on each element.

template<class Operation >
void	for_each (Operation &operation) const
	Const overload of `for_each(Operation&)`.

template<class Operation >
void	for_each (Operation &&operation) const
	Overload of `for_each(Operation&) const` that accepts rvalues.

template<class Operation >
void	for_each (Operation &&operation)
	Overload of `for_each(Operation&)` that accepts rvalues.

template<class Operation >
void	each (Operation &operation)
	Alias of `for_each(Operation&)`.

template<class Operation >
void	each (Operation &operation) const
	Const alias of `for_each(Operation&)`.

template<class Operation >
void	each (Operation &&operation) const
	Const alias of `for_each(Operation&)` that accepts rvalues.

template<class Operation >
void	each (Operation &&operation)
	Alias of `for_each(Operation&)` that accepts rvalues.

template<class Operation >
void	each (size_t pos, const size_t slice, Operation &operation) const
	Traverse the container starting at `pos` taking one item every `slice`, performing a mutable operation on each visited element.

template<class Operation >
void	each (const size_t pos, const size_t slice, Operation &&operation) const

template<class Operation >
void	mutable_for_each (Operation &operation)

template<class Operation >
void	mutable_for_each (Operation &&operation)

template<class Operation >
bool	all (Operation &operation) const
	Check if all the elements of container satisfy a condition.

template<class Operation >
bool	all (Operation &&operation) const
	Overload of `all(Operation&)` that accepts rvalues.

template<class Operation >
bool	exists (Operation &op) const
	Test for existence in the container of an element satisfying a criteria.

template<class Operation >
bool	exists (Operation &&op) const
	Overload of `exists(Operation&)` that accepts rvalues.

template<typename __T = T, class Operation = Aleph::Dft_Map_Op<T, __T>>
Aleph::DynList< __T >	maps (Operation &op) const
	Map the elements of the container.

template<typename __T = T, class Operation = Aleph::Dft_Map_Op<__T, __T>>
Aleph::DynList< __T >	maps (Operation &&op) const
	Overload of `maps(Operation&)` that accepts rvalues.

template<typename __T = T, class Prop , class Operation >
Aleph::DynList< __T >	maps_if (Prop prop, Operation &op) const
	Conditional mapping of the elements of the container.

template<typename __T = T, class Prop , class Operation >
Aleph::DynList< __T >	maps_if (Prop prop, Operation &&op) const
	Overload of `maps_if(Prop, Operation&)` that accepts rvalues.

Aleph::DynList< T >	to_dynlist () const
	Convert container to DynList.

std::vector< T >	to_vector () const
	Convert container to std::vector.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	foldl (const __T &init, Op &op) const
	Fold the elements of the container to a specific result.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	foldl (const __T &init, Op &&op=Op()) const
	Overload of `foldl(const __T&, Op&)` that accepts rvalues.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	fold_left (const __T &init, Op &op) const
	Alias for foldl with the same accumulator type.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	fold_left (const __T &init, Op &&op=Op()) const
	Overload of `fold_left(const __T&, Op&)` that accepts rvalues.

template<class Operation >
T	fold (const T &init, Operation &operation) const
	Simplified version of foldl() where the folded type is the same type of elements stored in the container.

template<class Operation >
T	fold (const T &init, Operation &&operation) const
	Overload of `fold(const T&, Operation&)` that accepts rvalues.

template<class Operation >
Aleph::DynList< T >	filter (Operation &operation) const
	Filter the elements of a container according to a matching criteria.

template<class Operation >
Aleph::DynList< T >	filter (Operation &&operation) const
	Overload of `filter(Operation&)` that accepts rvalues.

template<class Operation >
Aleph::DynList< const T * >	ptr_filter (Operation &operation) const
	Filter the elements of a container according to a matching criteria and return a pointer to the matched items in the container.

template<class Operation >
Aleph::DynList< const T * >	ptr_filter (Operation &&operation) const
	Overload of `ptr_filter(Operation&)` that accepts rvalues.

template<class Operation >
Aleph::DynList< std::tuple< T, size_t > >	pfilter (Operation &operation) const
	Filter the elements of a container according to a matching criteria and determine its positions respect to the traversal of container.

template<class Operation >
Aleph::DynList< std::tuple< T, size_t > >	pfilter (Operation &&operation) const
	Overload of `pfilter(Operation&)` that accepts rvalues.

template<class Operation >
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &op) const
	Exclusive partition of container according to a filter criteria.

template<class Operation >
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &&op) const
	Overload of `partition(Operation&)` that accepts rvalues.

template<class Operation >
std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (size_t n) const
	Exclusive partition of container in the nth item.

std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	split_half () const
	Split the container into two halves by alternating elements.

template<class Operation >
std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &op) const
	Exclusive partition of container according to a filter criteria.

template<class Operation >
std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &&op) const
	Overload of `tpartition(Operation&)` that accepts rvalues.

size_t	length () const noexcept
	Count the number of elements of a container.

Aleph::DynList< T >	rev () const
	Return a list with the elements of container in reverse order respect to its traversal order.

Aleph::DynList< T >	take (const size_t n) const
	Return a list with the first n elements seen in the container during its traversal.

Aleph::DynList< T >	take (size_t i, const size_t j, const size_t step=1) const
	Return a list with elements seen in the container between i and j position respect to its traversal.

Aleph::DynList< T >	drop (const size_t n) const
	Drop the first n elements seen in the container during its traversal.

void	mutable_drop (const size_t n)
	Drop the first n elements seen from container.

Public Member Functions inherited from GenericItems< Container, T >
Aleph::DynList< T >	items () const
	Return a list of all the elements of a container sorted by traversal order.

Aleph::DynList< T >	keys () const

Public Member Functions inherited from StlAlephIterator< SetName >
iterator	begin () noexcept
	Return an STL-compatible iterator to the first element.

iterator	end () noexcept
	Return an STL-compatible end iterator.

const_iterator	begin () const noexcept
	Return a const iterator to the first element.

const_iterator	end () const noexcept
	Return a const end iterator.

const_iterator	cbegin () const noexcept
	Return a const iterator to the first element.

const_iterator	cend () const noexcept
	Return a const end iterator.

Private Member Functions
T &	__insert (Dnode< T > *p) noexcept

T &	__append (Dnode< T > *p) noexcept

void	__insert (DynDlist< T > &list) noexcept

void	__append (DynDlist< T > &list) noexcept

Private Attributes
size_t	num_elem = 0

Additional Inherited Members
Static Public Member Functions inherited from Aleph::Dnode< T >
static Dnode *	data_to_node (T &data) noexcept
	Given an reference to the data in the node, returns a pointer to the `Dnode` object that contains it.

Protected Attributes inherited from Aleph::Dlink
Dlink *	prev

Dlink *	next

Related Symbols inherited from FunctionalMethods< Container, T >
	each

	each

	each

Detailed Description

template<typename T = int>
class Aleph::DynDlist< T >

Dynamic doubly linked list with O(1) size and bidirectional access.

DynDlist<T> is a doubly linked circular list that maintains a count of elements, enabling O(1) size queries. Unlike DynList (singly linked), DynDlist supports efficient operations at both ends and bidirectional iteration.

This container combines the flexibility of linked lists with a rich set of functional programming operations inherited from FunctionalMethods.

Template Parameters

T	The type of elements stored in the list (default: int).

Complexity:

insert() / append(): O(1)
remove_first() / remove_last(): O(1)
size(): O(1) - maintained by counter
Access by index: O(n)
Search: O(n)

Key Features:

O(1) insertion/removal at both ends
O(1) size query (unlike DynList)
Bidirectional iteration
Comprehensive functional operations (map, filter, fold, etc.)
Support for initializer lists and range construction

Example:: DynDlist<int> list = {1, 2, 3, 4, 5};

// O(1) operations

list.insert(0); // Insert at head

list.append(6); // Insert at tail

auto first = list.remove_first();

auto last = list.remove_last();

// Functional operations

auto doubled = list.maps<int>([](int x) { return x * 2; });

int sum = list.foldl(0, [](int acc, int x) { return acc + x; });

// Bidirectional iteration

for (auto it = list.get_it(); it.has_curr(); it.next())

std::cout << it.get_curr() << " ";

for (auto it = list.get_last_it(); it.has_curr(); it.prev())

std::cout << it.get_curr() << " ";

Aleph::Dlink::prev
Dlink * prev
Definition dlink.H:103

Aleph::DynDlist
Dynamic doubly linked list with O(1) size and bidirectional access.
Definition tpl_dynDlist.H:124

Aleph::DynDlist::remove_last
T remove_last()
Remove the last item of the list; return a copy of removed item.
Definition tpl_dynDlist.H:357

Aleph::DynDlist::append
T & append(const T &item)
Append a copied item at the end of the list.
Definition tpl_dynDlist.H:214

Aleph::DynDlist::insert
T & insert(const T &item)
Insert a copy of item at the beginning of the list.
Definition tpl_dynDlist.H:192

Aleph::DynDlist::remove_first
T remove_first()
Remove the first item of the list; return a copy of removed item.
Definition tpl_dynDlist.H:345

FunctionalMethods::foldl
__T foldl(const __T &init, Op &op) const
Fold the elements of the container to a specific result.
Definition ah-dry.H:1034

FunctionalMethods::maps
Aleph::DynList< __T > maps(Operation &op) const
Map the elements of the container.
Definition ah-dry.H:904

LocateFunctions::get_it
auto get_it() const
Return a properly initialized iterator positioned at the first item on the container.
Definition ah-dry.H:190

Note: The size is maintained automatically, so size() is O(1).; This is a circular doubly linked list with sentinel header.

See also: DynList Singly linked list alternative (no size counter).; Dlink Low-level doubly linked list node.; FunctionalMethods Inherited functional operations.

Definition at line 116 of file tpl_dynDlist.H.

Member Typedef Documentation

◆ Item_Type

template<typename T = int>

using Aleph::DynDlist< T >::Item_Type = T

The type of element that stores the container.

Definition at line 133 of file tpl_dynDlist.H.

◆ Key_Type

template<typename T = int>

using Aleph::DynDlist< T >::Key_Type = T

The type of element that stores the container.

Definition at line 136 of file tpl_dynDlist.H.

◆ Set_Type

template<typename T = int>

using Aleph::DynDlist< T >::Set_Type = DynDlist

The type of container.

Definition at line 130 of file tpl_dynDlist.H.

Constructor & Destructor Documentation

◆ DynDlist() [1/6]

template<typename T = int>

Aleph::DynDlist< T >::DynDlist ( )

default

◆ DynDlist() [2/6]

template<typename T = int>

template<template< typename > class List>

Aleph::DynDlist< T >::DynDlist ( const List< T > & l )

inline

Definition at line 153 of file tpl_dynDlist.H.

◆ DynDlist() [3/6]

template<typename T = int>

template<class It >

Aleph::DynDlist< T >::DynDlist	(	It	b,
		It	e
	)

inline

Definition at line 153 of file tpl_dynDlist.H.

◆ DynDlist() [4/6]

template<typename T = int>

Aleph::DynDlist< T >::DynDlist ( std::initializer_list< T > l )

inline

Definition at line 153 of file tpl_dynDlist.H.

◆ ~DynDlist()

template<typename T = int>

Aleph::DynDlist< T >::~DynDlist ( )

inline

Destructor.

Definition at line 163 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::empty().

◆ DynDlist() [5/6]

template<typename T = int>

Aleph::DynDlist< T >::DynDlist ( const DynDlist< T > & list )

inline

Copy constructor; all items of list are copied.

The construction time is proportional to the number of items of list

Parameters

[in] list to be copied

Exceptions

bad_alloc if there is no enough memory

Definition at line 758 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::append(), Aleph::Dlink::Iterator::has_curr(), Aleph::Dlink::is_empty(), and FunctionalMethods< Container, T >::maps().

◆ DynDlist() [6/6]

template<typename T = int>

Aleph::DynDlist< T >::DynDlist ( DynDlist< T > && list )

inlinenoexcept

Move constructor; all items of list are moved.

The construction time is constant, independently of number of items of list

Parameters

[in] list to be moved

Exceptions

bad_alloc if there is no enough memory

Definition at line 775 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::swap().

Member Function Documentation

◆ __append() [1/2]

template<typename T = int>

T & Aleph::DynDlist< T >::__append ( Dnode< T > * p )

inlineprivatenoexcept

Definition at line 177 of file tpl_dynDlist.H.

References Aleph::Dlink::append(), and Aleph::DynDlist< T >::num_elem.

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

◆ __append() [2/2]

template<typename T = int>

void Aleph::DynDlist< T >::__append ( DynDlist< T > & list )

inlineprivatenoexcept

Definition at line 241 of file tpl_dynDlist.H.

References Aleph::Dlink::append_list(), FunctionalMethods< Container, T >::maps(), and Aleph::DynDlist< T >::num_elem.

◆ __insert() [1/2]

template<typename T = int>

T & Aleph::DynDlist< T >::__insert ( Dnode< T > * p )

inlineprivatenoexcept

Definition at line 170 of file tpl_dynDlist.H.

References Aleph::Dlink::insert(), and Aleph::DynDlist< T >::num_elem.

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

◆ __insert() [2/2]

template<typename T = int>

void Aleph::DynDlist< T >::__insert ( DynDlist< T > & list )

inlineprivatenoexcept

Definition at line 232 of file tpl_dynDlist.H.

References Aleph::Dlink::insert_list(), FunctionalMethods< Container, T >::maps(), and Aleph::DynDlist< T >::num_elem.

◆ append() [1/4]

template<typename T = int>

Aleph::DynDlist< T >::append ( const DynDlist< T > & list )

inline

Append all the elements of list after this.

Parameters

[in] list to insert 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 272 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::__append(), and l.

◆ append() [2/4]

template<typename T = int>

Aleph::DynDlist< T >::append ( const T & item )

inline

Append a copied item at the end of the list.

Parameters

[in] item to be copied and appended at the end of the list

Returns: a modifiable reference to the appended item in the list

Exceptions

bad_alloc if there is no memory for the new item.

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 214 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::__append().

◆ append() [3/4]

template<typename T = int>

void Aleph::DynDlist< T >::append ( DynDlist< T > && list )

inlinenoexcept

Definition at line 279 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::__append().

◆ append() [4/4]

template<typename T = int>

Aleph::DynDlist< T >::append ( T && item )

inline

Append a moved item at the end of the list.

Parameters

[in] item to be moved and appended at the end of the list

Returns: a modifiable reference to the appended item in the list

Exceptions

bad_alloc si no hay memoria para el nuevo elemento.

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 225 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::__append().

◆ empty()

template<typename T = int>

void Aleph::DynDlist< T >::empty ( )

inlinenoexcept

Empty the list.

Definition at line 155 of file tpl_dynDlist.H.

References Aleph::Dlink::is_empty(), FunctionalMethods< Container, T >::maps(), and Aleph::Dnode< T >::remove_next().

Referenced by Aleph::DynDlist< T >::~DynDlist(), Aleph::compute_min_cut(), Aleph::Compute_Cut_Nodes< GT, SA >::cut_nodes(), Aleph::DynDlist< T >::operator=(), TEST(), TEST_F(), and to_dyndlist().

◆ erase()

template<typename T = int>

void Aleph::DynDlist< T >::erase ( T & data )

inlinenoexcept

Definition at line 415 of file tpl_dynDlist.H.

References Aleph::Dnode< T >::data, and Aleph::DynDlist< T >::remove().

Referenced by TEST().

◆ front()

template<typename T = int>

T & Aleph::DynDlist< T >::front ( )

inline

If this was treated as a queue, the it returns the most oldlest inserted item.

Definition at line 379 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::get_first().

Referenced by TEST().

◆ get()

template<typename T = int>

T Aleph::DynDlist< T >::get ( )

inline

Definition at line 371 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::remove_first().

Referenced by TEST().

◆ get_first()

template<typename T = int>

Aleph::DynDlist< T >::get_first ( ) const

inline

Return a modifiable reference to first item in 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 297 of file tpl_dynDlist.H.

References ah_underflow_error_if, Aleph::DynDlist< T >::get_first_ne(), and Aleph::Dlink::is_empty().

Referenced by Aleph::DynDlist< T >::front(), orden_ejecucion(), TEST(), TEST(), TEST(), TEST_F(), and Aleph::DynDlist< T >::top().

◆ get_first_ne()

template<typename T = int>

T & Aleph::DynDlist< T >::get_first_ne ( ) const

inlinenoexcept

Return a modifiable reference to first item in the list.

Definition at line 285 of file tpl_dynDlist.H.

References Aleph::Dnode< T >::get_next().

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

◆ get_last()

template<typename T = int>

T & Aleph::DynDlist< T >::get_last ( ) const

inline

Return a modifiable reference to last item in the list.

Definition at line 305 of file tpl_dynDlist.H.

References ah_underflow_error_if, Aleph::DynDlist< T >::get_last_ne(), and Aleph::Dlink::is_empty().

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

◆ get_last_ne()

template<typename T = int>

T & Aleph::DynDlist< T >::get_last_ne ( ) const

inlinenoexcept

Return a modifiable reference to last item in the list.

Definition at line 291 of file tpl_dynDlist.H.

References Aleph::Dnode< T >::get_prev().

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

◆ insert() [1/4]

template<typename T = int>

Aleph::DynDlist< T >::insert ( const DynDlist< T > & list )

inline

Insert all the elements of list before this.

Parameters

[in] list insert before 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 256 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::__insert(), and l.

◆ insert() [2/4]

template<typename T = int>

T & Aleph::DynDlist< T >::insert ( const T & item )

inline

Insert a copy of item at the beginning of the list.

Parameters

[in] item to be copied and inserted at the beginning

Returns: a modifiable reference to the inserted item in the list

Exceptions

bad_alloc if there is no enough memory

Definition at line 192 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::__insert().

Referenced by Aleph::DynDlist< T >::push(), Aleph::DynDlist< T >::push(), Aleph::DynDlist< T >::reverse(), TEST(), TEST(), TEST(), and TEST_F().

◆ insert() [3/4]

template<typename T = int>

void Aleph::DynDlist< T >::insert ( DynDlist< T > && list )

inlinenoexcept

Definition at line 263 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::__insert().

◆ insert() [4/4]

template<typename T = int>

T & Aleph::DynDlist< T >::insert ( T && item )

inline

Insert a moved item at the beginning of the list.

Parameters

[in] item to be moved and inserted at the beginning of the list

Returns: a modifiable reference to the inserted item in the list

Exceptions

bad_alloc if there is no enough memory

Definition at line 203 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::__insert().

◆ operator=() [1/2]

template<typename T = int>

DynDlist< T > & Aleph::DynDlist< T >::operator= ( const DynDlist< T > & list )

inline

Assignment by copy.

In this assignment this is emptied and the the items of list are copied to this. It takes since time proportional to the size of list more the old size of this

Parameters

[in] list to be copied

Exceptions

bad_alloc if there is no enough memory

Definition at line 737 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::append(), Aleph::DynDlist< T >::empty(), Aleph::Dlink::Iterator::has_curr(), and FunctionalMethods< Container, T >::maps().

◆ operator=() [2/2]

template<typename T = int>

DynDlist< T > & Aleph::DynDlist< T >::operator= ( DynDlist< T > && list )

inlinenoexcept

Assignment by moving.

In this assignment this is swapped with list. So, this takes constant time independently of list sizes.

Parameters

[in] list to be assigned by moving

Exceptions

bad_alloc if there is no enough memory

Definition at line 789 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::swap().

◆ operator[]()

template<typename T = int>

T & Aleph::DynDlist< T >::operator[] ( const size_t n ) const

inline

Return a modifiable reference to the i-th item of the list.

Exceptions

out_of_range if n is greater than or equal to the list size.

Definition at line 797 of file tpl_dynDlist.H.

References ah_out_of_range_error_if, LocateFunctions< Container, Type >::get_it(), and FunctionalMethods< Container, T >::maps().

◆ pop()

template<typename T = int>

T Aleph::DynDlist< T >::pop ( )

inline

Definition at line 388 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::remove_first().

Referenced by TEST().

◆ push() [1/2]

template<typename T = int>

T & Aleph::DynDlist< T >::push ( const T & item )

inline

Definition at line 382 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::insert().

Referenced by TEST().

◆ push() [2/2]

template<typename T = int>

T & Aleph::DynDlist< T >::push ( T && item )

inline

Definition at line 385 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::insert().

◆ put() [1/2]

template<typename T = int>

T & Aleph::DynDlist< T >::put ( const T & item )

inline

Definition at line 365 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::append().

Referenced by Aleph::compute_bipartite(), and TEST().

◆ put() [2/2]

template<typename T = int>

T & Aleph::DynDlist< T >::put ( T && item )

inline

Definition at line 368 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::append().

◆ rear()

template<typename T = int>

T & Aleph::DynDlist< T >::rear ( )

inline

If this was treated as a queue, the it returns the most recently inserted item.

Definition at line 375 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::get_last().

Referenced by TEST().

◆ remove()

template<typename T = int>

Aleph::DynDlist< T >::remove ( T & data )

inlinenoexcept

Assuming that data is a reference to the item in the list, it removes the item.

This method can be more powerful given that allows to remove any item in constant time given a valid reference to it.

Warning: Unpredictable results if the reference is not valid. So be sure that you do not pass a reference to a copy of the item. It must be a reference to the item returned by some accessor methods of this class.

Parameters

[in] data valid reference to the item in 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 406 of file tpl_dynDlist.H.

References Aleph::Dnode< T >::data, Aleph::Dnode< T >::data_to_node(), Aleph::Dlink::del(), and Aleph::DynDlist< T >::num_elem.

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

◆ remove_first()

template<typename T = int>

Aleph::DynDlist< T >::remove_first ( )

inline

Remove the first item of the list; return a copy of removed item.

Returns: a copy of removed item

Exceptions

underflow_error if this is empty

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 345 of file tpl_dynDlist.H.

References ah_underflow_error_if, Aleph::Dlink::is_empty(), and Aleph::DynDlist< T >::remove_first_ne().

Referenced by demo_dynlist(), Aleph::DynDlist< T >::get(), Aleph::DynDlist< T >::pop(), TEST(), and TEST().

◆ remove_first_ne()

template<typename T = int>

T Aleph::DynDlist< T >::remove_first_ne ( )

inlinenoexcept

Remove the first item of the list; return a copy of removed item.

Returns: a copy of removed item

Definition at line 316 of file tpl_dynDlist.H.

References Aleph::Dnode< T >::get_data(), FunctionalMethods< Container, T >::maps(), Aleph::DynDlist< T >::num_elem, and Aleph::Dnode< T >::remove_next().

Referenced by Eepic_Plane::~Eepic_Plane(), and Aleph::DynDlist< T >::remove_first().

◆ remove_last()

template<typename T = int>

T Aleph::DynDlist< T >::remove_last ( )

inline

Remove the last item of the list; return a copy of removed item.

Returns: a copy of removed item

Exceptions

underflow_error if this is empty

Definition at line 357 of file tpl_dynDlist.H.

References ah_underflow_error_if, Aleph::Dlink::is_empty(), and Aleph::DynDlist< T >::remove_last_ne().

Referenced by demo_dynlist(), and TEST().

◆ remove_last_ne()

template<typename T = int>

T Aleph::DynDlist< T >::remove_last_ne ( )

inlinenoexcept

Remove the last item of the list; return a copy of removed item.

Returns: a copy of removed item

Definition at line 330 of file tpl_dynDlist.H.

References Aleph::Dnode< T >::get_data(), FunctionalMethods< Container, T >::maps(), Aleph::DynDlist< T >::num_elem, and Aleph::Dnode< T >::remove_prev().

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

◆ rev() [1/2]

template<typename T = int>

DynDlist< T > Aleph::DynDlist< T >::rev ( ) const

inline

Definition at line 829 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::reverse().

◆ rev() [2/2]

template<typename T = int>

DynDlist & Aleph::DynDlist< T >::rev ( )

inlinenoexcept

Definition at line 815 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::reverse().

◆ reverse() [1/2]

template<typename T = int>

DynDlist< T > Aleph::DynDlist< T >::reverse ( ) const

inline

Return a reversed copy of this

Note: Not confuse with reverse without const, which is mutable

Definition at line 821 of file tpl_dynDlist.H.

References LocateFunctions< Container, Type >::get_it(), Aleph::DynDlist< T >::insert(), and FunctionalMethods< Container, T >::maps().

◆ reverse() [2/2]

template<typename T = int>

DynDlist & Aleph::DynDlist< T >::reverse ( )

inlinenoexcept

Definition at line 809 of file tpl_dynDlist.H.

References Aleph::Dlink::reverse().

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

◆ size()

template<typename T = int>

const size_t & Aleph::DynDlist< T >::size ( ) const

inlinenoexcept

Return the number of elements (constant time)

Definition at line 139 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::num_elem.

Referenced by demo_cut_nodes(), demo_resilience_comparison(), Eepic_Plane::draw(), Aleph::load_digraph(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), and TEST_F().

◆ split()

template<typename T = int>

void Aleph::DynDlist< T >::split	(	DynDlist< T > &	l,
		DynDlist< T > &	r
	)

inline

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

See split_list for parameter documentation.

Definition at line 476 of file tpl_dynDlist.H.

References l, and Aleph::DynDlist< T >::split_list().

Referenced by TEST().

◆ split_list()

template<typename T = int>

void Aleph::DynDlist< T >::split_list	(	DynDlist< T > &	l,
		DynDlist< T > &	r
	)

inline

Split the list in two.

This method takes the first n/2 items of this and puts them, in the same order, in list l. The remainder items are put in list r. After operation this becomes empty. The order of items is preserved through l and r.

Parameters

[out]	l	list containing the first n/2 items (must be empty)
[out]	r	list containing the last n/2 items (must be empty)

Exceptions

domain_error if any of the lists is not empty

Definition at line 467 of file tpl_dynDlist.H.

References ah_domain_error_if, Aleph::Dlink::is_empty(), Aleph::HTList::is_empty(), l, FunctionalMethods< Container, T >::maps(), and Aleph::DynDlist< T >::split_list_ne().

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

◆ split_list_ne()

template<typename T = int>

void Aleph::DynDlist< T >::split_list_ne	(	DynDlist< T > &	l,
		DynDlist< T > &	r
	)

inlinenoexcept

Split the list in two.

This method takes the first n/2 items of this and puts them, in the same order, in list l. The remainder items are put in list r. After operation this becomes empty. The order of items is preserved through l and r.

Parameters

[out]	l	list containing the first n/2 items
[out]	r	list containing the last n/2 items

Exceptions

domain_error any of the lists is not empty

Definition at line 439 of file tpl_dynDlist.H.

References Aleph::count(), l, Aleph::DynDlist< T >::num_elem, and Aleph::Dlink::split_list().

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

◆ swap()

template<typename T = int>

void Aleph::DynDlist< T >::swap ( DynDlist< T > & l )

inlinenoexcept

Swap in constant time all the items of this with all the items of l (very fast!)

Definition at line 422 of file tpl_dynDlist.H.

References l, Aleph::DynDlist< T >::num_elem, and Aleph::Dlink::swap().

Referenced by Aleph::DynDlist< T >::DynDlist(), and Aleph::DynDlist< T >::operator=().

◆ top()

template<typename T = int>

T & Aleph::DynDlist< T >::top ( ) const

inline

Definition at line 391 of file tpl_dynDlist.H.

References Aleph::DynDlist< T >::get_first().

Referenced by TEST().

Member Data Documentation

◆ num_elem

template<typename T = int>

size_t Aleph::DynDlist< T >::num_elem = 0

private

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

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Item_Type

◆ Key_Type

◆ Set_Type

Constructor & Destructor Documentation

◆ DynDlist() [1/6]

◆ DynDlist() [2/6]

◆ DynDlist() [3/6]

◆ DynDlist() [4/6]

◆ ~DynDlist()

◆ DynDlist() [5/6]

◆ DynDlist() [6/6]

Member Function Documentation

◆ __append() [1/2]

◆ __append() [2/2]

◆ __insert() [1/2]

◆ __insert() [2/2]

◆ append() [1/4]

◆ append() [2/4]

◆ append() [3/4]

◆ append() [4/4]

◆ empty()

◆ erase()

◆ front()

◆ get()

◆ get_first()

◆ get_first_ne()

◆ get_last()

◆ get_last_ne()

◆ insert() [1/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]()

◆ pop()

◆ push() [1/2]

◆ push() [2/2]

◆ put() [1/2]

◆ put() [2/2]

◆ rear()

◆ remove()

◆ remove_first()

◆ remove_first_ne()

◆ remove_last()

◆ remove_last_ne()

◆ rev() [1/2]

◆ rev() [2/2]

◆ reverse() [1/2]

◆ reverse() [2/2]

◆ size()

◆ split()

◆ split_list()

◆ split_list_ne()

◆ swap()

◆ top()

Member Data Documentation

◆ num_elem