class List : precompile {
  use Fn;
  
  has values   : object[];
  has capacity : int;
  has length   : ro int;

  private enum {
    DEFAULT_CAPACITY = 16,
  }
  static method new : List ($objects : object[]) {
    my $self = new List;
    
    my $length : int;
    if ($objects) {
      $length = @$objects;
    }
    else {
      $length = 0;
    }
    
    my $capacity = 0;
    if ($length < List->DEFAULT_CAPACITY()) {
      $capacity = List->DEFAULT_CAPACITY();
    }
    else {
      $capacity = $length;
    }
    $self->{capacity} = $capacity;
    
    if ($objects) {
      $self->{values} = Fn->new_array_proto($objects, $capacity);
    }
    else {
      $self->{values} = Fn->new_array_proto(new object[0], $capacity);
    }
    
    for (my $i = 0; $i < @$objects; ++$i) {
      $self->{values}[$i] = $objects->[$i];
    }
    $self->{length} = @$objects;

    return $self;
  }

  static method new_len : List ($proto_array : object[], $length : int) {
    unless ($proto_array) {
      die "First argument must not be undef";
    }
    
    my $self = new List;
    unless ($length >= 0) {
      die "length must be more than or equals to zero";
    }
    my $capacity = 0;
    if ($length < List->DEFAULT_CAPACITY()) {
      $capacity = List->DEFAULT_CAPACITY();
    }
    else {
      $capacity = $length;
    }
    $self->{capacity} = $capacity;
    $self->{length} = $length;
    $self->{values} = Fn->new_array_proto($proto_array, $capacity);
    return $self;
  }
  
  method insert : void ($index : int, $value : object) {
    my $length = $self->{length};
    my $capacity = $self->{capacity};
    
    unless ($index >= 0 && $index <= $length) {
      die "Out of range";
    }
    
    if ($length >= $capacity) {
      $self->_extend;
    }
    
    my $values = $self->{values};
    if ($index != $length) {
      for (my $i = $length - 1; $i >= $index; $i--) {
        $values->[$i + 1] = $values->[$i];
      }
    }
    $values->[$index] = $value;
    
    $self->{length}++;
  }

  method remove : object ($index : int) {
    my $length = $self->{length};
    my $capacity = $self->{capacity};
    
    unless ($index >= 0 && $index < $length) {
      die "Out of range";
    }
    
    my $values = $self->{values};
    my $remove_value = $values->[$index];

    for (my $i = $index; $i < $length - 1; $i++) {
      $values->[$i] = $values->[$i + 1];
    }
    $values->[$length - 1] = undef;
    
    $self->{length}--;
    
    return $remove_value;
  }

  method push : void ($value : object) {
    my $length = $self->{length};
    my $capacity = $self->{capacity};

    if ($length >= $capacity) {
      $self->_extend;
    }
    my $index = $self->{length};
    $self->{values}[$index] = $value;
    ++$self->{length};
  }
  
  method pop : object () {
    if ($self->{length} <= 0) {
      die "Length must be more than 0 for pop";
    }
    
    my $index = $self->{length};
    
    my $ret = $self->{values}[$index - 1];
    
    $self->{values}[$index - 1] = undef;
    
    --$self->{length};
    
    return $ret;
  }

  method unshift : void ($value : object) {
    my $length = $self->{length};
    my $capacity = $self->{capacity};
    
    if ($length >= $capacity) {
      $self->_extend;
    }
    
    my $values = $self->{values};
    
    for (my $i = 0; $i < $length; $i++) {
      $values->[$length - $i] = $values->[$length - $i - 1];
    }
    
    $values->[0] = $value;
    $self->{length}++;
  }

  method shift : object () {
    my $length = $self->{length};
    my $capacity = $self->{capacity};
    
    if ($length == 0) {
      die "Length must be more than 0 for shift";
    }
    
    my $values = $self->{values};
    
    my $value = $values->[0];
    
    for (my $i = 0; $i < $length - 1; $i++) {
      $values->[$i] = $values->[$i + 1];
    }
    $values->[$length - 1] = undef;
    
    $self->{length}--;
    
    return $value;
  }

  method set : void ($index : int, $value : object) {
    my $length = $self->length;

    if ($index < 0 || $index > $length - 1) {
      die "Out of range";
    }
    
    $self->{values}[$index] = $value;
  }

  method set_array : void ($array : object[]) {
    unless ($array) {
      die "Array must be defined";
    }
    
    my $cur_length = $self->length;
    
    my $set_length = @$array;
    
    unless ($set_length == $cur_length) {
      die "The length of argument array must be same as the length of current list array";
    }
    
    my $values = $self->{values};
    for (my $i = 0; $i < $cur_length; $i++) {
      $values->[$i] = $array->[$i];
    }
  }

  method get : object ($index : int) {
    my $length = $self->length;

    if ($index < 0 || $index > $length - 1) {
      die "Out of range";
    }
    
    return $self->{values}[$index];
  }

  private method _extend_with_capacity : void ($new_capacity : int) {
    my $new_values = Fn->new_array_proto($self->{values}, $new_capacity);
    for (my $i = 0; $i < $self->{length}; ++$i) {
      my $target = $i;
      if ($target < 0) { $target += $self->{capacity}; };
      $new_values->[$i] = $self->{values}[$target];
    }
    $self->{capacity} = $new_capacity;
    $self->{values} = $new_values;
  }

  private method _extend : void () {
    my $capacity = $self->{capacity};
    my $length = $self->{length};
    my $values = $self->{values};
    
    my $new_capacity = $capacity * 2;
    
    my $new_values = Fn->new_array_proto($self->{values}, $new_capacity);
    
    for (my $i = 0; $i < $length; $i++) {
      $new_values->[$i] = $values->[$i];
    }
    
    $self->{values} = $new_values;
    $self->{capacity} = $new_capacity;
  }
  
  method resize : void ($new_length : int) {
    if ($new_length < 0) {
      die "New length must be more than or equals to 0";
    }
    
    my $length = $self->{length};
    my $capacity = $self->{capacity};
    
    if ($new_length > $length) {
      if ($new_length > $capacity) {
        $self->_extend_with_capacity($new_length);
      }
    }
    elsif ($new_length < $length) {
      for (my $i = $new_length; $i < $length; $i++) {
        $self->{values}[$i] = undef;
      }
    }
    $self->{length} = $new_length;
  }
  
  method to_array : object[] () {
    my $length = $self->{length};
    my $objects = Fn->new_array_proto($self->{values}, $length);
    for (my $i = 0; $i < $length; $i++) {
      $objects->[$i] = $self->{values}[$i];
    }
    return $objects;
  }
}