Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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