Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::SListPure< E > Class Template Reference

Singly linked lists. More...

#include <ogdf/basic/SList.h>

+ Inheritance diagram for ogdf::SListPure< E >:

Public Types

using const_iterator = SListConstIterator< E >
 Provides a forward 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 iterator = SListIterator< E >
 Provides a forward 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 value_type = E
 Represents the data type stored in a list element. More...
 

Public Member Functions

 SListPure ()
 Constructs an empty singly linked list. More...
 
 SListPure (const SListPure< E > &L)
 Constructs a singly linked list that is a copy of L. More...
 
 SListPure (SListPure< E > &&L)
 Constructs a singly linked list containing the elements of L (move semantics). More...
 
 SListPure (std::initializer_list< E > init)
 Constructs a singly linked list containing the elements in init. More...
 
virtual ~SListPure ()
 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 reference to the first element. More...
 
reference front ()
 Returns a reference to the first element. More...
 
const_reference back () const
 Returns a reference to the last element. More...
 
reference back ()
 Returns a reference to the last element. More...
 
const_iterator get (int pos) const
 Returns an 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 it in the list. More...
 
Iterators

These methods return forward 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...
 
iterator backIterator ()
 Returns an iterator to the last element of the list. More...
 
const_iterator backIterator () const
 Returns a const iterator to the last element of the list. More...
 
const_iterator cyclicSucc (const_iterator it) const
 Returns an iterator to the cyclic successor of it. More...
 
iterator cyclicSucc (iterator it)
 Returns an iterator to the cyclic successor of it. More...
 
Operators

The following operators are provided by lists.

SListPure< E > & operator= (const SListPure< E > &L)
 Assignment operator. More...
 
SListPure< E > & operator= (SListPure< E > &&L)
 Assignment operator (move semantics). More...
 
bool operator== (const SListPure< E > &L) const
 Equality operator. More...
 
bool operator!= (const SListPure< 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 insertAfter (const E &x, iterator itBefore)
 Inserts element x after itBefore. 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 delSucc (iterator itBefore)
 Removes the succesor of itBefore. 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 moveFrontToFront (SListPure< E > &L2)
 Moves the first element of this list to the begin of list L2. More...
 
void moveFrontToBack (SListPure< E > &L2)
 Moves the first element of this list to the end of list L2. More...
 
void moveFrontToSucc (SListPure< E > &L2, iterator itBefore)
 Moves the first element of this list to list L2 inserted after itBefore. More...
 
void conc (SListPure< E > &L2)
 Appends L2 to this list and makes L2 empty. More...
 
void reverse ()
 Reverses the order of the list elements. More...
 
Searching and sorting

These methods provide searching for values and sorting the list.

SListConstIterator< 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...
 
SListIterator< 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 >
SListConstIterator< 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 >
SListIterator< 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...
 
void bucketSort (BucketFunc< E > &f)
 Sorts the list using bucket sort. More...
 

Private Attributes

SListElement< E > * m_head
 Pointer to first element. More...
 
SListElement< 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
 
iterator chooseIterator (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
 
const_reference chooseElement (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
 
reference chooseElement (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
 
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 SListPure< 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 (SListElement< E > *start=nullptr)
 Sets the debug reference of all list elements starting at start to this. More...
 

Detailed Description

template<class E>
class ogdf::SListPure< E >

Singly linked lists.

Use ogdf::SListConstIterator or ogdf::SListIterator in order to iterate over the list.

In contrast to ogdf::SList, instances of ogdf::SListPure do not store the length of the list.

Template Parameters
Eis the data type stored in list elements.

Definition at line 38 of file SList.h.

Member Typedef Documentation

◆ const_iterator

template<class E >
using ogdf::SListPure< E >::const_iterator = SListConstIterator<E>

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

Definition at line 187 of file SList.h.

◆ const_reference

template<class E >
using ogdf::SListPure< 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 185 of file SList.h.

◆ iterator

template<class E >
using ogdf::SListPure< E >::iterator = SListIterator<E>

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

Definition at line 189 of file SList.h.

◆ reference

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

Provides a reference to an element stored in a list.

Definition at line 183 of file SList.h.

◆ value_type

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

Represents the data type stored in a list element.

Definition at line 181 of file SList.h.

Constructor & Destructor Documentation

◆ SListPure() [1/4]

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

Constructs an empty singly linked list.

Definition at line 192 of file SList.h.

◆ SListPure() [2/4]

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

Constructs a singly linked list containing the elements in init.

Definition at line 195 of file SList.h.

◆ SListPure() [3/4]

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

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

Definition at line 200 of file SList.h.

◆ SListPure() [4/4]

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

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

The list L is empty afterwards.

Definition at line 208 of file SList.h.

◆ ~SListPure()

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

Destructor.

Definition at line 213 of file SList.h.

Member Function Documentation

◆ back() [1/2]

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

Returns a reference to the last element.

Precondition
The list is not empty!

Definition at line 267 of file SList.h.

◆ back() [2/2]

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

Returns a reference to the last element.

Precondition
The list is not empty!

Definition at line 258 of file SList.h.

◆ backIterator() [1/2]

template<class E >
iterator ogdf::SListPure< E >::backIterator ( )
inline

Returns an iterator to the last element of the list.

If the list is empty, an invalid iterator is returned.

Definition at line 354 of file SList.h.

◆ backIterator() [2/2]

template<class E >
const_iterator ogdf::SListPure< E >::backIterator ( ) const
inline

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

If the list is empty, an invalid iterator is returned.

Definition at line 360 of file SList.h.

◆ begin() [1/2]

template<class E >
iterator ogdf::SListPure< 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 318 of file SList.h.

◆ begin() [2/2]

template<class E >
const_iterator ogdf::SListPure< 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 324 of file SList.h.

◆ bucketSort() [1/2]

template<class E >
void ogdf::SListPure< E >::bucketSort ( BucketFunc< E > &  f)

Sorts the list using bucket sort.

Definition at line 977 of file SList.h.

◆ bucketSort() [2/2]

template<class E >
void ogdf::SListPure< 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 997 of file SList.h.

◆ cbegin()

template<class E >
const_iterator ogdf::SListPure< 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 330 of file SList.h.

◆ cend()

template<class E >
const_iterator ogdf::SListPure< 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 348 of file SList.h.

◆ chooseElement() [1/2]

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

Definition at line 717 of file SList.h.

◆ chooseElement() [2/2]

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

Definition at line 708 of file SList.h.

◆ chooseIterator() [1/2]

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

Definition at line 701 of file SList.h.

◆ chooseIterator() [2/2]

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

Definition at line 694 of file SList.h.

◆ clear()

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

Removes all elements from the list.

Definition at line 529 of file SList.h.

◆ conc()

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

Appends L2 to this list and makes L2 empty.

Definition at line 598 of file SList.h.

◆ copy()

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

Definition at line 740 of file SList.h.

◆ cyclicSucc() [1/2]

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

Returns an iterator to the cyclic successor of it.

Precondition
it points to an element in this list!

Definition at line 366 of file SList.h.

◆ cyclicSucc() [2/2]

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

Returns an iterator to the cyclic successor of it.

Precondition
it points to an element in this list!

Definition at line 376 of file SList.h.

◆ delSucc()

template<class E >
void ogdf::SListPure< E >::delSucc ( iterator  itBefore)
inline

Removes the succesor of itBefore.

Precondition
itBefore points to an element in this list.

Definition at line 518 of file SList.h.

◆ emplaceBack()

template<class E >
template<class ... Args>
iterator ogdf::SListPure< 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 465 of file SList.h.

◆ emplaceFront()

template<class E >
template<class ... Args>
iterator ogdf::SListPure< 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 444 of file SList.h.

◆ empty()

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

Returns true iff the list is empty.

Definition at line 222 of file SList.h.

◆ end() [1/2]

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

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

This is always a null pointer iterator.

Definition at line 336 of file SList.h.

◆ end() [2/2]

template<class E >
const_iterator ogdf::SListPure< 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 342 of file SList.h.

◆ front() [1/2]

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

Returns a reference to the first element.

Precondition
The list is not empty!

Definition at line 249 of file SList.h.

◆ front() [2/2]

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

Returns a reference to the first element.

Precondition
The list is not empty!

Definition at line 240 of file SList.h.

◆ get() [1/2]

template<class E >
iterator ogdf::SListPure< 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 287 of file SList.h.

◆ get() [2/2]

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

Returns an iterator pointing to the element at position pos.

The running time of this method is linear in pos.

Definition at line 276 of file SList.h.

◆ insertAfter()

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

Inserts element x after itBefore.

Precondition
itBefore references an element in this list.

Definition at line 478 of file SList.h.

◆ moveFrontToBack()

template<class E >
void ogdf::SListPure< E >::moveFrontToBack ( SListPure< E > &  L2)
inline

Moves the first element of this list to the end of list L2.

Definition at line 563 of file SList.h.

◆ moveFrontToFront()

template<class E >
void ogdf::SListPure< E >::moveFrontToFront ( SListPure< E > &  L2)
inline

Moves the first element of this list to the begin of list L2.

Definition at line 549 of file SList.h.

◆ moveFrontToSucc()

template<class E >
void ogdf::SListPure< E >::moveFrontToSucc ( SListPure< E > &  L2,
iterator  itBefore 
)
inline

Moves the first element of this list to list L2 inserted after itBefore.

Precondition
itBefore points to an element in L2.

Definition at line 582 of file SList.h.

◆ operator!=()

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

Inequality operator.

Definition at line 421 of file SList.h.

◆ operator=() [1/2]

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

Assignment operator.

Definition at line 390 of file SList.h.

◆ operator=() [2/2]

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

Assignment operator (move semantics).

The list L is empty afterwards.

Definition at line 399 of file SList.h.

◆ operator==()

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

Equality operator.

Definition at line 409 of file SList.h.

◆ permute() [1/3]

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

Randomly permutes the elements in the list.

Definition at line 726 of file SList.h.

◆ permute() [2/3]

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

Permutes elements in list randomly; n is the length of the list.

Definition at line 1031 of file SList.h.

◆ permute() [3/3]

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

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

Definition at line 733 of file SList.h.

◆ popFront()

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

Removes the first element from the list.

Precondition
The list is not empty!

Definition at line 497 of file SList.h.

◆ popFrontRet()

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

Removes the first element from the list and returns it.

Precondition
The list is not empty!

Definition at line 508 of file SList.h.

◆ pos()

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

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

Positions are numbered 0,1,...

Precondition
it is an iterator pointing to an element in this list.

Definition at line 299 of file SList.h.

◆ pushBack()

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

Adds element x at the end of the list.

Definition at line 451 of file SList.h.

◆ pushFront()

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

Adds element x at the beginning of the list.

Definition at line 433 of file SList.h.

◆ quicksort() [1/2]

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

Sorts the list using Quicksort.

Definition at line 663 of file SList.h.

◆ quicksort() [2/2]

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

Sorts the list using Quicksort and comparer comp.

Definition at line 669 of file SList.h.

◆ reassignListRefs()

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

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

Definition at line 750 of file SList.h.

◆ reverse()

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

Reverses the order of the list elements.

Definition at line 611 of file SList.h.

◆ search() [1/4]

template<class E >
SListIterator<E> ogdf::SListPure< 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 637 of file SList.h.

◆ search() [2/4]

template<class E >
SListConstIterator<E> ogdf::SListPure< 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 629 of file SList.h.

◆ search() [3/4]

template<class E >
template<class COMPARER >
SListIterator<E> ogdf::SListPure< 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 655 of file SList.h.

◆ search() [4/4]

template<class E >
template<class COMPARER >
SListConstIterator<E> ogdf::SListPure< 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 646 of file SList.h.

◆ size()

template<class E >
virtual int ogdf::SListPure< 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 SList instead of SListPure.

Reimplemented in ogdf::SList< E >, ogdf::SList< ogdf::MultiEdgeApproxInserter::VertexBlock >, ogdf::SList< double >, ogdf::SList< ogdf::SimpleCluster * >, ogdf::SList< int >, ogdf::SList< ogdf::NodeElement >, ogdf::SList< ogdf::AdjElement >, ogdf::SList< ogdf::EdgeElement >, and ogdf::Queue< E >.

Definition at line 229 of file SList.h.

Member Data Documentation

◆ m_head

template<class E >
SListElement<E>* ogdf::SListPure< E >::m_head
private

Pointer to first element.

Definition at line 176 of file SList.h.

◆ m_tail

template<class E >
SListElement<E>* ogdf::SListPure< E >::m_tail
private

Pointer to last element.

Definition at line 177 of file SList.h.


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