template <class T>
class list 
{
private:
  // The data structure is a circular doubly-linked list of nodes.
  // A dummy header node is kept, which makes inserting and erasing
  // nodes easier because their is never a null pointer in the list.
  // Note that this means that an iterator to the "end" position 
  // is actually a pointer to the header node.
  struct node {
    node * next;
    node * prev;
    T data;
    node() {}
    node(const T & x) : data(x) {}
  };

  node * head;

public:      
  typedef T value_type;

  friend class iterator;
  class iterator {
  private:
    // An iterator is just a wrapper around a pointer to a node.
    node * ptr;

    // Allow list operations to directly manipulate the pointer.
    friend class list;

  public:
    typedef T value_type;
    typedef T * pointer;
    typedef T & reference;
    typedef int size_type;
    typedef int difference_type;

    iterator() {}
    iterator(node * x) : ptr(x) {}
    iterator(const iterator & x) : ptr(x.ptr) {}

    bool operator==(const iterator & x) const { return ptr == x.ptr; }
    bool operator!=(const iterator & x) const { return ptr != x.ptr; }

    T & operator*() const { return ptr->data; }
    T * operator->() const { return &(ptr->data); }

    iterator & operator++() 
    { 
      ptr = ptr->next;
      return *this;
    }
    iterator operator++(int) 
    { 
      iterator tmp = *this;
      ++*this;
      return tmp;
    }
    iterator & operator--() 
    { 
      ptr = ptr->prev;
      return *this;
    }
    iterator operator--(int) 
    { 
      iterator tmp = *this;
      --*this;
      return tmp;
    }
  };

  // For brevity, const_iterator is omitted.
  // It would look largely identical to the above with const
  // in appropriate places.

  list()
  {
    head = new node;
    head->next = head;
    head->prev = head;
  }

  ~list()
  {
    clear();
    delete head;
  }

  explicit list(size_type n, const T & value = T())
  { 
    while (n > 0)
    {
      insert(begin(), value);
      --n;
    }
  }

  list(const list & x)
  { 
    node * cur = x.head->prev;
    while (cur != x.head)
    {
      insert(begin(), cur->data); 
      cur = cur->prev;
    }
  }

  iterator begin() { return head->next; }
  iterator end() { return head; }

  bool empty() const { return head->next == head; }
  size_type size() const { return std::distance(begin(), end(), result); }

  T & front() { return *begin(); }
  T & back() { return *(--end()); }

  void swap(list & x) { std::swap(head, x.head); }

  iterator insert(iterator position, const T & x) 
  {
    node * tmp = new node(x);
    tmp->next = position.ptr;
    tmp->prev = position.ptr->prev;
    position.ptr->prev->next = tmp;
    position.ptr->prev = tmp;
    return tmp;
  }

  void push_front(const T & x) { insert(begin(), x); }
  void push_back(const T & x) { insert(end(), x); }

  iterator erase(iterator position) 
  {
    node * next_node = position.ptr->next;
    node * prev_node = position.ptr->prev;
    prev_node->next = next_node;
    next_node->prev = prev_node;
    delete position.ptr;
    return next_node;
  }

  // This is more efficient than erasing each element individually.
  void clear()
  {
    node * cur = head->next;
    while (cur != head) 
    {
      node * tmp = cur;
      cur = cur->next;
      delete tmp;
    }
    head->next = node;
    head->prev = node;
  }

  void pop_front() { erase(begin()); }
  void pop_back() 
  { 
    iterator tmp = end();
    --tmp;
    erase(tmp);
  }

  list & operator=(const list & x)
  {
    if (this != &x) 
    {
      // A simple way to do this would be to clear the list and then
      // rebuild it, copying data from the nodes in list x as in the
      // copy constructor.
      // Instead, for efficiency we will reuse any existing nodes in 
      // the list being assigned to.  We proceed in two steps:

      // First copy data from list x, using existing nodes,
      // until we reach the end of either list.
      node * src = x.head->next;
      node * dest = head->next;
      while (src != x.head && dest != head)
      {
        dest->data = src->data;
        dest = dest->next;
        src = src->next;
      }

      if (dest == head)
      {
        // If we reached the end of the list being assigned to first,
        // copy any remaining data from list x, creating nodes 
        // as we go.
        while (src != x.head)
        {
          push_back(src->data);
          src = src->next;
        }
      }
      else
      {
        // Otherwise we need to destroy the extra nodes remaining in
        // the list being assigned to.
        while (dest != head)
          dest = erase(dest);
      }
    }
    return *this;
  }

  void reverse() 
  {
    node * p = head;
    do 
    {
      std::swap(p.next, p.prev);
      p = p->prev;  // Old next node.
    } while (p != head); 
  }    

  // One advantage of a linked list data structure is that we can
  // efficiently transfer many adjacent nodes from one list to another 
  // (or from one position to another in the same list).
  // We call this operation a "splice".
  // It transfers all the nodes in the range between first and last
  // to immediately before position.
  // This operations takes constant time regardless of the number
  // of items between first and last.
  // VERY IMPORTANT:  If position is between first and last,
  // the data structure will become corrupted!
  void splice(iterator position, iterator first, iterator last)
  {
    if (position != last && first != last) 
    {
      last.ptr->prev->next = position.ptr;
      first.ptr->prev->next = last.ptr;
      position.ptr->prev->next = first.ptr; 
      node * tmp = position.ptr->prev;
      position.ptr->prev = last.ptr->prev;
      last.ptr->prev = first.ptr->prev; 
      first.ptr->prev = tmp;
    }
  }

  // Merge with another sorted list.
  void merge(list & x)
  {
    iterator first1 = begin();
    iterator last1 = end();
    iterator first2 = x.begin();
    iterator last2 = x.end();
    while (first1 != last1 && first2 != last2)
      if (*first2 < *first1) 
      {
        iterator next = first2;
        ++next;
        splice(first1, first2, next);
        first2 = next;
      }
      else
        ++first1;
    if (first2 != last2) 
      splice(last1, first2, last2);
  }

  // This is an implementation of bottom-up mergesort.
  // The trick is to avoid the following two pitfalls:
  //   1. If we try to merge sublists within the list, we will
  //      inefficiently need to advance iterators through the list
  //      (for example, on the last merge we would need to advance
  //      to first + n/2, taking O(n) time).
  //   2. If we try to be clever and save iterators to the sublists
  //      to avoid having to advance, we will waste a lot of 
  //      memory (for example, on the first merge pass we would
  //      need to store n/2 iterators).
  //
  // To get around these problems, we keep a bunch of sublists, but
  // each sublist will be twice as long as the previous sublist.
  // This means we only need O(log n) lists.
  void sort()
  {
    // Do nothing if the list has length 0 or 1.
    if (head->next != head && head->next->next != head) 
    {
      // The array counter will hold the sublists; counter[i]
      // will either be empty or have length 2^i.  We could 
      // calculate the log of the length of the list being sorted
      // and dynamically allocate the array, but since 2^64 > 1.8 * 10^19
      // and we are unlikely to ever need to sort lists longer than
      // that, we will just hardcode the size of the array.
      // We will also need a scratch list called carry.
      list counter[64];
      list carry;

      // The following loop will result in all the data from the list
      // being moved to various counter lists, such that:
      //   - each list counter[i] is sored
      //   - each list counter[i] is empty or has length 2^i
      // The variable fill keeps track of how many of the counter lists
      // we have used.
      // Note how we make only a single pass through the list.
      int fill = 0;
      while (!empty()) 
      {
        // Move the first item from the list into the (empty) carry list.
        iterator tmp = begin();
        ++tmp;
        carry.splice(carry.begin(), begin(), tmp);

        // Merge the carry list, which will be sorted and of length 2^i,
        // with counter[i], which has the same properties.  
        // This results in a sorted list of length 2^(i+1), which we
        // put in carry, and an empty list which we put in counter[i].
        // Repeat until we reach an empty counter list.
        int i = 0;
        while(!counter[i].empty()) 
        {
          counter[i].merge(carry);
          carry.swap(counter[i]);
          ++i;
        }
        
        // The carry list now has 2^i items in it, and counter[i]
        // is empty.  Swap them, and update the fill variable.
        carry.swap(counter[i]);         
        if (i == fill) 
          ++fill;
      } 

      // Now merge each counter list into the one following it.
      // When done, swap the last counter list with the original list.
      for (int i = 1; i < fill; ++i)
        counter[i].merge(counter[i-1]);
      swap(counter[fill-1]);
    }
  }
};

template <class T>
inline bool operator==(const list<T> & x, const list<T> & y)
{
  node * px = x.head->next;
  node * py = y.head->next;
  node * endx = x.head;
  node * endy = y.head;
  while (px != endx && py != endy && px->data == py->data)
  {
    px = px->next;
    py = py->next;
  }
  return px == endx && py == endy;
}

template <class T>
inline bool operator<(const list<T> & x, const list<T> & y)
{
  return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

template <class T>
inline bool operator!=(const list<T> & x, const list<T> & y) 
{
  return !(x == y);
}

template <class T>
inline bool operator>(const list<T> & x, const list<T> & y) 
{
  return y < x;
}

template <class T>
inline bool operator<=(const list<T> & x, const list<T> & y) 
{
  return !(y < x);
}

template <class T>
inline bool operator>=(const list<T> & x, const list<T> & y) 
{
  return !(x < y);
}

template <class T>
inline void swap(list<T> & x, list<T> & y)
{
  x.swap(y);
}