/* This file contains the List class, a singly linked unordered
 * templated list class.  struct List_Link is the data structure for
 * the list links.
 *
 * Copyright (c) 1994, 2014 by Aaron Bloomfield
 * Released under a CC BY-SA license
 *
 * Revision history
 * 05-01-94: Main code written
 * 07-12-95: Bug updates
 * 01-13-14: Modified to fit modern C++ compilers; reformatted
 *
 * The tail of the list, in this implementation, is where the elements
 * are pushed (added) to and popped (removed) from.  For example:
 *
 * head <-- element <-- element <-- element <-- element <-- tail
 *
 *
 * Methods:
 *
 * List()                 Constructor, initilized an empty list
 * ~List()                Destructor, deletes the entire list
 * void push(T item);     Adds an item to the tail of the list
 * T* pop();              Removes an item from the tail of the list
 * int size();            Returns the size (length) of the list
 * void display();        Displays the list
 * int empty();           Returns 1 if the list is empty, 0 otherwise
 * void clear();          Clears (removes all elements from) the list
 * T* push_head();        Adds an item to the head of the list
 * T* tail();             Returns the tail data
 * T* head();             Returns the head data
 * int element (T item);  Returns 1 if T is in the list, 0 otherwise
 * pop_head (T item);     Removes an item from the head of the list
 * int remove (T item)    Removes item, returns 1 if sucessful, else 0
 * T* getptr (T item)     Returns the pointer to the parameter or NULL
 * void save(FILE *fp)    Saves the list- calls the objects methods
 *
 *
 * The List class requires <iostream> to be included, as it uses
 * cout's in the display method.
 *
 * In order to use the List class, the data type T must either be a
 * standard type, or be a class with the '==' operator overloaded.  To
 * use the display method, the data type must also have the '<<'
 * operator overloaded.  Examples follow, using a Complex class with
 * two attributes, real and imag (both ints).  The operator overloads
 * need to be functions outside the class declaration, and the
 * attributes used need to be public.
 *
 *      class Complex {
 *        public:
 *          int real, imag;
 *          Complex () { real = imag = 0; }
 *          Complex (int r, int i) { real = r; imag = i; }
 *          ~Complex () { }
 *          void set (int r, int i) { real = r; imag = i; }
 *      };
 *
 *      int operator == (Complex c1, Complex c2) {
 *        return ( (c1.real == c2.real) && (c1.imag == c2.imag) );
 *      }
 *
 *      int operator != (Complex c1, Complex c2) {
 *        return ( (c1.real != c2.real) || (c1.imag != c2.imag) );
 *      }
 *
 *      ostream& operator << (ostream& out, Complex c) {
 *        return (out << c.real << " + " << c.imag << "i");
 *      }
 *
 */

#include <iostream>
using namespace std;


template <class T>
struct List_Link {
    T *data;
    List_Link<T> *next;
};


template <class T>
class List {
    friend class Fsm;
    /*  head <-- element <-- element <-- element <-- element <-- tail       */
private:
    List_Link<T> *_head, *_tail;

public:
    List() {
        _head = _tail = NULL;
    } // cout << "List Constructor called.\n"; }

    ~List() {
        clear();
    }

    void push(T item) {
//    cout << "push(): called with element: " << item << endl;
        if ( _head == NULL ) {
            _head = _tail = new List_Link<T>;
            _head->next = NULL;
        } else {
            List_Link<T> *temp;
            temp = _tail;
            _tail = new List_Link<T>;
            _tail->next = temp;
        }
        _tail->data = new T;
        *_tail->data = item;
    }

    T* pop() {
        if ( _head == NULL )
            return NULL;
        else {
            List_Link<T> *temp;
            T *ret;
            temp = _tail;
            if ( _head == _tail )
                _tail = _head = NULL;
            else
                _tail = _tail->next;
            ret = temp->data;
            delete temp;
            return ret;
        }
    }

    int size() {
        if ( _tail == NULL )
            return 0;
        else {
            int s = 0;
            List_Link<T> *temp;
            for ( temp = _tail; temp != NULL; temp = temp->next )
                ++s;
            return s;
        }
    }

    void save(FILE *fp) {
        if ( _head == NULL ) {}
        else {
            List_Link<T> *temp;
            for ( temp = _tail; temp != NULL; temp = temp->next )
                temp->data->save(fp);
        }
    }

    void display() {
        if ( _head == NULL )
            cout << "List is empty.\n";
        else {
//      cout << "display(): List is printed reverse: List is not empty.\n\t";
            List_Link<T> *temp;
            for ( temp = _tail; temp != NULL; temp = temp->next )
                cout << *temp->data << " ";
            cout << endl;
        }
    }

    int empty() {
        return ( _head == NULL );
    }

    T* tail() {
        if ( _tail == NULL )
            return NULL;
        else
            return _tail->data;
    }

    T* head() {
        if ( _head == NULL )
            return NULL;
        else
            return _head->data;
    }

    int element (T item) {
        List_Link<T> *temp;
        if ( _tail == NULL )
            return 0;
        for ( temp = _tail; temp != NULL; temp = temp->next )
            if ( *temp->data == item )
                return 1;
        return 0;
    }

    T* getptr (T item) {
        List_Link<T> *temp;
        if ( _tail == NULL )
            return NULL;
        for ( temp = _tail; temp != NULL; temp = temp->next )
            if ( *temp->data == item )
                return temp->data;
        return NULL;
    }

    void clear() {
        while ( this->pop() != NULL ) { }
    }

    void push_head (T item) {
        if ( _head == NULL ) {
            _head = _tail = new List_Link<T>;
            _head->next = NULL;
        } else {
            List_Link<T> *temp;
            temp = _head;
            _head = new List_Link<T>;
            temp->next = _head;
            _head->next = NULL;
        }
        _head->data = new T;
        *_head->data = item;
    }

    T* pop_head() {
        if ( _head == NULL )
            return NULL;
        else {
            List_Link<T> *temp;
            T *ret;
            for ( temp = _tail; temp->next != _head; temp = temp->next ) { }
            ret = _head->data;
            _head = temp;
            temp = temp->next;
            delete temp;
            _head->next = NULL;
            return ret;
        }
    }

    int remove (T item) {
        if ( this->element(item) ) {
            cout << "remove(): element '" << item << "' exists.\n";
            if ( _head == _tail ) {
                delete _head;
                _head = _tail = NULL;
            } else if ( *_tail->data == item ) {
                List_Link<T> *temp;
                temp = _tail;
                _tail = _tail->next;
                delete temp;
            } else {
                List_Link<T> *temp, *temp2;
                for ( temp = _tail;
                        *temp->next->data != item;
                        temp = temp->next ) { }
                temp2 = temp->next;
                temp->next = temp->next->next;
                delete temp2;
            }
            return 1;
        } else {
            cout << "remove(): element '" << item << "' does not exist.\n";
            return 0;
        }
    }

};