Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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. More...
 
 List (const List< E > &L)
 Constructs a doubly linked list that is a copy of L. More...
 
 List (List< E > &&L)
 Constructs a doubly linked list containing the elements of L (move semantics). More...
 
 List (std::initializer_list< E > init)
 Constructs a doubly linked list containing the elements in init. More...
 
Access methods

These methods provide simple access without changing the list.

int size () const
 Returns the number of elements in the list. More...
 
const ListPure< E > & getListPure () const
 Conversion to const ListPure. More...
 
Operators

The following operators are provided by lists.

List< E > & operator= (const List< E > &L)
 Assignment operator. More...
 
List< E > & operator= (List< E > &&L)
 Assignment operator (move semantics). More...
 
bool operator== (const List< E > &L) const
 Equality operator. More...
 
bool operator!= (const List< 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 moveToFront (iterator it, List< E > &L2)
 Moves it to the begin of the list. More...
 
void moveToBack (iterator it, List< E > &L2)
 Moves it to the end of the list. More...
 
void moveToSucc (iterator it, List< E > &L2, iterator itBefore)
 Moves it after itBefore. More...
 
void moveToPrec (iterator it, List< E > &L2, iterator itAfter)
 Moves it before itAfter. More...
 
void conc (List< E > &L2)
 Appends L2 to this list and makes L2 empty. More...
 
void concFront (List< E > &L2)
 Prepends L2 to this list and makes L2 empty. More...
 
void swap (List< E > &other)
 Exchanges the contents of this list and other in constant time. More...
 
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. More...
 

Private Attributes

int m_count
 The length of the list. More...
 

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
Eis the data type stored in list elements.

Definition at line 40 of file List.h.

Constructor & Destructor Documentation

◆ List() [1/4]

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

Constructs an empty doubly linked list.

Definition at line 1287 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 1290 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 1293 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 1299 of file List.h.

Member Function Documentation

◆ clear()

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

Removes all elements from the list.

Definition at line 1452 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 1489 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 1496 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 1438 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 1381 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 1368 of file List.h.

◆ getListPure()

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

Conversion to const ListPure.

Definition at line 1316 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
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 1387 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 1399 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 1393 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 1471 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 1465 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 1483 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 1477 of file List.h.

◆ operator!=()

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

Inequality operator.

Definition at line 1349 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 1326 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 1336 of file List.h.

◆ operator==()

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

Equality operator.

Definition at line 1344 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 1425 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 1431 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 1412 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 1418 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 1374 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 1361 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 1444 of file List.h.

◆ size()

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

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.

Definition at line 1313 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 1509 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 1503 of file List.h.

Member Data Documentation

◆ m_count

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

The length of the list.

Definition at line 1275 of file List.h.


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