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

fn pub static with_capacity(amount: Int) -> Map[K, V] {
  let size = if amount <= 0 {
    DEFAULT_CAPACITY
  } else {
    amount.nearest_power_of_two
  }
  let slots = Array.filled(with: EMPTY, times: size)
  let resize_at = resize_threshold(size)

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

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

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

  iter.all?(fn (ours) {
    match other.entries_index(ours.key) {
      case EMPTY -> false
      case index -> other.entries.get(index).value == ours.value
    }
  })
}

fn pub capacity -> Int {
  @slots.size
}

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('{')

  iter.each_with_index(fn (index, entry) {
    if index > 0 { formatter.write(', ') }

    entry.key.fmt(formatter)
    formatter.write(': ')
    entry.value.fmt(formatter)
  })

  formatter.write('}')
}

fn pub get(index: ref K) -> ref V {
  match entries_index(index) {
    case EMPTY -> panic("The key doesn't exist")
    case index -> @entries.get(index).value
  }
}

fn pub mut get_mut(index: ref K) -> mut V {
  match entries_index(index) {
    case EMPTY -> panic("The key doesn't exist")
    case index -> @entries.get_mut(index).value
  }
}

fn pub hash[H: mut + Hasher](hasher: mut H) {
  iter.each(fn (entry) {
    entry.key.hash(hasher)
    entry.value.hash(hasher)
  })
}

fn pub move into_iter -> IntoIter[Entry[K, V]] {
  @entries.into_iter
}

fn pub iter -> Stream[ref Entry[K, V]] {
  @entries.iter
}

fn pub mut iter_mut -> Stream[mut Entry[K, V]] {
  @entries.iter_mut
}

fn pub keys -> Stream[ref K] {
  iter.map(fn (e) { e.key })
}

fn pub mut merge(other: Map[K, V]) {
  other.into_iter.each(fn (entry) {
    entry.distance = 0
    entry.hash = hash_key(entry.key)

    insert_entry(entry)
  })
}

fn pub opt(key: ref K) -> Option[ref V] {
  match entries_index(key) {
    case EMPTY -> Option.None
    case index -> Option.Some(@entries.get(index).value)
  }
}

fn pub mut opt_mut(key: ref K) -> Option[mut V] {
  match entries_index(key) {
    case EMPTY -> Option.None
    case index -> Option.Some(@entries.get_mut(index).value)
  }
}

fn pub mut remove(key: ref K) -> Option[V] {
  let mut slot = slot_index(hash_key(key))
  let mut dist = 0
  let mut index = @slots.get(slot)

  # For the removal we need both the slot and the entry index, so we have to
  # duplicate the logic of `entries_index()` here, as this is the only place
  # we need both.
  loop {
    if index == EMPTY { return Option.None }

    let entry = @entries.get(index)

    if dist > entry.distance { return Option.None }

    if entry.key == key { break }

    slot = slot_index(slot + 1)
    index = @slots.get(slot)
    dist += 1
  }

  let value = @entries.remove_at(index).into_value

  @slots.set(slot, EMPTY)

  # Because we shifted the entries to the left, any slots pointing to entries
  # _after_ the removed value have to be updated accordingly.
  @slots.iter.each_with_index(fn (slot, entry) {
    if entry > index { @slots.set(slot, entry - 1) }
  })

  let mut prev_slot = slot

  slot = slot_index(slot + 1)

  loop {
    let mut index = @slots.get(slot)

    if index == EMPTY { break }

    let entry = @entries.get_mut(index)

    if entry.distance > 0 {
      @slots.set(slot, EMPTY)
      @slots.set(prev_slot, index)

      entry.distance -= 1
    } else {
      break
    }

    prev_slot = slot
    slot = slot_index(slot + 1)
  }

  Option.Some(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, distance: 0)

  insert_entry(entry)
}

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

fn pub values -> Stream[ref V] {
  iter.map(fn (e) { e.value })
}

fn pub mut values_mut -> Stream[mut V] {
  iter_mut.map(fn (e) { e.value })
}