#ifndef cs2list_h_
#define cs2list_h_
// A simplified implementation of a generic list container class,
// including the iterator, but not the const_iterators.  Three
// separate classes are defined: a Node class, an iterator class, and
// the actual list class.  The underlying list is doubly-linked, but
// there is no dummy head node and the list is not circular.

// -----------------------------------------------------------------
// NODE CLASS
template <class T>
class Node {
public:
  Node() : next_(NULL), prev_(NULL) {}
  Node(const T& v) : value_(v), next_(NULL), prev_(NULL) {}

  // REPRESENTATION
  T value_;
  Node<T>* next_;
  Node<T>* prev_;
};

// A "forward declaration" of this class is needed
template <class T> class cs2list;

// -----------------------------------------------------------------
// LIST ITERATOR
template <class T>
class list_iterator {
public:
  list_iterator() : ptr_(NULL) {}
  list_iterator(Node<T>* p) : ptr_(p) {}
  list_iterator(list_iterator<T> const& old) : ptr_(old.ptr_) {}
  ~list_iterator() {}

  list_iterator<T> & operator=(const list_iterator<T> & old) { 
    ptr_ = old.ptr_;  return *this; }

  // dereferencing operator gives access to the value at the pointer
  T& operator*()  { return ptr_->value_;  }

  // increment & decrement operators
  list_iterator<T> & operator++() { 
    ptr_ = ptr_->next_; 
    return *this;
  }
  list_iterator<T> operator++(int) {
    list_iterator<T> temp(*this);
    ptr_ = ptr_->next_;
    return temp;
  }
  list_iterator<T> & operator--() {
    ptr_ = ptr_->prev_;
    return *this;
  }
  list_iterator<T> operator--(int) {
    list_iterator<T> temp(*this);
    ptr_ = ptr_->prev;
    return temp;
  }

  friend class cs2list<T>;

  // Comparions operators are straightforward
  friend bool operator==(const list_iterator<T>& l, const list_iterator<T>& r) {
    return l.ptr_ == r.ptr_; }
  friend bool operator!=(const list_iterator<T>& l, const list_iterator<T>& r) {
    return l.ptr_ != r.ptr_; }

private:
  // REPRESENTATION
  Node<T>* ptr_;    // ptr to node in the list

};

// -----------------------------------------------------------------
// LIST CLASS DECLARATION
// Note that it explicitly maintains the size of the list.
template <class T>
class cs2list {
public:
  cs2list() : head_(NULL), tail_(NULL), size_(0) {}
  cs2list(const cs2list<T>& old) { this->copy_list(old); }
  ~cs2list() { this->destroy_list(); }
  cs2list& operator= (const cs2list<T>& old);

  int size() const { return size_; }
  bool empty() const { return head_ == NULL; }
  void clear() { this->destroy_list(); }
   
  void push_front(const T& v);
  void pop_front();
  void push_back(const T& v);
  void pop_back();

  const T& front() const { return head_->value_;  }
  T& front() { return head_->value_; }
  const T& back() const { return tail_->value_; }
  T& back() { return tail_->value_; }

  typedef list_iterator<T> iterator;
  iterator erase(iterator itr);
  iterator insert(iterator itr, T const& v);
  iterator begin() { return iterator(head_); }
  iterator end() { return iterator(NULL); }

private:
  void copy_list(cs2list<T> const & old);
  void destroy_list();

  //REPRESENTATION
  Node<T>* head_;
  Node<T>* tail_;
  int size_;
};

// -----------------------------------------------------------------
// LIST CLASS IMPLEMENTATION
template <class T>
cs2list<T>& cs2list<T>::operator= (const cs2list<T>& old) {
  if (&old != this) {
    this->destroy_list();
    this->copy_list(old);
  }
  return *this;
}

template <class T> 
void cs2list<T>::push_back(const T& v) {
  Node<T>*p = new Node<T>(v);
  if (!head_) {
    head_ = tail_ = p;
  } else {
    p->prev_ = tail_;
    tail_->next_ = p;
    tail_ = p;
  }
  ++ size_;
}

template <class T> 
void cs2list<T>::push_front(const T& v) {
  Node<T>*p = new Node<T>(v);
  if (!head_) {
    head_ = tail_ = p;
  } else {
    p->next_ = head_;
    head_->prev_ = p;
    head_ = p;
  }
  ++ size_;
}

template <class T> 
void cs2list<T>::pop_back() {
 






}

template <class T> 
void cs2list<T>::pop_front() {






}

template <class T> 
typename cs2list<T>::iterator cs2list<T>::erase(iterator itr) {
  -- size_;
  iterator result(itr.ptr_->next_);
  
  // One node left in the list.  
  if (itr.ptr_ == head_ && head_ == tail_) {
    head_ = tail_ = 0;
  }

  //  Removing the head in a list with at least two nodes
  else if (itr.ptr_ == head_) {
    head_ = head_->next_;
    head_->prev_ = 0;
  }

  //  Removing the tail in a list with at least two nodes
  else if (itr.ptr_ == tail_) {
    tail_ = tail_->prev_;
    tail_->next_ = 0;
  }

  //  Normal remove
  else {
    itr.ptr_->prev_->next_ = itr.ptr_->next_;
    itr.ptr_->next_->prev_ = itr.ptr_->prev_;
  }
  
  delete itr.ptr_;
  return result;
}

template <class T> 
typename cs2list<T>::iterator cs2list<T>::insert(iterator itr, T const& v) {









}

template <class T> 
void cs2list<T>::copy_list(cs2list<T> const & old) {
















}

template <class T> 
void cs2list<T>::destroy_list() {







}

#endif