//  Program:  HW 1, Word Circle
//  Author:   Chuck Stewart
//  Overview:  Solution to the word circle search problem for HW 1 in
//    Computer Science II, Spring 2008.  A dictionary of words is
//    created and then the puzzle strings are read into the program,
//    one at a time.  The program generates each of the 2*n different
//    potential words, where n is length of the puzzle string, and
//    tests it against the dictionary using binary search.  As soon as
//    a word is found, the puzzle is considered to be solved for,
//    output is generated, and the next puzzle string is tested.

#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

//  Application of binary search to look for a word in the dictionary.
//  The function simply returns true or false, depending on whether or
//  not the word is in the dictionary, represented by a vector of
//  strings.
bool
word_in_dictionary( const std::string& word,
                    const std::vector<std::string> & dictionary )
{
  int low = 0;
  int high = dictionary.size()-1;

  while ( low < high )
    {
      int mid = (low+high)/2;
      if ( word <= dictionary[mid] )
	high = mid;
      else
	low = mid+1;
    }
  return word == dictionary[low];
}


int main( int argc, char* argv[] )
{
  //  Check the number of command-line arguments
  if ( argc != 4 )
    {
      std::cerr << "Usage: " << argv[0] << " dictionary puzzle words-found\n";
      return 1;
    }

  //  Attach an input stream to the dictionary file specified in the
  //  first command-line argument.
  std::ifstream dictionary_ifs( argv[1] );
  if ( !dictionary_ifs )
    {
      std::cerr << "Can not open the dictionary file " << argv[1] << "\n";
      return 1;
    }

  //  Create the puzzle stream.
  std::ifstream puzzle_ifs( argv[2] );
  if ( !puzzle_ifs )
    {
      std::cerr << "Can not open the puzzle words stream " << argv[3] << "\n";
      return 1;
    }

  //  Create the words-found result stream.
  std::ofstream found_ofs( argv[3] );
  if ( !found_ofs )
    {
      std::cerr << "Can not open the results stream " << argv[3] << "\n";
      return 1;
    }

  //  Represent the dictionary as a vector of strings
  std::vector<std::string> dictionary;
  std::string one_word;

  //  Read the dictionary and then sort the resulting vector
  while ( dictionary_ifs >> one_word )
    {
      dictionary.push_back( one_word );
    }
  std::sort( dictionary.begin(), dictionary.end() );

  //  Read and test the input strings one at a time...
  std::string letters;
  while ( puzzle_ifs >> letters )
    {
      int n = int(letters.length());
      std::string forward(n,' '), backward(n, ' ');
      bool found = false;

      //  For each starting letter, generate the forward and backward
      //  strings that start with that letter and test each against
      //  the dictionary.
      for ( int start_i=0; start_i<n && !found; ++start_i )
        {
          //  Generate the strings
          for ( int j=0; j<n; ++j )
            {
              forward[j] = letters[ (start_i+j) % n ];
              backward[j] = letters[ (start_i+n-j) % n ]; 
            }
          
          //  Test the forward string
          if ( word_in_dictionary(forward, dictionary) )
            {
              found = true;
              found_ofs << letters << ": " << forward << '\n';
            }

          //  Test the backward string
          else if ( word_in_dictionary(backward, dictionary) )
            {
              found = true;
              found_ofs << letters << ": " << backward << '\n';
            }
        }

      //  If a word was not found, just output the letters
      if ( !found )  found_ofs << letters << ": <none>\n";
    }

  return 0;

}