// dictionary.cpp -- implementation of Dictionary of <string,frequency> pairs
// CSE143 assignment 2 sample solution, hp 1/99

#include <string.h>
#include <ctype.h>
#include <iostream.h>
#include <assert.h>

#include "dictionary.h"


// constructor -- make empty Dictionary
Dictionary::Dictionary( ) {
	sz = 0;
}


// = number of distinct words in this Dictionary
int Dictionary::size( ) const {
	return sz;
}


// = location of word w in this Dictionary or sz if w is not found.
// pre:  length of w <= dictMaxWordLen
// post: lower-case copy of w stored in words[sz].w.
int Dictionary::find(const char *w) {
	int len;  // length of w
	int k;
	
	// copy word w to end of list
	len = strlen(w);
	assert(len <= dictMaxWordLen);
	strcpy(words[sz].w, w);
	
	// convert copy of word w to lower case
	for (k=0; k < len; k++)
		words[sz].w[k] = tolower(words[sz].w[k]);
	
	// sentinal search: see if w is already in the list
	k = 0;
	while (strcmp(words[k].w, words[sz].w) != 0)
		k++;
	
	return k;
}


// Increase number of occurrences of word w in this Dictionary,
// adding it to this Dictionary if needed.
// pre: length of w <= dictMaxWordLen and sz < dictMaxNumWords if w is not
//      already in this Dictionary.
void Dictionary::add(const char * w) {
	int k;   // words[k].w = w
	
	k = find(w);
	if (k == sz) {
		// Add new word to dictionary with frequency 1
		assert(sz < dictMaxNumWords);
		words[sz].freq = 1;
		sz ++;
	} else {
		// Word w already in this Dictionary; increase frequency.
		words[k].freq++;
	}
}


// = "words[i] should appear before words[j] in the sorted list"
bool Dictionary::isLess(int i, int j) const {
	return (words[i].freq > words[j].freq)
		|| (words[i].freq == words[j].freq 
		    && strcmp(words[i].w, words[j].w) < 0);
}


// sort Dictionary in descending order by frequency; words with identical 
// frequencies are further sorted in alphabetical order
void Dictionary::sort( ) {
	int k;		// boundary between sorted and unsorted region (see below)
	int min;	// words[min] is smallest in words[k..sz-1]
	int j;
	wordFreq temp;
	
	// selection sort: words[0..k-1] is the sorted part of the list,
	// words[k..sz-1] is the unsorted part, and all of words[0..k-1] 
	// should appear before words[k..sz-1].
	
	for (k=0; k<sz-1; k++) {
		
		// set min to location of smallest element in words[k..sz-1]
		min = k;
		for (j=k+1; j<sz; j++)
			if (isLess(j,min))
				min = j;
			
			// swap words[min] and words[k]
			temp = words[k];
			words[k] = words[min];
			words[min] = temp;
	}
}


// Stream output: Print Dictionary with one frequency,word pair per line.
// Output begins at the current location on the current line, and ends
// with a newline after the last word is printed.
ostream& operator<<(ostream &s, Dictionary &d) {
	int k;
	
	d.sort();
	for (k = 0; k < d.sz; k++) {
		s << d.words[k].freq << "  " << d.words[k].w << '\n';
	}
	return (s << endl);
	
}