package algs51; // section 5.1
import stdlib.*;
/* *********************************************************************************
 *  Compilation: javac LSD.java
 *  Execution:   java LSD < input.txt
 *
 *  LSD radix sort an array of extended ASCII strings, each of length W.
 *
 *  % java LSD < words3.txt
 *  all
 *  bad
 *  bed
 *  bug
 *  dad
 *  ...
 *  yes
 *  yet
 *  zoo
 *
 * LENGTH = 8
 * RESULTS WITH Arrays.sort (Mergesort)
 *
 *     $ ./runjava algs51.LSD
 *       256000 [0.239 0.879]
 *       512000 [0.303 1.268]
 *      1024000 [0.750 2.475]
 *     $ ./runjava algs51.LSD
 *       256000 [0.224 0.783]
 *       512000 [0.302 1.348]
 *      1024000 [0.763 2.526]
 *     $ ./runjava algs51.LSD
 *       256000 [0.261 0.839]
 *       512000 [0.306 1.172]
 *      1024000 [0.738 2.412]
 *
 * RESULTS with LSD
 *
 *     $ ./runjava algs51.LSD
 *       256000 [0.463 1.564]
 *       512000 [0.990 2.138]
 *      1024000 [2.293 2.316]
 *     $ ./runjava algs51.LSD
 *       256000 [0.442 1.811]
 *       512000 [0.956 2.163]
 *      1024000 [2.251 2.355]
 *     $ ./runjava algs51.LSD
 *       256000 [0.440 1.753]
 *       512000 [0.958 2.177]
 *      1024000 [2.278 2.378]
 *
 * LENGTH = 4
 * RESULTS WITH Arrays.sort (Mergesort)
 *
 *     $ #ARRAYS 4
 *     $ ./runjava algs51.LSD
 *       256000 [0.259 0.893]
 *       512000 [0.345 1.332]
 *      1024000 [0.762 2.209]
 *     $ ./runjava algs51.LSD
 *       256000 [0.267 0.837]
 *       512000 [0.953 3.569]
 *      1024000 [1.625 1.705]
 *     $ ./runjava algs51.LSD
 *       256000 [0.252 1.016]
 *       512000 [0.964 3.825]
 *      1024000 [1.629 1.690]
 *
 * RESULTS with LSD
 *
 *     $ ./runjava algs51.LSD
 *       256000 [0.185 1.350]
 *       512000 [0.844 4.562]
 *      1024000 [1.862 2.206]
 *     $ ./runjava algs51.LSD
 *       256000 [0.179 1.366]
 *       512000 [0.813 4.542]
 *      1024000 [1.827 2.247]
 *     $ ./runjava algs51.LSD
 *       256000 [0.178 1.348]
 *       512000 [0.815 4.579]
 *      1024000 [1.848 2.267]
 *
 ***********************************************************************************/

public class LSD {

	// LSD radix sort
	public static void sort(String[] a, int W) {
		int N = a.length;
		int R = 256;   // extend ASCII alphabet size
		String[] aux = new String[N];

		for (int d = W-1; d >= 0; d--) {
			// sort by key-indexed counting on dth character

			// compute frequency counts
			int[] count = new int[R+1];
			for (int i = 0; i < N; i++)
				count[a[i].charAt(d) + 1]++;

			// compute cumulates
			for (int r = 0; r < R; r++)
				count[r+1] += count[r];

			// move data
			for (int i = 0; i < N; i++)
				aux[count[a[i].charAt(d)]++] = a[i];

			// copy back
			for (int i = 0; i < N; i++)
				a[i] = aux[i];
		}
	}


	/* *********************************************************************************
	 *  Test code
	 ***********************************************************************************/
	private static final int LENGTH = 4;
	private static final String CHARACTERS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789`~!@#$%^&*()_-+={[}]\\|:;'\"<>,./?";
	private static String randomString() {
		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, LENGTH);
		//Merge.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 main2(String[] args) {
		StdIn.fromFile ("data/words3.txt");
		String[] a = StdIn.readAllStrings();
		int N = a.length;

		// check that strings have fixed length
		int W = a[0].length();
		for (int i = 0; i < N; i++)
			assert a[i].length() == W : "Strings must have fixed length";

		// sort the strings
		sort(a, W);

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