# Copyright (c) 2023 Yuki Kimoto
# MIT License
class Sort {
version_from SPVM;
use Comparator::Int;
use Comparator::Long;
use Comparator::Float;
use Comparator::Double;
use Comparator::String;
use Comparator;
use Fn;
use Array;
static method sort_byte : void ($array : byte[], $comparator : Comparator::Int, $offset : int = 0, $length : int = -1) {
unless ($array) {
die "The array \$array must be defined.";
}
unless ($comparator) {
die "The comparator \$comparator must be defined.";
}
unless ($offset >= 0) {
die "The offset \$offset must be greater than or equal to 0.";
}
my $array_length = @$array;
if ($length < 0) {
$length = $array_length - $offset;
}
unless ($offset + $length <= $array_length) {
die "The offset \$offset + the length \$length must be less than or equal to the length of the array \$array.";
}
if ($length == 0) {
return;
}
my $b = new byte[$length];
Sort->_sort_byte_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
}
static method sort_byte_asc : void ($array : byte[], $offset : int = 0, $length : int = -1) {
&sort_byte($array, method : int ($a : int, $b : int) { return $a <=> $b; }, $offset, $length);
}
static method sort_byte_desc : void ($array : byte[], $offset : int = 0, $length : int = -1) {
&sort_byte($array, method : int ($a : int, $b : int) { return $b <=> $a; }, $offset, $length);
}
static method sort_double : void ($array : double[], $comparator : Comparator::Double, $offset : int = 0, $length : int = -1) {
unless ($array) {
die "The array \$array must be defined.";
}
unless ($comparator) {
die "The comparator \$comparator must be defined.";
}
unless ($offset >= 0) {
die "The offset \$offset must be greater than or equal to 0.";
}
my $array_length = @$array;
if ($length < 0) {
$length = $array_length - $offset;
}
unless ($offset + $length <= $array_length) {
die "The offset \$offset + the length \$length must be less than or equal to the length of the array \$array.";
}
if ($length == 0) {
return;
}
my $b = new double[$length];
Sort->_sort_double_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
}
static method sort_double_asc : void ($array : double[], $offset : int = 0, $length : int = -1) {
&sort_double($array, method : int ($a : double, $b : double) { return $a <=> $b; }, $offset, $length);
}
static method sort_double_desc : void ($array : double[], $offset : int = 0, $length : int = -1) {
&sort_double($array, method : int ($a : double, $b : double) { return $b <=> $a; }, $offset, $length);
}
static method sort_float : void ($array : float[], $comparator : Comparator::Float, $offset : int = 0, $length : int = -1) {
unless ($array) {
die "The array \$array must be defined.";
}
unless ($comparator) {
die "The comparator \$comparator must be defined.";
}
unless ($offset >= 0) {
die "The offset \$offset must be greater than or equal to 0.";
}
my $array_length = @$array;
if ($length < 0) {
$length = $array_length - $offset;
}
unless ($offset + $length <= $array_length) {
die "The offset \$offset + the length \$length must be less than or equal to the length of the array \$array.";
}
if ($length == 0) {
return;
}
my $b = new float[$length];
Sort->_sort_float_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
}
static method sort_float_asc : void ($array : float[], $offset : int = 0, $length : int = -1) {
&sort_float($array, method : int ($a : float, $b : float) { return $a <=> $b; }, $offset, $length);
}
static method sort_float_desc : void ($array : float[], $offset : int = 0, $length : int = -1) {
&sort_float($array, method : int ($a : float, $b : float) { return $b <=> $a; }, $offset, $length);
}
static method sort_int : void ($array : int[], $comparator : Comparator::Int, $offset : int = 0, $length : int = -1) {
unless ($array) {
die "The array \$array must be defined.";
}
unless ($comparator) {
die "The comparator \$comparator must be defined.";
}
unless ($offset >= 0) {
die "The offset \$offset must be greater than or equal to 0.";
}
my $array_length = @$array;
if ($length < 0) {
$length = $array_length - $offset;
}
unless ($offset + $length <= $array_length) {
die "The offset \$offset + the length \$length must be less than or equal to the length of the array \$array.";
}
if ($length == 0) {
return;
}
my $b = new int[$length];
Sort->_sort_int_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
}
static method sort_int_asc : void ($array : int[], $offset : int = 0, $length : int = -1) {
&sort_int($array, method : int ($a : int, $b : int) { return $a <=> $b; }, $offset, $length);
}
static method sort_int_desc : void ($array : int[], $offset : int = 0, $length : int = -1) {
&sort_int($array, method : int ($a : int, $b : int) { return $b <=> $a; }, $offset, $length);
}
static method sort_long : void ($array : long[], $comparator : Comparator::Long, $offset : int = 0, $length : int = -1) {
unless ($array) {
die "The array \$array must be defined.";
}
unless ($comparator) {
die "The comparator \$comparator must be defined.";
}
unless ($offset >= 0) {
die "The offset \$offset must be greater than or equal to 0.";
}
my $array_length = @$array;
if ($length < 0) {
$length = $array_length - $offset;
}
unless ($offset + $length <= $array_length) {
die "The offset \$offset + the length \$length must be less than or equal to the length of the array \$array.";
}
if ($length == 0) {
return;
}
my $b = new long[$length];
Sort->_sort_long_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
}
static method sort_long_asc : void ($array : long[], $offset : int = 0, $length : int = -1) {
&sort_long($array, method : int ($a : long, $b : long) { return $a <=> $b; }, $offset, $length);
}
static method sort_long_desc : void ($array : long[], $offset : int = 0, $length : int = -1) {
&sort_long($array, method : int ($a : long, $b : long) { return $b <=> $a; }, $offset, $length);
}
static method sort_object : void ($array : object[], $comparator : Comparator, $offset : int = 0, $length : int = -1) {
unless ($array) {
die "The array \$array must be defined.";
}
unless ($comparator) {
die "The comparator \$comparator must be defined.";
}
unless ($offset >= 0) {
die "The offset \$offset must be greater than or equal to 0.";
}
my $array_length = @$array;
if ($length < 0) {
$length = $array_length - $offset;
}
unless ($offset + $length <= $array_length) {
die "The offset \$offset + the length \$length must be less than or equal to the length of the array \$array.";
}
if ($length == 0) {
return;
}
my $b = Array->new_proto($array, $length);
Sort->_sort_object_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
}
static method sort_short : void ($array : short[], $comparator : Comparator::Int, $offset : int = 0, $length : int = -1) {
unless ($array) {
die "The array \$array must be defined.";
}
unless ($comparator) {
die "The comparator \$comparator must be defined.";
}
unless ($offset >= 0) {
die "The offset \$offset must be greater than or equal to 0.";
}
my $array_length = @$array;
if ($length < 0) {
$length = $array_length - $offset;
}
unless ($offset + $length <= $array_length) {
die "The offset \$offset + the length \$length must be less than or equal to the length of the array \$array.";
}
if ($length == 0) {
return;
}
my $b = new short[$length];
Sort->_sort_short_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
}
static method sort_short_asc : void ($array : short[], $offset : int = 0, $length : int = -1) {
&sort_short($array, method : int ($a : int, $b : int) { return $a <=> $b; }, $offset, $length);
}
static method sort_short_desc : void ($array : short[], $offset : int = 0, $length : int = -1) {
&sort_short($array, method : int ($a : int, $b : int) { return $b <=> $a; }, $offset, $length);
}
static method sort_string : void ($array : string[], $comparator : Comparator::String, $offset : int = 0, $length : int = -1) {
unless ($array) {
die "The array \$array must be defined.";
}
unless ($comparator) {
die "The comparator \$comparator must be defined.";
}
unless ($offset >= 0) {
die "The offset \$offset must be greater than or equal to 0.";
}
my $array_length = @$array;
if ($length < 0) {
$length = $array_length - $offset;
}
unless ($offset + $length <= $array_length) {
die "The offset \$offset + the length \$length must be less than or equal to the length of the array \$array.";
}
if ($length == 0) {
return;
}
my $b = new string[$length];
Sort->_sort_string_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
}
static method sort_string_asc : void ($array : string[], $offset : int = 0, $length : int = -1) {
&sort_string($array, method : int ($a : string, $b : string) { return $a cmp $b; }, $offset, $length);
}
static method sort_string_desc : void ($array : string[], $offset : int = 0, $length : int = -1) {
&sort_string($array, method : int ($a : string, $b : string) { return $b cmp $a; }, $offset, $length);
}
precompile private static method _sort_byte_merge : void($a : byte[], $b : byte[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::Int) {
my $i = $left;
my $j = $mid + 1;
my $k = 0;
while ($i <= $mid && $j <= $right) {
$i = $left;
$j = $mid + 1;
$k = 0;
while ($i <= $mid && $j <= $right) {
if ($comparator->($a->[$i], $a->[$j]) <= 0) {
$b->[$k] = $a->[$i];
$i++;
} else {
$b->[$k] = $a->[$j];
$j++;
}
$k++;
}
if ($i == $mid + 1) {
while ($j <= $right) {
$b->[$k] = $a->[$j];
$j++;
$k++;
}
} else {
while($i <= $mid) {
$b->[$k] = $a->[$i];
$i++;
$k++;
}
}
}
for ($i = 0; $i < $k; $i++) {
$a->[$i + $left] = $b->[$i];
}
}
private static method _sort_byte_merge_sort : void($a : byte[], $b : byte[], $left : int, $right : int, $n : int, $comparator : Comparator::Int){
if ($left >= $right) {
return;
}
my $mid = ($left + $right) / 2;
Sort->_sort_byte_merge_sort($a, $b, $left, $mid, $n, $comparator);
Sort->_sort_byte_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
Sort->_sort_byte_merge($a, $b, $left, $mid, $right, $n, $comparator);
}
precompile private static method _sort_double_merge : void($a : double[], $b : double[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::Double) {
my $i = $left;
my $j = $mid + 1;
my $k = 0;
while ($i <= $mid && $j <= $right) {
$i = $left;
$j = $mid + 1;
$k = 0;
while ($i <= $mid && $j <= $right) {
if ($comparator->($a->[$i], $a->[$j]) <= 0) {
$b->[$k] = $a->[$i];
$i++;
} else {
$b->[$k] = $a->[$j];
$j++;
}
$k++;
}
if ($i == $mid + 1) {
while ($j <= $right) {
$b->[$k] = $a->[$j];
$j++;
$k++;
}
} else {
while($i <= $mid) {
$b->[$k] = $a->[$i];
$i++;
$k++;
}
}
}
for ($i = 0; $i < $k; $i++) {
$a->[$i + $left] = $b->[$i];
}
}
private static method _sort_double_merge_sort : void($a : double[], $b : double[], $left : int, $right : int, $n : int, $comparator : Comparator::Double){
if ($left >= $right) {
return;
}
my $mid = ($left + $right) / 2;
Sort->_sort_double_merge_sort($a, $b, $left, $mid, $n, $comparator);
Sort->_sort_double_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
Sort->_sort_double_merge($a, $b, $left, $mid, $right, $n, $comparator);
}
precompile private static method _sort_float_merge : void($a : float[], $b : float[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::Float) {
my $i = $left;
my $j = $mid + 1;
my $k = 0;
while ($i <= $mid && $j <= $right) {
$i = $left;
$j = $mid + 1;
$k = 0;
while ($i <= $mid && $j <= $right) {
if ($comparator->($a->[$i], $a->[$j]) <= 0) {
$b->[$k] = $a->[$i];
$i++;
} else {
$b->[$k] = $a->[$j];
$j++;
}
$k++;
}
if ($i == $mid + 1) {
while ($j <= $right) {
$b->[$k] = $a->[$j];
$j++;
$k++;
}
} else {
while($i <= $mid) {
$b->[$k] = $a->[$i];
$i++;
$k++;
}
}
}
for ($i = 0; $i < $k; $i++) {
$a->[$i + $left] = $b->[$i];
}
}
private static method _sort_float_merge_sort : void($a : float[], $b : float[], $left : int, $right : int, $n : int, $comparator : Comparator::Float){
if ($left >= $right) {
return;
}
my $mid = ($left + $right) / 2;
Sort->_sort_float_merge_sort($a, $b, $left, $mid, $n, $comparator);
Sort->_sort_float_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
Sort->_sort_float_merge($a, $b, $left, $mid, $right, $n, $comparator);
}
precompile private static method _sort_int_merge : void($a : int[], $b : int[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::Int) {
my $i = $left;
my $j = $mid + 1;
my $k = 0;
while ($i <= $mid && $j <= $right) {
$i = $left;
$j = $mid + 1;
$k = 0;
while ($i <= $mid && $j <= $right) {
if ($comparator->($a->[$i], $a->[$j]) <= 0) {
$b->[$k] = $a->[$i];
$i++;
} else {
$b->[$k] = $a->[$j];
$j++;
}
$k++;
}
if ($i == $mid + 1) {
while ($j <= $right) {
$b->[$k] = $a->[$j];
$j++;
$k++;
}
} else {
while($i <= $mid) {
$b->[$k] = $a->[$i];
$i++;
$k++;
}
}
}
for ($i = 0; $i < $k; $i++) {
$a->[$i + $left] = $b->[$i];
}
}
private static method _sort_int_merge_sort : void($a : int[], $b : int[], $left : int, $right : int, $n : int, $comparator : Comparator::Int){
if ($left >= $right) {
return;
}
my $mid = ($left + $right) / 2;
Sort->_sort_int_merge_sort($a, $b, $left, $mid, $n, $comparator);
Sort->_sort_int_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
Sort->_sort_int_merge($a, $b, $left, $mid, $right, $n, $comparator);
}
precompile private static method _sort_long_merge : void($a : long[], $b : long[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::Long) {
my $i = $left;
my $j = $mid + 1;
my $k = 0;
while ($i <= $mid && $j <= $right) {
$i = $left;
$j = $mid + 1;
$k = 0;
while ($i <= $mid && $j <= $right) {
if ($comparator->($a->[$i], $a->[$j]) <= 0) {
$b->[$k] = $a->[$i];
$i++;
} else {
$b->[$k] = $a->[$j];
$j++;
}
$k++;
}
if ($i == $mid + 1) {
while ($j <= $right) {
$b->[$k] = $a->[$j];
$j++;
$k++;
}
} else {
while($i <= $mid) {
$b->[$k] = $a->[$i];
$i++;
$k++;
}
}
}
for ($i = 0; $i < $k; $i++) {
$a->[$i + $left] = $b->[$i];
}
}
private static method _sort_long_merge_sort : void($a : long[], $b : long[], $left : int, $right : int, $n : int, $comparator : Comparator::Long){
if ($left >= $right) {
return;
}
my $mid = ($left + $right) / 2;
Sort->_sort_long_merge_sort($a, $b, $left, $mid, $n, $comparator);
Sort->_sort_long_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
Sort->_sort_long_merge($a, $b, $left, $mid, $right, $n, $comparator);
}
precompile private static method _sort_object_merge : void($a : object[], $b : object[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator) {
my $i = $left;
my $j = $mid + 1;
my $k = 0;
while ($i <= $mid && $j <= $right) {
$i = $left;
$j = $mid + 1;
$k = 0;
while ($i <= $mid && $j <= $right) {
if ($comparator->($a->[$i], $a->[$j]) <= 0) {
$b->[$k] = $a->[$i];
$i++;
} else {
$b->[$k] = $a->[$j];
$j++;
}
$k++;
}
if ($i == $mid + 1) {
while ($j <= $right) {
$b->[$k] = $a->[$j];
$j++;
$k++;
}
} else {
while($i <= $mid) {
$b->[$k] = $a->[$i];
$i++;
$k++;
}
}
}
for ($i = 0; $i < $k; $i++) {
$a->[$i + $left] = $b->[$i];
}
}
private static method _sort_object_merge_sort : void($a : object[], $b : object[], $left : int, $right : int, $n : int, $comparator : Comparator){
if ($left >= $right) {
return;
}
my $mid = ($left + $right) / 2;
Sort->_sort_object_merge_sort($a, $b, $left, $mid, $n, $comparator);
Sort->_sort_object_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
Sort->_sort_object_merge($a, $b, $left, $mid, $right, $n, $comparator);
}
precompile private static method _sort_short_merge : void($a : short[], $b : short[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::Int) {
my $i = $left;
my $j = $mid + 1;
my $k = 0;
while ($i <= $mid && $j <= $right) {
$i = $left;
$j = $mid + 1;
$k = 0;
while ($i <= $mid && $j <= $right) {
if ($comparator->($a->[$i], $a->[$j]) <= 0) {
$b->[$k] = $a->[$i];
$i++;
} else {
$b->[$k] = $a->[$j];
$j++;
}
$k++;
}
if ($i == $mid + 1) {
while ($j <= $right) {
$b->[$k] = $a->[$j];
$j++;
$k++;
}
} else {
while($i <= $mid) {
$b->[$k] = $a->[$i];
$i++;
$k++;
}
}
}
for ($i = 0; $i < $k; $i++) {
$a->[$i + $left] = $b->[$i];
}
}
private static method _sort_short_merge_sort : void($a : short[], $b : short[], $left : int, $right : int, $n : int, $comparator : Comparator::Int){
if ($left >= $right) {
return;
}
my $mid = ($left + $right) / 2;
Sort->_sort_short_merge_sort($a, $b, $left, $mid, $n, $comparator);
Sort->_sort_short_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
Sort->_sort_short_merge($a, $b, $left, $mid, $right, $n, $comparator);
}
precompile private static method _sort_string_merge : void($a : string[], $b : string[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::String) {
my $i = $left;
my $j = $mid + 1;
my $k = 0;
while ($i <= $mid && $j <= $right) {
$i = $left;
$j = $mid + 1;
$k = 0;
while ($i <= $mid && $j <= $right) {
if ($comparator->($a->[$i], $a->[$j]) <= 0) {
$b->[$k] = $a->[$i];
$i++;
} else {
$b->[$k] = $a->[$j];
$j++;
}
$k++;
}
if ($i == $mid + 1) {
while ($j <= $right) {
$b->[$k] = $a->[$j];
$j++;
$k++;
}
} else {
while($i <= $mid) {
$b->[$k] = $a->[$i];
$i++;
$k++;
}
}
}
for ($i = 0; $i < $k; $i++) {
$a->[$i + $left] = $b->[$i];
}
}
private static method _sort_string_merge_sort : void($a : string[], $b : string[], $left : int, $right : int, $n : int, $comparator : Comparator::String){
if ($left >= $right) {
return;
}
my $mid = ($left + $right) / 2;
Sort->_sort_string_merge_sort($a, $b, $left, $mid, $n, $comparator);
Sort->_sort_string_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
Sort->_sort_string_merge($a, $b, $left, $mid, $right, $n, $comparator);
}
precompile static method sort_options_asc : void ($options : object[]) {
unless ($options) {
die "The options \$options must be defined.";
}
my $options_length = @$options;
unless ($options_length % 2 == 0) {
die "The length of the options \$options must be an even number.";
}
my $sorted_options_h = Hash->new;
my $key_values_list = List->new;
for (my $i = 0; $i < $options_length; $i += 2) {
unless ($options->[$i]) {
die "The key of \$options must be defined.";
}
unless ($options->[$i] isa string) {
die "The key of \$options must be string type.";
}
my $name = (string)$options->[$i];
my $value = $options->[$i + 1];
$key_values_list->push({$name => $value});
}
my $key_values = $key_values_list->to_array;
Sort->sort_object($key_values, method : int ($object1 : object, $object2 : object) {
my $name1 = $object1->(object[])->[0]->(string);
my $name2 = $object2->(object[])->[0]->(string);
return $name1 cmp $name2;
});
my $index = 0;
for my $key_value (@$key_values) {
my $key = $key_value->(object[])->[0];
my $value = $key_value->(object[])->[1];
$options->[$index] = $key;
$options->[$index + 1] = $value;
$index += 2;
}
}
}