#ifndef LIST_HH
#define LIST_HH

// Filename: list.hh
// Author:   Michael P. Schubmehl
// Date(s):  11/17/99 10/23/99
// Purpose:    This file defines the interface to the List class, a template
//           class that stores a list of objects. The class also defines a
//           variety of routines for modifying and examining the list, as
//           detailed below.
//             The file also defines the class Node, which represents a single
//           item in the list. Since the two classes are mutually dependent,
//           they are both included in this file.
//             Finally, it has a list iterator for use with the list class. The
//           iterator is like a pointer to individual items in the list, which
//           supports operators like ++ to make the iterator point to the next
//           item in the list, * to dereference the iterator and get back the
//           value in the item it's pointing to, and a cast to boolean to
//           determine whether the list is out of items. It also supports an
//           assignment operator, and a function to reset the iterator to the
//           head of the list over which it is iterating.
//
// Notes:    Implemented in list.icc.


// Classes Defined ************************************************************
template <typename T> class List;               // A list of objects
template <typename T> class Node;               // A single node in the list
template <typename T> class ListIter;           // List iterator
// END Classes Defined ********************************************************


// class List *****************************************************************
template <typename T> class List {
  public:
    List();                    // Constructor
    ~List();                   // Destructor

    void push(T &value);       // Add item to head of list
    void pushAtTail(T &value); // Add item to tail of list
    T pop();                   // Remove item from head and return its value
    T popAtTail();             // Remove item from tail and return its value

    bool isEmpty();            // True if list is empty
    T peek();                  // Return value of item at head of list
    T peekAtTail();            // Return value of item at tail of list
    int length();              // Return length of the list

    void insert(T &value);     // Insert value at the appropriate place in the
                               //  list using the < operator for comparison.
    friend class ListIter<T>;  // Allow the list iterator class to access the
                               //   private data fields and functions of the
                               //   list class.
  private:
    List(const List<T>& oldList);               // Disable copy/assignment
    List<T>& operator=(const List<T>& source);

    Node<T>* head;             // Head of the list

    Node<T>* tail();           // Return a pointer to the tail of the list.
};
// END class List *************************************************************


// class Node *****************************************************************
template <typename T> class Node {
  public:
    Node();                        // Default constructor
    Node(T &value, Node<T>* next); // Create a node for value that points to
                                   //  the node specified by next
    ~Node();                       // Destructor

  private:
    Node(const Node<T>& oldNode);               // Disable copy/assignment
    Node<T>& operator=(const Node<T>& source);

    T value;                       // Value stored in node
    Node* next;                    // Pointer to next node
    friend class List<T>;          // Allow lists to access the private
                                   //  fields of the Node class. This will
                                   //  greatly simplify code for manipulation
                                   //  of lists.
    friend class ListIter<T>;      // Allow list iterators access to nodes
                                   //   as well, so they can return the values
                                   //   they point at.
};
// END class Node *************************************************************


// class ListIter *************************************************************
template <typename T> class ListIter {
  public:
    ListIter(const List<T>& target);                 // No null constructor
    ListIter(const ListIter<T>& source);             // Copy constructor
    ~ListIter();

    ListIter<T>& operator=(const ListIter<T>& source); // Assignment

    operator bool() const;                           // Test for completion

    ListIter<T>& operator++();                       // Step to next element
    ListIter<T>  operator++(int);                    // Suffix step

    T& operator*();                                  // Dereference iterator
    void reset();                                    // Reset to head of list

  private:
    Node<T>* head;                 // Head of the list being iterated over
    Node<T>* current;              // The list element currently pointed to
};
// END class ListIter *********************************************************

#include "list.icc"                // Implementation must go in header file to
                                   //  make a templated class work properly
                                   //  with the g++ compiler.

#endif // LIST_HH