fn pub static filled[V: Clone](with: move V, times: Int) -> Array[move V] {
  if times == 0 { return [] }

  let array = with_capacity(times)
  let temp = ref with

  (times - 1).times(fn (_) { array.push(temp.clone) })
  array.push(with)
  array
}

fn pub static with_capacity(size: Int) -> Array[T] {
  if size < 0 { invalid_capacity(size) }

  Array(size: 0, capacity: size, buffer: alloc.resize(0 as Pointer[T], size))
}

fn pub !=(other: ref Self) -> Bool {
  (self == other).false?
}

fn pub ==(other: ref Array[T]) -> Bool {
  if @size != other.size { return false }

  let mut index = 0
  let max = @size

  while index < max {
    let ours = get(index)
    let theirs = other.get(index)

    if ours != theirs { return false }

    index += 1
  }

  true
}

fn pub mut append(other: Array[T]) {
  let len = other.size

  if len == 0 { return }

  reserve_exact(len)

  let tail = ptr.add(@buffer, @size)

  alloc.copy(other.pointer, tail, len)
  @size += len

  # This is necessary such that when `other` is dropped, we don't drop the
  # values that have been moved into `self`.
  other.size = 0
}

fn pub capacity -> Int {
  @capacity
}

fn pub mut clear {
  let mut index = 0
  let max = @size

  while index < max { read_from(index := index + 1) }

  @size = 0
}

fn pub clone -> Array[move T] {
  let len = @size
  let new = Array.with_capacity(len)
  let mut index = 0

  while index < len { new.push(get_unchecked(index := index + 1).clone) }

  new
}

fn pub contains?(value: ref T) -> Bool {
  iter.any?(fn (ours) { ours == value })
}

fn pub empty? -> Bool {
  @size == 0
}

fn pub fmt(formatter: mut Formatter) {
  let fmt = formatter.array

  for value in iter { fmt.value(value) }

  fmt.finish
}

fn pub inline get(index: Int) -> Result[ref T, OutOfBounds] {
  try check_bounds(index, @size)
  Result.Ok(get_unchecked(index))
}

fn pub inline mut get_mut(index: Int) -> Result[mut T, OutOfBounds] {
  try check_bounds(index, @size)
  Result.Ok(get_unchecked_mut(index))
}

fn pub hash[H: mut + Hasher](hasher: mut H) {
  let mut index = 0
  let len = @size

  while index < len { get_unchecked(index := index + 1).hash(hasher) }
}

fn pub index_of(value: ref T) -> Option[Int] {
  let mut idx = 0

  while idx < @size {
    if get_unchecked(idx) == value { return Option.Some(idx) }

    idx += 1
  }

  Option.None
}

fn pub mut insert(index: Int, value: T) {
  if index < 0 or index > @size {
    panic(OutOfBounds.new(index, @size).to_string)
  }

  reserve(1)

  # Shift to the right if the insertion isn't at the end of the array. If we
  # have values like this:
  #
  #     [A, B, C, D]
  #
  # And we want to insert at the index of B (index 1), this results in the
  # following values:
  #
  #     [A, B, B, C, D]
  #
  # We can then overwrite index 1 with the value to insert.
  if index < @size {
    let from = address_of(index)
    let to = address_of(index + 1)

    alloc.copy(from, to, size: @size - index)
  }

  write_to(index, value)
  @size += 1
}

fn pub move into_iter -> IntoIter[T] {
  IntoIter(array: self, index: 0)
}

fn pub iter -> Stream[ref T] {
  let mut idx = 0

  Stream.new(fn move {
    if idx < @size {
      Option.Some(get_unchecked(idx := idx + 1))
    } else {
      Option.None
    }
  })
}

fn pub mut iter_mut -> Stream[mut T] {
  let mut idx = 0

  Stream.new(fn move {
    if idx < @size {
      Option.Some(get_unchecked_mut(idx := idx + 1))
    } else {
      Option.None
    }
  })
}

fn pub last -> Option[ref T] {
  get(size - 1).ok
}

fn pub mut last_mut -> Option[mut T] {
  get_mut(size - 1).ok
}

fn pub mut pop -> Option[T] {
  if @size == 0 { return Option.None }

  @size -= 1
  Option.Some(read_from(@size))
}

fn pub mut push(value: T) {
  reserve(1)
  write_to(@size, value)
  @size += 1
}

fn pub mut remove_at(index: Int) -> Result[T, OutOfBounds] {
  let len = size

  try check_bounds(index, len)

  let addr = address_of(index)
  let val = addr.0

  alloc.copy(from: ptr.add(addr, 1), to: addr, size: len - index - 1)
  @size = len - 1
  Result.Ok(val)
}

fn pub mut remove_if(condition: fn (ref T) -> Bool) {
  let mut idx = 0

  while idx < @size {
    if condition.call(get_unchecked(idx)) {
      let addr = address_of(idx)

      drop_value(addr.0)
      alloc.copy(from: ptr.add(addr, 1), to: addr, size: @size - idx - 1)
      @size -= 1

      # Because we shift to the left, we need to visit the current index
      # again, otherwise we'd miss the value that came after it _before_ the
      # shift.
    } else {
      idx += 1
    }
  }
}

fn pub mut reserve(size: Int) {
  if @capacity - @size >= size { return }

  @capacity = max(@capacity * 2, @capacity + size)
  @buffer = alloc.resize(@buffer, @capacity)
}

fn pub mut reserve_exact(size: Int) {
  if @capacity - @size >= size { return }

  @capacity = @capacity + size
  @buffer = alloc.resize(@buffer, @capacity)
}

fn pub mut reverse {
  let mut a = 0
  let mut b = @size - 1

  while a < b {
    let a_val = read_from(a)
    let b_val = read_from(b)

    write_to(b, a_val)
    write_to(a, b_val)
    a += 1
    b -= 1
  }
}

fn pub reverse_iter -> Stream[ref T] {
  let mut index = size - 1

  Stream.new(fn move {
    if index > -1 { get(index := index - 1).ok } else { Option.None }
  })
}

fn pub mut set(index: Int, value: T) {
  check_bounds(index, @size).or_panic
  drop_value(read_from(index))
  write_to(index, value)
}

fn pub mut shuffle(rng: mut Random) {
  let mut swap = size - 1

  while swap > 0 {
    swap_indexes(swap, with: rng.int_between(min: 0, max: swap))
    swap -= 1
  }
}

fn pub size -> Int {
  @size
}

fn pub mut sort {
  stable_sort(self, fn (a, b) { a <= b })
}

fn pub mut sort_by(block: fn (ref T, ref T) -> Ordering) {
  stable_sort(self, fn (a, b) {
    match block.call(a, b) {
      case Less or Equal -> true
      case _ -> false
    }
  })
}

fn pub mut swap(index: Int, with: T) -> T {
  check_bounds(index, @size).or_panic

  let old = read_from(index)

  write_to(index, with)
  old
}

fn pub mut swap_indexes(index: Int, with: Int) {
  check_bounds(index, @size).or_panic
  check_bounds(with, @size).or_panic

  let a = read_from(index)
  let b = read_from(with)

  write_to(index, b)
  write_to(with, a)
}