#include <iostream.h>
#include <apvector.h>
#include <apstring.h>
#include <iomanip.h>
#include <fstream.h>

struct dataType
{
	apstring word;
	int  count;  // occurrences of word
};

struct listType
{
	apvector<dataType> list;
	int number;	 // number of words in list
};


void parseWords (ifstream &, listType &);
bool validLetter (char c1);
void lowerCaseWord (apstring &);
void addWord (listType &, apstring);
int searchForWord (const listType &, apstring);
void swap (dataType &, dataType &);
void sortByWord (listType &);
void qSortByCount (apvector<dataType> &, int, int);
void printTopCount (const listType &, int);


int main(void)
{
	ifstream inFile("dream2.txt");
	listType data;
	
	data.list.resize(100);		
	    // start off with a capacity for 100 words
	data.number = 0;
	
	parseWords (inFile,data);
	qSortByCount (data.list,0,data.number-1);
	printTopCount (data,data.number);
	return 0;
}


bool validLetter (char c1)
{
	if (('A'<=c1) && (c1<='Z'))
		return true;
	else if (('a'<=c1) && (c1<='z'))
		return true;
	else if ('\'' == c1)
		return true;
	else
		return false;
}

void parseWords (ifstream &inFile, listType &data)
{
	apstring word, blank;
	char oldC, current;
	
	if (inFile.get(oldC))		
		// load first letter
	{
		if (validLetter(oldC))
			word += oldC;
		while (inFile.get(current))
		{
			if ('-' == current)
			{
				if (word != blank)		
			// a hyphenated word, such as sixty-three
					word = word + current;
			} // end if '-'
			else if (validLetter(current))	
				// alphabet letter or '
			{
				word = word + current;
			} // end validLetter(current)
			else if (validLetter (oldC) && !(validLetter(current)))
			{
				addWord (data,word);
				// cout << word << endl;
				word = blank;
			}
			oldC = current;
		}
	}
}	

void lowerCaseWord (apstring &word)
{	
	for (int k=0; k<word.length(); k++)
		if (('A'<=word[k]) && (word[k]<='Z'))
			word[k]+=32;
}
		
void addWord (listType &data, apstring nextWord)
/*  will add nextWord to data.  Sequence of events:
	1.  search for nextWord in data, if found, add one to count field
	2.  if nextWord is not in data, add to list using an insertion
sort algorithm
		 and update count of words in list by +1.  */
{
	int index;
	
	lowerCaseWord (nextWord);
	index = searchForWord (data, nextWord);
	if (-1 == index)		// nextWord is a new word in list
	{
		if (data.number == data.list.length()) 	
			data.list.resize(data.number+10);
		data.number++;
		data.list[data.number-1].word = nextWord;
		data.list[data.number-1].count = 1;
		index = data.number-1;
		while ((index > 0) && (data.list[index-1].word >
data.list[index].word))
		{
			swap (data.list[index-1], data.list[index]);
			index--;
		}
	}
	else
	{
		data.list[index].count++;
	}
}

int searchForWord (const listType &data, apstring w1)
// searches for w1 in list using a binary search
{
	int low=0, high=data.number-1, mid;
	
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (data.list[mid].word == w1)
			return mid;
		else 
			if (w1 < data.list[mid].word)
				high = mid - 1;
			else
				low = mid + 1;
	}
   return -1;
}


void swap (dataType &one, dataType &two)
{
	dataType temp = one;
	one = two;
	two = temp;
}

void qSortByCount (apvector<dataType> &list, int first, int last)
// quickSort in descending order
{
	int g = first, h = last;
	int midIndex;
	int dividingValue;

	midIndex = (first + last) / 2;
	dividingValue = list[midIndex].count;
	do
	{
		while (list[g].count > dividingValue) g++;
		while (list[h].count < dividingValue) h--;
		if (g <= h)
		{
			swap(list[g], list[h]);
			g++;
			h--;
		}
	}
	while (h > g);
	if (h > first) qSortByCount (list,first,h);
	if (g < last) qSortByCount (list,g,last);
}

	
void printTopCount (const listType &data, int howMany)
{
	int k, line=1, num=0;
	
	cout << setiosflags (ios::right);
	for (k=0; k<howMany; k++)
	{
		num += data.list[k].count;
		cout << setw(3) << line << setw(6) << data.list[k].count;
		cout << "   " << data.list[k].word << endl;
		if (line % 5 == 0) cout << endl;
		line++;
	}
	cout << "Number of words used = " << data.number << endl;
	cout << "Total # of words = " << num << endl;
}