Open
Graph Drawing
Framework

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

Loading...
Searching...
No Matches
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
40namespace ogdf {
41
42template<class KEY, class INFO, class CMP, bool isConst, bool isReverse>
43class SortedSequenceIteratorBase;
44
45template<class KEY, class INFO, class CMP>
46using SortedSequenceIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, false, false>;
47
48template<class KEY, class INFO, class CMP>
49using SortedSequenceConstIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, true, false>;
50
51template<class KEY, class INFO, class CMP>
52using SortedSequenceReverseIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, false, true>;
53
54template<class KEY, class INFO, class CMP>
55using SortedSequenceConstReverseIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, true, true>;
56
58
65template<class KEY, class INFO, class CMP = StdComparer<KEY>>
66class 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
124public:
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
164
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
212
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
263
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
292
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
320
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
346private:
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
378template<class KEY, class INFO, class CMP, bool isConst, bool isReverse>
379class 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
393public:
395 SortedSequenceIteratorBase() : m_pElement(nullptr) { }
396
398 template<bool isArgConst, typename std::enable_if<isConst || !isArgConst, int>::type = 0, bool isArgReverse>
402
404 // gcc9 complains since it cannot match the templated constructor above (-Werror=deprecated-copy).
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
429
436
442
449
454
459
466
471
476
477private:
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
489template<class KEY, class INFO, class CMP>
490SortedSequence<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
497template<class KEY, class INFO, class CMP>
498SortedSequence<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
508template<class KEY, class INFO, class CMP>
509SortedSequence<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
523template<class KEY, class INFO, class CMP>
524SortedSequence<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
536template<class KEY, class INFO, class CMP>
537SortedSequence<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
561template<class KEY, class INFO, class CMP>
562bool 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
579template<class KEY, class INFO, class CMP>
580const 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
597template<class KEY, class INFO, class CMP>
598typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::lookup(
599 const KEY& key) {
600 return iterator(const_cast<Element*>(_lookup(key)));
601}
602
603template<class KEY, class INFO, class CMP>
608
609template<class KEY, class INFO, class CMP>
610const 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
625template<class KEY, class INFO, class CMP>
626typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::locate(
627 const KEY& key) {
628 return iterator(const_cast<Element*>(_locate(key)));
629}
630
631template<class KEY, class INFO, class CMP>
636
637template<class KEY, class INFO, class CMP>
638void 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
651template<class KEY, class INFO, class CMP>
652int 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
665template<class KEY, class INFO, class CMP>
666typename 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
699template<class KEY, class INFO, class CMP>
700void SortedSequence<KEY, INFO, CMP>::del(const KEY& key) {
701 iterator it = lookup(key);
702 if (it.valid()) {
703 delItem(it);
704 }
705}
706
707template<class KEY, class INFO, class CMP>
708typename 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
720template<class KEY, class INFO, class CMP>
721void 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
736template<class KEY, class INFO, class CMP>
737void 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
746template<class KEY, class INFO, class CMP>
747void 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
758template<class KEY, class INFO, class CMP>
759void 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
767template<class KEY, class INFO, class CMP>
768inline 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
772template<class KEY, class INFO, class CMP>
773inline typename SortedSequence<KEY, INFO, CMP>::const_iterator
774SortedSequence<KEY, INFO, CMP>::begin() const {
775 return (m_dummy->m_next[0] != m_dummy) ? m_dummy->m_next[0] : 0;
776}
777
778template<class KEY, class INFO, class CMP>
782
783template<class KEY, class INFO, class CMP>
784inline typename SortedSequence<KEY, INFO, CMP>::const_iterator
788
789template<class KEY, class INFO, class CMP>
790inline typename SortedSequence<KEY, INFO, CMP>::reverse_iterator
791SortedSequence<KEY, INFO, CMP>::rbegin() {
792 return (m_dummy->m_prev[0] != m_dummy) ? m_dummy->m_prev[0] : 0;
793}
794
795template<class KEY, class INFO, class CMP>
796inline typename SortedSequence<KEY, INFO, CMP>::const_reverse_iterator
797SortedSequence<KEY, INFO, CMP>::rbegin() const {
798 return (m_dummy->m_prev[0] != m_dummy) ? m_dummy->m_prev[0] : 0;
799}
800
801template<class KEY, class INFO, class CMP>
805
806template<class KEY, class INFO, class CMP>
807inline typename SortedSequence<KEY, INFO, CMP>::const_reverse_iterator
811
812}
Reverse.h
Implementation of the Reverse class for the reverse iteration of containers.
ogdf::InsufficientMemoryException
Exception thrown when not enough memory is available to execute an algorithm.
Definition exceptions.h:203
ogdf::SortedSequence
Maintains a sequence of (key,info) pairs sorted by key.
Definition SortedSequence.h:66
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::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::SortedSequence::delItem
void delItem(iterator it)
Removes the element to which it points from the sequence.
Definition SortedSequence.h:759
ogdf::SortedSequence::m_rng
std::minstd_rand m_rng
Random number generator.
Definition SortedSequence.h:353
ogdf::SortedSequence::cend
const_iterator cend() const
Returns a const-iterator pointing to one past the last element.
Definition SortedSequence.h:187
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::m_realHeight
int m_realHeight
actual height of head/tail arrays.
Definition SortedSequence.h:351
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::reverseElements
void reverseElements(Element *p, Element *q)
Definition SortedSequence.h:737
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::operator=
SortedSequence< KEY, INFO, CMP > & operator=(const SortedSequence< KEY, INFO, CMP > &S)
Assignment operator.
Definition SortedSequence.h:524
ogdf::SortedSequence::m_size
int m_size
number of elements stored in the sequence.
Definition SortedSequence.h:348
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::reverseItems
void reverseItems(iterator itBegin, iterator itEnd)
Reverses the items in the subsequence from itBegin to itEnd (inclusive).
Definition SortedSequence.h:340
ogdf::SortedSequence::_lookup
const Element * _lookup(const KEY &key) const
Definition SortedSequence.h:580
ogdf::SortedSequence::iterator
SortedSequenceIterator< KEY, INFO, CMP > iterator
The iterator type for sorted sequences (bidirectional iterator).
Definition SortedSequence.h:126
ogdf::SortedSequence::_locate
const Element * _locate(const KEY &key) const
Definition SortedSequence.h:610
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::begin
iterator begin()
Returns an iterator pointing to the first element.
Definition SortedSequence.h:768
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::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_dummy
Element * m_dummy
dummy element representing the head and tail of the skiplist.
Definition SortedSequence.h:349
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::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::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::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::SortedSequence::reverse_iterator
SortedSequenceReverseIterator< KEY, INFO, CMP > reverse_iterator
The reverse iterator type for sorted sequences (bidirectional iterator).
Definition SortedSequence.h:130
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::~SortedSequence
~SortedSequence()
Destructor.
Definition SortedSequence.h:153
ogdf::SortedSequence::m_randomBits
std::uniform_int_distribution m_randomBits
Definition SortedSequence.h:354
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::insertElementAfterElement
void insertElementAfterElement(Element *p, Element *q)
Definition SortedSequence.h:721
ogdf::SortedSequence::const_iterator
SortedSequenceConstIterator< KEY, INFO, CMP > const_iterator
The const-iterator type for sorted sequences (bidirectional iterator).
Definition SortedSequence.h:128
ogdf::SortedSequence::empty
bool empty() const
Returns true if the sequence is empty, false otherwise.
Definition SortedSequence.h:169
ogdf::SortedSequence::crbegin
const_reverse_iterator crbegin() const
Returns a const reverse iterator pointing to the last element.
Definition SortedSequence.h:196
ogdf::SortedSequence::grow
void grow(int newHeight)
Definition SortedSequence.h:638
ogdf::SortedSequence::clear
void clear()
Removes all elements from the sorted sequence.
Definition SortedSequence.h:274
ogdf::SortedSequence::end
iterator end()
Returns an iterator pointing to one past the last element.
Definition SortedSequence.h:779
ogdf::SortedSequence::m_height
int m_height
current height of head/tail.
Definition SortedSequence.h:350
ogdf::SortedSequence::rbegin
reverse_iterator rbegin()
Returns a reverse iterator pointing to the last element.
Definition SortedSequence.h:791
ogdf::SortedSequence::removeElement
void removeElement(Element *p)
Definition SortedSequence.h:747
ogdf::SortedSequence::cbegin
const_iterator cbegin() const
Returns a const-iterator pointing to the first element.
Definition SortedSequence.h:178
ogdf::SortedSequenceIteratorBase
Iterators for sorted sequences.
Definition SortedSequence.h:379
ogdf::SortedSequenceIteratorBase::SortedSequenceIteratorBase
SortedSequenceIteratorBase(const SortedSequenceIteratorBase< KEY, INFO, CMP, isArgConst, isArgReverse > &it)
Copy constructor.
Definition SortedSequence.h:399
ogdf::SortedSequenceIteratorBase::operator++
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > operator++(int)
Moves the iterator one item forward (postfix notation)
Definition SortedSequence.h:431
ogdf::SortedSequenceIteratorBase::operator++
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > & operator++()
Move the iterator one item forward (prefix notation)
Definition SortedSequence.h:425
ogdf::SortedSequenceIteratorBase::info
std::conditional< isConst, constINFO, INFO >::type & info() const
Returns the info of the sequence element pointed to.
Definition SortedSequence.h:416
ogdf::SortedSequenceIteratorBase::operator==
bool operator==(const SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > &it) const
Equality operator.
Definition SortedSequence.h:468
ogdf::SortedSequenceIteratorBase::key
const KEY & key() const
Returns the key of the sequence element pointed to.
Definition SortedSequence.h:410
ogdf::SortedSequenceIteratorBase::SortedSequenceIteratorBase
SortedSequenceIteratorBase(Element *pElement)
Creates an iterator pointing to pElement.
Definition SortedSequence.h:391
ogdf::SortedSequenceIteratorBase::operator--
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > operator--(int)
Moves the iterator one item backward (postfix notation)
Definition SortedSequence.h:444
ogdf::SortedSequenceIteratorBase::operator--
SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > & operator--()
Moves the iterator one item backward (prefix notation)
Definition SortedSequence.h:438
ogdf::SortedSequenceIteratorBase::SortedSequenceIteratorBase
SortedSequenceIteratorBase()
Creates an invalid (null-) iterator.
Definition SortedSequence.h:395
ogdf::SortedSequenceIteratorBase::SortedSequenceIteratorBase
SortedSequenceIteratorBase(const SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > &it)
Copy constructor.
Definition SortedSequence.h:405
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::valid
bool valid() const
Returns true if the iterator points to an element.
Definition SortedSequence.h:422
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::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::SortedSequenceIteratorBase::operator!=
bool operator!=(const SortedSequenceIteratorBase< KEY, INFO, CMP, isConst, isReverse > &it) const
Inequality operator.
Definition SortedSequence.h:473
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::SortedSequenceIteratorBase::succElement
SortedSequence< KEY, INFO, CMP >::Element * succElement() const
Definition SortedSequence.h:478
ogdf::SortedSequenceIteratorBase::predElement
SortedSequence< KEY, INFO, CMP >::Element * predElement() const
Definition SortedSequence.h:483
comparer.h
Declarations for Comparer objects.
OGDF_THROW
#define OGDF_THROW(CLASS)
Replacement for throw.
Definition exceptions.h:63
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition memory.h:84
ogdf::randomSeed
long unsigned int randomSeed()
Returns a random value suitable as initial seed for a random number engine.
r
int r[]
Definition hierarchical-ranking.cpp:8
memory.h
Declaration of memory manager for allocating small pieces of memory.
getDoubleFactoredZeroAdjustedMerger
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
Definition multilevelmixer.cpp:36
ogdf
The namespace for all OGDF objects.
Definition AugmentationModule.h:36
ogdf::SortedSequence::Element
Internal structure to hold the items and internal forward/backward pointers of the skiplist.
Definition SortedSequence.h:73
ogdf::SortedSequence::Element::m_height
int m_height
the height of the skiplist element.
Definition SortedSequence.h:76
ogdf::SortedSequence::Element::m_next
Element ** m_next
array of successor elements.
Definition SortedSequence.h:78
ogdf::SortedSequence::Element::m_prev
Element ** m_prev
array of predecessor elements.
Definition SortedSequence.h:79
ogdf::SortedSequence::Element::grow
void grow(int newHeight)
Increases the element's height to newHeight.
Definition SortedSequence.h:107
ogdf::SortedSequence::Element::Element
Element(int height)
Creates a dummy (stop) element with given height.
Definition SortedSequence.h:93
ogdf::SortedSequence::Element::Element
Element(const Element &)=delete
ogdf::SortedSequence::Element::m_info
INFO m_info
stores the associated information.
Definition SortedSequence.h:75
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