#include <iostream>
#include <string>

using namespace std;

//Some forward declarations to help the compiler and for organization.
template <class Type>
struct nodeType;

template <class Type>
class linkedListType;

template <class Type>
class unorderedLinkedListType;

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


//The linked list class
template <class Type>
class linkedListType {
public:

    linkedListType();
    ~linkedListType();

    virtual void deleteNode(const Type&) = 0;

protected:
    nodeType<Type> *first;
    nodeType<Type> *last;
    int count;
};

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

template <class Type>
linkedListType<Type>::~linkedListType() {
    nodeType<Type> *temp;
    while (first != NULL) {
        temp = first;
        first = first->link;
        delete temp;
    }
    last = NULL;
    count = 0;
}





//The unordered linked list class
template <class Type>
class unorderedLinkedList : public linkedListType<Type> {
public:
    void insertFirst(const Type& newItem);
    void insertLast(const Type& newItem);
    void deleteNode(const Type& deleteItem);

};


template <class Type>
void unorderedLinkedList<Type>::insertFirst(const Type& newItem) {
    nodeType<Type> *newNode;
    newNode = new nodeType<Type>;
    newNode->info = newItem;
    newNode->link = first;
    first = newNode;
    count++;
    if (last == NULL) {
        last = newNode;
    }
}

template <class Type>
void unorderedLinkedList<Type>::insertLast(const Type& newItem) {
    nodeType<Type> *newNode;
    newNode = new nodeType<Type>;
    newNode->info = newItem;
    newNode->link = NULL;

    if (first == NULL) {
        first = newNode;
    } else {
        last->link = newNode;
    }
    last = newNode;
    count++;
}

template <class Type>
void unorderedLinkedList<Type>::deleteNode(const Type& deleteItem) {
    nodeType<Type> *current;
    nodeType<Type> *trailCurrent;
    bool found;

    if (first == NULL)
        cout << "Can't delete from an empty list" << endl;
    else {
        if (first->info == deleteItem) {
            current = first;
            first = first->link;
            count--;
            if(first == NULL)
                last = NULL;
            delete current;

        }
        else {
            found = false;
            trailCurrent = first;
            current = first->link;
            while (current != NULL && !found) {
                if (current->info != deleteItem) {
                    trailCurrent = current;
                    current = current->link;
                }
                else {
                    found = true;
                }
            }
            if (found) {
                trailCurrent->link = current->link;
                count--;
                if (last == current) {
                    last = trailCurrent;
                }
                delete current;
            } else {
                cout << "The item wasn't found" << endl;
            }
        }
    }
}


template <class Type>
class priorityQueue {
public:
    priorityQueue();
protected:
    unorderedLinkedList<Type> *u;
};

template <class Type>
priorityQueue<Type>::priorityQueue() {
    u = new unorderedLinkedList<Type>();
}

int main () {

    priorityQueue<string> *pQueue = new priorityQueue<string>();
    pQueue->push_back("cat");
    pQueue->push_back("dog");
    pQueue->push_back("slug");
    pQueue->push_back("spider");
    pQueue->push_back("rock");
    cout << pQueue->pop_front() << endl;  //Should display "cat"
    cout << pQueue->pop_front() << endl;  //Should display "dog"
    cout << pQueue->pop_front() << endl;  //Should display "slug"
    pQueue->push_front("apple");
    pQueue->push_front("orange");
    pQueue->push_front("banana");
    pQueue->push_front("lemon");
    pQueue->push_front("lime");
    pQueue->push_front("grape");
    cout << pQueue->pop_back() << endl;  //Should display "rock"
    cout << pQueue->pop_back() << endl;  //Should display "spider"
    pQueue->push_back_with_priority("The president of the United States", 2);
    pQueue->push_back_with_priority("The prime minister of the United Kingdom", 2);
    pQueue->push_back_with_priority("An average WSU CS student", 1);
    pQueue->push_back_with_priority("An average WSU marketing student", 0);
    pQueue->push_back_with_priority("Brad Peterson", 3);
    for (int i = 0; i < 11; i++) {
        cout << pQueue->pop_first_highest_priority() << endl;
    }
    delete pQueue;
    system("pause");
    return 0;
}