// skiplist.cpp

#include <iostream.h>
#include <stdlib.h>

typedef int Elem;

#define MAXLEVEL 9

class SkipNode {
  public:
    int myLevel;
    Elem value;
    SkipNode** forward;
    SkipNode(Elem r, int level) {
        myLevel = level;
        value = r;
        forward = new SkipNode* [level+1];
        for (int i=0; i<=level; i++)
            forward[i] = NULL;
  }
  ~SkipNode() { 
      delete [] forward; 
  }
};

class SkipList {
  private:
      SkipNode* head;
      int level;

      void AdjustHead(int& level) {level = MAXLEVEL;}
  public:
      SkipList() {
          head = new SkipNode(-1, MAXLEVEL);
          level = MAXLEVEL;
      }
      Elem search(int);
      void insert(Elem);
      void dump() {
          SkipNode* temp = head;
          int flag = 1;

          for ( ; temp!= NULL; temp = temp->forward[0]) {
              cout << "temp->value is " << temp->value << endl;
              for(int i=0; i<=temp->myLevel && flag != 0; i++)
                  if (temp->forward[i] == NULL){
                      cout << " rest of list is empty" << endl;
		      flag = 0;
		  }
                  else
                      cout<<"  point to "<<temp->forward[i]->value<<"\n";
          }
      }
};

int main() {
  SkipList S;
  cout << "Insert 10" << endl;
  S.insert(10);
  S.dump();
  cout << "Insert 20" << endl;
  S.insert(20);
  S.dump();
  cout << "Insert 15" << endl;
  S.insert(15);
  S.dump();
  cout << "Insert 200" << endl;
  S.insert(200);
  S.dump();
  cout << "Insert 5" << endl;
  S.insert(5);
  S.dump();
  cout << S.search(5) << endl;
  cout << S.search(210) << endl;
  cout << S.search(17) << endl;
  cout << S.search(20) << endl;
  cout << S.search(200) << endl;
  S.dump();
  return 0;
}

int randomLevel(void) { // Pick a level on exponential distribution
  int level;
  for (level=0; (random()%2) == 0; level++); // Do nothing
  return level;
}

Elem SkipList::search(int searchKey) { // Skiplist Search
  SkipNode *x = head;                  // Dummy header node
  for (int i=level; i>=0; i--)
    while ((x->forward[i] != NULL) &&
           (x->forward[i]->value < searchKey))
      x = x->forward[i];
  x = x->forward[0];  // Move to actual record, if it exists
  if ((x != NULL) && (x->value == searchKey)) return x->value;
  else return -1;
}

void SkipList::insert(Elem newValue) { // Insert into skiplist
  SkipNode *x = head;           // Start at header node
  int i;
  int newLevel = randomLevel(); // Select level for new node

  if (newLevel > level) {       // New node will be deepest in list
    AdjustHead(newLevel);       // Add null pointers to header
    level = newLevel;
  }
  SkipNode* update[level+1];    // Update tracks end of each level
  for(i=level; i>=0; i--) { // Search for insert position
    while((x->forward[i] != NULL) &&
          (x->forward[i]->value < newValue))
      x = x->forward[i];
    update[i] = x;              // Keep track of end at level i
  }
  x = new SkipNode(newValue, newLevel); // Create new node
  for (i=0; i<=newLevel; i++) { // Splice into list
    x->forward[i] = update[i]->forward[i]; // Who x points to
    update[i]->forward[i] = x;             // Who y points to
  }
}