#include <limits>  // Needed for std::numeric_limits.

template <class T>
class simple_skiplist_dictionary
{

  struct node
  {
    T data;
    node ** next;
    node(const T & x, int l) : data(x)
    {
      next = new node*[l + 1];
    }
  };

  static const int absolute_max_level;

  int max_level;
  node * head;

  // A simple RNG.
  bool coin_flip() 
  {
    static unsigned long x = 12241967;
    x = x * 3141592621UL + 1;
    return x > std::numeric_limits<unsigned long>::max() / 2;
  }

public:

  simple_skiplist_dictionary() : head(new node(T(), 0)), max_level(0) 
  {
    head->next[0] = 0;
  }

  bool lookup(const T & x) 
  {
    int level = max_level;
    node * p = head;
    do
    {
      while (p->next[level] && p->next[level]->data <= x)
        p = p->next[level];
      if (p != head && p->data == x)
        return true;
    } while (level-- > 0);
    return false;
  }

  void insert(const T & x)
  {
    // Find pred pointer at each level.
    node * pred[absolute_max_level + 1];
    int level = max_level;
    node * p = head;
    do 
    {
      while (p->next[level] && p->next[level]->data <= x)
        p = p->next[level];
      if (p != head && p->data == x)
        return;
      else
        pred[level] = p;
    } while (level-- > 0);

    // Randomly determine level of new node.
    int new_level = 0;
    while (coin_flip() && new_level < absolute_max_level)
      ++new_level;
    node * n = new node(x, new_level);
    
    // Increase level of head node if max_level increases.
    int old_level = max_level;
    if (new_level > max_level)
    {
      node ** new_head_next = new node*[new_level + 1];
      max_level = new_level;
      int i;
      for (i=0; i <= old_level; ++i)
        new_head_next[i] = head->next[i];
      delete head->next;
      head->next = new_head_next;
      for (; i <= max_level; ++i)
      {
        head->next[i] = n;
        n->next[i] = 0;
      }
    }

    // Insert the new node.
    for (int i=0; i <= old_level; ++i)
    {
      n->next[i] = pred[i]->next[i];
      pred[i]->next[i] = n;
    }
  }

  void erase(const T & x)
  {
    int level = max_level;
    node * p = head;
    node * n = 0;
    do
    {
      while (p->next[level] && p->next[level]->data < x)
        p = p->next[level];
      if (p->next[level] && p->next[level]->data == x)
      {
        n = p->next[level];
        p->next[level] = p->next[level]->next[level];
      }
    } while (level-- > 0);
    delete n;
  }
};

template <class T>
const int simple_skiplist_dictionary<T>::absolute_max_level = 32;