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) noexcept
	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...
E	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...
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...

Protected Member Functions
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...

Private Attributes
SListElement< E > *	m_head
	Pointer to first element. More...
SListElement< E > *	m_tail
	Pointer to last element. 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

E	is the data type stored in list elements.

Definition at line 52 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 203 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 201 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 205 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 199 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 197 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 208 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 211 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 218 of file SList.h.

SListPure() [4/4]

template<class E >

ogdf::SListPure< E >::SListPure ( SListPure< E > &&  L )

inlinenoexcept

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

The list L is empty afterwards.

Definition at line 224 of file SList.h.

~SListPure()

template<class E >

virtual ogdf::SListPure< E >::~SListPure ( )

inlinevirtual

Destructor.

Definition at line 229 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 284 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 275 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 380 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 386 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 344 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 350 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 1047 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

l	is the lowest bucket that will occur.
h	is the highest bucket that will occur.
f	returns 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 1071 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 356 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 374 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 788 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 779 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 772 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 765 of file SList.h.

clear()

template<class E >

void ogdf::SListPure< E >::clear ( )

inline

Removes all elements from the list.

Definition at line 567 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 650 of file SList.h.

copy()

template<class E >

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

inlineprotected

Definition at line 811 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 392 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 402 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 554 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 496 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 472 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 238 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 362 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 368 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 266 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 257 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 307 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 293 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 510 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 608 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 590 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 630 of file SList.h.

operator!=()

template<class E >

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

inline

Inequality operator.

Definition at line 449 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 416 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 426 of file SList.h.

operator==()

template<class E >

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

inline

Equality operator.

Definition at line 436 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 797 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 1108 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 804 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 531 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 544 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 322 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 481 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 459 of file SList.h.

quicksort() [1/2]

template<class E >

void ogdf::SListPure< E >::quicksort ( )

inline

Sorts the list using Quicksort.

Definition at line 736 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 740 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 822 of file SList.h.

reverse()

template<class E >

void ogdf::SListPure< E >::reverse ( )

inline

Reverses the order of the list elements.

Definition at line 666 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 697 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 685 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 725 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 711 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< double >, ogdf::SList< ogdf::sync_plan::internal::FrozenSimplifyMapping >, ogdf::SList< ogdf::SimpleCluster * >, ogdf::SList< ogdf::NodeElement >, ogdf::SList< ogdf::EdgeElement >, ogdf::SList< ogdf::AdjElement >, ogdf::Queue< E >, and ogdf::Queue< ogdf::NodeElement >.

Definition at line 245 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 192 of file SList.h.

m_tail

template<class E >

SListElement<E>* ogdf::SListPure< E >::m_tail

private

Pointer to last element.

Definition at line 193 of file SList.h.

---

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

• include/ogdf/basic/SList.h