Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
Skiplist.h
Go to the documentation of this file.
32#pragma once
33
34#include <ogdf/basic/basic.h>
35#include <ogdf/basic/memory.h>
36
37namespace ogdf {
38
39template<class X>
41
43
51template<class X>
52class Skiplist {
53 friend class SkiplistIterator<X>;
54 friend class Element;
55
57 class Element {
58 friend class Skiplist<X>;
59 friend class SkiplistIterator<X>;
60
61 X entry; // content
62 Element** next; // successor elements
63
64 // construction
65 Element(const X& item, int height) : entry(item) {
66 next = (Element**)malloc(height * sizeof(Element*));
67 }
68
69 ~Element() { free(next); }
70
72 };
73
74public:
77 srand((unsigned int)time(nullptr));
78 m_realheight = 5;
79 m_height = 1;
80 m_start = (Element**)malloc(m_realheight * sizeof(Element*));
81 m_start[0] = nullptr;
82 }
83
85 clear();
86 free(m_start);
87 }
88
90 bool isElement(X item) const {
91 int h = m_height - 1;
92 Element** cur = m_start; // wheeha!
93 while (true) {
94 if (cur[h] && *(cur[h]->entry) < *item) { //nxt != nullptr
95 cur = cur[h]->next;
96 } else if (--h < 0) {
97 return cur[0] && *(cur[0]->entry) == *item;
98 }
99 }
100 }
101
103 void add(X item) {
104 m_lSize++;
105
106 int nh = random_height();
107 Element* n = new Element(item, nh);
108 if (nh > m_height) {
109 grow(nh);
110 }
111
112 int h = m_height - 1;
113 Element** cur = m_start; // wheeha!
114 while (true) {
115 if (cur[h] && *(cur[h]->entry) < *item) { //nxt != nullptr
116 cur = cur[h]->next;
117 } else {
118 if (h < nh) { // add only if new element is high enough
119 n->next[h] = cur[h];
120 cur[h] = n;
121 }
122 if (--h < 0) {
123 return;
124 }
125 }
126 }
127 }
128
130 int size() const { return m_lSize; }
131
133 bool empty() const { return m_lSize == 0; }
134
136
140 void clear(bool killData = false) {
141 Element* item = m_start[0];
142 while (item) {
143 Element* old = item;
144 item = item->next[0];
145 if (killData) {
146 delete old->entry;
147 }
148 delete old;
149 }
150 m_lSize = 0;
151 m_height = 1;
152 m_start[0] = nullptr;
153 }
154
156 const SkiplistIterator<X> begin() const { return m_start[0]; }
157
159 const SkiplistIterator<X> end() const { return nullptr; }
160
161private:
166
168 int h = 1;
169 while (rand() > RAND_MAX / 2) {
170 h++;
171 }
172 return h;
173 }
174
175 void grow(int newheight) {
176 if (newheight > m_realheight) {
178 Element** newStart =
179 static_cast<Element**>(realloc(m_start, m_realheight * sizeof(Element*)));
180 if (newStart == nullptr) {
181 free(m_start);
182 } else {
184 }
185 }
186 for (int i = newheight; i-- > m_height;) {
187 m_start[i] = nullptr;
188 }
190 }
191};
192
194template<class X>
196 friend class Skiplist<X>;
197
198 const typename Skiplist<X>::Element* el;
199
200 SkiplistIterator(const typename Skiplist<X>::Element* e) { el = e; }
201
202public:
204 const X& operator*() const { return el->entry; }
205
206 bool valid() const { return el != nullptr; }
207
210 el = el->next[0];
211 return *this;
212 }
213
216 SkiplistIterator<X> it = *this;
217 el = el->next[0];
218 return it;
219 }
220
221 bool operator==(const SkiplistIterator<X> other) const { return el == other.el; }
222
223 bool operator!=(const SkiplistIterator<X> other) const { return !operator==(other); }
224};
225
226}
Basic declarations, included by all source files.
Internal structure to hold the items and internal forward pointers of the skiplist.
Definition Skiplist.h:57
Element(const X &item, int height)
Definition Skiplist.h:65
A randomized skiplist.
Definition Skiplist.h:52
void grow(int newheight)
Definition Skiplist.h:175
const SkiplistIterator< X > begin() const
returns an (forward) iterator for the skiplist
Definition Skiplist.h:156
const SkiplistIterator< X > end() const
returns an invalid iterator
Definition Skiplist.h:159
void clear(bool killData=false)
Clears the current skiplist.
Definition Skiplist.h:140
bool isElement(X item) const
Returns true if the item item is contained in the skiplist [O'(log n)].
Definition Skiplist.h:90
bool empty() const
Returns true if the skiplist contains no elements.
Definition Skiplist.h:133
Element ** m_start
Definition Skiplist.h:163
void add(X item)
Adds the item item into the skiplist [O'(log n)].
Definition Skiplist.h:103
int random_height()
Definition Skiplist.h:167
Skiplist()
Construct an initially empty skiplist.
Definition Skiplist.h:76
int size() const
Returns the current size of the skiplist, i.e., the number of elements.
Definition Skiplist.h:130
Forward-Iterator for Skiplists.
Definition Skiplist.h:195
SkiplistIterator(const typename Skiplist< X >::Element *e)
Definition Skiplist.h:200
bool operator!=(const SkiplistIterator< X > other) const
Definition Skiplist.h:223
const X & operator*() const
Returns the item to which the iterator points.
Definition Skiplist.h:204
bool valid() const
Definition Skiplist.h:206
bool operator==(const SkiplistIterator< X > other) const
Definition Skiplist.h:221
SkiplistIterator< X > operator++(int)
Move the iterator one item forward (prefix notation)
Definition Skiplist.h:215
const Skiplist< X >::Element * el
Definition Skiplist.h:198
SkiplistIterator< X > & operator++()
Move the iterator one item forward (prefix notation)
Definition Skiplist.h:209
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition memory.h:84
Declaration of memory manager for allocating small pieces of memory.
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.