#include <iostream>
#include <fstream>

using namespace std;

template <typename T>struct node
{
    T data;
    node *prev;
};

template <class T> class templateinterface
{
    int numberofitems;
    node<T> *head;
    node<T> *current;
    node<T> *previous;

public:
    templateinterface()
    {
        head = new node<T>;
        current = head;
        previous = head;
    }
    bool isEmpty()
    {
        bool re = false;
        if(numberofitems == 0)
        {
            re = true;
        }
        return re;
    }
    bool add(T newEntry)
    {
        current = new node<T>;
        current->data = newEntry;
        current ->prev = NULL;
        previous->prev = current;
        previous = current;
        numberofitems++;
        return (true);
    }
    bool remove(T anEntry)
    {
        node<T> *runner;
        bool found = false;

        runner = head;
        while(runner->prev != NULL)
        {
            if (runner->data == anEntry)
            {
                runner->prev = runner->prev->prev;
                numberofitems-=1;
                found = true;
            }
            else
            {
                runner = runner->prev;
            }
        }
        return (found);
    }
    void clear()
    {
        node<T> *runner;
        node<T> *temp;

        runner = head;
        while(runner->prev != NULL)
        {
            temp = runner->prev;
            runner->data = NULL;
            runner->prev = NULL;
            runner = temp;
        }

    }
    int getFrequencyOf(T anEntry)
    {
        node<T> *runner;
        int index = 0;

        runner = head;
        while(runner->prev != NULL)
        {
            if (runner->data == anEntry)
            {
                index+= 1;
                cout << index;
            }
            runner = runner->prev;
        }
        return index;
    }
    bool contains(T anEntry)
    {
        node<T> *runner;
        bool found = false;

        runner = head;
        while(runner->prev != NULL)
        {
            if (runner->data == anEntry)
            {
                runner->prev = runner->prev->prev;
                found = true;
            }
            else
            {
                runner = runner->prev;
            }
        }
        return found;
    }
};

int main()
{
    templateinterface<string> face;
    string anEntry;
    string test = "house";

    cout << "Reading file ... Words.txt " << endl;
    ifstream infile("Words.txt");
    while(!infile.eof())
    {
        infile >> anEntry;
        face.add(anEntry);
    }
    cout << "The word house " << (face.contains() ? "is" : "is not") << " in the file"
    << " (occurs " << face.getFrequencyOf(test) << " times)" << endl;
    return (0);
}