/***********************************************
 * list.h
 * LIST CONTAINER and ITERATOR
 ***********************************************/
 
#ifndef LIST_H
#define LIST_H

#include <cassert>
// debug........................................................................
#include <iostream>
using namespace std;

// Forward declaration of ListIterator
template <class T>
class ListIterator;

/**************************************************
 * NODE
 **************************************************/
template <class T>
struct Node
{
   // constructors: default and non-default
   Node ()            : data(NULL), pNext(0x00000000), pPrevious(0x00000000) {}
   Node (const T & t) : data(t),    pNext(0x00000000), pPrevious(0x00000000) {}

   // member variables
   T data;
   Node * pNext;
   Node * pPrevious;
};

/**************************************************
 * LIST
 **************************************************/
template <class T>
class List
{
  public:
   
   // Default constructor
  List() : numItems(0), pHead(NULL), pTail(NULL) {}

   // Copy Constructor
   //List(const List & rhs) throw (const char *) { *this = rhs; }

   
   // = Operator
   List <T> & operator = (const List & rhs) throw (const char *);

   // Destructor (deletes all nodes)
   // ~List() { clear();}

   // empty() Test whether the list is empty
   bool empty() {return numItems == 0;}

   // clear() empties the list
   void clear();

   // push_back() Adds an item to the back of the list
   void push_back(const T & t) throw(const char*);

   // push_front Adds an item to the front of the list
   void push_front(const T &t) throw(const char*);

   // front() returns the item currently at the front of the list
   T & front() throw (const char *);

   // back() return the item currentl at the back of the list
   T & back() throw (const char *);
   
   // insert() Inserts an item in the middle of the list.

   // Remove() Removes an item from the middle of the list

   // begin() Return an iterator to the first element of the list
   ListIterator <T> begin() { return ListIterator<T>(pHead); }

   // rbegin() Returns an iterator to the last element of the list
   ListIterator <T> rbegin() { return ListIterator<T>(pTail); }
   
   // end() Returns an iterator to the past-the-end element in the lsit
   ListIterator <T> end() { return ListIterator<T>(pTail + 1);}

   // rend() Returns an iterator referring to the past-the-front element
   //   in the list
   ListIterator <T> rend() { return ListIterator<T>(pHead - 1);}
   
  private:   
   Node <T> * pHead; // Head node
   Node <T> * pTail; // Tail node
   int numItems;     // Num of items in the list   
   void freeData(Node <T> * & pHead); // private function to delete nodes
};

/**************************************************
 * LIST :: CLEAR()
 * Empties the list of all items
 **************************************************/
template <class T>
void List <T> :: clear()
{
   // Return if there is nothing to do.
   if(numItems == 0)
      return;

   // for loop is only running one time, not working right...
   freeData(pHead);
   numItems = 0;
}

/*******************************************************************************
 * LIST :: FREE DATA
 * Allows the user to delete every Node in a list. 
 ******************************************************************************/
template <class T>
void List <T> :: freeData(Node <T> * & pHead)
{
   // if there is another Node linked to this one then delete that one first
   if (pHead->pNext)
   {
      freeData(pHead->pNext); // recursion!
      delete pHead;
      //cout << "delorted....\n";...............................................
   }
   else
      delete pHead;
      
   pHead = NULL;
   //cout << "end delort\n";....................................................

   return;
}

/*******************************************************************************
 * LIST :: PUSH_BACK
 * Add an item to the back of the list
 ******************************************************************************/
template <class T>
void List <T> :: push_back(const T & t) throw(const char*)
{
   Node <T> * pNew = new Node <T>(t);
   pNew -> pPrevious = pTail;

   pTail = pNew;
   //pTail -> pNext = NULL; it should already be set to null 

   // Increment numItems
   numItems++;

   if (numItems == 1)
      pHead = pTail;
}

/*******************************************************************************
 * List :: PUSH_FRONT
 * Add an item to the front of the list
 ******************************************************************************/
template <class T>
void List <T> :: push_front(const T & t) throw(const char*)
{
   Node <T> * pNew = new Node <T>(t);
   pNew -> pNext = pHead;
   pHead = pNew;
   //pHead -> pPrevious = NULL;

   // Increment numItems
   numItems++;

   if (numItems == 1)
      pTail = pHead;
}

/*******************************************************************************
 * LIST :: FRONT()
 * Return the item in the front by reference so it can be changed
 ******************************************************************************/
template <class T>
T & List <T> :: front() throw (const char *)
{
   if (numItems == 0)
      throw "ERROR: unable to access data from an empty deque";

   return pHead -> data;
}

/*******************************************************************************
 * LIST :: BACK()
 * Return the item in the front by reference so it can be changed
 ******************************************************************************/
template <class T>
T & List <T> :: back() throw (const char *)
{
   if (numItems == 0)
      throw "ERROR: unable to access data from an empty deque";

   return pTail -> data;
}


/**************************************************
 * List :: OPERATOR =
 * Acts the same as copy constructor
 **************************************************/
template <class T>
List <T> & List <T> :: operator = (const List & rhs) throw (const char *)
{
}

/**************************************************
 * LIST ITERATOR
 **************************************************/
template <class T>
class ListIterator
{
  public:
   // default constructor
  ListIterator() : p(0x00000000) {}

   // initialize to direct p to some item
  ListIterator(T * p) : p(p) {}

   // copy constructor
   ListIterator(const ListIterator & rhs) { *this = rhs; }

   // assignment operator
   ListIterator & operator = (const ListIterator & rhs)
   {
      this->p = rhs.p;
      return *this;
   }

   // not equals operator
   bool operator != (const ListIterator & rhs) const
   {
      return rhs.p != this->p;
   }
   // dereference operator
   T & operator * ()
   {
      return *p;
   }

   // prefix increment
   ListIterator <T> & operator ++ ()
   {
      p++;
      return *this;
   }

   // postfix increment
   ListIterator <T> operator++(int postfix)
   {
      ListIterator tmp(*this);
      p++;
      return tmp;
   }

   // prefix decrement for reverse iterator
   ListIterator <T> & operator -- ()
   {
      p--;
      return *this;
   }

   // postfix decrement for reverse iterator
   ListIterator <T> operator--(int postfix)
   {
      ListIterator tmp(*this);
      p;
      return tmp;
   }

  private:
   T * p;
};

#endif  // LIST_H