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

E	popFrontRet ()
	Removes the first element from the list and returns it. More...

void	popBack ()
	Removes the last element from the list. More...

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

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

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

Protected Attributes
ListElement< E > *	m_head
	Pointer to first element. More...

ListElement< E > *	m_tail
	Pointer to last element. 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

E	is the data type stored in list elements.

Definition at line 55 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 246 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 244 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 250 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 248 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 242 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 252 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 240 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 255 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 258 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 265 of file List.h.

◆ ListPure() [4/4]

template<class E >

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

inlinenoexcept

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

The list L is empty afterwards.

Definition at line 271 of file List.h.

◆ ~ListPure()

template<class E >

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

inlinevirtual

Destructor.

Definition at line 277 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 332 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 323 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 391 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 397 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

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 1733 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 403 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 421 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 1394 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 1385 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 1371 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 1364 of file List.h.

◆ clear()

template<class E >

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

inline

Removes all elements from the list.

Definition at line 799 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 1136 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 1154 of file List.h.

◆ copy()

template<class E >

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

inlineprotected

Definition at line 1417 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 439 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 457 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 501 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 520 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 511 of file List.h.

◆ cyclicPred() [4/4]

template<class E >

reverse_iterator ogdf::ListPure< E >::cyclicPred ( reverse_iterator it )

inline

Definition at line 529 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 463 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 482 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 473 of file List.h.

◆ cyclicSucc() [4/4]

template<class E >

reverse_iterator ogdf::ListPure< E >::cyclicSucc ( reverse_iterator it )

inline

Definition at line 491 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 765 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 627 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 601 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 286 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 409 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 415 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 825 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 314 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 305 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 355 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 341 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

x	is the element to be inserted.
it	is a list iterator in this list.
dir	determines 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 645 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 689 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 672 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 903 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 1035 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 875 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 1003 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 967 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 1104 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 931 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 1068 of file List.h.

◆ operator!=()

template<class E >

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

inline

Inequality operator.

Definition at line 576 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 543 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 553 of file List.h.

◆ operator==()

template<class E >

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

inline

Equality operator.

Definition at line 563 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 1403 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 1769 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 1410 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 739 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 755 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 713 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 729 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 369 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 612 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 586 of file List.h.

◆ quicksort() [1/2]

template<class E >

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

inline

Sorts the list using Quicksort.

Definition at line 1331 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 1335 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 427 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 433 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 1429 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 788 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 445 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 451 of file List.h.

◆ reverse()

template<class E >

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

inline

Reverses the order of the list elements.

Definition at line 1260 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 1292 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 1280 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 1320 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 1306 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 293 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 1190 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 1226 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 1242 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 1172 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 235 of file List.h.

◆ m_tail

template<class E >

ListElement<E>* ogdf::ListPure< E >::m_tail

protected

Pointer to last element.

Definition at line 236 of file List.h.

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

include/ogdf/basic/List.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

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

Member Typedef Documentation

◆ const_iterator

◆ const_reference

◆ const_reverse_iterator

◆ iterator

◆ reference

◆ reverse_iterator

◆ value_type

Constructor & Destructor Documentation

◆ ListPure() [1/4]

◆ ListPure() [2/4]

◆ ListPure() [3/4]

◆ ListPure() [4/4]

◆ ~ListPure()

Member Function Documentation

◆ back() [1/2]

◆ back() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ bucketSort()

◆ cbegin()

◆ cend()

◆ chooseElement() [1/2]

◆ chooseElement() [2/2]

◆ chooseIterator() [1/2]

◆ chooseIterator() [2/2]

◆ clear()

◆ conc()

◆ concFront()

◆ copy()

◆ crbegin()

◆ crend()

◆ cyclicPred() [1/4]

◆ cyclicPred() [2/4]

◆ cyclicPred() [3/4]

◆ cyclicPred() [4/4]

◆ cyclicSucc() [1/4]

◆ cyclicSucc() [2/4]

◆ cyclicSucc() [3/4]

◆ cyclicSucc() [4/4]

◆ del()

◆ emplaceBack()

◆ emplaceFront()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ exchange()

◆ front() [1/2]

◆ front() [2/2]

◆ get() [1/2]

◆ get() [2/2]

◆ insert()

◆ insertAfter()

◆ insertBefore()

◆ moveToBack() [1/2]

◆ moveToBack() [2/2]

◆ moveToFront() [1/2]

◆ moveToFront() [2/2]

◆ moveToPrec() [1/2]

◆ moveToPrec() [2/2]

◆ moveToSucc() [1/2]

◆ moveToSucc() [2/2]

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ permute() [1/3]

◆ permute() [2/3]

◆ permute() [3/3]

◆ popBack()

◆ popBackRet()

◆ popFront()

◆ popFrontRet()

Open
Graph Drawing
Framework

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