package SPVM::ArrayUtil : precompile {
  use SPVM::Cloner;
  use SPVM::EqualityChecker;
  use SPVM::StringUtil;
  use SPVM::Comparator::Byte;
  use SPVM::Comparator::Short;
  use SPVM::Comparator::Int;
  use SPVM::Comparator::Long;
  use SPVM::Comparator::Float;
  use SPVM::Comparator::Double;
  use SPVM::Comparator::String;
  use SPVM::Comparator::Object;

  sub copy_array_byte : byte[] ($nums : byte[]) {
    if ($nums == undef) {
      return undef;
    }
    
    my $length = @$nums;

    my $new_nums = new byte[$length];

    for (my $i = 0; $i < $length; $i++) {
      $new_nums->[$i] = $nums->[$i];
    }

    return $new_nums;
  }

  sub copy_array_short : short[] ($nums : short[]) {
    if ($nums == undef) {
      return undef;
    }
    
    my $length = @$nums;

    my $new_nums = new short[$length];

    for (my $i = 0; $i < $length; $i++) {
      $new_nums->[$i] = $nums->[$i];
    }

    return $new_nums;
  }

  sub copy_array_int : int[] ($nums : int[]) {
    if ($nums == undef) {
      return undef;
    }
    
    my $length = @$nums;

    my $new_nums = new int[$length];

    for (my $i = 0; $i < $length; $i++) {
      $new_nums->[$i] = $nums->[$i];
    }

    return $new_nums;
  }

  sub copy_array_long : long[] ($nums : long[]) {
    if ($nums == undef) {
      return undef;
    }
    
    my $length = @$nums;

    my $new_nums = new long[$length];

    for (my $i = 0; $i < $length; $i++) {
      $new_nums->[$i] = $nums->[$i];
    }

    return $new_nums;
  }

  sub copy_array_float : float[] ($nums : float[]) {
    if ($nums == undef) {
      return undef;
    }
    
    my $length = @$nums;

    my $new_nums = new float[$length];

    for (my $i = 0; $i < $length; $i++) {
      $new_nums->[$i] = $nums->[$i];
    }

    return $new_nums;
  }

  sub copy_array_double : double[] ($nums : double[]) {
    if ($nums == undef) {
      return undef;
    }
    
    my $length = @$nums;

    my $new_nums = new double[$length];

    for (my $i = 0; $i < $length; $i++) {
      $new_nums->[$i] = $nums->[$i];
    }

    return $new_nums;
  }

  sub copy_array_string : string[] ($strings : string[]) {
    if ($strings == undef) {
      return undef;
    }
    
    my $length = @$strings;

    my $new_strings = new string[$length];

    for (my $i = 0; $i < $length; $i++) {
      $new_strings->[$i] = SPVM::StringUtil->copy_string($strings->[$i]);
    }

    return $new_strings;
  }
  
  sub copy_array_object : object[] ($objects : object[], $cloner : SPVM::Cloner) {
    if ($objects == undef) {
      return undef;
    }
    
    my $length = @$objects;

    my $new_objects = new object[$length];

    for (my $i = 0; $i < $length; $i++) {
      $new_objects->[$i] = $cloner->($objects->[$i]);
    }

    return $new_objects;
  }

  sub copy_array_range_byte : byte[] ($nums : byte[], $offset : int, $length : int) {

    if ($nums == undef) {
      die "The argument array must be defined";
    }

    my $array_length = @$nums;

    if ($offset < 0 || $offset > $array_length - 1) {
      die "Offset must be in the array range";
    }

    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }

    if ($offset + $length > $array_length) {
      die "Offset + length must be in the array range";
    }

    my $range = new byte[$length];

    my $pos = 0;
    for (my $i = $offset; $i < $offset + $length; $i++) {
      $range->[$pos] = $nums->[$i];
      $pos++;
    }

    return $range;
  }

  sub copy_array_range_short : short[] ($nums : short[], $offset : int, $length : int) {

    if ($nums == undef) {
      die "The argument array must be defined";
    }

    my $array_length = @$nums;

    if ($offset < 0 || $offset > $array_length - 1) {
      die "Offset must be in the array range";
    }

    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }

    if ($offset + $length > $array_length) {
      die "Offset + length must be in the array range";
    }

    my $range = new short[$length];

    my $pos = 0;
    for (my $i = $offset; $i < $offset + $length; $i++) {
      $range->[$pos] = $nums->[$i];
      $pos++;
    }

    return $range;
  }

  sub copy_array_range_int : int[] ($nums : int[], $offset : int, $length : int) {

    if ($nums == undef) {
      die "The argument array must be defined";
    }

    my $array_length = @$nums;

    if ($offset < 0 || $offset > $array_length - 1) {
      die "Offset must be in the array range";
    }

    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }

    if ($offset + $length > $array_length) {
      die "Offset + length must be in the array range";
    }

    my $range = new int[$length];

    my $pos = 0;
    for (my $i = $offset; $i < $offset + $length; $i++) {
      $range->[$pos] = $nums->[$i];
      $pos++;
    }

    return $range;
  }

  sub copy_array_range_long : long[] ($nums : long[], $offset : int, $length : int) {

    if ($nums == undef) {
      die "The argument array must be defined";
    }

    my $array_length = @$nums;

    if ($offset < 0 || $offset > $array_length - 1) {
      die "Offset must be in the array range";
    }

    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }

    if ($offset + $length > $array_length) {
      die "Offset + length must not be in the array range";
    }

    my $range = new long[$length];

    my $pos = 0;
    for (my $i = $offset; $i < $offset + $length; $i++) {
      $range->[$pos] = $nums->[$i];
      $pos++;
    }

    return $range;
  }

  sub copy_array_range_float : float[] ($nums : float[], $offset : int, $length : int) {

    if ($nums == undef) {
      die "The argument array must be defined";
    }

    my $array_length = @$nums;

    if ($offset < 0 || $offset > $array_length - 1) {
      die "Offset must be in the array range";
    }

    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }

    if ($offset + $length > $array_length) {
      die "Offset + length must not be in the array range";
    }

    my $range = new float[$length];

    my $pos = 0;
    for (my $i = $offset; $i < $offset + $length; $i++) {
      $range->[$pos] = $nums->[$i];
      $pos++;
    }

    return $range;
  }

  sub copy_array_range_double : double[] ($nums : double[], $offset : int, $length : int) {

    if ($nums == undef) {
      die "The argument array must be defined";
    }

    my $array_length = @$nums;

    if ($offset < 0 || $offset > $array_length - 1) {
      die "Offset must be in the array range";
    }

    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }

    if ($offset + $length > $array_length) {
      die "Offset + length must not be in the array range";
    }

    my $range = new double[$length];

    my $pos = 0;
    for (my $i = $offset; $i < $offset + $length; $i++) {
      $range->[$pos] = $nums->[$i];
      $pos++;
    }

    return $range;
  }

  sub copy_array_range_string : string[] ($strings : string[], $offset : int, $length : int) {

    if ($strings == undef) {
      die "The argument array must be defined";
    }

    my $array_length = @$strings;

    if ($offset < 0 || $offset > $array_length - 1) {
      die "Offset must be in the array range";
    }

    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }

    if ($offset + $length > $array_length) {
      die "Offset + length must not be in the array range";
    }

    my $range = new string[$length];

    my $pos = 0;
    for (my $i = $offset; $i < $offset + $length; $i++) {
      $range->[$pos] = $strings->[$i];
      $pos++;
    }

    return $range;
  }

  sub copy_array_range_object : oarray ($objects : oarray, $offset : int, $length : int) {

    if ($objects == undef) {
      die "The argument array must be defined";
    }

    my $array_length = @$objects;

    if ($offset < 0 || $offset > $array_length - 1) {
      die "Offset must be in the array range";
    }

    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }

    if ($offset + $length > $array_length) {
      die "Offset + length must not be in the array range";
    }

    my $range = new_array_proto($objects, $length);

    my $pos = 0;
    for (my $i = $offset; $i < $offset + $length; $i++) {
      $range->[$pos] = $objects->[$i];
      $pos++;
    }

    return $range;
  }

  sub equals_array_byte : int ($nums1 : byte[], $nums2 : byte[]) {
    
    if ($nums1 == undef && $nums2 == undef) {
      return 1;
    }
    elsif ($nums1 != undef && $nums2 == undef) {
      return 0;
    }
    elsif ($nums1 == undef && $nums2 != undef) {
      return 0;
    }
    
    my $is_equals = 1;
    if (@$nums1 == @$nums2) {
      for (my $i = 0; $i < @$nums1; $i++) {
        if ($nums1->[$i] != $nums2->[$i]) {
          $is_equals = 0;
          last;
        }
      }
    }
    else {
      $is_equals = 0;
    }

    return $is_equals;
  }

  sub equals_array_short : int ($nums1 : short[], $nums2 : short[]) {
    if ($nums1 == undef && $nums2 == undef) {
      return 1;
    }
    elsif ($nums1 != undef && $nums2 == undef) {
      return 0;
    }
    elsif ($nums1 == undef && $nums2 != undef) {
      return 0;
    }
    
    my $is_equals = 1;
    if (@$nums1 == @$nums2) {
      for (my $i = 0; $i < @$nums1; $i++) {
        if ($nums1->[$i] != $nums2->[$i]) {
          $is_equals = 0;
          last;
        }
      }
    }
    else {
      $is_equals = 0;
    }

    return $is_equals;
  }
  sub equals_array_int : int ($nums1 : int[], $nums2 : int[]) {
    if ($nums1 == undef && $nums2 == undef) {
      return 1;
    }
    elsif ($nums1 != undef && $nums2 == undef) {
      return 0;
    }
    elsif ($nums1 == undef && $nums2 != undef) {
      return 0;
    }
    
    my $is_equals = 1;
    if (@$nums1 == @$nums2) {
      for (my $i = 0; $i < @$nums1; $i++) {
        if ($nums1->[$i] != $nums2->[$i]) {
          $is_equals = 0;
          last;
        }
      }
    }
    else {
      $is_equals = 0;
    }

    return $is_equals;
  }
  sub equals_array_long : int ($nums1 : long[], $nums2 : long[]) {
    if ($nums1 == undef && $nums2 == undef) {
      return 1;
    }
    elsif ($nums1 != undef && $nums2 == undef) {
      return 0;
    }
    elsif ($nums1 == undef && $nums2 != undef) {
      return 0;
    }
    
    my $is_equals = 1;
    if (@$nums1 == @$nums2) {
      for (my $i = 0; $i < @$nums1; $i++) {
        if ($nums1->[$i] != $nums2->[$i]) {
          $is_equals = 0;
          last;
        }
      }
    }
    else {
      $is_equals = 0;
    }

    return $is_equals;
  }
  sub equals_array_float : int ($nums1 : float[], $nums2 : float[]) {
    if ($nums1 == undef && $nums2 == undef) {
      return 1;
    }
    elsif ($nums1 != undef && $nums2 == undef) {
      return 0;
    }
    elsif ($nums1 == undef && $nums2 != undef) {
      return 0;
    }
    
    my $is_equals = 1;
    if (@$nums1 == @$nums2) {
      for (my $i = 0; $i < @$nums1; $i++) {
        if ($nums1->[$i] != $nums2->[$i]) {
          $is_equals = 0;
          last;
        }
      }
    }
    else {
      $is_equals = 0;
    }

    return $is_equals;
  }
  sub equals_array_double : int ($nums1 : double[], $nums2 : double[]) {
    if ($nums1 == undef && $nums2 == undef) {
      return 1;
    }
    elsif ($nums1 != undef && $nums2 == undef) {
      return 0;
    }
    elsif ($nums1 == undef && $nums2 != undef) {
      return 0;
    }
    
    my $is_equals = 1;
    if (@$nums1 == @$nums2) {
      for (my $i = 0; $i < @$nums1; $i++) {
        if ($nums1->[$i] != $nums2->[$i]) {
          $is_equals = 0;
          last;
        }
      }
    }
    else {
      $is_equals = 0;
    }

    return $is_equals;
  }

  sub equals_array_string : int ($strings1 : string[], $strings2 : string[]) {
    if ($strings1 == undef && $strings2 == undef) {
      return 1;
    }
    elsif ($strings1 != undef && $strings2 == undef) {
      return 0;
    }
    elsif ($strings1 == undef && $strings2 != undef) {
      return 0;
    }
    
    my $is_equals = 1;
    if (@$strings1 == @$strings2) {
      for (my $i = 0; $i < @$strings1; $i++) {
        if ($strings1->[$i] ne $strings2->[$i]) {
          $is_equals = 0;
          last;
        }
      }
    }
    else {
      $is_equals = 0;
    }

    return $is_equals;
  }

  sub equals_array_object : int ($objects1 : oarray, $objects2 : oarray, $equality_checker : SPVM::EqualityChecker) {
    if ($objects1 == undef && $objects2 == undef) {
      return 1;
    }
    elsif ($objects1 != undef && $objects2 == undef) {
      return 0;
    }
    elsif ($objects1 == undef && $objects2 != undef) {
      return 0;
    }
    
    my $is_equals = 1;
    if (@$objects1 == @$objects2) {
      for (my $i = 0; $i < @$objects1; $i++) {
        if (!$equality_checker->($objects1->[$i], $objects2->[$i])) {
          $is_equals = 0;
          last;
        }
      }
    }
    else {
      $is_equals = 0;
    }

    return $is_equals;
  }

  sub dump_array_byte : string ($nums : byte[]) {
    
    if ($nums == undef) {
      return undef;
    }
    
    my $dump = "[\n";

    for (my $i = 0; $i < @$nums; $i++) {
      my $string = (string)$nums->[$i];
      $dump .= "  $string";
      if ($i != @$nums - 1) {
        $dump .= ",\n";
      }
      else {
        $dump .= "\n";
      }
    }
    
    $dump .= "]";

    return $dump;
  }

  sub dump_array_short : string ($nums : short[]) {
    
    if ($nums == undef) {
      return undef;
    }
    
    my $dump = "[\n";

    for (my $i = 0; $i < @$nums; $i++) {
      my $string = (string)$nums->[$i];
      $dump .= "  $string";
      if ($i != @$nums - 1) {
        $dump .= ",\n";
      }
      else {
        $dump .= "\n";
      }
    }
    
    $dump .= "]";

    return $dump;
  }

  sub dump_array_int : string ($nums : int[]) {
    
    if ($nums == undef) {
      return undef;
    }
    
    my $dump = "[\n";

    for (my $i = 0; $i < @$nums; $i++) {
      my $string = (string)$nums->[$i];
      $dump .= "  $string";
      if ($i != @$nums - 1) {
        $dump .= ",\n";
      }
      else {
        $dump .= "\n";
      }
    }
    
    $dump .= "]";

    return $dump;
  }

  sub dump_array_long : string ($nums : long[]) {
    
    if ($nums == undef) {
      return undef;
    }
    
    my $dump = "[\n";

    for (my $i = 0; $i < @$nums; $i++) {
      my $string = (string)$nums->[$i];
      $dump .= "  $string";
      if ($i != @$nums - 1) {
        $dump .= ",\n";
      }
      else {
        $dump .= "\n";
      }
    }
    
    $dump .= "]";

    return $dump;
  }

  sub dump_array_unsigned_byte : string ($nums : byte[]) {
    
    if ($nums == undef) {
      return undef;
    }
    
    my $dump = "[\n";

    for (my $i = 0; $i < @$nums; $i++) {
      my $string = SPVM::StringUtil->sprintf("%u", (int)$nums->[$i] & 0xFF);
      $dump .= "  $string";
      if ($i != @$nums - 1) {
        $dump .= ",\n";
      }
      else {
        $dump .= "\n";
      }
    }
    
    $dump .= "]";

    return $dump;
  }

  sub dump_array_unsigned_short : string ($nums : short[]) {
    
    if ($nums == undef) {
      return undef;
    }
    
    my $dump = "[\n";

    for (my $i = 0; $i < @$nums; $i++) {
      my $string = SPVM::StringUtil->sprintf("%u", (int)$nums->[$i] & 0xFFFF);
      $dump .= "  $string";
      if ($i != @$nums - 1) {
        $dump .= ",\n";
      }
      else {
        $dump .= "\n";
      }
    }
    
    $dump .= "]";

    return $dump;
  }

  sub dump_array_unsigned_int : string ($nums : int[]) {
    
    if ($nums == undef) {
      return undef;
    }
    
    my $dump = "[\n";

    for (my $i = 0; $i < @$nums; $i++) {
      my $string = SPVM::StringUtil->sprintf("%u", $nums->[$i]);
      $dump .= "  $string";
      if ($i != @$nums - 1) {
        $dump .= ",\n";
      }
      else {
        $dump .= "\n";
      }
    }
    
    $dump .= "]";

    return $dump;
  }

  sub dump_array_unsigned_long : string ($nums : long[]) {
    
    if ($nums == undef) {
      return undef;
    }
    
    my $dump = "[\n";

    for (my $i = 0; $i < @$nums; $i++) {
      my $string = SPVM::StringUtil->sprintf("%lu", $nums->[$i]);
      $dump .= "  $string";
      if ($i != @$nums - 1) {
        $dump .= ",\n";
      }
      else {
        $dump .= "\n";
      }
    }
    
    $dump .= "]";

    return $dump;
  }

  sub dump_array_float : string ($nums : float[]) {
    
    if ($nums == undef) {
      return undef;
    }
    
    my $dump = "[\n";

    for (my $i = 0; $i < @$nums; $i++) {
      my $string = (string)$nums->[$i];
      $dump .= "  $string";
      if ($i != @$nums - 1) {
        $dump .= ",\n";
      }
      else {
        $dump .= "\n";
      }
    }
    
    $dump .= "]";

    return $dump;
  }

  sub dump_array_double : string ($nums : double[]) {
    
    if ($nums == undef) {
      return undef;
    }
    
    my $dump = "[\n";

    for (my $i = 0; $i < @$nums; $i++) {
      my $string = (string)$nums->[$i];
      $dump .= "  $string";
      if ($i != @$nums - 1) {
        $dump .= ",\n";
      }
      else {
        $dump .= "\n";
      }
    }
    
    $dump .= "]";

    return $dump;
  }

  sub dump_array_string : string ($strings : string[]) {
    
    if ($strings == undef) {
      return undef;
    }
    
    my $dump = "[\n";

    for (my $i = 0; $i < @$strings; $i++) {
      my $string = $strings->[$i];
      $dump .= "  $string";
      if ($i != @$strings - 1) {
        $dump .= ",\n";
      }
      else {
        $dump .= "\n";
      }
    }
    
    $dump .= "]";

    return $dump;
  }

  sub dump_array_object : string ($objects : oarray, $stringer : SPVM::Stringer) {
    
    if ($objects == undef) {
      return undef;
    }
    
    my $dump = "[\n";

    for (my $i = 0; $i < @$objects; $i++) {
      my $string = $stringer->($objects->[$i]);
      $dump .= "  $string";
      if ($i != @$objects - 1) {
        $dump .= ",\n";
      }
      else {
        $dump .= "\n";
      }
    }
    
    $dump .= "]";

    return $dump;
  }

  native sub memcpy_byte : void ($dest : byte[], $dest_offset : int, $source : byte[], $source_offset : int, $length : int);
  native sub memcpy_short : void ($dest : short[], $dest_offset : int, $source : short[], $source_offset : int, $length : int);
  native sub memcpy_int : void ($dest : int[], $dest_offset : int, $source : int[], $source_offset : int, $length : int);
  native sub memcpy_long : void ($dest : long[], $dest_offset : int, $source : long[], $source_offset : int, $length : int);
  native sub memcpy_float : void ($dest : float[], $dest_offset : int, $source : float[], $source_offset : int, $length : int);
  native sub memcpy_double : void ($dest : double[], $dest_offset : int, $source : double[], $source_offset : int, $length : int);

  native sub memmove_byte : void ($dest : byte[], $dest_offset : int, $source : byte[], $source_offset : int, $length : int);
  native sub memmove_short : void ($dest : short[], $dest_offset : int, $source : short[], $source_offset : int, $length : int);
  native sub memmove_int : void ($dest : int[], $dest_offset : int, $source : int[], $source_offset : int, $length : int);
  native sub memmove_long : void ($dest : long[], $dest_offset : int, $source : long[], $source_offset : int, $length : int);
  native sub memmove_float : void ($dest : float[], $dest_offset : int, $source : float[], $source_offset : int, $length : int);
  native sub memmove_double : void ($dest : double[], $dest_offset : int, $source : double[], $source_offset : int, $length : int);

  native sub new_array_proto : oarray ($proto_array : oarray, $length : int);

  sub sort_byte : void ($nums : byte[], $offset : int, $length : int, $comparator : SPVM::Comparator::Byte) {
    if ($nums == undef) {
      die "Array must be not undef";
    }
    
    my $nums_length = @$nums;
    
    if ($offset < 0) {
      die "Offset must be more than or equals to 0";
    }
    
    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }
    
    if ($offset + $length > $nums_length) {
      die "Offset + Length must be in the array range";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = new byte[$length];
    _sort_byte_merge_sort($nums, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  private sub _sort_byte_merge : void($a : byte[], $b : byte[], $left : int, $mid : int, $right : int, $n : int, $comparator : SPVM::Comparator::Byte) {
    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 sub _sort_byte_merge_sort : void($a : byte[], $b : byte[], $left : int, $right : int, $n : int, $comparator : SPVM::Comparator::Byte){
    if ($left >= $right) {
      return;
    }

    my $mid = ($left + $right) / 2;

    _sort_byte_merge_sort($a, $b, $left, $mid, $n, $comparator);
    _sort_byte_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    _sort_byte_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
  
  sub sort_short : void ($nums : short[], $offset : int, $length : int, $comparator : SPVM::Comparator::Short) {
    if ($nums == undef) {
      die "Array must be not undef";
    }
    
    my $nums_length = @$nums;
    
    if ($offset < 0) {
      die "Offset must be more than or equals to 0";
    }
    
    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }
    
    if ($offset + $length > $nums_length) {
      die "Offset + Length must be in the array range";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = new short[$length];
    _sort_short_merge_sort($nums, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  private sub _sort_short_merge : void($a : short[], $b : short[], $left : int, $mid : int, $right : int, $n : int, $comparator : SPVM::Comparator::Short) {
    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 sub _sort_short_merge_sort : void($a : short[], $b : short[], $left : int, $right : int, $n : int, $comparator : SPVM::Comparator::Short){
    if ($left >= $right) {
      return;
    }

    my $mid = ($left + $right) / 2;

    _sort_short_merge_sort($a, $b, $left, $mid, $n, $comparator);
    _sort_short_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    _sort_short_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
  
  sub sort_int : void ($nums : int[], $offset : int, $length : int, $comparator : SPVM::Comparator::Int) {
    if ($nums == undef) {
      die "Array must be not undef";
    }
    
    my $nums_length = @$nums;
    
    if ($offset < 0) {
      die "Offset must be more than or equals to 0";
    }
    
    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }
    
    if ($offset + $length > $nums_length) {
      die "Offset + Length must be in the array range";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = new int[$length];
    _sort_int_merge_sort($nums, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  private sub _sort_int_merge : void($a : int[], $b : int[], $left : int, $mid : int, $right : int, $n : int, $comparator : SPVM::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 sub _sort_int_merge_sort : void($a : int[], $b : int[], $left : int, $right : int, $n : int, $comparator : SPVM::Comparator::Int){
    if ($left >= $right) {
      return;
    }

    my $mid = ($left + $right) / 2;

    _sort_int_merge_sort($a, $b, $left, $mid, $n, $comparator);
    _sort_int_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    _sort_int_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
  
  sub sort_long : void ($nums : long[], $offset : int, $length : int, $comparator : SPVM::Comparator::Long) {
    if ($nums == undef) {
      die "Array must be not undef";
    }
    
    my $nums_length = @$nums;
    
    if ($offset < 0) {
      die "Offset must be more than or equals to 0";
    }
    
    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }
    
    if ($offset + $length > $nums_length) {
      die "Offset + Length must be in the array range";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = new long[$length];
    _sort_long_merge_sort($nums, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  private sub _sort_long_merge : void($a : long[], $b : long[], $left : int, $mid : int, $right : int, $n : int, $comparator : SPVM::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 sub _sort_long_merge_sort : void($a : long[], $b : long[], $left : int, $right : int, $n : int, $comparator : SPVM::Comparator::Long){
    if ($left >= $right) {
      return;
    }

    my $mid = ($left + $right) / 2;

    _sort_long_merge_sort($a, $b, $left, $mid, $n, $comparator);
    _sort_long_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    _sort_long_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
  
  sub sort_float : void ($nums : float[], $offset : int, $length : int, $comparator : SPVM::Comparator::Float) {
    if ($nums == undef) {
      die "Array must be not undef";
    }
    
    my $nums_length = @$nums;
    
    if ($offset < 0) {
      die "Offset must be more than or equals to 0";
    }
    
    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }
    
    if ($offset + $length > $nums_length) {
      die "Offset + Length must be in the array range";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = new float[$length];
    _sort_float_merge_sort($nums, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  private sub _sort_float_merge : void($a : float[], $b : float[], $left : int, $mid : int, $right : int, $n : int, $comparator : SPVM::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 sub _sort_float_merge_sort : void($a : float[], $b : float[], $left : int, $right : int, $n : int, $comparator : SPVM::Comparator::Float){
    if ($left >= $right) {
      return;
    }

    my $mid = ($left + $right) / 2;

    _sort_float_merge_sort($a, $b, $left, $mid, $n, $comparator);
    _sort_float_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    _sort_float_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
  
  sub sort_double : void ($nums : double[], $offset : int, $length : int, $comparator : SPVM::Comparator::Double) {
    if ($nums == undef) {
      die "Array must be not undef";
    }
    
    my $nums_length = @$nums;
    
    if ($offset < 0) {
      die "Offset must be more than or equals to 0";
    }
    
    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }
    
    if ($offset + $length > $nums_length) {
      die "Offset + Length must be in the array range";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = new double[$length];
    _sort_double_merge_sort($nums, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  private sub _sort_double_merge : void($a : double[], $b : double[], $left : int, $mid : int, $right : int, $n : int, $comparator : SPVM::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 sub _sort_double_merge_sort : void($a : double[], $b : double[], $left : int, $right : int, $n : int, $comparator : SPVM::Comparator::Double){
    if ($left >= $right) {
      return;
    }

    my $mid = ($left + $right) / 2;

    _sort_double_merge_sort($a, $b, $left, $mid, $n, $comparator);
    _sort_double_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    _sort_double_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }

  sub sort_string : void ($strings : string[], $offset : int, $length : int, $comparator : SPVM::Comparator::String) {
    if ($strings == undef) {
      die "Array must be not undef";
    }
    
    my $strings_length = @$strings;
    
    if ($offset < 0) {
      die "Offset must be more than or equals to 0";
    }
    
    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }
    
    if ($offset + $length > $strings_length) {
      die "Offset + Length must be in the array range";
    }
    
    my $b = new string[$length];
    _sort_string_merge_sort($strings, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }

  private sub _sort_string_merge : void($a : string[], $b : string[], $left : int, $mid : int, $right : int, $n : int, $comparator : SPVM::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 sub _sort_string_merge_sort : void($a : string[], $b : string[], $left : int, $right : int, $n : int, $comparator : SPVM::Comparator::String){
    if ($left >= $right) {
      return;
    }

    my $mid = ($left + $right) / 2;

    _sort_string_merge_sort($a, $b, $left, $mid, $n, $comparator);
    _sort_string_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    _sort_string_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }

  sub sort_object : void ($objects : oarray, $offset : int, $length : int, $comparator : SPVM::Comparator::Object) {
    if ($objects == undef) {
      die "Array must be not undef";
    }
    
    my $objects_length = @$objects;
    
    if ($offset < 0) {
      die "Offset must be more than or equals to 0";
    }
    
    if ($length < 0) {
      die "Length must be more than or equals to 0";
    }
    
    if ($offset + $length > $objects_length) {
      die "Offset + Length must be in the array range";
    }
    
    my $b = new_array_proto($objects, $length);
    
    _sort_object_merge_sort($objects, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }

  private sub _sort_object_merge : void($a : oarray, $b : oarray, $left : int, $mid : int, $right : int, $n : int, $comparator : SPVM::Comparator::Object) {
      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 sub _sort_object_merge_sort : void($a : oarray, $b : oarray, $left : int, $right : int, $n : int, $comparator : SPVM::Comparator::Object){
    if ($left >= $right) {
      return;
    }

    my $mid = ($left + $right) / 2;

    _sort_object_merge_sort($a, $b, $left, $mid, $n, $comparator);
    _sort_object_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    _sort_object_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
}