/* SI 486D Spring 2013
   This is a skeleton for a skip list class that only supports
   insertion of height-1 nodes.

   Nodes are stored in "towers" which contain a list of forward-facing
   links ("flinks"), as well as a key and a value.

   To demo on a small random example, run "make skiplist && ./skiplist"
*/

#include <cstdlib>
#include <limits>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

template <typename V>
class SkipList {
 protected:
  struct Tower {
    double key;
    V value;
    vector<Tower*> flinks;

    Tower(int h, double key, V value) {
      this->key = key;
      this->value = value;
      this->flinks.insert(this->flinks.begin(), h+1, static_cast<Tower*>(NULL));
    }
  };

  Tower* start;
  Tower* end;
  int thesize;

 public:
  SkipList() {
    this->start = new Tower(0, -numeric_limits<double>::infinity(), V());
    this->end = new Tower(0, numeric_limits<double>::infinity(), V());
    this->start->flinks[0] = this->end;
    this->thesize = 0;
  }

  int height() {
    return this->start->flinks.size()- 1;
  }

  int size() {
    return this->thesize;
  }

  void insert(double key, V value) {
    int h = 1; // TODO: choose height randomly!
    Tower* newTower = new Tower(h, key, value);

    // Grow height of start/end as needed
    while (h >= height()) {
      this->start->flinks.push_back(this->end);
      this->end->flinks.push_back(NULL);
    }

    Tower* currentTower = this->start;
    int level = currentTower->flinks.size()-1;
    while (level >= 0) {
      if (key > currentTower->flinks[level]->key) {
        // Move right if we can on this level
        currentTower = currentTower->flinks[level];
      } 
      else {
        // Otherwise go down a level
        if (level <= h) {
          // Insert the new tower on this level
          newTower->flinks[level] = currentTower->flinks[level];
          currentTower->flinks[level] = newTower;
        }
        level -= 1;
      }
    }

    this->thesize += 1;
  }

  void print(ostream& out = cout) {
    /* Prints a nice pretty representation of the skip list */
    for (int level = height(); level >= 0; --level) {
      Tower* currentTower = this->start;
      while (currentTower != this->end) {
        stringstream ss;
        ss << "(" << currentTower->key << ")";
        if (level >= currentTower->flinks.size()) {
          for (int i=0; i < ss.str().length(); ++i) out << "-";
        }
        else { out << ss.str(); }
        out << "--";
        currentTower = currentTower->flinks[0];
      }
      out << "(" << currentTower->key << ")\n";
    }
  }

};

int main() {
  unsigned long rseed;
  ifstream rin("/dev/urandom");
  rin.read((char*)&rseed, sizeof(rseed));
  rin.close();
  srand(rseed);

  // Randomly insert 10 numbers and print the resulting skip list
  SkipList<string> S;
  for (int i=0; i<10; ++i) {
    S.insert(rand() % 64, "this is the value");
  }
  S.print();

  return 0;
}