package Sorting;

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

public class Heapsort {
	// ---------------------------------------------------------------------------
	// siftDown
	// Purpose:
	//   Restore the max-heap property below root in values[0..end).
	// Parameters:
	//   values - list to mutate; root - subtree root; end - exclusive heap end.
	// Returns:
	//   None.
	// Variables used:
	//   child, temp - child selection and swap storage.
	// ---------------------------------------------------------------------------
	static void siftDown(List<Integer> values, int root, int end)
	{
		while(2 * root + 1 < end)
		{
			int child = 2 * root + 1;
			if(child + 1 < end && values.get(child) < values.get(child + 1)) child++;
			if(values.get(root) >= values.get(child)) return;
			int temp = values.get(root);
			values.set(root,  values.get(child));
			values.set(child, temp);
			root = child;
		}
	}
	
	// ---------------------------------------------------------------------------
	// readFile
	// Purpose:
	//   Read non-empty lines from a file and parse them as integers.
	// Parameters:
	//   fileSpec - input file path.
	// Returns:
	//   The loaded list; may throw IOException or a number-format exception.
	// Variables used:
	//   values, line - accumulated data and current input line.
	// ---------------------------------------------------------------------------
	static List<Integer> readFile(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 all values to a file, one integer per line.
	// Parameters:
	//   values - list to write; fileSpec - output path.
	// Returns:
	//   None; may throw IOException.
	// Variables used:
	//   stream mapping - converts each integer to its decimal string.
	// ---------------------------------------------------------------------------
	static void saveFile(List<Integer> values, String fileSpec) throws IOException {
		System.out.print("WRITING OUTPUT FILE...");
		Files.write(Path.of(fileSpec), values.stream().map(String::valueOf).toList());
		System.out.println("DONE.");		
	}
	
	// ---------------------------------------------------------------------------
	// heapSort
	// Purpose:
	//   Sort values in place using heap sort and measure elapsed time.
	// Parameters:
	//   values - list to sort.
	// Returns:
	//   Elapsed duration in seconds.
	// Variables used:
	//   startTime, endTime - nanosecond timer snapshots; start/end - heap bounds.
	// ---------------------------------------------------------------------------
	static double heapSort(List<Integer> values)
	{
		System.out.print("SORTING ELEMENTS...");
		long startTime = System.nanoTime();
		for(int start = values.size() / 2 - 1;start >= 0;start--) siftDown(values, start, values.size());
		for(int end = values.size() - 1;end > 0;end--) {
			int temp = values.get(0);
			values.set(0, values.get(end));
			values.set(end,  temp);
			siftDown(values,0,end);
		}
		long endTime = System.nanoTime();
		System.out.println("DONE.");
		return (endTime - startTime) / 1_000_000_000.0;
	}
	
	// ---------------------------------------------------------------------------
	// main
	// Purpose:
	//   Load, sort, and save the configured input data.
	// Parameters:
	//   args - process command-line arguments (unused).
	// Returns:
	//   None; may throw IOException.
	// Variables used:
	//   values - loaded/sorted data; elapsed - measured seconds.
	// ---------------------------------------------------------------------------
	public static void main(String[] args) throws IOException {
		System.out.println("***HEAPSORT JAVA***");
		List<Integer> values = readFile("D:/Sorting/Sorting_Input.txt");
		double elapsed = heapSort(values);
		saveFile(values, "D:/Sorting/Output_Java.txt");
		System.out.println("***RUN COMPLETE***");
		System.out.printf("HEAPSORT TOOK %.6f SECONDS.%n",elapsed);
	}
}