package Introsort;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;

public class Introsort {

	static Integer HeapSorts = 0;
	static Integer IntroSorts = 0;
	static Integer InsertionSorts = 0;
	
	// -------------------------------------------------------------------
	// loadFile
	// Purpose:
	//   Read non-blank integer lines from the named input file.
	// Parameters:
	//   fileSpec - path of the text file to read.
	// Returns:
	//   A list containing the parsed integers in input order.
	// Side effects:
	//   Opens and closes the input file and prints read progress.
	// -------------------------------------------------------------------
	static List<Integer> loadFile(String fileSpec) throws IOException {
		System.out.print("READING INPUT FILE...");
		List<Integer> values = new ArrayList<>();
		for(String line : Files.readAllLines(Path.of(fileSpec))) {
			if(!line.isBlank()) values.add(Integer.valueOf(line));
		}
		System.out.println("DONE.");
		return values;
	}
	// -------------------------------------------------------------------
	// saveFile
	// Purpose:
	//   Write each integer in values to the named output file.
	// Parameters:
	//   values - integer list to write in its current order.
	//   fileSpec - path of the output file to create or replace.
	// Returns:
	//   No value; propagates file errors as IOException.
	// Side effects:
	//   Writes and closes the output file and prints progress.
	// -------------------------------------------------------------------
	static void saveFile(List<Integer> values, String fileSpec) throws IOException {
		System.out.print("READING INPUT FILE...");
		Files.write(Path.of(fileSpec), values.stream().map(String::valueOf).toList());
		System.out.println("DONE.");
	}
	// -------------------------------------------------------------------
	// siftDown
	// Purpose:
	//   Restore max-heap order below root within the active heap range.
	// Parameters:
	//   values - integer list whose heap range may be rearranged.
	//   root - root index of the subtree to restore.
	//   start - inclusive first index of the heap range.
	//   end - exclusive end index of the heap range.
	// Returns:
	//   No value; modifies values in place.
	// Side effects:
	//   Swaps the root downward until it is no smaller than its children.
	// -------------------------------------------------------------------
	static void siftDown(List<Integer> values, Integer root, Integer start, Integer end) {
		while(start + 2 * (root - start) + 1 < end) {
			Integer child = start + 2 * (root - start) + 1;
			if (child + 1 < end && values.get(child) < values.get(child + 1)) child++;
			if(values.get(root) >= values.get(child))return;
			Integer temp = values.get(root);
			values.set(root,  values.get(child));
			values.set(child,  temp);
			root = child;
		}
	}
	// -------------------------------------------------------------------
	// heapSort
	// Purpose:
	//   Sort a half-open range in place with heapsort for the depth fallback.
	// Parameters:
	//   values - integer list to mutate.
	//   start - inclusive first index of the range.
	//   end - exclusive end index of the range.
	// Returns:
	//   No value; sorts the selected range.
	// Side effects:
	//   Builds a max heap, extracts its maximum repeatedly, and increments
	//   HeapSorts.
	// -------------------------------------------------------------------
	static void heapSort(List<Integer> values, Integer start, Integer end) {
		HeapSorts++;
		for(Integer root = start + (end - start) / 2 - 1; root >= start; root--)siftDown(values,root, start,end);
		for(Integer last = end - 1; last > start; last--) {
			Integer temp = values.get(start);
			values.set(start,  values.get(last));
			values.set(last,  temp);
			siftDown(values,start,start,last);
		}
	}
	// -------------------------------------------------------------------
	// insertionSort
	// Purpose:
	//   Sort a short half-open range by inserting each value in order.
	// Parameters:
	//   values - integer list to mutate.
	//   start - inclusive first index of the range.
	//   end - exclusive end index of the range.
	// Returns:
	//   No value; sorts the selected range.
	// Side effects:
	//   Shifts larger values right and increments InsertionSorts.
	// -------------------------------------------------------------------
	static void insertionSort(List<Integer> values, Integer start, Integer end) {
		InsertionSorts++;
		Integer value, pos;
		for(Integer index = start; index < end; index++) {
			value = values.get(index);
			pos = index -1;
			while(pos >= start && values.get(pos) > value) {
				values.set(pos + 1,  values.get(pos));
				pos--;
			}
			values.set(pos + 1,  value);
		}
	}
	// -------------------------------------------------------------------
	// partition
	// Purpose:
	//   Partition a half-open range around its middle-element pivot.
	// Parameters:
	//   values - integer list whose range is rearranged in place.
	//   start - inclusive first index of the range.
	//   end - exclusive end index of the range.
	// Returns:
	//   The first index of the right partition for recursive sorting.
	// Side effects:
	//   Exchanges values found on the wrong side of the pivot.
	// -------------------------------------------------------------------
	static Integer partition(List<Integer> values, Integer start, Integer end) {
		Integer left = start;
		Integer right = end - 1;
		Integer pivot = values.get(start + (end - start) / 2);
		while(left <= right) {
			while(values.get(left) < pivot)left++;
			while(values.get(right) > pivot)right--;
			if(left <= right) {
				Integer temp = values.get(left);
				values.set(left, values.get(right));
				values.set(right, temp);
				left++;
				right--;
			}
		}
		return left;
	}
	// -------------------------------------------------------------------
	// introSort
	// Purpose:
	//   Sort a range using insertion sort for small ranges, heapsort when the
	//   depth budget expires, or partitioning and recursion otherwise.
	// Parameters:
	//   values - integer list to sort in place.
	//   start - inclusive first index of the range.
	//   end - exclusive end index of the range.
	//   maxDepth - remaining partition budget before heapsort fallback.
	// Returns:
	//   No value; sorts the selected range.
	// Side effects:
	//   Updates IntroSorts and may recursively invoke the helper algorithms.
	// -------------------------------------------------------------------
	static void introSort(List<Integer> values, Integer start, Integer end, Integer maxDepth ) {
		IntroSorts++;
		Integer length = end - start;
		if(length <= 1)return;
		if(length < 16)insertionSort(values, start, end);
		else if(maxDepth <= 0)heapSort(values, start, end);
		else
		{
			int part = partition(values, start, end);
			introSort(values,start, part, maxDepth - 1);
			introSort(values, part, end, maxDepth - 1);
		}
	}
	// -------------------------------------------------------------------
	// performSort
	// Purpose:
	//   Measure a top-level sort of the complete list and initialize its depth.
	// Parameters:
	//   values - integer list to sort in place.
	// Returns:
	//   Elapsed time in seconds.
	// Side effects:
	//   Prints progress and invokes introSort.
	// -------------------------------------------------------------------
	static Double performSort(List<Integer> values) throws Exception {
		System.out.print("SORTING ELEMENTS...");
		Long startTime = System.nanoTime();
		Integer maxDepth = values.size() > 1 ? log2(values.size())  : 0;
		introSort(values,0,values.size(),maxDepth);
		Long endTime = System.nanoTime();
		System.out.println("DONE.");
		return (endTime - startTime) / 1_000_000_000.0;
	}
	// -------------------------------------------------------------------
	// log2
	// Purpose:
	//   Compute floor(log2(bits)) for the initial recursion-depth estimate.
	// Parameters:
	//   bits - positive integer whose base-two logarithm is requested.
	// Returns:
	//   The integer base-two logarithm.
	// Side effects:
	//   Throws Exception if bits is not positive.
	// -------------------------------------------------------------------
	static int log2(int bits) throws Exception {
		if (bits <=0) throw new Exception("Value must be greater than zero.");
		return 31 - Integer.numberOfLeadingZeros(bits);
	}
	// -------------------------------------------------------------------
	// main
	// Purpose:
	//   Program entry point: load values, sort them, save the result, and report
	//   elapsed time and helper invocation counts.
	// Parameters:
	//   args - command-line arguments provided by the runtime (unused here).
	// Returns:
	//   No value.
	// Side effects:
	//   Performs file I/O and writes run statistics to the console.
	// -------------------------------------------------------------------
	public static void main(String[] args) throws Exception {
		System.out.println("=========INTROSORT JAVA=========");
		List<Integer> values = loadFile("D:/Sorting/Sorting_Input.txt");
		Double elapsed = performSort(values);
		saveFile(values, "D:/Sorting/Output_JAVA.txt");
		System.out.println("==========RUN COMPLETE==========");
		System.out.printf("INTROSORT TOOK %.6f SECONDS.%n",elapsed);
		System.out.println("================================");
		System.out.println("SORT CALLED | TIMES");
		System.out.println("------------+-------------------");
		System.out.printf("Intro      | %5d%n", IntroSorts);
		System.out.printf("Insertion  | %5d%n", InsertionSorts);
		System.out.printf("Heap       | %5d%n", HeapSorts);
		System.out.println("================================");
	}

}