//
// countwrd.cpp
//
// Reads a text file and builds a frequency table for the words that
// appear in the file.  Allows the user to compare heuristics for
// how the linked list of words/frequencies should be maintained
// to speed up searches.
//
// Computer Science S-111, Harvard University
//

#include <assert.h>
#include <fstream.h>
#include <iomanip.h>
#include <iostream.h>
#include "list.hpp"    
#include "../util/getinput.hpp"


//
// This class will be used to store a word and a count of the
// number of times that it appears in the file.
//
class dictitem {
public:
    char *word;
    int count;

    dictitem();
    dictitem(int word_length);
    dictitem(const dictitem& a);

    const dictitem& operator =(const dictitem& a);
    friend bool operator ==(const dictitem& a, const dictitem& b);
    friend bool operator <(const dictitem& a, const dictitem& b);
    friend ostream& operator <<(ostream& s, const dictitem& a);
    friend istream& operator >>(istream& s, const dictitem& a);
};

dictitem::dictitem()
{
    word = new char[81];
}

dictitem::dictitem(int length)
{
    assert(length > 0 && length <= 80);
    word = new char[length+1];
}

dictitem::dictitem(const dictitem& a)
{
    word = new char[81];
    strcpy(word, a.word);
    count = a.count;
}

const dictitem&
dictitem::operator =(const dictitem& a)
{
    if (&a != this) {
	delete [] word;
	word = new char[81];
	strcpy(word, a.word);
	count = a.count;
    }
    return *this;
}

bool
operator ==(const dictitem& a, const dictitem& b)
{
    return (!strcmp(a.word, b.word));
}

bool
operator <(const dictitem& a, const dictitem& b)
{
    return (strcmp(a.word, b.word) < 0);
}

ostream&
operator <<(ostream& s, const dictitem& a)
{
    s << a.word;
    return s;
}

istream&
operator >>(istream& s, const dictitem& a)
{
    s >> a.word;
    return s;
}

//
// print_item - used by print_list to print each item in the list.
//
void
print_item(int pos, dictitem item)
{
    if (item.count != 0) {
	cout << setw(5) << pos << " " << item.word << " ";
	cout << item.count << "\n";

	// pause every 20 lines
	if (pos % 20 == 0)
	    if (!GetBoolean("More?", YES))
		exit(1);
    }
}


//
// List-ordering heuristic #1: append new words at the end of the list.
//
int
do_append(list<dictitem>& lst, ifstream& infile, int words_left)
{
    node<dictitem> *item_node;
    dictitem item;
    int num_compares, total_compares;

    total_compares = 0;
    while (!infile.eof() && (words_left > 0)) {
	infile >> item;
	if (!item.word[0])
	    break;
	item.count = 1;

	item_node = lst.search(item, num_compares);
	total_compares += num_compares;

	if (item_node == NULL) 
	    lst.append(item);
	else 
	    item_node->data.count++;
	
	words_left--;
    }

    return total_compares;
}

//
// List-ordering heuristic #2: maintain the list in alphabetical order.
//
int
do_ordered(list<dictitem>& lst, ifstream& infile, int words_left)
{
    node<dictitem> *item_greater_or_equal_node;
    dictitem item;
    int num_compares, total_compares;

    total_compares = 0;
    while (!infile.eof() && words_left > 0) {
	infile >> item;
	if (!item.word[0])
	    break;
	item.count = 1;

	item_greater_or_equal_node = lst.search_ordered(item, num_compares);
	total_compares += num_compares;

	if (!(item == item_greater_or_equal_node->data)) 
	    lst.insert(item_greater_or_equal_node, item);
	else 
	    item_greater_or_equal_node ->data.count++;

	words_left--;
    }

    return total_compares;
}

//
// List-ordering heuristic #3: as each word is read, move/insert it at
// the front of the list.
//
int
do_movefront(list<dictitem>& lst, ifstream& infile, int words_left)
{
    node<dictitem> *item_node;
    dictitem item;
    int num_compares, total_compares;

    total_compares = 0;
    while (!infile.eof() && words_left > 0) {
	infile >> item;
	if (!item.word[0])
	    break;
	item.count = 1;

	item_node = lst.search(item, num_compares);
	total_compares += num_compares;

	if (item_node != NULL) {
	    //
	    // The item is already in the list.  Remove it
	    // so that it can be put at the front of the list.
	    // Note that we use the version of remove() that
	    // gives us the data from the node being removed,
	    // because that item has the correct count for
	    // the word, and thus we need to insert it, rather
	    // than the item created above.
	    //
	    lst.remove(item_node, item);
	    item.count++;
	}
	lst.insert(lst.first(), item);

	words_left--;
    }

    return total_compares;
}

//
// List-ordering heuristic #4: if we've seen a word before, swap it
// with the word that is currently before it in the list.
//
int
do_transpose(list<dictitem>& lst, ifstream& infile, int words_left)
{
    node<dictitem> *item_node, *prev;
    dictitem item;
    int num_compares, total_compares;

    total_compares = 0;
    while (!infile.eof() && words_left > 0) {
	infile >> item;
	if (!item.word[0])
	    break;
	item.count = 1;

	item_node = lst.search(item, num_compares);
	total_compares += num_compares;

	if (item_node == NULL) 
	    lst.append(item);
	else {
	    item_node->data.count++;
	    if (item_node != lst.first()) {
		prev = lst.prev_node(item_node);
		lst.remove(item_node, item);
		lst.insert(prev,item);
	    }
	}

	words_left--;
    }

    return total_compares;
}


//
// List-ordering heuristic #5: like #4, but only do the swap if the
// word has appeared more often than the word in front of it.
//
int
do_count(list<dictitem>& lst, ifstream& infile, int words_left)
{
    node<dictitem> *item_node, *prev;
    dictitem item;
    int num_compares, total_compares;

    total_compares = 0;
    while (!infile.eof() && words_left > 0) {
	infile >> item;
	if (!item.word[0])
	    break;
	item.count = 1;

	item_node = lst.search(item, num_compares);
	total_compares += num_compares;

	if (item_node == NULL) 
	    lst.append(item);
	else {
	    item_node->data.count++;
	    if (item_node != lst.first()) {
		prev = lst.prev_node(item_node);
		if (item_node->data.count > prev->data.count) {
		    lst.remove(item_node, item);
		    lst.insert(prev, item);
		}
	    }
	}

	words_left--;
    }

    return total_compares;
}


//
// List-ordering heuristic #6: order the list in advance based on
// prior knowledge about how often the words tend to occur, putting
// the more frequently occurring words first.
//
int
do_frequency(list<dictitem>& lst, ifstream& infile, int words_left)
{
    ifstream freq_file;
    node<dictitem>* item_node;
    dictitem item;
    int freq, num_compares, total_compares;

    //
    // First build a list of the most common words ordered by
    // from the frequency file.
    //
    freq_file.open(ReadString("Frequency-ordered file?"));
    while (!freq_file.eof()) {
	freq_file >> freq;
	if (freq_file.eof())
	    break;
	freq_file >> item;
	item.count = 0;
	lst.append(item);
    }
    freq_file.close();
    freq_file.clear();

    //
    // Then process the input file.
    //
    total_compares = 0;
    while (!infile.eof() && words_left--) {
	infile >> item;
	if (!item.word[0])
	    break;
	item.count = 1;

	item_node = lst.search(item, num_compares);
	total_compares += num_compares;

	if (item_node == NULL) 
	    lst.append(item);
	else
	    item_node->data.count++;
    }

    return total_compares;
}

//
// write_cmd_list -- give the user a choice of heuristics
//
void
write_cmd_list()
{
    cout << endl;
    cout << "(1) APPEND NEW ITEM\n";
    cout << "(2) ORDERED LIST\n";
    cout << "(3) MOVE TO FRONT\n";
    cout << "(4) TRANSPOSE TO FRONT\n";
    cout << "(5) COUNT ORDER\n";
    cout << "(6) FREQUENCY ORDER\n";
}

int
main(int argc, char* argv[])
{
    list<dictitem> lst;
    ifstream infile;
    int cmd, num_words, total_compares;
    char fname[MAX_NAME_LEN];

    // Get the file name and number of words.
    if (argc< 3) {
	cout << "\nUsage: ./countwrd infile num_words";
	cout << "\nProceeding anyway...";
	cout << "\nName of file: ";
	cin >> fname;
	cout << "\nNumber of words: ";
	cin >> num_words;
    }
    else {
	strcpy(fname,argv[1]);
	num_words = atoi(argv[2]);
    }

    // Give the user a menu of heuristics.
    write_cmd_list();

    do {
	// Get the choice of heuristic.
	cout << endl;
	cmd = ReadInteger("SELECT A STRATEGY (0 TO EXIT)");
	if (cmd == 0)
	    break;

	// Open the text file.
	infile.open(fname);
	if(!infile) {
	    cout << "Bad filename.";
	    exit(1);
	}

	// Use the heuristic on the file and report the results.
	switch (cmd) {
	case 1:
	    total_compares = do_append(lst, infile, num_words);
	    break;
	case 2:
	    total_compares = do_ordered(lst, infile, num_words);
	    break;
	case 3:
	    total_compares = do_movefront(lst, infile, num_words);
	    break;
	case 4:
	    total_compares = do_transpose(lst, infile, num_words);
	    break;
	case 5:
	    total_compares = do_count(lst, infile, num_words);
	    break;
	case 6:
	    total_compares = do_frequency(lst, infile, num_words);
	    break;
	}

	if (cmd > 0 && cmd <=6) {
	    cout << lst.get_num_items() << " ITEMS IN LIST";
	    cout << endl << total_compares << " SEARCHES REQUIRED - ";
	    if (GetBoolean("Show the list?", NO)) {
		lst.print_list();
		write_cmd_list();
	    }

	    lst.reinit();
	    infile.close();
	    infile.clear();
	}
    } while (true);
}
