# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
ogdf::List< E > Class Template Reference

Doubly linked lists (maintaining the length of the list). More...

#include <ogdf/basic/List.h>

Inheritance diagram for ogdf::List< E >:

## Public Member Functions

List ()
Constructs an empty doubly linked list.

List (const List< E > &L)
Constructs a doubly linked list that is a copy of L.

List (List< E > &&L)
Constructs a doubly linked list containing the elements of L (move semantics).

List (std::initializer_list< E > init)
Constructs a doubly linked list containing the elements in init.

Access methods

These methods provide simple access without changing the list.

int size () const
Returns the number of elements in the list.

const ListPure< E > & getListPure () const
Conversion to const ListPure.

Operators

The following operators are provided by lists.

List< E > & operator= (const List< E > &L)
Assignment operator.

List< E > & operator= (List< E > &&L)
Assignment operator (move semantics).

bool operator== (const List< E > &L) const
Equality operator.

bool operator!= (const List< E > &L) const
Inequality operator.

These method add elements to the list.

iterator pushFront (const E &x)
Adds element x at the beginning of the list.

template<class... Args>
iterator emplaceFront (Args &&... args)
Adds a new element at the beginning of the list.

iterator pushBack (const E &x)
Adds element x at the end of the list.

template<class... Args>
iterator emplaceBack (Args &&... args)
Adds a new element at the end of the list.

iterator insert (const E &x, iterator it, Direction dir=Direction::after)
Inserts element x before or after it.

iterator insertBefore (const E &x, iterator it)
Inserts element x before it.

iterator insertAfter (const E &x, iterator it)
Inserts element x after it.

Removing elements

These method remove elements from the list.

void popFront ()
Removes the first element from the list.

popFrontRet ()
Removes the first element from the list and returns it.

void popBack ()
Removes the last element from the list.

popBackRet ()
Removes the last element from the list and returns it.

void del (iterator it)
Removes it from the list.

bool removeFirst (const E &x)
Removes the first occurrence of x (if any) from the list.

void clear ()
Removes all elements from the list.

Moving elements

The method allow to change the order of elements within the list, or to move elements to another list.

void moveToFront (iterator it, List< E > &L2)
Moves it to the begin of the list.

void moveToBack (iterator it, List< E > &L2)
Moves it to the end of the list.

void moveToSucc (iterator it, List< E > &L2, iterator itBefore)
Moves it after itBefore.

void moveToPrec (iterator it, List< E > &L2, iterator itAfter)
Moves it before itAfter.

void conc (List< E > &L2)
Appends L2 to this list and makes L2 empty.

void concFront (List< E > &L2)
Prepends L2 to this list and makes L2 empty.

void swap (List< E > &other)
Exchanges the contents of this list and other in constant time.

void split (iterator it, List< E > &L1, List< E > &L2, Direction dir=Direction::before)
Splits the list at element it into lists L1 and L2.

## Private Attributes

int m_count
The length of the list.

Private Attributes inherited from ogdf::ListPure< E >
ListElement< E > * m_head
Pointer to first element.

ListElement< E > * m_tail
Pointer to last element.

## Additional Inherited Members

Private Types inherited from ogdf::ListPure< E >
using const_iterator = ListConstIterator< E >
Provides a bidirectional iterator that can read a const element in a list.

using const_reference = const E &
Provides a reference to a const element stored in a list for reading and performing const operations.

using const_reverse_iterator = ListConstReverseIterator< E >
Provides a bidirectional reverse iterator that can read a const element in a list.

using iterator = ListIterator< E >
Provides a bidirectional iterator that can read or modify any element in a list.

using reference = E &
Provides a reference to an element stored in a list.

using reverse_iterator = ListReverseIterator< E >
Provides a bidirectional reverse iterator that can read or modify any element in a list.

using value_type = E
Represents the data type stored in a list element.

Private Member Functions inherited from ogdf::ListPure< E >
ListPure ()
Constructs an empty doubly linked list.

ListPure (const ListPure< E > &L)
Constructs a doubly linked list that is a copy of L.

ListPure (ListPure< E > &&L)
Constructs a doubly linked list containing the elements of L (move semantics).

ListPure (std::initializer_list< E > init)
Constructs a doubly linked list containing the elements in init.

virtual ~ListPure ()
Destructor.

bool empty () const
Returns true iff the list is empty.

const_reference front () const
Returns a const reference to the first element.

reference front ()
Returns a reference to the first element.

const_reference back () const
Returns a const reference to the last element.

reference back ()
Returns a reference to the last element.

const_iterator get (int pos) const
Returns a const iterator pointing to the element at position pos.

iterator get (int pos)
Returns an iterator pointing to the element at position pos.

int pos (const_iterator it) const
Returns the position (starting with 0) of iterator it in the list.

iterator begin ()
Returns an iterator to the first element of the list.

const_iterator begin () const
Returns a const iterator to the first element of the list.

const_iterator cbegin () const
Returns a const iterator to the first element of the list.

iterator end ()
Returns an iterator to one-past-last element of the list.

const_iterator end () const
Returns a const iterator to one-past-last element of the list.

const_iterator cend () const
Returns a const iterator to one-past-last element of the list.

reverse_iterator rbegin ()
Returns an iterator to the last element of the list.

const_reverse_iterator rbegin () const
Returns a const iterator to the last element of the list.

const_reverse_iterator crbegin () const
Returns a const iterator to the last element of the list.

reverse_iterator rend ()
Returns an iterator to one-before-first element of the list.

const_reverse_iterator rend () const
Returns a const iterator to one-before-first element of the list.

const_reverse_iterator crend () const
Returns a const iterator to one-before-first element of the list.

const_iterator cyclicSucc (const_iterator it) const
Returns a const iterator to the cyclic successor of it.

iterator cyclicSucc (iterator it)
Returns an iterator to the cyclic successor of it.

const_reverse_iterator cyclicSucc (const_reverse_iterator it) const
Returns a const iterator to the cyclic successor of it.

reverse_iterator cyclicSucc (reverse_iterator it)
Returns a const iterator to the cyclic successor of it.

const_iterator cyclicPred (const_iterator it) const
Returns a const iterator to the cyclic predecessor of it.

iterator cyclicPred (iterator it)
Returns an iterator to the cyclic predecessor of it.

const_reverse_iterator cyclicPred (const_reverse_iterator it) const
Returns a const iterator to the cyclic predecessor of it.

reverse_iterator cyclicPred (reverse_iterator it)
Returns a const iterator to the cyclic predecessor of it.

ListPure< E > & operator= (const ListPure< E > &L)
Assignment operator.

ListPure< E > & operator= (ListPure< E > &&L)
Assignment operator (move semantics).

bool operator== (const ListPure< E > &L) const
Equality operator.

bool operator!= (const ListPure< E > &L) const
Inequality operator.

iterator pushFront (const E &x)
Adds element x at the beginning of the list.

template<class... Args>
iterator emplaceFront (Args &&... args)
Adds a new element at the beginning of the list.

iterator pushBack (const E &x)
Adds element x at the end of the list.

template<class... Args>
iterator emplaceBack (Args &&... args)
Adds a new element at the end of the list.

iterator insert (const E &x, iterator it, Direction dir=Direction::after)
Inserts element x before or after it.

iterator insertBefore (const E &x, iterator it)
Inserts element x before it.

iterator insertAfter (const E &x, iterator it)
Inserts element x after it.

void popFront ()
Removes the first element from the list.

popFrontRet ()
Removes the first element from the list and returns it.

void popBack ()
Removes the last element from the list.

popBackRet ()
Removes the last element from the list and returns it.

void del (iterator it)
Removes it from the list.

bool removeFirst (const E &x)
Removes the first occurrence of x (if any) from the list.

void clear ()
Removes all elements from the list.

void exchange (iterator it1, iterator it2)
Exchanges the positions of it1 and it2 in the list.

void moveToFront (iterator it)
Moves it to the begin of the list.

void moveToBack (iterator it)
Moves it to the end of the list.

void moveToSucc (iterator it, iterator itBefore)
Moves it after itBefore.

void moveToPrec (iterator it, iterator itAfter)
Moves it before itAfter.

void moveToFront (iterator it, ListPure< E > &L2)
Moves it to the begin of L2.

void moveToBack (iterator it, ListPure< E > &L2)
Moves it to the end of L2.

void moveToSucc (iterator it, ListPure< E > &L2, iterator itBefore)
Moves it to list L2 and inserts it after itBefore.

void moveToPrec (iterator it, ListPure< E > &L2, iterator itAfter)
Moves it to list L2 and inserts it before itAfter.

void conc (ListPure< E > &L2)
Appends L2 to this list and makes L2 empty.

void concFront (ListPure< E > &L2)
Prepends L2 to this list and makes L2 empty.

void swap (ListPure< E > &other)
Exchanges the contents of this list and other in constant time.

void split (iterator it, ListPure< E > &L1, ListPure< E > &L2, Direction dir=Direction::before)
Splits the list at element it into lists L1 and L2.

void splitAfter (iterator it, ListPure< E > &L2)
Splits the list after it.

void splitBefore (iterator it, ListPure< E > &L2)
Splits the list before it.

void reverse ()
Reverses the order of the list elements.

ListConstIterator< E > search (const E &e) const
Scans the list for the specified element and returns an iterator to the first occurrence in the list, or an invalid iterator if not found.

ListIterator< E > search (const E &e)
Scans the list for the specified element and returns an iterator to the first occurrence in the list, or an invalid iterator if not found.

template<class COMPARER >
ListConstIterator< E > search (const E &e, const COMPARER &comp) const
Scans the list for the specified element (using the user-defined comparer) and returns an iterator to the first occurrence in the list, or an invalid iterator if not found.

template<class COMPARER >
ListIterator< E > search (const E &e, const COMPARER &comp)
Scans the list for the specified element (using the user-defined comparer) and returns an iterator to the first occurrence in the list, or an invalid iterator if not found.

void quicksort ()
Sorts the list using Quicksort.

template<class COMPARER >
void quicksort (const COMPARER &comp)
Sorts the list using Quicksort and comparer comp.

void bucketSort (int l, int h, BucketFunc< E > &f)
Sorts the list using bucket sort.

const_iterator chooseIterator (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
Returns an iterator to a random element.

iterator chooseIterator (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
Returns an iterator to a random element.

const_reference chooseElement (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
Returns a random element.

reference chooseElement (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
Returns a random element.

void permute ()
Randomly permutes the elements in the list.

template<class RNG >
void permute (RNG &rng)
Randomly permutes the elements in the list using random number generator rng.

void copy (const ListPure< E > &L)

template<class RNG >
void permute (const int n, RNG &rng)
permutes elements in list randomly; n is the length of the list

void reassignListRefs (ListElement< E > *start=nullptr)
Sets the debug reference of all list elements starting at start to this.

## Detailed Description

template<class E>
class ogdf::List< E >

Doubly linked lists (maintaining the length of the list).

Use ogdf::ListConstIterator or ogdf::ListIterator in order to iterate over the list.

In contrast to ogdf::ListPure, instances of ogdf::List store the length of the list.

Template Parameters
 E is the data type stored in list elements.

Definition at line 1435 of file List.h.

## ◆ List() [1/4]

template<class E >
 ogdf::List< E >::List ( )
inline

Constructs an empty doubly linked list.

Definition at line 1448 of file List.h.

## ◆ List() [2/4]

template<class E >
 ogdf::List< E >::List ( std::initializer_list< E > init )
inline

Constructs a doubly linked list containing the elements in init.

Definition at line 1451 of file List.h.

## ◆ List() [3/4]

template<class E >
 ogdf::List< E >::List ( const List< E > & L )
inline

Constructs a doubly linked list that is a copy of L.

Definition at line 1454 of file List.h.

## ◆ List() [4/4]

template<class E >
 ogdf::List< E >::List ( List< E > && L )
inline

Constructs a doubly linked list containing the elements of L (move semantics).

The list L is empty afterwards.

Definition at line 1460 of file List.h.

## ◆ clear()

template<class E >
 void ogdf::List< E >::clear ( )
inline

Removes all elements from the list.

Definition at line 1610 of file List.h.

## ◆ conc()

template<class E >
 void ogdf::List< E >::conc ( List< E > & L2 )
inline

Appends L2 to this list and makes L2 empty.

Definition at line 1651 of file List.h.

## ◆ concFront()

template<class E >
 void ogdf::List< E >::concFront ( List< E > & L2 )
inline

Prepends L2 to this list and makes L2 empty.

Definition at line 1658 of file List.h.

## ◆ del()

template<class E >
 void ogdf::List< E >::del ( iterator it )
inline

Removes it from the list.

Precondition
it points to an element in this list.

Definition at line 1595 of file List.h.

## ◆ emplaceBack()

template<class E >
template<class... Args>
 iterator ogdf::List< E >::emplaceBack ( Args &&... args )
inline

Adds a new element at the end of the list.

The element is constructed in-place with exactly the same arguments args as supplied to the function.

Definition at line 1538 of file List.h.

## ◆ emplaceFront()

template<class E >
template<class... Args>
 iterator ogdf::List< E >::emplaceFront ( Args &&... args )
inline

Adds a new element at the beginning of the list.

The element is constructed in-place with exactly the same arguments args as supplied to the function.

Definition at line 1525 of file List.h.

## ◆ getListPure()

template<class E >
 const ListPure< E > & ogdf::List< E >::getListPure ( ) const
inline

Conversion to const ListPure.

Definition at line 1475 of file List.h.

## ◆ insert()

template<class E >
 iterator ogdf::List< E >::insert ( const E & x, iterator it, Direction dir = Direction::after )
inline

Inserts element x before or after it.

Parameters
 x is the element to be inserted. it is a list iterator in this list. dir determines if x is inserted before or after it. Possible values are ogdf::before and ogdf::after.
Precondition
it points to an element in this list.

Definition at line 1544 of file List.h.

## ◆ insertAfter()

template<class E >
 iterator ogdf::List< E >::insertAfter ( const E & x, iterator it )
inline

Inserts element x after it.

Precondition
it points to an element in this list.

Definition at line 1556 of file List.h.

## ◆ insertBefore()

template<class E >
 iterator ogdf::List< E >::insertBefore ( const E & x, iterator it )
inline

Inserts element x before it.

Precondition
it points to an element in this list.

Definition at line 1550 of file List.h.

## ◆ moveToBack()

template<class E >
 void ogdf::List< E >::moveToBack ( iterator it, List< E > & L2 )
inline

Moves it to the end of the list.

Precondition
it points to an element in this list.

Definition at line 1630 of file List.h.

## ◆ moveToFront()

template<class E >
 void ogdf::List< E >::moveToFront ( iterator it, List< E > & L2 )
inline

Moves it to the begin of the list.

Precondition
it points to an element in this list.

Definition at line 1623 of file List.h.

## ◆ moveToPrec()

template<class E >
 void ogdf::List< E >::moveToPrec ( iterator it, List< E > & L2, iterator itAfter )
inline

Moves it before itAfter.

Precondition
it and itAfter point to elements in this list.

Definition at line 1644 of file List.h.

## ◆ moveToSucc()

template<class E >
 void ogdf::List< E >::moveToSucc ( iterator it, List< E > & L2, iterator itBefore )
inline

Moves it after itBefore.

Precondition
it and itBefore point to elements in this list.

Definition at line 1637 of file List.h.

## ◆ operator!=()

template<class E >
 bool ogdf::List< E >::operator!= ( const List< E > & L ) const
inline

Inequality operator.

Definition at line 1508 of file List.h.

## ◆ operator=() [1/2]

template<class E >
 List< E > & ogdf::List< E >::operator= ( const List< E > & L )
inline

Assignment operator.

Definition at line 1485 of file List.h.

## ◆ operator=() [2/2]

template<class E >
 List< E > & ogdf::List< E >::operator= ( List< E > && L )
inline

Assignment operator (move semantics).

The list L is empty afterwards.

Definition at line 1495 of file List.h.

## ◆ operator==()

template<class E >
 bool ogdf::List< E >::operator== ( const List< E > & L ) const
inline

Equality operator.

Definition at line 1503 of file List.h.

## ◆ popBack()

template<class E >
 void ogdf::List< E >::popBack ( )
inline

Removes the last element from the list.

Precondition
The list is not empty!

Definition at line 1582 of file List.h.

## ◆ popBackRet()

template<class E >
 E ogdf::List< E >::popBackRet ( )
inline

Removes the last element from the list and returns it.

Precondition
The list is not empty!

Definition at line 1588 of file List.h.

## ◆ popFront()

template<class E >
 void ogdf::List< E >::popFront ( )
inline

Removes the first element from the list.

Precondition
The list is not empty!

Definition at line 1569 of file List.h.

## ◆ popFrontRet()

template<class E >
 E ogdf::List< E >::popFrontRet ( )
inline

Removes the first element from the list and returns it.

Precondition
The list is not empty!

Definition at line 1575 of file List.h.

## ◆ pushBack()

template<class E >
 iterator ogdf::List< E >::pushBack ( const E & x )
inline

Adds element x at the end of the list.

Definition at line 1531 of file List.h.

## ◆ pushFront()

template<class E >
 iterator ogdf::List< E >::pushFront ( const E & x )
inline

Adds element x at the beginning of the list.

Definition at line 1518 of file List.h.

## ◆ removeFirst()

template<class E >
 bool ogdf::List< E >::removeFirst ( const E & x )
inline

Removes the first occurrence of x (if any) from the list.

If the list contains x several times, only the first element containing x is removed.

Returns
true if one element has been removed, false otherwise.

Definition at line 1601 of file List.h.

## ◆ size()

template<class E >
 int ogdf::List< E >::size ( ) const
inlinevirtual

Returns the number of elements in the list.

This method has constant runtime (in contrast to ListPure::size()), since the list maintains the current size.

Reimplemented from ogdf::ListPure< E >.

Reimplemented in ogdf::ListContainer< E, Master >.

Definition at line 1472 of file List.h.

## ◆ split()

template<class E >
 void ogdf::List< E >::split ( iterator it, List< E > & L1, List< E > & L2, Direction dir = Direction::before )
inline

Splits the list at element it into lists L1 and L2.

If it is not a null pointer and L = x1,...,x{k-1}, it,x_{k+1},xn, then L1 = x1,...,x{k-1} and L2 = it,x{k+1},...,xn if dir = Direction::before. If it is a null pointer, then L1 is made empty and L2 = L. Finally L is made empty if it is not identical to L1 or L2.

Precondition
it points to an element in this list.

Definition at line 1671 of file List.h.

## ◆ swap()

template<class E >
 void ogdf::List< E >::swap ( List< E > & other )
inline

Exchanges the contents of this list and other in constant time.

Definition at line 1665 of file List.h.

## ◆ m_count

template<class E >
 int ogdf::List< E >::m_count
private

The length of the list.

Definition at line 1436 of file List.h.

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