Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ogdf::QueuePure< E > Class Template Reference

Implementation of list-based queues. More...

#include <ogdf/basic/Queue.h>

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

Public Types

using const_iterator = SListConstIterator< E >
 Provides a forward iterator that can read a const element in a queue.
 
using const_reference = const E &
 Provides a reference to a const element stored in a queue for reading and performing const operations.
 
using iterator = SListIterator< E >
 Provides a forward iterator that can read or modify any element in a queue.
 
using reference = E &
 Provides a reference to an element stored in a queue.
 
using value_type = E
 Represents the data type stored in a queue element.
 

Public Member Functions

 QueuePure ()
 Constructs an empty queue.
 
 QueuePure (const QueuePure< E > &Q)
 Constructs a queue that is a copy of Q.
 
 QueuePure (QueuePure< E > &&Q)
 Constructs a queue containing the elements of Q (move semantics).
 
 QueuePure (std::initializer_list< E > initList)
 Constructs a queue and appends the elements in initList to it.
 
 ~QueuePure ()
 Destruction.
 
Access methods

These methods provide simple access without changing the list.

bool empty () const
 Returns true iff the queue is empty.
 
const_reference top () const
 Returns a reference to the front element.
 
reference top ()
 Returns a reference to the front element.
 
const_reference bottom () const
 Returns a reference to the back element.
 
reference bottom ()
 Returns a reference to the back element.
 
Iterators

These methods return forward iterators to elements in the queue.

iterator begin ()
 Returns an iterator to the first element of the queue.
 
const_iterator begin () const
 Returns a const iterator to the first element of the queue.
 
const_iterator cbegin () const
 Returns a const iterator to the first element of the queue.
 
iterator end ()
 Returns an iterator to one-past-last element of the queue.
 
const_iterator end () const
 Returns a const iterator to one-past-last element of the queue.
 
const_iterator cend () const
 Returns a const iterator to one-past-last element of the queue.
 
iterator backIterator ()
 Returns an iterator to the last element of the queue.
 
const_iterator backIterator () const
 Returns a const iterator to the last element of the queue.
 
Operators

The following operators are provided by lists.

QueuePure< E > & operator= (const QueuePure< E > &Q)
 Assignment operator.
 
QueuePure< E > & operator= (QueuePure< E > &&Q)
 Assignment operator (move semantics).
 
const SListPure< E > & getListPure () const
 Conversion to const SListPure.
 
Adding and removing elements

These method add elements to the list and remove elements from the list.

iterator append (const E &x)
 Adds x at the end of queue.
 
template<class... Args>
iterator emplace (Args &&... args)
 Adds a new element at the end of the queue.
 
pop ()
 Removes front element and returns it.
 
void clear ()
 Makes the queue empty.
 

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.
 
using const_reference = const E &
 Provides a reference to a const element stored in a list for reading and performing const operations.
 
using iterator = SListIterator< E >
 Provides a forward iterator that can read or modify any element in a list.
 
using reference = E &
 Provides a reference to an element stored in a list.
 
using value_type = E
 Represents the data type stored in a list element.
 
- Private Member Functions inherited from ogdf::SListPure< E >
 SListPure ()
 Constructs an empty singly linked list.
 
 SListPure (const SListPure< E > &L)
 Constructs a singly linked list that is a copy of L.
 
 SListPure (SListPure< E > &&L)
 Constructs a singly linked list containing the elements of L (move semantics).
 
 SListPure (std::initializer_list< E > init)
 Constructs a singly linked list containing the elements in init.
 
virtual ~SListPure ()
 Destructor.
 
bool empty () const
 Returns true iff the list is empty.
 
virtual int size () const
 Returns the number of elements in the list.
 
const_reference front () const
 Returns a reference to the first element.
 
reference front ()
 Returns a reference to the first element.
 
const_reference back () const
 Returns a reference to the last element.
 
reference back ()
 Returns a reference to the last element.
 
const_iterator get (int pos) const
 Returns an iterator pointing to the element at position pos.
 
iterator get (int pos)
 Returns an iterator pointing to the element at position pos.
 
int pos (const_iterator it) const
 Returns the position (starting with 0) of it in the list.
 
iterator begin ()
 Returns an iterator to the first element of the list.
 
const_iterator begin () const
 Returns a const iterator to the first element of the list.
 
const_iterator cbegin () const
 Returns a const iterator to the first element of the list.
 
iterator end ()
 Returns an iterator to one-past-last element of the list.
 
const_iterator end () const
 Returns a const iterator to one-past-last element of the list.
 
const_iterator cend () const
 Returns a const iterator to one-past-last element of the list.
 
iterator backIterator ()
 Returns an iterator to the last element of the list.
 
const_iterator backIterator () const
 Returns a const iterator to the last element of the list.
 
const_iterator cyclicSucc (const_iterator it) const
 Returns an iterator to the cyclic successor of it.
 
iterator cyclicSucc (iterator it)
 Returns an iterator to the cyclic successor of it.
 
SListPure< E > & operator= (const SListPure< E > &L)
 Assignment operator.
 
SListPure< E > & operator= (SListPure< E > &&L)
 Assignment operator (move semantics).
 
bool operator== (const SListPure< E > &L) const
 Equality operator.
 
bool operator!= (const SListPure< E > &L) const
 Inequality operator.
 
iterator pushFront (const E &x)
 Adds element x at the beginning of the list.
 
template<class... Args>
iterator emplaceFront (Args &&... args)
 Adds a new element at the beginning of the list.
 
iterator pushBack (const E &x)
 Adds element x at the end of the list.
 
template<class... Args>
iterator emplaceBack (Args &&... args)
 Adds a new element at the end of the list.
 
iterator insertAfter (const E &x, iterator itBefore)
 Inserts element x after itBefore.
 
void popFront ()
 Removes the first element from the list.
 
popFrontRet ()
 Removes the first element from the list and returns it.
 
void delSucc (iterator itBefore)
 Removes the succesor of itBefore.
 
void clear ()
 Removes all elements from the list.
 
void moveFrontToFront (SListPure< E > &L2)
 Moves the first element of this list to the begin of list L2.
 
void moveFrontToBack (SListPure< E > &L2)
 Moves the first element of this list to the end of list L2.
 
void moveFrontToSucc (SListPure< E > &L2, iterator itBefore)
 Moves the first element of this list to list L2 inserted after itBefore.
 
void conc (SListPure< E > &L2)
 Appends L2 to this list and makes L2 empty.
 
void reverse ()
 Reverses the order of the list elements.
 
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.
 
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.
 
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.
 
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.
 
void quicksort ()
 Sorts the list using Quicksort.
 
template<class COMPARER >
void quicksort (const COMPARER &comp)
 Sorts the list using Quicksort and comparer comp.
 
void bucketSort (int l, int h, BucketFunc< E > &f)
 Sorts the list using bucket sort.
 
void bucketSort (BucketFunc< E > &f)
 Sorts the list using bucket sort.
 
const_iterator chooseIterator (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
 Returns an iterator to a random element.
 
iterator chooseIterator (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
 Returns an iterator to a random element.
 
const_reference chooseElement (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
 Returns a random element.
 
reference chooseElement (std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
 Returns a random element.
 
void permute ()
 Randomly permutes the elements in the list.
 
template<class RNG >
void permute (RNG &rng)
 Randomly permutes the elements in the list using random number generator rng.
 
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.
 
void reassignListRefs (SListElement< E > *start=nullptr)
 Sets the debug reference of all list elements starting at start to this.
 

Detailed Description

template<class E>
class ogdf::QueuePure< E >

Implementation of list-based queues.

In contrast to Queue<E>, instances of QueuePure<E> do not store the number of elements contained in the queue.

Template Parameters
Eis the element type.

Definition at line 50 of file Queue.h.

Member Typedef Documentation

◆ const_iterator

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

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

Definition at line 59 of file Queue.h.

◆ const_reference

template<class E >
using ogdf::QueuePure< E >::const_reference = const E&

Provides a reference to a const element stored in a queue for reading and performing const operations.

Definition at line 57 of file Queue.h.

◆ iterator

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

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

Definition at line 61 of file Queue.h.

◆ reference

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

Provides a reference to an element stored in a queue.

Definition at line 55 of file Queue.h.

◆ value_type

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

Represents the data type stored in a queue element.

Definition at line 53 of file Queue.h.

Constructor & Destructor Documentation

◆ QueuePure() [1/4]

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

Constructs an empty queue.

Definition at line 64 of file Queue.h.

◆ QueuePure() [2/4]

template<class E >
ogdf::QueuePure< E >::QueuePure ( std::initializer_list< E >  initList)
inline

Constructs a queue and appends the elements in initList to it.

Definition at line 67 of file Queue.h.

◆ QueuePure() [3/4]

template<class E >
ogdf::QueuePure< E >::QueuePure ( const QueuePure< E > &  Q)
inline

Constructs a queue that is a copy of Q.

Definition at line 70 of file Queue.h.

◆ QueuePure() [4/4]

template<class E >
ogdf::QueuePure< E >::QueuePure ( QueuePure< E > &&  Q)
inline

Constructs a queue containing the elements of Q (move semantics).

Queue Q is empty afterwards.

Definition at line 76 of file Queue.h.

◆ ~QueuePure()

template<class E >
ogdf::QueuePure< E >::~QueuePure ( )
inline

Destruction.

Definition at line 79 of file Queue.h.

Member Function Documentation

◆ append()

template<class E >
iterator ogdf::QueuePure< E >::append ( const E &  x)
inline

Adds x at the end of queue.

Definition at line 166 of file Queue.h.

◆ backIterator() [1/2]

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

Returns an iterator to the last element of the queue.

Definition at line 128 of file Queue.h.

◆ backIterator() [2/2]

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

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

Definition at line 131 of file Queue.h.

◆ begin() [1/2]

template<class E >
iterator ogdf::QueuePure< E >::begin ( )
inline

Returns an iterator to the first element of the queue.

Definition at line 110 of file Queue.h.

◆ begin() [2/2]

template<class E >
const_iterator ogdf::QueuePure< E >::begin ( ) const
inline

Returns a const iterator to the first element of the queue.

Definition at line 113 of file Queue.h.

◆ bottom() [1/2]

template<class E >
reference ogdf::QueuePure< E >::bottom ( )
inline

Returns a reference to the back element.

Definition at line 100 of file Queue.h.

◆ bottom() [2/2]

template<class E >
const_reference ogdf::QueuePure< E >::bottom ( ) const
inline

Returns a reference to the back element.

Definition at line 97 of file Queue.h.

◆ cbegin()

template<class E >
const_iterator ogdf::QueuePure< E >::cbegin ( ) const
inline

Returns a const iterator to the first element of the queue.

Definition at line 116 of file Queue.h.

◆ cend()

template<class E >
const_iterator ogdf::QueuePure< E >::cend ( ) const
inline

Returns a const iterator to one-past-last element of the queue.

Definition at line 125 of file Queue.h.

◆ clear()

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

Makes the queue empty.

Definition at line 185 of file Queue.h.

◆ emplace()

template<class E >
template<class... Args>
iterator ogdf::QueuePure< E >::emplace ( Args &&...  args)
inline

Adds a new element at the end of the queue.

The element is constructed in-place with exactly the same arguments args as supplied to the function.

Definition at line 173 of file Queue.h.

◆ empty()

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

Returns true iff the queue is empty.

Definition at line 88 of file Queue.h.

◆ end() [1/2]

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

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

Definition at line 119 of file Queue.h.

◆ end() [2/2]

template<class E >
const_iterator ogdf::QueuePure< E >::end ( ) const
inline

Returns a const iterator to one-past-last element of the queue.

Definition at line 122 of file Queue.h.

◆ getListPure()

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

Conversion to const SListPure.

Definition at line 156 of file Queue.h.

◆ operator=() [1/2]

template<class E >
QueuePure< E > & ogdf::QueuePure< E >::operator= ( const QueuePure< E > &  Q)
inline

Assignment operator.

Definition at line 141 of file Queue.h.

◆ operator=() [2/2]

template<class E >
QueuePure< E > & ogdf::QueuePure< E >::operator= ( QueuePure< E > &&  Q)
inline

Assignment operator (move semantics).

Queue Q is empty afterwards.

Definition at line 150 of file Queue.h.

◆ pop()

template<class E >
E ogdf::QueuePure< E >::pop ( )
inline

Removes front element and returns it.

Definition at line 178 of file Queue.h.

◆ top() [1/2]

template<class E >
reference ogdf::QueuePure< E >::top ( )
inline

Returns a reference to the front element.

Definition at line 94 of file Queue.h.

◆ top() [2/2]

template<class E >
const_reference ogdf::QueuePure< E >::top ( ) const
inline

Returns a reference to the front element.

Definition at line 91 of file Queue.h.


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