Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::ListPure< E > Class Template Reference

Doubly linked lists. More...

#include <ogdf/basic/List.h>

Public Types

using const_iterator = ListConstIterator< E >
 Provides a bidirectional iterator that can read a const element in a list. More...
 
using const_reference = const E &
 Provides a reference to a const element stored in a list for reading and performing const operations. More...
 
using const_reverse_iterator = ListConstReverseIterator< E >
 Provides a bidirectional reverse iterator that can read a const element in a list. More...
 
using iterator = ListIterator< E >
 Provides a bidirectional iterator that can read or modify any element in a list. More...
 
using reference = E &
 Provides a reference to an element stored in a list. More...
 
using reverse_iterator = ListReverseIterator< E >
 Provides a bidirectional reverse iterator that can read or modify any element in a list. More...
 
using value_type = E
 Represents the data type stored in a list element. More...
 

Public Member Functions

 ListPure ()
 Constructs an empty doubly linked list. More...
 
 ListPure (const ListPure< E > &L)
 Constructs a doubly linked list that is a copy of L. More...
 
 ListPure (ListPure< E > &&L)
 Constructs a doubly linked list containing the elements of L (move semantics). More...
 
 ListPure (std::initializer_list< E > init)
 Constructs a doubly linked list containing the elements in init. More...
 
virtual ~ListPure ()
 Destructor. More...
 
Access methods

These methods provide simple access without changing the list.

bool empty () const
 Returns true iff the list is empty. More...
 
virtual int size () const
 Returns the number of elements in the list. More...
 
const_reference front () const
 Returns a const reference to the first element. More...
 
reference front ()
 Returns a reference to the first element. More...
 
const_reference back () const
 Returns a const reference to the last element. More...
 
reference back ()
 Returns a reference to the last element. More...
 
const_iterator get (int pos) const
 Returns a const iterator pointing to the element at position pos. More...
 
iterator get (int pos)
 Returns an iterator pointing to the element at position pos. More...
 
int pos (const_iterator it) const
 Returns the position (starting with 0) of iterator it in the list. More...
 
Iterators

These methods return bidirectional iterators to elements in the list and allow to iterate over the elements in linear or cyclic order.

iterator begin ()
 Returns an iterator to the first element of the list. More...
 
const_iterator begin () const
 Returns a const iterator to the first element of the list. More...
 
const_iterator cbegin () const
 Returns a const iterator to the first element of the list. More...
 
iterator end ()
 Returns an iterator to one-past-last element of the list. More...
 
const_iterator end () const
 Returns a const iterator to one-past-last element of the list. More...
 
const_iterator cend () const
 Returns a const iterator to one-past-last element of the list. More...
 
reverse_iterator rbegin ()
 Returns an iterator to the last element of the list. More...
 
const_reverse_iterator rbegin () const
 Returns a const iterator to the last element of the list. More...
 
const_reverse_iterator crbegin () const
 Returns a const iterator to the last element of the list. More...
 
reverse_iterator rend ()
 Returns an iterator to one-before-first element of the list. More...
 
const_reverse_iterator rend () const
 Returns a const iterator to one-before-first element of the list. More...
 
const_reverse_iterator crend () const
 Returns a const iterator to one-before-first element of the list. More...
 
const_iterator cyclicSucc (const_iterator it) const
 Returns a const iterator to the cyclic successor of it. More...
 
iterator cyclicSucc (iterator it)
 Returns an iterator to the cyclic successor of it. More...
 
const_reverse_iterator cyclicSucc (const_reverse_iterator it) const
 
reverse_iterator cyclicSucc (reverse_iterator it)
 
const_iterator cyclicPred (const_iterator it) const
 Returns a const iterator to the cyclic predecessor of it. More...
 
iterator cyclicPred (iterator it)
 Returns an iterator to the cyclic predecessor of it. More...
 
const_reverse_iterator cyclicPred (const_reverse_iterator it) const
 
reverse_iterator cyclicPred (reverse_iterator it)
 
Operators

The following operators are provided by lists.

ListPure< E > & operator= (const ListPure< E > &L)
 Assignment operator. More...
 
ListPure< E > & operator= (ListPure< E > &&L)
 Assignment operator (move semantics). More...
 
bool operator== (const ListPure< E > &L) const
 Equality operator. More...
 
bool operator!= (const ListPure< E > &L) const
 Inequality operator. More...
 
Adding elements

These method add elements to the list.

iterator pushFront (const E &x)
 Adds element x at the beginning of the list. More...
 
template<class ... Args>
iterator emplaceFront (Args &&... args)
 Adds a new element at the beginning of the list. More...
 
iterator pushBack (const E &x)
 Adds element x at the end of the list. More...
 
template<class ... Args>
iterator emplaceBack (Args &&... args)
 Adds a new element at the end of the list. More...
 
iterator insert (const E &x, iterator it, Direction dir=Direction::after)
 Inserts element x before or after it. More...
 
iterator insertBefore (const E &x, iterator it)
 Inserts element x before it. More...
 
iterator insertAfter (const E &x, iterator it)
 Inserts element x after it. More...
 
Removing elements

These method remove elements from the list.

void popFront ()
 Removes the first element from the list. More...
 
popFrontRet ()
 Removes the first element from the list and returns it. More...
 
void popBack ()
 Removes the last element from the list. More...
 
popBackRet ()
 Removes the last element from the list and returns it. More...
 
void del (iterator it)
 Removes it from the list. More...
 
bool removeFirst (const E &x)
 Removes the first occurrence of x (if any) from the list. More...
 
void clear ()
 Removes all elements from the list. More...
 
Moving elements

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

void exchange (iterator it1, iterator it2)
 Exchanges the positions of it1 and it2 in the list. More...
 
void moveToFront (iterator it)
 Moves it to the begin of the list. More...
 
void moveToBack (iterator it)
 Moves it to the end of the list. More...
 
void moveToSucc (iterator it, iterator itBefore)
 Moves it after itBefore. More...
 
void moveToPrec (iterator it, iterator itAfter)
 Moves it before itAfter. More...
 
void moveToFront (iterator it, ListPure< E > &L2)
 Moves it to the begin of L2. More...
 
void moveToBack (iterator it, ListPure< E > &L2)
 Moves it to the end of L2. More...
 
void moveToSucc (iterator it, ListPure< E > &L2, iterator itBefore)
 Moves it to list L2 and inserts it after itBefore. More...
 
void moveToPrec (iterator it, ListPure< E > &L2, iterator itAfter)
 Moves it to list L2 and inserts it before itAfter. More...
 
void conc (ListPure< E > &L2)
 Appends L2 to this list and makes L2 empty. More...
 
void concFront (ListPure< E > &L2)
 Prepends L2 to this list and makes L2 empty. More...
 
void swap (ListPure< E > &other)
 Exchanges the contents of this list and other in constant time. More...
 
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. More...
 
void splitAfter (iterator it, ListPure< E > &L2)
 Splits the list after it. More...
 
void splitBefore (iterator it, ListPure< E > &L2)
 Splits the list before it. More...
 
void reverse ()
 Reverses the order of the list elements. More...
 
Searching and sorting

These methods provide searching for values and sorting the list.

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. More...
 
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. More...
 
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. More...
 
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. More...
 
void quicksort ()
 Sorts the list using Quicksort. More...
 
template<class COMPARER >
void quicksort (const COMPARER &comp)
 Sorts the list using Quicksort and comparer comp. More...
 
void bucketSort (int l, int h, BucketFunc< E > &f)
 Sorts the list using bucket sort. More...
 

Protected Attributes

ListElement< E > * m_head
 Pointer to first element. More...
 
ListElement< E > * m_tail
 Pointer to last element. More...
 

Random elements and permutations

These methods allow to select a random element in the list, or to randomly permute the list.

const_iterator chooseIterator (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
 Returns an iterator to a random element. More...
 
iterator chooseIterator (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
 Returns an iterator to a random element. More...
 
const_reference chooseElement (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
 Returns a random element. More...
 
reference chooseElement (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
 Returns a random element. More...
 
void permute ()
 Randomly permutes the elements in the list. More...
 
template<class RNG >
void permute (RNG &rng)
 Randomly permutes the elements in the list using random number generator rng. More...
 
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 More...
 
void reassignListRefs (ListElement< E > *start=nullptr)
 Sets the debug reference of all list elements starting at start to this. More...
 

Detailed Description

template<class E>
class ogdf::ListPure< E >

Doubly linked lists.

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

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

Template Parameters
Eis the data type stored in list elements.

Definition at line 41 of file List.h.

Member Typedef Documentation

◆ const_iterator

template<class E >
using ogdf::ListPure< E >::const_iterator = ListConstIterator<E>

Provides a bidirectional iterator that can read a const element in a list.

Definition at line 215 of file List.h.

◆ const_reference

template<class E >
using ogdf::ListPure< E >::const_reference = const E&

Provides a reference to a const element stored in a list for reading and performing const operations.

Definition at line 213 of file List.h.

◆ const_reverse_iterator

template<class E >
using ogdf::ListPure< E >::const_reverse_iterator = ListConstReverseIterator<E>

Provides a bidirectional reverse iterator that can read a const element in a list.

Definition at line 219 of file List.h.

◆ iterator

template<class E >
using ogdf::ListPure< E >::iterator = ListIterator<E>

Provides a bidirectional iterator that can read or modify any element in a list.

Definition at line 217 of file List.h.

◆ reference

template<class E >
using ogdf::ListPure< E >::reference = E&

Provides a reference to an element stored in a list.

Definition at line 211 of file List.h.

◆ reverse_iterator

template<class E >
using ogdf::ListPure< E >::reverse_iterator = ListReverseIterator<E>

Provides a bidirectional reverse iterator that can read or modify any element in a list.

Definition at line 221 of file List.h.

◆ value_type

template<class E >
using ogdf::ListPure< E >::value_type = E

Represents the data type stored in a list element.

Definition at line 209 of file List.h.

Constructor & Destructor Documentation

◆ ListPure() [1/4]

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

Constructs an empty doubly linked list.

Definition at line 224 of file List.h.

◆ ListPure() [2/4]

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

Constructs a doubly linked list containing the elements in init.

Definition at line 227 of file List.h.

◆ ListPure() [3/4]

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

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

Definition at line 233 of file List.h.

◆ ListPure() [4/4]

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

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

The list L is empty afterwards.

Definition at line 241 of file List.h.

◆ ~ListPure()

template<class E >
virtual ogdf::ListPure< E >::~ListPure ( )
inlinevirtual

Destructor.

Definition at line 247 of file List.h.

Member Function Documentation

◆ back() [1/2]

template<class E >
reference ogdf::ListPure< E >::back ( )
inline

Returns a reference to the last element.

Precondition
The list is not empty!

Definition at line 302 of file List.h.

◆ back() [2/2]

template<class E >
const_reference ogdf::ListPure< E >::back ( ) const
inline

Returns a const reference to the last element.

Precondition
The list is not empty!

Definition at line 293 of file List.h.

◆ begin() [1/2]

template<class E >
iterator ogdf::ListPure< E >::begin ( )
inline

Returns an iterator to the first element of the list.

If the list is empty, a null pointer iterator is returned.

Definition at line 353 of file List.h.

◆ begin() [2/2]

template<class E >
const_iterator ogdf::ListPure< E >::begin ( ) const
inline

Returns a const iterator to the first element of the list.

If the list is empty, a null pointer iterator is returned.

Definition at line 359 of file List.h.

◆ bucketSort()

template<class E >
void ogdf::ListPure< E >::bucketSort ( int  l,
int  h,
BucketFunc< E > &  f 
)

Sorts the list using bucket sort.

Parameters
lis the lowest bucket that will occur.
his the highest bucket that will occur.
freturns the bucket for each element.
Precondition
The bucket function f will only return bucket values between l and h for this list.

Definition at line 1552 of file List.h.

◆ cbegin()

template<class E >
const_iterator ogdf::ListPure< E >::cbegin ( ) const
inline

Returns a const iterator to the first element of the list.

If the list is empty, a null pointer iterator is returned.

Definition at line 365 of file List.h.

◆ cend()

template<class E >
const_iterator ogdf::ListPure< E >::cend ( ) const
inline

Returns a const iterator to one-past-last element of the list.

This is always a null pointer iterator.

Definition at line 383 of file List.h.

◆ chooseElement() [1/2]

template<class E >
reference ogdf::ListPure< E >::chooseElement ( std::function< bool(const E &)>  includeElement = [](const E&) { return true; },
bool  isFastTest = true 
)
inline

Returns a random element.

Takes linear time.

Precondition
Requires at least one feasible element to exist.
See also
chooseIteratorFrom

Definition at line 1218 of file List.h.

◆ chooseElement() [2/2]

template<class E >
const_reference ogdf::ListPure< E >::chooseElement ( std::function< bool(const E &)>  includeElement = [](const E&) { return true; },
bool  isFastTest = true 
) const
inline

Returns a random element.

Takes linear time.

Precondition
Requires at least one feasible element to exist.
See also
chooseIteratorFrom

Definition at line 1209 of file List.h.

◆ chooseIterator() [1/2]

template<class E >
iterator ogdf::ListPure< E >::chooseIterator ( std::function< bool(const E &)>  includeElement = [](const E&) { return true; },
bool  isFastTest = true 
)
inline

Returns an iterator to a random element.

Takes linear time. An invalid iterator is returned iff no feasible element exists.

See also
chooseIteratorFrom

Definition at line 1195 of file List.h.

◆ chooseIterator() [2/2]

template<class E >
const_iterator ogdf::ListPure< E >::chooseIterator ( std::function< bool(const E &)>  includeElement = [](const E&) { return true; },
bool  isFastTest = true 
) const
inline

Returns an iterator to a random element.

Takes linear time. An invalid iterator is returned iff no feasible element exists.

See also
chooseIteratorFrom

Definition at line 1188 of file List.h.

◆ clear()

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

Removes all elements from the list.

Definition at line 731 of file List.h.

◆ conc()

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

Appends L2 to this list and makes L2 empty.

Definition at line 983 of file List.h.

◆ concFront()

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

Prepends L2 to this list and makes L2 empty.

Definition at line 1000 of file List.h.

◆ copy()

template<class E >
void ogdf::ListPure< E >::copy ( const ListPure< E > &  L)
inlineprotected

Definition at line 1241 of file List.h.

◆ crbegin()

template<class E >
const_reverse_iterator ogdf::ListPure< E >::crbegin ( ) const
inline

Returns a const iterator to the last element of the list.

If the list is empty, a null pointer iterator is returned.

Definition at line 401 of file List.h.

◆ crend()

template<class E >
const_reverse_iterator ogdf::ListPure< E >::crend ( ) const
inline

Returns a const iterator to one-before-first element of the list.

This is always a null pointer iterator.

Definition at line 419 of file List.h.

◆ cyclicPred() [1/4]

template<class E >
const_iterator ogdf::ListPure< E >::cyclicPred ( const_iterator  it) const
inline

Returns a const iterator to the cyclic predecessor of it.

Precondition
it points to an element in this list or to nullptr!

Definition at line 463 of file List.h.

◆ cyclicPred() [2/4]

template<class E >
const_reverse_iterator ogdf::ListPure< E >::cyclicPred ( const_reverse_iterator  it) const
inline

Definition at line 482 of file List.h.

◆ cyclicPred() [3/4]

template<class E >
iterator ogdf::ListPure< E >::cyclicPred ( iterator  it)
inline

Returns an iterator to the cyclic predecessor of it.

Precondition
it points to an element in this list or to nullptr!

Definition at line 473 of file List.h.

◆ cyclicPred() [4/4]

template<class E >
reverse_iterator ogdf::ListPure< E >::cyclicPred ( reverse_iterator  it)
inline

Definition at line 491 of file List.h.

◆ cyclicSucc() [1/4]

template<class E >
const_iterator ogdf::ListPure< E >::cyclicSucc ( const_iterator  it) const
inline

Returns a const iterator to the cyclic successor of it.

Precondition
it points to an element in this list or to nullptr!

Definition at line 425 of file List.h.

◆ cyclicSucc() [2/4]

template<class E >
const_reverse_iterator ogdf::ListPure< E >::cyclicSucc ( const_reverse_iterator  it) const
inline

Definition at line 444 of file List.h.

◆ cyclicSucc() [3/4]

template<class E >
iterator ogdf::ListPure< E >::cyclicSucc ( iterator  it)
inline

Returns an iterator to the cyclic successor of it.

Precondition
it points to an element in this list or to nullptr!

Definition at line 435 of file List.h.

◆ cyclicSucc() [4/4]

template<class E >
reverse_iterator ogdf::ListPure< E >::cyclicSucc ( reverse_iterator  it)
inline

Definition at line 453 of file List.h.

◆ del()

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

Removes it from the list.

Precondition
it points to an element in this list.

Definition at line 705 of file List.h.

◆ emplaceBack()

template<class E >
template<class ... Args>
iterator ogdf::ListPure< 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 586 of file List.h.

◆ emplaceFront()

template<class E >
template<class ... Args>
iterator ogdf::ListPure< 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 562 of file List.h.

◆ empty()

template<class E >
bool ogdf::ListPure< E >::empty ( ) const
inline

Returns true iff the list is empty.

Definition at line 257 of file List.h.

◆ end() [1/2]

template<class E >
iterator ogdf::ListPure< E >::end ( )
inline

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

This is always a null pointer iterator.

Definition at line 371 of file List.h.

◆ end() [2/2]

template<class E >
const_iterator ogdf::ListPure< E >::end ( ) const
inline

Returns a const iterator to one-past-last element of the list.

This is always a null pointer iterator.

Definition at line 377 of file List.h.

◆ exchange()

template<class E >
void ogdf::ListPure< E >::exchange ( iterator  it1,
iterator  it2 
)
inline

Exchanges the positions of it1 and it2 in the list.

Precondition
it1 and it2 point to elements in this list.

Definition at line 754 of file List.h.

◆ front() [1/2]

template<class E >
reference ogdf::ListPure< E >::front ( )
inline

Returns a reference to the first element.

Precondition
The list is not empty!

Definition at line 284 of file List.h.

◆ front() [2/2]

template<class E >
const_reference ogdf::ListPure< E >::front ( ) const
inline

Returns a const reference to the first element.

Precondition
The list is not empty!

Definition at line 275 of file List.h.

◆ get() [1/2]

template<class E >
iterator ogdf::ListPure< E >::get ( int  pos)
inline

Returns an iterator pointing to the element at position pos.

The running time of this method is linear in pos.

Definition at line 322 of file List.h.

◆ get() [2/2]

template<class E >
const_iterator ogdf::ListPure< E >::get ( int  pos) const
inline

Returns a const iterator pointing to the element at position pos.

The running time of this method is linear in pos.

Definition at line 311 of file List.h.

◆ insert()

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

Inserts element x before or after it.

Parameters
xis the element to be inserted.
itis a list iterator in this list.
dirdetermines 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 603 of file List.h.

◆ insertAfter()

template<class E >
iterator ogdf::ListPure< 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 638 of file List.h.

◆ insertBefore()

template<class E >
iterator ogdf::ListPure< 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 624 of file List.h.

◆ moveToBack() [1/2]

template<class E >
void ogdf::ListPure< E >::moveToBack ( iterator  it)
inline

Moves it to the end of the list.

Precondition
it points to an element in this list.

Definition at line 811 of file List.h.

◆ moveToBack() [2/2]

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

Moves it to the end of L2.

Precondition
it points to an element in this list.

Definition at line 907 of file List.h.

◆ moveToFront() [1/2]

template<class E >
void ogdf::ListPure< E >::moveToFront ( iterator  it)
inline

Moves it to the begin of the list.

Precondition
it points to an element in this list.

Definition at line 790 of file List.h.

◆ moveToFront() [2/2]

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

Moves it to the begin of L2.

Precondition
it points to an element in this list.

Definition at line 882 of file List.h.

◆ moveToPrec() [1/2]

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

Moves it before itAfter.

Precondition
it and itAfter point to elements in this list.

Definition at line 857 of file List.h.

◆ moveToPrec() [2/2]

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

Moves it to list L2 and inserts it before itAfter.

Precondition
it points to an element in this list, and itAfter points to an element in L2.

Definition at line 960 of file List.h.

◆ moveToSucc() [1/2]

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

Moves it after itBefore.

Precondition
it and itBefore point to elements in this list.

Definition at line 832 of file List.h.

◆ moveToSucc() [2/2]

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

Moves it to list L2 and inserts it after itBefore.

Precondition
it points to an element in this list, and itBefore points to an element in L2.

Definition at line 933 of file List.h.

◆ operator!=()

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

Inequality operator.

Definition at line 536 of file List.h.

◆ operator=() [1/2]

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

Assignment operator.

Definition at line 505 of file List.h.

◆ operator=() [2/2]

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

Assignment operator (move semantics).

The list L is empty afterwards.

Definition at line 514 of file List.h.

◆ operator==()

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

Equality operator.

Definition at line 524 of file List.h.

◆ permute() [1/3]

template<class E >
void ogdf::ListPure< E >::permute ( )
inline

Randomly permutes the elements in the list.

Definition at line 1227 of file List.h.

◆ permute() [2/3]

template<class E >
template<class RNG >
void ogdf::ListPure< E >::permute ( const int  n,
RNG &  rng 
)
protected

permutes elements in list randomly; n is the length of the list

Definition at line 1585 of file List.h.

◆ permute() [3/3]

template<class E >
template<class RNG >
void ogdf::ListPure< E >::permute ( RNG &  rng)
inline

Randomly permutes the elements in the list using random number generator rng.

Definition at line 1234 of file List.h.

◆ popBack()

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

Removes the last element from the list.

Precondition
The list is not empty!

Definition at line 682 of file List.h.

◆ popBackRet()

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

Removes the last element from the list and returns it.

Precondition
The list is not empty!

Definition at line 695 of file List.h.

◆ popFront()

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

Removes the first element from the list.

Precondition
The list is not empty!

Definition at line 659 of file List.h.

◆ popFrontRet()

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

Removes the first element from the list and returns it.

Precondition
The list is not empty!

Definition at line 672 of file List.h.

◆ pos()

template<class E >
int ogdf::ListPure< E >::pos ( const_iterator  it) const
inline

Returns the position (starting with 0) of iterator it in the list.

Precondition
it is a valid iterator pointing to an element in this list!

Definition at line 333 of file List.h.

◆ pushBack()

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

Adds element x at the end of the list.

Definition at line 572 of file List.h.

◆ pushFront()

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

Adds element x at the beginning of the list.

Definition at line 548 of file List.h.

◆ quicksort() [1/2]

template<class E >
void ogdf::ListPure< E >::quicksort ( )
inline

Sorts the list using Quicksort.

Definition at line 1153 of file List.h.

◆ quicksort() [2/2]

template<class E >
template<class COMPARER >
void ogdf::ListPure< E >::quicksort ( const COMPARER &  comp)
inline

Sorts the list using Quicksort and comparer comp.

Definition at line 1159 of file List.h.

◆ rbegin() [1/2]

template<class E >
reverse_iterator ogdf::ListPure< E >::rbegin ( )
inline

Returns an iterator to the last element of the list.

If the list is empty, a null pointer iterator is returned.

Definition at line 389 of file List.h.

◆ rbegin() [2/2]

template<class E >
const_reverse_iterator ogdf::ListPure< E >::rbegin ( ) const
inline

Returns a const iterator to the last element of the list.

If the list is empty, a null pointer iterator is returned.

Definition at line 395 of file List.h.

◆ reassignListRefs()

template<class E >
void ogdf::ListPure< E >::reassignListRefs ( ListElement< E > *  start = nullptr)
inlineprotected

Sets the debug reference of all list elements starting at start to this.

Definition at line 1252 of file List.h.

◆ removeFirst()

template<class E >
bool ogdf::ListPure< 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 722 of file List.h.

◆ rend() [1/2]

template<class E >
reverse_iterator ogdf::ListPure< E >::rend ( )
inline

Returns an iterator to one-before-first element of the list.

This is always a null pointer iterator.

Definition at line 407 of file List.h.

◆ rend() [2/2]

template<class E >
const_reverse_iterator ogdf::ListPure< E >::rend ( ) const
inline

Returns a const iterator to one-before-first element of the list.

This is always a null pointer iterator.

Definition at line 413 of file List.h.

◆ reverse()

template<class E >
void ogdf::ListPure< E >::reverse ( )
inline

Reverses the order of the list elements.

Definition at line 1100 of file List.h.

◆ search() [1/4]

template<class E >
ListIterator<E> ogdf::ListPure< E >::search ( const E &  e)
inline

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.

Definition at line 1127 of file List.h.

◆ search() [2/4]

template<class E >
ListConstIterator<E> ogdf::ListPure< E >::search ( const E &  e) const
inline

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.

Definition at line 1119 of file List.h.

◆ search() [3/4]

template<class E >
template<class COMPARER >
ListIterator<E> ogdf::ListPure< E >::search ( const E &  e,
const COMPARER &  comp 
)
inline

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.

Definition at line 1145 of file List.h.

◆ search() [4/4]

template<class E >
template<class COMPARER >
ListConstIterator<E> ogdf::ListPure< E >::search ( const E &  e,
const COMPARER &  comp 
) const
inline

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.

Definition at line 1136 of file List.h.

◆ size()

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

Returns the number of elements in the list.

Notice that this method requires to iterate over the whole list and takes linear running time! If you require frequent access to the size of the list, consider using ogdf::List instead of ogdf::ListPure.

Definition at line 264 of file List.h.

◆ split()

template<class E >
void ogdf::ListPure< E >::split ( iterator  it,
ListPure< E > &  L1,
ListPure< 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 1035 of file List.h.

◆ splitAfter()

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

Splits the list after it.

Definition at line 1068 of file List.h.

◆ splitBefore()

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

Splits the list before it.

Definition at line 1084 of file List.h.

◆ swap()

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

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

Definition at line 1017 of file List.h.

Member Data Documentation

◆ m_head

template<class E >
ListElement<E>* ogdf::ListPure< E >::m_head
protected

Pointer to first element.

Definition at line 204 of file List.h.

◆ m_tail

template<class E >
ListElement<E>* ogdf::ListPure< E >::m_tail
protected

Pointer to last element.

Definition at line 205 of file List.h.


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