fn pub static new -> Map[K, V] {
  with_capacity(DEFAULT_CAPACITY)
}

fn pub static with_capacity(amount: Int) -> Map[K, V] {
  if amount <= 0 { invalid_capacity(amount) }

  let mut size = amount.nearest_power_of_two
  let mut resize_at = resize_threshold(size)

  # If the amount is greater than the resize threshold we'd still need a
  # resize, so in this case we double the capacity (due to it always being a
  # power of two).
  if resize_at < amount {
    size = (size * 2).nearest_power_of_two
    resize_at = resize_threshold(size)
  }

  if size > MAX_SIZE { map_too_large }

  let slots = Array.filled(with: Slot.empty, times: size)
  let entries = Array.with_capacity(amount)

  Map(slots: slots, entries: entries, resize_at: resize_at)
}

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

fn pub ==(other: ref Map[K, V]) -> Bool {
  if size != other.size { return false }

  for (k, v) in iter {
    match other.entries_index(k) {
      case EMPTY -> return false
      case idx if other.entries.get(idx).or_panic.value != v -> return false
      case _ -> {}
    }
  }

  true
}

fn pub capacity -> Int {
  @resize_at
}

fn pub mut clear {
  @slots = Array.filled(with: Slot.empty, times: @slots.size)
  @entries.clear
}

fn pub clone -> Map[K, V] {
  Map(slots: @slots.clone, entries: @entries.clone, resize_at: @resize_at)
}

fn pub contains?(value: ref K) -> Bool {
  entries_index(value) > EMPTY
}

fn pub fmt(formatter: mut Formatter) {
  formatter.write('{')

  for (index, (k, v)) in iter.with_index {
    if index > 0 { formatter.write(', ') }

    k.fmt(formatter)
    formatter.write(': ')
    v.fmt(formatter)
  }

  formatter.write('}')
}

fn pub get(key: ref K) -> Result[ref V, MissingKey[K]] {
  match entries_index(key) {
    case EMPTY -> Result.Error(MissingKey.new(key))
    case index -> Result.Ok(@entries.get(index).or_panic.value)
  }
}

fn pub mut get_mut(key: ref K) -> Result[mut V, MissingKey[K]] {
  match entries_index(key) {
    case EMPTY -> Result.Error(MissingKey.new(key))
    case index -> Result.Ok(@entries.get_mut(index).or_panic.value)
  }
}

fn pub hash[H: mut + Hasher](hasher: mut H) {
  for (k, v) in iter {
    k.hash(hasher)
    v.hash(hasher)
  }
}

fn pub move into_iter -> Stream[(K, V)] {
  let iter = @entries.into_iter

  Stream(fn move {
    match iter.next {
      case Some({ @key = k, @value = v }) -> Option.Some((k, v))
      case _ -> Option.None
    }
  })
}

fn pub iter -> Stream[(ref K, ref V)] {
  let mut idx = 0

  Stream(fn move {
    match @entries.get(idx) {
      case Ok(e) -> {
        idx += 1
        Option.Some((e.key, e.value))
      }
      case _ -> Option.None
    }
  })
}

fn pub mut iter_mut -> Stream[(ref K, mut V)] {
  let mut idx = 0

  Stream(fn move {
    match @entries.get_mut(idx) {
      case Ok(e) -> {
        idx += 1
        Option.Some((e.key, e.value))
      }
      case _ -> Option.None
    }
  })
}

fn pub keys -> Stream[ref K] {
  let mut idx = 0

  Stream(fn move {
    match @entries.get(idx) {
      case Ok(e) -> {
        idx += 1
        Option.Some(e.key)
      }
      case _ -> Option.None
    }
  })
}

fn pub mut merge(other: Map[K, V]) {
  for (k, v) in other { set(k, v) }
}

fn pub mut remove(key: ref K) -> Result[V, MissingKey[K]] {
  let mut slot_idx = index_for(hash_key(key))
  let mut dist = 0
  let mut slot = @slots.get(slot_idx).or_panic

  loop {
    if slot.empty? or dist > slot.distance { throw MissingKey.new(key) }

    if @entries.get(slot.entry).or_panic.key == key { break }

    slot_idx = index_for(slot_idx + 1)
    slot = @slots.get(slot_idx).or_panic
    dist += 1
  }

  let value = @entries.remove_at(slot.entry).or_panic.into_value

  @slots.set(slot_idx, Slot.empty)

  # Because we shifted the entries to the left, any slots pointing to entries
  # _after_ the removed value have to be updated accordingly.
  #
  # We have to iterate over _all_ the slots because any slot can point to an
  # entry after the one that was removed.
  let mut shift_idx = 0

  while shift_idx < @slots.size {
    let shift = @slots.get(shift_idx).or_panic

    if shift.entry > slot.entry { @slots.set(shift_idx, shift.reduce_entry) }

    shift_idx += 1
  }

  let mut prev_slot = slot_idx

  slot_idx = index_for(slot_idx + 1)

  # Removing an entry means we migh be able to shift slots that were pushed to
  # the right (= its distance is increased) due to a collision.
  loop {
    let slot = @slots.get(slot_idx).or_panic

    if slot.empty? or slot.distance == 0 { break }

    @slots.set(slot_idx, Slot.empty)
    @slots.set(prev_slot, slot.reduce_distance)
    prev_slot = slot_idx
    slot_idx = index_for(slot_idx + 1)
  }

  Result.Ok(value)
}

fn pub mut set(key: K, value: V) -> Option[V] {
  if size >= @resize_at { resize }

  let hash = hash_key(key)
  let entry = Entry(key: key, value: value, hash: hash)

  insert_entry(entry)
}

fn pub size -> Int {
  @entries.size
}

fn pub values -> Stream[ref V] {
  let mut idx = 0

  Stream(fn move {
    match @entries.get(idx) {
      case Ok(e) -> {
        idx += 1
        Option.Some(e.value)
      }
      case _ -> Option.None
    }
  })
}

fn pub mut values_mut -> Stream[mut V] {
  let mut idx = 0

  Stream(fn move {
    match @entries.get_mut(idx) {
      case Ok(e) -> {
        idx += 1
        Option.Some(e.value)
      }
      case _ -> Option.None
    }
  })
}