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

#include <ogdf/basic/SList.h>

Inheritance diagram for ogdf::SList< E >:

Public Member Functions
	SList ()
	Constructs an empty singly linked list. More...

	SList (const SList< E > &L)
	Constructs a singly linked list that is a copy of `L`. More...

	SList (SList< E > &&L) noexcept
	Constructs a singly linked list containing the elements of `L` (move semantics). More...

	SList (std::initializer_list< E > init)
	Constructs a singly 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 SListPure< E > &	getSListPure () const
	Conversion to const SListPure. More...

Operators
The following operators are provided by lists.
SList< E > &	operator= (const SList< E > &L)
	Assignment operator. More...

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

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

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

Adding elements
These method add elements to the list.
SListIterator< E >	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...

SListIterator< E >	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...

SListIterator< E >	insertAfter (const E &x, SListIterator< E > 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 (SListIterator< E > 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 (SList< E > &L2)
	Moves the first element of this list to the begin of list `L2`. More...

void	moveFrontToBack (SList< E > &L2)
	Moves the first element of this list to the end of list `L2`. More...

void	moveFrontToSucc (SList< E > &L2, SListIterator< E > itBefore)
	Moves the first element of this list to list `L2` inserted after `itBefore`. More...

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

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

Additional Inherited Members
Private Types inherited from ogdf::SListPure< E >
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...

Private Member Functions inherited from ogdf::SListPure< E >
	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...

bool	empty () const
	Returns true iff the list is empty. 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...

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...

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...

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...

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...

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...

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...

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::SList< E >

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

Use ogdf::SListConstIterator or ogdf::SListIterator in order to iterate over the list. In contrast to ogdf::SListPure, instances of ogdf::SList store the length of the list and thus allow constant time access to the length.

Template Parameters

E	is the data type stored in list elements.

Definition at line 845 of file SList.h.

Constructor & Destructor Documentation

◆ SList() [1/4]

template<class E >

ogdf::SList< E >::SList ( )

inline

Constructs an empty singly linked list.

Definition at line 856 of file SList.h.

◆ SList() [2/4]

template<class E >

ogdf::SList< E >::SList ( std::initializer_list< E > init )

inline

Constructs a singly linked list containing the elements in init.

Definition at line 859 of file SList.h.

◆ SList() [3/4]

template<class E >

ogdf::SList< E >::SList ( const SList< E > & L )

inline

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

Definition at line 862 of file SList.h.

◆ SList() [4/4]

template<class E >

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

inlinenoexcept

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

The list L is empty afterwards.

Definition at line 868 of file SList.h.

Member Function Documentation

◆ clear()

template<class E >

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

inline

Removes all elements from the list.

Definition at line 984 of file SList.h.

◆ conc()

template<class E >

void ogdf::SList< E >::conc ( SList< E > & L2 )

inline

Appends L2 to this list and makes L2 empty.

Definition at line 1018 of file SList.h.

◆ delSucc()

template<class E >

void ogdf::SList< E >::delSucc ( SListIterator< E > itBefore )

inline

Removes the succesor of itBefore.

Precondition: itBefore points to an element in this list.

Definition at line 978 of file SList.h.

◆ emplaceBack()

template<class E >

template<class... Args>

iterator ogdf::SList< 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 946 of file SList.h.

◆ emplaceFront()

template<class E >

template<class... Args>

iterator ogdf::SList< 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 933 of file SList.h.

◆ getSListPure()

template<class E >

const SListPure<E>& ogdf::SList< E >::getSListPure ( ) const

inline

Conversion to const SListPure.

Definition at line 883 of file SList.h.

◆ insertAfter()

template<class E >

SListIterator<E> ogdf::SList< E >::insertAfter	(	const E &	x,
		SListIterator< E >	itBefore
	)

inline

Inserts element x after itBefore.

Precondition: itBefore references an element in this list.

Definition at line 952 of file SList.h.

◆ moveFrontToBack()

template<class E >

void ogdf::SList< E >::moveFrontToBack ( SList< E > & L2 )

inline

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

Definition at line 1004 of file SList.h.

◆ moveFrontToFront()

template<class E >

void ogdf::SList< E >::moveFrontToFront ( SList< E > & L2 )

inline

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

Definition at line 997 of file SList.h.

◆ moveFrontToSucc()

template<class E >

void ogdf::SList< E >::moveFrontToSucc	(	SList< E > &	L2,
		SListIterator< E >	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 1011 of file SList.h.

◆ operator!=()

template<class E >

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

inline

Inequality operator.

Definition at line 916 of file SList.h.

◆ operator=() [1/2]

template<class E >

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

inline

Assignment operator.

Definition at line 893 of file SList.h.

◆ operator=() [2/2]

template<class E >

SList<E>& ogdf::SList< E >::operator= ( SList< E > && L )

inline

Assignment operator (move semantics).

The list L is empty afterwards.

Definition at line 903 of file SList.h.

◆ operator==()

template<class E >

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

inline

Equality operator.

Definition at line 911 of file SList.h.

◆ popFront()

template<class E >

void ogdf::SList< E >::popFront ( )

inline

Removes the first element from the list.

Precondition: The list is not empty!

Definition at line 965 of file SList.h.

◆ popFrontRet()

template<class E >

E ogdf::SList< E >::popFrontRet ( )

inline

Removes the first element from the list and returns it.

Precondition: The list is not empty!

Definition at line 971 of file SList.h.

◆ pushBack()

template<class E >

SListIterator<E> ogdf::SList< E >::pushBack ( const E & x )

inline

Adds element x at the end of the list.

Definition at line 939 of file SList.h.

◆ pushFront()

template<class E >

SListIterator<E> ogdf::SList< E >::pushFront ( const E & x )

inline

Adds element x at the beginning of the list.

Definition at line 926 of file SList.h.

◆ size()

template<class E >

int ogdf::SList< E >::size ( ) const

inlinevirtual

Returns the number of elements in the list.

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

Reimplemented from ogdf::SListPure< E >.

Definition at line 880 of file SList.h.

Member Data Documentation

◆ m_count

template<class E >

int ogdf::SList< E >::m_count

private

The length of the list.

Definition at line 846 of file SList.h.

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

include/ogdf/basic/SList.h

OpenGraph DrawingFramework

Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

template<class E> class ogdf::SList< E >

Constructor & Destructor Documentation

◆ SList() [1/4]

◆ SList() [2/4]

◆ SList() [3/4]

◆ SList() [4/4]

Member Function Documentation

◆ clear()

◆ conc()

◆ delSucc()

◆ emplaceBack()

◆ emplaceFront()

◆ getSListPure()

◆ insertAfter()

◆ moveFrontToBack()

◆ moveFrontToFront()

◆ moveFrontToSucc()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ popFront()

◆ popFrontRet()

◆ pushBack()

◆ pushFront()

◆ size()

Member Data Documentation

◆ m_count

Open
Graph Drawing
Framework

template<class E>
class ogdf::SList< E >