Skiplist.hh

/****************************************************************************
 * File: Skiplist.hh
 * Author: Keith Schwarz (htiek@cs.stanford.edu)
 *
 * An implementation of a set abstraction backed by a skiplist.  A skiplist
 * is a probabilistic data structure introduced by William Pugh in his paper
 * "Skip Lists: A Probabilistic Alternative to Balanced Trees."  The skiplist
 * can be thought of as a sorted linked list where each node stores pointers
 * to a collection of nodes further down in the list, not just the next node.
 * These pointers are "stacked" on top of one another, with the topmost pointer
 * pointing furthest down in the structure, the second-to-topmost pointer
 * pointing no further than that, etc.  The bottommost level points directly to
 * the next node in the skiplist.  The skiplist structure itself maintains an
 * array of pointers stored in the same fashion.  Searches can then be done by
 * starting at the top of the pointer stack, then advancing to the indicated
 * node if its value is no greater than the key to search for, and otherwise
 * dropping down a level and repeating.
 *
 * The main advantage of a skiplist over a standard self-balancing binary 
 * search tree is that the skiplist implemention is significantly easier than
 * most balanced tree implementations.  There are no tree rotations, nor
 * "colors" or "balance factors" to keep track of.  Instead, the balancing
 * comes probabalistically with the choice of the heights of each node.
 * Moreover, the constant factors on skiplist implementations of search,
 * insert, and delete operations are often much lower than the constant factors
 * on typical balanced BSTs.
 *
 * This implementation of the skiplist uses the skiplist to represent an
 * associative array structure like the STL map.  Each entry stores a constant
 * key and mutable value, as well as the forward pointers.  The structure also
 * supports forward iterators, which can read and write entries.  However, in
 * the interests of simplicity, this implementation does not comply with the
 * associative container requirements of the C++ standard; this would require
 * an enormous amount of extra code that could complicate the implementation
 * without necessarily adding anything interesting.
 *
 * This code does contain one optimization which might make it a bit harder
 * to read.  Although any two nodes in a skiplist might support different
 * numbers of pointers, once a node is constructed the number of pointers it
 * stores is fixed.  Rather than having each node store a vector of pointers or
 * a dynamically-allocated array of pointers, I instead override the new and
 * delete operators for nodes so that when a node is constructed on the heap,
 * it is overallocated with space to store the extra pointers.  This saves an
 * indirection to locate the pointer array, since they're bundled directly with
 * the object itself.  This was mostly for my own edification (I've seen this
 * technique used before, but never implemented it myself), and I apologize if
 * it complicates the implementation.
 */
#ifndef Skiplist_Included
#define Skiplist_Included

#include <algorithm>   // For lexicographical_compare, equal, max
#include <functional>  // For less
#include <utility>     // For pair
#include <iterator>    // For iterator
#include <cstring>     // For memset
#include <cstdlib>     // For rand
#include <stdexcept>   // For out_of_range

/**
 * A map-like class backed by a skiplist.
 */
template <typename Key, typename Value, typename Comparator = std::less<Key> >
class Skiplist {
public:
  /**
   * Constructor: Skiplist(Comparator comp = Comparator());
   * Usage: Skiplist<string, int> mySkiplist;
   * Usage: Skiplist<string, int> mySkiplist(MyComparisonFunction);
   * -------------------------------------------------------------------------
   * Constructs a new, empty skiplist that uses the indicated comparator to
   * compare keys.
   */
  Skiplist(Comparator comp = Comparator());

  /**
   * Destructor: ~Skiplist();
   * Usage: (implicit)
   * -------------------------------------------------------------------------
   * Destroys the skiplist, deallocating all memory allocated internally.
   */
  ~Skiplist();

  /**
   * Copy functions: Skiplist(const Skiplist& other);
   *                 Skiplist& operator= (const Skiplist& other);
   * Usage: Skiplist<string, int> one = two;
   *        one = two;
   * -------------------------------------------------------------------------
   * Makes this skiplist equal to a deep-copy of some other skiplist.
   */
  Skiplist(const Skiplist& other);
  Skiplist& operator= (const Skiplist& other);

  /**
   * Type: iterator
   * Type: const_iterator
   * -------------------------------------------------------------------------
   * A pair of types that can traverse the elements of a skiplist in ascending
   * order.
   */
  class iterator;
  class const_iterator;

  /**
   * std::pair<iterator, bool> insert(const Key& key, const Value& value);
   * Usage: mySkiplist.insert("Skiplist", 137);
   * -------------------------------------------------------------------------
   * Inserts the specified key/value pair into the skiplist.  If an entry with
   * the specified key already existed, this function returns false paired
   * with an iterator to the extant value.  If the entry was inserted
   * successfully, returns true paired with an iterator to the new element.
   */
  std::pair<iterator, bool> insert(const Key& key, const Value& value);

  /**
   * bool erase(const Key& key);
   * Usage: mySkiplist.erase("AVL Tree");
   * -------------------------------------------------------------------------
   * Removes the entry from the skiplist with the specified key, if it exists.
   * Returns whether or not an element was erased.
   */
  bool erase(const Key& key);

  /**
   * iterator find(const Key& key);
   * const_iterator find(const Key& key);
   * Usage: if (mySkiplist.find("Skiplist") != mySkiplist.end()) { ... }
   * -------------------------------------------------------------------------
   * Returns an iterator to the entry in the skiplist with the specified key,
   * or end() as as sentinel if it does not exist.
   */
  iterator find(const Key& key);
  const_iterator find(const Key& key) const;

  /**
   * Value& operator[] (const Key& key);
   * Usage: mySkiplist["skiplist"] = 137;
   * -------------------------------------------------------------------------
   * Returns a reference to the value associated with the specified key in the
   * skiplist.  If the key is not contained in the skiplist, it will be
   * inserted into the skiplist with a default-constructed Entry as its value.
   */
  Value& operator[] (const Key& key);

  /**
   * Value& at(const Key& key);
   * const Value& at(const Key& key) const;
   * Usage: mySkiplist.at("skiplist") = 137;
   * -------------------------------------------------------------------------
   * Returns a reference to the value associated with the specified key,
   * throwing a std::out_of_range exception if the key does not exist in the
   * skiplist.
   */
  Value& at(const Key& key);
  const Value& at(const Key& key) const;

  /**
   * (const_)iterator begin() (const);
   * (const_)iterator end() (const);
   * Usage: for (Skiplist<string, int>::iterator itr = s.begin(); 
   *             itr != s.end(); ++itr) { ... }
   * -------------------------------------------------------------------------
   * Returns iterators delineating the full contents of the skiplist.  Each
   * iterator acts as a pointer to a std::pair<const Key, Entry>.
   */
  iterator begin();
  iterator end();
  const_iterator begin() const;
  const_iterator end() const;

  /**
   * size_t size() const;
   * Usage: cout << "Skiplist contains " << s.size() << " entries." << endl;
   * -------------------------------------------------------------------------
   * Returns the number of elements stored in the skiplist.
   */
  size_t size() const;

  /**
   * bool empty() const;
   * Usage: if (s.empty()) { ... }
   * -------------------------------------------------------------------------
   * Returns whether the skiplist contains no elements.
   */
  bool empty() const;

  /**
   * void swap(Skiplist& other);
   * Usage: one.swap(two);
   * -------------------------------------------------------------------------
   * Exchanges the contents of this skiplist and some other skiplist.
   */
  void swap(Skiplist& other);

private:
  /* A type representing a node in the skiplist.  This node is designed to
   * be allocated on the heap with the number of extra pointers required
   * specified as an argument to operator new.
   */
  struct Node {
    std::pair<const Key, Value> mValue; // The actual value stored here
    const size_t mLevel;                // The level of this node

    /* The first of many pointers that may be stored here.  operator new will
     * overallocate this structure to store the remaining pointers.  This
     * MUST be the final data member in this struct.
     */
    Node* mNext[1];

    /* Constructor sets up the value to the specified key/value pair. */
    Node(const Key& key, const Value& value, size_t level);

    /* operator new overallocates storage for the entry. */
    void* operator new (size_t size, size_t numPointers);

    /* Matching operator delete exists in case an exception is thrown. */
    void operator delete (void* memory);
  };

  /* A constant controlling the maximum number of pointers to store in any
   * element.
   */
  static const size_t kMaxLevel = 32; // Enough space to hold 2^32 elements

  /* An array of kMaxLevel pointers to entries in the list, all initially
   * set to NULL.
   */
  Node* mList[kMaxLevel];

  /* The maximum level of any entry actually stored in the list.  Note that
   * this is an inclusive value, and so the pointer referenced by mHighestLevel
   * is a valid pointer.
   */
  size_t mHighestLevel;

  /* The comparator to use when storing elements. */
  Comparator mComp;

  /* The number of elements in the list. */
  size_t mSize;

  /* A utility base class for iterator and const_iterator which actually
   * supplies all of the logic necessary for the two to work together.  The
   * parameters are the derived type, the type of a pointer being visited, and
   * the type of a reference being visited.  This uses the Curiously-Recurring
   * Template Pattern to work correctly.
   */
  template <typename DerivedType, typename Pointer, typename Reference>
  class IteratorBase;
  template <typename DerivedType, typename Pointer, typename Reference>
  friend class IteratorBase;

  /* Make iterator and const_iterator friends as well so they can use the
   * Node type.
   */
  friend class iterator;
  friend class const_iterator;

  /* Utility function to scan over the list and look for an entry with a given
   * key.  This function is marked const even though it returns a mutable
   * pointer into the list because the result is always wrapped up in an
   * iterator or treated correctly by the implementation function that uses
   * it.
   *
   * If the node does not exist, this function returns NULL.
   */
  Node* findNode(const Key& key) const;

  /* A variant of the above function which in addition to returning a pointer
   * to the node in question, returns the pointer stack of all pointers 
   * pointing into it at each level.  This could be rolled in to the previous
   * function, but for efficiency reasons I've kept them separate.
   */
  Node* findNodeAndPredecessors(const Key& key, Node** predecessors[]);

  /* A utility function to pick a random level for a node. */
  static size_t chooseRandomLevel();
};

/* Comparison operators for Skiplists. */
template <typename Key, typename Value, typename Comparator>
bool operator<  (const Skiplist<Key, Value, Comparator>& lhs,
                 const Skiplist<Key, Value, Comparator>& rhs);
template <typename Key, typename Value, typename Comparator>
bool operator<= (const Skiplist<Key, Value, Comparator>& lhs,
                 const Skiplist<Key, Value, Comparator>& rhs);
template <typename Key, typename Value, typename Comparator>
bool operator== (const Skiplist<Key, Value, Comparator>& lhs,
                 const Skiplist<Key, Value, Comparator>& rhs);
template <typename Key, typename Value, typename Comparator>
bool operator!= (const Skiplist<Key, Value, Comparator>& lhs,
                 const Skiplist<Key, Value, Comparator>& rhs);
template <typename Key, typename Value, typename Comparator>
bool operator>= (const Skiplist<Key, Value, Comparator>& lhs,
                 const Skiplist<Key, Value, Comparator>& rhs);
template <typename Key, typename Value, typename Comparator>
bool operator>  (const Skiplist<Key, Value, Comparator>& lhs,
                 const Skiplist<Key, Value, Comparator>& rhs);

/* * * * * Implementation Below This Point * * * * */

/* Definition of the IteratorBase type, which is used to provide a common
 * implementation for iterator and const_iterator.
 */
template <typename Key, typename Value, typename Comparator>
template <typename DerivedType, typename Pointer, typename Reference>
class Skiplist<Key, Value, Comparator>::IteratorBase {
public:
  /* Utility typedef to talk about nodes. */
  typedef typename Skiplist<Key, Value, Comparator>::Node Node;

  /* Advance operators just construct derived type instances of the proper
   * type, then advance them.
   */
  DerivedType& operator++ () {
    mCurr = mCurr->mNext[0];

    /* Downcast to our actual type. */
    return static_cast<DerivedType&>(*this);
  }
  const DerivedType operator++ (int) {
    /* Copy our current value by downcasting to our real type. */
    DerivedType result = static_cast<DerivedType&>(*this);

    /* Advance to the next element. */
    ++*this;

    /* Hand back the cached value. */
    return result;
  }

  /* Equality and disequality operators are parameterized - we'll allow anyone
   * whose type is IteratorBase to compare with us.  This means that we can
   * compare both iterator and const_iterator against one another.
   */
  template <typename DerivedType2, typename Pointer2, typename Reference2>
  bool operator== (const IteratorBase<DerivedType2, Pointer2, Reference2>& rhs) {
    /* Just check the underlying pointer, which (fortunately!) is of the same
     * type.
     */
    return mCurr == rhs.mCurr;
  }
  template <typename DerivedType2, typename Pointer2, typename Reference2>
  bool operator!= (const IteratorBase<DerivedType2, Pointer2, Reference2>& rhs) {
    /* We are disequal if equality returns false. */
    return !(*this == rhs);
  }

  /* Pointer dereference operator hands back a reference. */
  Reference operator* () const {
    return mCurr->mValue;
  }
  
  /* Arrow operator returns a pointer. */
  Pointer operator-> () const {
    /* Use the standard "&**this" trick to dereference this object and return
     * a pointer to the referenced value.
     */
    return &**this;
  }

protected:
  /* Where we are in the list. */
  Node* mCurr;

  /* In order for equality comparisons to work correctly, all IteratorBases
   * must be friends of one another.
   */
  template <typename Derived2, typename Pointer2, typename Reference2>
  friend class IteratorBase;

  /* Constructor sets up the skiplist pointer appropriately. */
  IteratorBase(Node* curr = NULL) : mCurr(curr) {
    // Handled in initializer list
  }
};

/* iterator and const_iterator implementations work by deriving off of
 * IteratorBase, passing in parameters that make all the operators work.
 * Additionally, we inherit from std::iterator to import all the necessary
 * typedefs to qualify as an iterator.
 */
template <typename Key, typename Value, typename Comparator>
class Skiplist<Key, Value, Comparator>::iterator:
  public std::iterator< std::forward_iterator_tag,
                        std::pair<const Key, Value> >,
  public IteratorBase<iterator,                       // Our type
                      std::pair<const Key, Value>*,   // Reference type
                      std::pair<const Key, Value>&> { // Pointer type 
public:
  /* Default constructor forwards NULL to base implicity. */
  iterator() {
    // Nothing to do here.
  }

  /* All major operations inherited from the base type. */

private:
  /* Constructor for creating an iterator out of a raw node just forwards this
   * argument to the base type.  This line is absolutely awful because the
   * type of the base is so complex.
   */
  iterator(typename Skiplist<Key, Value, Comparator>::Node* node) :
    IteratorBase<iterator,
                 std::pair<const Key, Value>*,
                 std::pair<const Key, Value>&>(node) {
    // Handled by initializer list
  }

  /* Make the Skiplist a friend so it can call this constructor. */
  friend class Skiplist;

  /* Make const_iterator a friend so it can steal the pointer when doing an
   * iterator-to-const_iterator conversion.
   */
  friend class const_iterator;
};

/* Same as above, but with const added in. */
template <typename Key, typename Value, typename Comparator>
class Skiplist<Key, Value, Comparator>::const_iterator:
  public std::iterator< std::forward_iterator_tag,
                        const std::pair<const Key, Value> >,
  public IteratorBase<const_iterator,                       // Our type
                      const std::pair<const Key, Value>*,   // Reference type
                      const std::pair<const Key, Value>&> { // Pointer type 
public:
  /* Default constructor forwards NULL to base implicity. */
  const_iterator() {
    // Nothing to do here.
  }

  /* Conversion constructor from the iterator type initializes the base class
   * as a copy of the iterator's base fields.
   */
  const_iterator(iterator itr) :
    IteratorBase<const_iterator,
                 const std::pair<const Key, Value>*,
                 const std::pair<const Key, Value>&>(itr.mCurr) {
    // Handled in initializer list.
  }

  /* All major operations inherited from the base type. */

private:
  /* See iterator implementation for details about what this does. */
  const_iterator(typename Skiplist<Key, Value, Comparator>::Node* node) :
    IteratorBase<const_iterator,
                 const std::pair<const Key, Value>*,
                 const std::pair<const Key, Value>&>(node) {
    // Handled by initializer list
  }
  
  /* Make the Skiplist a friend so it can call this constructor. */
  friend class Skiplist;
};

/**** Skiplist::Node Implementation. ****/

/* Constructor initializes the key/value pair using its arguments. */
template <typename Key, typename Value, typename Comparator>
Skiplist<Key, Value, Comparator>::Node::Node(const Key& key, const Value& value, size_t level) 
  : mValue(key, value), mLevel(level) {
  // Handled in initializer list
}

/* operator new overallocates space so that there are sufficiently many
 * pointers available off the end of the struct.
 */
template <typename Key, typename Value, typename Comparator>
void* Skiplist<Key, Value, Comparator>::Node::operator new (size_t size, size_t numPointers) {
  /* The Node itself contains one pointer, so we need to allocate space for
   * numPointers - 1 extra pointers.
   */
  const size_t spaceNeeded = size + (numPointers - 1) * sizeof(Node*);
  void* result = ::operator new(spaceNeeded);

  /* Zero out the memory; we want to ensure that the pointers are zeroed
   * before continuing.
   */
  std::memset(result, 0, spaceNeeded);

  return result;
}

/* operator delete implementation exists in case the constructor throws an
 * exception.  This should never happen, but we should put this here anyway
 * in case a future version ends up throwing.
 */
template <typename Key, typename Value, typename Comparator>
void Skiplist<Key, Value, Comparator>::Node::operator delete(void* memory) {
  /* This can be handled using the default operator delete implementation. */
  ::operator delete(memory);
}

/**** Skiplist Implementation ****/

/* Constructor zeros out relevant fields. */
template <typename Key, typename Value, typename Comparator>
Skiplist<Key, Value, Comparator>::Skiplist(Comparator comp) : mComp(comp) {
  /* Set all of the node pointers to NULL. */
  std::memset(mList, 0, sizeof(mList));

  /* Our highest level is zero, since none of the pointers are valid. */
  mHighestLevel = 0;

  /* Our size is zero, since we currently have no elements. */
  mSize = 0;
}

/* Destructor walks across the skiplist, deleting elements. */
template <typename Key, typename Value, typename Comparator>
Skiplist<Key, Value, Comparator>::~Skiplist() {
  /* Walk across the bottom of the list. */
  Node* curr = mList[0];
  while (curr != NULL) {
    /* Cache where to go next, since we're about to destroy our last reference
     * to it.
     */
    Node* next = curr->mNext[0];

    /* Free memory, then advance to the next location. */
    delete curr;
    curr = next;
  }
}

/* begin hands back a (const_)iterator initialized to the head of the list. */
template <typename Key, typename Value, typename Comparator>
typename Skiplist<Key, Value, Comparator>::iterator
Skiplist<Key, Value, Comparator>::begin() {
  return iterator(mList[0]); // Scan bottom row
}
template <typename Key, typename Value, typename Comparator>
typename Skiplist<Key, Value, Comparator>::const_iterator
Skiplist<Key, Value, Comparator>::begin() const {
  return const_iterator(mList[0]); // Scan bottom row
}

/* end hands back a (const_)iterator initialized to NULL, which comes one step
 * past the end of the list.
 */
template <typename Key, typename Value, typename Comparator>
typename Skiplist<Key, Value, Comparator>::iterator
Skiplist<Key, Value, Comparator>::end() {
  return iterator(NULL);
}
template <typename Key, typename Value, typename Comparator>
typename Skiplist<Key, Value, Comparator>::const_iterator
Skiplist<Key, Value, Comparator>::end() const {
  return const_iterator(NULL);
}

/* We cache the size to simplify this implementation. */
template <typename Key, typename Value, typename Comparator>
size_t Skiplist<Key, Value, Comparator>::size() const {
  return mSize;
}

/* Checking for emptiness just checks whether the stored size is zero. */
template <typename Key, typename Value, typename Comparator>
bool Skiplist<Key, Value, Comparator>::empty() const {
  return size() == 0;
}

/* Checking whether an element exists involves scanning over the skiplist
 * level-by-level looking for the key.
 */
template <typename Key, typename Value, typename Comparator>
typename Skiplist<Key, Value, Comparator>::Node*
Skiplist<Key, Value, Comparator>::findNode(const Key& key) const {
  /* At each step, we need to maintain an array of pointers containing
   * possible places to look.  This is initially the skiplist's own master
   * list of pointers.
   */
  Node* const* table = mList;

  /* The scan works as follows.  We start at the topmost level and continue
   * advancing along it as long as the next node exists and has a key that is
   * less than the key in question.  We then drop one level down and repeat
   * this process until we finish scanning the bottom level.
   *
   * During this scan, we use integers to encode the level so that if we drop
   * below the first level, we don't integer-overflow up to some outrageously
   * high level.
   */
  for (int level = int(mHighestLevel); level >= 0; --level)
    while (table[level] && mComp(table[level]->mValue.first, key))
      table = table[level]->mNext;

  /* Finally, once we've hit the bottom, we're looking at a pointer stack that
   * comes right before the node we want (if it exists) or some other random
   * node if the entry doesn't exist.  Check which of these two cases holds.
   */
  if (table[0] &&                            // Entry exists
      !mComp(key, table[0]->mValue.first) && // ... and isn't less than key
      !mComp(table[0]->mValue.first, key))   // ... and isn't greater than key
    return table[0];

  /* Otherwise we didn't find it. */
  return NULL;
}

/* Both versions of find work by calling findNode and then wrapping up the
 * result.
 */
template <typename Key, typename Value, typename Comparator>
typename Skiplist<Key, Value, Comparator>::iterator
Skiplist<Key, Value, Comparator>::find(const Key& key) {
  return iterator(findNode(key));
}
template <typename Key, typename Value, typename Comparator>
typename Skiplist<Key, Value, Comparator>::const_iterator
Skiplist<Key, Value, Comparator>::find(const Key& key) const {
  return const_iterator(findNode(key));
}

/* Checking whether an element exists involves scanning over the skiplist
 * level-by-level looking for the key.
 */
template <typename Key, typename Value, typename Comparator>
typename Skiplist<Key, Value, Comparator>::Node*
Skiplist<Key, Value, Comparator>::findNodeAndPredecessors(const Key& key,
                                                          Node** predecessors[]) {
  /* At each step, we need to maintain an array of pointers containing
   * possible places to look.  This is initially the skiplist's own master
   * list of pointers.
   */
  Node** table = mList;

  /* The scan works as follows.  We start at the topmost level and continue
   * advancing along it as long as the next node exists and has a key that is
   * less than the key in question.  We then drop one level down and repeat
   * this process until we hit the bottom level.  At the end of each scan,
   * we record the last pointer we found.
   */
  for (int level = int(mHighestLevel); level >= 0; --level) {
    /* Walk forward as far as possible. */
    while (table[level] && mComp(table[level]->mValue.first, key))
      table = table[level]->mNext;

    /* Record this entry. */
    predecessors[level] = &table[level];
  }

  /* Finally, once we've hit the bottom, we're looking at a pointer stack that
   * comes right before the node we want (if it exists) or some other random
   * node if the entry doesn't exist.  Check which of these two cases holds.
   */
  if (table[0] &&                            // Entry exists
      !mComp(key, table[0]->mValue.first) && // ... and isn't less than key
      !mComp(table[0]->mValue.first, key))   // ... and isn't greater than key
    return table[0];

  /* Otherwise we didn't find it. */
  return NULL;
}

/* Picks a random level for a node by advancing upward and upward with
 * uniform probability.
 */
template <typename Key, typename Value, typename Comparator>
size_t Skiplist<Key, Value, Comparator>::chooseRandomLevel() {
  /* We advance to a new level with probability 1/4 at each point, as suggested
   * by the original paper.  To do this with a minimum of floating-point
   * computations, we compute RAND_MAX / 4 and then go up a level every time
   * rand() is no greater than this value.
   */
  static const int kLevelProbability = RAND_MAX / 4;

  /* In the worst case, we have one level of pointers. */
  size_t result = 1;

  /* Loop while we keep choosing to promote and while the level is no larger
   * than the max level.
   */
  while (rand() < kLevelProbability && result < kMaxLevel)
    ++result;

  return result;
}

/* Insertion into the skiplist works by building up the predecessors, then
 * inserting the new node with some arbitrary height at the indicated spot.
 */
template <typename Key, typename Value, typename Comparator>
std::pair<typename Skiplist<Key, Value, Comparator>::iterator, bool>
Skiplist<Key, Value, Comparator>::insert(const Key& key, const Value& value) {
  /* Begin by calling the find predecessors function to determine what comes
   * right before this node.
   */
  Node** predecessors[kMaxLevel];
  Node* entry = findNodeAndPredecessors(key, predecessors);

  /* If this node already exists, hand back an iterator to it, marking that
   * we didn't insert anything.
   */
  if (entry != NULL)
    return std::make_pair(iterator(entry), false);

  /* Otherwise, we need to actually insert the node here.  Begin by picking
   * a random level for it.
   */
  const size_t level = chooseRandomLevel();

  /* Create the node object to hold the key/value pair.  We pass the level as
   * an argument to new to ensure space exists for the pointers.
   */
  Node* node = new (level) Node(key, value, level);

  /* To splice this node into the list, we'll make all of its outgoing
   * pointers on each of its levels point to the location the predecessor used
   * to be pointing.  We'll also change the predecessors to point to this
   * node instead of where they were pointing.
   */
  for (size_t i = 0; i < level; ++i) {
    /* If this level exceeds the maximum level, then the predecessor is the
     * root noot and not whatever garbage coincidentally happened to be in
     * the array.
     */
    if (i > mHighestLevel) {
      node->mNext[i] = NULL;
      mList[i] = node;
    }
    /* Otherwise, the predecessor is what was stored in the table. */
    else {
      node->mNext[i] = *predecessors[i];
      *predecessors[i] = node;
    }
  }

  /* Update the max level stored in the list in case this is the new
   * largest element.
   */
  mHighestLevel = std::max(mHighestLevel, level);

  /* Increase the size, since we just added an entry. */
  ++mSize;

  /* Return an iterator to the new element, paired with true because something
   * was added.
   */
  return std::make_pair(iterator(node), true);
}

/* The const version of at uses findNode to locate the element, then complains
 * if nothing was found.
 */
template <typename Key, typename Value, typename Comparator>
const Value& Skiplist<Key, Value, Comparator>::at(const Key& key) const {
  /* Look up the node and return its value if found. */
  if (Node* node = findNode(key))
    return node->mValue.second;
  throw std::out_of_range("Key does not exist in skiplist.");
}

/* Non-const version implemented in terms of const version using the
 * const_cast/static_cast trick.
 */
template <typename Key, typename Value, typename Comparator>
Value& Skiplist<Key, Value, Comparator>::at(const Key& key) {
  return const_cast<Value&>(static_cast<const Skiplist*>(this)->at(key));
}

/* operator[] implemented by inserting a dummy element with insert, then using
 * the returned iterator to extract the value.
 */
template <typename Key, typename Value, typename Comparator>
Value& Skiplist<Key, Value, Comparator>::operator[] (const Key& key) {      
  return insert(key, Value()).first->second;
}

/* Erasing an element works by locating its predecessors, then wiring them
 * around the element to be deleted.
 */
template <typename Key, typename Value, typename Comparator>
bool Skiplist<Key, Value, Comparator>::erase(const Key& key) {
  /* Begin by calling the find predecessors function to determine what comes
   * right before this node.
   */
  Node** predecessors[kMaxLevel];
  Node* entry = findNodeAndPredecessors(key, predecessors);

  /* If the node doesn't exist, we don't have any work to do. */
  if (entry == NULL)
    return false;

  /* We now need to take this node out of the list.  We do this by walking
   * over its predecessors and rewiring them to point to the element that
   * comes right after the element.
   */
  for (size_t i = 0; i < entry->mLevel; ++i)
    *predecessors[i] = entry->mNext[i];

  /* Actually delete the node to ensure that the memory isn't leaked. */
  delete entry;

  /* Determine if the level of the list needs to be updated.  We do this by
   * marching downward across the master pointer table, decrementing the count
   * every time we find a null entry.
   */
  while (mHighestLevel > 0 && mList[mHighestLevel] == NULL)
    --mHighestLevel;

  /* Decrement the size, since we just lost an entry. */
  --mSize;

  /* Hand back true, since something was removed. */
  return true;
}

/* Copy constructor deep-copies the other list by inserting all of the other
 * list's elements into this list one at a time.  This is by no means the most
 * efficient way to accomplish this, but it's simple to implement and avoids
 * all sorts of awful pointer wrangling.
 */
template <typename Key, typename Value, typename Comparator>
Skiplist<Key, Value, Comparator>::Skiplist(const Skiplist& other) : mComp(other.mComp) {
  /* Clear out the pointers, size fields, etc. */
  std::memset(mList, 0, sizeof(mList));
  mHighestLevel = mSize = 0;

  /* Add all of the elements from the other list to this list. */
  for (const_iterator itr = other.begin(); itr != other.end(); ++itr)
    insert(itr->first, itr->second);
}

/* Assignment operator implemented using the copy-and-swap approach. */
template <typename Key, typename Value, typename Comparator>
Skiplist<Key, Value, Comparator>& 
Skiplist<Key, Value, Comparator>::operator= (const Skiplist& other) {
  Skiplist clone = other;
  clone.swap(*this);
  return *this;
}

/* swap just uses the standard swap function to exchange the contents of this
 * skiplist and the other skiplist.
 */
template <typename Key, typename Value, typename Comparator>
void Skiplist<Key, Value, Comparator>::swap(Skiplist& other) {
  /* Swap pointers. */
  for (size_t i = 0; i < kMaxLevel; ++i)
    std::swap(mList[i], other.mList[i]);

  /* Swap sizes and heights. */
  std::swap(mSize, other.mSize);
  std::swap(mHighestLevel, other.mHighestLevel);

  /* Exchange comparators so we don't end up using the wrong comparison
   * functions.
   */
  std::swap(mComp, other.mComp);
}

/* Comparison operators == and < use the standard STL algorithms. */
template <typename Key, typename Value, typename Comparator>
bool operator<  (const Skiplist<Key, Value, Comparator>& lhs,
                 const Skiplist<Key, Value, Comparator>& rhs) {
  return std::lexicographical_compare(lhs.begin(), lhs.end(),
                                      rhs.begin(), rhs.end());
}
template <typename Key, typename Value, typename Comparator>
bool operator== (const Skiplist<Key, Value, Comparator>& lhs,
                 const Skiplist<Key, Value, Comparator>& rhs) {
  return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), 
                                                rhs.begin());
}

/* Remaining comparisons implemented in terms of the above comparisons. */
template <typename Key, typename Value, typename Comparator>
bool operator<= (const Skiplist<Key, Value, Comparator>& lhs,
                 const Skiplist<Key, Value, Comparator>& rhs) {
  /* x <= y   iff !(x > y)   iff !(y < x) */
  return !(rhs < lhs);
}
template <typename Key, typename Value, typename Comparator>
bool operator!= (const Skiplist<Key, Value, Comparator>& lhs,
                 const Skiplist<Key, Value, Comparator>& rhs) {
  return !(lhs == rhs);
}
template <typename Key, typename Value, typename Comparator>
bool operator>= (const Skiplist<Key, Value, Comparator>& lhs,
                 const Skiplist<Key, Value, Comparator>& rhs) {
  /* x >= y   iff !(x < y) */
  return !(lhs < rhs);
}
template <typename Key, typename Value, typename Comparator>
bool operator>  (const Skiplist<Key, Value, Comparator>& lhs,
                 const Skiplist<Key, Value, Comparator>& rhs) {
  /* x > y iff y < x */
  return rhs < lhs;
}

#endif