1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

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