Open
Graph Drawing
Framework

  v. 2023.09 (Elderberry)
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

SortedSequence.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <ogdf/basic/Reverse.h>
35 #include <ogdf/basic/comparer.h>
36 #include <ogdf/basic/memory.h>
37 
38 #include <random>
39 
40 namespace ogdf {
41 
42 template<class KEY, class INFO, class CMP, bool isConst, bool isReverse>
43 class SortedSequenceIteratorBase;
44 
45 template<class KEY, class INFO, class CMP>
46 using SortedSequenceIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, false, false>;
47 
48 template<class KEY, class INFO, class CMP>
49 using SortedSequenceConstIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, true, false>;
50 
51 template<class KEY, class INFO, class CMP>
52 using SortedSequenceReverseIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, false, true>;
53 
54 template<class KEY, class INFO, class CMP>
55 using SortedSequenceConstReverseIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, true, true>;
56 
58 
65 template<class KEY, class INFO, class CMP = StdComparer<KEY>>
66 class SortedSequence {
67  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, false, false>;
68  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, true, false>;
69  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, false, true>;
70  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, true, true>;
71 
73  struct Element {
74  KEY m_key;
75  INFO m_info;
76  int m_height;
77 
78  Element** m_next;
79  Element** m_prev;
80 
82  Element(const KEY& key, const INFO& info, int height)
83  : m_key(key), m_info(info), m_height(height) {
84  m_next = (Element**)malloc(height * sizeof(Element*));
85  m_prev = (Element**)malloc(height * sizeof(Element*));
86  }
87 
89 
93  Element(int height) : m_height(0) {
94  m_next = (Element**)malloc(height * sizeof(Element*));
95  m_prev = (Element**)malloc(height * sizeof(Element*));
96  }
97 
98  Element(const Element&) = delete;
99 
101  ~Element() {
102  free(m_prev);
103  free(m_next);
104  }
105 
107  void grow(int newHeight) {
108  Element** p = static_cast<Element**>(realloc(m_next, newHeight * sizeof(Element*)));
109  if (p == nullptr) {
110  OGDF_THROW(InsufficientMemoryException);
111  }
112  m_next = p;
113 
114  p = static_cast<Element**>(realloc(m_prev, newHeight * sizeof(Element*)));
115  if (p == nullptr) {
116  OGDF_THROW(InsufficientMemoryException);
117  }
118  m_prev = p;
119  }
120 
121  OGDF_NEW_DELETE
122  };
123 
124 public:
126  using iterator = SortedSequenceIterator<KEY, INFO, CMP>;
128  using const_iterator = SortedSequenceConstIterator<KEY, INFO, CMP>;
130  using reverse_iterator = SortedSequenceReverseIterator<KEY, INFO, CMP>;
132  using const_reverse_iterator = SortedSequenceConstReverseIterator<KEY, INFO, CMP>;
133 
135  SortedSequence(const CMP& comparer = CMP())
136  : m_comparer(comparer), m_rng(randomSeed()), m_randomBits(0, 1) {
137  initEmpty();
138  }
139 
141  SortedSequence(std::initializer_list<std::pair<KEY, INFO>> initList);
142 
144  SortedSequence(const SortedSequence<KEY, INFO, CMP>& S);
145 
147 
150  SortedSequence(SortedSequence<KEY, INFO, CMP>&& S);
151 
153  ~SortedSequence() {
154  clear();
155  delete m_dummy;
156  }
157 
163 
166  int size() const { return m_size; }
167 
169  bool empty() const { return m_size == 0; }
170 
172  iterator begin();
173 
175  const_iterator begin() const;
176 
178  const_iterator cbegin() const { return begin(); }
179 
181  iterator end();
182 
184  const_iterator end() const;
185 
187  const_iterator cend() const { return end(); }
188 
190  reverse_iterator rbegin();
191 
193  const_reverse_iterator rbegin() const;
194 
196  const_reverse_iterator crbegin() const { return rbegin(); }
197 
199  reverse_iterator rend();
200 
202  const_reverse_iterator rend() const;
203 
205  const_reverse_iterator crend() const { return rend(); }
206 
211 
214  iterator lookup(const KEY& key);
215 
217  const_iterator lookup(const KEY& key) const;
218 
222  iterator locate(const KEY& key);
223 
227  const_iterator locate(const KEY& key) const;
228 
231 
234  iterator minItem() { return begin(); }
235 
238 
241  const_iterator minItem() const { return begin(); }
242 
245 
248  reverse_iterator maxItem() { return rbegin(); }
249 
252 
255  const_reverse_iterator maxItem() const { return rbegin(); }
256 
258 
262 
265  iterator insert(const KEY& key, const INFO& info);
266 
268  void del(const KEY& key);
269 
271  void delItem(iterator it);
272 
274  void clear() {
275  Element* item = m_dummy->m_next[0];
276  while (item != m_dummy) {
277  Element* old = item;
278  item = item->m_next[0];
279  delete old;
280  }
281  m_size = 0;
282  m_height = 1;
283  m_dummy->m_next[0] = m_dummy->m_prev[0] = m_dummy;
284  }
285 
287 
291 
294  SortedSequence<KEY, INFO, CMP>& operator=(const SortedSequence<KEY, INFO, CMP>& S);
295 
297 
300  SortedSequence<KEY, INFO, CMP>& operator=(SortedSequence<KEY, INFO, CMP>&& S);
301 
303 
306  bool operator==(const SortedSequence<KEY, INFO, CMP>& S);
307 
309 
312  bool operator!=(const SortedSequence<KEY, INFO, CMP>& S) { return !operator==(S); }
313 
315 
319 
322 
327  iterator insertAfter(iterator it, const KEY& key, const INFO& info);
328 
330 
340  void reverseItems(iterator itBegin, iterator itEnd) {
341  reverseElements(itBegin.m_pElement, itEnd.m_pElement);
342  }
343 
345 
346 private:
347  CMP m_comparer;
348  int m_size;
349  Element* m_dummy;
350  int m_height;
351  int m_realHeight;
352 
353  std::minstd_rand m_rng;
354  std::uniform_int_distribution<> m_randomBits;
355 
356  void initEmpty() {
357  m_size = 0;
358  m_realHeight = 5;
359  m_height = 1;
360 
361  m_dummy = new Element(m_realHeight);
362  m_dummy->m_next[0] = m_dummy;
363  m_dummy->m_prev[0] = m_dummy;
364  }
365 
366  int randomHeightAndGrow();
367  void grow(int newHeight);
368 
369  const Element* _lookup(const KEY& key) const;
370  const Element* _locate(const KEY& key) const;
371 
372  void removeElement(Element* p);
373  void insertElementAfterElement(Element* p, Element* q);
374  void reverseElements(Element* p, Element* q);
375 };
376 
378 template<class KEY, class INFO, class CMP, bool isConst, bool isReverse>
379 class SortedSequenceIteratorBase {
380  friend class SortedSequence<KEY, INFO, CMP>;
381  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, !isConst, isReverse>;
382  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, !isReverse>;
383  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, !isConst, !isReverse>;
384 
385  using Element =
386  typename std::conditional<isConst, const typename SortedSequence<KEY, INFO, CMP>::Element,
387  typename SortedSequence<KEY, INFO, CMP>::Element>::type;
388  Element* m_pElement;
389 
391  SortedSequenceIteratorBase(Element* pElement) : m_pElement(pElement) { }
392 
393 public:
395  SortedSequenceIteratorBase() : m_pElement(nullptr) { }
396 
398  template<bool isArgConst, typename std::enable_if<isConst || !isArgConst, int>::type = 0, bool isArgReverse>
399  SortedSequenceIteratorBase(
400  const SortedSequenceIteratorBase<KEY, INFO, CMP, isArgConst, isArgReverse>& it)
401  : m_pElement(it.m_pElement) { }
402 
404  // gcc9 complains since it cannot match the templated constructor above (-Werror=deprecated-copy).
405  SortedSequenceIteratorBase(
406  const SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& it)
407  : m_pElement(it.m_pElement) { }
408 
410  const KEY& key() const {
411  OGDF_ASSERT(valid());
412  return m_pElement->m_key;
413  }
414 
416  typename std::conditional<isConst, const INFO, INFO>::type& info() const {
417  OGDF_ASSERT(valid());
418  return m_pElement->m_info;
419  }
420 
422  bool valid() const { return m_pElement != nullptr; }
423 
425  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& operator++() {
426  m_pElement = isReverse ? predElement() : succElement();
427  return *this;
428  }
429 
431  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> operator++(int) {
432  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> it = *this;
433  m_pElement = isReverse ? predElement() : succElement();
434  return it;
435  }
436 
438  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& operator--() {
439  m_pElement = isReverse ? succElement() : predElement();
440  return *this;
441  }
442 
444  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> operator--(int) {
445  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> it = *this;
446  m_pElement = isReverse ? succElement() : predElement();
447  return it;
448  }
449 
451  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> succ() const {
452  return isReverse ? predElement() : succElement();
453  }
454 
456  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> pred() const {
457  return isReverse ? succElement() : predElement();
458  }
459 
461  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& operator=(
462  const SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& it) {
463  m_pElement = it.m_pElement;
464  return *this;
465  }
466 
468  bool operator==(const SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& it) const {
469  return m_pElement == it.m_pElement;
470  }
471 
473  bool operator!=(const SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& it) const {
474  return m_pElement != it.m_pElement;
475  }
476 
477 private:
478  typename SortedSequence<KEY, INFO, CMP>::Element* succElement() const {
479  OGDF_ASSERT(valid());
480  return (m_pElement->m_next[0]->m_height > 0) ? m_pElement->m_next[0] : nullptr;
481  }
482 
483  typename SortedSequence<KEY, INFO, CMP>::Element* predElement() const {
484  OGDF_ASSERT(valid());
485  return (m_pElement->m_prev[0]->m_height > 0) ? m_pElement->m_prev[0] : nullptr;
486  }
487 };
488 
489 template<class KEY, class INFO, class CMP>
490 SortedSequence<KEY, INFO, CMP>::SortedSequence(std::initializer_list<std::pair<KEY, INFO>> initList)
491  : SortedSequence() {
492  for (const auto& p : initList) {
493  insert(p.first, p.second);
494  }
495 }
496 
497 template<class KEY, class INFO, class CMP>
498 SortedSequence<KEY, INFO, CMP>::SortedSequence(const SortedSequence<KEY, INFO, CMP>& S)
499  : m_comparer(S.m_comparer), m_rng(randomSeed()), m_randomBits(0, 1) {
500  initEmpty();
501 
502  iterator it = m_dummy;
503  for (Element* pS = S.m_dummy->m_next[0]; pS != S.m_dummy; pS = pS->m_next[0]) {
504  it = insertAfter(it, pS->m_key, pS->m_info);
505  }
506 }
507 
508 template<class KEY, class INFO, class CMP>
509 SortedSequence<KEY, INFO, CMP>::SortedSequence(SortedSequence<KEY, INFO, CMP>&& S)
510  : m_comparer(S.m_comparer)
511  , m_size(S.m_size)
512  , m_height(S.m_height)
513  , m_realHeight(S.m_realHeight)
514  , m_rng(randomSeed())
515  , m_randomBits(0, 1) {
516  // move all elements to this sequence
517  m_dummy = S.m_dummy;
518 
519  // initalize S with an empty sequence
520  S.initEmpty();
521 }
522 
523 template<class KEY, class INFO, class CMP>
524 SortedSequence<KEY, INFO, CMP>& SortedSequence<KEY, INFO, CMP>::operator=(
525  const SortedSequence<KEY, INFO, CMP>& S) {
526  clear();
527 
528  iterator it = m_dummy;
529  for (Element* pS = S.m_dummy->m_next[0]; pS != S.m_dummy; pS = pS->m_next[0]) {
530  it = insertAfter(it, pS->m_key, pS->m_info);
531  }
532 
533  return *this;
534 }
535 
536 template<class KEY, class INFO, class CMP>
537 SortedSequence<KEY, INFO, CMP>& SortedSequence<KEY, INFO, CMP>::operator=(
538  SortedSequence<KEY, INFO, CMP>&& S) {
539  // clear this sequence
540  Element* item = m_dummy->m_next[0];
541  while (item != m_dummy) {
542  Element* old = item;
543  item = item->m_next[0];
544  delete old;
545  }
546  delete m_dummy;
547 
548  // move elements from S to this sequence
549  m_comparer = S.m_comparer;
550  m_size = S.m_size;
551  m_height = S.m_height;
552  m_realHeight = S.m_realHeight;
553  m_dummy = S.m_dummy;
554 
555  // make S the empty sequence
556  S.initEmpty();
557 
558  return *this;
559 }
560 
561 template<class KEY, class INFO, class CMP>
562 bool SortedSequence<KEY, INFO, CMP>::operator==(const SortedSequence<KEY, INFO, CMP>& S) {
563  if (m_size != S.m_size) {
564  return false;
565  }
566 
567  Element *p = m_dummy->m_next[0], *pS = S.m_dummy->m_next[0];
568  while (p != m_dummy) {
569  if (!m_comparer.equal(p->m_key, pS->m_key)) {
570  return false;
571  }
572  p = p->m_next[0];
573  pS = pS->m_next[0];
574  }
575 
576  return true;
577 }
578 
579 template<class KEY, class INFO, class CMP>
580 const typename SortedSequence<KEY, INFO, CMP>::Element* SortedSequence<KEY, INFO, CMP>::_lookup(
581  const KEY& key) const {
582  int h = m_height - 1;
583  Element** pElement = m_dummy->m_next;
584 
585  while (true) {
586  if (pElement[h] != m_dummy && m_comparer.less(pElement[h]->m_key, key)) {
587  pElement = pElement[h]->m_next;
588  } else if (--h < 0) {
589  if (pElement[0] != m_dummy && m_comparer.equal(pElement[0]->m_key, key)) {
590  return pElement[0];
591  }
592  return nullptr;
593  }
594  }
595 }
596 
597 template<class KEY, class INFO, class CMP>
598 typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::lookup(
599  const KEY& key) {
600  return iterator(const_cast<Element*>(_lookup(key)));
601 }
602 
603 template<class KEY, class INFO, class CMP>
604 typename SortedSequence<KEY, INFO, CMP>::const_iterator SortedSequence<KEY, INFO, CMP>::lookup(
605  const KEY& key) const {
606  return const_iterator(_lookup(key));
607 }
608 
609 template<class KEY, class INFO, class CMP>
610 const typename SortedSequence<KEY, INFO, CMP>::Element* SortedSequence<KEY, INFO, CMP>::_locate(
611  const KEY& key) const {
612  int h = m_height - 1;
613  Element** pElement = m_dummy->m_next;
614 
615  while (true) {
616  if (pElement[h] != m_dummy && m_comparer.less(pElement[h]->m_key, key)) {
617  pElement = pElement[h]->m_next;
618  } else if (--h < 0) {
619  Element* p = (pElement[0] != m_dummy) ? pElement[0] : nullptr;
620  return p;
621  }
622  }
623 }
624 
625 template<class KEY, class INFO, class CMP>
626 typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::locate(
627  const KEY& key) {
628  return iterator(const_cast<Element*>(_locate(key)));
629 }
630 
631 template<class KEY, class INFO, class CMP>
632 typename SortedSequence<KEY, INFO, CMP>::const_iterator SortedSequence<KEY, INFO, CMP>::locate(
633  const KEY& key) const {
634  return const_iterator(_locate(key));
635 }
636 
637 template<class KEY, class INFO, class CMP>
638 void SortedSequence<KEY, INFO, CMP>::grow(int newHeight) {
639  if (newHeight > m_realHeight) {
640  m_realHeight = newHeight;
641  m_dummy->grow(newHeight);
642  }
643 
644  for (int i = newHeight; i-- > m_height;) {
645  m_dummy->m_next[i] = m_dummy;
646  m_dummy->m_prev[i] = m_dummy;
647  }
648  m_height = newHeight;
649 }
650 
651 template<class KEY, class INFO, class CMP>
652 int SortedSequence<KEY, INFO, CMP>::randomHeightAndGrow() {
653  int h = 1;
654  while (m_randomBits(m_rng) == 1) {
655  h++;
656  }
657 
658  if (h > m_height) {
659  grow(h);
660  }
661 
662  return h;
663 }
664 
665 template<class KEY, class INFO, class CMP>
666 typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::insert(
667  const KEY& key, const INFO& info) {
668  int h = m_height - 1;
669  Element* pCurrent = m_dummy;
670 
671  while (true) {
672  if (pCurrent->m_next[h] != m_dummy && m_comparer.less(pCurrent->m_next[h]->m_key, key)) {
673  pCurrent = pCurrent->m_next[h];
674 
675  } else {
676  if (--h < 0) {
677  // found element?
678  if (pCurrent->m_next[0] != m_dummy
679  && m_comparer.equal(pCurrent->m_next[0]->m_key, key)) {
680  pCurrent->m_next[0]->m_info = info;
681  return iterator(pCurrent->m_next[0]);
682  }
683  break;
684  }
685  }
686  }
687 
688  // add new element (key,inf)
689  m_size++;
690 
691  int nh = randomHeightAndGrow();
692 
693  Element* pNewElement = new Element(key, info, nh);
694  insertElementAfterElement(pNewElement, pCurrent);
695 
696  return iterator(pNewElement);
697 }
698 
699 template<class KEY, class INFO, class CMP>
700 void SortedSequence<KEY, INFO, CMP>::del(const KEY& key) {
701  iterator it = lookup(key);
702  if (it.valid()) {
703  delItem(it);
704  }
705 }
706 
707 template<class KEY, class INFO, class CMP>
708 typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::insertAfter(
709  iterator it, const KEY& key, const INFO& info) {
710  m_size++;
711 
712  int nh = randomHeightAndGrow();
713 
714  Element* pNewElement = new Element(key, info, nh);
715  insertElementAfterElement(pNewElement, it.m_pElement);
716 
717  return pNewElement;
718 }
719 
720 template<class KEY, class INFO, class CMP>
721 void SortedSequence<KEY, INFO, CMP>::insertElementAfterElement(Element* p, Element* q) {
722  OGDF_ASSERT(p->m_height <= m_height);
723 
724  for (int h = 0; h < p->m_height; ++h) {
725  while (q != m_dummy && q->m_height <= h) {
726  q = q->m_prev[h - 1];
727  }
728 
729  Element* r = q->m_next[h];
730  p->m_next[h] = r;
731  p->m_prev[h] = q;
732  q->m_next[h] = r->m_prev[h] = p;
733  }
734 }
735 
736 template<class KEY, class INFO, class CMP>
737 void SortedSequence<KEY, INFO, CMP>::reverseElements(Element* p, Element* q) {
738  while (p != q) {
739  Element* r = p;
740  p = p->m_next[0];
741  removeElement(r);
742  insertElementAfterElement(r, q);
743  }
744 }
745 
746 template<class KEY, class INFO, class CMP>
747 void SortedSequence<KEY, INFO, CMP>::removeElement(Element* p) {
748  OGDF_ASSERT(p != nullptr);
749  OGDF_ASSERT(p != m_dummy);
750 
751  for (int h = 0; h < p->m_height; ++h) {
752  Element *pPred = p->m_prev[h], *pSucc = p->m_next[h];
753  pPred->m_next[h] = pSucc;
754  pSucc->m_prev[h] = pPred;
755  }
756 }
757 
758 template<class KEY, class INFO, class CMP>
759 void SortedSequence<KEY, INFO, CMP>::delItem(typename SortedSequence<KEY, INFO, CMP>::iterator it) {
760  Element* p = it.m_pElement;
761  removeElement(p);
762 
763  m_size--;
764  delete p;
765 }
766 
767 template<class KEY, class INFO, class CMP>
768 inline typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::begin() {
769  return (m_dummy->m_next[0] != m_dummy) ? m_dummy->m_next[0] : nullptr;
770 }
771 
772 template<class KEY, class INFO, class CMP>
773 inline typename SortedSequence<KEY, INFO, CMP>::const_iterator
774 SortedSequence<KEY, INFO, CMP>::begin() const {
775  return (m_dummy->m_next[0] != m_dummy) ? m_dummy->m_next[0] : 0;
776 }
777 
778 template<class KEY, class INFO, class CMP>
779 inline typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::end() {
780  return SortedSequence<KEY, INFO, CMP>::iterator();
781 }
782 
783 template<class KEY, class INFO, class CMP>
784 inline typename SortedSequence<KEY, INFO, CMP>::const_iterator
785 SortedSequence<KEY, INFO, CMP>::end() const {
786  return SortedSequence<KEY, INFO, CMP>::const_iterator();
787 }
788 
789 template<class KEY, class INFO, class CMP>
790 inline typename SortedSequence<KEY, INFO, CMP>::reverse_iterator
791 SortedSequence<KEY, INFO, CMP>::rbegin() {
792  return (m_dummy->m_prev[0] != m_dummy) ? m_dummy->m_prev[0] : 0;
793 }
794 
795 template<class KEY, class INFO, class CMP>
796 inline typename SortedSequence<KEY, INFO, CMP>::const_reverse_iterator
797 SortedSequence<KEY, INFO, CMP>::rbegin() const {
798  return (m_dummy->m_prev[0] != m_dummy) ? m_dummy->m_prev[0] : 0;
799 }
800 
801 template<class KEY, class INFO, class CMP>
802 inline typename SortedSequence<KEY, INFO, CMP>::reverse_iterator SortedSequence<KEY, INFO, CMP>::rend() {
803  return SortedSequence<KEY, INFO, CMP>::iterator();
804 }
805 
806 template<class KEY, class INFO, class CMP>
807 inline typename SortedSequence<KEY, INFO, CMP>::const_reverse_iterator
808 SortedSequence<KEY, INFO, CMP>::rend() const {
809  return SortedSequence<KEY, INFO, CMP>::const_iterator();
810 }
811 
812 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::SortedSequenceIteratorBase::valid
bool valid() const
Returns true if the iterator points to an element.
Definition: SortedSequence.h:422
ogdf::SortedSequence::Element::Element
Element(int height)
Creates a dummy (stop) element with given height.
Definition: SortedSequence.h:93
ogdf::SortedSequence::grow
void grow(int newHeight)
Definition: SortedSequence.h:638
ogdf::SortedSequence::m_height
int m_height
current height of head/tail.
Definition: SortedSequence.h:350
ogdf::SortedSequence::clear
void clear()
Removes all elements from the sorted sequence.
Definition: SortedSequence.h:274
ogdf::SortedSequence::maxItem
reverse_iterator maxItem()
Returns a reverse iterator to the element with maximal key if the sequence is not empty,...
Definition: SortedSequence.h:248
ogdf::InsufficientMemoryException
Exception thrown when not enough memory is available to execute an algorithm.
Definition: exceptions.h:205
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:54
ogdf::SortedSequence::randomHeightAndGrow
int randomHeightAndGrow()
Definition: SortedSequence.h:652
ogdf::SortedSequence::reverseItems
void reverseItems(iterator itBegin, iterator itEnd)
Reverses the items in the subsequence from itBegin to itEnd (inclusive).
Definition: SortedSequence.h:340
ogdf::SortedSequenceIteratorBase::succ
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > succ() const
Returns an iterator pointing to the next element in the sequence.
Definition: SortedSequence.h:451
ogdf::SortedSequence::empty
bool empty() const
Returns true if the sequence is empty, false otherwise.
Definition: SortedSequence.h:169
ogdf::SortedSequence::Element
Internal structure to hold the items and internal forward/backward pointers of the skiplist.
Definition: SortedSequence.h:73
ogdf::SortedSequenceIteratorBase::predElement
SortedSequence< KEY, INFO, CMP >::Element * predElement() const
Definition: SortedSequence.h:483
ogdf::SortedSequence::insertElementAfterElement
void insertElementAfterElement(Element *p, Element *q)
Definition: SortedSequence.h:721
ogdf::SortedSequenceIteratorBase::Element
typename std::conditional< isConst, const typename SortedSequence< KEY, INFO, CMP >::Element, typename SortedSequence< KEY, INFO, CMP >::Element >::type Element
Definition: SortedSequence.h:387
ogdf::SortedSequence::operator!=
bool operator!=(const SortedSequence< KEY, INFO, CMP > &S)
Returns false if the keys stored in this sequence equal the keys in S, true otherwise.
Definition: SortedSequence.h:312
ogdf::SortedSequence::m_randomBits
std::uniform_int_distribution m_randomBits
Definition: SortedSequence.h:354
ogdf::SortedSequence::crbegin
const_reverse_iterator crbegin() const
Returns a const reverse iterator pointing to the last element.
Definition: SortedSequence.h:196
ogdf::SortedSequenceIteratorBase::operator==
bool operator==(const SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > &it) const
Equality operator.
Definition: SortedSequence.h:468
ogdf::SortedSequence::const_reverse_iterator
SortedSequenceConstReverseIterator< KEY, INFO, CMP > const_reverse_iterator
The const reverse iterator type for sorted sequences (bidirectional iterator).
Definition: SortedSequence.h:132
ogdf::SortedSequence::delItem
void delItem(iterator it)
Removes the element to which it points from the sequence.
Definition: SortedSequence.h:759
ogdf::SortedSequence::_lookup
const Element * _lookup(const KEY &key) const
Definition: SortedSequence.h:580
ogdf::SortedSequence::begin
iterator begin()
Returns an iterator pointing to the first element.
Definition: SortedSequence.h:768
ogdf::SortedSequence::insert
iterator insert(const KEY &key, const INFO &info)
Updates information for key if contained in sequence, or adds a new element <key, info>.
Definition: SortedSequence.h:666
ogdf::SortedSequenceIteratorBase::SortedSequenceIteratorBase
SortedSequenceIteratorBase(const SortedSequenceIteratorBase< KEY, INFO, CMP, isArgConst, isArgReverse > &it)
Copy constructor.
Definition: SortedSequence.h:399
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
ogdf::SortedSequenceIteratorBase::info
std::conditional< isConst, const INFO, INFO >::type & info() const
Returns the info of the sequence element pointed to.
Definition: SortedSequence.h:416
ogdf::SortedSequenceIteratorBase::pred
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > pred() const
Returns an iterator pointing to the previous element in the sequence.
Definition: SortedSequence.h:456
ogdf::SortedSequenceIteratorBase::operator--
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > operator--(int)
Moves the iterator one item backward (postfix notation)
Definition: SortedSequence.h:444
ogdf::SortedSequence::Element::m_info
INFO m_info
stores the associated information.
Definition: SortedSequence.h:75
ogdf::SortedSequence::minItem
const_iterator minItem() const
Returns a const-iterator to the element with minimal key if the sequence is not empty,...
Definition: SortedSequence.h:241
ogdf::SortedSequence::Element::m_prev
Element ** m_prev
array of predecessor elements.
Definition: SortedSequence.h:79
ogdf::SortedSequence::minItem
iterator minItem()
Returns an iterator to the element with minimal key if the sequence is not empty, an invalid iterator...
Definition: SortedSequence.h:234
ogdf::SortedSequenceIteratorBase::SortedSequenceIteratorBase
SortedSequenceIteratorBase(const SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > &it)
Copy constructor.
Definition: SortedSequence.h:405
r
int r[]
Definition: hierarchical-ranking.cpp:8
ogdf::SortedSequence::operator==
bool operator==(const SortedSequence< KEY, INFO, CMP > &S)
Returns true if the keys stored in this sequence equal the keys in S, false otherwise.
Definition: SortedSequence.h:562
ogdf::SortedSequence::lookup
iterator lookup(const KEY &key)
Returns an iterator to the element with key key, or a null iterator if no such element exists.
Definition: SortedSequence.h:598
ogdf::SortedSequence::_locate
const Element * _locate(const KEY &key) const
Definition: SortedSequence.h:610
ogdf::SortedSequence::const_iterator
SortedSequenceConstIterator< KEY, INFO, CMP > const_iterator
The const-iterator type for sorted sequences (bidirectional iterator).
Definition: SortedSequence.h:128
backward::Color::type
type
Definition: backward.hpp:1716
OGDF_THROW
#define OGDF_THROW(CLASS)
Replacement for throw.
Definition: exceptions.h:70
ogdf::SortedSequence::m_comparer
CMP m_comparer
Definition: SortedSequence.h:347
ogdf::SortedSequence::rbegin
reverse_iterator rbegin()
Returns a reverse iterator pointing to the last element.
Definition: SortedSequence.h:791
ogdf::SortedSequence::m_dummy
Element * m_dummy
dummy element representing the head and tail of the skiplist.
Definition: SortedSequence.h:349
ogdf::SortedSequenceIteratorBase::SortedSequenceIteratorBase
SortedSequenceIteratorBase()
Creates an invalid (null-) iterator.
Definition: SortedSequence.h:395
ogdf::SortedSequence::removeElement
void removeElement(Element *p)
Definition: SortedSequence.h:747
ogdf::SortedSequence::Element::grow
void grow(int newHeight)
Increases the element's height to newHeight.
Definition: SortedSequence.h:107
ogdf::SortedSequence::insertAfter
iterator insertAfter(iterator it, const KEY &key, const INFO &info)
Adds a new element <key, info> after element it.
Definition: SortedSequence.h:708
ogdf::SortedSequenceIteratorBase::m_pElement
Element * m_pElement
Definition: SortedSequence.h:388
ogdf::SortedSequence::~SortedSequence
~SortedSequence()
Destructor.
Definition: SortedSequence.h:153
ogdf::SortedSequence::cend
const_iterator cend() const
Returns a const-iterator pointing to one past the last element.
Definition: SortedSequence.h:187
ogdf::SortedSequence::Element::Element
Element(const KEY &key, const INFO &info, int height)
Creates a skiplist element for(key,info) and given height.
Definition: SortedSequence.h:82
ogdf::SortedSequence::Element::m_next
Element ** m_next
array of successor elements.
Definition: SortedSequence.h:78
ogdf::SortedSequence::reverse_iterator
SortedSequenceReverseIterator< KEY, INFO, CMP > reverse_iterator
The reverse iterator type for sorted sequences (bidirectional iterator).
Definition: SortedSequence.h:130
ogdf::SortedSequence::maxItem
const_reverse_iterator maxItem() const
Returns a const reverse iterator to the element with maximal key if the sequence is not empty,...
Definition: SortedSequence.h:255
ogdf::SortedSequence::iterator
SortedSequenceIterator< KEY, INFO, CMP > iterator
The iterator type for sorted sequences (bidirectional iterator).
Definition: SortedSequence.h:126
ogdf::SortedSequence::rend
reverse_iterator rend()
Returns a reverse iterator pointing to one before the first element.
Definition: SortedSequence.h:802
ogdf::SortedSequence::SortedSequence
SortedSequence(const CMP &comparer=CMP())
Constructs an initially empty sorted sequence.
Definition: SortedSequence.h:135
ogdf::randomSeed
long unsigned int randomSeed()
Returns a random value suitable as initial seed for a random number engine.
ogdf::SortedSequence::del
void del(const KEY &key)
Removes the element with key key (if such an element exists).
Definition: SortedSequence.h:700
ogdf::SortedSequence::initEmpty
void initEmpty()
Definition: SortedSequence.h:356
Reverse.h
Implementation of the Reverse class for the reverse iteration of containers.
ogdf::SortedSequenceIteratorBase::key
const KEY & key() const
Returns the key of the sequence element pointed to.
Definition: SortedSequence.h:410
ogdf::SortedSequenceIteratorBase::operator++
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > & operator++()
Move the iterator one item forward (prefix notation)
Definition: SortedSequence.h:425
ogdf::SortedSequenceIteratorBase::operator!=
bool operator!=(const SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > &it) const
Inequality operator.
Definition: SortedSequence.h:473
ogdf::SortedSequence::end
iterator end()
Returns an iterator pointing to one past the last element.
Definition: SortedSequence.h:779
ogdf::SortedSequence::operator=
SortedSequence< KEY, INFO, CMP > & operator=(const SortedSequence< KEY, INFO, CMP > &S)
Assignment operator.
Definition: SortedSequence.h:524
ogdf::SortedSequenceIteratorBase::operator=
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > & operator=(const SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > &it)
Assignment operator.
Definition: SortedSequence.h:461
ogdf::SortedSequenceIteratorBase
Iterators for sorted sequences.
Definition: SortedSequence.h:43
ogdf::SortedSequence::Element::m_height
int m_height
the height of the skiplist element.
Definition: SortedSequence.h:76
ogdf::SortedSequence::Element::~Element
~Element()
Destructor.
Definition: SortedSequence.h:101
ogdf::SortedSequence::m_realHeight
int m_realHeight
actual height of head/tail arrays.
Definition: SortedSequence.h:351
ogdf::SortedSequence::locate
iterator locate(const KEY &key)
Returns an iterator to the element < k1, i1 > such that k1 is minimal with k1 ≥ key,...
Definition: SortedSequence.h:626
ogdf::SortedSequenceIteratorBase::succElement
SortedSequence< KEY, INFO, CMP >::Element * succElement() const
Definition: SortedSequence.h:478
ogdf::SortedSequenceIteratorBase::SortedSequenceIteratorBase
SortedSequenceIteratorBase(Element *pElement)
Creates an iterator pointing to pElement.
Definition: SortedSequence.h:391
ogdf::SortedSequence
Maintains a sequence of (key,info) pairs sorted by key.
Definition: SortedSequence.h:66
ogdf::SortedSequence::size
int size() const
Returns the current size of the sequence, i.e., the number of stored elements.
Definition: SortedSequence.h:166
ogdf::SortedSequenceIteratorBase::operator--
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > & operator--()
Moves the iterator one item backward (prefix notation)
Definition: SortedSequence.h:438
ogdf::SortedSequence::crend
const_reverse_iterator crend() const
Returns a const reverse iterator pointing to one before the first element.
Definition: SortedSequence.h:205
ogdf::SortedSequence::m_rng
std::minstd_rand m_rng
Random number generator.
Definition: SortedSequence.h:353
ogdf::SortedSequence::reverseElements
void reverseElements(Element *p, Element *q)
Definition: SortedSequence.h:737
comparer.h
Declarations for Comparer objects.
ogdf::SortedSequence::m_size
int m_size
number of elements stored in the sequence.
Definition: SortedSequence.h:348
ogdf::SortedSequence::cbegin
const_iterator cbegin() const
Returns a const-iterator pointing to the first element.
Definition: SortedSequence.h:178
ogdf::SortedSequenceIteratorBase::operator++
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > operator++(int)
Moves the iterator one item forward (postfix notation)
Definition: SortedSequence.h:431
memory.h
Declaration of memory manager for allocating small pieces of memory.
ogdf::SortedSequence::Element::m_key
KEY m_key
stores the key.
Definition: SortedSequence.h:74