import java.util.SortedSet;
import java.util.TreeSet;

/**
 * A utility class containing methods related to word games.
 * 
 * @author EECS1030_W15
 * 
 */
public class WordGamesUtil {

  /**
   * A dictionary of lower case English words. The dictionary cannot be
   * modified. 
   */
  public static final Dictionary DICTIONARY = Dictionary.INSTANCE;

  /**
   * Private constructor to prevent instantiation.
   */
  private WordGamesUtil() {
    throw new UnsupportedOperationException();
  }
  
  /**
   * Returns the Hamming distance between two strings. The Hamming
   * distance is the number of indices where the characters in
   * two strings are different.
   * 
   * @param s a string
   * @param t a string
   * @return the Hamming distance between s and t
   * @throws IllegalArgumentException if s.length() != t.length()
   */
  public static int distance(String s, String t) {
    if (s.length() != t.length()) {
      throw new IllegalArgumentException("strings have different lengths");
    }
    int n = 0;
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) != t.charAt(i)) {
        n++;
      }
    }
    return n;
  }
  
  /**
   * Determines if two strings are adjacent words. The string s is
   * adjacent to t if and only if all of the following conditions
   * are true:
   * 
   * <ul>
   * <li>the string s is in WordGamesUtility.DICTIONARY
   * <li>the string t is in WordGamesUtility.DICTIONARY
   * <li>the string s is the same length as t
   * <li>s and t are identical except in exactly one position
   * </ul>
   * 
   * @param s
   *          a string
   * @param t
   *          a string
   * @return true if s and t are adjacent, false otherwise
   */
  public static boolean areAdjacent(String s, String t) {
    // is s in the dictionary?
    if (!WordGamesUtil.DICTIONARY.contains(s)) {
      return false;
    }

    // is t in the dictionary?
    if (!WordGamesUtil.DICTIONARY.contains(t)) {
      return false;
    }

    // do s and t have the same length?
    if (s.length() != t.length()) {
      return false;
    }

    return WordGamesUtil.distance(s, t) == 1;
  }

  /**
   * Returns a sorted set of all words in
   * WordGamesUtility.DICTIONARY that are adjacent to the string
   * s. The sorting of the elements of the set is lexicographical
   * (dictionary order).
   * 
   * @param s
   *          a string
   * @return a sorted set of words in WordGamesUtility.DICTIONARY
   *         that are adjacent to s
   */
  public static SortedSet<String> allAdjacentTo(String s) {
    SortedSet<String> result = new TreeSet<String>();
    for (String word : DICTIONARY) {
      if (WordGamesUtil.areAdjacent(word, s)) {
        result.add(word);
      }
    }
    return result;
  }
  
  /**
   * Returns a sorted set of all words in
   * WordGamesUtility.DICTIONARY that are adjacent to the string
   * s and differ from s exactly at the given index.
   * The sorting of the elements of the set is lexicographical
   * (dictionary order).
   * 
   * <p>For example, suppose that we want to find all words
   * that can be formed by changing the 't' in "cat".
   * alldjacentTo("cat", 2) returns the set containing the
   * strings "cab", "cad", "cam", "can", "cap", "car", "caw", "cay".
   * 
   * @param s
   *          a string
   * @param index the index where the adjacent words differ from s
   * @pre. index >= 0 && index < s.length()
   * @return a sorted set of words in WordGamesUtility.DICTIONARY
   *         that are adjacent to s and differ from s exactly
   *         at the given index
   */
  public static SortedSet<String> allAdjacentTo(String s, int index) {
    SortedSet<String> result = new TreeSet<String>();
    StringBuilder b = new StringBuilder(s);
    for (char c = 'a'; c <= 'z'; c++) {
      b.setCharAt(index, c);
      String t = b.toString();
      if (WordGamesUtil.areAdjacent(s, t)) {
        result.add(t);
      }
    }
    return result;
  }
}