package algs51; // section 5.1
import stdlib.*;
/* *********************************************************************************
 *  Compilation: javac Quick3string.java
 *  Execution:   java Quick3string < input.txt
 *
 *  Reads string from standard input and 3-way string quicksort them.
 *
 *  WARNING: This program assumes that the {@code substring()} method takes
 *  constant time and space. Beginning with Oracle / OpenJDK Java 7, Update 6,
 *  the substring method takes linear time and space in the size of the
 *  extracted substring. Do NOT use this code with such versions.
 *
 *  To fix: replace less() with a version that uses charAt().
 *
 *  PATCH HAS BEEN APPLIED HERE: See less() versus less1() below.
 *
 *  % java Quick3string < shell.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.Quick3string
 *       256000 [0.282 0.876]
 *       512000 [0.384 1.362]
 *      1024000 [0.839 2.185]
 *     $ ./runjava algs51.Quick3string
 *       256000 [0.291 1.003]
 *       512000 [0.380 1.306]
 *      1024000 [0.880 2.316]
 *     $ ./runjava algs51.Quick3string
 *       256000 [0.243 0.721]
 *       512000 [0.396 1.630]
 *      1024000 [0.846 2.136]
 *
 * RESULTS with Quick3string (with less implemented using charAt)
 *
 *     $ ./runjava  algs51.Quick3string
 *       256000 [0.108 1.714]
 *       512000 [0.248 2.296]
 *      1024000 [0.567 2.286]
 *     $ ./runjava  algs51.Quick3string
 *       256000 [0.104 1.576]
 *       512000 [0.250 2.404]
 *      1024000 [0.605 2.420]
 *     $ ./runjava  algs51.Quick3string
 *       256000 [0.110 1.746]
 *       512000 [0.261 2.373]
 *      1024000 [0.589 2.257]
 *
 * RESULTS with Quick3string (with less implemented using substring)
 *
 *     $ ./runjava  algs51.Quick3string
 *       256000 [0.251 0.815]
 *       512000 [0.422 1.681]
 *      1024000 [0.893 2.116]
 *     $ ./runjava  algs51.Quick3string
 *       256000 [0.235 0.739]
 *       512000 [0.404 1.719]
 *      1024000 [0.883 2.186]
 *     $ ./runjava  algs51.Quick3string
 *       256000 [0.265 0.828]
 *       512000 [0.413 1.558]
 *      1024000 [0.886 2.145]
 *
 * RESULTS WITH Arrays.sort (Mergesort)
 *
 *     $ ./runjava algs51.Quick3string
 *     dickens: [6.855]
 *     $ ./runjava algs51.Quick3string
 *     dickens: [3.650]
 *     $ ./runjava algs51.Quick3string
 *     dickens: [4.384]
 *
 * RESULTS with Quick3string (with less implemented using charAt)
 *
 *     $ ./runjava algs51.Quick3string
 *     dickens: [2.103]
 *     $ ./runjava algs51.Quick3string
 *     dickens: [2.309]
 *     $ ./runjava algs51.Quick3string
 *     dickens: [2.136]
 *
 * RESULTS with Quick3string (with less implemented using substring)
 *
 *     $ ./runjava algs51.Quick3string
 *     dickens: [6.783]
 *     $ ./runjava algs51.Quick3string
 *     dickens: [7.296]
 *     $ ./runjava algs51.Quick3string
 *     dickens: [6.995]
 *
 ***********************************************************************************/

public class Quick3string {
	private static final int CUTOFF =  15;   // cutoff to insertion sort

	// sort the array a[] of strings
	public static void sort(String[] a) {
		// StdRandom.shuffle(a);
		sort(a, 0, a.length-1, 0);
		assert isSorted(a);
	}

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


	// 3-way string quicksort a[lo..hi] starting at dth character
	private static void sort(String[] a, int lo, int hi, int d) {

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

		int lt = lo, gt = hi;
		int v = charAt(a[lo], d);
		int i = lo + 1;
		while (i <= gt) {
			int t = charAt(a[i], d);
			if      (t < v) exch(a, lt++, i++);
			else if (t > v) exch(a, i, gt--);
			else              i++;
		}

		// a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
		sort(a, lo, lt-1, d);
		if (v >= 0) sort(a, lt, gt, d+1);
		sort(a, gt+1, hi, d);
	}

	// sort from a[lo] to a[hi], starting at the dth character
	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;
	}


	// is the array sorted
	private static boolean isSorted(String[] a) {
		for (int i = 1; i < a.length; i++)
			if (a[i].compareTo(a[i-1]) < 0) return false;
		return true;
	}


	/* *********************************************************************************
	 *  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] = 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);
		//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 main1(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) {
		// read in the strings from standard input
		String[] a = StdIn.readAllStrings();
		int N = a.length;

		// sort the strings
		sort(a);

		// print the results
		for (int i = 0; i < N; i++)
			StdOut.println(a[i]);
	}
}