import java.io.*;
import java.util.*;

public class EncodedWord extends Word
{
   private static final int MAX = 100;
   private String code;

   EncodedWord(String s, int n)
   {
      super(s, n);
      code = encodeWord(s);
   }

   EncodedWord(String codeOnly)
   {
      super("", 0);
      code = codeOnly;
   }

   public String getWord() { return super.word; }
   public int getFreq() { return super.freq; }
   public String getCode() { return code; }

   public String toString()
   { return super.word + " " + code + " " + super.freq; }

   public static String encodeWord(String s1)
   {
      String s2 = "";
      for (int i = 0; i < s1.length(); ++i)
      {
         char c = Character.toLowerCase(s1.charAt(i));
         s2 = s2 + encodeLetter(c);
      }
      return s2;
   }

   public static char encodeLetter(char c)
   {
      if (c == 'a' || c == 'b' || c == 'c') return '2';
      if (c == 'd' || c == 'e' || c == 'f') return '3';
      if (c == 'g' || c == 'h' || c == 'i') return '4';
      if (c == 'j' || c == 'k' || c == 'l') return '5';
      if (c == 'm' || c == 'n' || c == 'o') return '6';
      if (c == 'p' || c == 'q' || c == 'r' || c == 's') return '7';
      if (c == 't' || c == 'u' || c == 'v') return '8';
      if (c == 'w' || c == 'x' || c == 'y' || c == 'z') return '9';
      if (c == ' ') return ' ';
      return '#';          
   }

   public static EncodedWord[] loadDictionary(String fileName) throws IOException
   {
      // ensure dictionary file exists
      File f = new File(fileName);
      if (!f.exists())
      {
         System.out.println("File not found - " + fileName);
         System.exit(1);
      }

      // open dictionary file for input
      BufferedReader inputFile =
         new BufferedReader(new FileReader(fileName));

      // read lines from dictionary ('word' and 'frequency' on each)
      String line;
      Vector v = new Vector();
      while ((line = inputFile.readLine()) != null)
      {
         StringTokenizer st = new StringTokenizer(line);

         // exactly two entries per line required
         if (st.countTokens() != 2)
         {
            System.out.println("Dictionary format error");
            System.exit(1);
         }

         // get the word
         String newWord = st.nextToken();

         // get the frequency
         int newFreq = Integer.parseInt(st.nextToken());

         // add to vector as a EncodedWord object
         v.addElement(new EncodedWord(newWord, newFreq));
      }

      // close disk file
      inputFile.close(); 

      // declare an EncodedWord array of just the size needed
      EncodedWord[] dict = new EncodedWord[v.size()];

      // copy elements from vector into array
      v.copyInto(dict);

      // sort the dictionary by code
      Arrays.sort(dict, new ByCode());
      return dict;
   }

   // returns an array of words matching the code (sorted by frequency)
   // returns a null reference if no matches
   public static String[] getUnique(String code, EncodedWord[] dict)
   {
      String[] words = null;

      // no matches if no code!
      if (code == "")
         return words;

      // find lower bracketing index (n1)
      int n1 = Arrays.binarySearch(dict, new EncodedWord(code), new ByCode());

      // no matches if return value < 0
      if (n1 < 0)
         return words;  // no matches

      // because codes are not unique, backup index if necessary
      while (n1 > 0 && dict[n1].getCode().compareTo(dict[n1 - 1].getCode()) == 0)
         --n1;

      // s2 is 1st entry 'after' entries matching code 
      String s2 = code + "0";

      // find upper bracketing index (n2)
      int n2 = Arrays.binarySearch(dict, new EncodedWord(s2), new ByCode());

      // is no match for s2, that's OK; need a +ve index anyway
      if (n2 < 0)
         n2 = -n2 - 1;

      // make a new Word array for all choices (and there are some!)
      EncodedWord[] ew = new EncodedWord[n2 - n1];
      int i, j;
      for (i = n1, j = 0; i < n2; i++, j++)
         ew[j] = dict[i];

      // sort the new array by frequency
      Arrays.sort(ew, new ByFreq());
 
      // make a String array for just the words
      words = new String[ew.length];  
      for (i = 0; i < words.length; ++i)
         words[i] = ew[i].getWord();
      return words;
   }

   // returns an array containing words tentatively matching code
   // returns a null reference if no matches
   public static String[] getTentative(String code, EncodedWord[] dict)
   {
      String[] words = null;

      // no matches if no code!
      if (code == "")
         return words;

      // find position in array of code entered and s2
      int n1 = Arrays.binarySearch(dict, new EncodedWord(code), new ByCode());


      // no matches (insertion point at beginning, it is not a word)
      if (n1 == -1)
         return words;

      // no matches (insertion points in middle, it is a word)
      if (n1 < 0)
         n1 = -n1 - 1;

      // no matches (insertion point at end, it is not a word)
      if (n1 >= dict.length)
         return words;

      // find lower bracketing index
      while (n1 > 0)
      {
         String s = dict[n1 - 1].getCode();

         if (s.length() < code.length())
            break;
         s = s.substring(0, code.length());
         if (s.compareTo(code) == 0)
            --n1;
         else
            break;         
      }

      // find upper bracketing index
      int n2 = n1;
      while (n2 < dict.length)
      {
         String s = dict[n2].getCode();

         if (s.length() < code.length())
            break;

         s = s.substring(0, code.length());
         if (s.compareTo(code) == 0)
            ++n2;
         else
            break;
      }

      // it is not a word, and there are no tentative matches
      if (n1 == n2)
         return words;

      // make an EncodedWord array containing all tentative matches
      EncodedWord[] ew = null;
      ew = new EncodedWord[n2 - n1];
      int i, j;
      for (i = n1, j = 0; i < n2; i++, j++)
         ew[j] = dict[i];

      // sort the array by frequency
      Arrays.sort(ew, new ByFreq());

      // might be absurdly big, limit size to MAX
      int n = ew.length > MAX ? MAX : ew.length;

      // copy only the words into a string array
      words = new String[n];
      for (i = 0; i < n; ++i)
         words[i] = ew[i].getWord();

      // success!
      return words;
   }

   /** Returns a string array containing a query.
   * Returns a null if reference is no entries in query.
   * A query consists of an array of words beginning
   * with those returned by getUnique(), followed by those
   * returned by getTentative().  Duplicates are
   * removed.
   **/
   public static String[] getQuery(String code, EncodedWord[] dict)
   {
      String[] query = null;

      // no query if no code!
      if (code == "")
         return query;

      String[] unique = getUnique(code, dict);
      String[] tentative = getTentative(code, dict);

      // coming up empty
      if (unique == null && tentative == null)
         return query;

      // only tenative matches, return them
      if (unique == null && tentative != null)
         return tentative;

      // only uniques matches, return them
      if (unique != null && tentative == null)
         return unique;

      // OK, we've got a combination of unique and tentative matches

      // first, put the unique matches into a vector
      Vector v = new Vector();
      for (int i = 0; i < unique.length; ++i)
         v.addElement(unique[i]);

      // then add the tenative matches to the end, omitting duplicates
      for (int i = 0; i < tentative.length; ++i)
         if (!v.contains(tentative[i]))
            v.addElement(tentative[i]);

      // make a query array of just the size needed
      query = new String[v.size()];

      // copy the results into the query array
      v.copyInto(query);

      // success!
      return query;
   }

   public static void printEncodedWord(EncodedWord[] ew)
   {
      for (int i = 0; i < ew.length; ++i)
         System.out.println(ew[i]);
   }

   public static void printStringArray(String[] s)
   {
      if (s == null)
         System.out.println("sorry!");
      else
      {
         for (int i = 0; i < s.length; ++i)
            System.out.print(s[i] + " ");
         System.out.println();
      }
   }

   public static void main(String[] args) throws IOException
   {
      // one command line argument needed
      if (args.length == 0 || args.length > 2)
      {
         System.out.println("usage: java EncodedWord dictionary");
         return;
      }

      EncodedWord[] ew;
      System.out.print("Load and sort dictionary...");
      ew = EncodedWord.loadDictionary(args[0]);
      System.out.println("(done)");
      System.out.println("Dictionary contains " + ew.length + " words");

      BufferedReader stdin =
         new BufferedReader(new InputStreamReader(System.in), 1);

      System.out.println("*** Test the get methods ***");
      System.out.println("Enter codes... (^z to exit)");
      // process lines until no more input
      String code;
      while ((code = stdin.readLine()) != null)
      {
         String[] s;

         s = getUnique(code, ew);
         System.out.println("\nResults of getUnique()...");
         //System.out.println("unique = " + s);
         printStringArray(s);

         s = getTentative(code, ew);
         System.out.println("\nResults of getTentative()...");
         //System.out.println("tentative = " + s);
         printStringArray(s);

         s = getQuery(code, ew);
         System.out.println("\nResults of getQuery()...");
         //System.out.println("query = " + s);
         printStringArray(s);
      }
   }
}

class ByCode implements Comparator
{
   public int compare(Object o1, Object o2)
   {
      String s1 = ((EncodedWord)o1).getCode();
      String s2 = ((EncodedWord)o2).getCode();
      return s1.compareTo(s2);
   }
}