#include <iostream>
#include <vector>
#include <stdlib.h>
#include <math.h>
#include <assert.h>

using namespace std;

// Predeclarations
class SkipList;
ostream& operator << (ostream&, const SkipList&);

// This is our new awesome data structure
class SkipList
{
  // We would like to be able to print the contents of this data structure
  friend ostream& operator << (ostream&, const SkipList&);
public:
  // An empty SkipList
  SkipList();
  
  // Insert into the SkipList
  void insert(int toInsert);

  // Remove an element (if it exists) from the SkipList
  void remove(int toRemove);
  
  // Does the given element occur in this list?
  bool find(int toFind);

private:
  // The list node type for this class
  class SkipListNode
  {
  public:
    // Default
    SkipListNode();

    // Give a value and the number of levels that this entry exists on
    SkipListNode(int val, int levels);

    // The value held in this node
    int val;

    // The pointers to the other things "adjacent" to this entry
    // on each of the levels it exists on (only forward pointers)
    vector<SkipListNode*> nexts;
  };

  // This actually returns a SkipListNode whose "nexts" fields all
  // point at the _previous_ entry at that level or above.
  SkipListNode findInsertPoint(int val, int levels);

  // Given a value, find the node corresponding to it, or return NULL
  SkipListNode* findNode(int val);

  // The head of the list.
  SkipListNode head;


};


// Empty constructor.  We guess 5 for the initial height, that'll 
// allow us an average of 2^5 = 32 entries before having to resize
// the nexts in head.
SkipList::SkipList()
  : head(0, 5)
{

}

// Construct a SkipListNode
SkipList::SkipListNode::SkipListNode(int _val, int levels)
  : val(_val),
    nexts(levels)
{
  // Zero out all the nexts
  for (int i = 0; i < levels; i++)
    nexts[i] = NULL;
}

// Basically the same as above
SkipList::SkipListNode::SkipListNode()
  : val(0),
    nexts(5)
{
  // Zero out all the nexts
  for (int i = 0; i < 5; i++)
    nexts[i] = NULL;
}

// Find where we would insert and return a SkipListNode with
// the nexts fields pointing at the _previous_ node that has
// an entry at level i or above.  (This way we can update the
// nexts for everyone we care about.)
// This is really the hardest part of the entire data structure
SkipList::SkipListNode SkipList::findInsertPoint(int val, int levels)
{
  // The level we are starting at
  int level = levels - 1;

  // This will be our return value
  SkipListNode ret(0, levels);

  // We are starting at the first non-head entry on the highest 
  // level
  SkipListNode* cur = head.nexts[level];

  // Track prev so we don't have to do any O(n) operations
  SkipListNode* prev = &head;

  // Now loop down through the levels
  while (level >= 0)
    {
      // Loop until prev and cur surround where we would insert at
      // this level.
      while (cur != NULL && cur->val < val)
	{
	  prev = cur;
	  cur = cur->nexts[level];
	}
      // Now we know the previous entry at this level.
      ret.nexts[level] = prev;

      // This is primarily for debugging, but it also expresses
      // nicely what we know to be true: cur and prev surround
      // the value we are looking for
      assert((cur == NULL || cur->val >= val) && 
	     (prev == &head || prev->val <= val));

      // Now back up one, and go down a level and continue
      cur = prev;
      level--;
    }

  // Now we've filled in everything, we are done
  return ret;
}

// Insert a value
void SkipList::insert(int val)
{
  // No duplicates
  if (find(val)) return;
  
  // Start out knowing that it will exist on at least 1 level (level 0)
  int levels = 1;
  
  // This is the coin-flip stage: while we get "heads", incremement
  // the number of levels.  Some implementations put a cap on this,
  // I'm just trusting in probability.
  while (rand() % 2) levels++;

  // If we are inserting at a level higher than the head knows about,
  // then we had better inform the head.
  if ((int)head.nexts.size() < levels) head.nexts.resize(levels);

  // Find the previous nodes
  SkipListNode lookBack = findInsertPoint(val, levels);

  // This is our new node
  SkipListNode* newNode = new SkipListNode(val, levels);

  // Stitch it in
  for (int i = 0; i < levels; i++)
    {
      // The next of us should be set to the next of the previous node.
      newNode->nexts[i] = lookBack.nexts[i]->nexts[i];

      // The next of the previous node needs to point to us
      lookBack.nexts[i]->nexts[i] = newNode;
    }

  // The surgery was a success.
}

// Find a given node in the list
SkipList::SkipListNode* SkipList::findNode(int val)
{
  // We will start looking at the highest level
  int level = head.nexts.size() - 1;

  // Cur is the first thing in that level
  SkipListNode* cur = head.nexts[level];

  // Prev is head
  SkipListNode* prev = &head;

  // If there is nothing IN that level, just move down, it
  // won't help us to search it
  while (cur == NULL)
    {
      level--;
      if (level < ) return NULL;
      cur = head.nexts[level];
    }

  // Now, the real search: while we haven't gotten to the
  // bottom, and while we haven't found what we are looking for
  while (level >= 0 and cur->val != val)
    {
      // Move until we have val surrounded: prev->val < val < cur->val 
      while (cur != NULL && cur->val < val)
	{
	  prev = cur;
	  cur = cur->nexts[level];
	}
      
      // If we found it, we're done
      if (cur && cur->val == val) return cur;

      // Otherwise, continue the search on the next level.
      cur = prev;
      level--;
    }

  // Ife we didn't find it, we failed
  if (level < 0 || cur == &head) return NULL;

  // Otherwise, this ought to be the right one.
  return cur;
}

// The publicly usable find: does it exist?
bool SkipList::find(int val)
{
  // It exists if and only if we could find a node that holds it
  return findNode(val) != NULL;
}

// Rather like insert
void SkipList::remove(int val)
{
  // Find the node to remove
  SkipListNode* toRemove = findNode(val);

  // Didn't exist, we're done
  if (toRemove == NULL) return;

  // We need to remove it from those levels it exists on
  int level = toRemove->nexts.size() - 1;

  // Find the back pointers
  SkipListNode lookBack = findInsertPoint(val, level + 1);
  
  // Remove from each level
  while (level >= 0)
    {
      // prev->next = cur->next
      lookBack.nexts[level]->nexts[level] = toRemove->nexts[level];      
      level--;
    }

  // And clear it up
  delete toRemove;

}

// We'd like to be able to print this out
ostream& operator << (ostream& toStream, const SkipList& rhs)
{
  // Start at the front
  SkipList::SkipListNode* current = rhs.head.nexts[0];

  // If there is anything in the list, print the first one
  if (current)
    {
      toStream << current->val;
      current = current->nexts[0];
    }

  // Now print the rest as " " + val.  (This way we don't get
  // and extra annoying " " at the end of the list.  
  while (current != NULL)
    {
      toStream << " " << current->val;
      current = current->nexts[0];
    }

  // Return the stream
  return toStream;
}

int main()
{
  // THIS is absolutely necessary.  The annoying part is that 
  // to really do this properly, the skip list would need a unique
  // individual random number stream.  Isn't worth it for this demonstration.
  srand(time(0));

  // An empty list
  SkipList sl;

  // Insert some things by hand, in order and out of order
  sl.insert(10);
  sl.insert(11);
  sl.insert(12);
  sl.insert(13);
  sl.insert(9);
  sl.insert(100);
  cout << sl << endl;

  // Now insert 10 other random things
  for (int i = 0; i < 10; i++)
    {
      sl.insert(rand() % 100000);
    }

  cout << sl << endl;

  // Now do a very slow check of everything that could be in the list
  for (int i = 0 ; i < 100000; i++)
    {
      if (sl.find(i)) cout << i << endl;
    }

  // And remove every odd number from the list
  for (int i = 0; i < 100000; i++)
    {
      if (sl.find(i) and i % 2) 
	{
	  sl.remove(i);
	  cout << sl << endl;
	}
    }

}