// Copyright 2026 International Digital Economy Academy
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

///|
let default_init_capacity = 8

///|
fn[K, V] new_hashmap(capacity : Int) -> HashMap[K, V] {
  let capacity = capacity.next_power_of_two()
  {
    size: 0,
    capacity,
    entries: FixedArray::make(capacity, None),
    capacity_mask: capacity - 1,
  }
}

///|
fn capacity_for_length(length : Int) -> Int {
  (length * 2).next_power_of_two()
}

///|
/// Creates a new hash map from an array of key-value pairs. Pairs with duplicate
/// keys will keep the latest value, overwriting the previous ones.
/// The optional `capacity` is treated as a minimum initial capacity and will be
/// rounded up to the smallest power of 2 that can hold the requested capacity.
///
/// Parameters:
///
/// * `arr` : An array of key-value tuples. Each tuple contains a hashable and
/// comparable key of type `K`, and an associated value of type `V`.
///
/// Returns a new hash map containing all the key-value pairs from the input
/// array.
///
/// Example:
///
/// ```mbt check
/// test {
///   let arr : ReadOnlyArray[(Int, String)] = [(1, "one"), (2, "two"), (1, "ONE")]
///   let map = @hashmap.HashMap(arr)
///   debug_inspect(map.get(1), content="Some(\"ONE\")")
///   debug_inspect(map.get(2), content="Some(\"two\")")
/// }
/// ```
#alias(from_array)
#as_free_fn(from_array)
#alias(of, deprecated="Use from_array instead")
#as_free_fn(of, deprecated="Use from_array instead")
pub fn[K : Hash + Eq, V] HashMap::HashMap(
  arr : ArrayView[(K, V)],
  capacity? : Int,
) -> HashMap[K, V] {
  let length = arr.length()
  let capacity = match capacity {
    Some(capacity) => capacity.max(capacity_for_length(length))
    None =>
      if length == 0 {
        default_init_capacity
      } else {
        capacity_for_length(length)
      }
  }
  let m = new_hashmap(capacity)
  arr.each(e => m.set(e.0, e.1))
  m
}

///|
/// Sets a key-value pair into the hash map. If the key already exists, updates
/// its value. If the hash map is near full capacity (>= 50%), automatically
/// grows the internal storage to accommodate more entries.
///
/// Parameters:
///
/// * `map` : The hash map to modify.
/// * `key` : The key to insert or update. Must implement `Hash` and `Eq` traits.
/// * `value` : The value to associate with the key.
///
/// Example:
///
/// ```mbt check
/// test {
///   let map : @hashmap.HashMap[String, Int] = HashMap([])
///   map.set("key", 42)
///   debug_inspect(map.get("key"), content="Some(42)")
///   map.set("key", 24) // update existing key
///   debug_inspect(map.get("key"), content="Some(24)")
/// }
/// ```
#alias("_[_]=_")
#owned(value)
pub fn[K : Hash + Eq, V] HashMap::set(
  self : HashMap[K, V],
  key : K,
  value : V,
) -> Unit {
  self.set_with_hash(key, value, Hash::hash(key))
}

///|
#owned(value)
fn[K : Eq, V] HashMap::set_with_hash(
  self : HashMap[K, V],
  key : K,
  value : V,
  hash : Int,
) -> Unit {
  // Only grow when actually inserting a new entry, not when updating existing
  for psl = 0, idx = hash & self.capacity_mask {
    match self.entries[idx] {
      None => {
        // Need to insert new entry - check if grow is needed first
        if self.size >= self.capacity / 2 {
          self.grow()
          // Restart search with new capacity_mask
          continue 0, hash & self.capacity_mask
        }
        let entry = { psl, key, value, hash }
        self.entries[idx] = Some(entry)
        self.size += 1
        return
      }
      Some(curr_entry) => {
        if curr_entry.hash == hash && curr_entry.key == key {
          // Key exists - just update value, no grow needed
          curr_entry.value = value
          return
        }
        if psl > curr_entry.psl {
          // Need to insert and push away - check if grow is needed first
          if self.size >= self.capacity / 2 {
            self.grow()
            // Restart search with new capacity_mask
            continue 0, hash & self.capacity_mask
          }
          self.push_away(idx, curr_entry)
          let entry = { psl, key, value, hash }
          self.entries[idx] = Some(entry)
          self.size += 1
          return
        }
        continue psl + 1, (idx + 1) & self.capacity_mask
      }
    }
  }
}

///|
#owned(entry)
fn[K, V] HashMap::push_away(
  self : HashMap[K, V],
  idx : Int,
  entry : Entry[K, V],
) -> Unit {
  for psl = entry.psl + 1, idx = (idx + 1) & self.capacity_mask, entry = entry {
    match self.entries[idx] {
      None => {
        entry.psl = psl
        self.entries[idx] = Some(entry)
        break
      }
      Some(curr_entry) =>
        if psl > curr_entry.psl {
          entry.psl = psl
          self.entries[idx] = Some(entry)
          continue curr_entry.psl + 1,
            (idx + 1) & self.capacity_mask,
            curr_entry
        } else {
          continue psl + 1, (idx + 1) & self.capacity_mask, entry
        }
    }
  }
}

///|
/// Retrieves the value associated with a given key in the hash map.
///
/// Parameters:
///
/// * `self` : The hash map to search in.
/// * `key` : The key to look up in the map.
///
/// Returns `Some(value)` if the key exists in the map, `None` otherwise.
///
/// Example:
///
/// ```mbt check
/// test {
///   let map = @hashmap.from_array([("key", 42)])
///   debug_inspect(map.get("key"), content="Some(42)")
///   debug_inspect(map.get("nonexistent"), content="None")
/// }
/// ```
pub fn[K : Hash + Eq, V] HashMap::get(self : HashMap[K, V], key : K) -> V? {
  // self.get_with_hash(key, key.hash())
  let hash = Hash::hash(key)
  for i = 0, idx = hash & self.capacity_mask {
    guard self.entries[idx] is Some(entry) else { break None }
    if entry.hash == hash && entry.key == key {
      break Some(entry.value)
    }
    if i > entry.psl {
      break None
    }
    continue i + 1, (idx + 1) & self.capacity_mask
  }
}

///|
/// Retrieves the value associated with a `BytesView` key in a hash map with
/// `Bytes` keys.
///
/// This allows efficient lookups using a `BytesView` (e.g. a sub-slice of a
/// larger byte buffer) without allocating a fresh `Bytes`.
///
/// Returns `Some(value)` if a matching key exists in the map, `None` otherwise.
///
/// Example:
///
/// ```mbt check
/// test {
///   let map = @hashmap.from_array([(b"hello", 1), (b"world", 2)])
///   let bytes = b"prefix_hello_suffix"
///   let view = bytes[7:12] // view of "hello"
///   @debug.debug_inspect(map.get_from_bytes(view), content="Some(1)")
/// }
/// ```
pub fn[V] HashMap::get_from_bytes(
  self : HashMap[Bytes, V],
  key : BytesView,
) -> V? {
  let hash = Hash::hash(key)
  for i = 0, idx = hash & self.capacity_mask {
    guard self.entries[idx] is Some(entry) else { break None }
    if entry.hash == hash && key.equal_to_bytes(entry.key) {
      break Some(entry.value)
    }
    if i > entry.psl {
      break None
    }
    continue i + 1, (idx + 1) & self.capacity_mask
  }
}

///|
/// Retrieves the value associated with a `StringView` key in a hash map with
/// `String` keys.
///
/// This allows efficient lookups using a `StringView` (e.g. a substring of a
/// larger string) without allocating a fresh `String`.
///
/// Returns `Some(value)` if a matching key exists in the map, `None` otherwise.
///
/// Example:
///
/// ```mbt check
/// test {
///   let map = @hashmap.from_array([("hello", 1), ("world", 2)])
///   let str = "say hello to everyone"
///   let view = str.view(start_offset=4, end_offset=9) // view of "hello"
///   @debug.debug_inspect(map.get_from_string(view), content="Some(1)")
/// }
/// ```
pub fn[V] HashMap::get_from_string(
  self : HashMap[String, V],
  key : StringView,
) -> V? {
  let hash = Hash::hash(key)
  for i = 0, idx = hash & self.capacity_mask {
    guard self.entries[idx] is Some(entry) else { break None }
    if entry.hash == hash && key.equal_to_string(entry.key) {
      break Some(entry.value)
    }
    if i > entry.psl {
      break None
    }
    continue i + 1, (idx + 1) & self.capacity_mask
  }
}

///|
/// Retrieves the value associated with a given key in the hash map.
///
/// Parameters:
///
/// * `self` : The hash map to search in.
/// * `key` : The key to look up in the map.
///
/// Returns `value` if the key exists in the map, panic otherwise.
///
/// Example:
///
/// ```mbt check
/// test {
///   let map = @hashmap.from_array([("key", 42)])
///   inspect(map["key"], content="42")
/// }
/// ```
#alias("_[_]")
pub fn[K : Hash + Eq, V] HashMap::at(self : HashMap[K, V], key : K) -> V {
  let hash = Hash::hash(key)
  for i = 0, idx = hash & self.capacity_mask {
    guard! self.entries[idx] is Some(entry)
    if entry.hash == hash && entry.key == key {
      break entry.value
    }
    guard! i <= entry.psl
    continue i + 1, (idx + 1) & self.capacity_mask
  }
}

///|
/// Gets the value associated with the given key. If the key doesn't exist in the
/// map, initializes it with the result of calling the provided initialization
/// function.
///
/// Parameters:
///
/// * `self` : The hash map.
/// * `key` : The key to look up in the map.
/// * `init` : A function that takes no arguments and returns a value to be
/// associated with the key if it doesn't exist.
///
/// Returns the value associated with the key, either existing or newly
/// initialized.
///
/// Example:
///
/// ```mbt check
/// test {
///   let map : @hashmap.HashMap[String, Int] = HashMap([])
///   let value = map.get_or_init("key", () => 42)
///   inspect(value, content="42")
///   debug_inspect(map.get("key"), content="Some(42)")
/// }
/// ```
pub fn[K : Hash + Eq, V] HashMap::get_or_init(
  self : HashMap[K, V],
  key : K,
  init : () -> V,
) -> V {
  let hash = Hash::hash(key)
  let (idx, psl, new_value, push_away) = for psl = 0, idx = hash &
                                               self.capacity_mask {
    match self.entries[idx] {
      Some(entry) => {
        if entry.hash == hash && entry.key == key {
          return entry.value
        }
        if psl > entry.psl {
          let new_value = init()
          break (idx, psl, new_value, Some(entry))
        }
        continue psl + 1, (idx + 1) & self.capacity_mask
      }
      None => {
        let new_value = init()
        break (idx, psl, new_value, None)
      }
    }
  }
  if self.size >= self.capacity / 2 {
    // Slow path, we need to resize
    self.grow()
    self.set_with_hash(key, new_value, hash)
  } else {
    if push_away is Some(entry) {
      self.push_away(idx, entry)
    }
    let entry = { psl, hash, key, value: new_value }
    self.entries[idx] = Some(entry)
    self.size += 1
  }
  new_value
}

///|
/// Updates a value in the map based on the existing value.
///
/// This method allows you to conditionally update, insert, or remove a key-value pair
/// based on whether the key already exists in the map. The provided function `f` is
/// called with `Some(current_value)` if the key exists, or `None` if it doesn't.
///
/// Parameters:
///
/// * `self` : The map to update.
/// * `key` : The key to update.
/// * `f` : A function that takes the current value (wrapped in `Option`) and returns
///   the new value (wrapped in `Option`). Returning `None` will remove the key-value
///   pair from the map.
///
/// Behavior:
///
/// * If the key exists and `f` returns `Some(new_value)`, the value is updated.
/// * If the key exists and `f` returns `None`, the key-value pair is removed.
/// * If the key doesn't exist and `f` returns `Some(new_value)`, a new pair is inserted.
/// * If the key doesn't exist and `f` returns `None`, no operation is performed.
///
/// Example:
///
/// ```mbt check
/// test {
///   let map : @hashmap.HashMap[String, Int] = HashMap([("a", 1), ("b", 2)])
///
///   // Update existing value
///   map.update("a", fn(v) {
///     match v {
///       Some(x) => Some(x + 10)
///       None => Some(0)
///     }
///   })
///   debug_inspect(map.get("a"), content="Some(11)")
///
///   // Insert new value
///   map.update("c", fn(v) {
///     match v {
///       Some(x) => Some(x)
///       None => Some(3)
///     }
///   })
///   debug_inspect(map.get("c"), content="Some(3)")
///
///   // Remove existing value
///   map.update("b", fn(_) { None })
///   debug_inspect(map.get("b"), content="None")
/// }
/// ```
pub fn[K : Hash + Eq, V] HashMap::update(
  self : HashMap[K, V],
  key : K,
  f : (V?) -> V?,
) -> Unit {
  let hash = Hash::hash(key)
  let (idx, psl, new_value, push_away) = for psl = 0, idx = hash &
                                               self.capacity_mask {
    match self.entries[idx] {
      Some(entry) => {
        if entry.hash == hash && entry.key == key {
          if f(Some(entry.value)) is Some(new_value) {
            entry.value = new_value
          } else {
            self.shift_back(idx)
            self.size -= 1
          }
          return
        }
        if psl > entry.psl {
          guard f(None) is Some(new_value) else { return }
          break (idx, psl, new_value, Some(entry))
        }
        continue psl + 1, (idx + 1) & self.capacity_mask
      }
      None => {
        guard f(None) is Some(new_value) else { return }
        break (idx, psl, new_value, None)
      }
    }
  }
  if self.size >= self.capacity / 2 {
    self.grow()
    self.set_with_hash(key, new_value, hash)
  } else {
    if push_away is Some(entry) {
      self.push_away(idx, entry)
    }
    self.entries[idx] = Some({ psl, hash, key, value: new_value })
    self.size += 1
  }
}

///|
/// Inserts `default` for `key` if it is absent, otherwise replaces the existing
/// value with `f(existing)`. The pairing of an eager `default` value with a
/// modifier function lets the canonical counter pattern read literally:
///
/// ```mbt check
/// test {
///   let counts : @hashmap.HashMap[String, Int] = HashMap([])
///   counts.update_or_default("a", 1, x => x + 1)
///   counts.update_or_default("a", 1, x => x + 1)
///   counts.update_or_default("b", 1, x => x + 1)
///   debug_inspect(counts.get("a"), content="Some(2)")
///   debug_inspect(counts.get("b"), content="Some(1)")
/// }
/// ```
///
/// Note: `f` is *not* applied to `default` on first insertion — `default` is
/// the value stored when the key is absent. This mirrors Java's `Map.merge`
/// and Rust's `Entry::and_modify(f).or_insert(default)`.
pub fn[K : Hash + Eq, V] HashMap::update_or_default(
  self : HashMap[K, V],
  key : K,
  default : V,
  f : (V) -> V,
) -> Unit {
  let hash = Hash::hash(key)
  let (idx, psl, push_away) = for psl = 0, idx = hash & self.capacity_mask {
    match self.entries[idx] {
      Some(entry) => {
        if entry.hash == hash && entry.key == key {
          entry.value = f(entry.value)
          return
        }
        if psl > entry.psl {
          break (idx, psl, Some(entry))
        }
        continue psl + 1, (idx + 1) & self.capacity_mask
      }
      None => break (idx, psl, None)
    }
  }
  if self.size >= self.capacity / 2 {
    self.grow()
    self.set_with_hash(key, default, hash)
  } else {
    if push_away is Some(entry) {
      self.push_away(idx, entry)
    }
    let entry = { psl, hash, key, value: default }
    self.entries[idx] = Some(entry)
    self.size += 1
  }
}

///|
/// Gets the value associated with a given key from the hash map. If the key
/// doesn't exist, returns the provided default value instead.
///
/// Parameters:
///
/// * `map` : The hash map to retrieve the value from.
/// * `key` : The key to look up in the map.
/// * `default` : The value to return if the key is not found in the map.
///
/// Returns the value associated with the key if it exists, otherwise returns the
/// default value.
///
/// Example:
///
/// ```mbt check
/// test {
///   let map = @hashmap.from_array([("a", 1), ("b", 2)])
///   inspect(map.get_or_default("a", 0), content="1")
///   inspect(map.get_or_default("c", 0), content="0")
/// }
/// ```
pub fn[K : Hash + Eq, V] HashMap::get_or_default(
  self : HashMap[K, V],
  key : K,
  default : V,
) -> V {
  let hash = Hash::hash(key)
  for i = 0, idx = hash & self.capacity_mask {
    guard self.entries[idx] is Some(entry) else { break default }
    if entry.hash == hash && entry.key == key {
      break entry.value
    }
    if i > entry.psl {
      break default
    }
    continue i + 1, (idx + 1) & self.capacity_mask
  }
}

///|
/// Checks if a key exists in the hash map.
///
/// Parameters:
///
/// * `self` : The hash map to search in.
/// * `key` : The key to look for in the hash map.
///
/// Returns `true` if the key exists in the hash map, `false` otherwise.
///
/// Example:
///
/// ```mbt check
/// test {
///   let map = @hashmap.from_array([("a", 1), ("b", 2)])
///   inspect(map.contains("a"), content="true")
///   inspect(map.contains("c"), content="false")
/// }
/// ```
pub fn[K : Hash + Eq, V] HashMap::contains(
  self : HashMap[K, V],
  key : K,
) -> Bool {
  let hash = Hash::hash(key)
  for i = 0, idx = hash & self.capacity_mask {
    guard self.entries[idx] is Some(entry) else { return false }
    if entry.hash == hash && entry.key == key {
      return true
    }
    if i > entry.psl {
      return false
    }
    continue i + 1, (idx + 1) & self.capacity_mask
  }
}

///|
/// Checks if a map contains a specific key-value pair.
///
/// Parameters:
///
/// * `map` : A map of type `@hashmap.HashMap[K, V]` to search in.
/// * `key` : The key to look up in the map.
/// * `value` : The value to be compared with the value associated with the key.
///
/// Returns `true` if the map contains the specified key and its associated value
/// equals the given value, `false` otherwise.
///
/// Example:
///
/// ```mbt check
/// test {
///   let map = @hashmap.HashMap([])
///   map.set("a", 1)
///   map.set("b", 2)
///   inspect(map.contains_kv("a", 1), content="true")
///   inspect(map.contains_kv("a", 2), content="false")
///   inspect(map.contains_kv("c", 3), content="false")
/// }
/// ```
pub fn[K : Hash + Eq, V : Eq] HashMap::contains_kv(
  self : HashMap[K, V],
  key : K,
  value : V,
) -> Bool {
  let hash = Hash::hash(key)
  for i = 0, idx = hash & self.capacity_mask {
    guard self.entries[idx] is Some(entry) else { return false }
    if entry.hash == hash && entry.key == key && entry.value == value {
      return true
    }
    if i > entry.psl {
      return false
    }
    continue i + 1, (idx + 1) & self.capacity_mask
  }
}

///|
/// Removes the entry for the specified key from the hash map. If the key exists
/// in the map, removes its entry and adjusts the probe sequence length (PSL) of
/// subsequent entries to maintain the Robin Hood hashing invariant. If the key
/// does not exist, the map remains unchanged.
///
/// Parameters:
///
/// * `self` : The hash map to remove the entry from.
/// * `key` : The key to remove from the map.
///
/// Example:
///
/// ```mbt check
/// test {
///   let map = @hashmap.from_array([("a", 1), ("b", 2)])
///   map.remove("a")
///   debug_inspect(map.get("a"), content="None")
///   inspect(map.length(), content="1")
/// }
/// ```
pub fn[K : Hash + Eq, V] HashMap::remove(self : HashMap[K, V], key : K) -> Unit {
  self.remove_with_hash(key, Hash::hash(key))
}

///|
fn[K : Eq, V] HashMap::remove_with_hash(
  self : HashMap[K, V],
  key : K,
  hash : Int,
) -> Unit {
  for i = 0, idx = hash & self.capacity_mask {
    match self.entries[idx] {
      Some(entry) => {
        if entry.hash == hash && entry.key == key {
          self.shift_back(idx)
          self.size -= 1
          break
        }
        if i > entry.psl {
          break
        }
        continue i + 1, (idx + 1) & self.capacity_mask
      }
      None => break
    }
  }
}

///|
fn[K, V] HashMap::shift_back(self : HashMap[K, V], idx : Int) -> Unit {
  for cur = idx {
    let next = (cur + 1) & self.capacity_mask
    match self.entries[next] {
      None | Some({ psl: 0, .. }) => {
        self.entries[cur] = None
        break
      }
      Some(entry) => {
        entry.psl -= 1
        self.entries[cur] = Some(entry)
        continue next
      }
    }
  }
}

///|
fn[K, V] HashMap::grow(self : HashMap[K, V]) -> Unit {
  let old_entries = self.entries
  let new_capacity = self.capacity << 1
  self.entries = FixedArray::make(new_capacity, None)
  self.capacity = new_capacity
  self.capacity_mask = new_capacity - 1
  for entry in old_entries {
    if entry is Some(entry) {
      self.rehash_place_entry(entry)
    }
  }
}

///|
#owned(entry)
fn[K, V] HashMap::rehash_place_entry(
  self : HashMap[K, V],
  entry : Entry[K, V],
) -> Unit {
  let hash = entry.hash
  for psl = 0, idx = hash & self.capacity_mask {
    match self.entries[idx] {
      None => {
        entry.psl = psl
        self.entries[idx] = Some(entry)
        return
      }
      Some(curr) =>
        if psl > curr.psl {
          self.push_away(idx, curr)
          entry.psl = psl
          self.entries[idx] = Some(entry)
          return
        } else {
          continue psl + 1, (idx + 1) & self.capacity_mask
        }
    }
  }
}

///|
/// Creates a new hash map from a fixed array of key-value pairs.
///
/// Parameters:
///
/// * `pairs` : A fixed array of tuples, where each tuple contains a key of type
/// `K` and a value of type `V`. The key type must implement both `Eq` and `Hash`
/// traits.
///
/// Returns a new hash map containing all the key-value pairs from the input
/// array.
///

///|
test "of" {
  let m = from_array([(1, 2), (3, 4)])
  @debug.debug_inspect(m.get(1), content="Some(2)")
  @debug.debug_inspect(m.get(3), content="Some(4)")
}

///|
pub impl[K, V] Default for HashMap[K, V] with fn default() {
  new_hashmap(default_init_capacity)
}

///|
/// Applies a function to each key-value pair in the map and 
/// returns a new map with the results, using the original keys.
pub fn[K, V, V2] HashMap::map(
  self : HashMap[K, V],
  f : (K, V) -> V2,
) -> HashMap[K, V2] {
  let other = {
    capacity: self.capacity,
    entries: FixedArray::make(self.capacity, None),
    size: self.size,
    capacity_mask: self.capacity_mask,
  }
  if self.size == 0 {
    return other
  }
  for i in 0.. HashMap[K, V] {
  let other = {
    capacity: self.capacity,
    entries: FixedArray::make(self.capacity, None),
    size: self.size,
    capacity_mask: self.capacity_mask,
  }
  if self.size == 0 {
    return other
  }
  for i in 0.. HashMap[K, V] {
  let result = self.copy()
  result.merge_in_place(other)
  result
}

///|
/// Merges another map into this map in-place. Updates the current map by adding
/// all key-value pairs from `other`. When both maps contain the same key, the
/// value from `other` overwrites the value in this map.
///
/// This is a mutating operation - it modifies the receiver map.
///
/// Parameters:
///
/// * `self` : The map to be modified.
/// * `other` : The map whose entries will be added to `self`.
///
/// Example:
///
/// ```mbt check
/// test {
///   let map1 = @hashmap.from_array([("a", 1), ("b", 2)])
///   let map2 = @hashmap.from_array([("b", 3), ("c", 4)])
///   map1.merge_in_place(map2)
///   let merged = map1.to_array()
///   merged.sort()
///   @json.json_inspect(merged, content=[["a", 1], ["b", 3], ["c", 4]])
/// }
/// ```
pub fn[K : Eq, V] HashMap::merge_in_place(
  self : HashMap[K, V],
  other : HashMap[K, V],
) -> Unit {
  if physical_equal(self, other) {
    return
  }
  for entry in other.entries {
    if entry is Some({ key, value, hash, .. }) {
      self.set_with_hash(key, value, hash)
    }
  }
}

///|
priv struct MyString(String) derive(Eq, @debug.Debug)

///|
#coverage.skip
impl Hash for MyString with fn hash(self) {
  let MyString(self) = self
  self.length()
}

///|
#coverage.skip
impl Hash for MyString with fn hash_combine(self, hasher) {
  hasher.combine_string(self.0)
}

///|
test "set" {
  let m : HashMap[MyString, Int] = new_hashmap(default_init_capacity)
  m.set("a", 1)
  m.set("b", 1)
  m.set("bc", 2)
  m.set("abc", 3)
  m.set("cd", 2)
  m.set("c", 1)
  m.set("d", 1)
  inspect(m.length(), content="7")
  // inspect(
  //   m._debug_entries(),
  //   content="_,(0,a,1),(1,b,1),(2,c,1),(3,d,1),(3,bc,2),(4,cd,2),(4,abc,3),_,_,_,_,_,_,_,_",
  // )
}

///|
test "remove" {
  let m : HashMap[MyString, Int] = new_hashmap(default_init_capacity)
  m.set("a", 1)
  m.set("ab", 2)
  m.set("bc", 2)
  m.set("cd", 2)
  m.set("abc", 3)
  m.set("abcdef", 6)
  m.remove("ab")
  inspect(m.length(), content="5")
  // inspect(
  //   m._debug_entries(),
  //   content="_,(0,a,1),(0,bc,2),(1,cd,2),(1,abc,3),_,(0,abcdef,6),_,_,_,_,_,_,_,_,_",
  // )
}

///|
test "remove_unexist_key" {
  let m : HashMap[MyString, Int] = new_hashmap(default_init_capacity)
  m.set("a", 1)
  m.set("ab", 2)
  m.set("abc", 3)
  m.remove("d")
  inspect(m.length(), content="3")
  // inspect(m._debug_entries(), content="_,(0,a,1),(0,ab,2),(0,abc,3),_,_,_,_")
}

///|
test "clear" {
  let m : HashMap[MyString, Int] = from_array([("a", 1), ("b", 2), ("c", 3)])
  m.clear()
  inspect(m.length(), content="0")
  inspect(m.capacity(), content="8")
  for entry in m.entries {
    @test.assert_same_object(entry, None)
  }
}

///|
test "grow" {
  let m : HashMap[MyString, Int] = new_hashmap(default_init_capacity)
  m.set("C", 1)
  m.set("Go", 2)
  m.set("C++", 3)
  m.set("Java", 4)
  m.set("Scala", 5)
  m.set("Julia", 5)
  inspect(m.length(), content="6")
  inspect(m.capacity(), content="16")
  m.set("Cobol", 5)
  inspect(m.length(), content="7")
  inspect(m.capacity(), content="16")
  m.set("Python", 6)
  m.set("Haskell", 7)
  m.set("Rescript", 8)
  inspect(m.length(), content="10")
  inspect(m.capacity(), content="32")
  @debug.debug_inspect(m.get("C"), content="Some(1)")
  @debug.debug_inspect(m.get("Go"), content="Some(2)")
  @debug.debug_inspect(m.get("C++"), content="Some(3)")
  @debug.debug_inspect(m.get("Java"), content="Some(4)")
  @debug.debug_inspect(m.get("Scala"), content="Some(5)")
  @debug.debug_inspect(m.get("Julia"), content="Some(5)")
  @debug.debug_inspect(m.get("Cobol"), content="Some(5)")
  @debug.debug_inspect(m.get("Python"), content="Some(6)")
  @debug.debug_inspect(m.get("Haskell"), content="Some(7)")
  @debug.debug_inspect(m.get("Rescript"), content="Some(8)")
  // Only for debugging
  // inspect(
  //   m._debug_entries(),
  //   content="_,(0,C,1),(0,Go,2),(0,C++,3),(0,Java,4),(0,Scala,5),(1,Julia,5),(2,Cobol,5),(2,Python,6),(2,Haskell,7),(2,Rescript,8),_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_",
  // )
}

///|
test "_[_]" {
  let m : HashMap[MyString, Int] = new_hashmap(default_init_capacity)
  m.set("a", 1)
  m.set("b", 1)
  m.set("cc", 2)
  inspect(m["a"], content="1")
  inspect(m["b"], content="1")
  inspect(m["cc"], content="2")
  // inspect(m._debug_entries(), content="_,(0,a,1),(1,b,1),(1,cc,2),_,_,_,_")
}

///|
test "get_or_init" {
  let m : HashMap[MyString, Int] = new_hashmap(default_init_capacity)
  inspect(m.get_or_init("a", () => 1), content="1")
  @debug.debug_inspect(m.get("a"), content="Some(1)")
  inspect(m.get_or_init("a", () => 2), content="1")
  @debug.debug_inspect(m.get("a"), content="Some(1)")
}