feat: Add normal skiplist implemention

Signed-off-by: KunoiSayami <[email protected]>

1 files changed, 195 insertions, 0 deletions

diff --git a/normal_skiplist.cpp b/normal_skiplist.cpp
new file mode 100644
index 0000000..d96f2f1
--- /dev/null
+++ b/normal_skiplist.cpp
@@ -0,0 +1,195 @@
+#include <cstdio>
+#include <iostream>
+#include <map>
+#include <memory.h>
+#include <random>
+#include <sstream>
+
+// Class to implement node
+class Node {
+public:
+  int key;
+
+  // Array to hold pointers to node of different level
+  Node **next;
+  Node(int, int);
+};
+
+Node::Node(int key, int level) {
+  this->key = key;
+
+  // Allocate memory to next
+  next = new Node *[level + 1];
+
+  // Fill next array with 0(NULL)
+  memset(next, 0, sizeof(Node *) * (level + 1));
+}
+
+// Class for Skip list
+class SkipList {
+  // Maximum level for this skip list
+  int max_level;
+
+  // P is the fraction of the nodes with level
+  // i pointers also having level i+1 pointers
+  float P;
+
+  // current level of skip list
+  int level;
+
+  // pointer to header node
+  Node *header;
+  std::mt19937 random_engine;
+
+public:
+  SkipList(int, float);
+  int randomLevel() const;
+  static Node *createNode(int, int);
+  void insertElement(int);
+  void displayList();
+};
+
+SkipList::SkipList(int max_level_, float P) {
+  this->max_level = max_level_;
+  this->P = P;
+  this->level = 0;
+
+  std::random_device randomDevice;
+  std::mt19937 randomEngine(randomDevice());
+  this->random_engine = randomEngine;
+
+  // create header node and initialize key to -1
+  header = new Node(-1, max_level_);
+}
+
+#define MT19937
+
+// create random level for node
+int SkipList::randomLevel() const {
+#ifdef MT19937
+  std::geometric_distribution<> distribution(1 - this->P);
+  return std::min(this->max_level,
+                  (int)distribution((std::mt19937 &)this->random_engine));
+#else
+  float r = (float)rand() / RAND_MAX;
+  int lvl = 0;
+  while (r < P && lvl < max_level) {
+    lvl++;
+    r = (float)rand() / RAND_MAX;
+  }
+  return lvl;
+#endif
+}
+
+// create new node
+Node *SkipList::createNode(int key, int level_) {
+  Node *n = new Node(key, level_);
+  return n;
+}
+
+// Insert given key in skip list
+void SkipList::insertElement(int key) {
+  Node *current = header;
+
+  // create update array and initialize it
+  Node *update[max_level + 1];
+  memset(update, 0, sizeof(Node *) * (max_level + 1));
+
+  /*    start from highest level of skip list
+      move the current pointer next while key
+      is greater than key of node next to current
+      Otherwise inserted current in update and
+      move one level down and continue search
+  */
+  for (int i = level; i >= 0; i--) {
+    while (current->next[i] != nullptr && current->next[i]->key < key)
+      current = current->next[i];
+    update[i] = current;
+  }
+
+  /* reached level 0 and next pointer to
+     right, which is desired position to
+     insert key.
+  */
+  current = current->next[0];
+
+  /* if current is NULL that means we have reached
+     to end of the level or current's key is not equal
+     to key to insert that means we have to insert
+     node between update[0] and current node */
+  if (current == nullptr || current->key != key) {
+    // Generate a random level for node
+    int rlevel = randomLevel();
+
+    // If random level is greater than list's current
+    // level (node with highest level inserted in
+    // list so far), initialize update value with pointer
+    // to header for further use
+    if (rlevel > level) {
+      for (int i = level + 1; i < rlevel + 1; i++)
+        update[i] = header;
+
+      // Update the list current level
+      level = rlevel;
+    }
+
+    // create new node with random level generated
+    Node *n = createNode(key, rlevel);
+
+    // insert node by rearranging pointers
+    for (int i = 0; i <= rlevel; i++) {
+      n->next[i] = update[i]->next[i];
+      update[i]->next[i] = n;
+    }
+    std::cout << "Successfully Inserted key " << key << "\n";
+  }
+}
+
+// Display skip list level wise
+void SkipList::displayList() {
+  std::cout << "\n*****Skip List*****"
+            << "\n";
+  for (int i = 0; i <= level; i++) {
+    Node *node = header->next[i];
+    std::cout << "Level " << i << ": ";
+    while (node != nullptr) {
+      std::cout << node->key << " ";
+      node = node->next[i];
+    }
+    std::cout << "\n";
+  }
+}
+
+// Driver to test above code
+int main() {
+  // Seed random number generator
+  srand((unsigned)time(nullptr));
+
+  // create SkipList object with max_level and P
+  SkipList lst(3, 0.5);
+
+#ifdef MT19937
+  std::cout << "MT19937\n";
+#endif
+
+  lst.insertElement(3);
+  lst.insertElement(6);
+  lst.insertElement(7);
+  lst.insertElement(9);
+  lst.insertElement(12);
+  lst.insertElement(19);
+  lst.insertElement(17);
+  lst.insertElement(26);
+  lst.insertElement(21);
+  lst.insertElement(25);
+  lst.displayList();
+
+  /*  int a[5] = {0};
+
+    for (int i = 0; i < 100'0000; i++) {
+      a[lst.randomLevel()]++;
+    }
+    for (int i = 0; i < 5; i++) {
+      std::cout << "a[" << i << "]: " << a[i] << std::endl;
+    }*/
+}
\ No newline at end of file