#include <iostream>
#include <string>
#include <fstream>
using namespace std;

#include "tvector.h"
#include "permuter.h"
#include "prompt.h"
#include "strutils.h"
#include "ctimer.h"

/**
 * illustrate jumble/anagram finding in an inefficient manner
 * user provides a sorted file of words, then a sequence of
 * 'jumbled' words to look up.  Example:
 *
 * look up 'ueprg', find it's an anagram/jumble of 'purge'
 *
 * The method used is forming all permutations of the word and
 * looking up each one.  Each look up uses binary search, so lookups
 * are fast, but there are lots of permutations
 */

class Dictionary
{
  public:
    Dictionary(const string& filename);     // sorted file of words
    
    bool contains(const string& s)  const;  // return true if s in dictionary

  private:
    tvector<string> myWords;                // list of words
};

Dictionary::Dictionary(const string& filename)
// pre: filename corresponds to a readable and sorted file of words
// post: words in filename read and stored    
{
    ifstream input(filename.c_str());
    string word;
    while (input >> word)
    {
	myWords.push_back(LowerString(word));
    }
}

bool Dictionary::contains(const string & s) const
// pre: dictionary contains list of words in sorted order
// post: returns true if s contained in dictionary, false otherwise
// runtime: O(log n) where n is number of words in dictionary    
{
    int low = 0;
    int high = myWords.size()-1;
    int mid;

    // use binary search, s in [low..high] 
    
    while (low <= high)
    {
	mid = (low+high)/2;
	if (myWords[mid] == s)
	{
	    return true;   
	}
	else if (s < myWords[mid])
	{
	    high = mid-1;
	}
	else  // s in upper half
	{
	    low = mid+1;
	}
    }
    return false;
}

void FindAnagram(const string& word, const Dictionary& wordSource)
// post: finds and prints first anagram of word as found
//       in wordSource. reports runtime statistics    
{
    tvector<int> list(word.length());
    int k;
    for(k=0; k < list.size(); k++)
    {
	list[k] = k;
    }
    Permuter p(list);
    CTimer timer;
    int count = 0;
    
    string copy(word);   // makes copy the right length

    // generate each permutation of letters in 'word'
    // store permutations in copy and look them up
    
    timer.Start();
    for(p.Init(); p.HasMore(); p.Next())
    {
	p.Current(list);
	for(k=0; k < list.size(); k++)
	{
	    copy[k] = word[list[k]];
	}
//	cout << "checking: " << copy << endl;
	count++;
	if (wordSource.contains(copy))
	{
	    cout << "anagram of " << copy << endl;
	    break;  // find first anagram only
	}
    }
    timer.Stop();
    cout << "tested " << count << " words in "
	 << timer.ElapsedTime() << " secs." << endl;
    cout << timer.ElapsedTime()/count << " secs/word" << endl;
}

int main(int argc, char * argv[])
{
    string filename;
    if (argc > 1)
    {
	filename = argv[1];
    }
    else
    {
	filename = PromptlnString("enter filename: ");
    }
    Dictionary wordSource(filename);
    string word;

    while(true)
    {
	word = PromptlnString("word (return to stop) ");
	if (word == "") break; // out of loop

	FindAnagram(word,wordSource);
    }
    return 0;
}