#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;

#include "ctimer.h"
#include "tvector.h"

class Unique
{
  public:
    virtual void add(const string& s) = 0;
    void add(const tvector<string>& list);

    virtual int size()                         const = 0;
    virtual void getAll(tvector<string>& list) const = 0;
};

void Unique::add(const tvector<string>& list)
{
    for(int k=0; k < list.size(); k++){
	add(list[k]);
    }
}

class VectorUnique : public Unique
{
  public:
    VectorUnique(){
	
    }
    virtual ~VectorUnique(){ }
    virtual void add(const string& s){
	for(int k=0; k < myWords.size(); k++){
	    if (myWords[k] == s) return;
	}
	myWords.push_back(s);
    }
    
    virtual int size() const {
	return myWords.size();
    }

    virtual void getAll(tvector<string>& list) const {
	list = myWords;
    }

  private:
    
    tvector<string> myWords;  
};

class ListUnique : public Unique
{
  public:
    ListUnique()
	: myFirst(0),
	  myCount(0)
    {
	
    }
    virtual ~ListUnique(){ }
    virtual void add(const string& s){

	myFirst = addHelper(s,myFirst);
    }
    
    virtual int size() const {
	return myCount;
    }

    virtual void getAll(tvector<string>& list) const {
	Node * current = myFirst;
	while (current != 0){
	    list.push_back(current->info);
	    current = current->next;
	}	
    }

  protected:
    
    struct Node {
	string info;
	Node * next;
	Node (const string& s, Node * link)
	    : info(s),
	      next(link)
	{
	    
	}
    };

    virtual Node * addHelper(const string& s, Node * list) {
	
	Node * first = list;
	
	while (list != 0){
	    if (list->info == s){
		return first;
	    }
	    list = list->next;
	}
	first = new Node(s,first);  // add to front
	myCount++;
	return first;
    }
    
    
    Node * myFirst;
    int myCount;
};

class VectorListUnique : public ListUnique
{
  public:
    VectorListUnique()
	: ListUnique(),
	  myList(256,0)
    {
	    
    }

    void add(const string& s) {
	int index = s[0];
	myList[index] = addHelper(s,myList[index]);
    }
    

    void getAll(tvector<string>& list) const {
	
	for(int k=0; k < myList.size(); k++){
	    Node * current = myList[k];
	    while (current != 0){
		list.push_back(current->info);
		current = current->next;
	    }
	}
    }
        
  private:
    
    tvector<Node *> myList;
};

double stress(const tvector<string>& list, Unique * unique){

    CTimer timer;
    timer.Start();
    unique->add(list);
    timer.Stop();
    return timer.ElapsedTime();
}

int main(int argc, char * argv[])
{
    tvector<string> list;
    string filename,word;

    if (argc > 1) {
        filename = argv[1];
    }
    else {
        cout << "enter filename: ";
        cin >> filename;
    }
    ifstream input(filename.c_str());
    while (input >> word) {
        list.push_back(word);
    }

    Unique * vectUn  = new VectorUnique();
    Unique * listUn  = new ListUnique();
    Unique * vlistUn = new VectorListUnique();

    cout << "vector time =\t "     << stress(list,vectUn)
	 << " size = " << vectUn->size() << endl;
    
    cout << "list time =\t "       << stress(list,listUn)
	 << " size = " << listUn->size() << endl;
    
    cout << "vlist time =\t " << stress(list,vlistUn)
	 << " size = " << vlistUn->size() << endl;

    return 0;
}