#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;
    }*/
}