/****** [tlistp.h] Template for List ADT implemented with pointers/


 For a Class to be used in this template it must have:

     Constructor if it used dynamic memory
     Assignment Operator
     Copy Constructor
     Destructor if it uses dynamic memory
     bool operator !=


----*/

#ifndef _TLISTP_H
#define _TLISTP_H

template <class T>
class List {
    public:
//------------- Node --------------------------------------
    class Node {              // This is a class for single node on list
      public:               
         T d;
         Node * n;
      Node() {                // When allocated (by new)
        n = NULL;             //      every node has n == NULL
        }
       };

    typedef Node * NPtr;       // conveniences
    typedef T *  DPtr;

//------------ Value Semantics for List -------------------
    List() {                  // creation constructor for List
      start = new Node;
      start->n = NULL;
      cursor = start->n;
      }

 
     // ----- Copy constructor ----------------------------
     List(const List<T> & orig){   // copy constructor for List
       empty();                    // recycle any old nodes
       start = duplst(orig.start);
       cursor = NULL;
       }

     //------ Assignment Operator -------------------------
     const List<T> & operator=(const List<T> & right) {
       if ( this != & right) {
	  empty();
	  start = duplst(right.start);
	  cursor = NULL;
	  }
       return *this;
       }

    //------- Destructor  (sounds like WWF bad guy) -------   
    ~List() {             // delete  destructor to recycle nodes
     NPtr
       tp;
     while (start!=NULL) {
       tp = start->n;
       delete start;
       start = tp;
       }
     start = cursor = NULL;
     }

// ==========  Member Functions (ADT)  ==============================
  void empty(){
  // frees all data memory on list 
     NPtr
       tp;
     while (start!=NULL) {
       tp = start->n;
       delete start;
       start = tp;
       }
     //     start = cursor = NULL;
      start = new Node;
      start->n = NULL;
      cursor = start->n;
     //    List<T>::~List();
    }

  bool isfull() {
     return false;   // ??? how to check for this in dynamic memory
     }

  NPtr  currentnode()  {
    return  lastptr;
    }

  DPtr  currentdata() {
    return & (lastptr->d);
    }  

  int length() {
    // returns number of nodes on the list
    NPtr
      tp = start->n;
    int 
      len = 0;
    while (tp != NULL) {
      len++;
      tp = tp->n;
      }
    return len;
    }


  bool add(const T & x) {
  // adds data value x to the list (after dummy)
  //  returns false if not enough dynamic memory
  //----
     NPtr tp;
     tp = new Node;
     if (tp == NULL) {
       lastptr = NULL;
       return false;
       }
     tp->d = x;
     tp->n = start->n;
     start->n = tp;
     lastptr = tp;
     return true;
  }

  bool remove(const T & x) {
  // removes data value from the list
  // returns true on success, else returns false (not found in list)
     NPtr 
       pp = start,
       tp = start->n;

     while (tp != NULL && tp->d != x) {
         pp = tp;
         tp = tp->n;
         }


     if ( tp== NULL || tp->d != x) {
       lastptr = NULL;
       return false;
       }
     pp->n = tp->n;
     delete tp;
     lastptr = pp;
     return true;
     }
     

  bool getitem( T & x) {
  // finds data value in the list
  //  returns true on find, false not found
     NPtr 
       tp = start->n;

     while (tp != NULL && tp->d != x) {
         tp = tp->n;
         }
     if ( tp== NULL || tp->d != x) {
       lastptr = NULL;
       return false;
       }
     x = tp->d;
     lastptr = tp;
     return true;
     }


  bool getfirst(T & x) {
  // a simple form of getfirst
  //    0. if cursor is end of list return false
  //    1. moves cursor forward in the list
  //    2. puts the data at cursor in x and returns true
  //
    if (start->n == NULL) {
      lastptr = NULL;
      return false;
      }
    cursor = start->n;
    x = cursor->d;
    lastptr = cursor;
    return true;
    }

  bool getnext(T & x) {
  // a simple form of getnext
  //    0. if cursor is end of list return false
  //    1. moves cursor forward in the list
  //    2. puts the data at cursor in x and returns true
  //
    if (cursor == NULL || cursor->n == NULL) {
      lastptr = NULL;
      return false;
      }
    cursor = cursor->n;
    x = cursor->d;
    lastptr = cursor;
    return true;
    }

  void show(ostream & out) {
  // function to display list, requires class T to
  //  have << operator defined
  // --------
     NPtr
       xp = start->n;
     while (xp != NULL) {
       out << xp->d << " | ";
       xp = xp->n;
       }
     out <<" eol ";
     }


  //  private:
public:
    NPtr duplst(NPtr cp) {
       if (cp==NULL)
         return NULL;
       NPtr tp = new Node;
       tp->d = cp->d;
       tp->n = duplst(cp->n);
       return tp;
       }


    NPtr
      start,
      lastptr,
      cursor;


  };  // class List

template <class T>
ostream & operator<< (ostream & out, List<T> & t ) {
  t.show(out);
  return (out);
  }


#endif