use strict;
use warnings;
use Time::HiRes qw(time);

sub read_file {
	print "READING INPUT FILE...";
	my ($fileSpec) = @_;
	open my $input_file, '<', $fileSpec or die "Cannot open $fileSpec: $!";
	my @values = map {chomp; $_} grep {/\S/} <$input_file>;
	close $input_file;
	print "DONE.\n";
	return @values;
}

sub save_file {
	print "SAVING OUTPUT FILE...";
	my ($values, $fileSpec) = @_;
	open my $output_file, '>', $fileSpec or die "Cannot create $fileSpec: $!";
	print {$output_file} "$_\n" for @$values;
	close $output_file or die "Cannot close $fileSpec: $1";
	print "DONE.\n";
}

sub sift_down {
	my ($values, $root, $end) = @_;
	while (2 * $root + 1 < $end) {
		my $child = 2 * $root + 1;
		$child++ if $child + 1 < $end && $values->[$child] < $values->[$child + 1];
		return if $values->[$root] >= $values->[$child];
		@$values[$root, $child] = @$values[$child, $root];
		$root = $child;
	}
}

sub heapsort {
	print "SORTING ELEMENTS...";
	my ($values) = @_;
	my $startTime = time;
	
	sift_down($values, $_, scalar @$values) for reverse 0 .. int(@$values / 2) -1;
	
	for(my $end = @$values -1; $end > 0; $end--) {
		@$values[0, $end] = @$values[$end, 0];
		sift_down($values, 0, $end);
	}
	
	my $endTime = time;
	print "DONE.\n";
	return $endTime - $startTime;
}

print "***HEAPSORT PERL***\n";
my @values = read_file("D:/Sorting/Sorting_Input.txt");
my $elapsed = heapsort(\@values);
save_file(\@values, "D:/Sorting/Output_PERL.txt");
print "***RUN COMPLETE***\n";
printf "HEAPSORT TOOK %.6f SECONDS.\n", $elapsed;