#ifndef TmpLIST_SEEN__
#define TmpLIST_SEEN__
///////    File: List.h    ///////
#include <iostream.h>
// linked list template

// forward teamplate class declaration
template <class T> class Item;           
template <class T> class ListIterator;

// type T must define operator== and overload <<

template <class T>
class List
{   friend class ListIterator<T>;
  public:
    List() : head(NULL) { }            // empty list constructor 
    List(T& c)                         // list with first cell
    //: head (new Item<T>(c,NULL)) { }
    : head (new Item<T>(c)) { }
    Item<T>* first() { return head; }  // first cell
    static Item<T>* next(Item<T>* p)   // next cell
      { return (p ? p->next : p); }
    static int is_end(Item<T>* p)      // end test   
      { return(p == End); }        
    static Item<T>* End;               // end marker
    Item<T>* last();                   // last cell
    Item<T>* find(T& c);               // first value equals c
    int substitute(T& r, T& s);        // r for first s on list
    int remove(T& c);                  // c from entire list
    void remove(Item<T>* cell);        // remove given cell
    int shorten(int n);                // remove first n cells
    static T& content(Item<T>* p)
      {  return p->value();  }
    int put_on(T& c);                  // insert in front
    int insert(T& c, Item<T>* cell);   // insert after cell
    int append(T& c)                   // insert at end
      { return insert(c, last()); }
    int is_empty()
      { return(is_end(head)); }
    void display(ostream& out,         // display from p to end
                 Item<T>* p) const;
    void display(ostream& out) const
    { display(out, head); }            // display whole list
    ~List();                           // destructor
  private:
    int equal(T&, T&);                 // equality test
    Item<T>* head;                     // first cell of list
    void free();                       // free all cells
};

template <class T>
class ListIterator
{  public:
      ListIterator(List<T>& x) : l(x)
      { cur = pre = x.first(); }
      int operator()(T& n); // returns next entry in n
      void del();           // erases last retrieved entry from list
   private:
      List<T>& l;
      Item<T>* cur;
      Item<T>* pre;
};

template <class T>
class Item
{ friend class List<T>;
  friend class ListIterator<T>;
  private:
    T& value() { return(*val); }
    void value(T& v) { val = &v; } // set value
    T* val;                        // store pointer to type T
    Item<T>* next;
    Item(T& c, Item<T>* ptr = NULL)
    :  val(&c), next(ptr) { }   // constructor
};
#endif