#include <iostream>

using namespace std;

template <class Type>
struct nodeType
{
    Type info;
    nodeType<Type> *link;
};

template <class Type>
class linkedListIterator
{
public:
    linkedListIterator(); //Default constructor
    linkedListIterator(nodeType<Type> *p); //constructor
    Type operator*(); //overload dereferencing operator * ie. *p=val
    linkedListIterator<Type> operator++(); //overload the PREincrement operator
    //POSTincrement would be linkedListIterator<Type> operator++(int);
    bool operator==(const linkedListIterator<Type>& right) const;
    //overload equality operator. second const is to make function itself const,
    //because it doesn't modify the object
    bool operator!=(const linkedListIterator<Type>& right) const;
    //over not equal to operator. reference param must be const to prevent change.

private:
    nodeType<Type> *current; //ptr points to current node in linked list
};//UML on page 281

template <class Type>
class linkedListType
{
public:
    const linkedListType<Type>& operator=(const linkedListType<Type>&);
    //overload the assignment operator

    void initializeList(); //initialize list into an empty state
    bool isEmptyList() const; //function to determine if list is empty,
                            //doesn't change list, so constant.
    void print() const; //function to output data in each node
    int length() const; //return number of nodes in list
    void destroyList(); //delete all nodes from list, no const, because change
    Type front() const; //return first element of list
    Type back() const; //return last element of list
    //to be derived functions-virtual =0 pure virtual, only overwritten
    virtual bool search(const Type& searchItem) const = 0;// determine if item in list
    virtual void insertFirst(const Type& newItem) = 0; //insert newitem at begin of list
    virtual void insertLast(const Type& newItem) = 0; //insert newitem at end of list
    virtual void deleteNode(const Type& deleteItem) = 0; //delete item from list

    //returntype             function make use of the linkedListIterator class?
    linkedListIterator<Type> begin(); //return an iterator at beginning of linked list
    linkedListIterator<Type> end(); //return iterator one element past last element of list

    linkedListType(); //default constructor
    linkedListType(const linkedListType<Type>& otherList); //argument constructor
    ~linkedListType(); //destructor

protected: //for use in class functions and derived classes/functions
    int count; //number of list items
    nodeType<Type> *first; //pointer to first node of list
    nodeType<Type> *last; //pointer to last node of list

private:
    void copyList(const linkedListType<Type>& otherList);
    //function to make a copy of otherlist and assign to this list
};

template <class Type>
class unorderedLinkedList: public linkedListType<Type> //inherit public section of lLT class
{
public:
    bool search(const Type& searchItem) const; //const on referenced item, const on function
                                                //determines if item is in the list
    void insertFirst(const Type& newItem); //insert newitem at beginning of list
    void insertLast(const Type& newItem); //insert newitem at end of list
    void deleteNode(const Type& deleteItem); //delete deleteItem from list
};

template <class Type> //default constructor
linkedListIterator<Type>::linkedListIterator()
{   //constructors don't need return type
    current = NULL;
}

template <class Type> //argument constructor
linkedListIterator<Type>::linkedListIterator(nodeType<Type> *p)
{
    current = p; //set current to pointer argument
}

template <class Type> //overload dereference operator
Type linkedListIterator<Type>::operator*() //return type template
{
    return current->info;
}

template <class Type> //overload preincrement operator
linkedListIterator<Type> linkedListIterator<Type>::operator++()
{
    current = current->link;
    return *this;
}

template <class Type> //overload equality operator
bool linkedListIterator<Type>::operator==(const linkedListIterator<Type>& right) const
{
    return (current == right.current); //compares both values
}

template <class Type> //overload not equal to operator
bool linkedListIterator<Type>::operator!=(const linkedListIterator<Type>& right) const
{
    return (current != right.current);
}

template <class Type> //O(1)
bool linkedListType<Type>::isEmptyList() const
{
    return (first == NULL); //if equal to NULL, then list empty
}

template <class Type>//O(1)
linkedListType<Type>::linkedListType() //Default constructor
{
    first = NULL;
    last = NULL;
    count = 0; //create empty list
}

template <class Type>//O(n)
void linkedListType<Type>::destroyList() //deallocates memory occupied by nodes
{
    nodeType<Type> *temp; //pointer to deallocate memory

    while (first != NULL) //while there are nodes, loop
    {
        temp = first;
        first = first->link; //move first onto next node to prevent losing place and
                            // ending up with dangling pointers/memory
        delete temp; //deallocate memory in this node
    }

    last = NULL; //initialize last to NULL, while loop already set first to NULL
    count = 0; //no more nodes..
}

template <class Type>//O(n)
void linkedListType<Type>::initializeList() //p287, reinitialize list to empty state, delete nodes
{
    destroyList(); //if list has any nodes, delete them
}

template <class Type>//O(n)
void linkedListType<Type>::print() const
{
    nodeType<Type> *current; //pointer to traverse list, if you use first, list will be lost
    current = first;
    while (current != NULL) //while more data to print, loop
    {
        cout << current->info << " ";
        current = current->link; //next node
    }
}

template <class Type>//O(1)
int linkedListType<Type>::length() const //return int count number
{
    return count; //member var that counts amount of nodes in list
}

template <class Type>//O(1)
Type linkedListType<Type>::front() const //returns info in first node
{
    assert(first != NULL); //if list NULL, assert terminates program
    return first->info; //return info of first node
}

template <class Type>//O(1)
Type linkedListType<Type>::back() const // returns info in last node
{
    assert(last != NULL); //term if NULL
    return last->info;//info of last node
}

//iterators begin and end, for use in for loops?
template <class Type>//O(1)
//Type(iterator)            memberclass::member
linkedListIterator<Type> linkedListType<Type>::begin() //begin iterator
{
    linkedListIterator<Type> temp(first);
    return temp;
}

template <class Type>//O(1)
//Type(iterator)            memberclass::member
linkedListIterator<Type> linkedListType<Type>::end() //end iterator
{
    linkedListIterator<Type> temp(NULL);
    return temp;
}

//make deep copy of list
template <class Type>//O(n)
void linkedListType<Type>::copyList(const linkedListType<Type>& otherList)//const, don't want to change list
{   //create ptrs to be used
    nodeType<Type> *newNode; //ptr to create a node
    nodeType<Type> *current; //ptr to traverse list

    if (first != NULL) //if list nonempty, then make it empty
        destroyList();

    if (otherList.first == NULL) //otherList is empty
    {
        first = NULL;
        last = NULL;
        count = 0;
    }
    else
    {
        current = otherList.first; //current points to list to be copied
        count = otherList.count;
        //copy first node-head
        first = new nodeType<Type>; //create node
        first->info = current->info; //copy info
        first->link = NULL; //set the link field of node to NULL
        last = first; //make last point to first
        current = current->link; //point current to next node

        //copy remaining list
        while (current != NULL)
        {
            newNode = new nodeType<Type>; //create node
            newNode->info = current->info; //copy info
            newNode->link = NULL; //set link of newNode to NULL
            last->link = newNode; //attach newnode after last
            last = newNode; //make last point to actual last
            current = current->link; //point current to next node
        }
    }
}

template <class Type>//O(n)
linkedListType<Type>::~linkedListType() //destructor
{
    destroyList();
}

template<class Type>//O(n)
linkedListType<Type>::linkedListType(const linkedListType<Type>& otherList) //copy constructor
{
    first = NULL; //must be NULL to use copyList
    copyList(otherList);
}

template <class Type>//O(n)
const linkedListType<Type>& linkedListType<Type>::operator=(const linkedListType<Type>& otherList)
//overloaded assignment operator
{
    if (this != &otherList) //avoid self-copy
    {
        copyList(otherList);
    }

    return *this; //return value of this pointer
}

template <class Type>//O(n)
bool unorderedLinkedList<Type>::search(const Type& searchItem) const
{ //search for item then return true if found
    nodeType<Type> *current; //create pointer to traverse list
    bool found = false; //loop controll variable, if true stop
    current = first; //current points to first node in list

    while (current != NULL && !found) //repeat until end of list, and found is true
    //above will keep looping while found is not true, the moment found is true,
    //i.e. opposite of !found, it will stop the loop.
        if (current->info == searchItem) //searchItem is found
            found = true;
        else
            current = current->link; //point current to next node, move through list
    return found;
}

template <class Type>//O(1)
void unorderedLinkedList<Type>::insertFirst(const Type& newItem)
{
    nodeType<Type> *newNode; //pointer to create the new node
    newNode = new nodeType<Type>; //allocate memory for and create node
    newNode->info = newItem; //store new item inside new node
    newNode->link = first; //insert newnode before first
    first = newNode; //make first point to actual first node
    count++; //increment count, size of list

    if (last == NULL)
        last = newNode; //if list was empty, set last to point to newnode as last
}

template <class Type>//O(1)
void unorderedLinkedList<Type>::insertLast(const Type& newItem)
{
    nodeType<Type> *newNode; //pointer to create new node
    newNode = new nodeType<Type>; //allocate new memory for node and create it
    newNode->info = newItem; //store new item in the node
    newNode->link = NULL; //set link of newnode to NULL, it's at end of list after all

    if (first == NULL) //if the list is empty, newNode is both first and last node
    {
        first = newNode;
        last = newNode;
        count++; //increment size/counter of list
    }
    else //list not empty, insert newnode after last
    {
        last->link = newNode; //insert newNode after last
        last = newNode; //make last point to actual last node in list
        count++; //increment list size count
    }
}

int main()
{
    cout << "Hello world!" << endl;
    return 0;
}//UML on page 285