// Templated Class definitions and implementations 
// for both a List ADT and Ordered List ADT
// File:    list-temp.h
// Author:  Henry M. Walker
// Date:    May 29, 1998

#define NIL 0
#include <iostream.h>

// template list node header
template<class T>  
struct ListNode {
     T data;
     ListNode *next;
     };
    
// template list header
template<class T>  // type T to be filled in later
class List {
public:
    List (void); 
    /* pre:  true;
      post:  the list is initialized */

    void insert (T item);  
    /* pre:  the list has been initialized
      post:  the specified item is placed at the front of the list  */

    bool isin (T item);
    /* pre:  the list has been initialized
      post:  function returns TRUE if item is in list and FALSE otherwise */

    void print (void);
    /* pre:  the list has been initialized
      post:  a title is printed, followed by the items from front to back */

    void print_reverse (void);
    /* pre:  the list has been initialized
      post:  a title is printed, followed by the items from back to front */

    void count (void);
    /* pre:  the list has been initialized
      post:  the items in the list are counted and printed */

protected:  // allow access to first in derived classes (e.g., OrderedList)
    ListNode<T> *first;

private:    // these functions can be accessed only by class List functions
    void printData (ListNode<T> *front);
    void printReverse (ListNode<T> *front);
    int countNode (ListNode<T> *front);

}; // List


// template ordered list header
template<class T>  // type T to be filled in later
class OrderedList : public List<T> {//follows unordered list, except for insert
public:
    void insert (T item);  
    /* pre:  the list has been initialized
      post:  the item is placed in the list to maintain ordering by < */

protected: 
    void rec_insert (T item, ListNode<T> **front);
}; // OrderedList

// template list implementation

template<class T>
List<T>::List (void)   
    /* pre:  true;
      post:  the List is initialized */
{   first=NIL;
}


template<class T>
void List<T>::insert (T item)
    /* pre:  the list has been initialized
      post:  the specified item is placed at the front of the list  */
{  ListNode<T> *temp = new ListNode<T>;
   temp->data=item;
   temp->next=first;
   first = temp;
}

template<class T>
bool List<T>::isin (T item)
    /* pre:  the list has been initialized
      post:  function returns TRUE if item is in list and FALSE otherwise */
{   ListNode<T> *temp = first;
    while (temp) {
       if (temp->data == item)
          {return (true);}
          else {temp = temp->next;}
    }
    return (false);
}

template<class T>
void List<T>:: print (void)
    /* pre:  the list has been initialized
      post:  a title is printed, followed by the items from front to back */
{   cout << "The items on the list, from front to back, are:" << endl;
    printData(first);
    cout << "End of list" << endl;
}

template<class T>
void List<T>::print_reverse (void)
    /* pre:  the list has been initialized
      post:  a title is printed, followed by the items from back to front */
{   cout << "The items on the list, from back to front, are:" << endl;
    printReverse(first);
    cout << "End of list" << endl;
}

template<class T>
void List<T>::count (void)
    /* pre:  the list has been initialized
      post:  the items in the list are counted and printed */
{   cout << "The number of nodes in the list is " << countNode (first) << endl;
}

template<class T>
void List<T>::printData (ListNode<T> *front)
{   if (front != NIL) {
        cout << front->data << endl;
        List<T>::printData (front->next);}
}


template<class T>
void List<T>::printReverse (ListNode<T> *front)
{   if (front != NIL) {
        List<T>::printReverse (front->next);
        cout << front->data << endl;}
}

template<class T>
int List<T>::countNode (ListNode<T> *front)
/* helping function to recursively count the number of nodes in the list */
{   if (front == NIL)
        return (0);
        else return (1 + List<T>::countNode(front->next));
}

template<class T>
void OrderedList<T>::insert (T item)
    /* pre:  the list has been initialized
      post:  the specified item is placed at the front of the list  */
{  rec_insert(item, &first);
}

template<class T>
void OrderedList<T>::rec_insert (T item, ListNode<T> **front)
    /* pre:  the list has been initialized
      post:  the specified item is placed at the front of the list  */
{ if ((*front == NIL) || (item < (*front)->data))
     { ListNode<T> *temp = new ListNode<T>;
       temp->data=item;
       temp->next=*front;
       *front = temp;
     } else { rec_insert (item, &((*front)->next));}
}