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 {
	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;
		}
	}
	
	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;
	}
	
	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.");		
	}
	
	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;
	}
	
	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);
	}
}