<commit_before>primitive _MapEmpty
primitive _MapDeleted

type Map[K: (Hashable box & Comparable[K] box), V] is HashMap[K, V, HashEq[K]]
  """
  This is a map that uses structural equality on the key.
  """

type MapIs[K, V] is HashMap[K, V, HashIs[K]]
  """
  This is a map that uses identity comparison on the key.
  """

class HashMap[K, V, H: HashFunction[K] val]
  """
  A quadratic probing hash map. Resize occurs at a load factor of 0.75. A
  resized map has 2 times the space. The hash function can be plugged in to the
  type to create different kinds of maps.
  """
  var _size: U64 = 0
  var _array: Array[((K, V) | _MapEmpty | _MapDeleted)]

  new create(prealloc: U64 = 6) =>
    """
    Create an array with space for prealloc elements without triggering a
    resize. Defaults to 6.
    """
    let len = (prealloc * 4) / 3
    let n = len.next_pow2().max(8)
    _array = _array.create(n)

    for i in Range(0, n) do
      _array.push(_MapEmpty)
    end

  fun size(): U64 =>
    """
    The number of items in the map.
    """
    _size

  fun space(): U64 =>
    """
    The available space in the map. Resize will happen when
    size / space >= 0.75.
    """
    _array.space()

  fun apply(key: box->K!): this->V ? =>
    """
    Gets a value from the map. Raises an error if no such item exists.
    """
    (let i, let found) = _search(key)

    if found then
      _array(i) as (_, this->V)
    else
      error
    end

  fun ref update(key: K, value: V): (V^ | None) =>
    """
    Sets a value in the map. Returns the old value if there was one, otherwise
    returns None. If there was no previous value, this may trigger a resize.
    """
    try
      (let i, _) = _search(key)

      match _array(i) = (consume key, consume value)
      | (_, let v: V) =>
        return consume v
      else
        _size = _size + 1

        if (_size * 4) > (_array.size() * 3) then
          _resize(_array.size() * 2)
        end
      end
    end
    None

  fun ref insert(key: K, value: V): V ? =>
    """
    Set a value in the map. Returns the new value, allowing reuse.
    """
    try
      (let i, let found) = _search(key)
      _array(i) = (consume key, consume value)

      if not found then
        _size = _size + 1

        if (_size * 4) > (_array.size() * 3) then
          _resize(_array.size() * 2)
        end
      end

      _array(i) as (_, V)
    else
      // This is unreachable, since index will never be out-of-bounds.
      error
    end

  fun ref remove(key: box->K!): (K^, V^) ? =>
    """
    Delete a value from the map and return it. Raises an error if there was no
    value for the given key.
    """
    try
      (let i, let found) = _search(key)

      if found then
        _size = _size - 1

        match _array(i) = _MapDeleted
        | (let k: K, let v: V) =>
          return (consume k, consume v)
        end
      end
    end
    error

  fun ref concat(iter: Iterator[(K^, V^)]) =>
    """
    Add K, V pairs from the iterator to the map.
    """
    for (k, v) in iter do
      this(consume k) = consume v
    end

  fun add[H2: HashFunction[this->K!] val = H](key: this->K!, value: this->V!):
    HashMap[this->K!, this->V!, H2]^
  =>
    """
    This with the new (key, value) mapping.
    """
    let r = clone[H2]()
    r(key) = value
    r

  fun sub[H2: HashFunction[this->K!] val = H](key: this->K!, value: this->V!):
    HashMap[this->K!, this->V!, H2]^
  =>
    """
    This without the given key.
    """
    let r = clone[H2]()
    try r.remove(key) end
    r

  fun next_index(prev: U64 = -1): U64 ? =>
    """
    Given an index, return the next index that has a populated key and value.
    Raise an error if there is no next populated index.
    """
    for i in Range(prev + 1, _array.size()) do
      match _array(i)
      | (_, _) => return i
      end
    end
    error

  fun index(i: U64): (this->K, this->V) ? =>
    """
    Returns the key and value at a given index.
    Raise an error if the index is not populated.
    """
    _array(i) as (this->K, this->V)

  fun ref compact(): HashMap[K, V, H]^ =>
    """
    Minimise the memory used for the map.
    """
    _resize(((_size * 4) / 3).next_pow2().max(8))
    this

  fun clone[H2: HashFunction[this->K!] val = H]():
    HashMap[this->K!, this->V!, H2]^
  =>
    """
    Create a clone. The key and value types may be different due to aliasing
    and viewpoint adaptation.
    """
    let r = HashMap[this->K!, this->V!, H2](_size)

    for (k, v) in pairs() do
      r(k) = v
    end
    r

  fun ref clear(): HashMap[K, V, H]^ =>
    """
    Remove all entries.
    """
    _size = 0
    _array = _array.create()
    this<commit_msg>Fix Map.clear() bug<commit_after>primitive _MapEmpty
primitive _MapDeleted

type Map[K: (Hashable box & Comparable[K] box), V] is HashMap[K, V, HashEq[K]]
  """
  This is a map that uses structural equality on the key.
  """

type MapIs[K, V] is HashMap[K, V, HashIs[K]]
  """
  This is a map that uses identity comparison on the key.
  """

class HashMap[K, V, H: HashFunction[K] val]
  """
  A quadratic probing hash map. Resize occurs at a load factor of 0.75. A
  resized map has 2 times the space. The hash function can be plugged in to the
  type to create different kinds of maps.
  """
  var _size: U64 = 0
  var _array: Array[((K, V) | _MapEmpty | _MapDeleted)]

  new create(prealloc: U64 = 6) =>
    """
    Create an array with space for prealloc elements without triggering a
    resize. Defaults to 6.
    """
    let len = (prealloc * 4) / 3
    let n = len.next_pow2().max(8)
    _array = _array.create(n)

    for i in Range(0, n) do
      _array.push(_MapEmpty)
    end

  fun size(): U64 =>
    """
    The number of items in the map.
    """
    _size

  fun space(): U64 =>
    """
    The available space in the map. Resize will happen when
    size / space >= 0.75.
    """
    _array.space()

  fun apply(key: box->K!): this->V ? =>
    """
    Gets a value from the map. Raises an error if no such item exists.
    """
    (let i, let found) = _search(key)

    if found then
      _array(i) as (_, this->V)
    else
      error
    end

  fun ref update(key: K, value: V): (V^ | None) =>
    """
    Sets a value in the map. Returns the old value if there was one, otherwise
    returns None. If there was no previous value, this may trigger a resize.
    """
    try
      (let i, _) = _search(key)

      match _array(i) = (consume key, consume value)
      | (_, let v: V) =>
        return consume v
      else
        _size = _size + 1

        if (_size * 4) > (_array.size() * 3) then
          _resize(_array.size() * 2)
        end
      end
    end
    None

  fun ref insert(key: K, value: V): V ? =>
    """
    Set a value in the map. Returns the new value, allowing reuse.
    """
    try
      (let i, let found) = _search(key)
      _array(i) = (consume key, consume value)

      if not found then
        _size = _size + 1

        if (_size * 4) > (_array.size() * 3) then
          _resize(_array.size() * 2)
        end
      end

      _array(i) as (_, V)
    else
      // This is unreachable, since index will never be out-of-bounds.
      error
    end

  fun ref remove(key: box->K!): (K^, V^) ? =>
    """
    Delete a value from the map and return it. Raises an error if there was no
    value for the given key.
    """
    try
      (let i, let found) = _search(key)

      if found then
        _size = _size - 1

        match _array(i) = _MapDeleted
        | (let k: K, let v: V) =>
          return (consume k, consume v)
        end
      end
    end
    error

  fun ref concat(iter: Iterator[(K^, V^)]) =>
    """
    Add K, V pairs from the iterator to the map.
    """
    for (k, v) in iter do
      this(consume k) = consume v
    end

  fun add[H2: HashFunction[this->K!] val = H](key: this->K!, value: this->V!):
    HashMap[this->K!, this->V!, H2]^
  =>
    """
    This with the new (key, value) mapping.
    """
    let r = clone[H2]()
    r(key) = value
    r

  fun sub[H2: HashFunction[this->K!] val = H](key: this->K!, value: this->V!):
    HashMap[this->K!, this->V!, H2]^
  =>
    """
    This without the given key.
    """
    let r = clone[H2]()
    try r.remove(key) end
    r

  fun next_index(prev: U64 = -1): U64 ? =>
    """
    Given an index, return the next index that has a populated key and value.
    Raise an error if there is no next populated index.
    """
    for i in Range(prev + 1, _array.size()) do
      match _array(i)
      | (_, _) => return i
      end
    end
    error

  fun index(i: U64): (this->K, this->V) ? =>
    """
    Returns the key and value at a given index.
    Raise an error if the index is not populated.
    """
    _array(i) as (this->K, this->V)

  fun ref compact(): HashMap[K, V, H]^ =>
    """
    Minimise the memory used for the map.
    """
    _resize(((_size * 4) / 3).next_pow2().max(8))
    this

  fun clone[H2: HashFunction[this->K!] val = H]():
    HashMap[this->K!, this->V!, H2]^
  =>
    """
    Create a clone. The key and value types may be different due to aliasing
    and viewpoint adaptation.
    """
    let r = HashMap[this->K!, this->V!, H2](_size)

    for (k, v) in pairs() do
      r(k) = v
    end
    r

  fun ref clear(): HashMap[K, V, H]^ =>
    """
    Remove all entries.
    """
    _size = 0
    // Our default prealloc of 6 corresponds to an array alloc size of 8.
    let n: U64 = 8
    _array = _array.create(n)

    for i in Range(0, n) do
      _array.push(_MapEmpty)
    end
    this
{'fraction_non_alphanumeric': 0.13438155136268343, 'fraction_numerical': 0.011949685534591196, 'mean_word_length': 2.0757575757575757, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 91, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6485821', 'n_tokens_mistral': 3419, 'n_tokens_neox': 3257, 'n_words': 1216}