Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
data_structures::SkipList Class Reference
Collaboration diagram for data_structures::SkipList:
[legend]

Public Member Functions

 SkipList ()
 
int randomLevel ()
 
void insertElement (int key, void *value)
 
void deleteElement (int key)
 
void * searchElement (int key)
 
void displayList ()
 

Private Attributes

int level
 Maximum level of the skiplist.
 
std::shared_ptr< Nodeheader
 Pointer to the header node.
 

Detailed Description

SkipList class implementation with basic methods

Constructor & Destructor Documentation

◆ SkipList()

data_structures::SkipList::SkipList ( )
inline

Skip List constructor. Initializes header, start Node for searching in the list

64  {
65  level = 0;
66  // Header initialization
67  header = std::make_shared<Node>(-1, MAX_LEVEL);
68  }

Member Function Documentation

◆ deleteElement()

void data_structures::SkipList::deleteElement ( int  key)
inline

Deletes an element by key and prints if has been removed successfully

Parameters
keyis number that is used for comparision.
133  {
135 
137  update.fill(nullptr);
138 
139  for (int i = level; i >= 0; i--) {
140  while (x->forward[i] != nullptr && x->forward[i]->key < key) {
141  x = x->forward[i];
142  }
143  update[i] = x;
144  }
145 
146  x = x->forward[0];
147 
148  bool doesnt_exist = (x == nullptr || x->key != key);
149 
150  if (!doesnt_exist) {
151  for (int i = 0; i <= level; i++) {
152  if (update[i]->forward[i] != x) {
153  break;
154  }
155  update[i]->forward[i] = x->forward[i];
156  }
157  /* Remove empty levels*/
158  while (level > 0 && header->forward[level] == nullptr) level--;
159  std::cout << "Deleted" << std::endl;
160  } else {
161  std::cout << "Doesn't exist" << std::endl;
162  }
163  }
Here is the call graph for this function:

◆ displayList()

void data_structures::SkipList::displayList ( )
inline

Display skip list level

191  {
192  std::cout << "Displaying list:\n";
193  for (int i = 0; i <= level; i++) {
194  std::shared_ptr<Node> node = header->forward[i];
195  std::cout << "Level " << (i) << ": ";
196  while (node != nullptr) {
197  std::cout << node->key << " ";
198  node = node->forward[i];
199  }
200  std::cout << std::endl;
201  }
202  }
Here is the call graph for this function:

◆ insertElement()

void data_structures::SkipList::insertElement ( int  key,
void *  value 
)
inline

Inserts elements with given key and value; It's level is computed by randomLevel() function.

Parameters
keyis number that is used for comparision
valuepointer to a value, that can be any type
90  {
91  std::cout << "Inserting" << key << "...";
94  update.fill(nullptr);
95 
96  for (int i = level; i >= 0; i--) {
97  while (x->forward[i] != nullptr && x->forward[i]->key < key) {
98  x = x->forward[i];
99  }
100  update[i] = x;
101  }
102 
103  x = x->forward[0];
104 
105  bool doesnt_exist = (x == nullptr || x->key != key);
106  if (doesnt_exist) {
107  int rlevel = randomLevel();
108 
109  if (rlevel > level) {
110  for (int i = level + 1; i < rlevel + 1; i++) update[i] = header;
111 
112  // Update current level
113  level = rlevel;
114  }
115 
117  std::make_shared<Node>(key, rlevel, value);
118  for (int i = 0; i <= rlevel; i++) {
119  n->forward[i] = update[i]->forward[i];
120  update[i]->forward[i] = n;
121  }
122  std::cout << "Inserted" << std::endl;
123 
124  } else {
125  std::cout << "Exists" << std::endl;
126  }
127  }
Here is the call graph for this function:

◆ randomLevel()

int data_structures::SkipList::randomLevel ( )
inline

Returns random level of the skip list. Every higher level is 2 times less likely.

Returns
random level for skip list
75  {
76  int lvl = 0;
77  while (static_cast<float>(std::rand()) / RAND_MAX < PROBABILITY &&
78  lvl < MAX_LEVEL) {
79  lvl++;
80  }
81  return lvl;
82  }
Here is the call graph for this function:

◆ searchElement()

void* data_structures::SkipList::searchElement ( int  key)
inline

Searching element in skip list structure

Parameters
keyis number that is used for comparision
Returns
pointer to the value of the node
170  {
172  std::cout << "Searching for " << key << std::endl;
173 
174  for (int i = level; i >= 0; i--) {
175  while (x->forward[i] && x->forward[i]->key < key) x = x->forward[i];
176  }
177 
178  x = x->forward[0];
179  if (x && x->key == key) {
180  std::cout << "Found" << std::endl;
181  return x->value;
182  } else {
183  std::cout << "Not Found" << std::endl;
184  return nullptr;
185  }
186  }
Here is the call graph for this function:

The documentation for this class was generated from the following file:
std::shared_ptr< Node >
data_structures::SkipList::level
int level
Maximum level of the skiplist.
Definition: skip_list.cpp:56
data_structures::MAX_LEVEL
constexpr int MAX_LEVEL
Maximum level of skip list.
Definition: skip_list.cpp:27
node
Definition: avltree.cpp:13
std::cout
std::array
STL class.
std::rand
T rand(T... args)
std::endl
T endl(T... args)
data_structures::SkipList::randomLevel
int randomLevel()
Definition: skip_list.cpp:75
data_structures::SkipList::header
std::shared_ptr< Node > header
Pointer to the header node.
Definition: skip_list.cpp:57
data_structures::PROBABILITY
constexpr float PROBABILITY
Current probability for "coin toss".
Definition: skip_list.cpp:28