Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

SList.h
Go to the documentation of this file.
1 
32 #pragma once
33 
35 
36 namespace ogdf {
37 
38 template<class E> class SListPure;
39 template<class E, bool isConst> class SListIteratorBase;
41 template<class E> using SListIterator = SListIteratorBase<E, false>;
42 
44 template<class E>
45 class SListElement {
46  friend class SListPure<E>;
47  friend class SListIteratorBase<E, true>;
48  friend class SListIteratorBase<E, false>;
49 
51  E m_x;
52 #ifdef OGDF_DEBUG
53  SListPure<E> *m_list;
54 #endif
55 
57  SListElement(SListPure<E> *list, const E &x, SListElement<E> *next)
58  : m_next(next), m_x(x) {
59 #ifdef OGDF_DEBUG
60  m_list = list;
61 #endif
62  }
64  SListElement(SListPure<E> *list, const E &x) : SListElement(list, x, nullptr) { }
66  SListElement() : SListElement(nullptr, E()) { }
68  template<class ... Args>
69  SListElement(SListPure<E> *list, SListElement<E> *next, Args && ... args)
70  : SListElement(list, E(std::forward<Args>(args)...), next) { }
71 
73 };
74 
76 
85 template<class E, bool isConst> class SListIteratorBase {
86  friend class SListIteratorBase<E, !isConst>;
87  friend class SListPure<E>;
88 
90  using ListElem = typename std::conditional<isConst, const SListElement<E>, SListElement<E>>::type;
93 
95 
97  operator ListElem *() { return m_pX; }
98 
99 public:
102 
105 
109 
111  // gcc9 complains since it cannot match the templated constructor above (-Werror=deprecated-copy).
113 
115  bool valid() const { return m_pX != nullptr; }
116 
117 #ifdef OGDF_DEBUG
118  SListPure<E> *listOf() {
121  OGDF_ASSERT(valid());
122  return m_pX->m_list;
123  }
124 #endif
125 
128  return m_pX == it.m_pX;
129  }
130 
133  return m_pX != it.m_pX;
134  }
135 
137  SListIteratorBase<E, isConst> succ() const { return m_pX->m_next; }
138 
140  Elem &operator*() const { return m_pX->m_x; }
141 
144  m_pX = it.m_pX;
145  return *this;
146  }
147 
150  m_pX = m_pX->m_next;
151  return *this;
152  }
153 
157  m_pX = m_pX->m_next;
158  return it;
159  }
160 
162 };
163 
165 
175 template<class E> class SListPure {
178 
179 public:
181  using value_type = E;
183  using reference = E&;
185  using const_reference = const E&;
190 
192  SListPure() : m_head(nullptr), m_tail(nullptr) { }
193 
195  SListPure(std::initializer_list<E> init) : m_head(nullptr), m_tail(nullptr) {
196  for (const E &x : init)
197  pushBack(x);
198  }
200  SListPure(const SListPure<E> &L) : m_head(nullptr), m_tail(nullptr) {
201  copy(L);
202  }
203 
205 
209  L.m_head = L.m_tail = nullptr;
210  }
211 
213  virtual ~SListPure() { clear(); }
214 
220 
222  bool empty() const { return m_head == nullptr; }
223 
225 
229  virtual int size() const {
230  int count = 0;
231  for (SListElement<E> *pX = m_head; pX != nullptr; pX = pX->m_next)
232  ++count;
233  return count;
234  }
235 
237 
241  OGDF_ASSERT(m_head != nullptr);
242  return m_head->m_x;
243  }
244 
246 
250  OGDF_ASSERT(m_head != nullptr);
251  return m_head->m_x;
252  }
253 
255 
259  OGDF_ASSERT(m_tail != nullptr);
260  return m_tail->m_x;
261  }
262 
264 
268  OGDF_ASSERT(m_tail != nullptr);
269  return m_tail->m_x;
270  }
271 
273 
276  const_iterator get(int pos) const {
277  SListElement<E> *pX;
278  for(pX = m_head; pX != nullptr; pX = pX->m_next)
279  if (pos-- == 0) break;
280  return pX;
281  }
282 
284 
287  iterator get(int pos) {
288  SListElement<E> *pX;
289  for(pX = m_head; pX != nullptr; pX = pX->m_next)
290  if (pos-- == 0) break;
291  return pX;
292  }
293 
295 
299  int pos(const_iterator it) const {
300  OGDF_ASSERT(it.listOf() == this);
301  int p = 0;
302  for(SListElement<E> *pX = m_head; pX != nullptr; pX = pX->m_next, ++p)
303  if (pX == it) break;
304  return p;
305  }
306 
308 
313 
315 
318  iterator begin() { return m_head; }
319 
321 
324  const_iterator begin() const { return m_head; }
325 
327 
330  const_iterator cbegin() const { return m_head; }
331 
333 
336  iterator end() { return SListIterator<E>(); }
337 
339 
343 
345 
349 
351 
355 
357 
360  const_iterator backIterator() const { return m_tail; }
361 
363 
367  OGDF_ASSERT(it.listOf() == this);
368  const SListElement<E> *pX = it;
369  return (pX->m_next) ? pX->m_next : m_head;
370  }
371 
373 
377  OGDF_ASSERT(it.listOf() == this);
378  SListElement<E> *pX = it;
379  return (pX->m_next) ? pX->m_next : m_head;
380  }
381 
383 
388 
391  clear(); copy(L);
392  return *this;
393  }
394 
396 
400  clear();
401  m_head = L.m_head;
402  m_tail = L.m_tail;
403  L.m_head = L.m_tail = nullptr;
405  return *this;
406  }
407 
409  bool operator==(const SListPure<E> &L) const {
410  SListElement<E> *pX = m_head, *pY = L.m_head;
411  while(pX != nullptr && pY != nullptr) {
412  if(pX->m_x != pY->m_x)
413  return false;
414  pX = pX->m_next;
415  pY = pY->m_next;
416  }
417  return pX == nullptr && pY == nullptr;
418  }
419 
421  bool operator!=(const SListPure<E> &L) const {
422  return !operator==(L);
423  }
424 
426 
431 
433  iterator pushFront(const E &x) {
434  m_head = new SListElement<E>(this, x, m_head);
435  if (m_tail == nullptr) m_tail = m_head;
436  return m_head;
437  }
438 
440 
443  template<class ... Args>
444  iterator emplaceFront(Args && ... args) {
445  m_head = new SListElement<E>(this, m_head, std::forward<Args>(args)...);
446  if (m_tail == nullptr) m_tail = m_head;
447  return m_head;
448  }
449 
451  iterator pushBack(const E &x) {
452  SListElement<E> *pNew = new SListElement<E>(this, x);
453  if (m_head == nullptr)
454  m_head = m_tail = pNew;
455  else
456  m_tail = m_tail->m_next = pNew;
457  return m_tail;
458  }
459 
461 
464  template<class ... Args>
465  iterator emplaceBack(Args && ... args) {
466  SListElement<E> *pNew = new SListElement<E>(this, nullptr, std::forward<Args>(args)...);
467  if (m_head == nullptr)
468  m_head = m_tail = pNew;
469  else
470  m_tail = m_tail->m_next = pNew;
471  return m_tail;
472  }
473 
475 
478  iterator insertAfter(const E &x, iterator itBefore) {
479  OGDF_ASSERT(itBefore.listOf() == this);
480  SListElement<E> *pBefore = itBefore;
481  SListElement<E> *pNew = new SListElement<E>(this, x, pBefore->m_next);
482  if (pBefore == m_tail) m_tail = pNew;
483  return (pBefore->m_next = pNew);
484  }
485 
487 
492 
494 
497  void popFront() {
498  OGDF_ASSERT(m_head != nullptr);
499  SListElement<E> *pX = m_head;
500  if ((m_head = m_head->m_next) == nullptr) m_tail = nullptr;
501  delete pX;
502  }
503 
505 
509  E el = front();
510  popFront();
511  return el;
512  }
513 
515 
518  void delSucc(iterator itBefore) {
519  OGDF_ASSERT(itBefore.listOf() == this);
520  SListElement<E> *pBefore = itBefore;
521  OGDF_ASSERT(pBefore != nullptr);
522  SListElement<E> *pDel = pBefore->m_next;
523  OGDF_ASSERT(pDel != nullptr);
524  if ((pBefore->m_next = pDel->m_next) == nullptr) m_tail = pBefore;
525  delete pDel;
526  }
527 
529  void clear() {
530  if (m_head == nullptr) return;
531 
532  if (!std::is_trivially_destructible<E>::value) {
533  for(SListElement<E> *pX = m_head; pX != nullptr; pX = pX->m_next)
534  pX->m_x.~E();
535  }
536  OGDF_ALLOCATOR::deallocateList(sizeof(SListElement<E>),m_head,m_tail);
537 
538  m_head = m_tail = nullptr;
539  }
540 
542 
547 
550  OGDF_ASSERT(m_head != nullptr);
551  OGDF_ASSERT(this != &L2);
552 
553  SListElement<E> *pX = m_head;
554  if ((m_head = m_head->m_next) == nullptr) m_tail = nullptr;
555  pX->m_next = L2.m_head;
556  L2.m_head = pX;
557  if (L2.m_tail == nullptr) L2.m_tail = L2.m_head;
558 
559  L2.m_head->m_list = &L2;
560  }
561 
564  OGDF_ASSERT(m_head != nullptr);
565  OGDF_ASSERT(this != &L2);
566 
567  SListElement<E> *pX = m_head;
568  if ((m_head = m_head->m_next) == nullptr) m_tail = nullptr;
569  pX->m_next = nullptr;
570  if (L2.m_head == nullptr)
571  L2.m_head = L2.m_tail = pX;
572  else
573  L2.m_tail = L2.m_tail->m_next = pX;
574 
575  L2.m_tail->m_list = &L2;
576  }
577 
579 
582  void moveFrontToSucc(SListPure<E> &L2, iterator itBefore) {
583  OGDF_ASSERT(m_head != nullptr);
584  OGDF_ASSERT(this != &L2);
585  OGDF_ASSERT(itBefore.listOf() == &L2);
586 
587  SListElement<E> *pBefore = itBefore;
588  SListElement<E> *pX = m_head;
589  if ((m_head = m_head->m_next) == nullptr) m_tail = nullptr;
590  pX->m_next = pBefore->m_next;
591  pBefore->m_next = pX;
592  if (pBefore == L2.m_tail) L2.m_tail = pX;
593 
594  pX->m_list = &L2;
595  }
596 
598  void conc(SListPure<E> &L2) {
599  if (m_head)
600  m_tail->m_next = L2.m_head;
601  else
602  m_head = L2.m_head;
603  if (L2.m_tail != nullptr) m_tail = L2.m_tail;
604 
605  reassignListRefs(L2.m_head);
606 
607  L2.m_head = L2.m_tail = nullptr;
608  }
609 
611  void reverse() {
612  SListElement<E> *p, *pNext, *pPred = nullptr;
613  for(p = m_head; p; p = pNext) {
614  pNext = p->m_next;
615  p->m_next = pPred;
616  pPred = p;
617  }
618  std::swap(m_head,m_tail);
619  }
620 
622 
627 
629  SListConstIterator<E> search(const E &e) const {
631  for (i = begin(); i.valid(); ++i)
632  if (*i == e) return i;
633  return i;
634  }
635 
637  SListIterator<E> search(const E &e) {
639  for (i = begin(); i.valid(); ++i)
640  if (*i == e) return i;
641  return i;
642  }
643 
645  template<class COMPARER>
646  SListConstIterator<E> search(const E &e, const COMPARER &comp) const {
648  for (i = begin(); i.valid(); ++i)
649  if (comp.equal(*i, e)) return i;
650  return i;
651  }
652 
654  template<class COMPARER>
655  SListIterator<E> search(const E &e, const COMPARER &comp) {
657  for (i = begin(); i.valid(); ++i)
658  if (comp.equal(*i, e)) return i;
659  return i;
660  }
661 
663  void quicksort() {
665  }
666 
668  template<class COMPARER>
669  void quicksort(const COMPARER &comp) {
670  ogdf::quicksortTemplate(*this,comp);
671  }
672 
674 
681  void bucketSort(int l, int h, BucketFunc<E> &f);
682 
684  void bucketSort(BucketFunc<E> &f);
685 
687 
692 
695  std::function<bool(const E&)> includeElement = [](const E&) { return true; },
696  bool isFastTest = true) const {
697  return chooseIteratorFrom(*this, includeElement, isFastTest);
698  }
699 
702  std::function<bool(const E&)> includeElement = [](const E&) { return true; },
703  bool isFastTest = true) {
704  return chooseIteratorFrom(*this, includeElement, isFastTest);
705  }
706 
709  std::function<bool(const E&)> includeElement = [](const E&) { return true; },
710  bool isFastTest = true) const {
711  const_iterator result = chooseIterator(includeElement, isFastTest);
712  OGDF_ASSERT(result.valid());
713  return *result;
714  }
715 
718  std::function<bool(const E&)> includeElement = [](const E&) { return true; },
719  bool isFastTest = true) {
720  iterator result = chooseIterator(includeElement, isFastTest);
721  OGDF_ASSERT(result.valid());
722  return *result;
723  }
724 
726  void permute() {
727  std::minstd_rand rng(randomSeed());
728  permute(size(), rng);
729  }
730 
732  template<class RNG>
733  void permute(RNG &rng) {
734  permute(size(), rng);
735  }
736 
738 
739 protected:
740  void copy(const SListPure<E> &L) {
741  for(SListElement<E> *pX = L.m_head; pX != nullptr; pX = pX->m_next)
742  pushBack(pX->m_x);
743  }
744 
746  template<class RNG>
747  void permute(const int n, RNG &rng);
748 
750  inline void reassignListRefs(SListElement<E> *start = nullptr) {
751 #ifdef OGDF_DEBUG
752  for(auto e = start == nullptr ? m_head : start; e != nullptr; e = e->m_next) {
753  e->m_list = this;
754  }
755 #endif
756  }
757 
759 };
760 
762 
772 template<class E>
773 class SList : private SListPure<E> {
774 
775  int m_count;
776 
777 public:
778  using typename SListPure<E>::value_type;
779  using typename SListPure<E>::reference;
780  using typename SListPure<E>::const_reference;
781  using typename SListPure<E>::const_iterator;
782  using typename SListPure<E>::iterator;
783 
785  SList() : m_count(0) { }
786 
788  SList(std::initializer_list<E> init) : SListPure<E>(init), m_count((int) init.size()) { }
789 
791  SList(const SList<E> &L) : SListPure<E>(L), m_count(L.m_count) { }
792 
794 
798  L.m_count = 0;
799  }
800 
806 
808 
811  int size() const { return m_count; }
812 
814  const SListPure<E> &getSListPure() const { return *this; }
815 
817 
822 
826  m_count = L.m_count;
827  return *this;
828  }
829 
831 
835  m_count = L.m_count;
837  L.m_count = 0;
838  return *this;
839  }
840 
842  bool operator==(const SList<E> &L) const {
843  return (m_count == L.m_count) && SListPure<E>::operator==(L);
844  }
845 
847  bool operator!=(const SList<E> &L) const {
848  return !operator==(L);
849  }
850 
852 
857 
860  ++m_count;
861  return SListPure<E>::pushFront(x);
862  }
863 
865  template<class ... Args>
866  iterator emplaceFront(Args && ... args) {
867  ++m_count;
868  return SListPure<E>::emplaceFront(std::forward<Args>(args)...);
869  }
870 
873  ++m_count;
874  return SListPure<E>::pushBack(x);
875  }
876 
878  template<class ... Args>
879  iterator emplaceBack(Args && ... args) {
880  ++m_count;
881  return SListPure<E>::emplaceBack(std::forward<Args>(args)...);
882  }
883 
886  ++m_count;
887  return SListPure<E>::insertAfter(x, itBefore);
888  }
889 
891 
896 
898  void popFront() {
899  --m_count;
901  }
902 
905  E el = front();
906  popFront();
907  return el;
908  }
909 
911  void delSucc(SListIterator<E> itBefore) {
912  --m_count;
913  SListPure<E>::delSucc(itBefore);
914  }
915 
917  void clear() {
918  m_count = 0;
920  }
921 
923 
928 
932  --m_count; ++L2.m_count;
933  }
934 
938  --m_count; ++L2.m_count;
939  }
940 
943  SListPure<E>::moveFrontToSucc(L2,itBefore);
944  --m_count; ++L2.m_count;
945  }
946 
948  void conc(SList<E> &L2) {
949  SListPure<E>::conc(L2);
950  m_count += L2.m_count;
951  L2.m_count = 0;
952  }
953 
954  using SListPure<E>::empty;
955  using SListPure<E>::front;
956  using SListPure<E>::back;
957  using SListPure<E>::get;
958  using SListPure<E>::pos;
959  using SListPure<E>::begin;
960  using SListPure<E>::cbegin;
961  using SListPure<E>::end;
962  using SListPure<E>::cend;
965  using SListPure<E>::reverse;
966  using SListPure<E>::search;
971  using SListPure<E>::permute;
972 
974 };
975 
976 template<class E>
978 {
979  // if less than two elements, nothing to do
980  if (m_head == m_tail) return;
981 
982  int l, h;
983  l = h = f.getBucket(m_head->m_x);
984 
985  SListElement<E> *pX;
986  for(pX = m_head->m_next; pX; pX = pX->m_next)
987  {
988  int i = f.getBucket(pX->m_x);
989  if (i < l) l = i;
990  if (i > h) h = i;
991  }
992 
993  bucketSort(l,h,f);
994 }
995 
996 template<class E>
998 {
999  // if less than two elements, nothing to do
1000  if (m_head == m_tail) return;
1001 
1002  Array<SListElement<E> *> head(l,h,nullptr), tail(l,h);
1003 
1004  SListElement<E> *pX;
1005  for (pX = m_head; pX; pX = pX->m_next) {
1006  int i = f.getBucket(pX->m_x);
1007  if (head[i])
1008  tail[i] = (tail[i]->m_next = pX);
1009  else
1010  head[i] = tail[i] = pX;
1011  }
1012 
1013  SListElement<E> *pY = nullptr;
1014  for (int i = l; i <= h; i++) {
1015  pX = head[i];
1016  if (pX) {
1017  if (pY)
1018  pY->m_next = pX;
1019  else
1020  m_head = pX;
1021  pY = tail[i];
1022  }
1023  }
1024 
1025  m_tail = pY;
1026  pY->m_next = nullptr;
1027 }
1028 
1029 template<class E>
1030 template<class RNG>
1031 void SListPure<E>::permute(const int n, RNG &rng)
1032 {
1033  if (n == 0) {
1034  return;
1035  }
1036 
1037  Array<SListElement<E> *> A(n+1);
1038  A[n] = nullptr;
1039 
1040  int i = 0;
1041  SListElement<E> *pX;
1042  for (pX = m_head; pX; pX = pX->m_next)
1043  A[i++] = pX;
1044 
1045  A.permute(0,n-1,rng);
1046 
1047  for (i = 0; i < n; i++) {
1048  A[i]->m_next = A[i+1];
1049  }
1050 
1051  m_head = A[0];
1052  m_tail = A[n-1];
1053 }
1054 
1056 template<class E>
1057 void print(std::ostream &os, const SListPure<E> &L, char delim = ' ')
1058 {
1059  SListConstIterator<E> pX = L.begin();
1060  if (pX.valid()) {
1061  os << *pX;
1062  for(++pX; pX.valid(); ++pX)
1063  os << delim << *pX;
1064  }
1065 }
1066 
1068 template<class E>
1069 void print(std::ostream &os, const SList<E> &L, char delim = ' ')
1070 {
1071  print(os, L.getSListPure(), delim);
1072 }
1073 
1075 template<class E>
1076 std::ostream &operator<<(std::ostream &os, const SListPure<E> &L)
1077 {
1078  print(os,L);
1079  return os;
1080 }
1081 
1083 template<class E>
1084 std::ostream &operator<<(std::ostream &os, const SList<E> &L)
1085 {
1086  return operator<<(os,L.getSListPure());
1087 }
1088 
1091 template<class E>
1092 void bucketSort(Array<E> &a, int min, int max, BucketFunc<E> &f)
1093 {
1094  if (a.low() >= a.high()) return;
1095 
1096  Array<SListPure<E> > bucket(min,max);
1097 
1098  int i;
1099  for(i = a.low(); i <= a.high(); ++i)
1100  bucket[f.getBucket(a[i])].pushBack(a[i]);
1101 
1102  i = a.low();
1103  for(int j = min; j <= max; ++j) {
1104  SListConstIterator<E> it = bucket[j].begin();
1105  for(; it.valid(); ++it)
1106  a[i++] = *it;
1107  }
1108 }
1109 
1110 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
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::SListPure::SListPure
SListPure(const SListPure< E > &L)
Constructs a singly linked list that is a copy of L.
Definition: SList.h:200
ogdf::SList::getSListPure
const SListPure< E > & getSListPure() const
Conversion to const SListPure.
Definition: SList.h:814
ogdf::SListPure::chooseIterator
const_iterator chooseIterator(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
Definition: SList.h:694
ogdf::SListPure::iterator
SListIterator< E > iterator
Provides a forward iterator that can read or modify any element in a list.
Definition: SList.h:189
ogdf::SListIteratorBase::ListElem
typename std::conditional< isConst, const SListElement< E >, SListElement< E > >::type ListElem
The underlying list element, depending on isConst.
Definition: SList.h:90
ogdf::SList::emplaceFront
iterator emplaceFront(Args &&... args)
Adds a new element at the beginning of the list.
Definition: SList.h:866
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::SListElement::m_x
E m_x
Stores the content.
Definition: SList.h:51
ogdf::SListPure::search
SListIterator< E > search(const E &e, const COMPARER &comp)
Scans the list for the specified element (using the user-defined comparer) and returns an iterator to...
Definition: SList.h:655
ogdf::SListPure::const_reference
const E & const_reference
Provides a reference to a const element stored in a list for reading and performing const operations.
Definition: SList.h:185
ogdf::SListPure::search
SListConstIterator< E > search(const E &e) const
Scans the list for the specified element and returns an iterator to the first occurrence in the list,...
Definition: SList.h:629
ogdf::SListPure::backIterator
iterator backIterator()
Returns an iterator to the last element of the list.
Definition: SList.h:354
ogdf::SList::m_count
int m_count
The length of the list.
Definition: SList.h:775
ogdf::SListPure::reverse
void reverse()
Reverses the order of the list elements.
Definition: SList.h:611
ogdf::SList::moveFrontToFront
void moveFrontToFront(SList< E > &L2)
Moves the first element of this list to the begin of list L2.
Definition: SList.h:930
ogdf::SList::SList
SList(std::initializer_list< E > init)
Constructs a singly linked list containing the elements in init.
Definition: SList.h:788
ogdf::SListPure::front
const_reference front() const
Returns a reference to the first element.
Definition: SList.h:240
ogdf::SListPure::quicksort
void quicksort(const COMPARER &comp)
Sorts the list using Quicksort and comparer comp.
Definition: SList.h:669
ogdf::SList::SList
SList()
Constructs an empty singly linked list.
Definition: SList.h:785
ogdf::SListPure::pos
int pos(const_iterator it) const
Returns the position (starting with 0) of it in the list.
Definition: SList.h:299
ogdf::SList::operator=
SList< E > & operator=(const SList< E > &L)
Assignment operator.
Definition: SList.h:824
ogdf::SListElement::SListElement
SListElement()
Constructs an SListElement.
Definition: SList.h:66
ogdf::whaType::A
@ A
ogdf::SListIteratorBase
Encapsulates a pointer to an ogdf::SList element.
Definition: SList.h:39
ogdf::Array::high
INDEX high() const
Returns the maximal array index.
Definition: Array.h:283
ogdf::SListPure::get
iterator get(int pos)
Returns an iterator pointing to the element at position pos.
Definition: SList.h:287
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:773
ogdf::SList::popFrontRet
E popFrontRet()
Removes the first element from the list and returns it.
Definition: SList.h:904
ogdf::SListPure::back
reference back()
Returns a reference to the last element.
Definition: SList.h:267
ogdf::SListPure::permute
void permute()
Randomly permutes the elements in the list.
Definition: SList.h:726
ogdf::SListElement::SListElement
SListElement(SListPure< E > *list, const E &x)
Constructs an SListElement.
Definition: SList.h:64
ogdf::SListPure::insertAfter
iterator insertAfter(const E &x, iterator itBefore)
Inserts element x after itBefore.
Definition: SList.h:478
ogdf::SListPure::clear
void clear()
Removes all elements from the list.
Definition: SList.h:529
ogdf::BucketFunc
Abstract base class for bucket functions.
Definition: basic.h:241
ogdf::bucketSort
void bucketSort(Array< E > &a, int min, int max, BucketFunc< E > &f)
Bucket-sort array a using bucket assignment f; the values of f must be in the interval [min,...
Definition: SList.h:1092
ogdf::SListPure::m_head
SListElement< E > * m_head
Pointer to first element.
Definition: SList.h:176
ogdf::SListPure::SListPure
SListPure()
Constructs an empty singly linked list.
Definition: SList.h:192
ogdf::SListIteratorBase::valid
bool valid() const
Returns true iff the iterator points to an element.
Definition: SList.h:115
ogdf::SList::insertAfter
SListIterator< E > insertAfter(const E &x, SListIterator< E > itBefore)
Inserts element x after itBefore.
Definition: SList.h:885
ogdf::SListPure::copy
void copy(const SListPure< E > &L)
Definition: SList.h:740
ogdf::SListPure::value_type
E value_type
Represents the data type stored in a list element.
Definition: SList.h:181
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
ogdf::SListPure::chooseIterator
iterator chooseIterator(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
Definition: SList.h:701
ogdf::SListPure::quicksort
void quicksort()
Sorts the list using Quicksort.
Definition: SList.h:663
ogdf::SListPure::cyclicSucc
iterator cyclicSucc(iterator it)
Returns an iterator to the cyclic successor of it.
Definition: SList.h:376
ogdf::SListPure::reference
E & reference
Provides a reference to an element stored in a list.
Definition: SList.h:183
ogdf::SListPure::const_iterator
SListConstIterator< E > const_iterator
Provides a forward iterator that can read a const element in a list.
Definition: SList.h:187
ogdf::SListPure::begin
iterator begin()
Returns an iterator to the first element of the list.
Definition: SList.h:318
ogdf::SListElement::m_next
SListElement< E > * m_next
Pointer to successor element.
Definition: SList.h:50
ogdf::SListPure::cend
const_iterator cend() const
Returns a const iterator to one-past-last element of the list.
Definition: SList.h:348
ogdf::SListPure::back
const_reference back() const
Returns a reference to the last element.
Definition: SList.h:258
ogdf::SListPure::empty
bool empty() const
Returns true iff the list is empty.
Definition: SList.h:222
ogdf::SListPure::emplaceBack
iterator emplaceBack(Args &&... args)
Adds a new element at the end of the list.
Definition: SList.h:465
ogdf::SList::moveFrontToBack
void moveFrontToBack(SList< E > &L2)
Moves the first element of this list to the end of list L2.
Definition: SList.h:936
ogdf::SListIteratorBase::operator=
SListIteratorBase< E, isConst > & operator=(const SListIterator< E > &it)
Assignment operator.
Definition: SList.h:143
ogdf::SListPure::m_tail
SListElement< E > * m_tail
Pointer to last element.
Definition: SList.h:177
ogdf::SList::moveFrontToSucc
void moveFrontToSucc(SList< E > &L2, SListIterator< E > itBefore)
Moves the first element of this list to list L2 inserted after itBefore.
Definition: SList.h:942
list_templates.h
Implementation of algorithms as templates working with different list types.
ogdf::SList::operator==
bool operator==(const SList< E > &L) const
Equality operator.
Definition: SList.h:842
ogdf::SListPure::conc
void conc(SListPure< E > &L2)
Appends L2 to this list and makes L2 empty.
Definition: SList.h:598
ogdf::SListPure::end
iterator end()
Returns an iterator to one-past-last element of the list.
Definition: SList.h:336
ogdf::SListPure::search
SListIterator< E > search(const E &e)
Scans the list for the specified element and returns an iterator to the first occurrence in the list,...
Definition: SList.h:637
ogdf::SListIteratorBase::SListIteratorBase
SListIteratorBase()
Constructs an invalid iterator.
Definition: SList.h:104
backward::Color::type
type
Definition: backward.hpp:1716
ogdf::SListPure::delSucc
void delSucc(iterator itBefore)
Removes the succesor of itBefore.
Definition: SList.h:518
ogdf::SListPure::operator=
SListPure< E > & operator=(SListPure< E > &&L)
Assignment operator (move semantics).
Definition: SList.h:399
ogdf::SListPure::permute
void permute(RNG &rng)
Randomly permutes the elements in the list using random number generator rng.
Definition: SList.h:733
ogdf::SListIteratorBase< ogdf::ExternE >::Elem
typename std::conditional< isConst, const ogdf::ExternE, ogdf::ExternE >::type Elem
The underlying type, depending on isConst.
Definition: SList.h:92
backward::details::move
const T & move(const T &v)
Definition: backward.hpp:243
ogdf::SList::size
int size() const
Returns the number of elements in the list.
Definition: SList.h:811
ogdf::Array
The parameterized class Array implements dynamic arrays of type E.
Definition: Array.h:204
ogdf::SListIteratorBase::operator==
bool operator==(const SListIteratorBase< E, isConst > &it) const
Equality operator.
Definition: SList.h:127
ogdf::SListIteratorBase::operator!=
bool operator!=(const SListIteratorBase< E, isConst > &it) const
Inequality operator.
Definition: SList.h:132
ogdf::SListIteratorBase::operator++
SListIteratorBase< E, isConst > operator++(int)
Increment operator (postfix).
Definition: SList.h:155
ogdf::SListIteratorBase::operator*
Elem & operator*() const
Returns a reference to the element content.
Definition: SList.h:140
ogdf::SListPure
Singly linked lists.
Definition: SList.h:38
ogdf::SListPure::SListPure
SListPure(SListPure< E > &&L)
Constructs a singly linked list containing the elements of L (move semantics).
Definition: SList.h:208
ogdf::SListPure::get
const_iterator get(int pos) const
Returns an iterator pointing to the element at position pos.
Definition: SList.h:276
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::Array::begin
iterator begin()
Returns an iterator to the first element.
Definition: Array.h:314
ogdf::SListPure::reassignListRefs
void reassignListRefs(SListElement< E > *start=nullptr)
Sets the debug reference of all list elements starting at start to this.
Definition: SList.h:750
ogdf::SList::pushFront
SListIterator< E > pushFront(const E &x)
Adds element x at the beginning of the list.
Definition: SList.h:859
ogdf::SListPure::size
virtual int size() const
Returns the number of elements in the list.
Definition: SList.h:229
ogdf::SListPure::begin
const_iterator begin() const
Returns a const iterator to the first element of the list.
Definition: SList.h:324
ogdf::SList::SList
SList(SList< E > &&L)
Constructs a singly linked list containing the elements of L (move semantics).
Definition: SList.h:797
ogdf::SListPure::operator!=
bool operator!=(const SListPure< E > &L) const
Inequality operator.
Definition: SList.h:421
ogdf::SList::operator!=
bool operator!=(const SList< E > &L) const
Inequality operator.
Definition: SList.h:847
ogdf::SList::clear
void clear()
Removes all elements from the list.
Definition: SList.h:917
ogdf::SList::delSucc
void delSucc(SListIterator< E > itBefore)
Removes the succesor of itBefore.
Definition: SList.h:911
ogdf::randomSeed
long unsigned int randomSeed()
Returns a random value suitable as initial seed for a random number engine.
ogdf::SListPure::popFrontRet
E popFrontRet()
Removes the first element from the list and returns it.
Definition: SList.h:508
ogdf::SListPure::cbegin
const_iterator cbegin() const
Returns a const iterator to the first element of the list.
Definition: SList.h:330
ogdf::SListPure::moveFrontToBack
void moveFrontToBack(SListPure< E > &L2)
Moves the first element of this list to the end of list L2.
Definition: SList.h:563
ogdf::SListIteratorBase::operator++
SListIteratorBase< E, isConst > & operator++()
Increment operator (prefix).
Definition: SList.h:149
ogdf::graphics::init
void init()
Definition: graphics.h:472
ogdf::SListElement
Structure for elements of singly linked lists.
Definition: SList.h:45
ogdf::SListIteratorBase::SListIteratorBase
SListIteratorBase(const SListIterator< E > &it)
Copy constructor.
Definition: SList.h:112
std
Definition: GML.h:110
ogdf::SListIteratorBase::SListIteratorBase
SListIteratorBase(const SListIteratorBase< E, isArgConst > &it)
Constructs an iterator that is a copy of it.
Definition: SList.h:108
ogdf::SListIteratorBase::succ
SListIteratorBase< E, isConst > succ() const
Returns successor iterator.
Definition: SList.h:137
ogdf::SListElement::SListElement
SListElement(SListPure< E > *list, SListElement< E > *next, Args &&... args)
Constructs an SListElement with given arguments args for constructor of element type.
Definition: SList.h:69
ogdf::SListPure::end
const_iterator end() const
Returns a const iterator to one-past-last element of the list.
Definition: SList.h:342
ogdf::SList::emplaceBack
iterator emplaceBack(Args &&... args)
Adds a new element at the end of the list.
Definition: SList.h:879
ogdf::SListPure::chooseElement
reference chooseElement(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true)
Definition: SList.h:717
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::SListIteratorBase::m_pX
ListElem * m_pX
Pointer to slist element.
Definition: SList.h:94
ogdf::SListPure::~SListPure
virtual ~SListPure()
Destructor.
Definition: SList.h:213
ogdf::Array::low
INDEX low() const
Returns the minimal array index.
Definition: Array.h:280
ogdf::SList::conc
void conc(SList< E > &L2)
Appends L2 to this list and makes L2 empty.
Definition: SList.h:948
ogdf::SListIteratorBase::SListIteratorBase
SListIteratorBase(ListElem *pX)
Constructs an iterator that points to pX.
Definition: SList.h:101
ogdf::SListPure::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: SList.h:451
ogdf::SListPure::cyclicSucc
const_iterator cyclicSucc(const_iterator it) const
Returns an iterator to the cyclic successor of it.
Definition: SList.h:366
ogdf::SListElement::SListElement
SListElement(SListPure< E > *list, const E &x, SListElement< E > *next)
Constructs an SListElement.
Definition: SList.h:57
ogdf::SListPure::operator==
bool operator==(const SListPure< E > &L) const
Equality operator.
Definition: SList.h:409
ogdf::SList::SList
SList(const SList< E > &L)
Constructs a singly linked list that is a copy of L.
Definition: SList.h:791
ogdf::SListPure::pushFront
iterator pushFront(const E &x)
Adds element x at the beginning of the list.
Definition: SList.h:433
ogdf::booth_lueker::PlanarLeafKey
Definition: PlanarLeafKey.h:41
ogdf::SListPure::backIterator
const_iterator backIterator() const
Returns a const iterator to the last element of the list.
Definition: SList.h:360
ogdf::quicksortTemplate
void quicksortTemplate(LIST &L)
Definition: list_templates.h:74
ogdf::SListPure::bucketSort
void bucketSort(int l, int h, BucketFunc< E > &f)
Sorts the list using bucket sort.
Definition: SList.h:997
ogdf::SList::operator=
SList< E > & operator=(SList< E > &&L)
Assignment operator (move semantics).
Definition: SList.h:834
ogdf::SListPure::SListPure
SListPure(std::initializer_list< E > init)
Constructs a singly linked list containing the elements in init.
Definition: SList.h:195
ogdf::SListPure::popFront
void popFront()
Removes the first element from the list.
Definition: SList.h:497
ogdf::SListPure::search
SListConstIterator< E > search(const E &e, const COMPARER &comp) const
Scans the list for the specified element (using the user-defined comparer) and returns an iterator to...
Definition: SList.h:646
ogdf::SListPure::emplaceFront
iterator emplaceFront(Args &&... args)
Adds a new element at the beginning of the list.
Definition: SList.h:444
ogdf::SListPure::operator=
SListPure< E > & operator=(const SListPure< E > &L)
Assignment operator.
Definition: SList.h:390
ogdf::SListPure::moveFrontToFront
void moveFrontToFront(SListPure< E > &L2)
Moves the first element of this list to the begin of list L2.
Definition: SList.h:549
ogdf::BucketFunc::getBucket
virtual int getBucket(const E &x)=0
Returns the bucket of x.
ogdf::SListPure::chooseElement
const_reference chooseElement(std::function< bool(const E &)> includeElement=[](const E &) { return true;}, bool isFastTest=true) const
Definition: SList.h:708
ogdf::SList::pushBack
SListIterator< E > pushBack(const E &x)
Adds element x at the end of the list.
Definition: SList.h:872
ogdf::SList::popFront
void popFront()
Removes the first element from the list.
Definition: SList.h:898
ogdf::SListPure::front
reference front()
Returns a reference to the first element.
Definition: SList.h:249
ogdf::SListPure::moveFrontToSucc
void moveFrontToSucc(SListPure< E > &L2, iterator itBefore)
Moves the first element of this list to list L2 inserted after itBefore.
Definition: SList.h:582