/*
 * Titus Winters
 * UCR CS 14 - Fall 2003 
 * Sample solution - Anagrams
 *
 * This program reads in a single word from standard input, and
 * prints out all of the words in /usr/share/dict/words that are
 * anagrams of that word, including the word itself if the word
 * is in the dictionary.
 */

#include <iostream>
#include <fstream>

using namespace std;

bool hasChar(string word, char c);
void replaceChar(string& word, char c);
bool isAnagram(string a, string b);

int main()
{
  string original;
  string dictWord;

  // Open the dictionary as a file stream
  ifstream dict("/usr/share/dict/words");
  if (!dict.is_open()) 
    {
      cout << "Unable to open /usr/share/dict/words, aborting." << endl;
      return 1;
    }

  // Read the original word
  cin >> original;

  // Loop through the dictionary, print out all anagrams.
  // Note that by not loading in the dictionary, we do everything in 
  // single pass, and don't have to waste memory storing words that we
  // are only going to look at once.
  while (dict >> dictWord)
    {
      // Check if the sizes are the same.  This way we have to make
      // fewer calls to isAnagram.
      if ((dictWord.size() == original.size()) && 
	  (isAnagram(dictWord, original)))
	{
	  // We found a winner.  Print it out.  Since we are reading
	  // a dictionary and going through it linearly, we know
	  // that they are already in dictionary order.  (That's just
	  // because of the file structure of /usr/share/dict/words,
	  // it has nothing to do with the ifstream class.)
	  cout << dictWord << endl;
	}
    }
}

// A simple function to tell if a given character appears in a word.
// string.find would also work nicely.
bool hasChar(string word, char c)
{
  for (unsigned int i = 0; i < word.size(); ++i)
    {
      if (word[i] == c) return true;
    }
  return false;
}

// A function to replace the _first_ instance of character c in the word w
// with ' '.  This is so words with duplicated letters don't incorrectly
// match.
void replaceChar(string& word, char c)
{
  for (unsigned int i = 0; i < word.size(); ++i)
    {
      if (word[i] == c)
	{
	  word[i] = ' ';
	  return;
	}
    }
}


bool isAnagram(string a, string b)
{
  // Loop through the letters in b
  for (unsigned int i = 0; i < b.size(); ++i)
    {
      // Match the current character
      if (hasChar(a, b[i]))
	{
	  // Remove the character that matched so that we don't use it
	  // repeatedly by mistake
	  replaceChar(a, b[i]);
	} else {
	  // We didn't find a matching character, so these aren't anagrams
	  return false;
	}
    }
  
  // If we found each letter in b to also be in a, then we win
  return true;
}