Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

List.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>
38 #include <ogdf/basic/memory.h>
39 
40 #include <functional>
41 #include <initializer_list>
42 #include <iterator>
43 #include <ostream>
44 #include <random>
45 #include <type_traits>
46 #include <utility>
47 
48 namespace ogdf {
49 
50 template<class E, bool isConst, bool isReverse>
52 template<class E>
53 class List;
54 template<class E>
55 class ListPure;
56 
57 template<class E>
59 template<class E>
61 template<class E>
63 template<class E>
65 
67 template<class E>
68 class ListElement {
69  friend class ListPure<E>;
70  friend class List<E>;
71  friend class ListIteratorBase<E, true, true>;
72  friend class ListIteratorBase<E, false, true>;
73  friend class ListIteratorBase<E, true, false>;
74  friend class ListIteratorBase<E, false, false>;
75 
78  E m_x;
79 #ifdef OGDF_DEBUG
81 #endif
82 
84  ListElement(ListPure<E>* list, const E& x, ListElement<E>* next, ListElement<E>* prev)
85  : m_next(next), m_prev(prev), m_x(x) {
86 #ifdef OGDF_DEBUG
87  m_list = list;
88 #endif
89  }
90 
92  ListElement(ListPure<E>* list, const E& x) : ListElement(list, x, nullptr, nullptr) { }
93 
95  template<class... Args>
96  ListElement(ListPure<E>* list, ListElement<E>* next, ListElement<E>* prev, Args&&... args)
97  : ListElement(list, E(std::forward<Args>(args)...), next, prev) { }
98 
100 };
101 
103 
112 template<class E, bool isConst, bool isReverse>
113 class ListIteratorBase {
114  friend class ListIteratorBase<E, !isConst, isReverse>;
115  friend class ListIteratorBase<E, isConst, !isReverse>;
116  friend class ListIteratorBase<E, !isConst, !isReverse>;
117  friend class ListPure<E>;
119  using ListElem = typename std::conditional<isConst, const ListElement<E>, ListElement<E>>::type;
122 
125 
126 public:
127  using difference_type = std::ptrdiff_t;
128  using value_type = Elem;
129  using iterator_category = std::bidirectional_iterator_tag;
130  using pointer = value_type*;
132 
134  operator ListElem*() { return m_pX; }
135 
138 
141 
145  : ListIteratorBase(it.m_pX) { }
146 
148  // gcc9 complains since it cannot match the templated constructor above (-Werror=deprecated-copy).
150  : ListIteratorBase(it.m_pX) { }
151 
153  bool valid() const { return m_pX != nullptr; }
154 
155 #ifdef OGDF_DEBUG
156  ListPure<E>* listOf() {
159  OGDF_ASSERT(valid());
160  return m_pX->m_list;
161  }
162 #endif
163  bool operator==(const ListIteratorBase<E, isConst, isReverse>& it) const {
165  return m_pX == it.m_pX;
166  }
167 
170  return m_pX != it.m_pX;
171  }
172 
175  return isReverse ? m_pX->m_prev : m_pX->m_next;
176  }
177 
180  return isReverse ? m_pX->m_next : m_pX->m_prev;
181  }
182 
184  Elem& operator*() const { return m_pX->m_x; }
185 
189  m_pX = it.m_pX;
190  return *this;
191  }
192 
195  m_pX = isReverse ? m_pX->m_prev : m_pX->m_next;
196  return *this;
197  }
198 
202  m_pX = isReverse ? m_pX->m_prev : m_pX->m_next;
203  return it;
204  }
205 
208  m_pX = isReverse ? m_pX->m_next : m_pX->m_prev;
209  return *this;
210  }
211 
215  m_pX = isReverse ? m_pX->m_next : m_pX->m_prev;
216  return it;
217  }
218 
220 };
221 
223 
232 template<class E>
233 class ListPure {
234 protected:
237 
238 public:
240  using value_type = E;
242  using reference = E&;
244  using const_reference = const E&;
253 
255  ListPure() : m_head(nullptr), m_tail(nullptr) { }
256 
258  ListPure(std::initializer_list<E> init) : m_head(nullptr), m_tail(nullptr) {
259  for (const E& x : init) {
260  pushBack(x);
261  }
262  }
263 
265  ListPure(const ListPure<E>& L) : m_head(nullptr), m_tail(nullptr) { copy(L); }
266 
268 
271  ListPure(ListPure<E>&& L) noexcept : m_head(L.m_head), m_tail(L.m_tail) {
272  L.m_head = L.m_tail = nullptr;
274  }
275 
277  virtual ~ListPure() { clear(); }
278 
283 
286  bool empty() const { return m_head == nullptr; }
287 
289 
293  virtual int size() const {
294  int count = 0;
295  for (ListElement<E>* pX = m_head; pX; pX = pX->m_next) {
296  ++count;
297  }
298  return count;
299  }
300 
302 
306  OGDF_ASSERT(m_head != nullptr);
307  return m_head->m_x;
308  }
309 
311 
315  OGDF_ASSERT(m_head != nullptr);
316  return m_head->m_x;
317  }
318 
320 
324  OGDF_ASSERT(m_tail != nullptr);
325  return m_tail->m_x;
326  }
327 
329 
333  OGDF_ASSERT(m_tail != nullptr);
334  return m_tail->m_x;
335  }
336 
338 
341  const_iterator get(int pos) const {
342  ListElement<E>* pX;
343  for (pX = m_head; pX != nullptr; pX = pX->m_next) {
344  if (pos-- == 0) {
345  break;
346  }
347  }
348  return pX;
349  }
350 
352 
355  iterator get(int pos) {
356  ListElement<E>* pX;
357  for (pX = m_head; pX != nullptr; pX = pX->m_next) {
358  if (pos-- == 0) {
359  break;
360  }
361  }
362  return pX;
363  }
364 
366 
369  int pos(const_iterator it) const {
370  OGDF_ASSERT(it.listOf() == this);
371  int p = 0;
372  for (ListElement<E>* pX = m_head; pX != nullptr; pX = pX->m_next, ++p) {
373  if (pX == (const ListElement<E>*)it) {
374  break;
375  }
376  }
377  return p;
378  }
379 
381 
385 
388 
391  iterator begin() { return m_head; }
392 
394 
397  const_iterator begin() const { return m_head; }
398 
400 
403  const_iterator cbegin() const { return m_head; }
404 
406 
409  iterator end() { return iterator(); }
410 
412 
415  const_iterator end() const { return const_iterator(); }
416 
418 
421  const_iterator cend() const { return const_iterator(); }
422 
424 
428 
430 
434 
436 
440 
442 
446 
448 
452 
454 
458 
460 
464  OGDF_ASSERT(!it.valid() || it.listOf() == this);
465  const ListElement<E>* pX = it;
466  return (pX && pX->m_next) ? pX->m_next : m_head;
467  }
468 
470 
474  OGDF_ASSERT(!it.valid() || it.listOf() == this);
475  ListElement<E>* pX = it;
476  return (pX && pX->m_next) ? pX->m_next : m_head;
477  }
478 
483  OGDF_ASSERT(!it.valid() || it.listOf() == this);
484  const ListElement<E>* pX = it;
485  return (pX && pX->m_prev) ? pX->m_prev : m_tail;
486  }
487 
492  OGDF_ASSERT(!it.valid() || it.listOf() == this);
493  ListElement<E>* pX = it;
494  return (pX && pX->m_prev) ? pX->m_prev : m_tail;
495  }
496 
498 
502  OGDF_ASSERT(!it.valid() || it.listOf() == this);
503  const ListElement<E>* pX = it;
504  return (pX && pX->m_prev) ? pX->m_prev : m_tail;
505  }
506 
508 
512  OGDF_ASSERT(!it.valid() || it.listOf() == this);
513  ListElement<E>* pX = it;
514  return (pX && pX->m_prev) ? pX->m_prev : m_tail;
515  }
516 
521  OGDF_ASSERT(!it.valid() || it.listOf() == this);
522  const ListElement<E>* pX = it;
523  return (pX && pX->m_next) ? pX->m_next : m_head;
524  }
525 
530  OGDF_ASSERT(!it.valid() || it.listOf() == this);
531  ListElement<E>* pX = it;
532  return (pX && pX->m_next) ? pX->m_next : m_head;
533  }
534 
536 
540 
544  clear();
545  copy(L);
546  return *this;
547  }
548 
550 
554  clear();
555  m_head = L.m_head;
556  m_tail = L.m_tail;
557  L.m_head = L.m_tail = nullptr;
559  return *this;
560  }
561 
563  bool operator==(const ListPure<E>& L) const {
564  ListElement<E>*pX = m_head, *pY = L.m_head;
565  while (pX != nullptr && pY != nullptr) {
566  if (pX->m_x != pY->m_x) {
567  return false;
568  }
569  pX = pX->m_next;
570  pY = pY->m_next;
571  }
572  return pX == nullptr && pY == nullptr;
573  }
574 
576  bool operator!=(const ListPure<E>& L) const { return !operator==(L); }
577 
579 
583 
586  iterator pushFront(const E& x) {
587  ListElement<E>* pX = new ListElement<E>(this, x, m_head, nullptr);
588  if (m_head) {
589  m_head = m_head->m_prev = pX;
590  } else {
591  m_head = m_tail = pX;
592  }
593  return m_head;
594  }
595 
597 
600  template<class... Args>
601  iterator emplaceFront(Args&&... args) {
602  ListElement<E>* pX = new ListElement<E>(this, m_head, nullptr, std::forward<Args>(args)...);
603  if (m_head) {
604  m_head = m_head->m_prev = pX;
605  } else {
606  m_head = m_tail = pX;
607  }
608  return m_head;
609  }
610 
612  iterator pushBack(const E& x) {
613  ListElement<E>* pX = new ListElement<E>(this, x, nullptr, m_tail);
614  if (m_head) {
615  m_tail = m_tail->m_next = pX;
616  } else {
617  m_tail = m_head = pX;
618  }
619  return m_tail;
620  }
621 
623 
626  template<class... Args>
627  iterator emplaceBack(Args&&... args) {
628  ListElement<E>* pX = new ListElement<E>(this, nullptr, m_tail, std::forward<Args>(args)...);
629  if (m_head) {
630  m_tail = m_tail->m_next = pX;
631  } else {
632  m_tail = m_head = pX;
633  }
634  return m_tail;
635  }
636 
638 
646  OGDF_ASSERT(it.listOf() == this);
647  ListElement<E>*pY = it, *pX;
648  if (dir == Direction::after) {
649  ListElement<E>* pYnext = pY->m_next;
650  pY->m_next = pX = new ListElement<E>(this, x, pYnext, pY);
651  if (pYnext) {
652  pYnext->m_prev = pX;
653  } else {
654  m_tail = pX;
655  }
656  } else {
657  ListElement<E>* pYprev = pY->m_prev;
658  pY->m_prev = pX = new ListElement<E>(this, x, pY, pYprev);
659  if (pYprev) {
660  pYprev->m_next = pX;
661  } else {
662  m_head = pX;
663  }
664  }
665  return pX;
666  }
667 
669 
672  iterator insertBefore(const E& x, iterator it) {
673  OGDF_ASSERT(it.listOf() == this);
674  ListElement<E>*pY = it, *pX;
675  ListElement<E>* pYprev = pY->m_prev;
676  pY->m_prev = pX = new ListElement<E>(this, x, pY, pYprev);
677  if (pYprev) {
678  pYprev->m_next = pX;
679  } else {
680  m_head = pX;
681  }
682  return pX;
683  }
684 
686 
689  iterator insertAfter(const E& x, iterator it) {
690  OGDF_ASSERT(it.listOf() == this);
691  ListElement<E>*pY = it, *pX;
692  ListElement<E>* pYnext = pY->m_next;
693  pY->m_next = pX = new ListElement<E>(this, x, pYnext, pY);
694  if (pYnext) {
695  pYnext->m_prev = pX;
696  } else {
697  m_tail = pX;
698  }
699  return pX;
700  }
701 
703 
707 
710 
713  void popFront() {
714  OGDF_ASSERT(m_head != nullptr);
715  ListElement<E>* pX = m_head;
716  m_head = m_head->m_next;
717  delete pX;
718  if (m_head) {
719  m_head->m_prev = nullptr;
720  } else {
721  m_tail = nullptr;
722  }
723  }
724 
726 
730  E el = front();
731  popFront();
732  return el;
733  }
734 
736 
739  void popBack() {
740  OGDF_ASSERT(m_tail != nullptr);
741  ListElement<E>* pX = m_tail;
742  m_tail = m_tail->m_prev;
743  delete pX;
744  if (m_tail) {
745  m_tail->m_next = nullptr;
746  } else {
747  m_head = nullptr;
748  }
749  }
750 
752 
756  E el = back();
757  popBack();
758  return el;
759  }
760 
762 
765  void del(iterator it) {
766  OGDF_ASSERT(it.listOf() == this);
767  ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
768  delete pX;
769  if (pPrev) {
770  pPrev->m_next = pNext;
771  } else {
772  m_head = pNext;
773  }
774  if (pNext) {
775  pNext->m_prev = pPrev;
776  } else {
777  m_tail = pPrev;
778  }
779  }
780 
782 
788  bool removeFirst(const E& x) {
789  for (ListElement<E>* pX = m_head; pX != nullptr; pX = pX->m_next) {
790  if (pX->m_x == x) {
791  del(pX);
792  return true;
793  }
794  }
795  return false;
796  }
797 
799  void clear() {
800  if (m_head == nullptr) {
801  return;
802  }
803 
804  if (!std::is_trivially_destructible<E>::value) {
805  for (ListElement<E>* pX = m_head; pX != nullptr; pX = pX->m_next) {
806  pX->m_x.~E();
807  }
808  }
809  OGDF_ALLOCATOR::deallocateList(sizeof(ListElement<E>), m_head, m_tail);
810 
811  m_head = m_tail = nullptr;
812  }
813 
815 
819 
822 
825  void exchange(iterator it1, iterator it2) {
826  OGDF_ASSERT(it1.valid());
827  OGDF_ASSERT(it2.valid());
828  OGDF_ASSERT(it1 != it2);
829  ListElement<E>*pX = it1, *pY = it2;
830 
831  std::swap(pX->m_next, pY->m_next);
832  std::swap(pX->m_prev, pY->m_prev);
833 #ifdef OGDF_DEBUG
834  std::swap(pX->m_list, pY->m_list);
835 #endif
836 
837  if (pX->m_next == pX) {
838  pX->m_next = pY;
839  pY->m_prev = pX;
840  }
841  if (pX->m_prev == pX) {
842  pX->m_prev = pY;
843  pY->m_next = pX;
844  }
845 
846  if (pX->m_prev) {
847  pX->m_prev->m_next = pX;
848  } else {
849  m_head = pX;
850  }
851 
852  if (pY->m_prev) {
853  pY->m_prev->m_next = pY;
854  } else {
855  m_head = pY;
856  }
857 
858  if (pX->m_next) {
859  pX->m_next->m_prev = pX;
860  } else {
861  m_tail = pX;
862  }
863 
864  if (pY->m_next) {
865  pY->m_next->m_prev = pY;
866  } else {
867  m_tail = pY;
868  }
869  }
870 
872 
876  OGDF_ASSERT(it.listOf() == this);
877  // remove it
878  ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
879  //already at front
880  if (!pPrev) {
881  return;
882  }
883 
884  //update old position
885  if (pPrev) {
886  pPrev->m_next = pNext;
887  }
888  if (pNext) {
889  pNext->m_prev = pPrev;
890  } else {
891  m_tail = pPrev;
892  }
893  // insert it at front
894  pX->m_prev = nullptr;
895  pX->m_next = m_head;
896  m_head = m_head->m_prev = pX;
897  }
898 
900 
903  void moveToBack(iterator it) {
904  OGDF_ASSERT(it.listOf() == this);
905  // remove it
906  ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
907  //already at back
908  if (!pNext) {
909  return;
910  }
911 
912  //update old position
913  if (pPrev) {
914  pPrev->m_next = pNext;
915  } else {
916  m_head = pNext;
917  }
918  if (pNext) {
919  pNext->m_prev = pPrev;
920  }
921  // insert it at back
922  pX->m_prev = m_tail;
923  pX->m_next = nullptr;
924  m_tail = m_tail->m_next = pX;
925  }
926 
928 
931  void moveToSucc(iterator it, iterator itBefore) {
932  OGDF_ASSERT(it.listOf() == this);
933  OGDF_ASSERT(itBefore.listOf() == this);
934  // move it
935  ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
936  //the same of already in place
937  ListElement<E>* pY = itBefore;
938  if (pX == pY || pPrev == pY) {
939  return;
940  }
941 
942  // update old position
943  if (pPrev) {
944  pPrev->m_next = pNext;
945  } else {
946  m_head = pNext;
947  }
948  if (pNext) {
949  pNext->m_prev = pPrev;
950  } else {
951  m_tail = pPrev;
952  }
953  // move it after itBefore
954  ListElement<E>* pYnext = pX->m_next = pY->m_next;
955  (pX->m_prev = pY)->m_next = pX;
956  if (pYnext) {
957  pYnext->m_prev = pX;
958  } else {
959  m_tail = pX;
960  }
961  }
962 
964 
967  void moveToPrec(iterator it, iterator itAfter) {
968  OGDF_ASSERT(it.listOf() == this);
969  OGDF_ASSERT(itAfter.listOf() == this);
970  // move it
971  ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
972  //the same of already in place
973  ListElement<E>* pY = itAfter;
974  if (pX == pY || pNext == pY) {
975  return;
976  }
977 
978  // update old position
979  if (pPrev) {
980  pPrev->m_next = pNext;
981  } else {
982  m_head = pNext;
983  }
984  if (pNext) {
985  pNext->m_prev = pPrev;
986  } else {
987  m_tail = pPrev;
988  }
989  // move it before itAfter
990  ListElement<E>* pYprev = pX->m_prev = pY->m_prev;
991  (pX->m_next = pY)->m_prev = pX;
992  if (pYprev) {
993  pYprev->m_next = pX;
994  } else {
995  m_head = pX;
996  }
997  }
998 
1000 
1004  OGDF_ASSERT(it.listOf() == this);
1005  OGDF_ASSERT(this != &L2);
1006  // remove it
1007  ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
1008  if (pPrev) {
1009  pPrev->m_next = pNext;
1010  } else {
1011  m_head = pNext;
1012  }
1013  if (pNext) {
1014  pNext->m_prev = pPrev;
1015  } else {
1016  m_tail = pPrev;
1017  }
1018  // insert it at front of L2
1019  pX->m_prev = nullptr;
1020  if ((pX->m_next = L2.m_head) != nullptr) {
1021  L2.m_head = L2.m_head->m_prev = pX;
1022  } else {
1023  L2.m_head = L2.m_tail = pX;
1024  }
1025 
1026 #ifdef OGDF_DEBUG
1027  pX->m_list = &L2;
1028 #endif
1029  }
1030 
1032 
1036  OGDF_ASSERT(it.listOf() == this);
1037  OGDF_ASSERT(this != &L2);
1038  // remove it
1039  ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
1040  if (pPrev) {
1041  pPrev->m_next = pNext;
1042  } else {
1043  m_head = pNext;
1044  }
1045  if (pNext) {
1046  pNext->m_prev = pPrev;
1047  } else {
1048  m_tail = pPrev;
1049  }
1050  // insert it at back of L2
1051  pX->m_next = nullptr;
1052  if ((pX->m_prev = L2.m_tail) != nullptr) {
1053  L2.m_tail = L2.m_tail->m_next = pX;
1054  } else {
1055  L2.m_head = L2.m_tail = pX;
1056  }
1057 
1058 #ifdef OGDF_DEBUG
1059  pX->m_list = this;
1060 #endif
1061  }
1062 
1064 
1068  void moveToSucc(iterator it, ListPure<E>& L2, iterator itBefore) {
1069  OGDF_ASSERT(it.listOf() == this);
1070  OGDF_ASSERT(itBefore.listOf() == &L2);
1071  OGDF_ASSERT(this != &L2);
1072  // remove it
1073  ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
1074  if (pPrev) {
1075  pPrev->m_next = pNext;
1076  } else {
1077  m_head = pNext;
1078  }
1079  if (pNext) {
1080  pNext->m_prev = pPrev;
1081  } else {
1082  m_tail = pPrev;
1083  }
1084  // insert it in list L2 after itBefore
1085  ListElement<E>* pY = itBefore;
1086  ListElement<E>* pYnext = pX->m_next = pY->m_next;
1087  (pX->m_prev = pY)->m_next = pX;
1088  if (pYnext) {
1089  pYnext->m_prev = pX;
1090  } else {
1091  L2.m_tail = pX;
1092  }
1093 
1094 #ifdef OGDF_DEBUG
1095  pX->m_list = &L2;
1096 #endif
1097  }
1098 
1100 
1104  void moveToPrec(iterator it, ListPure<E>& L2, iterator itAfter) {
1105  OGDF_ASSERT(it.listOf() == this);
1106  OGDF_ASSERT(itAfter.listOf() == &L2);
1107  OGDF_ASSERT(this != &L2);
1108  // remove it
1109  ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
1110  if (pPrev) {
1111  pPrev->m_next = pNext;
1112  } else {
1113  m_head = pNext;
1114  }
1115  if (pNext) {
1116  pNext->m_prev = pPrev;
1117  } else {
1118  m_tail = pPrev;
1119  }
1120  // insert it in list L2 after itBefore
1121  ListElement<E>* pY = itAfter;
1122  ListElement<E>* pYprev = pX->m_prev = pY->m_prev;
1123  (pX->m_next = pY)->m_prev = pX;
1124  if (pYprev) {
1125  pYprev->m_next = pX;
1126  } else {
1127  L2.m_head = pX;
1128  }
1129 
1130 #ifdef OGDF_DEBUG
1131  pX->m_list = &L2;
1132 #endif
1133  }
1134 
1136  void conc(ListPure<E>& L2) {
1137  OGDF_ASSERT(this != &L2);
1138  if (m_head) {
1139  m_tail->m_next = L2.m_head;
1140  } else {
1141  m_head = L2.m_head;
1142  }
1143  if (L2.m_head) {
1144  L2.m_head->m_prev = m_tail;
1145  m_tail = L2.m_tail;
1146  }
1147 
1148  reassignListRefs(L2.m_head);
1149 
1150  L2.m_head = L2.m_tail = nullptr;
1151  }
1152 
1155  OGDF_ASSERT(this != &L2);
1156  if (m_head) {
1157  m_head->m_prev = L2.m_tail;
1158  } else {
1159  m_tail = L2.m_tail;
1160  }
1161  if (L2.m_head) {
1162  L2.m_tail->m_next = m_head;
1163  m_head = L2.m_head;
1164  }
1165 
1166  reassignListRefs(L2.m_head);
1167 
1168  L2.m_head = L2.m_tail = nullptr;
1169  }
1170 
1172  void swap(ListPure<E>& other) {
1173  std::swap(m_head, other.m_head);
1174  std::swap(m_tail, other.m_tail);
1175 
1176  reassignListRefs();
1177  other.reassignListRefs();
1178  }
1179 
1181 
1191  OGDF_ASSERT(!it.valid() || it.listOf() == this);
1192  if (&L1 != this) {
1193  L1.clear();
1194  }
1195  if (&L2 != this) {
1196  L2.clear();
1197  }
1198 
1199  if (it.valid()) {
1200  L1.m_head = m_head;
1201  L2.m_tail = m_tail;
1202  if (dir == Direction::before) {
1203  L2.m_head = it;
1204  L1.m_tail = L2.m_head->m_prev;
1205  } else {
1206  L1.m_tail = it;
1207  L2.m_head = L1.m_tail->m_next;
1208  }
1209  L2.m_head->m_prev = L1.m_tail->m_next = nullptr;
1210 
1211  } else {
1212  L1.m_head = L1.m_tail = nullptr;
1213  L2.m_head = m_head;
1214  L2.m_tail = m_tail;
1215  }
1216 
1217  if (this != &L1 && this != &L2) {
1218  m_head = m_tail = nullptr;
1219  }
1220 
1221  L1.reassignListRefs();
1222  L2.reassignListRefs();
1223  }
1224 
1227  OGDF_ASSERT(it.listOf() == this);
1228  OGDF_ASSERT(this != &L2);
1229  L2.clear();
1230  ListElement<E>* pX = it;
1231  if (pX != m_tail) {
1232  (L2.m_head = pX->m_next)->m_prev = nullptr;
1233  pX->m_next = nullptr;
1234  L2.m_tail = m_tail;
1235  m_tail = pX;
1236  }
1237 
1238  L2.reassignListRefs();
1239  }
1240 
1243  OGDF_ASSERT(it.listOf() == this);
1244  OGDF_ASSERT(this != &L2);
1245  L2.clear();
1246  ListElement<E>* pX = it;
1247  L2.m_head = pX;
1248  L2.m_tail = m_tail;
1249  if ((m_tail = pX->m_prev) == nullptr) {
1250  m_head = nullptr;
1251  } else {
1252  m_tail->m_next = nullptr;
1253  }
1254  pX->m_prev = nullptr;
1255 
1256  L2.reassignListRefs();
1257  }
1258 
1260  void reverse() {
1261  ListElement<E>* pX = m_head;
1262  m_head = m_tail;
1263  m_tail = pX;
1264  while (pX) {
1265  ListElement<E>* pY = pX->m_next;
1266  pX->m_next = pX->m_prev;
1267  pX = pX->m_prev = pY;
1268  }
1269  }
1270 
1272 
1276 
1280  ListConstIterator<E> search(const E& e) const {
1282  for (i = begin(); i.valid(); ++i) {
1283  if (*i == e) {
1284  return i;
1285  }
1286  }
1287  return i;
1288  }
1289 
1292  ListIterator<E> search(const E& e) {
1293  ListIterator<E> i;
1294  for (i = begin(); i.valid(); ++i) {
1295  if (*i == e) {
1296  return i;
1297  }
1298  }
1299  return i;
1300  }
1301 
1305  template<class COMPARER>
1306  ListConstIterator<E> search(const E& e, const COMPARER& comp) const {
1308  for (i = begin(); i.valid(); ++i) {
1309  if (comp.equal(*i, e)) {
1310  return i;
1311  }
1312  }
1313  return i;
1314  }
1315 
1319  template<class COMPARER>
1320  ListIterator<E> search(const E& e, const COMPARER& comp) {
1321  ListIterator<E> i;
1322  for (i = begin(); i.valid(); ++i) {
1323  if (comp.equal(*i, e)) {
1324  return i;
1325  }
1326  }
1327  return i;
1328  }
1329 
1332 
1334  template<class COMPARER>
1335  void quicksort(const COMPARER& comp) {
1336  ogdf::quicksortTemplate(*this, comp);
1337  }
1338 
1340 
1347  void bucketSort(int l, int h, BucketFunc<E>& f);
1348 
1350 
1354 
1365  std::function<bool(const E&)> includeElement = [](const E&) { return true; },
1366  bool isFastTest = true) const {
1367  return chooseIteratorFrom(*this, includeElement, isFastTest);
1368  }
1369 
1372  std::function<bool(const E&)> includeElement = [](const E&) { return true; },
1373  bool isFastTest = true) {
1374  return chooseIteratorFrom(*this, includeElement, isFastTest);
1375  }
1376 
1386  std::function<bool(const E&)> includeElement = [](const E&) { return true; },
1387  bool isFastTest = true) const {
1388  const_iterator result = chooseIterator(includeElement, isFastTest);
1389  OGDF_ASSERT(result.valid());
1390  return *result;
1391  }
1392 
1395  std::function<bool(const E&)> includeElement = [](const E&) { return true; },
1396  bool isFastTest = true) {
1397  iterator result = chooseIterator(includeElement, isFastTest);
1398  OGDF_ASSERT(result.valid());
1399  return *result;
1400  }
1401 
1403  void permute() {
1404  std::minstd_rand rng(randomSeed());
1405  permute(size(), rng);
1406  }
1407 
1409  template<class RNG>
1410  void permute(RNG& rng) {
1411  permute(size(), rng);
1412  }
1413 
1415 
1416 protected:
1417  void copy(const ListPure<E>& L) {
1418  for (ListElement<E>* pX = L.m_head; pX != nullptr; pX = pX->m_next) {
1419  pushBack(pX->m_x);
1420  }
1421  }
1422 
1423  template<class RNG>
1424 
1426  void permute(const int n, RNG& rng);
1427 
1429  inline void reassignListRefs(ListElement<E>* start = nullptr) {
1430 #ifdef OGDF_DEBUG
1431  for (auto e = start == nullptr ? m_head : start; e != nullptr; e = e->m_next) {
1432  e->m_list = this;
1433  }
1434 #endif
1435  }
1436 
1438 };
1439 
1441 
1450 template<class E>
1451 class List : private ListPure<E> {
1452  int m_count;
1453 
1454 public:
1455  using typename ListPure<E>::value_type;
1456  using typename ListPure<E>::reference;
1457  using typename ListPure<E>::const_reference;
1458  using typename ListPure<E>::const_iterator;
1459  using typename ListPure<E>::iterator;
1460  using typename ListPure<E>::const_reverse_iterator;
1461  using typename ListPure<E>::reverse_iterator;
1462 
1464  List() : m_count(0) { }
1465 
1467  List(std::initializer_list<E> init) : ListPure<E>(init), m_count((int)init.size()) { }
1468 
1470  List(const List<E>& L) : ListPure<E>(L), m_count(L.m_count) { }
1471 
1473 
1476  List(List<E>&& L) noexcept : ListPure<E>(std::move(L)), m_count(L.m_count) { L.m_count = 0; }
1477 
1482 
1485 
1488  int size() const { return m_count; }
1489 
1491  const ListPure<E>& getListPure() const { return *this; }
1492 
1494 
1498 
1503  m_count = L.m_count;
1504  return *this;
1505  }
1506 
1508 
1512  m_count = L.m_count;
1514  L.m_count = 0;
1515  return *this;
1516  }
1517 
1519  bool operator==(const List<E>& L) const {
1520  return (m_count == L.m_count) && ListPure<E>::operator==(L);
1521  }
1522 
1524  bool operator!=(const List<E>& L) const { return !operator==(L); }
1525 
1527 
1531 
1534  iterator pushFront(const E& x) {
1535  ++m_count;
1536  return ListPure<E>::pushFront(x);
1537  }
1538 
1540  template<class... Args>
1541  iterator emplaceFront(Args&&... args) {
1542  ++m_count;
1543  return ListPure<E>::emplaceFront(std::forward<Args>(args)...);
1544  }
1545 
1547  iterator pushBack(const E& x) {
1548  ++m_count;
1549  return ListPure<E>::pushBack(x);
1550  }
1551 
1553  template<class... Args>
1554  iterator emplaceBack(Args&&... args) {
1555  ++m_count;
1556  return ListPure<E>::emplaceBack(std::forward<Args>(args)...);
1557  }
1558 
1560  iterator insert(const E& x, iterator it, Direction dir = Direction::after) {
1561  ++m_count;
1562  return ListPure<E>::insert(x, it, dir);
1563  }
1564 
1566  iterator insertBefore(const E& x, iterator it) {
1567  ++m_count;
1568  return ListPure<E>::insertBefore(x, it);
1569  }
1570 
1572  iterator insertAfter(const E& x, iterator it) {
1573  ++m_count;
1574  return ListPure<E>::insertAfter(x, it);
1575  }
1576 
1578 
1582 
1585  void popFront() {
1586  --m_count;
1588  }
1589 
1592  E el = front();
1593  popFront();
1594  return el;
1595  }
1596 
1598  void popBack() {
1599  --m_count;
1601  }
1602 
1605  E el = back();
1606  popBack();
1607  return el;
1608  }
1609 
1611  void del(iterator it) {
1612  --m_count;
1613  ListPure<E>::del(it);
1614  }
1615 
1617  bool removeFirst(const E& x) {
1618  bool hasRemoved = ListPure<E>::removeFirst(x);
1619  if (hasRemoved) {
1620  --m_count;
1621  }
1622  return hasRemoved;
1623  }
1624 
1626  void clear() {
1627  m_count = 0;
1629  }
1630 
1632 
1636 
1639  void moveToFront(iterator it, List<E>& L2) {
1640  ListPure<E>::moveToFront(it, L2);
1641  --m_count;
1642  ++L2.m_count;
1643  }
1644 
1646  void moveToBack(iterator it, List<E>& L2) {
1647  ListPure<E>::moveToBack(it, L2);
1648  --m_count;
1649  ++L2.m_count;
1650  }
1651 
1653  void moveToSucc(iterator it, List<E>& L2, iterator itBefore) {
1654  ListPure<E>::moveToSucc(it, L2, itBefore);
1655  --m_count;
1656  ++L2.m_count;
1657  }
1658 
1660  void moveToPrec(iterator it, List<E>& L2, iterator itAfter) {
1661  ListPure<E>::moveToPrec(it, L2, itAfter);
1662  --m_count;
1663  ++L2.m_count;
1664  }
1665 
1667  void conc(List<E>& L2) {
1668  ListPure<E>::conc(L2);
1669  m_count += L2.m_count;
1670  L2.m_count = 0;
1671  }
1672 
1674  void concFront(List<E>& L2) {
1676  m_count += L2.m_count;
1677  L2.m_count = 0;
1678  }
1679 
1681  void swap(List<E>& other) {
1682  ListPure<E>::swap(other);
1683  std::swap(m_count, other.m_count);
1684  }
1685 
1687  void split(iterator it, List<E>& L1, List<E>& L2, Direction dir = Direction::before) {
1688  ListPure<E>::split(it, L1, L2, dir);
1689  int countL = m_count, countL1 = 0;
1690  for (ListElement<E>* pX = L1.m_head; pX != nullptr; pX = pX->m_next) {
1691  ++countL1;
1692  }
1693 
1694  L1.m_count = countL1;
1695  L2.m_count = countL - countL1;
1696  if (this->m_head == nullptr) {
1697  m_count = 0;
1698  }
1699  }
1700 
1701  using ListPure<E>::empty;
1702  using ListPure<E>::front;
1703  using ListPure<E>::back;
1704  using ListPure<E>::get;
1705  using ListPure<E>::pos;
1706  using ListPure<E>::begin;
1707  using ListPure<E>::cbegin;
1708  using ListPure<E>::end;
1709  using ListPure<E>::cend;
1710  using ListPure<E>::rbegin;
1711  using ListPure<E>::crbegin;
1712  using ListPure<E>::rend;
1713  using ListPure<E>::crend;
1716  using ListPure<E>::exchange;
1721  using ListPure<E>::reverse;
1722  using ListPure<E>::search;
1723  using ListPure<E>::quicksort;
1727  using ListPure<E>::permute;
1728 
1730 };
1731 
1732 template<class E>
1733 void ListPure<E>::bucketSort(int l, int h, BucketFunc<E>& f) {
1734  if (m_head == m_tail) {
1735  return;
1736  }
1737 
1738  Array<ListElement<E>*> head(l, h, nullptr), tail(l, h);
1739 
1740  ListElement<E>* pX;
1741  for (pX = m_head; pX; pX = pX->m_next) {
1742  int i = f.getBucket(pX->m_x);
1743  if (head[i]) {
1744  tail[i] = ((pX->m_prev = tail[i])->m_next = pX);
1745  } else {
1746  head[i] = tail[i] = pX;
1747  }
1748  }
1749 
1750  ListElement<E>* pY = nullptr;
1751  for (int i = l; i <= h; i++) {
1752  pX = head[i];
1753  if (pX) {
1754  if (pY) {
1755  (pY->m_next = pX)->m_prev = pY;
1756  } else {
1757  (m_head = pX)->m_prev = nullptr;
1758  }
1759  pY = tail[i];
1760  }
1761  }
1762 
1763  m_tail = pY;
1764  pY->m_next = nullptr;
1765 }
1766 
1767 template<class E>
1768 template<class RNG>
1769 void ListPure<E>::permute(const int n, RNG& rng) {
1770  //if n==0 do nothing
1771  if (n == 0) {
1772  return;
1773  }
1774 
1775  Array<ListElement<E>*> A(n + 2);
1776  A[0] = A[n + 1] = nullptr;
1777 
1778  int i = 1;
1779  ListElement<E>* pX;
1780  for (pX = m_head; pX; pX = pX->m_next) {
1781  A[i++] = pX;
1782  }
1783 
1784  A.permute(1, n, rng);
1785 
1786  for (i = 1; i <= n; i++) {
1787  pX = A[i];
1788  pX->m_next = A[i + 1];
1789  pX->m_prev = A[i - 1];
1790  }
1791 
1792  m_head = A[1];
1793  m_tail = A[n];
1794 }
1795 
1797 template<class E>
1798 void print(std::ostream& os, const ListPure<E>& L, char delim = ' ') {
1799  typename ListPure<E>::const_iterator pX = L.begin();
1800  if (pX.valid()) {
1801  os << *pX;
1802  for (++pX; pX.valid(); ++pX) {
1803  os << delim << *pX;
1804  }
1805  }
1806 }
1807 
1809 template<class E>
1810 void print(std::ostream& os, const List<E>& L, char delim = ' ') {
1811  print(os, L.getListPure(), delim);
1812 }
1813 
1815 template<class E>
1816 std::ostream& operator<<(std::ostream& os, const ListPure<E>& L) {
1817  print(os, L);
1818  return os;
1819 }
1820 
1822 template<class E>
1823 std::ostream& operator<<(std::ostream& os, const List<E>& L) {
1824  return os << L.getListPure();
1825 }
1826 
1827 template<class E, class Master>
1828 class ListContainer : public List<E> {
1829  friend Master;
1830 
1831 public:
1836 
1838  iterator begin() const { return List<E>::cbegin(); }
1839 
1841  iterator end() const { return List<E>::cend(); }
1842 
1845 
1847  reverse_iterator rend() const { return List<E>::crend(); }
1848 
1850  int size() const { return List<E>::size(); }
1851 };
1852 
1853 }
ogdf::ListPure::begin
const_iterator begin() const
Returns a const iterator to the first element of the list.
Definition: List.h:397
ogdf::ListElement::ListElement
ListElement(ListPure< E > *list, const E &x, ListElement< E > *next, ListElement< E > *prev)
Constructs a ListElement.
Definition: List.h:84
ogdf::ListPure::reassignListRefs
void reassignListRefs(ListElement< E > *start=nullptr)
Sets the debug reference of all list elements starting at start to this.
Definition: List.h:1429
ogdf::ListPure< TObserver * >::reference
TObserver * & reference
Provides a reference to an element stored in a list.
Definition: List.h:242
ogdf
The namespace for all OGDF objects.
Definition: multilevelmixer.cpp:39
ogdf::ListIteratorBase::pred
ListIteratorBase< E, isConst, isReverse > pred() const
Returns predecessor iterator.
Definition: List.h:179
ogdf::ListPure::permute
void permute(RNG &rng)
Randomly permutes the elements in the list using random number generator rng.
Definition: List.h:1410
ogdf::chooseIteratorFrom
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.
Definition: list_templates.h:221
ogdf::ListPure::split
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.
Definition: List.h:1190
ogdf::ListElement::m_x
E m_x
Stores the content.
Definition: List.h:78
ogdf::ListPure::moveToPrec
void moveToPrec(iterator it, ListPure< E > &L2, iterator itAfter)
Moves it to list L2 and inserts it before itAfter.
Definition: List.h:1104
ogdf::Direction
Direction
Definition: basic.h:150
ogdf::ListPure::chooseIterator
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: List.h:1364
ogdf::List::moveToBack
void moveToBack(iterator it, List< E > &L2)
Moves it to the end of the list.
Definition: List.h:1646
ogdf::ListPure::m_head
ListElement< E > * m_head
Pointer to first element.
Definition: List.h:235
ogdf::ListPure::const_reverse_iterator
ListConstReverseIterator< E > const_reverse_iterator
Provides a bidirectional reverse iterator that can read a const element in a list.
Definition: List.h:250
ogdf::ListIteratorBase< ogdf::Graph::HiddenEdgeSet * >::value_type
Elem value_type
Definition: List.h:128
ogdf::ListPure::copy
void copy(const ListPure< E > &L)
Definition: List.h:1417
ogdf::ListPure::clear
void clear()
Removes all elements from the list.
Definition: List.h:799
ogdf::ListIteratorBase::ListIteratorBase
ListIteratorBase(const ListIteratorBase< E, isArgConst, isArgReverse > &it)
Constructs an iterator that is a copy of it.
Definition: List.h:144
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:66
ogdf::List::conc
void conc(List< E > &L2)
Appends L2 to this list and makes L2 empty.
Definition: List.h:1667
ogdf::List::swap
void swap(List< E > &other)
Exchanges the contents of this list and other in constant time.
Definition: List.h:1681
ogdf::ListPure::splitAfter
void splitAfter(iterator it, ListPure< E > &L2)
Splits the list after it.
Definition: List.h:1226
ogdf::ListIteratorBase::operator++
ListIteratorBase< E, isConst, isReverse > & operator++()
Increment operator (prefix).
Definition: List.h:194
ogdf::ListPure::bucketSort
void bucketSort(int l, int h, BucketFunc< E > &f)
Sorts the list using bucket sort.
Definition: List.h:1733
ogdf::ListElement::m_list
ListPure< E > * m_list
List object that the element belongs to.
Definition: List.h:80
ogdf::ListElement::ListElement
ListElement(ListPure< E > *list, const E &x)
Constructs a ListElement.
Definition: List.h:92
ogdf::List::popFront
void popFront()
Removes the first element from the list.
Definition: List.h:1585
ogdf::ListContainer::Master
friend Master
Definition: List.h:1829
ogdf::ListPure::moveToSucc
void moveToSucc(iterator it, ListPure< E > &L2, iterator itBefore)
Moves it to list L2 and inserts it after itBefore.
Definition: List.h:1068
ogdf::ListPure::cyclicSucc
iterator cyclicSucc(iterator it)
Returns an iterator to the cyclic successor of it.
Definition: List.h:473
ogdf::ListPure::back
reference back()
Returns a reference to the last element.
Definition: List.h:332
ogdf::List::split
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.
Definition: List.h:1687
ogdf::ListPure::size
virtual int size() const
Returns the number of elements in the list.
Definition: List.h:293
ogdf::List::List
List(std::initializer_list< E > init)
Constructs a doubly linked list containing the elements in init.
Definition: List.h:1467
ogdf::ListPure::emplaceFront
iterator emplaceFront(Args &&... args)
Adds a new element at the beginning of the list.
Definition: List.h:601
ogdf::ListPure::back
const_reference back() const
Returns a const reference to the last element.
Definition: List.h:323
ogdf::List::popFrontRet
E popFrontRet()
Removes the first element from the list and returns it.
Definition: List.h:1591
ogdf::whaType::A
@ A
ogdf::ListIteratorBase::operator!=
bool operator!=(const ListIteratorBase< E, isConst, isReverse > &it) const
Inequality operator.
Definition: List.h:169
ogdf::ListPure::operator==
bool operator==(const ListPure< E > &L) const
Equality operator.
Definition: List.h:563
ogdf::ListPure::insertAfter
iterator insertAfter(const E &x, iterator it)
Inserts element x after it.
Definition: List.h:689
ogdf::ListPure::begin
iterator begin()
Returns an iterator to the first element of the list.
Definition: List.h:391
ogdf::ListPure::popBackRet
E popBackRet()
Removes the last element from the list and returns it.
Definition: List.h:755
ogdf::ListIteratorBase::valid
bool valid() const
Returns true iff the iterator points to an element.
Definition: List.h:153
ogdf::List::operator==
bool operator==(const List< E > &L) const
Equality operator.
Definition: List.h:1519
ogdf::ListPure::crbegin
const_reverse_iterator crbegin() const
Returns a const iterator to the last element of the list.
Definition: List.h:439
ogdf::ListPure::popFront
void popFront()
Removes the first element from the list.
Definition: List.h:713
ogdf::BucketFunc
Abstract base class for bucket functions.
Definition: basic.h:257
ogdf::Direction::before
@ before
ogdf::ListPure::iterator
ListIterator< E > iterator
Provides a bidirectional iterator that can read or modify any element in a list.
Definition: List.h:248
ogdf::ListPure::cyclicSucc
const_iterator cyclicSucc(const_iterator it) const
Returns a const iterator to the cyclic successor of it.
Definition: List.h:463
ogdf::List::operator=
List< E > & operator=(const List< E > &L)
Assignment operator.
Definition: List.h:1501
ogdf::ListPure::exchange
void exchange(iterator it1, iterator it2)
Exchanges the positions of it1 and it2 in the list.
Definition: List.h:825
ogdf::ListPure::get
const_iterator get(int pos) const
Returns a const iterator pointing to the element at position pos.
Definition: List.h:341
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:85
ogdf::List::insertAfter
iterator insertAfter(const E &x, iterator it)
Inserts element x after it.
Definition: List.h:1572
ogdf::ListContainer< ogdf::ClusterElement, ogdf::ClusterElement >::reverse_iterator
typename List< ogdf::ClusterElement >::const_reverse_iterator reverse_iterator
Provides a bidirectional reverse iterator to an object in the container.
Definition: List.h:1835
ogdf::ListPure::search
ListIterator< E > search(const E &e)
Scans the list for the specified element and returns an iterator to the first occurrence in the list,...
Definition: List.h:1292
ogdf::ListContainer::rbegin
reverse_iterator rbegin() const
Returns a reverse iterator to the last element in the container.
Definition: List.h:1844
ogdf::ListElement::m_next
ListElement< E > * m_next
Pointer to successor element.
Definition: List.h:76
ogdf::ListPure::conc
void conc(ListPure< E > &L2)
Appends L2 to this list and makes L2 empty.
Definition: List.h:1136
ogdf::ListPure::ListPure
ListPure(std::initializer_list< E > init)
Constructs a doubly linked list containing the elements in init.
Definition: List.h:258
ogdf::List::concFront
void concFront(List< E > &L2)
Prepends L2 to this list and makes L2 empty.
Definition: List.h:1674
ogdf::ListPure::ListPure
ListPure(ListPure< E > &&L) noexcept
Constructs a doubly linked list containing the elements of L (move semantics).
Definition: List.h:271
ogdf::ListPure::end
iterator end()
Returns an iterator to one-past-last element of the list.
Definition: List.h:409
ogdf::ListPure::operator=
ListPure< E > & operator=(const ListPure< E > &L)
Assignment operator.
Definition: List.h:543
ogdf::List::m_count
int m_count
The length of the list.
Definition: List.h:1452
ogdf::ListContainer::size
int size() const
Returns the number of elements in the container.
Definition: List.h:1850
ogdf::ListPure::moveToBack
void moveToBack(iterator it)
Moves it to the end of the list.
Definition: List.h:903
ogdf::List::insert
iterator insert(const E &x, iterator it, Direction dir=Direction::after)
Inserts element x before or after it.
Definition: List.h:1560
ogdf::ListPure::moveToSucc
void moveToSucc(iterator it, iterator itBefore)
Moves it after itBefore.
Definition: List.h:931
ogdf::ListIteratorBase::ListIteratorBase
ListIteratorBase(ListElem *pX)
Constructs an iterator that points to pX.
Definition: List.h:137
ogdf::ListPure::end
const_iterator end() const
Returns a const iterator to one-past-last element of the list.
Definition: List.h:415
ogdf::ListIteratorBase::succ
ListIteratorBase< E, isConst, isReverse > succ() const
Returns successor iterator.
Definition: List.h:174
ogdf::ListElement::ListElement
ListElement(ListPure< E > *list, ListElement< E > *next, ListElement< E > *prev, Args &&... args)
Constructs a ListElement with given arguments args for constructor of element type.
Definition: List.h:96
ogdf::ListContainer< ogdf::ClusterElement, ogdf::ClusterElement >::iterator
typename List< ogdf::ClusterElement >::const_iterator iterator
Provides a bidirectional iterator to an object in the container.
Definition: List.h:1833
ogdf::ListIteratorBase::m_pX
ListElem * m_pX
pointer to list element
Definition: List.h:124
ogdf::ListPure::ListPure
ListPure(const ListPure< E > &L)
Constructs a doubly linked list that is a copy of L.
Definition: List.h:265
ogdf::List::operator=
List< E > & operator=(List< E > &&L)
Assignment operator (move semantics).
Definition: List.h:1511
ogdf::ListIteratorBase::operator--
ListIteratorBase< E, isConst, isReverse > operator--(int)
Decrement operator (postfix).
Definition: List.h:213
ogdf::ListPure::popFrontRet
E popFrontRet()
Removes the first element from the list and returns it.
Definition: List.h:729
ogdf::Direction::after
@ after
ogdf::ListPure::cyclicPred
const_iterator cyclicPred(const_iterator it) const
Returns a const iterator to the cyclic predecessor of it.
Definition: List.h:501
list_templates.h
Implementation of algorithms as templates working with different list types.
ogdf::ListPure::concFront
void concFront(ListPure< E > &L2)
Prepends L2 to this list and makes L2 empty.
Definition: List.h:1154
ogdf::ListIteratorBase::operator*
Elem & operator*() const
Returns a reference to the element content.
Definition: List.h:184
ogdf::ListPure::cyclicPred
iterator cyclicPred(iterator it)
Returns an iterator to the cyclic predecessor of it.
Definition: List.h:511
ogdf::List::pushFront
iterator pushFront(const E &x)
Adds element x at the beginning of the list.
Definition: List.h:1534
ogdf::ListIteratorBase< ogdf::Graph::HiddenEdgeSet * >::pointer
value_type * pointer
Definition: List.h:130
ogdf::ListPure::moveToFront
void moveToFront(iterator it)
Moves it to the begin of the list.
Definition: List.h:875
ogdf::ListPure::search
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...
Definition: List.h:1306
backward::Color::type
type
Definition: backward.hpp:1716
ogdf::ListPure::chooseIterator
iterator chooseIterator(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
Returns an iterator to a random element.
Definition: List.h:1371
backward::details::move
const T & move(const T &v)
Definition: backward.hpp:243
ogdf::Array
The parameterized class Array implements dynamic arrays of type E.
Definition: Array.h:219
ogdf::ListPure::swap
void swap(ListPure< E > &other)
Exchanges the contents of this list and other in constant time.
Definition: List.h:1172
ogdf::ListPure::~ListPure
virtual ~ListPure()
Destructor.
Definition: List.h:277
ogdf::ListContainer::begin
iterator begin() const
Returns an iterator to the first element in the container.
Definition: List.h:1838
ogdf::List::moveToSucc
void moveToSucc(iterator it, List< E > &L2, iterator itBefore)
Moves it after itBefore.
Definition: List.h:1653
ogdf::List::moveToPrec
void moveToPrec(iterator it, List< E > &L2, iterator itAfter)
Moves it before itAfter.
Definition: List.h:1660
ogdf::ListIteratorBase::operator++
ListIteratorBase< E, isConst, isReverse > operator++(int)
Increment operator (postfix).
Definition: List.h:200
ogdf::ListPure::chooseElement
const_reference chooseElement(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
Returns a random element.
Definition: List.h:1385
ogdf::ListPure::emplaceBack
iterator emplaceBack(Args &&... args)
Adds a new element at the end of the list.
Definition: List.h:627
ogdf::ListPure::moveToBack
void moveToBack(iterator it, ListPure< E > &L2)
Moves it to the end of L2.
Definition: List.h:1035
ogdf::operator<<
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition: Array.h:983
config_autogen.h
ogdf::ListPure::rbegin
reverse_iterator rbegin()
Returns an iterator to the last element of the list.
Definition: List.h:427
ogdf::ListPure::cbegin
const_iterator cbegin() const
Returns a const iterator to the first element of the list.
Definition: List.h:403
ogdf::ListPure::rend
reverse_iterator rend()
Returns an iterator to one-before-first element of the list.
Definition: List.h:445
ogdf::ListIteratorBase::operator--
ListIteratorBase< E, isConst, isReverse > & operator--()
Decrement operator (prefix).
Definition: List.h:207
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: DfsMakeBiconnected.h:40
ogdf::ListPure::reverse
void reverse()
Reverses the order of the list elements.
Definition: List.h:1260
ogdf::ListPure::search
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...
Definition: List.h:1320
ogdf::ListIteratorBase< ogdf::Graph::HiddenEdgeSet * >::reference
value_type & reference
Definition: List.h:131
ogdf::ListPure::popBack
void popBack()
Removes the last element from the list.
Definition: List.h:739
ogdf::ListPure::cend
const_iterator cend() const
Returns a const iterator to one-past-last element of the list.
Definition: List.h:421
ogdf::ListPure::const_iterator
ListConstIterator< E > const_iterator
Provides a bidirectional iterator that can read a const element in a list.
Definition: List.h:246
ogdf::List::popBackRet
E popBackRet()
Removes the last element from the list and returns it.
Definition: List.h:1604
ogdf::ListPure::insertBefore
iterator insertBefore(const E &x, iterator it)
Inserts element x before it.
Definition: List.h:672
ogdf::ListPure::cyclicPred
reverse_iterator cyclicPred(reverse_iterator it)
Definition: List.h:529
ogdf::ListPure::operator!=
bool operator!=(const ListPure< E > &L) const
Inequality operator.
Definition: List.h:576
ogdf::ListPure::removeFirst
bool removeFirst(const E &x)
Removes the first occurrence of x (if any) from the list.
Definition: List.h:788
ogdf::ListPure::moveToPrec
void moveToPrec(iterator it, iterator itAfter)
Moves it before itAfter.
Definition: List.h:967
ogdf::ListPure::rend
const_reverse_iterator rend() const
Returns a const iterator to one-before-first element of the list.
Definition: List.h:451
ogdf::List::List
List()
Constructs an empty doubly linked list.
Definition: List.h:1464
ogdf::ListPure::operator=
ListPure< E > & operator=(ListPure< E > &&L)
Assignment operator (move semantics).
Definition: List.h:553
ogdf::ListPure::rbegin
const_reverse_iterator rbegin() const
Returns a const iterator to the last element of the list.
Definition: List.h:433
ogdf::ListContainer
Definition: List.h:1828
ogdf::ListPure
Doubly linked lists.
Definition: List.h:55
ogdf::randomSeed
long unsigned int randomSeed()
Returns a random value suitable as initial seed for a random number engine.
ogdf::ListElement
Structure for elements of doubly linked lists.
Definition: List.h:68
ogdf::ListPure::cyclicSucc
const_reverse_iterator cyclicSucc(const_reverse_iterator it) const
Definition: List.h:482
ogdf::ListPure::ListPure
ListPure()
Constructs an empty doubly linked list.
Definition: List.h:255
ogdf::ListIteratorBase< ogdf::Graph::HiddenEdgeSet * >::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: List.h:129
ogdf::ListIteratorBase::operator==
bool operator==(const ListIteratorBase< E, isConst, isReverse > &it) const
Equality operator.
Definition: List.h:164
ogdf::ListPure::quicksort
void quicksort()
Sorts the list using Quicksort.
Definition: List.h:1331
ogdf::ListPure::pos
int pos(const_iterator it) const
Returns the position (starting with 0) of iterator it in the list.
Definition: List.h:369
ogdf::graphics::init
void init()
Definition: graphics.h:450
ogdf::ListIteratorBase::operator=
ListIteratorBase< E, isConst, isReverse > & operator=(const ListIteratorBase< E, isConst, isReverse > &it)
Assignment operator.
Definition: List.h:187
ogdf::List::getListPure
const ListPure< E > & getListPure() const
Conversion to const ListPure.
Definition: List.h:1491
ogdf::List::del
void del(iterator it)
Removes it from the list.
Definition: List.h:1611
basic.h
Basic declarations, included by all source files.
ogdf::ListPure::cyclicPred
const_reverse_iterator cyclicPred(const_reverse_iterator it) const
Definition: List.h:520
std
Definition: GML.h:111
ogdf::List::popBack
void popBack()
Removes the last element from the list.
Definition: List.h:1598
ogdf::ListIteratorBase::ListElem
typename std::conditional< isConst, const ListElement< E >, ListElement< E > >::type ListElem
The underlying list element, depending on isConst.
Definition: List.h:119
ogdf::ListContainer::end
iterator end() const
Returns an iterator to the one-past-last element in the container.
Definition: List.h:1841
ogdf::ListContainer::rend
reverse_iterator rend() const
Returns a reverse iterator to the one-before-first element in the container.
Definition: List.h:1847
ogdf::ListPure::crend
const_reverse_iterator crend() const
Returns a const iterator to one-before-first element of the list.
Definition: List.h:457
ogdf::ListIteratorBase::ListIteratorBase
ListIteratorBase()
Constructs an invalid iterator.
Definition: List.h:140
Array.h
Declaration and implementation of Array class and Array algorithms.
ogdf::ListIteratorBase::listOf
ListPure< E > * listOf()
Returns the list that this iterator belongs to.
Definition: List.h:158
ogdf::ListPure::moveToFront
void moveToFront(iterator it, ListPure< E > &L2)
Moves it to the begin of L2.
Definition: List.h:1003
ogdf::print
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
ogdf::ListPure::front
reference front()
Returns a reference to the first element.
Definition: List.h:314
ogdf::ListPure::front
const_reference front() const
Returns a const reference to the first element.
Definition: List.h:305
ogdf::ListPure::quicksort
void quicksort(const COMPARER &comp)
Sorts the list using Quicksort and comparer comp.
Definition: List.h:1335
ogdf::List::size
int size() const
Returns the number of elements in the list.
Definition: List.h:1488
ogdf::ListPure::get
iterator get(int pos)
Returns an iterator pointing to the element at position pos.
Definition: List.h:355
ogdf::ListIteratorBase
Encapsulates a pointer to a list element.
Definition: List.h:51
ogdf::List::List
List(List< E > &&L) noexcept
Constructs a doubly linked list containing the elements of L (move semantics).
Definition: List.h:1476
ogdf::ListPure::cyclicSucc
reverse_iterator cyclicSucc(reverse_iterator it)
Definition: List.h:491
ogdf::List::emplaceFront
iterator emplaceFront(Args &&... args)
Adds a new element at the beginning of the list.
Definition: List.h:1541
ogdf::ListPure::m_tail
ListElement< E > * m_tail
Pointer to last element.
Definition: List.h:236
ogdf::ListPure::chooseElement
reference chooseElement(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
Returns a random element.
Definition: List.h:1394
ogdf::quicksortTemplate
void quicksortTemplate(LIST &L)
Definition: list_templates.h:79
ogdf::ListIteratorBase::ListIteratorBase
ListIteratorBase(const ListIteratorBase< E, isConst, isReverse > &it)
Copy constructor.
Definition: List.h:149
ogdf::ListPure::search
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,...
Definition: List.h:1280
ogdf::ListPure::splitBefore
void splitBefore(iterator it, ListPure< E > &L2)
Splits the list before it.
Definition: List.h:1242
ogdf::ListPure::pushFront
iterator pushFront(const E &x)
Adds element x at the beginning of the list.
Definition: List.h:586
ogdf::ListPure::del
void del(iterator it)
Removes it from the list.
Definition: List.h:765
ogdf::List::removeFirst
bool removeFirst(const E &x)
Removes the first occurrence of x (if any) from the list.
Definition: List.h:1617
memory.h
Declaration of memory manager for allocating small pieces of memory.
ogdf::List::operator!=
bool operator!=(const List< E > &L) const
Inequality operator.
Definition: List.h:1524
ogdf::ListPure< TObserver * >::const_reference
const TObserver * & const_reference
Provides a reference to a const element stored in a list for reading and performing const operations.
Definition: List.h:244
ogdf::List::List
List(const List< E > &L)
Constructs a doubly linked list that is a copy of L.
Definition: List.h:1470
ogdf::ListIteratorBase< ogdf::Graph::HiddenEdgeSet * >::Elem
typename std::conditional< isConst, const ogdf::Graph::HiddenEdgeSet *, ogdf::Graph::HiddenEdgeSet * >::type Elem
The underlying type, depending on isConst.
Definition: List.h:121
ogdf::BucketFunc::getBucket
virtual int getBucket(const E &x)=0
Returns the bucket of x.
ogdf::List::emplaceBack
iterator emplaceBack(Args &&... args)
Adds a new element at the end of the list.
Definition: List.h:1554
ogdf::ListPure::empty
bool empty() const
Returns true iff the list is empty.
Definition: List.h:286
ogdf::ListPure::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: List.h:612
ogdf::List::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: List.h:1547
ogdf::List::clear
void clear()
Removes all elements from the list.
Definition: List.h:1626
ogdf::List::insertBefore
iterator insertBefore(const E &x, iterator it)
Inserts element x before it.
Definition: List.h:1566
ogdf::List::moveToFront
void moveToFront(iterator it, List< E > &L2)
Moves it to the begin of the list.
Definition: List.h:1639
ogdf::ListIteratorBase< ogdf::Graph::HiddenEdgeSet * >::difference_type
std::ptrdiff_t difference_type
Definition: List.h:127
ogdf::ListPure::reverse_iterator
ListReverseIterator< E > reverse_iterator
Provides a bidirectional reverse iterator that can read or modify any element in a list.
Definition: List.h:252
ogdf::ListPure::insert
iterator insert(const E &x, iterator it, Direction dir=Direction::after)
Inserts element x before or after it.
Definition: List.h:645
ogdf::ListPure::permute
void permute()
Randomly permutes the elements in the list.
Definition: List.h:1403
ogdf::ListPure< TObserver * >::value_type
TObserver * value_type
Represents the data type stored in a list element.
Definition: List.h:240
ogdf::ListElement::m_prev
ListElement< E > * m_prev
Pointer to predecessor element.
Definition: List.h:77