//  File:    cs2list.h
//  Author:  Chuck Stewart
//  Purpose: A simplified implementation of a generic list container
//    class, including the iterator, but not the const_iterators.
//
//  Overview:  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.


#ifndef cs2list_h_
#define cs2list_h_

///////////////////////////////////////////////////////////////////
///////////////         Node class        /////////////////////////
///////////////////////////////////////////////////////////////////

template <class T>
class Node {
public:
  Node( ) : next_(0), prev_(0) {}
  Node( const T& v ) : value_(v), next_(0), prev_(0) {}
  T value_;
  Node<T>* next_;
  Node<T>* prev_;
};


//  This is what's called a "forward declaration" of the templated
//  cs2list class so that the iterator class allows it to be named as
//  a friend.

template <class T> class cs2list;

///////////////////////////////////////////////////////////////////
///////////////         Iterator definitions          /////////////
///////////////////////////////////////////////////////////////////

template <class T>
class list_iterator {
private:
  Node<T>* ptr_;    // ptr to node in the list
public:
  friend class cs2list<T>;  // this declaration means that
                            //  the cs2list class can access
                            //  private member variables/functions
                            //  of this (list_iterator) class

  list_iterator() : ptr_(0) {}
  list_iterator( Node<T>* p ) : ptr_(p) {}
  list_iterator( list_iterator<T> const& old ) : ptr_(old.ptr_) {}

  // destructor
  ~list_iterator() {}

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

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

  //  pre-increment
  list_iterator<T> & operator++( )
  {
    ptr_ = ptr_ -> next_;   // next_ is from Node<T>
    return *this;
  }

  //  post-increment is indicated by the dummy int argument
  list_iterator<T> operator++( int dummy )
  {
    list_iterator<T> temp( *this );
    ptr_ = ptr_ -> next_;
    return temp;
  }

  //  pre-decrement
  list_iterator<T> & operator--( )
  {
    ptr_ = ptr_ -> prev_;   // next_ is from Node<T>
    return *this;
  }

  //  post-decrement is indicated by the dummy int argument
  list_iterator<T> operator--( int dummy )
  {
    list_iterator<T> temp( *this );
    ptr_ = ptr_ -> prev_;
    return temp;
  }

  //  Comparions operators are straightforward
  //  (these are NOT member functions; instead, they're friend functions,
  //     so they have access to private member variables/functions)
  friend bool operator== ( const list_iterator<T>& lft, const list_iterator<T>& rgt )
  { return lft.ptr_ == rgt.ptr_; }

  friend bool operator!= ( const list_iterator<T>& lft, const list_iterator<T>& rgt )
  { return lft.ptr_ != rgt.ptr_; }
};



///////////////////////////////////////////////////////////////////
/////////////         cs2list class declaration          //////////
///////////////////////////////////////////////////////////////////

//  Note that it explicitly maintains the size of the list.

template <class T>
class cs2list {
public:
  typedef list_iterator<T> iterator;

private:
  Node<T>* head_;
  Node<T>* tail_;
  int size_;

public:
  cs2list() : head_(0), tail_(0), 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_ == 0; }
  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_; }

  iterator erase( iterator itr );
  iterator insert( iterator itr, T const& v );

  iterator begin() { return iterator(head_); }
  iterator end() { return iterator(0); }

private:
  void copy_list( cs2list<T> const & old );
  void destroy_list( ) {}  //  replace {} with ; when we write the fcn
};


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


//  push_front() goes here:
template <class T>
void
cs2list<T>::push_front( const T& v )
{
  // create the new node:
  Node<T>* p = new Node<T>( v );

  // first consider if this is an empty list:
  if ( head_ == 0 ) {
    head_ = tail_ = p;
  }
  else
  {
    p->next_ = head_;
    head_->prev_ = p;
    head_ = p;
  }
  size_++;
}


//  erase() goes here:

template <class T>
typename cs2list<T>::iterator
cs2list<T>::erase( iterator itr )
{
  Node<T>* p = itr.ptr_;
  if ( head_ == tail_ ) {   // one-element list
    head_ = tail_ = 0;
    itr.ptr_ = 0;
  }
  else if ( head_ == p ) {   // erase first node
    head_ -> next_ -> prev_ = 0;
    head_ = head_ -> next_;
    itr.ptr_ = head_;
  }
  else if ( tail_ == p ) {   // erase last node
    tail_ -> prev_ -> next_ = 0;
    tail_ = tail_ -> prev_;
    itr.ptr_ = tail_;
  }
  else
  {
    p -> next_ -> prev_ = p -> prev_;
    p -> prev_ -> next_ = p -> next_;
    itr.ptr_ = p -> next_;
  }

  delete p;
  size_--;
  return itr;
}


#endif