|
Open Graph Drawing Framework |
v. 2023.09 (Elderberry)
|
|
|
Go to the documentation of this file.
41 #include <initializer_list>
45 #include <type_traits>
50 template<
class E,
bool isConst,
bool isReverse>
95 template<
class... Args>
97 :
ListElement(list, E(
std::forward<Args>(args)...), next, prev) { }
112 template<
class E,
bool isConst,
bool isReverse>
113 class ListIteratorBase {
163 bool operator==(
const ListIteratorBase<E, isConst, isReverse>& it)
const {
165 return m_pX == it.m_pX;
170 return m_pX != it.m_pX;
175 return isReverse ?
m_pX->m_prev :
m_pX->m_next;
180 return isReverse ?
m_pX->m_next :
m_pX->m_prev;
259 for (
const E& x :
init) {
272 L.m_head = L.m_tail =
nullptr;
557 L.m_head = L.m_tail =
nullptr;
565 while (pX !=
nullptr && pY !=
nullptr) {
566 if (pX->
m_x != pY->m_x) {
572 return pX ==
nullptr && pY ==
nullptr;
600 template<
class... Args>
626 template<
class... Args>
775 pNext->m_prev = pPrev;
804 if (!std::is_trivially_destructible<E>::value) {
831 std::swap(pX->
m_next, pY->m_next);
832 std::swap(pX->
m_prev, pY->m_prev);
834 std::swap(pX->
m_list, pY->m_list);
886 pPrev->m_next = pNext;
889 pNext->m_prev = pPrev;
914 pPrev->m_next = pNext;
919 pNext->m_prev = pPrev;
938 if (pX == pY || pPrev == pY) {
944 pPrev->m_next = pNext;
949 pNext->m_prev = pPrev;
955 (pX->
m_prev = pY)->m_next = pX;
974 if (pX == pY || pNext == pY) {
980 pPrev->m_next = pNext;
985 pNext->m_prev = pPrev;
991 (pX->
m_next = pY)->m_prev = pX;
1009 pPrev->m_next = pNext;
1014 pNext->m_prev = pPrev;
1020 if ((pX->
m_next = L2.m_head) !=
nullptr) {
1021 L2.m_head = L2.m_head->m_prev = pX;
1023 L2.m_head = L2.m_tail = pX;
1041 pPrev->m_next = pNext;
1046 pNext->m_prev = pPrev;
1052 if ((pX->
m_prev = L2.m_tail) !=
nullptr) {
1053 L2.m_tail = L2.m_tail->m_next = pX;
1055 L2.m_head = L2.m_tail = pX;
1075 pPrev->m_next = pNext;
1080 pNext->m_prev = pPrev;
1087 (pX->
m_prev = pY)->m_next = pX;
1111 pPrev->m_next = pNext;
1116 pNext->m_prev = pPrev;
1123 (pX->
m_next = pY)->m_prev = pX;
1139 m_tail->m_next = L2.m_head;
1144 L2.m_head->m_prev =
m_tail;
1150 L2.m_head = L2.m_tail =
nullptr;
1157 m_head->m_prev = L2.m_tail;
1162 L2.m_tail->m_next =
m_head;
1168 L2.m_head = L2.m_tail =
nullptr;
1173 std::swap(
m_head, other.m_head);
1174 std::swap(
m_tail, other.m_tail);
1177 other.reassignListRefs();
1204 L1.m_tail = L2.m_head->m_prev;
1207 L2.m_head = L1.m_tail->m_next;
1209 L2.m_head->m_prev = L1.m_tail->m_next =
nullptr;
1212 L1.m_head = L1.m_tail =
nullptr;
1217 if (
this != &L1 &&
this != &L2) {
1221 L1.reassignListRefs();
1222 L2.reassignListRefs();
1232 (L2.m_head = pX->
m_next)->m_prev =
nullptr;
1238 L2.reassignListRefs();
1252 m_tail->m_next =
nullptr;
1256 L2.reassignListRefs();
1305 template<
class COMPARER>
1309 if (comp.equal(*i, e)) {
1319 template<
class COMPARER>
1323 if (comp.equal(*i, e)) {
1334 template<
class COMPARER>
1365 std::function<
bool(
const E&)> includeElement = [](
const E&) {
return true; },
1366 bool isFastTest =
true)
const {
1372 std::function<
bool(
const E&)> includeElement = [](
const E&) {
return true; },
1373 bool isFastTest =
true) {
1386 std::function<
bool(
const E&)> includeElement = [](
const E&) {
return true; },
1387 bool isFastTest =
true)
const {
1395 std::function<
bool(
const E&)> includeElement = [](
const E&) {
return true; },
1396 bool isFastTest =
true) {
1418 for (
ListElement<E>* pX = L.m_head; pX !=
nullptr; pX = pX->m_next) {
1426 void permute(
const int n, RNG& rng);
1431 for (
auto e = start ==
nullptr ?
m_head : start; e !=
nullptr; e = e->m_next) {
1451 class List :
private ListPure<E> {
1540 template<
class... Args>
1553 template<
class... Args>
1683 std::swap(
m_count, other.m_count);
1689 int countL =
m_count, countL1 = 0;
1690 for (
ListElement<E>* pX = L1.m_head; pX !=
nullptr; pX = pX->m_next) {
1694 L1.m_count = countL1;
1695 L2.m_count = countL - countL1;
1696 if (this->m_head ==
nullptr) {
1734 if (m_head == m_tail) {
1741 for (pX = m_head; pX; pX = pX->
m_next) {
1744 tail[i] = ((pX->
m_prev = tail[i])->m_next = pX);
1746 head[i] = tail[i] = pX;
1751 for (
int i = l; i <= h; i++) {
1755 (pY->
m_next = pX)->m_prev = pY;
1757 (m_head = pX)->m_prev =
nullptr;
1776 A[0] =
A[n + 1] =
nullptr;
1780 for (pX = m_head; pX; pX = pX->
m_next) {
1784 A.permute(1, n, rng);
1786 for (i = 1; i <= n; i++) {
1802 for (++pX; pX.valid(); ++pX) {
1811 print(os, L.getListPure(), delim);
1824 return os << L.getListPure();
1827 template<
class E,
class Master>
const_iterator begin() const
Returns a const iterator to the first element of the list.
ListElement(ListPure< E > *list, const E &x, ListElement< E > *next, ListElement< E > *prev)
Constructs a ListElement.
void reassignListRefs(ListElement< E > *start=nullptr)
Sets the debug reference of all list elements starting at start to this.
TObserver * & reference
Provides a reference to an element stored in a list.
The namespace for all OGDF objects.
ListIteratorBase< E, isConst, isReverse > pred() const
Returns predecessor iterator.
void permute(RNG &rng)
Randomly permutes the elements in the list using random number generator rng.
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 split(iterator it, ListPure< E > &L1, ListPure< E > &L2, Direction dir=Direction::before)
Splits the list at element it into lists L1 and L2.
void moveToPrec(iterator it, ListPure< E > &L2, iterator itAfter)
Moves it to list L2 and inserts it before itAfter.
const_iterator chooseIterator(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
Returns an iterator to a random element.
void moveToBack(iterator it, List< E > &L2)
Moves it to the end of the list.
ListElement< E > * m_head
Pointer to first element.
ListConstReverseIterator< E > const_reverse_iterator
Provides a bidirectional reverse iterator that can read a const element in a list.
void copy(const ListPure< E > &L)
void clear()
Removes all elements from the list.
ListIteratorBase(const ListIteratorBase< E, isArgConst, isArgReverse > &it)
Constructs an iterator that is a copy of it.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
void conc(List< E > &L2)
Appends L2 to this list and makes L2 empty.
void swap(List< E > &other)
Exchanges the contents of this list and other in constant time.
void splitAfter(iterator it, ListPure< E > &L2)
Splits the list after it.
ListIteratorBase< E, isConst, isReverse > & operator++()
Increment operator (prefix).
void bucketSort(int l, int h, BucketFunc< E > &f)
Sorts the list using bucket sort.
ListPure< E > * m_list
List object that the element belongs to.
ListElement(ListPure< E > *list, const E &x)
Constructs a ListElement.
void popFront()
Removes the first element from the list.
void moveToSucc(iterator it, ListPure< E > &L2, iterator itBefore)
Moves it to list L2 and inserts it after itBefore.
iterator cyclicSucc(iterator it)
Returns an iterator to the cyclic successor of it.
reference back()
Returns a reference to the last element.
void split(iterator it, List< E > &L1, List< E > &L2, Direction dir=Direction::before)
Splits the list at element it into lists L1 and L2.
virtual int size() const
Returns the number of elements in the list.
List(std::initializer_list< E > init)
Constructs a doubly linked list containing the elements in init.
iterator emplaceFront(Args &&... args)
Adds a new element at the beginning of the list.
const_reference back() const
Returns a const reference to the last element.
E popFrontRet()
Removes the first element from the list and returns it.
bool operator!=(const ListIteratorBase< E, isConst, isReverse > &it) const
Inequality operator.
bool operator==(const ListPure< E > &L) const
Equality operator.
iterator insertAfter(const E &x, iterator it)
Inserts element x after it.
iterator begin()
Returns an iterator to the first element of the list.
E popBackRet()
Removes the last element from the list and returns it.
bool valid() const
Returns true iff the iterator points to an element.
bool operator==(const List< E > &L) const
Equality operator.
const_reverse_iterator crbegin() const
Returns a const iterator to the last element of the list.
void popFront()
Removes the first element from the list.
Abstract base class for bucket functions.
ListIterator< E > iterator
Provides a bidirectional iterator that can read or modify any element in a list.
const_iterator cyclicSucc(const_iterator it) const
Returns a const iterator to the cyclic successor of it.
List< E > & operator=(const List< E > &L)
Assignment operator.
void exchange(iterator it1, iterator it2)
Exchanges the positions of it1 and it2 in the list.
const_iterator get(int pos) const
Returns a const iterator pointing to the element at position pos.
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
iterator insertAfter(const E &x, iterator it)
Inserts element x after it.
typename List< ogdf::ClusterElement >::const_reverse_iterator reverse_iterator
Provides a bidirectional reverse iterator to an object in the container.
ListIterator< E > search(const E &e)
Scans the list for the specified element and returns an iterator to the first occurrence in the list,...
reverse_iterator rbegin() const
Returns a reverse iterator to the last element in the container.
ListElement< E > * m_next
Pointer to successor element.
void conc(ListPure< E > &L2)
Appends L2 to this list and makes L2 empty.
ListPure(std::initializer_list< E > init)
Constructs a doubly linked list containing the elements in init.
void concFront(List< E > &L2)
Prepends L2 to this list and makes L2 empty.
ListPure(ListPure< E > &&L) noexcept
Constructs a doubly linked list containing the elements of L (move semantics).
iterator end()
Returns an iterator to one-past-last element of the list.
ListPure< E > & operator=(const ListPure< E > &L)
Assignment operator.
int m_count
The length of the list.
int size() const
Returns the number of elements in the container.
void moveToBack(iterator it)
Moves it to the end of the list.
iterator insert(const E &x, iterator it, Direction dir=Direction::after)
Inserts element x before or after it.
void moveToSucc(iterator it, iterator itBefore)
Moves it after itBefore.
ListIteratorBase(ListElem *pX)
Constructs an iterator that points to pX.
const_iterator end() const
Returns a const iterator to one-past-last element of the list.
ListIteratorBase< E, isConst, isReverse > succ() const
Returns successor iterator.
ListElement(ListPure< E > *list, ListElement< E > *next, ListElement< E > *prev, Args &&... args)
Constructs a ListElement with given arguments args for constructor of element type.
typename List< ogdf::ClusterElement >::const_iterator iterator
Provides a bidirectional iterator to an object in the container.
ListElem * m_pX
pointer to list element
ListPure(const ListPure< E > &L)
Constructs a doubly linked list that is a copy of L.
List< E > & operator=(List< E > &&L)
Assignment operator (move semantics).
ListIteratorBase< E, isConst, isReverse > operator--(int)
Decrement operator (postfix).
E popFrontRet()
Removes the first element from the list and returns it.
const_iterator cyclicPred(const_iterator it) const
Returns a const iterator to the cyclic predecessor of it.
Implementation of algorithms as templates working with different list types.
void concFront(ListPure< E > &L2)
Prepends L2 to this list and makes L2 empty.
Elem & operator*() const
Returns a reference to the element content.
iterator cyclicPred(iterator it)
Returns an iterator to the cyclic predecessor of it.
iterator pushFront(const E &x)
Adds element x at the beginning of the list.
void moveToFront(iterator it)
Moves it to the begin of the list.
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...
iterator chooseIterator(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
Returns an iterator to a random element.
const T & move(const T &v)
The parameterized class Array implements dynamic arrays of type E.
void swap(ListPure< E > &other)
Exchanges the contents of this list and other in constant time.
virtual ~ListPure()
Destructor.
iterator begin() const
Returns an iterator to the first element in the container.
void moveToSucc(iterator it, List< E > &L2, iterator itBefore)
Moves it after itBefore.
void moveToPrec(iterator it, List< E > &L2, iterator itAfter)
Moves it before itAfter.
ListIteratorBase< E, isConst, isReverse > operator++(int)
Increment operator (postfix).
const_reference chooseElement(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
Returns a random element.
iterator emplaceBack(Args &&... args)
Adds a new element at the end of the list.
void moveToBack(iterator it, ListPure< E > &L2)
Moves it to the end of L2.
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
reverse_iterator rbegin()
Returns an iterator to the last element of the list.
const_iterator cbegin() const
Returns a const iterator to the first element of the list.
reverse_iterator rend()
Returns an iterator to one-before-first element of the list.
ListIteratorBase< E, isConst, isReverse > & operator--()
Decrement operator (prefix).
Doubly linked lists (maintaining the length of the list).
void reverse()
Reverses the order of the list elements.
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...
void popBack()
Removes the last element from the list.
const_iterator cend() const
Returns a const iterator to one-past-last element of the list.
ListConstIterator< E > const_iterator
Provides a bidirectional iterator that can read a const element in a list.
E popBackRet()
Removes the last element from the list and returns it.
iterator insertBefore(const E &x, iterator it)
Inserts element x before it.
reverse_iterator cyclicPred(reverse_iterator it)
bool operator!=(const ListPure< E > &L) const
Inequality operator.
bool removeFirst(const E &x)
Removes the first occurrence of x (if any) from the list.
void moveToPrec(iterator it, iterator itAfter)
Moves it before itAfter.
const_reverse_iterator rend() const
Returns a const iterator to one-before-first element of the list.
List()
Constructs an empty doubly linked list.
ListPure< E > & operator=(ListPure< E > &&L)
Assignment operator (move semantics).
const_reverse_iterator rbegin() const
Returns a const iterator to the last element of the list.
long unsigned int randomSeed()
Returns a random value suitable as initial seed for a random number engine.
Structure for elements of doubly linked lists.
const_reverse_iterator cyclicSucc(const_reverse_iterator it) const
ListPure()
Constructs an empty doubly linked list.
std::bidirectional_iterator_tag iterator_category
bool operator==(const ListIteratorBase< E, isConst, isReverse > &it) const
Equality operator.
void quicksort()
Sorts the list using Quicksort.
int pos(const_iterator it) const
Returns the position (starting with 0) of iterator it in the list.
ListIteratorBase< E, isConst, isReverse > & operator=(const ListIteratorBase< E, isConst, isReverse > &it)
Assignment operator.
const ListPure< E > & getListPure() const
Conversion to const ListPure.
void del(iterator it)
Removes it from the list.
Basic declarations, included by all source files.
const_reverse_iterator cyclicPred(const_reverse_iterator it) const
void popBack()
Removes the last element from the list.
typename std::conditional< isConst, const ListElement< E >, ListElement< E > >::type ListElem
The underlying list element, depending on isConst.
iterator end() const
Returns an iterator to the one-past-last element in the container.
reverse_iterator rend() const
Returns a reverse iterator to the one-before-first element in the container.
const_reverse_iterator crend() const
Returns a const iterator to one-before-first element of the list.
ListIteratorBase()
Constructs an invalid iterator.
Declaration and implementation of Array class and Array algorithms.
ListPure< E > * listOf()
Returns the list that this iterator belongs to.
void moveToFront(iterator it, ListPure< E > &L2)
Moves it to the begin of L2.
void print(std::ostream &os, const Array< E, INDEX > &a, char delim=' ')
Prints array a to output stream os using delimiter delim.
reference front()
Returns a reference to the first element.
const_reference front() const
Returns a const reference to the first element.
void quicksort(const COMPARER &comp)
Sorts the list using Quicksort and comparer comp.
int size() const
Returns the number of elements in the list.
iterator get(int pos)
Returns an iterator pointing to the element at position pos.
Encapsulates a pointer to a list element.
List(List< E > &&L) noexcept
Constructs a doubly linked list containing the elements of L (move semantics).
reverse_iterator cyclicSucc(reverse_iterator it)
iterator emplaceFront(Args &&... args)
Adds a new element at the beginning of the list.
ListElement< E > * m_tail
Pointer to last element.
reference chooseElement(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
Returns a random element.
void quicksortTemplate(LIST &L)
ListIteratorBase(const ListIteratorBase< E, isConst, isReverse > &it)
Copy constructor.
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,...
void splitBefore(iterator it, ListPure< E > &L2)
Splits the list before it.
iterator pushFront(const E &x)
Adds element x at the beginning of the list.
void del(iterator it)
Removes it from the list.
bool removeFirst(const E &x)
Removes the first occurrence of x (if any) from the list.
Declaration of memory manager for allocating small pieces of memory.
bool operator!=(const List< E > &L) const
Inequality operator.
const TObserver * & const_reference
Provides a reference to a const element stored in a list for reading and performing const operations.
List(const List< E > &L)
Constructs a doubly linked list that is a copy of L.
typename std::conditional< isConst, const ogdf::Graph::HiddenEdgeSet *, ogdf::Graph::HiddenEdgeSet * >::type Elem
The underlying type, depending on isConst.
virtual int getBucket(const E &x)=0
Returns the bucket of x.
iterator emplaceBack(Args &&... args)
Adds a new element at the end of the list.
bool empty() const
Returns true iff the list is empty.
iterator pushBack(const E &x)
Adds element x at the end of the list.
iterator pushBack(const E &x)
Adds element x at the end of the list.
void clear()
Removes all elements from the list.
iterator insertBefore(const E &x, iterator it)
Inserts element x before it.
void moveToFront(iterator it, List< E > &L2)
Moves it to the begin of the list.
std::ptrdiff_t difference_type
ListReverseIterator< E > reverse_iterator
Provides a bidirectional reverse iterator that can read or modify any element in a list.
iterator insert(const E &x, iterator it, Direction dir=Direction::after)
Inserts element x before or after it.
void permute()
Randomly permutes the elements in the list.
TObserver * value_type
Represents the data type stored in a list element.
ListElement< E > * m_prev
Pointer to predecessor element.