1/** \file
2 * \brief Data type for sorted sequences (based on skiplists)
3 *
4 * \author Carsten Gutwenger
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32#pragma once
33
34#include <random>
35#include <ogdf/basic/comparer.h>
36#include <ogdf/basic/memory.h>
37#include <ogdf/basic/Reverse.h>
38
39namespace ogdf {
40
41template<class KEY, class INFO, class CMP, bool isConst, bool isReverse>
42class SortedSequenceIteratorBase;
43
44template<class KEY, class INFO, class CMP>
45using SortedSequenceIterator = SortedSequenceIteratorBase<KEY,INFO,CMP,false,false>;
46
47template<class KEY, class INFO, class CMP>
48using SortedSequenceConstIterator = SortedSequenceIteratorBase<KEY,INFO,CMP,true,false>;
49
50template<class KEY, class INFO, class CMP>
51using SortedSequenceReverseIterator = SortedSequenceIteratorBase<KEY,INFO,CMP,false,true>;
52
53template<class KEY, class INFO, class CMP>
54using SortedSequenceConstReverseIterator = SortedSequenceIteratorBase<KEY,INFO,CMP,true,true>;
55
56//! Maintains a sequence of (key,info) pairs sorted by key.
57/**
58 * @ingroup containers
59 *
60 * Sorted sequences a implemented by doubly linked skiplists. Operations lookup, locate,
61 * insert, del, delItem take expected time O(log \a n), where \a n is the current size of
62 * the sequence.
63 */
64template<class KEY, class INFO, class CMP = StdComparer<KEY> >
65class SortedSequence {
66
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
72 //! Internal structure to hold the items and internal forward/backward pointers of the skiplist.
73 struct Element {
74
75 KEY m_key; //!< stores the key.
76 INFO m_info; //!< stores the associated information.
77 int m_height; //!< the height of the skiplist element.
78
79 Element** m_next; //!< array of successor elements.
80 Element** m_prev; //!< array of predecessor elements.
81
82 //! Creates a skiplist element for(\p key,\p info) and given \p height.
83 Element(const KEY &key, const INFO &info, int height)
84 : m_key(key), m_info(info), m_height(height)
85 {
86 m_next = (Element**)malloc(height * sizeof(Element*));
87 m_prev = (Element**)malloc(height * sizeof(Element*));
88 }
89
90 //! Creates a dummy (stop) element with given \p height.
91 /**
92 * Stop elements are marked with height 0, although this is not their real height.
93 * It is not necessary to store that, as we use realloc to increase their height.
94 */
95 Element(int height) : m_height(0)
96 {
97 m_next = (Element**)malloc(height * sizeof(Element*));
98 m_prev = (Element**)malloc(height * sizeof(Element*));
99 }
100
101 Element(const Element &) = delete;
102
103 //! Destructor.
104 ~Element() {
105 free(m_prev);
106 free(m_next);
107 }
108
109 //! Increases the element's height to \p newHeight.
110 void grow(int newHeight) {
111 Element **p = static_cast<Element**>( realloc(m_next, newHeight * sizeof(Element*)) );
112 if (p == nullptr) OGDF_THROW(InsufficientMemoryException);
113 m_next = p;
114
115 p = static_cast<Element**>(realloc(m_prev, newHeight * sizeof(Element*)));
116 if (p == nullptr) OGDF_THROW(InsufficientMemoryException);
117 m_prev = p;
118 }
119
120 OGDF_NEW_DELETE
121 };
122
123public:
124
125 //! The iterator type for sorted sequences (bidirectional iterator).
126 using iterator = SortedSequenceIterator<KEY,INFO,CMP>;
127 //! The const-iterator type for sorted sequences (bidirectional iterator).
128 using const_iterator = SortedSequenceConstIterator<KEY,INFO,CMP>;
129 //! The reverse iterator type for sorted sequences (bidirectional iterator).
130 using reverse_iterator = SortedSequenceReverseIterator<KEY,INFO,CMP>;
131 //! The const reverse iterator type for sorted sequences (bidirectional iterator).
132 using const_reverse_iterator = SortedSequenceConstReverseIterator<KEY,INFO,CMP>;
133
134 //! Constructs an initially empty sorted sequence.
135 SortedSequence(const CMP &comparer = CMP()) : m_comparer(comparer), m_rng(randomSeed()), m_randomBits(0,1) {
136 initEmpty();
137 }
138
139 //! Constructs a sorted sequence containing the elements in \p initList.
140 SortedSequence(std::initializer_list < std::pair < KEY, INFO >> initList);
141
142 //! Copy constructor.
143 SortedSequence(const SortedSequence<KEY,INFO,CMP> &S);
144
145 //! Copy constructor (move semantics).
146 /**
147 * The sequence \p S is empty afterwards.
148 */
149 SortedSequence(SortedSequence<KEY,INFO,CMP> &&S);
150
151
152 //! Destructor
153 ~SortedSequence() {
154 clear();
155 delete m_dummy;
156 }
157
158
159 //@}
160 /**
161 * @name General information and standard iterators
162 * These methods provide basic information like the number of elements in the list, as well as
163 * iterators to the begin and end of the sequence allowing forward and backward iteration over the sequence.
164 */
165 //@{
166
167 //! Returns the current size of the sequence, i.e., the number of stored elements.
168 int size() const { return m_size; }
169
170 //! Returns true if the sequence is empty, false otherwise.
171 bool empty() const { return m_size == 0; }
172
173 //! Returns an iterator pointing to the first element.
174 iterator begin();
175
176 //! Returns a const-iterator pointing to the first element.
177 const_iterator begin() const;
178
179 //! Returns a const-iterator pointing to the first element.
180 const_iterator cbegin() const { return begin(); }
181
182 //! Returns an iterator pointing to one past the last element.
183 iterator end();
184
185 //! Returns a const-iterator pointing to one past the last element.
186 const_iterator end() const;
187
188 //! Returns a const-iterator pointing to one past the last element.
189 const_iterator cend() const { return end(); }
190
191 //! Returns a reverse iterator pointing to the last element.
192 reverse_iterator rbegin();
193
194 //! Returns a const reverse iterator pointing to the last element.
195 const_reverse_iterator rbegin() const;
196
197 //! Returns a const reverse iterator pointing to the last element.
198 const_reverse_iterator crbegin() const { return rbegin(); }
199
200 //! Returns a reverse iterator pointing to one before the first element.
201 reverse_iterator rend();
202
203 //! Returns a const reverse iterator pointing to one before the first element.
204 const_reverse_iterator rend() const;
205
206 //! Returns a const reverse iterator pointing to one before the first element.
207 const_reverse_iterator crend() const { return rend(); }
208
209
210 /**
211 * @name Lookup operations
212 * These methods can be used to find elements by key. They return iterators pointing to the respective element in the sequence.
213 */
214 //@{
215
216 //! Returns an iterator to the element with key \p key, or a null iterator if no such element exists.
217 iterator lookup(const KEY &key);
218
219 //! Returns a const-iterator to the element with key \p key, or a null iterator if no such element exists.
220 const_iterator lookup(const KEY &key) const;
221
222 //! Returns an iterator to the element < \a k1, \a i1 > such that \a k1 is minimal with \a k1 &ge; \p key, or a null iterator if no such element exists.
223 iterator locate(const KEY &key);
224
225 //! Returns a const-iterator to the element < \a k1, \a i1 > such that \a k1 is minimal with \a k1 &ge; \p key, or a null iterator if no such element exists.
226 const_iterator locate(const KEY &key) const;
227
228 //! Returns an iterator to the element with minimal key if the sequence is not empty, an invalid iterator otherwise.
229 /**
230 * Calling this method is equivalent to calling begin(), but has a more intuitive name.
231 */
232 iterator minItem() { return begin(); }
233
234 //! Returns a const-iterator to the element with minimal key if the sequence is not empty, an invalid const-iterator otherwise.
235 /**
236 * Calling this method is equivalent to calling begin(), but has a more intuitive name.
237 */
238 const_iterator minItem() const { return begin(); }
239
240 //! Returns a reverse iterator to the element with maximal key if the sequence is not empty, an invalid reverse iterator otherwise.
241 /**
242 * Calling this method is equivalent to calling rbegin(), but has a more intuitive name.
243 */
244 reverse_iterator maxItem() { return rbegin(); }
245
246 //! Returns a const reverse iterator to the element with maximal key if the sequence is not empty, an invalid const reverse iterator otherwise.
247 /**
248 * Calling this method is equivalent to calling rbegin(), but has a more intuitive name.
249 */
250 const_reverse_iterator maxItem() const { return rbegin(); }
251
252
253 //@}
254 /**
255 * @name Insertion and deletion
256 * These method provide basic modification methods, like inserting new elements or removing elements from the sequence.
257 */
258 //@{
259
260 //! Updates information for \p key if contained in sequence, or adds a new element <\p key, \p info>.
261 iterator insert(const KEY &key, const INFO &info);
262
263 //! Removes the element with key \p key (if such an element exists).
264 void del(const KEY &key);
265
266 //! Removes the element to which \p it points from the sequence.
267 void delItem(iterator it);
268
269 //! Removes all elements from the sorted sequence.
270 void clear() {
271 Element* item = m_dummy->m_next[0];
272 while(item != m_dummy) {
273 Element* old = item;
274 item = item->m_next[0];
275 delete old;
276 }
277 m_size = 0;
278 m_height = 1;
279 m_dummy->m_next[0] = m_dummy->m_prev[0] = m_dummy;
280 }
281
282 //@}
283 /**
284 * @name Operators
285 * The following operators are overloeded for sorted sequences.
286 */
287 //@{
288
289 //! Assignment operator.
290 SortedSequence<KEY,INFO,CMP> &operator=(const SortedSequence<KEY,INFO,CMP> &S);
291
292 //! Assignment operator (move semantics).
293 /**
294 * The sequence \p S is empty afterwards.
295 */
296 SortedSequence<KEY,INFO,CMP> &operator=(SortedSequence<KEY,INFO,CMP> &&S);
297
298 //! Returns true if the keys stored in this sequence equal the keys in \p S, false otherwise.
299 /**
300 * Uses the given comparer object to compare keys.
301 */
302 bool operator==(const SortedSequence<KEY,INFO,CMP> &S);
303
304 //! Returns false if the keys stored in this sequence equal the keys in \p S, true otherwise.
305 /**
306 * Uses the given comparer object to compare keys.
307 */
308 bool operator!=(const SortedSequence<KEY,INFO,CMP> &S) {
309 return !operator==(S);
310 }
311
312 //@}
313 /**
314 * @name Special modification methods
315 * These methods must be handled with care; they are only useful in very specific scenarios. First read their documentation carefully!
316 */
317 //@{
318
319 //! Adds a new element <\p key, \p info> after element \p it.
320 /**
321 * \pre \p it points to an element in the sequence that shall appear before <\p key, \p info> in the sorted sequence,
322 * and its current successor \a itSucc shall appear after <\p key, \p info>, i.e., \p it's key is smaller than \p key
323 * and \a itSucc's key is greater than \p key.
324 */
325 iterator insertAfter(iterator it, const KEY &key, const INFO &info);
326
327 //! Reverses the items in the subsequence from \p itBegin to \p itEnd (inclusive).
328 /**
329 * \pre \p itBegin appears before \p itEnd in the sequence.
330 *
331 * \warning
332 * Usually, you do not need this method as the sequence is always sorted.
333 * It only makes sense if you use a special compare function that changes the underlying linear ordering,
334 * and you have to adjust the sorting manually.
335 * Do not use this method unless you know exactly what you are doing! After applying
336 * this method the subsequence should be ordered correctly according to the compare function.
337 */
338 void reverseItems(iterator itBegin, iterator itEnd) {
339 reverseElements(itBegin.m_pElement, itEnd.m_pElement);
340 }
341
342 //@}
343
344private:
345 CMP m_comparer;
346 int m_size; //!< number of elements stored in the sequence.
347 Element *m_dummy; //!< dummy element representing the head and tail of the skiplist.
348 int m_height; //!< current height of head/tail.
349 int m_realHeight; //!< actual height of head/tail arrays.
350
351 std::minstd_rand m_rng; //!< Random number generator
352 std::uniform_int_distribution<> m_randomBits;
353
354
355 void initEmpty() {
356 m_size = 0;
357 m_realHeight = 5;
358 m_height = 1;
359
360 m_dummy = new Element(m_realHeight);
361 m_dummy->m_next[0] = m_dummy;
362 m_dummy->m_prev[0] = m_dummy;
363 }
364
365 int randomHeightAndGrow();
366 void grow(int newHeight);
367
368 const Element *_lookup(const KEY &key) const;
369 const Element *_locate(const KEY &key) const;
370
371 void removeElement(Element *p);
372 void insertElementAfterElement(Element *p, Element *q);
373 void reverseElements(Element *p, Element *q);
374};
375
376
377//! Iterators for sorted sequences.
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 = typename std::conditional<isConst,
386 const typename SortedSequence<KEY,INFO,CMP>::Element,
387 typename SortedSequence<KEY,INFO,CMP>::Element>::type;
388 Element *m_pElement;
389
390 //! Creates an iterator pointing to \p pElement.
391 SortedSequenceIteratorBase(Element *pElement) : m_pElement(pElement) { }
392
393public:
394 //! Creates an invalid (null-) iterator.
395 SortedSequenceIteratorBase() : m_pElement(nullptr) { }
396
397 //! Copy constructor.
398 template<bool isArgConst, typename std::enable_if<isConst || !isArgConst, int>::type = 0, bool isArgReverse>
399 SortedSequenceIteratorBase(const SortedSequenceIteratorBase<KEY,INFO,CMP,isArgConst,isArgReverse> &it)
400 : m_pElement(it.m_pElement) { }
401
402 //! Returns the key of the sequence element pointed to.
403 const KEY &key() const {
404 OGDF_ASSERT(valid());
405 return m_pElement->m_key;
406 }
407
408 //! Returns the info of the sequence element pointed to.
409 typename std::conditional<isConst, const INFO, INFO>::type &info() const {
410 OGDF_ASSERT(valid());
411 return m_pElement->m_info;
412 }
413
414 //! Returns true if the iterator points to an element.
415 bool valid() const { return m_pElement != nullptr; }
416
417 //! Move the iterator one item forward (prefix notation)
418 SortedSequenceIteratorBase<KEY,INFO,CMP,isConst,isReverse> &operator++() {
419 m_pElement = isReverse ? predElement() : succElement();
420 return *this;
421 }
422
423 //! Moves the iterator one item forward (postfix notation)
424 SortedSequenceIteratorBase<KEY,INFO,CMP,isConst,isReverse> operator++(int) {
425 SortedSequenceIteratorBase<KEY,INFO,CMP,isConst,isReverse> it = *this;
426 m_pElement = isReverse ? predElement() : succElement();
427 return it;
428 }
429
430 //! Moves the iterator one item backward (prefix notation)
431 SortedSequenceIteratorBase<KEY,INFO,CMP,isConst,isReverse> &operator--() {
432 m_pElement = isReverse ? succElement() : predElement();
433 return *this;
434 }
435
436 //! Moves the iterator one item backward (postfix notation)
437 SortedSequenceIteratorBase<KEY,INFO,CMP,isConst,isReverse> operator--(int) {
438 SortedSequenceIteratorBase<KEY,INFO,CMP,isConst,isReverse> it = *this;
439 m_pElement = isReverse ? succElement() : predElement();
440 return it;
441 }
442
443 //! Returns an iterator pointing to the next element in the sequence.
444 SortedSequenceIteratorBase<KEY,INFO,CMP,isConst,isReverse> succ() const {
445 return isReverse ? predElement() : succElement();
446 }
447
448 //! Returns an iterator pointing to the previous element in the sequence.
449 SortedSequenceIteratorBase<KEY,INFO,CMP,isConst,isReverse> pred() const {
450 return isReverse ? succElement() : predElement();
451 }
452
453 //! Assignment operator
454 SortedSequenceIteratorBase<KEY,INFO,CMP,isConst,isReverse> &operator=(const SortedSequenceIteratorBase<KEY,INFO,CMP,isConst,isReverse> &it) {
455 m_pElement = it.m_pElement;
456 return *this;
457 }
458
459 //! Equality operator.
460 bool operator==(const SortedSequenceIteratorBase<KEY,INFO,CMP,isConst,isReverse> &it) const {
461 return m_pElement == it.m_pElement;
462 }
463
464 //! Inequality operator.
465 bool operator!=(const SortedSequenceIteratorBase<KEY,INFO,CMP,isConst,isReverse> &it) const {
466 return m_pElement != it.m_pElement;
467 }
468
469private:
470 typename SortedSequence<KEY,INFO,CMP>::Element *succElement() const {
471 OGDF_ASSERT(valid());
472 return (m_pElement->m_next[0]->m_height > 0) ? m_pElement->m_next[0] : nullptr;
473 }
474
475 typename SortedSequence<KEY,INFO,CMP>::Element *predElement() const {
476 OGDF_ASSERT(valid());
477 return (m_pElement->m_prev[0]->m_height > 0) ? m_pElement->m_prev[0] : nullptr;
478 }
479};
480
481template<class KEY, class INFO, class CMP>
482SortedSequence<KEY, INFO, CMP>::SortedSequence(std::initializer_list < std::pair < KEY, INFO >> initList)
483 : SortedSequence()
484{
485 for (const auto &p : initList)
486 insert(p.first, p.second);
487}
488
489
490template<class KEY, class INFO, class CMP>
491SortedSequence<KEY,INFO,CMP>::SortedSequence(const SortedSequence<KEY,INFO,CMP> &S)
492 : m_comparer(S.m_comparer), m_rng(randomSeed()), m_randomBits(0,1)
493{
494 initEmpty();
495
496 iterator it = m_dummy;
497 for(Element *pS = S.m_dummy->m_next[0]; pS != S.m_dummy; pS = pS->m_next[0])
498 it = insertAfter(it, pS->m_key, pS->m_info);
499}
500
501
502template<class KEY, class INFO, class CMP>
503SortedSequence<KEY,INFO,CMP>::SortedSequence(SortedSequence<KEY,INFO,CMP> &&S)
504 : m_comparer(S.m_comparer), m_size(S.m_size), m_height(S.m_height), m_realHeight(S.m_realHeight), m_rng(randomSeed()), m_randomBits(0,1)
505{
506 // move all elements to this sequence
507 m_dummy = S.m_dummy;
508
509 // initalize S with an empty sequence
510 S.initEmpty();
511}
512
513
514template<class KEY, class INFO, class CMP>
515SortedSequence<KEY,INFO,CMP> &SortedSequence<KEY,INFO,CMP>::operator=(const SortedSequence<KEY,INFO,CMP> &S)
516{
517 clear();
518
519 iterator it = m_dummy;
520 for(Element *pS = S.m_dummy->m_next[0]; pS != S.m_dummy; pS = pS->m_next[0])
521 it = insertAfter(it, pS->m_key, pS->m_info);
522
523 return *this;
524}
525
526
527template<class KEY, class INFO, class CMP>
528SortedSequence<KEY,INFO,CMP> &SortedSequence<KEY,INFO,CMP>::operator=(SortedSequence<KEY,INFO,CMP> &&S)
529{
530 // clear this sequence
531 Element* item = m_dummy->m_next[0];
532 while(item != m_dummy) {
533 Element* old = item;
534 item = item->m_next[0];
535 delete old;
536 }
537 delete m_dummy;
538
539 // move elements from S to this sequence
540 m_comparer = S.m_comparer;
541 m_size = S.m_size;
542 m_height = S.m_height;
543 m_realHeight = S.m_realHeight;
544 m_dummy = S.m_dummy;
545
546 // make S the empty sequence
547 S.initEmpty();
548
549 return *this;
550}
551
552
553template<class KEY, class INFO, class CMP>
554bool SortedSequence<KEY,INFO,CMP>::operator==(const SortedSequence<KEY,INFO,CMP> &S)
555{
556 if(m_size != S.m_size)
557 return false;
558
559 Element *p = m_dummy->m_next[0], *pS = S.m_dummy->m_next[0];
560 while(p != m_dummy) {
561 if (!m_comparer.equal(p->m_key,pS->m_key))
562 return false;
563 p = p ->m_next[0];
564 pS = pS->m_next[0];
565 }
566
567 return true;
568}
569
570
571template<class KEY, class INFO, class CMP>
572const typename SortedSequence<KEY,INFO,CMP>::Element *SortedSequence<KEY,INFO,CMP>::_lookup(const KEY &key) const
573{
574 int h = m_height - 1;
575 Element** pElement = m_dummy->m_next;
576
577 while(true) {
578 if( pElement[h] != m_dummy && m_comparer.less(pElement[h]->m_key, key) )
579 pElement = pElement[h]->m_next;
580 else if(--h < 0) {
581 if( pElement[0] != m_dummy && m_comparer.equal(pElement[0]->m_key, key) )
582 return pElement[0];
583 return nullptr;
584 }
585 }
586}
587
588template<class KEY, class INFO, class CMP>
589typename SortedSequence<KEY,INFO,CMP>::iterator SortedSequence<KEY,INFO,CMP>::lookup(const KEY &key)
590{
591 return iterator(const_cast<Element *>(_lookup(key)));
592}
593
594template<class KEY, class INFO, class CMP>
595typename SortedSequence<KEY,INFO,CMP>::const_iterator SortedSequence<KEY,INFO,CMP>::lookup(const KEY &key) const
596{
597 return const_iterator(_lookup(key));
598}
599
600
601template<class KEY, class INFO, class CMP>
602const typename SortedSequence<KEY,INFO,CMP>::Element *SortedSequence<KEY,INFO,CMP>::_locate(const KEY &key) const
603{
604 int h = m_height - 1;
605 Element** pElement = m_dummy->m_next;
606
607 while(true) {
608 if( pElement[h] != m_dummy && m_comparer.less(pElement[h]->m_key, key) )
609 pElement = pElement[h]->m_next;
610 else if(--h < 0) {
611 Element *p = (pElement[0] != m_dummy) ? pElement[0] : nullptr;
612 return p;
613 }
614 }
615}
616
617template<class KEY, class INFO, class CMP>
618typename SortedSequence<KEY,INFO,CMP>::iterator SortedSequence<KEY,INFO,CMP>::locate(const KEY &key)
619{
620 return iterator(const_cast<Element *>(_locate(key)));
621}
622
623template<class KEY, class INFO, class CMP>
624typename SortedSequence<KEY,INFO,CMP>::const_iterator SortedSequence<KEY,INFO,CMP>::locate(const KEY &key) const
625{
626 return const_iterator(_locate(key));
627}
628
629
630template<class KEY, class INFO, class CMP>
631void SortedSequence<KEY,INFO,CMP>::grow(int newHeight)
632{
633 if(newHeight > m_realHeight) {
634 m_realHeight = newHeight;
635 m_dummy->grow(newHeight);
636 }
637
638 for(int i = newHeight; i-- > m_height; ) {
639 m_dummy->m_next[i] = m_dummy;
640 m_dummy->m_prev[i] = m_dummy;
641 }
642 m_height = newHeight;
643}
644
645template<class KEY, class INFO, class CMP>
646int SortedSequence<KEY,INFO,CMP>::randomHeightAndGrow()
647{
648 int h = 1;
649 while(m_randomBits(m_rng) == 1)
650 h++;
651
652 if(h > m_height)
653 grow(h);
654
655 return h;
656}
657
658
659template<class KEY, class INFO, class CMP>
660typename SortedSequence<KEY,INFO,CMP>::iterator SortedSequence<KEY,INFO,CMP>::insert(const KEY &key, const INFO &info)
661{
662 int h = m_height - 1;
663 Element *pCurrent = m_dummy;
664
665 while(true) {
666 if( pCurrent->m_next[h] != m_dummy && m_comparer.less(pCurrent->m_next[h]->m_key, key) ) {
667 pCurrent = pCurrent->m_next[h];
668
669 } else {
670 if(--h < 0) {
671 // found element?
672 if( pCurrent->m_next[0] != m_dummy && m_comparer.equal(pCurrent->m_next[0]->m_key, key) ) {
673 pCurrent->m_next[0]->m_info = info;
674 return iterator(pCurrent->m_next[0]);
675 }
676 break;
677 }
678 }
679 }
680
681 // add new element (key,inf)
682 m_size++;
683
684 int nh = randomHeightAndGrow();
685
686 Element* pNewElement = new Element(key, info, nh);
687 insertElementAfterElement(pNewElement, pCurrent);
688
689 return iterator(pNewElement);
690}
691
692
693template<class KEY, class INFO, class CMP>
694void SortedSequence<KEY,INFO,CMP>::del(const KEY &key)
695{
696 iterator it = lookup(key);
697 if(it.valid())
698 delItem(it);
699}
700
701
702template<class KEY, class INFO, class CMP>
703typename SortedSequence<KEY,INFO,CMP>::iterator SortedSequence<KEY,INFO,CMP>::insertAfter(iterator it, const KEY &key, const INFO &info)
704{
705 m_size++;
706
707 int nh = randomHeightAndGrow();
708
709 Element* pNewElement = new Element(key, info, nh);
710 insertElementAfterElement(pNewElement, it.m_pElement);
711
712 return pNewElement;
713}
714
715
716template<class KEY, class INFO, class CMP>
717void SortedSequence<KEY,INFO,CMP>::insertElementAfterElement(Element *p, Element *q)
718{
719 OGDF_ASSERT(p->m_height <= m_height);
720
721 for(int h = 0; h < p->m_height; ++h) {
722 while(q != m_dummy && q->m_height <= h)
723 q = q->m_prev[h-1];
724
725 Element *r = q->m_next[h];
726 p->m_next[h] = r;
727 p->m_prev[h] = q;
728 q->m_next[h] = r->m_prev[h] = p;
729 }
730}
731
732
733template<class KEY, class INFO, class CMP>
734void SortedSequence<KEY,INFO,CMP>::reverseElements(Element *p, Element *q)
735{
736 while(p != q) {
737 Element *r = p;
738 p = p->m_next[0];
739 removeElement(r);
740 insertElementAfterElement(r,q);
741 }
742}
743
744
745template<class KEY, class INFO, class CMP>
746void SortedSequence<KEY,INFO,CMP>::removeElement(Element *p)
747{
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
759template<class KEY, class INFO, class CMP>
760void SortedSequence<KEY,INFO,CMP>::delItem(typename SortedSequence<KEY,INFO,CMP>::iterator it)
761{
762 Element *p = it.m_pElement;
763 removeElement(p);
764
765 m_size--;
766 delete p;
767}
768
769
770template<class KEY, class INFO, class CMP>
771inline typename SortedSequence<KEY,INFO,CMP>::iterator
772 SortedSequence<KEY,INFO,CMP>::begin()
773{
774 return (m_dummy->m_next[0] != m_dummy) ? m_dummy->m_next[0] : nullptr;
775}
776
777template<class KEY, class INFO, class CMP>
778inline typename SortedSequence<KEY,INFO,CMP>::const_iterator
779 SortedSequence<KEY,INFO,CMP>::begin() const
780{
781 return (m_dummy->m_next[0] != m_dummy) ? m_dummy->m_next[0] : 0;
782}
783
784
785template<class KEY, class INFO, class CMP>
786inline typename SortedSequence<KEY,INFO,CMP>::iterator
787 SortedSequence<KEY,INFO,CMP>::end()
788{
789 return SortedSequence<KEY,INFO,CMP>::iterator();
790}
791
792template<class KEY, class INFO, class CMP>
793inline typename SortedSequence<KEY,INFO,CMP>::const_iterator
794 SortedSequence<KEY,INFO,CMP>::end() const
795{
796 return SortedSequence<KEY,INFO,CMP>::const_iterator();
797}
798
799
800template<class KEY, class INFO, class CMP>
801inline typename SortedSequence<KEY,INFO,CMP>::reverse_iterator
802 SortedSequence<KEY,INFO,CMP>::rbegin()
803{
804 return (m_dummy->m_prev[0] != m_dummy) ? m_dummy->m_prev[0] : 0;
805}
806
807template<class KEY, class INFO, class CMP>
808inline typename SortedSequence<KEY,INFO,CMP>::const_reverse_iterator
809 SortedSequence<KEY,INFO,CMP>::rbegin() const
810{
811 return (m_dummy->m_prev[0] != m_dummy) ? m_dummy->m_prev[0] : 0;
812}
813
814
815template<class KEY, class INFO, class CMP>
816inline typename SortedSequence<KEY,INFO,CMP>::reverse_iterator
817 SortedSequence<KEY,INFO,CMP>::rend()
818{
819 return SortedSequence<KEY,INFO,CMP>::iterator();
820}
821
822template<class KEY, class INFO, class CMP>
823inline typename SortedSequence<KEY,INFO,CMP>::const_reverse_iterator
824 SortedSequence<KEY,INFO,CMP>::rend() const
825{
826 return SortedSequence<KEY,INFO,CMP>::const_iterator();
827}
828
829}
830