36#include <ogdf/basic/internal/config_autogen.h>
41#include <initializer_list>
49template<
class E,
bool isConst>
50class SListIteratorBase;
86 template<
class... Args>
103template<
class E,
bool isConst>
111 using Elem =
typename std::conditional<isConst, const E, E>::type;
126 template<bool isArgConst, typename std::enable_if<isConst || !isArgConst, int>::type = 0>
212 for (
const E& x : init) {
225 L.m_head = L.m_tail =
nullptr;
430 L.m_head = L.m_tail =
nullptr;
438 while (pX !=
nullptr && pY !=
nullptr) {
439 if (pX->
m_x != pY->m_x) {
445 return pX ==
nullptr && pY ==
nullptr;
471 template<
class... Args>
495 template<
class... Args>
517 return (pBefore->
m_next = pNew);
572 if (!std::is_trivially_destructible<E>::value) {
600 if (L2.
m_tail ==
nullptr) {
617 if (L2.
m_head ==
nullptr) {
642 if (pBefore == L2.
m_tail) {
656 if (L2.
m_tail !=
nullptr) {
668 for (p =
m_head; p; p = pNext) {
710 template<
class COMPARER>
714 if (comp.equal(*i, e)) {
724 template<
class COMPARER>
728 if (comp.equal(*i, e)) {
739 template<
class COMPARER>
766 std::function<
bool(
const E&)> includeElement = [](
const E&) {
return true; },
767 bool isFastTest =
true)
const {
773 std::function<
bool(
const E&)> includeElement = [](
const E&) {
return true; },
774 bool isFastTest =
true) {
780 std::function<
bool(
const E&)> includeElement = [](
const E&) {
return true; },
781 bool isFastTest =
true)
const {
789 std::function<
bool(
const E&)> includeElement = [](
const E&) {
return true; },
790 bool isFastTest =
true) {
824 for (
auto e = start ==
nullptr ?
m_head : start; e !=
nullptr; e = e->m_next) {
932 template<
class... Args>
945 template<
class... Args>
1049 if (m_head == m_tail) {
1073 if (m_head == m_tail) {
1080 for (pX = m_head; pX; pX = pX->
m_next) {
1083 tail[i] = (tail[i]->m_next = pX);
1085 head[i] = tail[i] = pX;
1090 for (
int i = l; i <= h; i++) {
1118 for (pX = m_head; pX; pX = pX->
m_next) {
1122 A.permute(0, n - 1, rng);
1124 for (i = 0; i < n; i++) {
1138 for (++pX; pX.valid(); ++pX) {
1174 for (i = a.
low(); i <= a.
high(); ++i) {
1175 bucket[f.
getBucket(a[i])].pushBack(a[i]);
1179 for (
int j = min; j <= max; ++j) {
1181 for (; it.
valid(); ++it) {
Declaration and implementation of Array class and Array algorithms.
Basic declarations, included by all source files.
The parameterized class Array implements dynamic arrays of type E.
iterator begin()
Returns an iterator to the first element.
INDEX high() const
Returns the maximal array index.
INDEX low() const
Returns the minimal array index.
Abstract base class for bucket functions.
virtual int getBucket(const E &x)=0
Returns the bucket of x.
Structure for elements of singly linked lists.
SListPure< E > * m_list
List object that the element belongs to.
SListElement(SListPure< E > *list, SListElement< E > *next, Args &&... args)
Constructs an SListElement with given arguments args for constructor of element type.
SListElement(SListPure< E > *list, const E &x)
Constructs an SListElement.
SListElement()
Constructs an SListElement.
SListElement< E > * m_next
Pointer to successor element.
SListElement(SListPure< E > *list, const E &x, SListElement< E > *next)
Constructs an SListElement.
Singly linked lists (maintaining the length of the list).
iterator emplaceBack(Args &&... args)
Adds a new element at the end of the list.
void moveFrontToSucc(SList< E > &L2, SListIterator< E > itBefore)
Moves the first element of this list to list L2 inserted after itBefore.
bool operator!=(const SList< E > &L) const
Inequality operator.
void clear()
Removes all elements from the list.
void moveFrontToFront(SList< E > &L2)
Moves the first element of this list to the begin of list L2.
int size() const
Returns the number of elements in the list.
SListIterator< E > insertAfter(const E &x, SListIterator< E > itBefore)
Inserts element x after itBefore.
SList(std::initializer_list< E > init)
Constructs a singly linked list containing the elements in init.
void conc(SList< E > &L2)
Appends L2 to this list and makes L2 empty.
void popFront()
Removes the first element from the list.
bool operator==(const SList< E > &L) const
Equality operator.
SList< E > & operator=(const SList< E > &L)
Assignment operator.
void moveFrontToBack(SList< E > &L2)
Moves the first element of this list to the end of list L2.
SList< E > & operator=(SList< E > &&L)
Assignment operator (move semantics).
SList(const SList< E > &L)
Constructs a singly linked list that is a copy of L.
void delSucc(SListIterator< E > itBefore)
Removes the succesor of itBefore.
E popFrontRet()
Removes the first element from the list and returns it.
SListIterator< E > pushFront(const E &x)
Adds element x at the beginning of the list.
const SListPure< E > & getSListPure() const
Conversion to const SListPure.
SList(SList< E > &&L) noexcept
Constructs a singly linked list containing the elements of L (move semantics).
int m_count
The length of the list.
iterator emplaceFront(Args &&... args)
Adds a new element at the beginning of the list.
SList()
Constructs an empty singly linked list.
SListIterator< E > pushBack(const E &x)
Adds element x at the end of the list.
Encapsulates a pointer to an ogdf::SList element.
SListIteratorBase()
Constructs an invalid iterator.
typename std::conditional< isConst, const SListElement< E >, SListElement< E > >::type ListElem
The underlying list element, depending on isConst.
SListIteratorBase< E, isConst > operator++(int)
Increment operator (postfix).
SListIteratorBase< E, isConst > & operator=(const SListIterator< E > &it)
Assignment operator.
bool operator==(const SListIteratorBase< E, isConst > &it) const
Equality operator.
SListIteratorBase< E, isConst > & operator++()
Increment operator (prefix).
SListIteratorBase(const SListIterator< E > &it)
Copy constructor.
bool valid() const
Returns true iff the iterator points to an element.
Elem & operator*() const
Returns a reference to the element content.
typename std::conditional< isConst, const E, E >::type Elem
The underlying type, depending on isConst.
ListElem * m_pX
Pointer to slist element.
SListPure< E > * listOf()
Returns the list that this iterator belongs to.
SListIteratorBase(const SListIteratorBase< E, isArgConst > &it)
Constructs an iterator that is a copy of it.
SListIteratorBase< E, isConst > succ() const
Returns successor iterator.
SListIteratorBase(ListElem *pX)
Constructs an iterator that points to pX.
bool operator!=(const SListIteratorBase< E, isConst > &it) const
Inequality operator.
void bucketSort(BucketFunc< E > &f)
Sorts the list using bucket sort.
bool operator==(const SListPure< E > &L) const
Equality operator.
const_iterator backIterator() const
Returns a const iterator to the last element of the list.
iterator chooseIterator(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
Returns an iterator to a random element.
iterator backIterator()
Returns an iterator to the last element of the list.
const E & const_reference
Provides a reference to a const element stored in a list for reading and performing const operations.
SListPure(const SListPure< E > &L)
Constructs a singly linked list that is a copy of L.
void reassignListRefs(SListElement< E > *start=nullptr)
Sets the debug reference of all list elements starting at start to this.
void quicksort(const COMPARER &comp)
Sorts the list using Quicksort and comparer comp.
void clear()
Removes all elements from the list.
SListPure()
Constructs an empty singly linked 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,...
SListIterator< E > iterator
Provides a forward iterator that can read or modify any element in a list.
SListPure< E > & operator=(SListPure< E > &&L)
Assignment operator (move semantics).
const_iterator chooseIterator(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
Returns an iterator to a random element.
SListConstIterator< E > const_iterator
Provides a forward iterator that can read a const element in a list.
SListElement< E > * m_tail
Pointer to last element.
iterator emplaceFront(Args &&... args)
Adds a new element at the beginning of the list.
reference front()
Returns a reference to the first element.
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...
void moveFrontToSucc(SListPure< E > &L2, iterator itBefore)
Moves the first element of this list to list L2 inserted after itBefore.
iterator end()
Returns an iterator to one-past-last element of the list.
void permute(RNG &rng)
Randomly permutes the elements in the list using random number generator rng.
E & reference
Provides a reference to an element stored in a list.
void reverse()
Reverses the order of the list elements.
iterator insertAfter(const E &x, iterator itBefore)
Inserts element x after itBefore.
void bucketSort(int l, int h, BucketFunc< E > &f)
Sorts the list using bucket sort.
const_iterator cyclicSucc(const_iterator it) const
Returns an iterator to the cyclic successor of it.
const_iterator cbegin() const
Returns a const iterator to the first element of the list.
const_iterator end() const
Returns a const iterator to one-past-last element of the list.
SListElement< E > * m_head
Pointer to first element.
iterator cyclicSucc(iterator it)
Returns an iterator to the cyclic successor of it.
int pos(const_iterator it) const
Returns the position (starting with 0) of it in the list.
void quicksort()
Sorts the list using Quicksort.
SListPure(SListPure< E > &&L) noexcept
Constructs a singly linked list containing the elements of L (move semantics).
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...
const_iterator get(int pos) const
Returns an iterator pointing to the element at position pos.
reference back()
Returns a reference to the last element.
const_iterator cend() const
Returns a const iterator to one-past-last element of the list.
SListIterator< E > search(const E &e)
Scans the list for the specified element and returns an iterator to the first occurrence in the list,...
bool empty() const
Returns true iff the list is empty.
iterator emplaceBack(Args &&... args)
Adds a new element at the end of the list.
reference chooseElement(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
Returns a random element.
SListPure< E > & operator=(const SListPure< E > &L)
Assignment operator.
const_reference front() const
Returns a reference to the first element.
E popFrontRet()
Removes the first element from the list and returns it.
virtual int size() const
Returns the number of elements in the list.
void permute()
Randomly permutes the elements in the list.
void moveFrontToBack(SListPure< E > &L2)
Moves the first element of this list to the end of list L2.
virtual ~SListPure()
Destructor.
E value_type
Represents the data type stored in a list element.
iterator pushFront(const E &x)
Adds element x at the beginning of the list.
const_reference back() const
Returns a reference to the last element.
void copy(const SListPure< E > &L)
bool operator!=(const SListPure< E > &L) const
Inequality operator.
iterator begin()
Returns an iterator to the first element of the list.
SListPure(std::initializer_list< E > init)
Constructs a singly linked list containing the elements in init.
iterator get(int pos)
Returns an iterator pointing to the element at position pos.
void moveFrontToFront(SListPure< E > &L2)
Moves the first element of this list to the begin of list L2.
const_iterator begin() const
Returns a const iterator to the first element of the list.
iterator pushBack(const E &x)
Adds element x at the end of the list.
void delSucc(iterator itBefore)
Removes the succesor of itBefore.
const_reference chooseElement(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
Returns a random element.
void permute(const int n, RNG &rng)
Permutes elements in list randomly; n is the length of the list.
void popFront()
Removes the first element from the list.
void conc(SListPure< E > &L2)
Appends L2 to this list and makes L2 empty.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
long unsigned int randomSeed()
Returns a random value suitable as initial seed for a random number engine.
Implementation of algorithms as templates working with different list types.
Declaration of memory manager for allocating small pieces of memory.
The namespace for all OGDF objects.
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
CONTAINER::iterator chooseIteratorFrom(CONTAINER &container, std::function< bool(const TYPE &)> includeElement=[](const TYPE &) { return true;}, bool isFastTest=true)
Returns an iterator to a random element in the container.
void bucketSort(Array< E > &a, int min, int max, BucketFunc< E > &f)
Bucket-sort array a using bucket assignment f; the values of f must be in the interval [min,...
void quicksortTemplate(LIST &L)
void print(std::ostream &os, const Array< E, INDEX > &a, char delim=' ')
Prints array a to output stream os using delimiter delim.