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;
	
	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;
	}
	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.");
	}
	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;
		}
	}
	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);
		}
	}
	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);
		}
	}
	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;
	}
	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);
		}
	}
	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;
	}
	static int log2(int bits) throws Exception {
		if (bits <=0) throw new Exception("Value must be greater than zero.");
		return 31 - Integer.numberOfLeadingZeros(bits);
	}
	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("================================");
	}

}