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

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



// default constructor
wordList::wordList () : 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 wordList object needs to have	
wordList::wordList (unsigned int numberOfElements) : 
			actualSize(0),
			list(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
wordList::wordList (const wordList & right) : 
			actualSize(right.actualSize),
			list(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] = right.list[i];
}


// 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 wordList::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])
		{
			position = mid;
			return true;
		}

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

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

	position = first;
	return false;
}

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

	// 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] = list[i-1];

	list[position] = right;
	return true;

}

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

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

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

// This function overloads the [ ] operator so as to provide convenient
// access to elements in a wordList object
string wordList::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 wordList::numberWords() const
{
	return actualSize;
}


// Function that overloads the insert operator so that wordList objects
// can be conveniently inserted into the output stream
ostream & operator << (ostream & out, const wordList & right)
{
	
	int i;
	int times = right.numberWords();
	for (i = 0; i < times; i++)
		// Note that the function that overloads the [ ] operator
		// for the wordList class is called here
		out << right[i] << endl;

	return out;
}