fn pub static new -> Deque[T] {
  with_capacity(0)
}

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

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

fn pub capacity -> Int {
  @capacity
}

fn pub mut clear {
  while @size > 0 {
    read_from(@head := to_buffer_index(1))
    @size -= 1
  }

  @head = 0
}

fn pub get(index: Int) -> ref T {
  bounds_check(index, @size)
  get_unchecked(to_buffer_index(index))
}

fn pub mut get_mut(index: Int) -> mut T {
  bounds_check(index, @size)
  get_unchecked_mut(to_buffer_index(index))
}

fn pub move into_iter -> IntoIter[T] {
  IntoIter(indexes: indexes, deque: self)
}

fn pub iter -> Stream[ref T] {
  indexes.map(fn (i) { get_unchecked(i) })
}

fn pub mut iter_mut -> Stream[mut T] {
  indexes.map(fn (i) { get_unchecked_mut(i) })
}

fn pub opt(index: Int) -> Option[ref T] {
  if index < 0 or index >= @size { return Option.None }

  Option.Some(get_unchecked(to_buffer_index(index)))
}

fn pub mut opt_mut(index: Int) -> Option[mut T] {
  if index < 0 or index >= @size { return Option.None }

  Option.Some(get_unchecked_mut(to_buffer_index(index)))
}

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

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

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

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

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

fn pub mut push_front(value: T) {
  reserve(1)
  @head = @head.wrapping_sub(1).wrapping_add(@capacity) % @capacity
  @size += 1
  write_to(@head, value)
}

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

  let old_cap = @capacity

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

fn pub size -> Int {
  @size
}