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/basic.h>
35 #include <ogdf/basic/comparer.h>
36 #include <ogdf/basic/exceptions.h>
37 #include <ogdf/basic/memory.h>
38 
39 #include <cstdlib>
40 #include <initializer_list>
41 #include <random>
42 #include <type_traits>
43 #include <utility>
44 
45 namespace ogdf {
46 
47 template<class KEY, class INFO, class CMP, bool isConst, bool isReverse>
48 class SortedSequenceIteratorBase;
49 
50 template<class KEY, class INFO, class CMP>
51 using SortedSequenceIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, false, false>;
52 
53 template<class KEY, class INFO, class CMP>
54 using SortedSequenceConstIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, true, false>;
55 
56 template<class KEY, class INFO, class CMP>
57 using SortedSequenceReverseIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, false, true>;
58 
59 template<class KEY, class INFO, class CMP>
60 using SortedSequenceConstReverseIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, true, true>;
61 
63 
70 template<class KEY, class INFO, class CMP = StdComparer<KEY>>
71 class SortedSequence {
72  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, false, false>;
73  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, true, false>;
74  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, false, true>;
75  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, true, true>;
76 
78  struct Element {
79  KEY m_key;
80  INFO m_info;
81  int m_height;
82 
83  Element** m_next;
84  Element** m_prev;
85 
87  Element(const KEY& key, const INFO& info, int height)
88  : m_key(key), m_info(info), m_height(height) {
89  m_next = (Element**)malloc(height * sizeof(Element*));
90  m_prev = (Element**)malloc(height * sizeof(Element*));
91  }
92 
94 
98  Element(int height) : m_height(0) {
99  m_next = (Element**)malloc(height * sizeof(Element*));
100  m_prev = (Element**)malloc(height * sizeof(Element*));
101  }
102 
103  Element(const Element&) = delete;
104 
106  ~Element() {
107  free(m_prev);
108  free(m_next);
109  }
110 
112  void grow(int newHeight) {
113  Element** p = static_cast<Element**>(realloc(m_next, newHeight * sizeof(Element*)));
114  if (p == nullptr) {
115  OGDF_THROW(InsufficientMemoryException);
116  }
117  m_next = p;
118 
119  p = static_cast<Element**>(realloc(m_prev, newHeight * sizeof(Element*)));
120  if (p == nullptr) {
121  OGDF_THROW(InsufficientMemoryException);
122  }
123  m_prev = p;
124  }
125 
126  OGDF_NEW_DELETE
127  };
128 
129 public:
131  using iterator = SortedSequenceIterator<KEY, INFO, CMP>;
133  using const_iterator = SortedSequenceConstIterator<KEY, INFO, CMP>;
135  using reverse_iterator = SortedSequenceReverseIterator<KEY, INFO, CMP>;
137  using const_reverse_iterator = SortedSequenceConstReverseIterator<KEY, INFO, CMP>;
138 
140  SortedSequence(const CMP& comparer = CMP())
141  : m_comparer(comparer), m_rng(randomSeed()), m_randomBits(0, 1) {
142  initEmpty();
143  }
144 
146  SortedSequence(std::initializer_list<std::pair<KEY, INFO>> initList);
147 
149  SortedSequence(const SortedSequence<KEY, INFO, CMP>& S);
150 
152 
155  SortedSequence(SortedSequence<KEY, INFO, CMP>&& S);
156 
158  ~SortedSequence() {
159  clear();
160  delete m_dummy;
161  }
162 
168 
171  int size() const { return m_size; }
172 
174  bool empty() const { return m_size == 0; }
175 
177  iterator begin();
178 
180  const_iterator begin() const;
181 
183  const_iterator cbegin() const { return begin(); }
184 
186  iterator end();
187 
189  const_iterator end() const;
190 
192  const_iterator cend() const { return end(); }
193 
195  reverse_iterator rbegin();
196 
198  const_reverse_iterator rbegin() const;
199 
201  const_reverse_iterator crbegin() const { return rbegin(); }
202 
204  reverse_iterator rend();
205 
207  const_reverse_iterator rend() const;
208 
210  const_reverse_iterator crend() const { return rend(); }
211 
216 
219  iterator lookup(const KEY& key);
220 
222  const_iterator lookup(const KEY& key) const;
223 
227  iterator locate(const KEY& key);
228 
232  const_iterator locate(const KEY& key) const;
233 
236 
239  iterator minItem() { return begin(); }
240 
243 
246  const_iterator minItem() const { return begin(); }
247 
250 
253  reverse_iterator maxItem() { return rbegin(); }
254 
257 
260  const_reverse_iterator maxItem() const { return rbegin(); }
261 
263 
267 
270  iterator insert(const KEY& key, const INFO& info);
271 
273  void del(const KEY& key);
274 
276  void delItem(iterator it);
277 
279  void clear() {
280  Element* item = m_dummy->m_next[0];
281  while (item != m_dummy) {
282  Element* old = item;
283  item = item->m_next[0];
284  delete old;
285  }
286  m_size = 0;
287  m_height = 1;
288  m_dummy->m_next[0] = m_dummy->m_prev[0] = m_dummy;
289  }
290 
292 
296 
299  SortedSequence<KEY, INFO, CMP>& operator=(const SortedSequence<KEY, INFO, CMP>& S);
300 
302 
305  SortedSequence<KEY, INFO, CMP>& operator=(SortedSequence<KEY, INFO, CMP>&& S);
306 
308 
311  bool operator==(const SortedSequence<KEY, INFO, CMP>& S);
312 
314 
317  bool operator!=(const SortedSequence<KEY, INFO, CMP>& S) { return !operator==(S); }
318 
320 
324 
327 
332  iterator insertAfter(iterator it, const KEY& key, const INFO& info);
333 
335 
345  void reverseItems(iterator itBegin, iterator itEnd) {
346  reverseElements(itBegin.m_pElement, itEnd.m_pElement);
347  }
348 
350 
351 private:
352  CMP m_comparer;
353  int m_size;
354  Element* m_dummy;
355  int m_height;
356  int m_realHeight;
357 
358  std::minstd_rand m_rng;
359  std::uniform_int_distribution<> m_randomBits;
360 
361  void initEmpty() {
362  m_size = 0;
363  m_realHeight = 5;
364  m_height = 1;
365 
366  m_dummy = new Element(m_realHeight);
367  m_dummy->m_next[0] = m_dummy;
368  m_dummy->m_prev[0] = m_dummy;
369  }
370 
371  int randomHeightAndGrow();
372  void grow(int newHeight);
373 
374  const Element* _lookup(const KEY& key) const;
375  const Element* _locate(const KEY& key) const;
376 
377  void removeElement(Element* p);
378  void insertElementAfterElement(Element* p, Element* q);
379  void reverseElements(Element* p, Element* q);
380 };
381 
383 template<class KEY, class INFO, class CMP, bool isConst, bool isReverse>
384 class SortedSequenceIteratorBase {
385  friend class SortedSequence<KEY, INFO, CMP>;
386  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, !isConst, isReverse>;
387  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, !isReverse>;
388  friend class SortedSequenceIteratorBase<KEY, INFO, CMP, !isConst, !isReverse>;
389 
390  using Element =
391  typename std::conditional<isConst, const typename SortedSequence<KEY, INFO, CMP>::Element,
392  typename SortedSequence<KEY, INFO, CMP>::Element>::type;
393  Element* m_pElement;
394 
396  SortedSequenceIteratorBase(Element* pElement) : m_pElement(pElement) { }
397 
398 public:
400  SortedSequenceIteratorBase() : m_pElement(nullptr) { }
401 
403  template<bool isArgConst, typename std::enable_if<isConst || !isArgConst, int>::type = 0, bool isArgReverse>
404  SortedSequenceIteratorBase(
405  const SortedSequenceIteratorBase<KEY, INFO, CMP, isArgConst, isArgReverse>& it)
406  : m_pElement(it.m_pElement) { }
407 
409  // gcc9 complains since it cannot match the templated constructor above (-Werror=deprecated-copy).
410  SortedSequenceIteratorBase(
411  const SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& it)
412  : m_pElement(it.m_pElement) { }
413 
415  const KEY& key() const {
416  OGDF_ASSERT(valid());
417  return m_pElement->m_key;
418  }
419 
421  typename std::conditional<isConst, const INFO, INFO>::type& info() const {
422  OGDF_ASSERT(valid());
423  return m_pElement->m_info;
424  }
425 
427  bool valid() const { return m_pElement != nullptr; }
428 
430  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& operator++() {
431  m_pElement = isReverse ? predElement() : succElement();
432  return *this;
433  }
434 
436  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> operator++(int) {
437  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> it = *this;
438  m_pElement = isReverse ? predElement() : succElement();
439  return it;
440  }
441 
443  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& operator--() {
444  m_pElement = isReverse ? succElement() : predElement();
445  return *this;
446  }
447 
449  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> operator--(int) {
450  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> it = *this;
451  m_pElement = isReverse ? succElement() : predElement();
452  return it;
453  }
454 
456  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> succ() const {
457  return isReverse ? predElement() : succElement();
458  }
459 
461  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> pred() const {
462  return isReverse ? succElement() : predElement();
463  }
464 
466  SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& operator=(
467  const SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& it) {
468  m_pElement = it.m_pElement;
469  return *this;
470  }
471 
473  bool operator==(const SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& it) const {
474  return m_pElement == it.m_pElement;
475  }
476 
478  bool operator!=(const SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& it) const {
479  return m_pElement != it.m_pElement;
480  }
481 
482 private:
483  typename SortedSequence<KEY, INFO, CMP>::Element* succElement() const {
484  OGDF_ASSERT(valid());
485  return (m_pElement->m_next[0]->m_height > 0) ? m_pElement->m_next[0] : nullptr;
486  }
487 
488  typename SortedSequence<KEY, INFO, CMP>::Element* predElement() const {
489  OGDF_ASSERT(valid());
490  return (m_pElement->m_prev[0]->m_height > 0) ? m_pElement->m_prev[0] : nullptr;
491  }
492 };
493 
494 template<class KEY, class INFO, class CMP>
495 SortedSequence<KEY, INFO, CMP>::SortedSequence(std::initializer_list<std::pair<KEY, INFO>> initList)
496  : SortedSequence() {
497  for (const auto& p : initList) {
498  insert(p.first, p.second);
499  }
500 }
501 
502 template<class KEY, class INFO, class CMP>
503 SortedSequence<KEY, INFO, CMP>::SortedSequence(const SortedSequence<KEY, INFO, CMP>& S)
504  : m_comparer(S.m_comparer), m_rng(randomSeed()), m_randomBits(0, 1) {
505  initEmpty();
506 
507  iterator it = m_dummy;
508  for (Element* pS = S.m_dummy->m_next[0]; pS != S.m_dummy; pS = pS->m_next[0]) {
509  it = insertAfter(it, pS->m_key, pS->m_info);
510  }
511 }
512 
513 template<class KEY, class INFO, class CMP>
514 SortedSequence<KEY, INFO, CMP>::SortedSequence(SortedSequence<KEY, INFO, CMP>&& S)
515  : m_comparer(S.m_comparer)
516  , m_size(S.m_size)
517  , m_height(S.m_height)
518  , m_realHeight(S.m_realHeight)
519  , m_rng(randomSeed())
520  , m_randomBits(0, 1) {
521  // move all elements to this sequence
522  m_dummy = S.m_dummy;
523 
524  // initalize S with an empty sequence
525  S.initEmpty();
526 }
527 
528 template<class KEY, class INFO, class CMP>
529 SortedSequence<KEY, INFO, CMP>& SortedSequence<KEY, INFO, CMP>::operator=(
530  const SortedSequence<KEY, INFO, CMP>& S) {
531  clear();
532 
533  iterator it = m_dummy;
534  for (Element* pS = S.m_dummy->m_next[0]; pS != S.m_dummy; pS = pS->m_next[0]) {
535  it = insertAfter(it, pS->m_key, pS->m_info);
536  }
537 
538  return *this;
539 }
540 
541 template<class KEY, class INFO, class CMP>
542 SortedSequence<KEY, INFO, CMP>& SortedSequence<KEY, INFO, CMP>::operator=(
543  SortedSequence<KEY, INFO, CMP>&& S) {
544  // clear this sequence
545  Element* item = m_dummy->m_next[0];
546  while (item != m_dummy) {
547  Element* old = item;
548  item = item->m_next[0];
549  delete old;
550  }
551  delete m_dummy;
552 
553  // move elements from S to this sequence
554  m_comparer = S.m_comparer;
555  m_size = S.m_size;
556  m_height = S.m_height;
557  m_realHeight = S.m_realHeight;
558  m_dummy = S.m_dummy;
559 
560  // make S the empty sequence
561  S.initEmpty();
562 
563  return *this;
564 }
565 
566 template<class KEY, class INFO, class CMP>
567 bool SortedSequence<KEY, INFO, CMP>::operator==(const SortedSequence<KEY, INFO, CMP>& S) {
568  if (m_size != S.m_size) {
569  return false;
570  }
571 
572  Element *p = m_dummy->m_next[0], *pS = S.m_dummy->m_next[0];
573  while (p != m_dummy) {
574  if (!m_comparer.equal(p->m_key, pS->m_key)) {
575  return false;
576  }
577  p = p->m_next[0];
578  pS = pS->m_next[0];
579  }
580 
581  return true;
582 }
583 
584 template<class KEY, class INFO, class CMP>
585 const typename SortedSequence<KEY, INFO, CMP>::Element* SortedSequence<KEY, INFO, CMP>::_lookup(
586  const KEY& key) const {
587  int h = m_height - 1;
588  Element** pElement = m_dummy->m_next;
589 
590  while (true) {
591  if (pElement[h] != m_dummy && m_comparer.less(pElement[h]->m_key, key)) {
592  pElement = pElement[h]->m_next;
593  } else if (--h < 0) {
594  if (pElement[0] != m_dummy && m_comparer.equal(pElement[0]->m_key, key)) {
595  return pElement[0];
596  }
597  return nullptr;
598  }
599  }
600 }
601 
602 template<class KEY, class INFO, class CMP>
603 typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::lookup(
604  const KEY& key) {
605  return iterator(const_cast<Element*>(_lookup(key)));
606 }
607 
608 template<class KEY, class INFO, class CMP>
609 typename SortedSequence<KEY, INFO, CMP>::const_iterator SortedSequence<KEY, INFO, CMP>::lookup(
610  const KEY& key) const {
611  return const_iterator(_lookup(key));
612 }
613 
614 template<class KEY, class INFO, class CMP>
615 const typename SortedSequence<KEY, INFO, CMP>::Element* SortedSequence<KEY, INFO, CMP>::_locate(
616  const KEY& key) const {
617  int h = m_height - 1;
618  Element** pElement = m_dummy->m_next;
619 
620  while (true) {
621  if (pElement[h] != m_dummy && m_comparer.less(pElement[h]->m_key, key)) {
622  pElement = pElement[h]->m_next;
623  } else if (--h < 0) {
624  Element* p = (pElement[0] != m_dummy) ? pElement[0] : nullptr;
625  return p;
626  }
627  }
628 }
629 
630 template<class KEY, class INFO, class CMP>
631 typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::locate(
632  const KEY& key) {
633  return iterator(const_cast<Element*>(_locate(key)));
634 }
635 
636 template<class KEY, class INFO, class CMP>
637 typename SortedSequence<KEY, INFO, CMP>::const_iterator SortedSequence<KEY, INFO, CMP>::locate(
638  const KEY& key) const {
639  return const_iterator(_locate(key));
640 }
641 
642 template<class KEY, class INFO, class CMP>
643 void SortedSequence<KEY, INFO, CMP>::grow(int newHeight) {
644  if (newHeight > m_realHeight) {
645  m_realHeight = newHeight;
646  m_dummy->grow(newHeight);
647  }
648 
649  for (int i = newHeight; i-- > m_height;) {
650  m_dummy->m_next[i] = m_dummy;
651  m_dummy->m_prev[i] = m_dummy;
652  }
653  m_height = newHeight;
654 }
655 
656 template<class KEY, class INFO, class CMP>
657 int SortedSequence<KEY, INFO, CMP>::randomHeightAndGrow() {
658  int h = 1;
659  while (m_randomBits(m_rng) == 1) {
660  h++;
661  }
662 
663  if (h > m_height) {
664  grow(h);
665  }
666 
667  return h;
668 }
669 
670 template<class KEY, class INFO, class CMP>
671 typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::insert(
672  const KEY& key, const INFO& info) {
673  int h = m_height - 1;
674  Element* pCurrent = m_dummy;
675 
676  while (true) {
677  if (pCurrent->m_next[h] != m_dummy && m_comparer.less(pCurrent->m_next[h]->m_key, key)) {
678  pCurrent = pCurrent->m_next[h];
679 
680  } else {
681  if (--h < 0) {
682  // found element?
683  if (pCurrent->m_next[0] != m_dummy
684  && m_comparer.equal(pCurrent->m_next[0]->m_key, key)) {
685  pCurrent->m_next[0]->m_info = info;
686  return iterator(pCurrent->m_next[0]);
687  }
688  break;
689  }
690  }
691  }
692 
693  // add new element (key,inf)
694  m_size++;
695 
696  int nh = randomHeightAndGrow();
697 
698  Element* pNewElement = new Element(key, info, nh);
699  insertElementAfterElement(pNewElement, pCurrent);
700 
701  return iterator(pNewElement);
702 }
703 
704 template<class KEY, class INFO, class CMP>
705 void SortedSequence<KEY, INFO, CMP>::del(const KEY& key) {
706  iterator it = lookup(key);
707  if (it.valid()) {
708  delItem(it);
709  }
710 }
711 
712 template<class KEY, class INFO, class CMP>
713 typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::insertAfter(
714  iterator it, const KEY& key, const INFO& info) {
715  m_size++;
716 
717  int nh = randomHeightAndGrow();
718 
719  Element* pNewElement = new Element(key, info, nh);
720  insertElementAfterElement(pNewElement, it.m_pElement);
721 
722  return pNewElement;
723 }
724 
725 template<class KEY, class INFO, class CMP>
726 void SortedSequence<KEY, INFO, CMP>::insertElementAfterElement(Element* p, Element* q) {
727  OGDF_ASSERT(p->m_height <= m_height);
728 
729  for (int h = 0; h < p->m_height; ++h) {
730  while (q != m_dummy && q->m_height <= h) {
731  q = q->m_prev[h - 1];
732  }
733 
734  Element* r = q->m_next[h];
735  p->m_next[h] = r;
736  p->m_prev[h] = q;
737  q->m_next[h] = r->m_prev[h] = p;
738  }
739 }
740 
741 template<class KEY, class INFO, class CMP>
742 void SortedSequence<KEY, INFO, CMP>::reverseElements(Element* p, Element* q) {
743  while (p != q) {
744  Element* r = p;
745  p = p->m_next[0];
746  removeElement(r);
747  insertElementAfterElement(r, q);
748  }
749 }
750 
751 template<class KEY, class INFO, class CMP>
752 void SortedSequence<KEY, INFO, CMP>::removeElement(Element* p) {
753  OGDF_ASSERT(p != nullptr);
754  OGDF_ASSERT(p != m_dummy);
755 
756  for (int h = 0; h < p->m_height; ++h) {
757  Element *pPred = p->m_prev[h], *pSucc = p->m_next[h];
758  pPred->m_next[h] = pSucc;
759  pSucc->m_prev[h] = pPred;
760  }
761 }
762 
763 template<class KEY, class INFO, class CMP>
764 void SortedSequence<KEY, INFO, CMP>::delItem(typename SortedSequence<KEY, INFO, CMP>::iterator it) {
765  Element* p = it.m_pElement;
766  removeElement(p);
767 
768  m_size--;
769  delete p;
770 }
771 
772 template<class KEY, class INFO, class CMP>
773 inline typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::begin() {
774  return (m_dummy->m_next[0] != m_dummy) ? m_dummy->m_next[0] : nullptr;
775 }
776 
777 template<class KEY, class INFO, class CMP>
778 inline typename SortedSequence<KEY, INFO, CMP>::const_iterator
779 SortedSequence<KEY, INFO, CMP>::begin() const {
780  return (m_dummy->m_next[0] != m_dummy) ? m_dummy->m_next[0] : 0;
781 }
782 
783 template<class KEY, class INFO, class CMP>
784 inline typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::end() {
785  return SortedSequence<KEY, INFO, CMP>::iterator();
786 }
787 
788 template<class KEY, class INFO, class CMP>
789 inline typename SortedSequence<KEY, INFO, CMP>::const_iterator
790 SortedSequence<KEY, INFO, CMP>::end() const {
791  return SortedSequence<KEY, INFO, CMP>::const_iterator();
792 }
793 
794 template<class KEY, class INFO, class CMP>
795 inline typename SortedSequence<KEY, INFO, CMP>::reverse_iterator
796 SortedSequence<KEY, INFO, CMP>::rbegin() {
797  return (m_dummy->m_prev[0] != m_dummy) ? m_dummy->m_prev[0] : 0;
798 }
799 
800 template<class KEY, class INFO, class CMP>
801 inline typename SortedSequence<KEY, INFO, CMP>::const_reverse_iterator
802 SortedSequence<KEY, INFO, CMP>::rbegin() const {
803  return (m_dummy->m_prev[0] != m_dummy) ? m_dummy->m_prev[0] : 0;
804 }
805 
806 template<class KEY, class INFO, class CMP>
807 inline typename SortedSequence<KEY, INFO, CMP>::reverse_iterator SortedSequence<KEY, INFO, CMP>::rend() {
808  return SortedSequence<KEY, INFO, CMP>::iterator();
809 }
810 
811 template<class KEY, class INFO, class CMP>
812 inline typename SortedSequence<KEY, INFO, CMP>::const_reverse_iterator
813 SortedSequence<KEY, INFO, CMP>::rend() const {
814  return SortedSequence<KEY, INFO, CMP>::const_iterator();
815 }
816 
817 }
ogdf
The namespace for all OGDF objects.
Definition: multilevelmixer.cpp:39
ogdf::SortedSequenceIteratorBase::valid
bool valid() const
Returns true if the iterator points to an element.
Definition: SortedSequence.h:427
ogdf::SortedSequence::Element::Element
Element(int height)
Creates a dummy (stop) element with given height.
Definition: SortedSequence.h:98
ogdf::SortedSequence::grow
void grow(int newHeight)
Definition: SortedSequence.h:643
ogdf::SortedSequence::m_height
int m_height
current height of head/tail.
Definition: SortedSequence.h:355
ogdf::SortedSequence::clear
void clear()
Removes all elements from the sorted sequence.
Definition: SortedSequence.h:279
exceptions.h
Definition of exception classes.
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:253
ogdf::InsufficientMemoryException
Exception thrown when not enough memory is available to execute an algorithm.
Definition: exceptions.h:209
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:66
ogdf::SortedSequence::randomHeightAndGrow
int randomHeightAndGrow()
Definition: SortedSequence.h:657
ogdf::SortedSequence::reverseItems
void reverseItems(iterator itBegin, iterator itEnd)
Reverses the items in the subsequence from itBegin to itEnd (inclusive).
Definition: SortedSequence.h:345
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:456
ogdf::SortedSequence::empty
bool empty() const
Returns true if the sequence is empty, false otherwise.
Definition: SortedSequence.h:174
ogdf::SortedSequence::Element
Internal structure to hold the items and internal forward/backward pointers of the skiplist.
Definition: SortedSequence.h:78
ogdf::SortedSequenceIteratorBase::predElement
SortedSequence< KEY, INFO, CMP >::Element * predElement() const
Definition: SortedSequence.h:488
ogdf::SortedSequence::insertElementAfterElement
void insertElementAfterElement(Element *p, Element *q)
Definition: SortedSequence.h:726
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:392
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:317
ogdf::SortedSequence::m_randomBits
std::uniform_int_distribution m_randomBits
Definition: SortedSequence.h:359
ogdf::SortedSequence::crbegin
const_reverse_iterator crbegin() const
Returns a const reverse iterator pointing to the last element.
Definition: SortedSequence.h:201
ogdf::SortedSequenceIteratorBase::operator==
bool operator==(const SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > &it) const
Equality operator.
Definition: SortedSequence.h:473
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:137
ogdf::SortedSequence::delItem
void delItem(iterator it)
Removes the element to which it points from the sequence.
Definition: SortedSequence.h:764
ogdf::SortedSequence::_lookup
const Element * _lookup(const KEY &key) const
Definition: SortedSequence.h:585
ogdf::SortedSequence::begin
iterator begin()
Returns an iterator pointing to the first element.
Definition: SortedSequence.h:773
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:671
ogdf::SortedSequenceIteratorBase::SortedSequenceIteratorBase
SortedSequenceIteratorBase(const SortedSequenceIteratorBase< KEY, INFO, CMP, isArgConst, isArgReverse > &it)
Copy constructor.
Definition: SortedSequence.h:404
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:85
ogdf::SortedSequenceIteratorBase::info
std::conditional< isConst, const INFO, INFO >::type & info() const
Returns the info of the sequence element pointed to.
Definition: SortedSequence.h:421
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:461
ogdf::SortedSequenceIteratorBase::operator--
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > operator--(int)
Moves the iterator one item backward (postfix notation)
Definition: SortedSequence.h:449
ogdf::SortedSequence::Element::m_info
INFO m_info
stores the associated information.
Definition: SortedSequence.h:80
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:246
ogdf::SortedSequence::Element::m_prev
Element ** m_prev
array of predecessor elements.
Definition: SortedSequence.h:84
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:239
ogdf::SortedSequenceIteratorBase::SortedSequenceIteratorBase
SortedSequenceIteratorBase(const SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > &it)
Copy constructor.
Definition: SortedSequence.h:410
r
int r[]
Definition: hierarchical-ranking.cpp:13
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:567
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:603
ogdf::SortedSequence::_locate
const Element * _locate(const KEY &key) const
Definition: SortedSequence.h:615
ogdf::SortedSequence::const_iterator
SortedSequenceConstIterator< KEY, INFO, CMP > const_iterator
The const-iterator type for sorted sequences (bidirectional iterator).
Definition: SortedSequence.h:133
backward::Color::type
type
Definition: backward.hpp:1716
OGDF_THROW
#define OGDF_THROW(CLASS)
Replacement for throw.
Definition: exceptions.h:74
ogdf::SortedSequence::m_comparer
CMP m_comparer
Definition: SortedSequence.h:352
ogdf::SortedSequence::rbegin
reverse_iterator rbegin()
Returns a reverse iterator pointing to the last element.
Definition: SortedSequence.h:796
ogdf::SortedSequence::m_dummy
Element * m_dummy
dummy element representing the head and tail of the skiplist.
Definition: SortedSequence.h:354
ogdf::SortedSequenceIteratorBase::SortedSequenceIteratorBase
SortedSequenceIteratorBase()
Creates an invalid (null-) iterator.
Definition: SortedSequence.h:400
ogdf::SortedSequence::removeElement
void removeElement(Element *p)
Definition: SortedSequence.h:752
ogdf::SortedSequence::Element::grow
void grow(int newHeight)
Increases the element's height to newHeight.
Definition: SortedSequence.h:112
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:713
ogdf::SortedSequenceIteratorBase::m_pElement
Element * m_pElement
Definition: SortedSequence.h:393
ogdf::SortedSequence::~SortedSequence
~SortedSequence()
Destructor.
Definition: SortedSequence.h:158
ogdf::SortedSequence::cend
const_iterator cend() const
Returns a const-iterator pointing to one past the last element.
Definition: SortedSequence.h:192
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:87
ogdf::SortedSequence::Element::m_next
Element ** m_next
array of successor elements.
Definition: SortedSequence.h:83
ogdf::SortedSequence::reverse_iterator
SortedSequenceReverseIterator< KEY, INFO, CMP > reverse_iterator
The reverse iterator type for sorted sequences (bidirectional iterator).
Definition: SortedSequence.h:135
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:260
ogdf::SortedSequence::iterator
SortedSequenceIterator< KEY, INFO, CMP > iterator
The iterator type for sorted sequences (bidirectional iterator).
Definition: SortedSequence.h:131
ogdf::SortedSequence::rend
reverse_iterator rend()
Returns a reverse iterator pointing to one before the first element.
Definition: SortedSequence.h:807
ogdf::SortedSequence::SortedSequence
SortedSequence(const CMP &comparer=CMP())
Constructs an initially empty sorted sequence.
Definition: SortedSequence.h:140
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:705
ogdf::SortedSequence::initEmpty
void initEmpty()
Definition: SortedSequence.h:361
ogdf::SortedSequenceIteratorBase::key
const KEY & key() const
Returns the key of the sequence element pointed to.
Definition: SortedSequence.h:415
ogdf::SortedSequenceIteratorBase::operator++
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > & operator++()
Move the iterator one item forward (prefix notation)
Definition: SortedSequence.h:430
ogdf::SortedSequenceIteratorBase::operator!=
bool operator!=(const SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > &it) const
Inequality operator.
Definition: SortedSequence.h:478
ogdf::SortedSequence::end
iterator end()
Returns an iterator pointing to one past the last element.
Definition: SortedSequence.h:784
ogdf::SortedSequence::operator=
SortedSequence< KEY, INFO, CMP > & operator=(const SortedSequence< KEY, INFO, CMP > &S)
Assignment operator.
Definition: SortedSequence.h:529
ogdf::SortedSequenceIteratorBase::operator=
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > & operator=(const SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > &it)
Assignment operator.
Definition: SortedSequence.h:466
ogdf::SortedSequenceIteratorBase
Iterators for sorted sequences.
Definition: SortedSequence.h:48
basic.h
Basic declarations, included by all source files.
ogdf::SortedSequence::Element::m_height
int m_height
the height of the skiplist element.
Definition: SortedSequence.h:81
ogdf::SortedSequence::Element::~Element
~Element()
Destructor.
Definition: SortedSequence.h:106
ogdf::SortedSequence::m_realHeight
int m_realHeight
actual height of head/tail arrays.
Definition: SortedSequence.h:356
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:631
ogdf::SortedSequenceIteratorBase::succElement
SortedSequence< KEY, INFO, CMP >::Element * succElement() const
Definition: SortedSequence.h:483
ogdf::SortedSequenceIteratorBase::SortedSequenceIteratorBase
SortedSequenceIteratorBase(Element *pElement)
Creates an iterator pointing to pElement.
Definition: SortedSequence.h:396
ogdf::SortedSequence
Maintains a sequence of (key,info) pairs sorted by key.
Definition: SortedSequence.h:71
ogdf::SortedSequence::size
int size() const
Returns the current size of the sequence, i.e., the number of stored elements.
Definition: SortedSequence.h:171
ogdf::SortedSequenceIteratorBase::operator--
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > & operator--()
Moves the iterator one item backward (prefix notation)
Definition: SortedSequence.h:443
ogdf::SortedSequence::crend
const_reverse_iterator crend() const
Returns a const reverse iterator pointing to one before the first element.
Definition: SortedSequence.h:210
ogdf::SortedSequence::m_rng
std::minstd_rand m_rng
Random number generator.
Definition: SortedSequence.h:358
ogdf::SortedSequence::reverseElements
void reverseElements(Element *p, Element *q)
Definition: SortedSequence.h:742
comparer.h
Declarations for Comparer objects.
ogdf::SortedSequence::m_size
int m_size
number of elements stored in the sequence.
Definition: SortedSequence.h:353
ogdf::SortedSequence::cbegin
const_iterator cbegin() const
Returns a const-iterator pointing to the first element.
Definition: SortedSequence.h:183
ogdf::SortedSequenceIteratorBase::operator++
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > operator++(int)
Moves the iterator one item forward (postfix notation)
Definition: SortedSequence.h:436
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:79