Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

List.h
Go to the documentation of this file.
1 
32 #pragma once
33 
35 #include <ogdf/basic/Reverse.h>
36 #include <random>
37 
38 namespace ogdf {
39 
40 template<class E> class List;
41 template<class E> class ListPure;
42 template<class E, bool isConst, bool isReverse> class ListIteratorBase;
47 
49 template<class E>
50 class ListElement {
51  friend class ListPure<E>;
52  friend class List<E>;
53  friend class ListIteratorBase<E, true, true>;
54  friend class ListIteratorBase<E, false, true>;
55  friend class ListIteratorBase<E, true, false>;
56  friend class ListIteratorBase<E, false, false>;
57 
60  E m_x;
61 #ifdef OGDF_DEBUG
62  ListPure<E> *m_list;
63 #endif
64 
66  ListElement(ListPure<E> *list, const E &x, ListElement<E> *next, ListElement<E> *prev)
67  : m_next(next), m_prev(prev), m_x(x) {
68 #ifdef OGDF_DEBUG
69  m_list = list;
70 #endif
71  }
73  ListElement(ListPure<E> *list, const E &x) : ListElement(list, x, nullptr, nullptr) { }
75  template<class ... Args>
76  ListElement(ListPure<E> *list, ListElement<E> *next, ListElement<E> *prev, Args && ... args)
77  : ListElement(list, E(std::forward<Args>(args)...), next, prev) { }
78 
80 };
81 
83 
92 template<class E, bool isConst, bool isReverse> class ListIteratorBase {
93  friend class ListIteratorBase<E, !isConst, isReverse>;
94  friend class ListIteratorBase<E, isConst, !isReverse>;
95  friend class ListIteratorBase<E, !isConst, !isReverse>;
96  friend class ListPure<E>;
98  using ListElem = typename std::conditional<isConst, const ListElement<E>, ListElement<E>>::type;
101 
104 
106  operator ListElem *() { return m_pX; }
107 
108 public:
111 
114 
118 
120  // gcc9 complains since it cannot match the templated constructor above (-Werror=deprecated-copy).
122 
124  bool valid() const { return m_pX != nullptr; }
125 
126 #ifdef OGDF_DEBUG
127  ListPure<E> *listOf() {
130  OGDF_ASSERT(valid());
131  return m_pX->m_list;
132  }
133 #endif
134  bool operator==(const ListIteratorBase<E, isConst, isReverse> &it) const {
136  return m_pX == it.m_pX;
137  }
138 
141  return m_pX != it.m_pX;
142  }
143 
146  return isReverse ? m_pX->m_prev : m_pX->m_next;
147  }
148 
151  return isReverse ? m_pX->m_next : m_pX->m_prev;
152  }
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 = isReverse ? m_pX->m_prev : m_pX->m_next;
166  return *this;
167  }
168 
172  m_pX = isReverse ? m_pX->m_prev : m_pX->m_next;
173  return it;
174  }
175 
178  m_pX = isReverse ? m_pX->m_next : m_pX->m_prev;
179  return *this;
180  }
181 
185  m_pX = isReverse ? m_pX->m_next : m_pX->m_prev;
186  return it;
187  }
188 
190 };
191 
193 
202 template<class E> class ListPure {
203 protected:
206 
207 public:
209  using value_type = E;
211  using reference = E&;
213  using const_reference = const E&;
222 
224  ListPure() : m_head(nullptr), m_tail(nullptr) { }
225 
227  ListPure(std::initializer_list<E> init) : m_head(nullptr), m_tail(nullptr) {
228  for (const E &x : init)
229  pushBack(x);
230  }
231 
233  ListPure(const ListPure<E> &L) : m_head(nullptr), m_tail(nullptr) {
234  copy(L);
235  }
236 
238 
243  L.m_head = L.m_tail = nullptr;
244  }
245 
247  virtual ~ListPure() { clear(); }
248 
249 
255 
257  bool empty() const { return m_head == nullptr; }
258 
260 
264  virtual int size() const {
265  int count = 0;
266  for (ListElement<E> *pX = m_head; pX; pX = pX->m_next)
267  ++count;
268  return count;
269  }
270 
272 
276  OGDF_ASSERT(m_head != nullptr);
277  return m_head->m_x;
278  }
279 
281 
285  OGDF_ASSERT(m_head != nullptr);
286  return m_head->m_x;
287  }
288 
290 
294  OGDF_ASSERT(m_tail != nullptr);
295  return m_tail->m_x;
296  }
297 
299 
303  OGDF_ASSERT(m_tail != nullptr);
304  return m_tail->m_x;
305  }
306 
308 
311  const_iterator get(int pos) const {
312  ListElement<E> *pX;
313  for(pX = m_head; pX != nullptr; pX = pX->m_next)
314  if (pos-- == 0) break;
315  return pX;
316  }
317 
319 
322  iterator get(int pos) {
323  ListElement<E> *pX;
324  for(pX = m_head; pX != nullptr; pX = pX->m_next)
325  if (pos-- == 0) break;
326  return pX;
327  }
328 
330 
333  int pos(const_iterator it) const {
334  OGDF_ASSERT(it.listOf() == this);
335  int p = 0;
336  for(ListElement<E> *pX = m_head; pX != nullptr; pX = pX->m_next, ++p)
337  if (pX == it) break;
338  return p;
339  }
340 
341 
343 
348 
350 
353  iterator begin() { return m_head; }
354 
356 
359  const_iterator begin() const { return m_head; }
360 
362 
365  const_iterator cbegin() const { return m_head; }
366 
368 
371  iterator end() { return iterator(); }
372 
374 
377  const_iterator end() const { return const_iterator(); }
378 
380 
383  const_iterator cend() const { return const_iterator(); }
384 
386 
390 
392 
396 
398 
402 
404 
408 
410 
414 
416 
420 
422 
426  OGDF_ASSERT(!it.valid() || it.listOf() == this);
427  const ListElement<E> *pX = it;
428  return (pX && pX->m_next) ? pX->m_next : m_head;
429  }
430 
432 
436  OGDF_ASSERT(!it.valid() || it.listOf() == this);
437  ListElement<E> *pX = it;
438  return (pX && pX->m_next) ? pX->m_next : m_head;
439  }
440 
445  OGDF_ASSERT(!it.valid() || it.listOf() == this);
446  const ListElement<E> *pX = it;
447  return (pX && pX->m_prev) ? pX->m_prev : m_tail;
448  }
449 
454  OGDF_ASSERT(!it.valid() || it.listOf() == this);
455  ListElement<E> *pX = it;
456  return (pX && pX->m_prev) ? pX->m_prev : m_tail;
457  }
458 
460 
464  OGDF_ASSERT(!it.valid() || it.listOf() == this);
465  const ListElement<E> *pX = it;
466  return (pX && pX->m_prev) ? pX->m_prev : m_tail;
467  }
468 
470 
474  OGDF_ASSERT(!it.valid() || it.listOf() == this);
475  ListElement<E> *pX = it;
476  return (pX && pX->m_prev) ? pX->m_prev : m_tail;
477  }
478 
483  OGDF_ASSERT(!it.valid() || it.listOf() == this);
484  const ListElement<E> *pX = it;
485  return (pX && pX->m_next) ? pX->m_next : m_head;
486  }
487 
492  OGDF_ASSERT(!it.valid() || it.listOf() == this);
493  ListElement<E> *pX = it;
494  return (pX && pX->m_next) ? pX->m_next : m_head;
495  }
496 
498 
503 
506  clear(); copy(L);
507  return *this;
508  }
509 
511 
515  clear();
516  m_head = L.m_head;
517  m_tail = L.m_tail;
518  L.m_head = L.m_tail = nullptr;
520  return *this;
521  }
522 
524  bool operator==(const ListPure<E> &L) const {
525  ListElement<E> *pX = m_head, *pY = L.m_head;
526  while(pX != nullptr && pY != nullptr) {
527  if(pX->m_x != pY->m_x)
528  return false;
529  pX = pX->m_next;
530  pY = pY->m_next;
531  }
532  return pX == nullptr && pY == nullptr;
533  }
534 
536  bool operator!=(const ListPure<E> &L) const {
537  return !operator==(L);
538  }
539 
541 
546 
548  iterator pushFront(const E &x) {
549  ListElement<E> *pX = new ListElement<E>(this, x, m_head, nullptr);
550  if (m_head)
551  m_head = m_head->m_prev = pX;
552  else
553  m_head = m_tail = pX;
554  return m_head;
555  }
556 
558 
561  template<class ... Args>
562  iterator emplaceFront(Args && ... args) {
563  ListElement<E> *pX = new ListElement<E>(this, m_head, nullptr, std::forward<Args>(args)...);
564  if (m_head)
565  m_head = m_head->m_prev = pX;
566  else
567  m_head = m_tail = pX;
568  return m_head;
569  }
570 
572  iterator pushBack(const E &x) {
573  ListElement<E> *pX = new ListElement<E>(this, x, nullptr, m_tail);
574  if (m_head)
575  m_tail = m_tail->m_next = pX;
576  else
577  m_tail = m_head = pX;
578  return m_tail;
579  }
580 
582 
585  template<class ... Args>
586  iterator emplaceBack(Args && ... args) {
587  ListElement<E> *pX = new ListElement<E>(this, nullptr, m_tail, std::forward<Args>(args)...);
588  if (m_head)
589  m_tail = m_tail->m_next = pX;
590  else
591  m_tail = m_head = pX;
592  return m_tail;
593  }
594 
596 
604  OGDF_ASSERT(it.listOf() == this);
605  ListElement<E> *pY = it, *pX;
606  if (dir == Direction::after) {
607  ListElement<E> *pYnext = pY->m_next;
608  pY->m_next = pX = new ListElement<E>(this, x, pYnext, pY);
609  if (pYnext) pYnext->m_prev = pX;
610  else m_tail = pX;
611  } else {
612  ListElement<E> *pYprev = pY->m_prev;
613  pY->m_prev = pX = new ListElement<E>(this, x, pY, pYprev);
614  if (pYprev) pYprev->m_next = pX;
615  else m_head = pX;
616  }
617  return pX;
618  }
619 
621 
624  iterator insertBefore(const E &x, iterator it) {
625  OGDF_ASSERT(it.listOf() == this);
626  ListElement<E> *pY = it, *pX;
627  ListElement<E> *pYprev = pY->m_prev;
628  pY->m_prev = pX = new ListElement<E>(this, x, pY, pYprev);
629  if (pYprev) pYprev->m_next = pX;
630  else m_head = pX;
631  return pX;
632  }
633 
635 
638  iterator insertAfter(const E &x, iterator it) {
639  OGDF_ASSERT(it.listOf() == this);
640  ListElement<E> *pY = it, *pX;
641  ListElement<E> *pYnext = pY->m_next;
642  pY->m_next = pX = new ListElement<E>(this, x, pYnext, pY);
643  if (pYnext) pYnext->m_prev = pX;
644  else m_tail = pX;
645  return pX;
646  }
647 
649 
654 
656 
659  void popFront() {
660  OGDF_ASSERT(m_head != nullptr);
661  ListElement<E> *pX = m_head;
662  m_head = m_head->m_next;
663  delete pX;
664  if (m_head) m_head->m_prev = nullptr;
665  else m_tail = nullptr;
666  }
667 
669 
673  E el = front();
674  popFront();
675  return el;
676  }
677 
679 
682  void popBack() {
683  OGDF_ASSERT(m_tail != nullptr);
684  ListElement<E> *pX = m_tail;
685  m_tail = m_tail->m_prev;
686  delete pX;
687  if (m_tail) m_tail->m_next = nullptr;
688  else m_head = nullptr;
689  }
690 
692 
696  E el = back();
697  popBack();
698  return el;
699  }
700 
702 
705  void del(iterator it) {
706  OGDF_ASSERT(it.listOf() == this);
707  ListElement<E> *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
708  delete pX;
709  if (pPrev) pPrev->m_next = pNext;
710  else m_head = pNext;
711  if (pNext) pNext->m_prev = pPrev;
712  else m_tail = pPrev;
713  }
714 
716 
722  bool removeFirst(const E &x) {
723  for(ListElement<E> *pX = m_head; pX != nullptr; pX = pX->m_next)
724  if(pX->m_x == x) {
725  del(pX); return true;
726  }
727  return false;
728  }
729 
731  void clear() {
732  if (m_head == nullptr) return;
733 
734  if (!std::is_trivially_destructible<E>::value) {
735  for(ListElement<E> *pX = m_head; pX != nullptr; pX = pX->m_next)
736  pX->m_x.~E();
737  }
738  OGDF_ALLOCATOR::deallocateList(sizeof(ListElement<E>),m_head,m_tail);
739 
740  m_head = m_tail = nullptr;
741  }
742 
744 
749 
751 
754  void exchange(iterator it1, iterator it2) {
755  OGDF_ASSERT(it1.valid());
756  OGDF_ASSERT(it2.valid());
757  OGDF_ASSERT(it1 != it2);
758  ListElement<E> *pX = it1, *pY = it2;
759 
760  std::swap(pX->m_next,pY->m_next);
761  std::swap(pX->m_prev,pY->m_prev);
762 #ifdef OGDF_DEBUG
763  std::swap(pX->m_list,pY->m_list);
764 #endif
765 
766  if(pX->m_next == pX) {
767  pX->m_next = pY; pY->m_prev = pX;
768  }
769  if(pX->m_prev == pX) {
770  pX->m_prev = pY; pY->m_next = pX;
771  }
772 
773  if(pX->m_prev) pX->m_prev->m_next = pX;
774  else m_head = pX;
775 
776  if(pY->m_prev) pY->m_prev->m_next = pY;
777  else m_head = pY;
778 
779  if(pX->m_next) pX->m_next->m_prev = pX;
780  else m_tail = pX;
781 
782  if(pY->m_next) pY->m_next->m_prev = pY;
783  else m_tail = pY;
784  }
785 
787 
791  OGDF_ASSERT(it.listOf() == this);
792  // remove it
793  ListElement<E> *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
794  //already at front
795  if (!pPrev) return;
796 
797  //update old position
798  if (pPrev) pPrev->m_next = pNext;
799  if (pNext) pNext->m_prev = pPrev;
800  else m_tail = pPrev;
801  // insert it at front
802  pX->m_prev = nullptr;
803  pX->m_next = m_head;
804  m_head = m_head->m_prev = pX;
805  }
806 
808 
811  void moveToBack(iterator it) {
812  OGDF_ASSERT(it.listOf() == this);
813  // remove it
814  ListElement<E> *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
815  //already at back
816  if (!pNext) return;
817 
818  //update old position
819  if (pPrev) pPrev->m_next = pNext;
820  else m_head = pNext;
821  if (pNext) pNext->m_prev = pPrev;
822  // insert it at back
823  pX->m_prev = m_tail;
824  pX->m_next = nullptr;
825  m_tail = m_tail->m_next = pX;
826  }
827 
829 
832  void moveToSucc(iterator it, iterator itBefore) {
833  OGDF_ASSERT(it.listOf() == this);
834  OGDF_ASSERT(itBefore.listOf() == this);
835  // move it
836  ListElement<E> *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
837  //the same of already in place
838  ListElement<E> *pY = itBefore;
839  if(pX == pY || pPrev == pY) return;
840 
841  // update old position
842  if (pPrev) pPrev->m_next = pNext;
843  else m_head = pNext;
844  if (pNext) pNext->m_prev = pPrev;
845  else m_tail = pPrev;
846  // move it after itBefore
847  ListElement<E> *pYnext = pX->m_next = pY->m_next;
848  (pX->m_prev = pY)->m_next = pX;
849  if (pYnext) pYnext->m_prev = pX;
850  else m_tail = pX;
851  }
852 
854 
857  void moveToPrec(iterator it, iterator itAfter) {
858  OGDF_ASSERT(it.listOf() == this);
859  OGDF_ASSERT(itAfter.listOf() == this);
860  // move it
861  ListElement<E> *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
862  //the same of already in place
863  ListElement<E> *pY = itAfter;
864  if(pX == pY || pNext == pY) return;
865 
866  // update old position
867  if (pPrev) pPrev->m_next = pNext;
868  else m_head = pNext;
869  if (pNext) pNext->m_prev = pPrev;
870  else m_tail = pPrev;
871  // move it before itAfter
872  ListElement<E> *pYprev = pX->m_prev = pY->m_prev;
873  (pX->m_next = pY)->m_prev = pX;
874  if (pYprev) pYprev->m_next = pX;
875  else m_head = pX;
876  }
877 
879 
883  OGDF_ASSERT(it.listOf() == this);
884  OGDF_ASSERT(this != &L2);
885  // remove it
886  ListElement<E> *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
887  if (pPrev) pPrev->m_next = pNext;
888  else m_head = pNext;
889  if (pNext) pNext->m_prev = pPrev;
890  else m_tail = pPrev;
891  // insert it at front of L2
892  pX->m_prev = nullptr;
893  if ((pX->m_next = L2.m_head) != nullptr)
894  L2.m_head = L2.m_head->m_prev = pX;
895  else
896  L2.m_head = L2.m_tail = pX;
897 
898 #ifdef OGDF_DEBUG
899  pX->m_list = &L2;
900 #endif
901  }
902 
904 
908  OGDF_ASSERT(it.listOf() == this);
909  OGDF_ASSERT(this != &L2);
910  // remove it
911  ListElement<E> *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
912  if (pPrev) pPrev->m_next = pNext;
913  else m_head = pNext;
914  if (pNext) pNext->m_prev = pPrev;
915  else m_tail = pPrev;
916  // insert it at back of L2
917  pX->m_next = nullptr;
918  if ((pX->m_prev = L2.m_tail) != nullptr)
919  L2.m_tail = L2.m_tail->m_next = pX;
920  else
921  L2.m_head = L2.m_tail = pX;
922 
923 #ifdef OGDF_DEBUG
924  pX->m_list = this;
925 #endif
926  }
927 
929 
933  void moveToSucc(iterator it, ListPure<E> &L2, iterator itBefore) {
934  OGDF_ASSERT(it.listOf() == this);
935  OGDF_ASSERT(itBefore.listOf() == &L2);
936  OGDF_ASSERT(this != &L2);
937  // remove it
938  ListElement<E> *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
939  if (pPrev) pPrev->m_next = pNext;
940  else m_head = pNext;
941  if (pNext) pNext->m_prev = pPrev;
942  else m_tail = pPrev;
943  // insert it in list L2 after itBefore
944  ListElement<E> *pY = itBefore;
945  ListElement<E> *pYnext = pX->m_next = pY->m_next;
946  (pX->m_prev = pY)->m_next = pX;
947  if (pYnext) pYnext->m_prev = pX;
948  else L2.m_tail = pX;
949 
950 #ifdef OGDF_DEBUG
951  pX->m_list = &L2;
952 #endif
953  }
954 
956 
960  void moveToPrec(iterator it, ListPure<E> &L2, iterator itAfter) {
961  OGDF_ASSERT(it.listOf() == this);
962  OGDF_ASSERT(itAfter.listOf() == &L2);
963  OGDF_ASSERT(this != &L2);
964  // remove it
965  ListElement<E> *pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
966  if (pPrev) pPrev->m_next = pNext;
967  else m_head = pNext;
968  if (pNext) pNext->m_prev = pPrev;
969  else m_tail = pPrev;
970  // insert it in list L2 after itBefore
971  ListElement<E> *pY = itAfter;
972  ListElement<E> *pYprev = pX->m_prev = pY->m_prev;
973  (pX->m_next = pY)->m_prev = pX;
974  if (pYprev) pYprev->m_next = pX;
975  else L2.m_head = pX;
976 
977 #ifdef OGDF_DEBUG
978  pX->m_list = &L2;
979 #endif
980  }
981 
983  void conc(ListPure<E> &L2) {
984  OGDF_ASSERT(this != &L2);
985  if (m_head)
986  m_tail->m_next = L2.m_head;
987  else
988  m_head = L2.m_head;
989  if (L2.m_head) {
990  L2.m_head->m_prev = m_tail;
991  m_tail = L2.m_tail;
992  }
993 
994  reassignListRefs(L2.m_head);
995 
996  L2.m_head = L2.m_tail = nullptr;
997  }
998 
1001  OGDF_ASSERT(this != &L2);
1002  if (m_head)
1003  m_head->m_prev = L2.m_tail;
1004  else
1005  m_tail = L2.m_tail;
1006  if (L2.m_head) {
1007  L2.m_tail->m_next = m_head;
1008  m_head = L2.m_head;
1009  }
1010 
1011  reassignListRefs(L2.m_head);
1012 
1013  L2.m_head = L2.m_tail = nullptr;
1014  }
1015 
1017  void swap(ListPure<E> &other) {
1018  std::swap(m_head, other.m_head);
1019  std::swap(m_tail, other.m_tail);
1020 
1021  reassignListRefs();
1022  other.reassignListRefs();
1023  }
1024 
1026 
1036  OGDF_ASSERT(!it.valid() || it.listOf() == this);
1037  if (&L1 != this) L1.clear();
1038  if (&L2 != this) L2.clear();
1039 
1040  if (it.valid()){
1041  L1.m_head = m_head;
1042  L2.m_tail = m_tail;
1043  if (dir == Direction::before){
1044  L2.m_head = it;
1045  L1.m_tail = L2.m_head->m_prev;
1046  }
1047  else {
1048  L1.m_tail = it;
1049  L2.m_head = L1.m_tail->m_next;
1050  }
1051  L2.m_head->m_prev = L1.m_tail->m_next = nullptr;
1052 
1053  } else {
1054  L1.m_head = L1.m_tail = nullptr;
1055  L2.m_head = m_head;
1056  L2.m_tail = m_tail;
1057  }
1058 
1059  if (this != &L1 && this != &L2) {
1060  m_head = m_tail = nullptr;
1061  }
1062 
1063  L1.reassignListRefs();
1064  L2.reassignListRefs();
1065  }
1066 
1069  OGDF_ASSERT(it.listOf() == this);
1070  OGDF_ASSERT(this != &L2);
1071  L2.clear();
1072  ListElement<E> *pX = it;
1073  if (pX != m_tail) {
1074  (L2.m_head = pX->m_next)->m_prev = nullptr;
1075  pX->m_next = nullptr;
1076  L2.m_tail = m_tail;
1077  m_tail = pX;
1078  }
1079 
1080  L2.reassignListRefs();
1081  }
1082 
1085  OGDF_ASSERT(it.listOf() == this);
1086  OGDF_ASSERT(this != &L2);
1087  L2.clear();
1088  ListElement<E> *pX = it;
1089  L2.m_head = pX; L2.m_tail = m_tail;
1090  if ((m_tail = pX->m_prev) == nullptr)
1091  m_head = nullptr;
1092  else
1093  m_tail->m_next = nullptr;
1094  pX->m_prev = nullptr;
1095 
1096  L2.reassignListRefs();
1097  }
1098 
1100  void reverse() {
1101  ListElement<E> *pX = m_head;
1102  m_head = m_tail;
1103  m_tail = pX;
1104  while(pX) {
1105  ListElement<E> *pY = pX->m_next;
1106  pX->m_next = pX->m_prev;
1107  pX = pX->m_prev = pY;
1108  }
1109  }
1110 
1112 
1117 
1119  ListConstIterator<E> search(const E& e) const {
1121  for (i = begin(); i.valid(); ++i)
1122  if (*i == e) return i;
1123  return i;
1124  }
1125 
1127  ListIterator<E> search(const E& e) {
1128  ListIterator<E> i;
1129  for (i = begin(); i.valid(); ++i)
1130  if (*i == e) return i;
1131  return i;
1132  }
1133 
1135  template<class COMPARER>
1136  ListConstIterator<E> search(const E &e, const COMPARER &comp) const {
1138  for (i = begin(); i.valid(); ++i)
1139  if (comp.equal(*i, e)) return i;
1140  return i;
1141  }
1142 
1144  template<class COMPARER>
1145  ListIterator<E> search(const E &e, const COMPARER &comp) {
1146  ListIterator<E> i;
1147  for (i = begin(); i.valid(); ++i)
1148  if (comp.equal(*i, e)) return i;
1149  return i;
1150  }
1151 
1153  void quicksort() {
1154  ogdf::quicksortTemplate(*this);
1155  }
1156 
1158  template<class COMPARER>
1159  void quicksort(const COMPARER &comp) {
1160  ogdf::quicksortTemplate(*this,comp);
1161  }
1162 
1164 
1171  void bucketSort(int l, int h, BucketFunc<E> &f);
1172 
1174 
1179 
1189  std::function<bool(const E&)> includeElement = [](const E&) { return true; },
1190  bool isFastTest = true) const {
1191  return chooseIteratorFrom(*this, includeElement, isFastTest);
1192  }
1193 
1196  std::function<bool(const E&)> includeElement = [](const E&) { return true; },
1197  bool isFastTest = true) {
1198  return chooseIteratorFrom(*this, includeElement, isFastTest);
1199  }
1200 
1210  std::function<bool(const E&)> includeElement = [](const E&) { return true; },
1211  bool isFastTest = true) const {
1212  const_iterator result = chooseIterator(includeElement, isFastTest);
1213  OGDF_ASSERT(result.valid());
1214  return *result;
1215  }
1216 
1219  std::function<bool(const E&)> includeElement = [](const E&) { return true; },
1220  bool isFastTest = true) {
1221  iterator result = chooseIterator(includeElement, isFastTest);
1222  OGDF_ASSERT(result.valid());
1223  return *result;
1224  }
1225 
1227  void permute() {
1228  std::minstd_rand rng(randomSeed());
1229  permute(size(), rng);
1230  }
1231 
1233  template<class RNG>
1234  void permute(RNG &rng) {
1235  permute(size(), rng);
1236  }
1237 
1239 
1240 protected:
1241  void copy(const ListPure<E> &L) {
1242  for(ListElement<E> *pX = L.m_head; pX != nullptr; pX = pX->m_next)
1243  pushBack(pX->m_x);
1244  }
1245 
1246  template<class RNG>
1247 
1249  void permute(const int n, RNG &rng);
1250 
1252  inline void reassignListRefs(ListElement<E> *start = nullptr) {
1253 #ifdef OGDF_DEBUG
1254  for(auto e = start == nullptr ? m_head : start; e != nullptr; e = e->m_next) {
1255  e->m_list = this;
1256  }
1257 #endif
1258  }
1259 
1261 };
1262 
1264 
1273 template<class E>
1274 class List : private ListPure<E> {
1275  int m_count;
1276 
1277 public:
1278  using typename ListPure<E>::value_type;
1279  using typename ListPure<E>::reference;
1280  using typename ListPure<E>::const_reference;
1281  using typename ListPure<E>::const_iterator;
1282  using typename ListPure<E>::iterator;
1283  using typename ListPure<E>::const_reverse_iterator;
1284  using typename ListPure<E>::reverse_iterator;
1285 
1287  List() : m_count(0) { }
1288 
1290  List(std::initializer_list<E> init) : ListPure<E>(init), m_count((int)init.size()) { }
1291 
1293  List(const List<E> &L) : ListPure<E>(L), m_count(L.m_count) { }
1294 
1296 
1299  List(List<E> &&L) : ListPure<E>(std::move(L)), m_count(L.m_count) {
1300  L.m_count = 0;
1301  }
1302 
1308 
1310 
1313  int size() const { return m_count; }
1314 
1316  const ListPure<E> &getListPure() const { return *this; }
1317 
1319 
1324 
1328  m_count = L.m_count;
1329  return *this;
1330  }
1331 
1333 
1337  m_count = L.m_count;
1339  L.m_count = 0;
1340  return *this;
1341  }
1342 
1344  bool operator==(const List<E> &L) const {
1345  return (m_count == L.m_count) && ListPure<E>::operator==(L);
1346  }
1347 
1349  bool operator!=(const List<E> &L) const {
1350  return !operator==(L);
1351  }
1352 
1354 
1359 
1361  iterator pushFront(const E &x) {
1362  ++m_count;
1363  return ListPure<E>::pushFront(x);
1364  }
1365 
1367  template<class ... Args>
1368  iterator emplaceFront(Args && ... args) {
1369  ++m_count;
1370  return ListPure<E>::emplaceFront(std::forward<Args>(args)...);
1371  }
1372 
1374  iterator pushBack(const E &x) {
1375  ++m_count;
1376  return ListPure<E>::pushBack(x);
1377  }
1378 
1380  template<class ... Args>
1381  iterator emplaceBack(Args && ... args) {
1382  ++m_count;
1383  return ListPure<E>::emplaceBack(std::forward<Args>(args)...);
1384  }
1385 
1387  iterator insert(const E &x, iterator it, Direction dir = Direction::after) {
1388  ++m_count;
1389  return ListPure<E>::insert(x,it,dir);
1390  }
1391 
1393  iterator insertBefore(const E &x, iterator it) {
1394  ++m_count;
1395  return ListPure<E>::insertBefore(x,it);
1396  }
1397 
1399  iterator insertAfter(const E &x, iterator it) {
1400  ++m_count;
1401  return ListPure<E>::insertAfter(x,it);
1402  }
1403 
1405 
1410 
1412  void popFront() {
1413  --m_count;
1415  }
1416 
1419  E el = front();
1420  popFront();
1421  return el;
1422  }
1423 
1425  void popBack() {
1426  --m_count;
1428  }
1429 
1432  E el = back();
1433  popBack();
1434  return el;
1435  }
1436 
1438  void del(iterator it) {
1439  --m_count;
1440  ListPure<E>::del(it);
1441  }
1442 
1444  bool removeFirst(const E &x) {
1445  bool hasRemoved = ListPure<E>::removeFirst(x);
1446  if(hasRemoved)
1447  --m_count;
1448  return hasRemoved;
1449  }
1450 
1452  void clear() {
1453  m_count = 0;
1455  }
1456 
1458 
1463 
1465  void moveToFront(iterator it, List<E> &L2) {
1466  ListPure<E>::moveToFront(it,L2);
1467  --m_count; ++L2.m_count;
1468  }
1469 
1471  void moveToBack(iterator it, List<E> &L2) {
1472  ListPure<E>::moveToBack(it,L2);
1473  --m_count; ++L2.m_count;
1474  }
1475 
1477  void moveToSucc(iterator it, List<E> &L2, iterator itBefore) {
1478  ListPure<E>::moveToSucc(it,L2,itBefore);
1479  --m_count; ++L2.m_count;
1480  }
1481 
1483  void moveToPrec(iterator it, List<E> &L2, iterator itAfter) {
1484  ListPure<E>::moveToPrec(it,L2,itAfter);
1485  --m_count; ++L2.m_count;
1486  }
1487 
1489  void conc(List<E> &L2) {
1490  ListPure<E>::conc(L2);
1491  m_count += L2.m_count;
1492  L2.m_count = 0;
1493  }
1494 
1496  void concFront(List<E> &L2) {
1498  m_count += L2.m_count;
1499  L2.m_count = 0;
1500  }
1501 
1503  void swap(List<E> &other) {
1504  ListPure<E>::swap(other);
1505  std::swap(m_count, other.m_count);
1506  }
1507 
1509  void split(iterator it, List<E> &L1, List<E> &L2, Direction dir = Direction::before) {
1510  ListPure<E>::split(it,L1,L2,dir);
1511  int countL = m_count, countL1 = 0;
1512  for(ListElement<E> *pX = L1.m_head; pX != nullptr; pX = pX->m_next)
1513  ++countL1;
1514 
1515  L1.m_count = countL1;
1516  L2.m_count = countL - countL1;
1517  if (this->m_head == nullptr) m_count = 0;
1518  }
1519 
1520  using ListPure<E>::empty;
1521  using ListPure<E>::front;
1522  using ListPure<E>::back;
1523  using ListPure<E>::get;
1524  using ListPure<E>::pos;
1525  using ListPure<E>::begin;
1526  using ListPure<E>::cbegin;
1527  using ListPure<E>::end;
1528  using ListPure<E>::cend;
1529  using ListPure<E>::rbegin;
1530  using ListPure<E>::crbegin;
1531  using ListPure<E>::rend;
1532  using ListPure<E>::crend;
1535  using ListPure<E>::exchange;
1540  using ListPure<E>::reverse;
1541  using ListPure<E>::search;
1542  using ListPure<E>::quicksort;
1546  using ListPure<E>::permute;
1547 
1549 };
1550 
1551 template<class E>
1553 {
1554  if (m_head == m_tail) return;
1555 
1556  Array<ListElement<E> *> head(l,h,nullptr), tail(l,h);
1557 
1558  ListElement<E> *pX;
1559  for (pX = m_head; pX; pX = pX->m_next) {
1560  int i = f.getBucket(pX->m_x);
1561  if (head[i])
1562  tail[i] = ((pX->m_prev = tail[i])->m_next = pX);
1563  else
1564  head[i] = tail[i] = pX;
1565  }
1566 
1567  ListElement<E> *pY = nullptr;
1568  for (int i = l; i <= h; i++) {
1569  pX = head[i];
1570  if (pX) {
1571  if (pY) {
1572  (pY->m_next = pX)->m_prev = pY;
1573  } else
1574  (m_head = pX)->m_prev = nullptr;
1575  pY = tail[i];
1576  }
1577  }
1578 
1579  m_tail = pY;
1580  pY->m_next = nullptr;
1581 }
1582 
1583 template<class E>
1584 template<class RNG>
1585 void ListPure<E>::permute(const int n, RNG &rng)
1586 {
1587  //if n==0 do nothing
1588  if (n == 0) { return; }
1589 
1590  Array<ListElement<E> *> A(n+2);
1591  A[0] = A[n+1] = nullptr;
1592 
1593  int i = 1;
1594  ListElement<E> *pX;
1595  for (pX = m_head; pX; pX = pX->m_next)
1596  A[i++] = pX;
1597 
1598  A.permute(1,n,rng);
1599 
1600  for (i = 1; i <= n; i++) {
1601  pX = A[i];
1602  pX->m_next = A[i+1];
1603  pX->m_prev = A[i-1];
1604  }
1605 
1606  m_head = A[1];
1607  m_tail = A[n];
1608 }
1609 
1611 template<class E>
1612 void print(std::ostream &os, const ListPure<E> &L, char delim = ' ')
1613 {
1614  typename ListPure<E>::const_iterator pX = L.begin();
1615  if (pX.valid()) {
1616  os << *pX;
1617  for(++pX; pX.valid(); ++pX)
1618  os << delim << *pX;
1619  }
1620 }
1621 
1623 template<class E>
1624 void print(std::ostream &os, const List<E> &L, char delim = ' ')
1625 {
1626  print(os, L.getListPure(), delim);
1627 }
1628 
1630 template<class E>
1631 std::ostream &operator<<(std::ostream &os, const ListPure<E> &L)
1632 {
1633  print(os,L);
1634  return os;
1635 }
1636 
1638 template<class E>
1639 std::ostream &operator<<(std::ostream &os, const List<E> &L)
1640 {
1641  return os << L.getListPure();
1642 }
1643 
1644 template<class E, class Master>
1645 class ListContainer : public List<E> {
1646  friend Master;
1647 
1648 public:
1653 
1655  iterator begin() const { return List<E>::cbegin(); }
1656 
1658  iterator end() const { return List<E>::cend(); }
1659 
1662 
1664  reverse_iterator rend() const { return List<E>::crend(); }
1665 
1667  int size() const { return List<E>::size(); }
1668 };
1669 
1670 }
ogdf::ListPure::begin
const_iterator begin() const
Returns a const iterator to the first element of the list.
Definition: List.h:359
ogdf::ListElement::ListElement
ListElement(ListPure< E > *list, const E &x, ListElement< E > *next, ListElement< E > *prev)
Constructs a ListElement.
Definition: List.h:66
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:1252
ogdf::ListPure::reference
E & reference
Provides a reference to an element stored in a list.
Definition: List.h:211
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::ListIteratorBase::pred
ListIteratorBase< E, isConst, isReverse > pred() const
Returns predecessor iterator.
Definition: List.h:150
ogdf::ListPure::permute
void permute(RNG &rng)
Randomly permutes the elements in the list using random number generator rng.
Definition: List.h:1234
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:1035
ogdf::ListElement::m_x
E m_x
Stores the content.
Definition: List.h:60
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:960
ogdf::Direction
Direction
Definition: basic.h:134
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:1188
ogdf::List::moveToBack
void moveToBack(iterator it, List< E > &L2)
Moves it to the end of the list.
Definition: List.h:1471
ogdf::ListPure::m_head
ListElement< E > * m_head
Pointer to first element.
Definition: List.h:204
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:219
ogdf::ListPure::copy
void copy(const ListPure< E > &L)
Definition: List.h:1241
ogdf::ListPure::clear
void clear()
Removes all elements from the list.
Definition: List.h:731
ogdf::ListIteratorBase::ListIteratorBase
ListIteratorBase(const ListIteratorBase< E, isArgConst, isArgReverse > &it)
Constructs an iterator that is a copy of it.
Definition: List.h:117
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::List::conc
void conc(List< E > &L2)
Appends L2 to this list and makes L2 empty.
Definition: List.h:1489
ogdf::List::swap
void swap(List< E > &other)
Exchanges the contents of this list and other in constant time.
Definition: List.h:1503
ogdf::ListPure::splitAfter
void splitAfter(iterator it, ListPure< E > &L2)
Splits the list after it.
Definition: List.h:1068
ogdf::ListIteratorBase::operator++
ListIteratorBase< E, isConst, isReverse > & operator++()
Increment operator (prefix).
Definition: List.h:164
ogdf::ListPure::bucketSort
void bucketSort(int l, int h, BucketFunc< E > &f)
Sorts the list using bucket sort.
Definition: List.h:1552
ogdf::ListElement::ListElement
ListElement(ListPure< E > *list, const E &x)
Constructs a ListElement.
Definition: List.h:73
ogdf::List::popFront
void popFront()
Removes the first element from the list.
Definition: List.h:1412
ogdf::ListContainer::Master
friend Master
Definition: List.h:1646
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:933
ogdf::ListPure::cyclicSucc
iterator cyclicSucc(iterator it)
Returns an iterator to the cyclic successor of it.
Definition: List.h:435
ogdf::ListPure::back
reference back()
Returns a reference to the last element.
Definition: List.h:302
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:1509
ogdf::ListPure::size
virtual int size() const
Returns the number of elements in the list.
Definition: List.h:264
ogdf::List::List
List(std::initializer_list< E > init)
Constructs a doubly linked list containing the elements in init.
Definition: List.h:1290
ogdf::ListPure::emplaceFront
iterator emplaceFront(Args &&... args)
Adds a new element at the beginning of the list.
Definition: List.h:562
ogdf::ListPure::back
const_reference back() const
Returns a const reference to the last element.
Definition: List.h:293
ogdf::List::popFrontRet
E popFrontRet()
Removes the first element from the list and returns it.
Definition: List.h:1418
ogdf::whaType::A
@ A
ogdf::ListIteratorBase::operator!=
bool operator!=(const ListIteratorBase< E, isConst, isReverse > &it) const
Inequality operator.
Definition: List.h:140
ogdf::ListPure::operator==
bool operator==(const ListPure< E > &L) const
Equality operator.
Definition: List.h:524
ogdf::ListPure::insertAfter
iterator insertAfter(const E &x, iterator it)
Inserts element x after it.
Definition: List.h:638
ogdf::ListPure::begin
iterator begin()
Returns an iterator to the first element of the list.
Definition: List.h:353
ogdf::ListPure::popBackRet
E popBackRet()
Removes the last element from the list and returns it.
Definition: List.h:695
ogdf::ListIteratorBase::valid
bool valid() const
Returns true iff the iterator points to an element.
Definition: List.h:124
ogdf::List::operator==
bool operator==(const List< E > &L) const
Equality operator.
Definition: List.h:1344
ogdf::ListPure::crbegin
const_reverse_iterator crbegin() const
Returns a const iterator to the last element of the list.
Definition: List.h:401
ogdf::ListPure::popFront
void popFront()
Removes the first element from the list.
Definition: List.h:659
ogdf::BucketFunc
Abstract base class for bucket functions.
Definition: basic.h:241
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:217
ogdf::ListPure::cyclicSucc
const_iterator cyclicSucc(const_iterator it) const
Returns a const iterator to the cyclic successor of it.
Definition: List.h:425
ogdf::List::operator=
List< E > & operator=(const List< E > &L)
Assignment operator.
Definition: List.h:1326
ogdf::ListPure::exchange
void exchange(iterator it1, iterator it2)
Exchanges the positions of it1 and it2 in the list.
Definition: List.h:754
ogdf::ListPure::get
const_iterator get(int pos) const
Returns a const iterator pointing to the element at position pos.
Definition: List.h:311
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
ogdf::List::insertAfter
iterator insertAfter(const E &x, iterator it)
Inserts element x after it.
Definition: List.h:1399
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:1652
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:1127
ogdf::ListContainer::rbegin
reverse_iterator rbegin() const
Returns a reverse iterator to the last element in the container.
Definition: List.h:1661
ogdf::ListElement::m_next
ListElement< E > * m_next
Pointer to successor element.
Definition: List.h:58
ogdf::ListPure::conc
void conc(ListPure< E > &L2)
Appends L2 to this list and makes L2 empty.
Definition: List.h:983
ogdf::ListPure::ListPure
ListPure(std::initializer_list< E > init)
Constructs a doubly linked list containing the elements in init.
Definition: List.h:227
ogdf::List::concFront
void concFront(List< E > &L2)
Prepends L2 to this list and makes L2 empty.
Definition: List.h:1496
ogdf::ListPure::end
iterator end()
Returns an iterator to one-past-last element of the list.
Definition: List.h:371
ogdf::ListPure::operator=
ListPure< E > & operator=(const ListPure< E > &L)
Assignment operator.
Definition: List.h:505
ogdf::List::m_count
int m_count
The length of the list.
Definition: List.h:1275
ogdf::ListContainer::size
int size() const
Returns the number of elements in the container.
Definition: List.h:1667
ogdf::ListPure::moveToBack
void moveToBack(iterator it)
Moves it to the end of the list.
Definition: List.h:811
ogdf::List::insert
iterator insert(const E &x, iterator it, Direction dir=Direction::after)
Inserts element x before or after it.
Definition: List.h:1387
ogdf::ListPure::moveToSucc
void moveToSucc(iterator it, iterator itBefore)
Moves it after itBefore.
Definition: List.h:832
ogdf::ListIteratorBase::ListIteratorBase
ListIteratorBase(ListElem *pX)
Constructs an iterator that points to pX.
Definition: List.h:110
ogdf::ListPure::end
const_iterator end() const
Returns a const iterator to one-past-last element of the list.
Definition: List.h:377
ogdf::ListIteratorBase::succ
ListIteratorBase< E, isConst, isReverse > succ() const
Returns successor iterator.
Definition: List.h:145
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:76
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:1650
ogdf::ListIteratorBase::m_pX
ListElem * m_pX
pointer to list element
Definition: List.h:103
ogdf::ListPure::ListPure
ListPure(const ListPure< E > &L)
Constructs a doubly linked list that is a copy of L.
Definition: List.h:233
ogdf::List::operator=
List< E > & operator=(List< E > &&L)
Assignment operator (move semantics).
Definition: List.h:1336
ogdf::ListIteratorBase::operator--
ListIteratorBase< E, isConst, isReverse > operator--(int)
Decrement operator (postfix).
Definition: List.h:183
ogdf::ListPure::popFrontRet
E popFrontRet()
Removes the first element from the list and returns it.
Definition: List.h:672
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:463
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:1000
ogdf::ListIteratorBase::operator*
Elem & operator*() const
Returns a reference to the element content.
Definition: List.h:155
ogdf::ListPure::cyclicPred
iterator cyclicPred(iterator it)
Returns an iterator to the cyclic predecessor of it.
Definition: List.h:473
ogdf::List::pushFront
iterator pushFront(const E &x)
Adds element x at the beginning of the list.
Definition: List.h:1361
ogdf::ListPure::moveToFront
void moveToFront(iterator it)
Moves it to the begin of the list.
Definition: List.h:790
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:1136
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:1195
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:204
ogdf::ListPure::swap
void swap(ListPure< E > &other)
Exchanges the contents of this list and other in constant time.
Definition: List.h:1017
ogdf::ListPure::~ListPure
virtual ~ListPure()
Destructor.
Definition: List.h:247
ogdf::ListContainer::begin
iterator begin() const
Returns an iterator to the first element in the container.
Definition: List.h:1655
ogdf::List::moveToSucc
void moveToSucc(iterator it, List< E > &L2, iterator itBefore)
Moves it after itBefore.
Definition: List.h:1477
ogdf::List::moveToPrec
void moveToPrec(iterator it, List< E > &L2, iterator itAfter)
Moves it before itAfter.
Definition: List.h:1483
ogdf::ListIteratorBase::operator++
ListIteratorBase< E, isConst, isReverse > operator++(int)
Increment operator (postfix).
Definition: List.h:170
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:1209
ogdf::ListPure::emplaceBack
iterator emplaceBack(Args &&... args)
Adds a new element at the end of the list.
Definition: List.h:586
ogdf::ListPure::moveToBack
void moveToBack(iterator it, ListPure< E > &L2)
Moves it to the end of L2.
Definition: List.h:907
ogdf::operator<<
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition: Array.h:949
ogdf::ListPure::rbegin
reverse_iterator rbegin()
Returns an iterator to the last element of the list.
Definition: List.h:389
ogdf::ListPure::cbegin
const_iterator cbegin() const
Returns a const iterator to the first element of the list.
Definition: List.h:365
ogdf::ListPure::rend
reverse_iterator rend()
Returns an iterator to one-before-first element of the list.
Definition: List.h:407
ogdf::ListIteratorBase::operator--
ListIteratorBase< E, isConst, isReverse > & operator--()
Decrement operator (prefix).
Definition: List.h:177
ogdf::GraphObserver
Abstract Base class for graph observers.
Definition: GraphObserver.h:57
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: List.h:40
ogdf::ListPure::reverse
void reverse()
Reverses the order of the list elements.
Definition: List.h:1100
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:1145
ogdf::ListPure::popBack
void popBack()
Removes the last element from the list.
Definition: List.h:682
ogdf::ListPure::cend
const_iterator cend() const
Returns a const iterator to one-past-last element of the list.
Definition: List.h:383
ogdf::ListPure::const_iterator
ListConstIterator< E > const_iterator
Provides a bidirectional iterator that can read a const element in a list.
Definition: List.h:215
ogdf::List::popBackRet
E popBackRet()
Removes the last element from the list and returns it.
Definition: List.h:1431
ogdf::ListPure::insertBefore
iterator insertBefore(const E &x, iterator it)
Inserts element x before it.
Definition: List.h:624
ogdf::ListPure::cyclicPred
reverse_iterator cyclicPred(reverse_iterator it)
Definition: List.h:491
ogdf::ListPure::operator!=
bool operator!=(const ListPure< E > &L) const
Inequality operator.
Definition: List.h:536
ogdf::ListPure::removeFirst
bool removeFirst(const E &x)
Removes the first occurrence of x (if any) from the list.
Definition: List.h:722
ogdf::ListPure::moveToPrec
void moveToPrec(iterator it, iterator itAfter)
Moves it before itAfter.
Definition: List.h:857
ogdf::ListPure::rend
const_reverse_iterator rend() const
Returns a const iterator to one-before-first element of the list.
Definition: List.h:413
ogdf::List::List
List()
Constructs an empty doubly linked list.
Definition: List.h:1287
ogdf::ListPure::operator=
ListPure< E > & operator=(ListPure< E > &&L)
Assignment operator (move semantics).
Definition: List.h:514
ogdf::ListPure::rbegin
const_reverse_iterator rbegin() const
Returns a const iterator to the last element of the list.
Definition: List.h:395
ogdf::ListContainer
Definition: List.h:1645
ogdf::ListPure
Doubly linked lists.
Definition: List.h:41
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:50
Reverse.h
Implementation of the Reverse class for the reverse iteration of containers.
ogdf::ListPure::cyclicSucc
const_reverse_iterator cyclicSucc(const_reverse_iterator it) const
Definition: List.h:444
ogdf::ListPure::ListPure
ListPure()
Constructs an empty doubly linked list.
Definition: List.h:224
ogdf::ListIteratorBase::operator==
bool operator==(const ListIteratorBase< E, isConst, isReverse > &it) const
Equality operator.
Definition: List.h:135
ogdf::ListPure::quicksort
void quicksort()
Sorts the list using Quicksort.
Definition: List.h:1153
ogdf::ListPure::pos
int pos(const_iterator it) const
Returns the position (starting with 0) of iterator it in the list.
Definition: List.h:333
ogdf::graphics::init
void init()
Definition: graphics.h:472
ogdf::ListIteratorBase::operator=
ListIteratorBase< E, isConst, isReverse > & operator=(const ListIteratorBase< E, isConst, isReverse > &it)
Assignment operator.
Definition: List.h:158
ogdf::ListPure::ListPure
ListPure(ListPure< E > &&L)
Constructs a doubly linked list containing the elements of L (move semantics).
Definition: List.h:241
ogdf::List::getListPure
const ListPure< E > & getListPure() const
Conversion to const ListPure.
Definition: List.h:1316
ogdf::List::del
void del(iterator it)
Removes it from the list.
Definition: List.h:1438
ogdf::ListPure::cyclicPred
const_reverse_iterator cyclicPred(const_reverse_iterator it) const
Definition: List.h:482
std
Definition: GML.h:110
ogdf::List::popBack
void popBack()
Removes the last element from the list.
Definition: List.h:1425
ogdf::ListIteratorBase::ListElem
typename std::conditional< isConst, const ListElement< E >, ListElement< E > >::type ListElem
The underlying list element, depending on isConst.
Definition: List.h:98
ogdf::ListContainer::end
iterator end() const
Returns an iterator to the one-past-last element in the container.
Definition: List.h:1658
ogdf::ListContainer::rend
reverse_iterator rend() const
Returns a reverse iterator to the one-before-first element in the container.
Definition: List.h:1664
ogdf::ListPure::crend
const_reverse_iterator crend() const
Returns a const iterator to one-before-first element of the list.
Definition: List.h:419
ogdf::ListIteratorBase::ListIteratorBase
ListIteratorBase()
Constructs an invalid iterator.
Definition: List.h:113
ogdf::ListPure::moveToFront
void moveToFront(iterator it, ListPure< E > &L2)
Moves it to the begin of L2.
Definition: List.h:882
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:938
ogdf::ListPure::front
reference front()
Returns a reference to the first element.
Definition: List.h:284
ogdf::ListPure::front
const_reference front() const
Returns a const reference to the first element.
Definition: List.h:275
ogdf::ListPure::quicksort
void quicksort(const COMPARER &comp)
Sorts the list using Quicksort and comparer comp.
Definition: List.h:1159
ogdf::List::size
int size() const
Returns the number of elements in the list.
Definition: List.h:1313
ogdf::ListPure::get
iterator get(int pos)
Returns an iterator pointing to the element at position pos.
Definition: List.h:322
ogdf::ListIteratorBase
Encapsulates a pointer to a list element.
Definition: List.h:42
ogdf::List::List
List(List< E > &&L)
Constructs a doubly linked list containing the elements of L (move semantics).
Definition: List.h:1299
ogdf::ListPure::cyclicSucc
reverse_iterator cyclicSucc(reverse_iterator it)
Definition: List.h:453
ogdf::List::emplaceFront
iterator emplaceFront(Args &&... args)
Adds a new element at the beginning of the list.
Definition: List.h:1368
ogdf::ListPure::m_tail
ListElement< E > * m_tail
Pointer to last element.
Definition: List.h:205
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:1218
ogdf::quicksortTemplate
void quicksortTemplate(LIST &L)
Definition: list_templates.h:74
ogdf::ListIteratorBase::ListIteratorBase
ListIteratorBase(const ListIteratorBase< E, isConst, isReverse > &it)
Copy constructor.
Definition: List.h:121
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:1119
ogdf::ListPure::splitBefore
void splitBefore(iterator it, ListPure< E > &L2)
Splits the list before it.
Definition: List.h:1084
ogdf::ListPure::pushFront
iterator pushFront(const E &x)
Adds element x at the beginning of the list.
Definition: List.h:548
ogdf::ListPure::del
void del(iterator it)
Removes it from the list.
Definition: List.h:705
ogdf::List::removeFirst
bool removeFirst(const E &x)
Removes the first occurrence of x (if any) from the list.
Definition: List.h:1444
ogdf::List::operator!=
bool operator!=(const List< E > &L) const
Inequality operator.
Definition: List.h:1349
ogdf::ListPure::const_reference
const E & const_reference
Provides a reference to a const element stored in a list for reading and performing const operations.
Definition: List.h:213
ogdf::List::List
List(const List< E > &L)
Constructs a doubly linked list that is a copy of L.
Definition: List.h:1293
ogdf::ListIteratorBase< ogdf::EdgeElement >::Elem
typename std::conditional< isConst, const ogdf::EdgeElement, ogdf::EdgeElement >::type Elem
The underlying type, depending on isConst.
Definition: List.h:100
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:1381
ogdf::ListPure::empty
bool empty() const
Returns true iff the list is empty.
Definition: List.h:257
ogdf::ListPure::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: List.h:572
ogdf::List::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: List.h:1374
ogdf::List::clear
void clear()
Removes all elements from the list.
Definition: List.h:1452
ogdf::List::insertBefore
iterator insertBefore(const E &x, iterator it)
Inserts element x before it.
Definition: List.h:1393
ogdf::List::moveToFront
void moveToFront(iterator it, List< E > &L2)
Moves it to the begin of the list.
Definition: List.h:1465
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:221
ogdf::ListPure::insert
iterator insert(const E &x, iterator it, Direction dir=Direction::after)
Inserts element x before or after it.
Definition: List.h:603
ogdf::ListPure::permute
void permute()
Randomly permutes the elements in the list.
Definition: List.h:1227
ogdf::ListPure::value_type
E value_type
Represents the data type stored in a list element.
Definition: List.h:209
ogdf::ListElement::m_prev
ListElement< E > * m_prev
Pointer to predecessor element.
Definition: List.h:59