package algs24;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac Heap.java
 *  Execution:    java Heap < input.txt
 *  Dependencies: StdOut.java StdIn.java
 *  Data files:   http://algs4.cs.princeton.edu/24pq/tiny.txt
 *                http://algs4.cs.princeton.edu/24pq/words3.txt
 *
 *  Sorts a sequence of strings from standard input using heapsort.
 *
 *  % more tiny.txt
 *  S O R T E X A M P L E
 *
 *  % java Heap < tiny.txt
 *  A E E L M O P R S T X                 [ one string per line ]
 *
 *  % more words3.txt
 *  bed bug dad yes zoo ... all bad yet
 *
 *  % java Heap < words3.txt
 *  all bad bed bug dad ... yes yet zoo   [ one string per line ]
 *
 *************************************************************************/

public class Heap {

	public static <T extends Comparable<? super T>> void sort(T[] pq) {
		int N = pq.length;
		for (int k = N/2; k >= 1; k--) {
			sink(pq, k, N);
		}
		while (N > 1) {
			exch(pq, 1, N);
			N--;
			sink(pq, 1, N);
		}
	}

	/* *********************************************************************
	 * Helper functions to restore the heap invariant.
	 **********************************************************************/

	private static <T extends Comparable<? super T>> void sink(T[] pq, int k, int N) {
		while (2*k <= N) {
			int j = 2*k;
			if (j < N && less(pq, j, j+1)) j++;
			if (!less(pq, k, j)) break;
			exch(pq, k, j);
			k = j;
		}
	}

	/* *********************************************************************
	 * Helper functions for comparisons and swaps.
	 * Indices are "off-by-one" to support 1-based indexing.
	 **********************************************************************/
	private static <T extends Comparable<? super T>> boolean less(T[] pq, int i, int j) {
		if (COUNT_OPS) DoublingTest.incOps ();
		return pq[i-1].compareTo(pq[j-1]) < 0;
	}

	private static <T> void exch(T[] pq, int i, int j) {
		if (COUNT_OPS) DoublingTest.incOps ();
		T swap = pq[i-1];
		pq[i-1] = pq[j-1];
		pq[j-1] = swap;
	}

	// is v < w ?
	private static <T extends Comparable<? super T>> boolean less(T v, T w) {
		if (COUNT_OPS) DoublingTest.incOps ();
		return (v.compareTo(w) < 0);
	}


	/* *********************************************************************
	 *  Check if array is sorted - useful for debugging
	 ***********************************************************************/
	private static <T extends Comparable<? super T>> boolean isSorted(T[] a) {
		for (int i = 1; i < a.length; i++)
			if (less(a[i], a[i-1])) return false;
		return true;
	}


	// print array to standard output
	private static <T> void show(T[] a) {
		for (T element : a) {
			StdOut.println(element);
		}
	}


	// test code
	private static boolean COUNT_OPS = false;
	public static void main(String[] args) {
		StdIn.fromString ("S O R T E X A M P L E");
		//StdIn.fromFile ("data/tiny.txt");
		//StdIn.fromFile ("data/cards.txt");
		//StdIn.fromFile ("data/words3.txt");

		String[] a = StdIn.readAllStrings();
		//StdRandom.shuffle (a);
		//show(a);
		//StdOut.println ("----------------");
		sort(a);
		show(a);

		COUNT_OPS = true;
		DoublingTest.run (2000, 10, N -> ArrayGenerator.integerRandomUnique (N),          (Integer[] x) -> sort (x));
		//DoublingTest.run (2000, 10, N -> ArrayGenerator.integerRandom (N, 2),             (Integer[] x) -> sort (x));
		//DoublingTest.run (2000, 10, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x));
	}
}