/** File "DList.h", KWR edit of Koffman-Wolfgang Ch. 4 double linked-list
    example.  "Item_Type" has been changed to "T" for simplicity, and the use
    of templates has been made more explicit, rather than "typedef'ed away".
    For CSE250 Fall 2010.
 */
#ifndef DLIST_H_
#define DLIST_H_

#include <iostream>
#include <sstream>
#include <string>

using std::string;     //From now on we rule out "using namespace std;"
using std::iostream;   //in library files---only clients may do it.
using std::ostringstream;
using std::cout;
using std::cerr;
using std::endl;


template <typename I>  //REQ: I has I(), operator<<(iostream&, const I&)
class DList;


/** A DNode is the building block for a double-linked list.  Text uses struct
    to make data fields public---later (of course!) we will encapsulate it.
 */
template <typename I>
struct DNode {
  /** A pointer to the list I belong to---added by KWR.
      [Not needed or even good for your node class, *yes* should do for
      your iterator class.]
   */
  DList<I>* myList;

  /** A copy of the data   (KWR: we might use pointers to avoid copying)
   */
  I data;

  /** Pointers to previous and next DNode (KWR: note different order from text)
   */
  DNode<I>* prev;
  DNode<I>* next;

  DNode(DList<I>* myList, const I& item, DNode<I>* prev = NULL,
                                         DNode<I>* next = NULL)
   : myList(myList), data(item), next(next), prev(prev) 
  { }
};


template <typename I>    //Written by KWR. 
class DList {
   DNode<I>* firstNode;  //by convention, a "real" node
   DNode<I>* endNode;    //by convention, a dummy node. Use to end while loops.

   //CLASS INV: firstNode always points to first node, endNode to dummy node
   //CLASS INV: Empty list exactly when firstNode == endNode == the dummy node
   //CLASS INV: endNode never changes; we only insert before it.
 public:
   DList<I>() 
    : firstNode(new DNode<I>(this, I(), NULL, NULL))
    , endNode(firstNode)
   { }

   /** Example of destructor added by KWR.  Using "cerr" guarantees 
       immediate screen output.
    */
   virtual ~DList<I>() {
      cerr << "This list will self-destruct in 5 nanoseconds..." << endl;
      DNode<I>* current = endNode;
      while (current != firstNode) {
         cerr << "Deleting: " << current->data << "; ";
         current = current->prev;
         delete(current->next);
      }
      //delete(current);  //do you dare comment this in?
      cerr << "Deleting: " << current->data << "; done." << endl;
      delete(current);  //i.e. delete(firstNode);
   }

   DNode<I>* begin() const { return firstNode; }  
   DNode<I>* end() const { return endNode; }
   //LATER we will "hide" the node implementation and return iterators instead.

   void insert(DNode<I>* beforeMe, I newItem) {  
      DNode<I>* newNode = new DNode<I>(this,newItem,beforeMe->prev,beforeMe);
      if (beforeMe->prev != NULL) {   //i.e. if we're not inserting a new first
         beforeMe->prev->next = newNode;
         beforeMe->prev = newNode;  //don't forget!
      } else {
         beforeMe->prev = newNode;
         firstNode = newNode;
      }
   }

   size_t size() const {            //illustrates size_t (unsigned int) type
      size_t count = 0;
      DNode<I>* current = firstNode;
      while (current != endNode) {
         count++;
         current = current->next;
      }
      return count;
   }

   string toString() const {       //Node resemblance to code in Deque<I> class
      ostringstream OUT;
      DNode<I>* current = firstNode;
      while (current != endNode) {
         OUT << current->data << " ";  //REQ of T having operator<< used here.
         current = current->next;
      }
      return OUT.str();
   }

};
#endif