import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class SortTester<E extends Comparable<E>> {
  public static final String DICTIONARY_FILE = "dictionary.txt";
  public static final int MIN_ARRAY_SIZE =  50000;
  public static final int MAX_ARRAY_SIZE = 100000;
  public static final int MAX_ELEMENT_SIZE = 1000;
  public static final int SORTED_STEP_SIZE = 10;

  /**
   * Entry point.
   */
  public static void main(String[] args) {
    System.out.println("Checking merge algorithm:");
    MergeSorter<Integer> sorter = new MergeSorter<Integer>();
    if (!checkMerge()) {
      System.out.println("Failure.");
    } else {
      System.out.println("Success!");
    }
    System.out.println();

    if (sortIntegers()) {
      System.out.println("Integer array sort successful.");
    } else {
      System.out.println("Integer array sort unsuccessful.");
    }
    System.out.println();
    System.out.println("Simple string sort:");

    List<String> starray = new ArrayList<String>();
    starray.add("the");
    starray.add("quick");
    starray.add("brown");
    starray.add("fox");
    starray.add("jumps");
    starray.add("over");
    starray.add("the");
    starray.add("lazy");
    starray.add("dog");

    MergeSorter<String> stringsorter = new MergeSorter<String>();
    stringsorter.printCollection(starray);
    starray = stringsorter.sort(starray);
    stringsorter.printCollection(starray);
    System.out.println();

    if (sortStrings()) {
      System.out.println("String array sort successful.");
    } else {
      System.out.println("String array sort unsuccessful.");
    }

  }

  /**
   * Test against a randomly generated array of integers.
   */
  private static boolean sortIntegers() {
    Random rand = new Random();
    int arraySize = MIN_ARRAY_SIZE + rand.nextInt(MAX_ARRAY_SIZE - MIN_ARRAY_SIZE);
    List<Integer> array = new ArrayList<Integer>();
    for (int i = 0; i < arraySize; i++) {
      array.add(rand.nextInt(MAX_ELEMENT_SIZE));
    }

    SortTester<Integer> intTester = new SortTester<Integer>();

    System.out.println("Initial (int) array of size " + array.size()
                       + " is sorted: " + intTester.checkSorted(array));


    long startTime;
    long endTime;
    MergeSorter<Integer> intsorter = new MergeSorter<Integer>();
    startTime = System.nanoTime();
    array = intsorter.sort(array);
    endTime = System.nanoTime();
    long mergeSortTime = endTime - startTime;

    double millis = mergeSortTime / 1000000.;

    System.out.println("Mergesort: " + millis + " ms");
    if (millis > 500) {
      System.out.println("Sort too slow, you sure it's mergesort?");
      return false;
    }

    return intTester.checkSorted(array);
  }

  private static ArrayList<String> readDictionary() {
    Scanner fileScan = null;
    try {
      fileScan = new Scanner(new File(DICTIONARY_FILE));
    } catch (FileNotFoundException e) {
      System.out.println("Can't find dictionary file.");
      System.out.println("Modify the variable 'DICTIONARY_FILE' in SortTester.java");
      System.out.println("to point to the correct file (dictionary.txt)");
      System.exit(1);
    }
    ArrayList<String> dictionary = new ArrayList<String>(130000);
    while (fileScan.hasNext()) {
      dictionary.add(fileScan.next());
    }
    return dictionary;
  }

  private static boolean sortStrings() {
    ArrayList<String> dictionary = readDictionary();
    Random rand = new Random();
    int arraySize = MIN_ARRAY_SIZE + rand.nextInt(MAX_ARRAY_SIZE - MIN_ARRAY_SIZE);
    List<String> array = new ArrayList<String>();
    for (int i = 0; i < arraySize; i++) {
      array.add(dictionary.get(rand.nextInt(dictionary.size())));
    }
    SortTester<String> stringTester = new SortTester<String>();
    System.out.println("Initial (String) array of size " + array.size()
                       + " is sorted: " + stringTester.checkSorted(array));

    long startTime;
    long endTime;
    MergeSorter<String> stringsorter = new MergeSorter<String>();
    startTime = System.nanoTime();
    array = stringsorter.sort(array);
    endTime = System.nanoTime();
    long mergeSortTime = endTime - startTime;

    double millis = mergeSortTime / 1000000.;

    System.out.println("Mergesort: " + millis + " ms");
    if (millis > 500) {
      System.out.println("Sort too slow, you sure it's mergesort?");
      return false;
    }

    return stringTester.checkSorted(array);
  }

  /**
   * Checks if an ArrayList is sorted in ascending order.
   * @param array The array to verify.
   * @return True if the array is sorted, false otherwise
   */
  public boolean checkSorted(List<E> array) {
    for (int i = 1; i < array.size(); i ++) {
      if (array.get(i).compareTo(array.get(i - 1)) < 0) {
        return false;
      }
    }
    return true;
  }

  public static boolean checkMerge() {
    // Generate two arbitrary arrays
    Random rand = new Random();
    int arr1Size = MIN_ARRAY_SIZE + rand.nextInt(MAX_ARRAY_SIZE - MIN_ARRAY_SIZE);
    int arr2Size = MIN_ARRAY_SIZE + rand.nextInt(MAX_ARRAY_SIZE - MIN_ARRAY_SIZE);
    ArrayList<Integer> arr1 = generateSortedArray(arr1Size);
    ArrayList<Integer> arr2 = generateSortedArray(arr1Size);
    MergeSorter<Integer> intMerger = new MergeSorter<Integer>();
    List<Integer> merged = intMerger.merge(arr1, arr2);
    SortTester<Integer> intTester = new SortTester<Integer>();
    return intTester.checkSorted(merged);
  }

  public static ArrayList<Integer> generateSortedArray(int size) {
    ArrayList<Integer> arr = new ArrayList<Integer>();
    Random rand = new Random();
    Integer prevElement = 0;
    for (int i = 0; i < size; i++) {
      Integer newElement = prevElement + rand.nextInt(SORTED_STEP_SIZE);
      arr.add(newElement);
      prevElement = newElement;
    }
    return arr;
  }
}