#include <assert.h>
#include "fwList.h"	// for using definitions in the interface of the fwList class

// Version 1 of the WordList class implementation.
// Programmer: Sriram Pemmaraju, Oct 10th, 2003



// default constructor
fwList::fwList () : actualSize(0)
{
	// Nothing needs to be done here. In the initializer list, 
	// actualSize get initialized to 0 and list gets constructed via 
	// an implicit call to the default constructor in the Vector class
}


// constructor that is told the number of elements
// the constructed fwList object needs to have	
fwList::fwList (unsigned int numberOfElements) : 
			actualSize(0),
			list(numberOfElements)
{
	list.resize(numberOfElements) ;
	// Nothing needs to be done here. In the initializer list, actualSize  
	// gets initialized to 0, and a Vector called list
	// with size equal to numberOfElements is constructed

}

// Copy constructor. In the initializer list the variable actualSize
// gets the correct value. An uninitialized Vector called list of the right size
// gets constructed in the initializer list. It acquires correct values inside
// the body of the function
fwList::fwList (const fwList & right) : 
			actualSize(right.actualSize),
			list(right.list.length())
{
	list.resize(right.list.length()) ;
	// Copies the contents of list from the right hand side into list
	int i;
	for (i = 0; i < actualSize; i++){
		list[i].word = right.list[i].word;
		list[i].frequency = right.list[i].frequency ;
	}//for
}


// function to search for a certain word. Returns true if word is found; 
// false otherwise. Also returns position of the found word or position of where
// the word ought to go if inserted. This is an implementation of
// iterative binary search. This depends on the words in list being sorted
// alphabetically
bool fwList::search(const string & myWord, int & position) const
{
	int first = 0;
	int last = actualSize - 1;
	unsigned int mid;

	// Search while there is more of the Vector to look at
	while (first <= last)
	{
		// Look at the midpoint of the Vector
		mid = (first + last) / 2;

		// myWord is found
		if (myWord == list[mid].word)
		{
			position = mid;
			return true;
		}

		// myWord is in the second half
		else if (myWord > list[mid].word)
			first = mid + 1;

		// myWord is in the first half
		else if (myWord < list[mid].word)
			last = mid - 1;
	}

	position = first;
	return false;
}

// function that overloads the operator +=. This changes
// the receiver by adding to it a word
bool fwList::insert(const string & right)
{
	// First determine if the word right is already in list
	int position;
	unsigned int isFound = search(right, position);
	if(isFound){
		// just increment the frequency
		list[position].frequency++ ;
		return false;
	}//if

	// Check if there is enough space in the vector list
	if(actualSize == list.length())
		list.resize(2*list.length()+1);
	

	// The number of words stored in list needs to be incremented
	// The Vector may have to be resized. But we'll add this later
	actualSize++;

	// This loop shifts the positions of the elements in 
	// list[position..actualSize] down by one slot each
	int i;
	for (i = actualSize - 1; i > position; i--)
		list[i].word = list[i-1].word;
	for (i = actualSize - 1; i > position; i--)
		list[i].frequency = list[i-1].frequency ;

	list[position].word = right;
	list[position].frequency = 1;  //1st time we found it
	return true;

}

// function that overloads the = operator. This function
// copies the fwList object on the right hand side
// of = into the fwList object on the left hand side of =
// Individual private data members are copied one at a time.
void fwList::operator = (const fwList & right)
{

	// Note that list may have to be resized to match the size of
	// the vector in the right hand side fwList object
	list.resize(right.list.length());

	actualSize = right.actualSize;
	
	int i;
	for (i = 0; i < actualSize; i++){
		list[i].word = right.list[i].word;
		list[i].frequency = right.list[i].frequency ;
	}//for
	
}

// This function overloads the [ ] operator so as to provide convenient
// access to elements in a fwList object
item fwList::operator [ ] (unsigned int index) const
{

	// Asserts that a valid word is being accessed
	assert((index >= 0) && (index < actualSize));
	return list[index];

}

// This function tells the word the number of words stored in list
unsigned int fwList::numberWords() const
{
	return actualSize;
}


// Function that overloads the insert operator so that fwList objects
// can be conveniently inserted into the output stream
ostream & operator << (ostream & out, fwList & right)
{
	int mf_count ;
	if(right.numberWords() < 500)
		mf_count = right.numberWords() ;
	else
		mf_count = 500 ;

	apvector<string> mf = right.getMostFrequent(mf_count) ;

	int i;

	for(i= 0 ; i < mf.size() ; i++)
		out << mf[i] <<  endl ;	

	for (i = 0; i < right.numberWords(); i++)
		// Note that the function that overloads the [ ] operator
		// for the fwList class is called here
		if(right[i].selected == false)
			out << right[i].word << endl;

	return out;
}

// NEW FUNCTIONS
int fwList::getFrequency(const string & myWord) const{
	int position ;
	if(search(myWord,position))
		return list[position].frequency ;
	else
		return 0 ;
}//end of getFrequency function

// k is the number of most frequent words I want
// marks them all as true, in the selected variable
apvector<string> fwList::getMostFrequent(int k){
	int i,j ;
	apvector<string> return_me ;
	return_me.resize(k) ;

	for(i = 0 ; i < actualSize ; i++)
		list[i].selected = false ;

	for(j = 0 ; j < k ; j++){
		int max = -1 ;
		int max_index = -1 ;
		for(i = 0 ; i < actualSize ; i++){
			if(list[i].selected == false)
				if(list[i].frequency >= max){
					max = list[i].frequency ;
					max_index = i ;
				}//if
		}//for
		return_me.push_back(list[max_index].word) ;
		list[max_index].selected = true ;		
	}//for


	return return_me; 
}//end of getMostFrequent