package algs51; // section 5.1
import stdlib.*;
/* *********************************************************************************
 *  Compilation: javac MSD.java
 *  Execution:   java MSD < input.txt
 *
 *  Reads extended ASCII string from standard input and MSD radix sorts them.
 *
 *  % java MSD < shells.txt
 *  are
 *  by
 *  sea
 *  seashells
 *  seashells
 *  sells
 *  sells
 *  she
 *  she
 *  shells
 *  shore
 *  surely
 *  the
 *  the
 *
 * MAX_LENGTH = 64
 * RESULTS WITH Arrays.sort (Mergesort)
 *
 *     $ ./runjava algs51.MSD
 *       256000 [0.243 0.880]
 *       512000 [0.398 1.638]
 *      1024000 [0.851 2.138]
 *     $ ./runjava algs51.MSD
 *       256000 [0.281 1.011]
 *       512000 [0.365 1.299]
 *      1024000 [0.848 2.323]
 *     $ ./runjava algs51.MSD
 *       256000 [0.270 1.031]
 *       512000 [0.370 1.370]
 *      1024000 [0.857 2.316]
 *
 * RESULTS with MSD
 *
 *     $ ./runjava algs51.MSD
 *       256000 [0.299 3.785]
 *       512000 [0.151 0.505]
 *      1024000 [0.305 2.020]
 *     $ ./runjava algs51.MSD
 *       256000 [0.296 3.795]
 *       512000 [0.139 0.470]
 *      1024000 [0.303 2.180]
 *     $ ./runjava algs51.MSD
 *       256000 [0.294 3.769]
 *       512000 [0.141 0.480]
 *      1024000 [0.282 2.000]
 *
 * RESULTS WITH Arrays.sort (Mergesort)
 *
 *     $ ./runjava algs51.MSD
 *     dickens: [4.205]
 *     $ ./runjava algs51.MSD
 *     dickens: [4.257]
 *     $ ./runjava algs51.MSD
 *     dickens: [4.222]
 *
 * RESULTS with MSD
 *
 *     $ ./runjava algs51.MSD
 *     dickens: [7.331]
 *     $ ./runjava algs51.MSD
 *     dickens: [7.411]
 *     $ ./runjava algs51.MSD
 *     dickens: [7.523]
 *
 ***********************************************************************************/

public class MSD {
  private static final int R      = 256;   // extended ASCII alphabet size
  private static final int CUTOFF =  15;   // cutoff to insertion sort

  // sort array of strings
  public static void sort(String[] a) {
    int N = a.length;
    String[] aux = new String[N];
    sort(a, 0, N-1, 0, aux);
  }

  // return dth character of s, -1 if d = length of string
  private static int charAt(String s, int d) {
    assert d >= 0 && d <= s.length();
    if (d == s.length()) return -1;
    return s.charAt(d);
  }

  // sort from a[lo] to a[hi], starting at the dth character
  private static void sort(String[] a, int lo, int hi, int d, String[] aux) {

    // cutoff to insertion sort for small subarrays
    if (hi <= lo + CUTOFF) {
      insertion(a, lo, hi, d);
      return;
    }

    // compute frequency counts
    int[] count = new int[R+2];
    for (int i = lo; i <= hi; i++) {
      int c = charAt(a[i], d);
      count[c+2]++;
    }

    // transform counts to indicies
    for (int r = 0; r < R+1; r++)
      count[r+1] += count[r];

    // distribute
    for (int i = lo; i <= hi; i++) {
      int c = charAt(a[i], d);
      aux[count[c+1]++] = a[i];
    }

    // copy back
    for (int i = lo; i <= hi; i++)
      a[i] = aux[i - lo];


    // recursively sort for each character
    for (int r = 0; r < R; r++) {
      //sort(a, lo + count[r], lo + count[r+1] - 1, d+1, aux);

      int newLo = lo + count[r];
      int newHi = lo + count[r+1] - 1;
      if (newHi > newLo)
        sort(a, newLo, newHi, d+1, aux);
    }
  }


  // return dth character of s, -1 if d = length of string
  private static void insertion(String[] a, int lo, int hi, int d) {
    for (int i = lo; i <= hi; i++)
      for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
        exch(a, j, j-1);
  }

  // exchange a[i] and a[j]
  private static void exch(String[] a, int i, int j) {
    String temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

  // is v less than w, starting at character d
  private static boolean less1(String v, String w, int d) {
    assert v.substring(0, d).equals(w.substring(0, d));
    return v.substring(d).compareTo(w.substring(d)) < 0;
  }
  // is v less than w, starting at character d
  private static boolean less(String v, String w, int d) {
    assert v.substring(0, d).equals(w.substring(0, d));
    int len1 = v.length ();
    int len2 = w.length ();
    int n = Math.min(len1, len2);
    int k = 0;
    while (k < n) {
      char c1 = v.charAt (k);
      char c2 = w.charAt (k);
      if (c1 != c2) {
        return c1 < c2;
      }
      k++;
    }
    return len1 < len2;
  }


  /* *********************************************************************************
   *  Test code
   ***********************************************************************************/
  private static final int MAX_LENGTH = 64;
  private static final String CHARACTERS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789`~!@#$%^&*()_-+={[}]\\|:;'\"<>,./?";
  private static String randomString() {
    int length = 2 + StdRandom.uniform (MAX_LENGTH);
    char[] text = new char[length];
    int NUM_CHARACTERS = CHARACTERS.length ();
    for (int i = 0; i < length; i++) {
      text[i] = CHARACTERS.charAt(StdRandom.uniform (NUM_CHARACTERS));
    }
    return new String(text);
  }
  private static void exch(int[] a, int i, int j) {
    int swap = a[i];
    a[i] = a[j];
    a[j] = swap;
  }
  private static double time;
  private static void countops (int N) {
    String[] a = new String[N];
    //for (int i = 0; i < a.length; i++) a[i] = (N*i)/N;
    //StdRandom.shuffle (a);
    for (int i = 0; i < a.length; i++) a[i] = randomString ();
    //Arrays.sort (a);
    //Arrays.sort (a); for (int i = 0; i < (N-1)/2; i++) exch(a, i, N-i-1);

    Stopwatch sw = new Stopwatch ();
    sort (a);
    //Quick3way.sort (a);
    //Arrays.sort (a);
    time = sw.elapsedTime ();
  }
  public static void main(String[] args) {
    int N = 128000;
    countops (N);
    //System.exit (0);
    double prevTime = time;
    for (int i=0; i<3; i++) {
      N *= 2;
      countops (N);
      StdOut.format("%8d [%5.3f %5.3f]\n", N, time, time/prevTime);
      prevTime = time;
    }
  }
  public static void main3(String[] args) {
    String[] a = new In("data/dickens.txt").readAllStrings ();
    Stopwatch sw = new Stopwatch ();
    sort (a);
    //Arrays.sort (a);
    StdOut.format("dickens: [%5.3f]\n", sw.elapsedTime ());
  }
  public static void main2(String[] args) {
    String[] a = StdIn.readAllStrings();
    int N = a.length;
    sort(a);
    for (int i = 0; i < N; i++)
      StdOut.println(a[i]);
  }
}