#ifndef dslist_h_
#define dslist_h_
#include <cassert>

// A simplified implementation of the STL 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 or tail node and the list is not circular.

// -----------------------------------------------------------------
// NODE CLASS
template <class T>
class Node {
public:
  // CONSTRUCTORS: set the pointers to NULL
  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 dslist;

// -----------------------------------------------------------------
// LIST ITERATOR
template <class T>
class list_iterator {
public:
  // default constructor, copy constructor, assignment operator, & destructor
  list_iterator(Node<T>* p=NULL) : ptr_(p) {}
  // NOTE: the implicit compiler definitions of the copy constructor,
  // assignment operator, and destructor are correct for this class.

  // The dereferencing operator gives access to the value within the Node.
  T& operator*()  { return ptr_->value_;  }

  // pre-increment, e.g., ++iter
  list_iterator<T>& operator++() {     
    ptr_ = ptr_->next_;
    return *this;
  }
  // post-increment, e.g., iter++
  list_iterator<T> operator++(int) {  
    list_iterator<T> temp(*this);
    ptr_ = ptr_->next_;
    return temp;
  }
  // pre-decrement, e.g., --iter
  list_iterator<T>& operator--() {
    ptr_ = ptr_->prev_;
    return *this;
  }
  // post-decrement, e.g., iter--
  list_iterator<T> operator--(int) {
    list_iterator<T> temp(*this);
    ptr_ = ptr_->prev_;
    return temp;
  }

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

  // the dslist class needs access to the private ptr_ member variable
  friend class dslist<T>;

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 dslist {
public:
  // default constructor, copy constructor, assignment operator, & destructor
  dslist() : head_(NULL), tail_(NULL), size_(0) {}
  dslist(const dslist<T> &old) { copy_list(old); }
  dslist& operator= (const dslist<T>& old);
  ~dslist() { destroy_list(); }

  // typedef allows use of 'dslist<int>::iterator' syntax
  typedef list_iterator<T> iterator;

  // simple accessors & modifiers
  unsigned int size() const { return size_; }
  bool empty() const { return head_ == NULL; }
  void clear() { destroy_list(); }

  // read/write access to contents
  const T& front() const { return head_->value_;  }
  T& front() { return head_->value_; }
  const T& back() const { return tail_->value_; }
  T& back() { return tail_->value_; }
  
  // modify the linked list structure
  void push_front(const T& v);
  void pop_front();
  void push_back(const T& v);
  void pop_back();
  iterator erase(iterator itr);
  iterator insert(iterator itr, const T& v);
  iterator begin() { return iterator(head_); }
  iterator end() { return iterator(NULL); }

  friend class list_iterator<T>;

private:
  // private helper functions
  void copy_list(dslist<T> old);
  void destroy_list();

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

// -----------------------------------------------------------------
// LIST CLASS IMPLEMENTATION
// Remember: Because this is a templated class, the implementation of all
// member functions (even those longer than 1 line) should be in the .h file.
// Compilation of any file that #includes the header file of a templated
// class needs all the code, not just the declaration.

// NOTE: We have intentionally added a small, but significant typo to
// the assignment operator.  In Lab 6 Checkpoint 2 you will
// write test cases to show the problem with the buggy version.

template <class T>
dslist<T>& dslist<T>::operator= (const dslist<T>& old) {
  destroy_list();
  copy_list(old);
  return *this;
}

template <class T>
void dslist<T>::push_front(const T& v) {

  // You will implement this in Lab 6 Checkpoint 2




}

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

  // You will implement this in Lab 6 Checkpoint 2



}

template <class T>
void dslist<T>::push_back(const T& v) {
  Node<T>* newp = new Node<T>(v);
  // special case: initially empty list
  if (!tail_) {
    head_ = tail_ = newp;
  } else {
    // normal case: at least one node already
    newp->prev_ = tail_;
    tail_->next_ = newp;
    tail_ = newp;
  }
  ++size_;
}

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

  // You will implement this in Lab 6 Checkpoint 2



}

// operator== asks "Do these lists look the same (length & contents)?"
template <class T>
bool operator== (dslist<T>& left, dslist<T>& right) {
  if (left.size() != right.size()) return false;
  typename dslist<T>::iterator left_itr = left.begin();
  typename dslist<T>::iterator right_itr = right.begin();
  // walk over both lists, looking for a mismatched value
  while (left_itr != left.end()) {
    if (*left_itr != *right_itr) return false;
    left_itr++; right_itr++;
  }
  return true;
}

template <class T>
bool operator!= (dslist<T>& left, dslist<T>& right){ return !(left==right); }

template <class T>
typename dslist<T>::iterator dslist<T>::erase(iterator itr) {
  assert (size_ > 0);
  --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 dslist<T>::iterator dslist<T>::insert(iterator itr, const T& v) {
  Node<T>* p = new Node<T>(v);
  ++size_ ;
  if (size_ == 1) {
    // insert into a empty list
    head_ = tail_ = p;
  } else if (itr.ptr_ == NULL) {
    // insert at the back of the list
    tail_->next_ = p;
    p->prev_ = tail_;
    tail_ = p;
  } else if (itr.ptr_ == head_) {
    // insert at the front of the list
    p->next_ = head_;
    head_->prev_ = p;
    head_ = p;
  } else {
    // insert between two nodes
    p->prev_ = itr.ptr_->prev_;
    itr.ptr_->prev_ = p;    
    p->next_ = itr.ptr_;
    p->prev_->next_ = p;
  }
  return iterator(p);
}


// NOTE: We have intentionally added a small, but significant typo to
// the copy_list helper function.  In Lab 6 Checkpoint 2 you will
// write test cases to show the problem with the buggy version.

template <class T>
void dslist<T>::copy_list(dslist<T> old) {

  size_ = old.size_;
  // Handle the special case of an empty list.
  if (size_ == 0) {
    head_ = tail_ = 0;
    return;
  }
  // Create a new head node.
  head_ = new Node<T>(old.head_->value_);
  // tail_ will point to the last node created and therefore will move
  // down the new list as it is built
  tail_ = head_;
  // old_p will point to the next node to be copied in the old list
  Node<T>* old_p = old.head_->next_;
  // copy the remainder of the old list, one node at a time
  while (old_p) {
    tail_->next_ = new Node<T>(old_p->value_);
    tail_->next_->prev_ = tail_;
    tail_ = tail_->next_;
    old_p = old_p->next_;
  }
}

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

  // You will complete this implemention in Lab 6 Checkpoint 1

  size_ = 0;
  head_ = NULL;
  
}

#endif