//node.h
#ifndef NODE_H
#define NODE_H

#include <iostream>

using namespace std;

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

#endif
//end of node.h

//linkedListIterator.h
#ifndef LINKED_LIST_ITERATOR_H
#define LINKED_LIST_ITERATOR_H
#include <iostream>
#include "node.h"

using namespace std;

template <class Type>
class linkedListIterator
{
    public:
        linkedListIterator();
        //default constructor.
        //postCondition: current = null;

        linkedListIterator(nodeType<Type> *ptr);
        //constructor with aparameter.
        //postCondition: current = ptr;

        Type operator* ();
        //function to overload the dereferencing operator *.
        //postCondition: returns the info contained in the node.

        linkedListIterator<Type> operator++();
        //overload the pre-increment operator.
        //postCondition: the iterator is advanced to the next node.

        bool operator == (const linkedListIterator<Type> &right) const;
        //overload the equality operator.
        //postCondition: Returns true if this iterator is equal to
        //               the iterator specified by right,
        //               otherwise it returns false.

        bool operator !=(const linkedListIterator<Type> &right) const;
        //overload the not equal to operator
        //postCondition: returns true if this iterator is not equal
        //               to the iterator specified by right,
        //               otherwise it returns false.

    private:
        nodeType<Type> *current;
        //pointer to point to the current node in the linked list
};
#endif
//end of linkedListIterator.h

//linkedListIterator.cpp
#include <iostream>
#include "linkedListIterator.h"
#include "node.h"

using namespace std;

template <class Type>
linkedListIterator<Type>::linkedListIterator()
{
    current = NULL;
}
template <class Type>
linkedListIterator<Type>::
                        linkedListIterator(nodeType<Type> *ptr)
{
    current = ptr;
}

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

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

template <class Type>
bool linkedListIterator<Type>::operator ==
                    (const linkedListIterator<Type> &right) const
{
    return (current == right.current);
}

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

//end of linkedListIterator.cpp

//linkedListType.h
#ifndef LINKED_LIST_TYPE_H
#define LINKED_LIST_TYPE_H
#include <iostream>
#include "linkedListIterator.h"
#include "node.h"

using namespace std;

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

    void initializeList();
    //initialize the list to an empty state.
    //postCondition: first = NULL, last = NULL, count = 0;

    bool isEmptyList() const;
    //function to ditermine whether the list is empty.
    //postCondition: returns true if the list is empty,
    //otherwise returns false

    void print() const;
    //function to output the data contained in each node.
    //postcondition: none

    int length() const;
    //function to return the number of nodes in the list.
    //postcondition: the value of count is returned.

    void destroyList();
    //function to delete all the nodes from the list.
    //postCondition: first = NULL, last = NULL, count = 0;

    Type front() const;
    //function to return the first element of the list.
    //preCondition: the list must exist and must not be empty.
    //postCondition: if the list is empty, the program
    //                  terminates; otherwise, the first
    //                  element of the list is returned.

    Type back() const;
    //function to return the last element of the list.
    //preCondition: the list must exist and must not be empty.
    //postCondition: if the list is empty, the program terminates;
    //                      otherwise the last element
    //                      of the list is returned.

    virtual bool search(const Type& searchItem) const = 0;
    //function to determine whether searchItem is in the list.
    //postCondition: returns true if searchItem is in the list.
    //otherwise the value false is returned

    virtual void insertFirst(const Type &newItem) = 0;
    //function to insert newItem at the beginning of the list.
    //postCondition: first points to the new list, newItem is
    //              inserted at the end of the list,
    //              last points to the last node in the list,
    //              and count is incremented by 1.

    virtual void insertLast(const Type &newItem) = 0;
    //function to insert newItem at the end of the list
    //postCondition: first points to the new list,
    //               newItem is inserted
    //               at the end of the list,
    //               last points to the last node in the list,
    //               and count is incremented by 1.

    virtual void deleteNode(const Type &deleteItem) = 0;
    //function to delete deleteItem from the list.
    //postCondition: if found, the node containing
    //               deleteItem is deleted from the list.
    //               first points to the first node,
    //               last points to the last node of the updated
    //               list, and count is decremented by 1.

    linkedListIterator<Type> begin();
    //function to return an iterator at the beginning of the linked list
    //postCondition: returns an iterator such that current is set to first.

    linkedListIterator<Type> end();
    //function to return an iterator one element past the last
    //element of the linked list.
    //postCondition: returns an iterator such that current is set to NULL

    linkedListType();
    //default constructor
    //initializes the list to an empty state.
    //postCondition: first = NULL, last = NULL, count = 0;

    linkedListType(const linkedListType<Type> &otherList);
    //copy constructor

    ~linkedListType();
    //destructor
    //deletes all the nodes from the list.
    //postCondition: the list object is destroyed.

protected:
    int count; //variable to store the number of elements in the list
    nodeType<Type> *first; //pointer to the first node of the list
    nodeType<Type> *last; //pointer to the last node of the list

private:
    void copyList(const linkedListType<Type> &otherList);
    //function to make a copy of otherList.
    //postCondition: a copy of otherList is created and assigned to this list.

};
#endif
//end of linkedListType.h

//linkedListType.cpp
#include <iostream>
#include "linkedListIterator.h"
#include "linkedListType.h"

using namespace std;

template <class Type>
bool linkedListType<Type>::isEmptyList() const
{
    return (first == NULL);
}

template <class Type>
linkedListType<Type>::linkedListType() //default constructor
{
    first = NULL;
    last = NULL;
    count = 0;
}

template <class Type>
void linkedListType<Type>::destroyList()
{
    nodeType<Type> *temp; //pointer to deallocate the memory
                         //occupied by the node
    while (first != NULL) //while there are nodes in the list
    {
        temp = first;    //set temp to the current node
        first = first -> link; //advance first to the next node
        delete temp;        //deallocate the memory occupied by temp
    }

    last = NULL; //initialize last to NULL; first has already
                //been set to NULL by the while loop
    count = 0;
}

template <class Type>
void linkedListType<Type>::initializeList()
{
    destroyList(); //if the list has any nodes, delete them
}

template <class Type>
void linkedListType<Type>::print() const
{
    nodeType<Type> *current; //pointer to traverse the list

    current = first; //set current so that it points to the first node

    while (current != NULL) //while more data to print
    {
        cout << current -> info << " ";
        current = current -> link;
    }
} //end print

template <class Type>
int linkedListType<Type>::length() const
{
    return count;
}

template <class Type>
Type linkedListType<Type>::front() const
{
    assert (first != NULL);
    return first -> info; //return the info of the first node
}//end front
template <class Type>
Type linkedListType<Type>::back() const
{
    assert (last != NULL);

    return last -> info; //return the info of the last node
}//end back

template <class Type>
linkedListIterator<Type> linkedListType<Type>::begin()
{
    linkedListIterator<Type> temp(first);

    return temp;
}

template <class Type>
linkedListIterator<Type> linkedListType<Type>::end()
{
    linkedListIterator<Type> temp(NULL);

    return temp;
}

template <class Type>
void linkedListType<Type>::copyList
                    (const linkedListType<Type> &otherList)
{
    nodeType<Type> *newNode; //pointer to create a node
    nodeType<Type> *current; //pointer to traverse the list

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

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

        //copy the remaining list

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

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

template<class Type>
linkedListType<Type>::linkedListType(const linkedListType<Type> &otherList)
{
    first = NULL;
    copyList(otherList);
} //end copy constructor

template<class Type>
const linkedListType<Type> &linkedListType<Type>::operator=
                            (const linkedListType<Type> &otherList)
{
    if (this != &otherList) //avoid self-copy
    {
        copyList(otherList);
    }//end if/else
    return this;
}
//end of linkedListType.cpp

//unorderedLinkedList.h
#ifndef UNORDERED_LINKED_LIST_H
#define UNORDERED_LINKED_LIST_H

#include <iostream>
#include "node.h"
#include "linkedListType.h"
#include "linkedListIterator.h"

using namespace std;

template <class Type>
class unorderedLinkedList: public linkedListType<Type>
{
public:
    bool search(const Type &searchItem) const;
    //function to determine whether searchItem is in the list.
    //postCondition: returns true if searchItem is in the list,
    //               otherwise the value false is returned

    void insertFirst(const Type &newItem);
    //function to insert newItem at the beginning of the list.
    //postCondition: first point to the new list, newItem is
    //               inserted at the beginning of the list,
    //               last points to last node in the list,
    //               and count is incremented by 1.

    void insertLast(const Type &newItem);
    //function to insert newItem at the end of the list.
    //postCondition: first points to the new list,
    //               newItem is inserted at the end of the list,
    //               last points to the last node in the list,
    //               and count is incremented by 1.

    void deleteNode(const Type &deleteItem);
    //function to delete deleteItem from the list.
    //postCondition: if found, the node containing
    //               deleteItem is deleted from the list.
    //               first points to the first node,
    //               last points to the last node of the updated
    //               lis, and count is decremented by 1.

};
#endif
//end of unorderedLinkedList.h

//unorderedLinkedList.cpp
#include <iostream>
#include "node.h"
#include "linkedListIterator.h"
#include "linkedListType.h"
#include "unorderedLinkedList.h"

using namespace std;

template <class Type>
bool unorderedLinkedList<Type>::
                    search(const Type &searchItem) const
{
    nodeType<Type> *current; //pointer to traverse the list
    bool found = false;
    current = first; //set current to point to the first
                    //node in the list
    while (current != NULL && !found) //search the list
        if(current -> info == searchItem) //search item is found
            found = true;
        else
            current = current -> link; //make current point to the next node
        return found;
}//end search

template <class Type>
void unorderedLinkedList<Type>::insertFirst(const Type &newItem)
{
    nodeType<Type> *newNode; //pointer to create the new node
    newNode = new nodeType<Type>; //creat the new node
    newNode -> info = newItem; //store the new item in the node
    newNode -> link = first; //insert newNode before first
    first = newNode; //make first pointo the actual first node
    count ++;       //increment count

    if (last == NULL) //if the list was empty, newNode is also the last node in the list
        last = newNode;
}//end insertFirst

template<class Type>
void unorderedLinkedList<Type>::insertLast(const Type &newItem)
{
    nodeType<Type> *newNode; //pointer to create the new node

    newNode = new nodeType<Type>; //create the new node
    newNode -> info = newItem; //store the new item in the node
    newNode -> link = NULL; //set the link field of newNode to NULL

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


template <class Type>
void unorderedLinkedList<Type>::deleteNode(const Type &deleteItem)
{
    nodeType<Type> *current; //pointer to traverse the list
    nodeType<Type> *trailCurrent; //pointer just before current
    bool found;

    if (first == NULL) //case 1; the list is empty
        cout << "Cannot delete from an empty list." << endl;
    else
    {
        if(first -> info == deleteItem) //case 2
        {
            current = first;
            first = first -> link;
            count --;

            if(first == NULL) //the list has only one node
               last = NULL;

            delete current;
        }
        else //search the list for the node for node with the given info
        {
            found = false;
            trailCurrent = first; //set trailCurrent to point
                                 //to the first node
            current = first ->link; //set current to point to
                                    //the second node

            while (current != NULL && !found)
            {
                if (current -> info != deleteItem)
                {
                    trailCurrent = current;
                    current = current -> link;
                }
                else
                found = true;
            } //end while
            if(found) //case3; if found, delete the node
            {
                trailCurrent -> link = current -> link;
                count --;

                if (last == current) //node to be deleted was last node
                last = trailCurrent; //update the value of last
                delete current; //delete the node from the list
            }
            else
                cout << "The item to be deleted is not in the list." << endl;
            }//end else
        }//end else
    }//end deleteNode
//end of unorderedLinkedList.cpp

//orderedLinkedList.h
#ifndef ORDERED_LINKED_LIST_H
#define ORDERED_LINKED_LIST_H

#include <iostream>
#include "linkedListType.h"
#include "node.h"

using namespace std;

template <class Type>
class orderedLinkedList: public linkedListType<Type>
{
public:
    bool search (const Type &searchItem) const;
    //function to determine whether searchitem is in the list.
    //postCondition: returns true if searchItem is in the list,
    //otherwise returns the value false

    void insert(const Type &newItem);
    //function to insert newItem in the list.
    //postCondition: first points to the new list, newItem
    //               is inserted at the proper place in the list,
    //               and count is incremented by 1.

    void insertFirst(const Type &newItem);
    //function to insert newItem at the beginning of the list.
    //postCondition: first points to the new list,
    //               newItem is inserted at the proper place in the list,
    //               last points to the last node in the list,
    //               and count is incremented by 1.

    void insertLast (const Type &newItem);
    //function to insert newItem at the end of the list.
    //postCondition: first points to the new list,
    //               newItemis inserted at the proper place in the list,
    //               last points to the last node in the list,
    //               and count is incremented by 1.

    void deleteNode(const Type &deleteItem);
    //function to delete deleteItem from the list.
    //postCondition: if found, the node containing deleteItem
    //               is deleted from the list,
    //               first points to the first node of the new list,
    //               and count is decremented by 1.
    //               if deleteItem is not in the list,
    //               an appropriate message is printed.

};

#endif
//end of orderedLinkedList.h

//orderedLinkedList.cpp
#include <iostream>
#include "node.h"
#include "linkedListType.h"
#include "orderedLinkedList.h"

using namespace std;

template <class Type>
bool orderedLinkedList<Type>::
                      search(const Type &searchItem) const
{
    bool found = false;
    nodeType<Type> *current; //pointer to traverse the list

    current = first; //start the search at the first node

    while (current != NULL && !found)
        if (current -> info >= searchItem)
            found = true;
        else
            current = current -> link;

        if(found)
            found = (current -> info == searchItem); //test for equality

    return found;
}//end search

template<class Type>
void orderedLinkedList<Type>::insert(const Type &newItem)
{
    nodeType<Type> *current; //pointer to traverse the list
    nodeType<Type> *trailCurrent; //pointer just before current
    nodeType<Type> *newNode; //pointer to create a new node
    bool found;

    newNode = new nodeType<Type>; //create the node
    newNode -> info = newItem; //store newItem in the node
    newNode -> link = NULL; //set the link field of the node to NULL

    if (first == NULL) //case 1
    {
        first = newNode;
        last = newNode;
        count ++;
    }
    else
    {
        current = first;
        found = false;

        while (current != NULL && !found) //search the list
            if(current -> info >= newItem)
                found = true;
            else
            {
                trailCurrent = current;
                current = current -> link;
            }
        if (current == first) //case 2
        {
            newNode -> link = first;
            first = newNode;
            count ++;
        }
        else                //case 3
        {
            trailCurrent -> link = newNode;
            newNode -> link = current;

            if(curent == NULL)
                last = newNode;

            count ++;
        }
    }
}

template <class Type>
void orderedLinkedList<Type>::insertFirst(const Type &newItem)
{
    insert(newItem);
}

template <class Type>
void orderedLinkedList<Type>::insertLast(const Type &newItem)
{
    insert(newItem);
}//end insertLasttemplate <class Type>

template <class Type>
void orderedLinkedList<Type>::deleteNode(const Type &deleteItem)
{
    nodeType<Type> *current; //pointer to traverse the list
    nodeType<Type> *trailCurrent; //pointer just before curent
    bool found;

    if(first == NULL) //case 1
        cout << "Cannot delete from an empty list." << endl;
    else
    {
        current = first;
        found = false;

        while (current != NULL && !found) //search the list
            if (current -> info >= deleteItem)
                found = true;
            else
            {
                trailCurrent = current;
                current = current ->link;
            }
        if(current == NULL) //case 4
            cout << "The item to be deleted is not in the list." << endl;
        else
            if(current -> info == deleteItem)//the item to be delete is in the list
            {
                if(first == current) //case 2
                {
                    first = first -> link;

                    if (first == NULL)
                        last = NULL;

                        delete current;
                }
                count --;
            }
            else
                cout << "The item to be deleted is not in the list." << endl;
        }
}//end deleteNode

//end of orderedLinkedList.cpp