#include <iostream>
#include <string>
#include <iterator>
#include <set>
#include <stdexcept>
#include <algorithm>
#include <cctype>
#include <fstream>
#include "sharedptr.h"
using namespace std;

/* A version of the CS106B/X Lexicon that's layered on top of an STL set.
 * Not nearly as efficient as the real Lexicon (which is massively
 * optimized), but pretty good nonetheless.
 */
class Lexicon {
public:
	/* Constructor loads in all of the words from a file.  The file
	 * is assumed to exist; the Lexicon is empty otherwise.
	 */
	explicit Lexicon(const string& filename);

	/* Returns whether a word is contained in the Lexicon. */
	bool containsWord(const string& word) const;

	/* Returns whether a word is a prefix in the Lexicon. */
	bool containsPrefix(const string& prefix) const;

	void addWord(const string& word) {
		ensureUnique();
		allWords->insert(word);
	}

	/* Allows you to iterate over the contents of the Lexicon. */
	typedef set<string>::const_iterator const_iterator;
	const_iterator begin() const;
	const_iterator end() const;
private:
	SharedPtr< set<string> > allWords;

	void ensureUnique() {
		if (ShareCount(allWords) != 1)
			allWords.operator =(SharedPtr< set<string> >(new set<string>(*allWords)));
	}
};

/* Helper function to convert a word to lower case. */
string ConvertToLowerCase(const string& str) {
	string result = str;
	transform(result.begin(), result.end(), result.begin(), ::tolower);
	return result;
}

/* Constructor just copies the strings out of the file using copy
 * and some istream_iterators.
 */
Lexicon::Lexicon(const string& filename) : allWords(new set<string>) {
	ifstream input(filename.c_str()); // Assume file exists... would normally do error-checking.
	allWords->insert(istream_iterator<string>(input), istream_iterator<string>());
}

/* containsWord just checks if the word is in the set. */
bool Lexicon::containsWord(const string& word) const {
	return allWords->find(ConvertToLowerCase(word)) != allWords->end();
}

/* Checking whether a prefix exists is a bit subtle.  We use
 * the lower_bound function to get an iterator to the first word that
 * compares lexicographically no less than the prefix.  If the element
 * has the given prefix, the prefix exists; otherwise it does not.
 */
bool Lexicon::containsPrefix(const string& prefix) const {
	const string lowerPrefix = ConvertToLowerCase(prefix);

	/* Get an iterator to the first element no less than the prefix. */
	set<string>::const_iterator itr = allWords->lower_bound(lowerPrefix);

	/* If we get the end iterator, this prefix comes after everything in
	 * the lexicon.
	 */
	if(itr == allWords->end()) return false;

	/* Otherwise, check how the word compares to the word we found. */
	return itr->compare(0, lowerPrefix.size(), lowerPrefix) == 0;
}

/* begin and end functions for iteration. */
Lexicon::const_iterator Lexicon::begin() const {
	return allWords->begin();
}
Lexicon::const_iterator Lexicon::end() const {
	return allWords->end();
}