Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
SList.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <ogdf/basic/Array.h>
35#include <ogdf/basic/basic.h>
36#include <ogdf/basic/internal/config_autogen.h>
38#include <ogdf/basic/memory.h>
39
40#include <functional>
41#include <initializer_list>
42#include <ostream>
43#include <random>
44#include <type_traits>
45#include <utility>
46
47namespace ogdf {
48
49template<class E, bool isConst>
50class SListIteratorBase;
51template<class E>
52class SListPure;
53
54template<class E>
56template<class E>
58
60template<class E>
62 friend class SListPure<E>;
63 friend class SListIteratorBase<E, true>;
64 friend class SListIteratorBase<E, false>;
65
67 E m_x;
68#ifdef OGDF_DEBUG
70#endif
71
73 SListElement(SListPure<E>* list, const E& x, SListElement<E>* next) : m_next(next), m_x(x) {
74#ifdef OGDF_DEBUG
75 m_list = list;
76#endif
77 }
78
80 SListElement(SListPure<E>* list, const E& x) : SListElement(list, x, nullptr) { }
81
83 SListElement() : SListElement(nullptr, E()) { }
84
86 template<class... Args>
87 SListElement(SListPure<E>* list, SListElement<E>* next, Args&&... args)
88 : SListElement(list, E(std::forward<Args>(args)...), next) { }
89
91};
92
94
103template<class E, bool isConst>
105 friend class SListIteratorBase<E, !isConst>;
106 friend class SListPure<E>;
107
109 using ListElem = typename std::conditional<isConst, const SListElement<E>, SListElement<E>>::type;
111 using Elem = typename std::conditional<isConst, const E, E>::type;
112
114
116 operator ListElem*() { return m_pX; }
117
118public:
121
124
126 template<bool isArgConst, typename std::enable_if<isConst || !isArgConst, int>::type = 0>
128
130 // gcc9 complains since it cannot match the templated constructor above (-Werror=deprecated-copy).
132
134 bool valid() const { return m_pX != nullptr; }
135
136#ifdef OGDF_DEBUG
141 return m_pX->m_list;
142 }
143#endif
144
146 bool operator==(const SListIteratorBase<E, isConst>& it) const { return m_pX == it.m_pX; }
147
149 bool operator!=(const SListIteratorBase<E, isConst>& it) const { return m_pX != it.m_pX; }
150
152 SListIteratorBase<E, isConst> succ() const { return m_pX->m_next; }
153
155 Elem& operator*() const { return m_pX->m_x; }
156
159 m_pX = it.m_pX;
160 return *this;
161 }
162
165 m_pX = m_pX->m_next;
166 return *this;
167 }
168
172 m_pX = m_pX->m_next;
173 return it;
174 }
175
177};
178
180
190template<class E>
194
195public:
197 using value_type = E;
199 using reference = E&;
201 using const_reference = const E&;
206
208 SListPure() : m_head(nullptr), m_tail(nullptr) { }
209
211 SListPure(std::initializer_list<E> init) : m_head(nullptr), m_tail(nullptr) {
212 for (const E& x : init) {
213 pushBack(x);
214 }
215 }
216
218 SListPure(const SListPure<E>& L) : m_head(nullptr), m_tail(nullptr) { copy(L); }
219
221
224 SListPure(SListPure<E>&& L) noexcept : m_head(L.m_head), m_tail(L.m_tail) {
225 L.m_head = L.m_tail = nullptr;
226 }
227
229 virtual ~SListPure() { clear(); }
230
236
238 bool empty() const { return m_head == nullptr; }
239
241
245 virtual int size() const {
246 int count = 0;
247 for (SListElement<E>* pX = m_head; pX != nullptr; pX = pX->m_next) {
248 ++count;
249 }
250 return count;
251 }
252
254
258 OGDF_ASSERT(m_head != nullptr);
259 return m_head->m_x;
260 }
261
263
267 OGDF_ASSERT(m_head != nullptr);
268 return m_head->m_x;
269 }
270
272
276 OGDF_ASSERT(m_tail != nullptr);
277 return m_tail->m_x;
278 }
279
281
285 OGDF_ASSERT(m_tail != nullptr);
286 return m_tail->m_x;
287 }
288
290
293 const_iterator get(int pos) const {
294 SListElement<E>* pX;
295 for (pX = m_head; pX != nullptr; pX = pX->m_next) {
296 if (pos-- == 0) {
297 break;
298 }
299 }
300 return pX;
301 }
302
304
308 SListElement<E>* pX;
309 for (pX = m_head; pX != nullptr; pX = pX->m_next) {
310 if (pos-- == 0) {
311 break;
312 }
313 }
314 return pX;
315 }
316
318
322 int pos(const_iterator it) const {
323 OGDF_ASSERT(it.listOf() == this);
324 int p = 0;
325 for (SListElement<E>* pX = m_head; pX != nullptr; pX = pX->m_next, ++p) {
326 if (pX == it) {
327 break;
328 }
329 }
330 return p;
331 }
332
334
339
341
344 iterator begin() { return m_head; }
345
347
350 const_iterator begin() const { return m_head; }
351
353
356 const_iterator cbegin() const { return m_head; }
357
359
363
365
369
371
375
377
381
383
387
389
393 OGDF_ASSERT(it.listOf() == this);
394 const SListElement<E>* pX = it;
395 return (pX->m_next) ? pX->m_next : m_head;
396 }
397
399
403 OGDF_ASSERT(it.listOf() == this);
404 SListElement<E>* pX = it;
405 return (pX->m_next) ? pX->m_next : m_head;
406 }
407
409
414
417 clear();
418 copy(L);
419 return *this;
420 }
421
423
427 clear();
428 m_head = L.m_head;
429 m_tail = L.m_tail;
430 L.m_head = L.m_tail = nullptr;
432 return *this;
433 }
434
436 bool operator==(const SListPure<E>& L) const {
437 SListElement<E>*pX = m_head, *pY = L.m_head;
438 while (pX != nullptr && pY != nullptr) {
439 if (pX->m_x != pY->m_x) {
440 return false;
441 }
442 pX = pX->m_next;
443 pY = pY->m_next;
444 }
445 return pX == nullptr && pY == nullptr;
446 }
447
449 bool operator!=(const SListPure<E>& L) const { return !operator==(L); }
450
452
457
459 iterator pushFront(const E& x) {
460 m_head = new SListElement<E>(this, x, m_head);
461 if (m_tail == nullptr) {
462 m_tail = m_head;
463 }
464 return m_head;
465 }
466
468
471 template<class... Args>
472 iterator emplaceFront(Args&&... args) {
473 m_head = new SListElement<E>(this, m_head, std::forward<Args>(args)...);
474 if (m_tail == nullptr) {
475 m_tail = m_head;
476 }
477 return m_head;
478 }
479
481 iterator pushBack(const E& x) {
482 SListElement<E>* pNew = new SListElement<E>(this, x);
483 if (m_head == nullptr) {
484 m_head = m_tail = pNew;
485 } else {
486 m_tail = m_tail->m_next = pNew;
487 }
488 return m_tail;
489 }
490
492
495 template<class... Args>
496 iterator emplaceBack(Args&&... args) {
497 SListElement<E>* pNew = new SListElement<E>(this, nullptr, std::forward<Args>(args)...);
498 if (m_head == nullptr) {
499 m_head = m_tail = pNew;
500 } else {
501 m_tail = m_tail->m_next = pNew;
502 }
503 return m_tail;
504 }
505
507
510 iterator insertAfter(const E& x, iterator itBefore) {
511 OGDF_ASSERT(itBefore.listOf() == this);
512 SListElement<E>* pBefore = itBefore;
513 SListElement<E>* pNew = new SListElement<E>(this, x, pBefore->m_next);
514 if (pBefore == m_tail) {
515 m_tail = pNew;
516 }
517 return (pBefore->m_next = pNew);
518 }
519
521
526
528
531 void popFront() {
532 OGDF_ASSERT(m_head != nullptr);
534 if ((m_head = m_head->m_next) == nullptr) {
535 m_tail = nullptr;
536 }
537 delete pX;
538 }
539
541
545 E el = front();
546 popFront();
547 return el;
548 }
549
551
554 void delSucc(iterator itBefore) {
555 OGDF_ASSERT(itBefore.listOf() == this);
556 SListElement<E>* pBefore = itBefore;
557 OGDF_ASSERT(pBefore != nullptr);
558 SListElement<E>* pDel = pBefore->m_next;
559 OGDF_ASSERT(pDel != nullptr);
560 if ((pBefore->m_next = pDel->m_next) == nullptr) {
561 m_tail = pBefore;
562 }
563 delete pDel;
564 }
565
567 void clear() {
568 if (m_head == nullptr) {
569 return;
570 }
571
572 if (!std::is_trivially_destructible<E>::value) {
573 for (SListElement<E>* pX = m_head; pX != nullptr; pX = pX->m_next) {
574 pX->m_x.~E();
575 }
576 }
577 OGDF_ALLOCATOR::deallocateList(sizeof(SListElement<E>), m_head, m_tail);
578
579 m_head = m_tail = nullptr;
580 }
581
583
588
591 OGDF_ASSERT(m_head != nullptr);
592 OGDF_ASSERT(this != &L2);
593
595 if ((m_head = m_head->m_next) == nullptr) {
596 m_tail = nullptr;
597 }
598 pX->m_next = L2.m_head;
599 L2.m_head = pX;
600 if (L2.m_tail == nullptr) {
601 L2.m_tail = L2.m_head;
602 }
603
604 L2.m_head->m_list = &L2;
605 }
606
609 OGDF_ASSERT(m_head != nullptr);
610 OGDF_ASSERT(this != &L2);
611
613 if ((m_head = m_head->m_next) == nullptr) {
614 m_tail = nullptr;
615 }
616 pX->m_next = nullptr;
617 if (L2.m_head == nullptr) {
618 L2.m_head = L2.m_tail = pX;
619 } else {
620 L2.m_tail = L2.m_tail->m_next = pX;
621 }
622
623 L2.m_tail->m_list = &L2;
624 }
625
627
631 OGDF_ASSERT(m_head != nullptr);
632 OGDF_ASSERT(this != &L2);
633 OGDF_ASSERT(itBefore.listOf() == &L2);
634
635 SListElement<E>* pBefore = itBefore;
637 if ((m_head = m_head->m_next) == nullptr) {
638 m_tail = nullptr;
639 }
640 pX->m_next = pBefore->m_next;
641 pBefore->m_next = pX;
642 if (pBefore == L2.m_tail) {
643 L2.m_tail = pX;
644 }
645
646 pX->m_list = &L2;
647 }
648
650 void conc(SListPure<E>& L2) {
651 if (m_head) {
652 m_tail->m_next = L2.m_head;
653 } else {
654 m_head = L2.m_head;
655 }
656 if (L2.m_tail != nullptr) {
657 m_tail = L2.m_tail;
658 }
659
661
662 L2.m_head = L2.m_tail = nullptr;
663 }
664
666 void reverse() {
667 SListElement<E>*p, *pNext, *pPred = nullptr;
668 for (p = m_head; p; p = pNext) {
669 pNext = p->m_next;
670 p->m_next = pPred;
671 pPred = p;
672 }
673 std::swap(m_head, m_tail);
674 }
675
677
682
685 SListConstIterator<E> search(const E& e) const {
687 for (i = begin(); i.valid(); ++i) {
688 if (*i == e) {
689 return i;
690 }
691 }
692 return i;
693 }
694
699 for (i = begin(); i.valid(); ++i) {
700 if (*i == e) {
701 return i;
702 }
703 }
704 return i;
705 }
706
710 template<class COMPARER>
711 SListConstIterator<E> search(const E& e, const COMPARER& comp) const {
713 for (i = begin(); i.valid(); ++i) {
714 if (comp.equal(*i, e)) {
715 return i;
716 }
717 }
718 return i;
719 }
720
724 template<class COMPARER>
725 SListIterator<E> search(const E& e, const COMPARER& comp) {
727 for (i = begin(); i.valid(); ++i) {
728 if (comp.equal(*i, e)) {
729 return i;
730 }
731 }
732 return i;
733 }
734
737
739 template<class COMPARER>
740 void quicksort(const COMPARER& comp) {
741 ogdf::quicksortTemplate(*this, comp);
742 }
743
745
752 void bucketSort(int l, int h, BucketFunc<E>& f);
753
756
758
763
766 std::function<bool(const E&)> includeElement = [](const E&) { return true; },
767 bool isFastTest = true) const {
768 return chooseIteratorFrom(*this, includeElement, isFastTest);
769 }
770
773 std::function<bool(const E&)> includeElement = [](const E&) { return true; },
774 bool isFastTest = true) {
775 return chooseIteratorFrom(*this, includeElement, isFastTest);
776 }
777
780 std::function<bool(const E&)> includeElement = [](const E&) { return true; },
781 bool isFastTest = true) const {
782 const_iterator result = chooseIterator(includeElement, isFastTest);
783 OGDF_ASSERT(result.valid());
784 return *result;
785 }
786
789 std::function<bool(const E&)> includeElement = [](const E&) { return true; },
790 bool isFastTest = true) {
791 iterator result = chooseIterator(includeElement, isFastTest);
792 OGDF_ASSERT(result.valid());
793 return *result;
794 }
795
797 void permute() {
798 std::minstd_rand rng(randomSeed());
799 permute(size(), rng);
800 }
801
803 template<class RNG>
804 void permute(RNG& rng) {
805 permute(size(), rng);
806 }
807
809
810protected:
811 void copy(const SListPure<E>& L) {
812 for (SListElement<E>* pX = L.m_head; pX != nullptr; pX = pX->m_next) {
813 pushBack(pX->m_x);
814 }
815 }
816
818 template<class RNG>
819 void permute(const int n, RNG& rng);
820
822 inline void reassignListRefs(SListElement<E>* start = nullptr) {
823#ifdef OGDF_DEBUG
824 for (auto e = start == nullptr ? m_head : start; e != nullptr; e = e->m_next) {
825 e->m_list = this;
826 }
827#endif
828 }
829
831};
832
834
844template<class E>
845class SList : private SListPure<E> {
847
848public:
849 using typename SListPure<E>::value_type;
850 using typename SListPure<E>::reference;
851 using typename SListPure<E>::const_reference;
852 using typename SListPure<E>::const_iterator;
853 using typename SListPure<E>::iterator;
854
856 SList() : m_count(0) { }
857
859 SList(std::initializer_list<E> init) : SListPure<E>(init), m_count((int)init.size()) { }
860
862 SList(const SList<E>& L) : SListPure<E>(L), m_count(L.m_count) { }
863
865
868 SList(SList<E>&& L) noexcept : SListPure<E>(std::move(L)), m_count(L.m_count) { L.m_count = 0; }
869
875
877
880 int size() const { return m_count; }
881
883 const SListPure<E>& getSListPure() const { return *this; }
884
886
891
895 m_count = L.m_count;
896 return *this;
897 }
898
900
904 m_count = L.m_count;
905 SListPure<E>::operator=(std::move(L));
906 L.m_count = 0;
907 return *this;
908 }
909
911 bool operator==(const SList<E>& L) const {
912 return (m_count == L.m_count) && SListPure<E>::operator==(L);
913 }
914
916 bool operator!=(const SList<E>& L) const { return !operator==(L); }
917
919
924
927 ++m_count;
928 return SListPure<E>::pushFront(x);
929 }
930
932 template<class... Args>
933 iterator emplaceFront(Args&&... args) {
934 ++m_count;
935 return SListPure<E>::emplaceFront(std::forward<Args>(args)...);
936 }
937
940 ++m_count;
941 return SListPure<E>::pushBack(x);
942 }
943
945 template<class... Args>
946 iterator emplaceBack(Args&&... args) {
947 ++m_count;
948 return SListPure<E>::emplaceBack(std::forward<Args>(args)...);
949 }
950
953 ++m_count;
954 return SListPure<E>::insertAfter(x, itBefore);
955 }
956
958
963
965 void popFront() {
966 --m_count;
968 }
969
972 E el = front();
973 popFront();
974 return el;
975 }
976
978 void delSucc(SListIterator<E> itBefore) {
979 --m_count;
980 SListPure<E>::delSucc(itBefore);
981 }
982
984 void clear() {
985 m_count = 0;
987 }
988
990
995
999 --m_count;
1000 ++L2.m_count;
1001 }
1002
1006 --m_count;
1007 ++L2.m_count;
1008 }
1009
1012 SListPure<E>::moveFrontToSucc(L2, itBefore);
1013 --m_count;
1014 ++L2.m_count;
1015 }
1016
1018 void conc(SList<E>& L2) {
1020 m_count += L2.m_count;
1021 L2.m_count = 0;
1022 }
1023
1024 using SListPure<E>::empty;
1025 using SListPure<E>::front;
1026 using SListPure<E>::back;
1027 using SListPure<E>::get;
1028 using SListPure<E>::pos;
1029 using SListPure<E>::begin;
1030 using SListPure<E>::cbegin;
1031 using SListPure<E>::end;
1032 using SListPure<E>::cend;
1033 using SListPure<E>::backIterator;
1034 using SListPure<E>::cyclicSucc;
1035 using SListPure<E>::reverse;
1036 using SListPure<E>::search;
1037 using SListPure<E>::quicksort;
1038 using SListPure<E>::bucketSort;
1040 using SListPure<E>::chooseElement;
1041 using SListPure<E>::permute;
1042
1044};
1045
1046template<class E>
1048 // if less than two elements, nothing to do
1049 if (m_head == m_tail) {
1050 return;
1051 }
1052
1053 int l, h;
1054 l = h = f.getBucket(m_head->m_x);
1055
1056 SListElement<E>* pX;
1057 for (pX = m_head->m_next; pX; pX = pX->m_next) {
1058 int i = f.getBucket(pX->m_x);
1059 if (i < l) {
1060 l = i;
1061 }
1062 if (i > h) {
1063 h = i;
1064 }
1065 }
1066
1067 bucketSort(l, h, f);
1068}
1069
1070template<class E>
1072 // if less than two elements, nothing to do
1073 if (m_head == m_tail) {
1074 return;
1075 }
1076
1077 Array<SListElement<E>*> head(l, h, nullptr), tail(l, h);
1078
1079 SListElement<E>* pX;
1080 for (pX = m_head; pX; pX = pX->m_next) {
1081 int i = f.getBucket(pX->m_x);
1082 if (head[i]) {
1083 tail[i] = (tail[i]->m_next = pX);
1084 } else {
1085 head[i] = tail[i] = pX;
1086 }
1087 }
1088
1089 SListElement<E>* pY = nullptr;
1090 for (int i = l; i <= h; i++) {
1091 pX = head[i];
1092 if (pX) {
1093 if (pY) {
1094 pY->m_next = pX;
1095 } else {
1096 m_head = pX;
1097 }
1098 pY = tail[i];
1099 }
1100 }
1101
1102 m_tail = pY;
1103 pY->m_next = nullptr;
1104}
1105
1106template<class E>
1107template<class RNG>
1108void SListPure<E>::permute(const int n, RNG& rng) {
1109 if (n == 0) {
1110 return;
1111 }
1112
1113 Array<SListElement<E>*> A(n + 1);
1114 A[n] = nullptr;
1115
1116 int i = 0;
1117 SListElement<E>* pX;
1118 for (pX = m_head; pX; pX = pX->m_next) {
1119 A[i++] = pX;
1120 }
1121
1122 A.permute(0, n - 1, rng);
1123
1124 for (i = 0; i < n; i++) {
1125 A[i]->m_next = A[i + 1];
1126 }
1127
1128 m_head = A[0];
1129 m_tail = A[n - 1];
1130}
1131
1133template<class E>
1134void print(std::ostream& os, const SListPure<E>& L, char delim = ' ') {
1136 if (pX.valid()) {
1137 os << *pX;
1138 for (++pX; pX.valid(); ++pX) {
1139 os << delim << *pX;
1140 }
1141 }
1142}
1143
1145template<class E>
1146void print(std::ostream& os, const SList<E>& L, char delim = ' ') {
1147 print(os, L.getSListPure(), delim);
1148}
1149
1151template<class E>
1152std::ostream& operator<<(std::ostream& os, const SListPure<E>& L) {
1153 print(os, L);
1154 return os;
1155}
1156
1158template<class E>
1159std::ostream& operator<<(std::ostream& os, const SList<E>& L) {
1160 return operator<<(os, L.getSListPure());
1161}
1162
1165template<class E>
1166void bucketSort(Array<E>& a, int min, int max, BucketFunc<E>& f) {
1167 if (a.low() >= a.high()) {
1168 return;
1169 }
1170
1171 Array<SListPure<E>> bucket(min, max);
1172
1173 int i;
1174 for (i = a.low(); i <= a.high(); ++i) {
1175 bucket[f.getBucket(a[i])].pushBack(a[i]);
1176 }
1177
1178 i = a.low();
1179 for (int j = min; j <= max; ++j) {
1180 SListConstIterator<E> it = bucket[j].begin();
1181 for (; it.valid(); ++it) {
1182 a[i++] = *it;
1183 }
1184 }
1185}
1186
1187}
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.
Definition Array.h:219
iterator begin()
Returns an iterator to the first element.
Definition Array.h:329
INDEX high() const
Returns the maximal array index.
Definition Array.h:299
INDEX low() const
Returns the minimal array index.
Definition Array.h:296
Abstract base class for bucket functions.
Definition basic.h:257
virtual int getBucket(const E &x)=0
Returns the bucket of x.
Structure for elements of singly linked lists.
Definition SList.h:61
SListPure< E > * m_list
List object that the element belongs to.
Definition SList.h:69
SListElement(SListPure< E > *list, SListElement< E > *next, Args &&... args)
Constructs an SListElement with given arguments args for constructor of element type.
Definition SList.h:87
E m_x
Stores the content.
Definition SList.h:67
SListElement(SListPure< E > *list, const E &x)
Constructs an SListElement.
Definition SList.h:80
SListElement()
Constructs an SListElement.
Definition SList.h:83
SListElement< E > * m_next
Pointer to successor element.
Definition SList.h:66
SListElement(SListPure< E > *list, const E &x, SListElement< E > *next)
Constructs an SListElement.
Definition SList.h:73
Singly linked lists (maintaining the length of the list).
Definition SList.h:845
iterator emplaceBack(Args &&... args)
Adds a new element at the end of the list.
Definition SList.h:946
void moveFrontToSucc(SList< E > &L2, SListIterator< E > itBefore)
Moves the first element of this list to list L2 inserted after itBefore.
Definition SList.h:1011
bool operator!=(const SList< E > &L) const
Inequality operator.
Definition SList.h:916
void clear()
Removes all elements from the list.
Definition SList.h:984
void moveFrontToFront(SList< E > &L2)
Moves the first element of this list to the begin of list L2.
Definition SList.h:997
int size() const
Returns the number of elements in the list.
Definition SList.h:880
SListIterator< E > insertAfter(const E &x, SListIterator< E > itBefore)
Inserts element x after itBefore.
Definition SList.h:952
SList(std::initializer_list< E > init)
Constructs a singly linked list containing the elements in init.
Definition SList.h:859
void conc(SList< E > &L2)
Appends L2 to this list and makes L2 empty.
Definition SList.h:1018
void popFront()
Removes the first element from the list.
Definition SList.h:965
bool operator==(const SList< E > &L) const
Equality operator.
Definition SList.h:911
SList< E > & operator=(const SList< E > &L)
Assignment operator.
Definition SList.h:893
void moveFrontToBack(SList< E > &L2)
Moves the first element of this list to the end of list L2.
Definition SList.h:1004
SList< E > & operator=(SList< E > &&L)
Assignment operator (move semantics).
Definition SList.h:903
SList(const SList< E > &L)
Constructs a singly linked list that is a copy of L.
Definition SList.h:862
void delSucc(SListIterator< E > itBefore)
Removes the succesor of itBefore.
Definition SList.h:978
E popFrontRet()
Removes the first element from the list and returns it.
Definition SList.h:971
SListIterator< E > pushFront(const E &x)
Adds element x at the beginning of the list.
Definition SList.h:926
const SListPure< E > & getSListPure() const
Conversion to const SListPure.
Definition SList.h:883
SList(SList< E > &&L) noexcept
Constructs a singly linked list containing the elements of L (move semantics).
Definition SList.h:868
int m_count
The length of the list.
Definition SList.h:846
iterator emplaceFront(Args &&... args)
Adds a new element at the beginning of the list.
Definition SList.h:933
SList()
Constructs an empty singly linked list.
Definition SList.h:856
SListIterator< E > pushBack(const E &x)
Adds element x at the end of the list.
Definition SList.h:939
Encapsulates a pointer to an ogdf::SList element.
Definition SList.h:104
SListIteratorBase()
Constructs an invalid iterator.
Definition SList.h:123
typename std::conditional< isConst, const SListElement< E >, SListElement< E > >::type ListElem
The underlying list element, depending on isConst.
Definition SList.h:109
SListIteratorBase< E, isConst > operator++(int)
Increment operator (postfix).
Definition SList.h:170
SListIteratorBase< E, isConst > & operator=(const SListIterator< E > &it)
Assignment operator.
Definition SList.h:158
bool operator==(const SListIteratorBase< E, isConst > &it) const
Equality operator.
Definition SList.h:146
SListIteratorBase< E, isConst > & operator++()
Increment operator (prefix).
Definition SList.h:164
SListIteratorBase(const SListIterator< E > &it)
Copy constructor.
Definition SList.h:131
bool valid() const
Returns true iff the iterator points to an element.
Definition SList.h:134
Elem & operator*() const
Returns a reference to the element content.
Definition SList.h:155
typename std::conditional< isConst, const E, E >::type Elem
The underlying type, depending on isConst.
Definition SList.h:111
ListElem * m_pX
Pointer to slist element.
Definition SList.h:113
SListPure< E > * listOf()
Returns the list that this iterator belongs to.
Definition SList.h:139
SListIteratorBase(const SListIteratorBase< E, isArgConst > &it)
Constructs an iterator that is a copy of it.
Definition SList.h:127
SListIteratorBase< E, isConst > succ() const
Returns successor iterator.
Definition SList.h:152
SListIteratorBase(ListElem *pX)
Constructs an iterator that points to pX.
Definition SList.h:120
bool operator!=(const SListIteratorBase< E, isConst > &it) const
Inequality operator.
Definition SList.h:149
Singly linked lists.
Definition SList.h:191
void bucketSort(BucketFunc< E > &f)
Sorts the list using bucket sort.
Definition SList.h:1047
bool operator==(const SListPure< E > &L) const
Equality operator.
Definition SList.h:436
const_iterator backIterator() const
Returns a const iterator to the last element of the list.
Definition SList.h:386
iterator chooseIterator(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
Returns an iterator to a random element.
Definition SList.h:772
iterator backIterator()
Returns an iterator to the last element of the list.
Definition SList.h:380
const E & const_reference
Provides a reference to a const element stored in a list for reading and performing const operations.
Definition SList.h:201
SListPure(const SListPure< E > &L)
Constructs a singly linked list that is a copy of L.
Definition SList.h:218
void reassignListRefs(SListElement< E > *start=nullptr)
Sets the debug reference of all list elements starting at start to this.
Definition SList.h:822
void quicksort(const COMPARER &comp)
Sorts the list using Quicksort and comparer comp.
Definition SList.h:740
void clear()
Removes all elements from the list.
Definition SList.h:567
SListPure()
Constructs an empty singly linked list.
Definition SList.h:208
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,...
Definition SList.h:685
SListIterator< E > iterator
Provides a forward iterator that can read or modify any element in a list.
Definition SList.h:205
SListPure< E > & operator=(SListPure< E > &&L)
Assignment operator (move semantics).
Definition SList.h:426
const_iterator chooseIterator(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
Returns an iterator to a random element.
Definition SList.h:765
SListConstIterator< E > const_iterator
Provides a forward iterator that can read a const element in a list.
Definition SList.h:203
SListElement< E > * m_tail
Pointer to last element.
Definition SList.h:193
iterator emplaceFront(Args &&... args)
Adds a new element at the beginning of the list.
Definition SList.h:472
reference front()
Returns a reference to the first element.
Definition SList.h:266
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...
Definition SList.h:725
void moveFrontToSucc(SListPure< E > &L2, iterator itBefore)
Moves the first element of this list to list L2 inserted after itBefore.
Definition SList.h:630
iterator end()
Returns an iterator to one-past-last element of the list.
Definition SList.h:362
void permute(RNG &rng)
Randomly permutes the elements in the list using random number generator rng.
Definition SList.h:804
E & reference
Provides a reference to an element stored in a list.
Definition SList.h:199
void reverse()
Reverses the order of the list elements.
Definition SList.h:666
iterator insertAfter(const E &x, iterator itBefore)
Inserts element x after itBefore.
Definition SList.h:510
void bucketSort(int l, int h, BucketFunc< E > &f)
Sorts the list using bucket sort.
Definition SList.h:1071
const_iterator cyclicSucc(const_iterator it) const
Returns an iterator to the cyclic successor of it.
Definition SList.h:392
const_iterator cbegin() const
Returns a const iterator to the first element of the list.
Definition SList.h:356
const_iterator end() const
Returns a const iterator to one-past-last element of the list.
Definition SList.h:368
SListElement< E > * m_head
Pointer to first element.
Definition SList.h:192
iterator cyclicSucc(iterator it)
Returns an iterator to the cyclic successor of it.
Definition SList.h:402
int pos(const_iterator it) const
Returns the position (starting with 0) of it in the list.
Definition SList.h:322
void quicksort()
Sorts the list using Quicksort.
Definition SList.h:736
SListPure(SListPure< E > &&L) noexcept
Constructs a singly linked list containing the elements of L (move semantics).
Definition SList.h:224
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...
Definition SList.h:711
const_iterator get(int pos) const
Returns an iterator pointing to the element at position pos.
Definition SList.h:293
reference back()
Returns a reference to the last element.
Definition SList.h:284
const_iterator cend() const
Returns a const iterator to one-past-last element of the list.
Definition SList.h:374
SListIterator< E > search(const E &e)
Scans the list for the specified element and returns an iterator to the first occurrence in the list,...
Definition SList.h:697
bool empty() const
Returns true iff the list is empty.
Definition SList.h:238
iterator emplaceBack(Args &&... args)
Adds a new element at the end of the list.
Definition SList.h:496
reference chooseElement(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
Returns a random element.
Definition SList.h:788
SListPure< E > & operator=(const SListPure< E > &L)
Assignment operator.
Definition SList.h:416
const_reference front() const
Returns a reference to the first element.
Definition SList.h:257
E popFrontRet()
Removes the first element from the list and returns it.
Definition SList.h:544
virtual int size() const
Returns the number of elements in the list.
Definition SList.h:245
void permute()
Randomly permutes the elements in the list.
Definition SList.h:797
void moveFrontToBack(SListPure< E > &L2)
Moves the first element of this list to the end of list L2.
Definition SList.h:608
virtual ~SListPure()
Destructor.
Definition SList.h:229
E value_type
Represents the data type stored in a list element.
Definition SList.h:197
iterator pushFront(const E &x)
Adds element x at the beginning of the list.
Definition SList.h:459
const_reference back() const
Returns a reference to the last element.
Definition SList.h:275
void copy(const SListPure< E > &L)
Definition SList.h:811
bool operator!=(const SListPure< E > &L) const
Inequality operator.
Definition SList.h:449
iterator begin()
Returns an iterator to the first element of the list.
Definition SList.h:344
SListPure(std::initializer_list< E > init)
Constructs a singly linked list containing the elements in init.
Definition SList.h:211
iterator get(int pos)
Returns an iterator pointing to the element at position pos.
Definition SList.h:307
void moveFrontToFront(SListPure< E > &L2)
Moves the first element of this list to the begin of list L2.
Definition SList.h:590
const_iterator begin() const
Returns a const iterator to the first element of the list.
Definition SList.h:350
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition SList.h:481
void delSucc(iterator itBefore)
Removes the succesor of itBefore.
Definition SList.h:554
const_reference chooseElement(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
Returns a random element.
Definition SList.h:779
void permute(const int n, RNG &rng)
Permutes elements in list randomly; n is the length of the list.
Definition SList.h:1108
void popFront()
Removes the first element from the list.
Definition SList.h:531
void conc(SListPure< E > &L2)
Appends L2 to this list and makes L2 empty.
Definition SList.h:650
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:52
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition memory.h:85
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.
Definition Array.h:983
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,...
Definition SList.h:1166
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.
Definition Array.h:972
Definition GML.h:111