import StringSorter;
import SimpleOutput;
import QuicksortStrings;
import MergeSortStrings;
import java.util.Random;

/**
 * Test a sorting routine.  Fun fun fun.  Created as part of the
 * answer key for assignment 7 of Grinnell College's CSC152 99S.
 * This can either be used as a helper class, in which case you
 * need to create a StringSorter and pass it to the constructor, 
 * or as the main class, in which case you need to specify the 
 * sorting method on the command line (quick or merge).
 *
 * The technique we use for sorting is to start with a sorted
 * list, mix the list up, sort it, and see if we got the same
 * list.  We do it again and again and again, for lists of
 * varying sizes.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of March 1999
 */
public class SortTester {

  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** The sorting method we use. */
  protected StringSorter sorter;

  /** The maximum size of list to try to sort. */
  protected int listSize;

  /** The number of times we try to sort each list. */
  protected int repetitions;

  /** A string of many A's.  Used to generate sample strings. */
  protected String As;

  /** Are we testing our tester? */
  protected boolean TESTING = false;

  /** A random number generator. */
  protected Random generator;


  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Build a tester that uses a default maximum size and
   * number of repetitions.
   */
  public SortTester(StringSorter sorter) {
    this(sorter, 20, 10);
  } // SortTester(StringSorter)

  /**
   * Build a tester that uses a specified sorting routine,
   * maximum list size, and number of repetitions.
   */
  public SortTester(StringSorter sorter, int size, int reps) {
    this.sorter = sorter;
    this.listSize = size;
    this.repetitions = reps;
    this.As = "AAAAA";
    this.generator = new Random();
  } // SortTester(StringSorter, int, int)


  // +----------------+------------------------------------------
  // | Public Methods |
  // +----------------+

  /**
   * Run the tests, reporting the results.
   */
  public void runTests(SimpleOutput out) {
    String[] sorted;	// A sorted array
    String[] mixedup;	// A "mixed up" version
    String[] resorted;	// That array, resorted

    // For each list size
    for (int size = 1; size <= listSize; ++size) {
      // Build a sorted list of the appropriate size
      sorted = makeSortedList(size);
      // Print some information
      out.println();
      out.println("Checking list of size " + size);
      // Print it out when testing
      if (TESTING) printArray(out, sorted);
      // Make a copy
      mixedup = copyArray(sorted);
      // Run the tests
      for (int test = 0; test < repetitions; ++test) {
        // Some feedback so that you can tell it's running
        out.print(".");
        // Build a permutation.
        mixup(mixedup);
        // Sort the permutation
        resorted = sorter.sort(mixedup);
        // Print out an example when testing
        if ((TESTING) && (test == 0)) {
          out.println();
          out.println("Mixed up");
          printArray(out, mixedup);
          out.println();
          out.println("Resorted");
          printArray(out, resorted);
        }
        // See if it's correctly sorted.
        if (different(sorted,resorted)) {
          out.println("Problem sorting!");
          out.println("=== ORIGINAL ARRAY ===");
          printArray(out, mixedup);
          out.println("=== 'SORTED' ARRAY ===");
          printArray(out, resorted);
        } // if it's not correctly sorted
      } // for each test
      out.println();
    } // for each list size
  } // runTests(SimpleOutput)


  // +----------------+------------------------------------------
  // | Helper Methods |
  // +----------------+

  /**
   * Copy an array of strings.
   */
  protected String[] copyArray(String[] strings) {
    String[] copy = new String[strings.length];
    for (int i = 0;i < strings.length; ++i) {
      copy[i] = strings[i];
    }
    return copy;
  } // copyArray(String[])

  /**
   * See if two arrays of strings are different.
   */
  protected boolean different(String[] alpha, String[] beta) {
    if (alpha.length != beta.length) return true;
    for (int i = 0; i < alpha.length; ++i) {
      if (!alpha[i].equals(beta[i])) return true;
    }
    // If we've made it this far, they must be the same.
    return false;
  } // different(String[], String[])

  /**
   * Make a sorted list of an appropriate size.
   */
  protected String[] makeSortedList(int size) {
    String[] sorted = new String[size];
    for (int i = 0; i < size; ++i) {
      sorted[i] = nAs(i+1);
    }
    return sorted;
  } // makeSortedList(int)

  /**
   * Mix up the elements of an array.
   */
  protected void mixup(String[] strings) {
    // Randomly swap some number of times.
    for (int i = 0; i < strings.length; ++i) {
      swap(strings, 
           Math.abs(generator.nextInt() % strings.length),
           Math.abs(generator.nextInt() % strings.length));
    } // for
  } // mixup(String[])

  /**
   * Create a string of n "A"s.
   */
  protected String nAs(int n) {
    while (As.length() < n) {
      As = As.concat(As);
    }
    return As.substring(0,n);
  } // nAs(int)

  /**
   * Print an array of strings.
   */
  protected void printArray(SimpleOutput out, String[] strings) {
    for (int i = 0; i < strings.length; ++i) {
      out.println(strings[i]);
    }
  } // printArray(SimpleOutput, String[])

  /**
   * Swap two elements.
   */
  protected void swap(String[] strings, int x, int y) {
    String tmp = strings[x];
    strings[x] = strings[y];
    strings[y] = tmp;
  } // swap(String[], int, int)


  // +------+----------------------------------------------------
  // | Main |
  // +------+

  public static void main(String[] args) {
    SimpleOutput out = new SimpleOutput();
    SortTester tester = new SortTester(new MergeSortStrings());
    if (args.length < 1) {
      out.println("You must specificy quick or merge");
      return;
    }
    if (args[0].equals("quick")) {
      tester = new SortTester(new QuicksortStrings());
    }
    else if (args[0].equals("merge")) {
      // already set
    }
    else {
      out.println("Invalid sorting method: " + args[0]);
      out.println("You must specificy quick or merge");
      return;
    }
    tester.runTests(out);
  } // main(String[])
} // SortTester