// 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.

// Default initial capacity

///|
let default_init_capacity = 8

///|
fn[K] new_hashset(capacity : Int32) -> HashSet[K] {
  let capacity = capacity.next_power_of_two()
  {
    size: 0,
    capacity,
    capacity_mask: capacity - 1,
    grow_at: calc_grow_threshold(capacity),
    entries: FixedArray::make(capacity, None),
  }
}

///|
fn capacity_for_length(length : Int32) -> Int32 {
  let mut capacity = length.next_power_of_two()
  if length > calc_grow_threshold(capacity) {
    capacity *= 2
  }
  capacity
}

///|
/// Creates a hash set containing all elements from the given array.
/// 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.
#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] HashSet::HashSet(
  arr : ArrayView[K],
  capacity? : Int32,
) -> HashSet[K] {
  let length = arr.length()
  let capacity = match capacity {
    Some(capacity) | (None with capacity = default_init_capacity) =>
      capacity.max(capacity_for_length(length))
  }
  let m = new_hashset(capacity)
  arr.each(e => m.add(e))
  m
}

///|
/// Insert a key into hash set.
///
/// Parameters:
///
/// * `self` : The hash set to modify.
/// * `key` : The key to insert. Must implement `Hash` and `Eq` traits.
///
/// Example:
///
/// ```mbt check
/// test {
///   let set : @hashset.HashSet[String] = HashSet([])
///   set.add("key")
///   inspect(set.contains("key"), content="true")
///   set.add("key") // no effect since it already exists
///   inspect(set.length(), content="1")
/// }
/// ```
#alias(insert, deprecated)
pub fn[K : Hash + Eq] HashSet::add(self : HashSet[K], key : K) -> Unit {
  self.add_with_hash(key, Hash::hash(key))
}

///|
fn[K : Eq] HashSet::add_with_hash(
  self : HashSet[K],
  key : K,
  hash : Int32,
) -> Unit {
  if self.size >= self.grow_at {
    self.grow()
  }
  let (idx, psl) = for psl = 0, idx = hash & self.capacity_mask {
    // SAFETY: `idx` starts masked by `capacity_mask` and every step re-masks
    // it, so it is in bounds for `entries`, whose length is `capacity`.
    match self.entries.unsafe_get(idx) {
      None => break (idx, psl)
      Some(curr_entry) => {
        if curr_entry.hash == hash && curr_entry.key == key {
          return
        }
        if psl > curr_entry.psl {
          self.push_away(idx, curr_entry)
          break (idx, psl)
        }
        continue psl + 1, (idx + 1) & self.capacity_mask
      }
    }
  }
  let entry = { psl, key, hash, }
  self.set_entry(entry, idx)
  self.size += 1
}

///|
#owned(entry)
fn[K] HashSet::push_away(
  self : HashSet[K],
  idx : Int32,
  entry : Entry[K],
) -> Unit {
  for psl = entry.psl + 1, idx = (idx + 1) & self.capacity_mask, entry = entry {
    // SAFETY: same masked-index invariant as `add_with_hash`.
    match self.entries.unsafe_get(idx) {
      None => {
        entry.psl = psl
        self.set_entry(entry, idx)
        break
      }
      Some(curr_entry) =>
        if psl > curr_entry.psl {
          entry.psl = psl
          self.set_entry(entry, idx)
          continue curr_entry.psl + 1,
            (idx + 1) & self.capacity_mask,
            curr_entry
        } else {
          continue psl + 1, (idx + 1) & self.capacity_mask, entry
        }
    }
  }
}

///|
#inline
#owned(entry)
fn[K] HashSet::set_entry(
  self : HashSet[K],
  entry : Entry[K],
  new_idx : Int32,
) -> Unit {
  // SAFETY: every caller supplies an index already proven in bounds -- from
  // a masked probe, or from `shift_back`'s `cur`.
  self.entries.unsafe_set(new_idx, Some(entry))
}

///|
/// Returns `true` if the set contains the given key.
pub fn[K : Hash + Eq] HashSet::contains(self : HashSet[K], key : K) -> Bool {
  self.contains_with_hash(key, Hash::hash(key))
}

///|
/// `contains` with a precomputed `hash`. The set operations pass the hash
/// stored in the other set's entry: both sets hash `K` with the same `Hash`
/// impl, so the stored hash is exactly what `contains` would recompute.
#inline
fn[K : Eq] HashSet::contains_with_hash(
  self : HashSet[K],
  key : K,
  hash : Int32,
) -> Bool {
  for i = 0, idx = hash & self.capacity_mask {
    // SAFETY: same masked-index invariant as `add_with_hash`.
    guard self.entries.unsafe_get(idx) is Some(entry) else { break false }
    if entry.hash == hash && entry.key == key {
      break true
    }
    if i > entry.psl {
      break false
    }
    continue i + 1, (idx + 1) & self.capacity_mask
  }
}

///|
// Retrieve the stored key representative without hashing it again.
#inline
fn[K : Eq] HashSet::find_entry_with_hash(
  self : HashSet[K],
  key : K,
  hash : Int32,
) -> Entry[K]? {
  for distance = 0, index = hash & self.capacity_mask {
    // SAFETY: the initial index and each following index are masked.
    guard self.entries.unsafe_get(index) is Some(entry) else { break None }
    if entry.hash == hash && entry.key == key {
      break Some(entry)
    }
    if distance > entry.psl {
      break None
    }
    continue distance + 1, (index + 1) & self.capacity_mask
  }
}

///|
/// Remove a key from hash set. If the key exists in the set, removes it
/// and adjusts the probe sequence length (PSL) of subsequent entries to
/// maintain the Robin Hood hashing invariant. If the key does not exist,
/// the set remains unchanged.
///
/// Parameters:
///
/// * `self` : The hash set to remove the key from.
/// * `key` : The key to remove from the set.
///
/// Example:
///
/// ```mbt check
/// test {
///   let set = @hashset.from_array(["a", "b"])
///   set.remove("a")
///   inspect(set.contains("a"), content="false")
///   inspect(set.length(), content="1")
/// }
/// ```
pub fn[K : Hash + Eq] HashSet::remove(self : HashSet[K], key : K) -> Unit {
  let hash = Hash::hash(key)
  for i = 0, idx = hash & self.capacity_mask {
    // SAFETY: same masked-index invariant as `add_with_hash`.
    guard self.entries.unsafe_get(idx) is Some(entry) else { break }
    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
  }
}

///|
fn[K] HashSet::shift_back(self : HashSet[K], idx : Int32) -> Unit {
  for cur = idx {
    let next = (cur + 1) & self.capacity_mask
    // SAFETY: the initial `cur` is in bounds by either route its callers
    // take -- `remove` derives it from a masked probe, and `retain` reaches
    // here only after a checked `entries[i]` read succeeded. `next` is
    // re-masked each step, and `cur` afterwards is a previous `next`.
    match self.entries.unsafe_get(next) {
      None | Some({ psl: 0, .. }) => {
        self.entries.unsafe_set(cur, None)
        break
      }
      Some(entry) => {
        entry.psl -= 1
        self.set_entry(entry, cur)
        continue next
      }
    }
  }
}

///|
fn[K] HashSet::grow(self : HashSet[K]) -> Unit {
  // handle zero capacity
  if self.capacity == 0 {
    self.capacity = default_init_capacity
    self.capacity_mask = self.capacity - 1
    self.grow_at = calc_grow_threshold(self.capacity)
    self.size = 0
    self.entries = FixedArray::make(self.capacity, None)
    return
  }
  let old_entries = self.entries
  let new_capacity = self.capacity * 2
  self.entries = FixedArray::make(new_capacity, None)
  self.capacity = new_capacity
  self.capacity_mask = new_capacity - 1
  self.grow_at = calc_grow_threshold(self.capacity)
  for entry in old_entries {
    if entry is Some(entry) {
      self.rehash_place_entry(entry)
    }
  }
}

///|
#owned(entry)
fn[K] HashSet::rehash_place_entry(self : HashSet[K], entry : Entry[K]) -> Unit {
  let hash = entry.hash
  for psl = 0, idx = hash & self.capacity_mask {
    // SAFETY: same masked-index invariant as `add_with_hash`; `grow` installs
    // the new `entries` and `capacity_mask` together before rehashing.
    match self.entries.unsafe_get(idx) {
      None => {
        entry.psl = psl
        self.set_entry(entry, idx)
        return
      }
      Some(curr) =>
        if psl > curr.psl {
          self.push_away(idx, curr)
          entry.psl = psl
          self.set_entry(entry, idx)
          return
        } else {
          continue psl + 1, (idx + 1) & self.capacity_mask
        }
    }
  }
}

// Utils

///|
#deprecated("Use @debug.Debug instead of Show for debugging purposes. See https://github.com/moonbitlang/core/blob/main/debug/README.mbt.md")
pub impl[K : Show] Show for HashSet[K]

///|
pub impl[K : Show] Show for HashSet[K] with fn output(self, logger) {
  logger.write_iter(self.iter(), prefix="@hashset.from_array([", suffix="])")
}

///|
/// Returns the number of elements in the set.
#alias(size, deprecated)
pub fn[K] HashSet::length(self : HashSet[K]) -> Int32 {
  self.size
}

///|
/// Returns the current capacity of the internal storage.
pub fn[K] HashSet::capacity(self : HashSet[K]) -> Int32 {
  self.capacity
}

///|
/// Returns `true` if the set contains no elements.
pub fn[K] HashSet::is_empty(self : HashSet[K]) -> Bool {
  self.size == 0
}

///|
/// Calls `f` on each element in the set.
#locals(f)
pub fn[K] HashSet::each(
  self : HashSet[K],
  f : (K) -> Unit raise?,
) -> Unit raise? {
  for entry in self.entries {
    if entry is Some({ key, .. }) {
      f(key)
    }
  }
}

///|
/// Calls `f` on each element with its index (0-based).
#locals(f)
pub fn[K] HashSet::eachi(
  self : HashSet[K],
  f : (Int32, K) -> Unit raise?,
) -> Unit raise? {
  for i in 0.. Unit {
  self.entries.fill(None)
  self.size = 0
}

///|
/// Returns an iterator over the elements of the set.
#alias(iterator, deprecated)
pub fn[K] HashSet::iter(self : HashSet[K]) -> Iter[K] {
  let mut i = 0
  let len = self.entries.length()
  Iter::new(
    fn() {
      while i < len {
        let entry = self.entries.unsafe_get(i)
        i += 1
        if entry is Some({ key, .. }) {
          return Some(key)
        }
      } nobreak {
        None
      }
    },
    size_hint=self.size,
  )
}

///|
/// Converts the hash set to an array.
pub fn[K] HashSet::to_array(self : HashSet[K]) -> Array[K] {
  [
    for entry in self.entries if entry is Some({ key, .. }) => key
  ]
}

///|
/// Creates a hash set from an iterator of keys.
#as_free_fn
#alias(from_iterator, deprecated)
#as_free_fn(from_iterator, deprecated)
pub fn[K : Hash + Eq] HashSet::from_iter(iter : Iter[K]) -> HashSet[K] {
  let s = new_hashset(default_init_capacity)
  while iter.next() is Some(e) {
    s.add(e)
  }
  s
}

///|
/// Returns a new set containing all elements from both sets.
pub fn[K : Eq] HashSet::union(
  self : HashSet[K],
  other : HashSet[K],
) -> HashSet[K] {
  let m = self.copy()
  m.union_in_place(other)
  m
}

///|
/// Adds every element of `other` to `self`, in place: the mutating
/// counterpart of `union`, as `HashMap::merge_in_place` is of
/// `HashMap::merge`. Elements are not hashed again, so only `Eq` is needed.
///
/// Example:
///
/// ```mbt check
/// test {
///   let set = @hashset.from_array([3, 1])
///   set.union_in_place(@hashset.from_array([2, 3, 4]))
///   inspect(set.length(), content="4")
///   inspect(set.contains(4), content="true")
/// }
/// ```
pub fn[K : Eq] HashSet::union_in_place(
  self : HashSet[K],
  other : HashSet[K],
) -> Unit {
  if physical_equal(self, other) {
    return
  }
  for entry in other.entries {
    if entry is Some({ key, hash, .. }) {
      self.add_with_hash(key, hash)
    }
  }
}

///|
/// Returns a new set containing only elements present in both sets.
/// Equal keys retain the representative from this set.
pub fn[K : Eq] HashSet::intersection(
  self : HashSet[K],
  other : HashSet[K],
) -> HashSet[K] {
  let m = new_hashset(default_init_capacity)
  if self.size == 0 || other.size == 0 {
    return m
  }
  // Iteration visits the entire backing table, including empty slots left by
  // removals, so choose by capacity, breaking ties by live size to reduce lookups.
  if self.capacity < other.capacity ||
    (self.capacity == other.capacity && self.size <= other.size) {
    for entry in self.entries {
      if entry is Some({ key, hash, .. }) && other.contains_with_hash(key, hash) {
        m.add_with_hash(key, hash)
      }
    }
  } else {
    for candidate in other.entries {
      if candidate is Some({ key, hash, .. }) &&
        self.find_entry_with_hash(key, hash) is Some(original) {
        m.add_with_hash(original.key, original.hash)
      }
    }
  }
  m
}

///|
/// Returns a new set containing elements in `self` that are not in `other`.
pub fn[K : Eq] HashSet::difference(
  self : HashSet[K],
  other : HashSet[K],
) -> HashSet[K] {
  let m = new_hashset(default_init_capacity)
  for entry in self.entries {
    if entry is Some({ key, hash, .. }) && !other.contains_with_hash(key, hash) {
      m.add_with_hash(key, hash)
    }
  }
  m
}

///|
/// Symmetric difference of two hash sets.
pub fn[K : Eq] HashSet::symmetric_difference(
  self : HashSet[K],
  other : HashSet[K],
) -> HashSet[K] {
  let m = self.difference(other)
  for entry in other.entries {
    if entry is Some({ key, hash, .. }) && !self.contains_with_hash(key, hash) {
      m.add_with_hash(key, hash)
    }
  }
  m
}

///|
/// Returns `true` if the two sets have no elements in common.
pub fn[K : Eq] HashSet::is_disjoint(
  self : HashSet[K],
  other : HashSet[K],
) -> Bool {
  let (small, large) = if self.length() <= other.length() {
    (self, other)
  } else {
    (other, self)
  }
  for entry in small.entries {
    if entry is Some({ key, hash, .. }) && large.contains_with_hash(key, hash) {
      return false
    }
  }
  true
}

///|
/// Returns `true` if every element of `self` is also in `other`.
pub fn[K : Eq] HashSet::is_subset(
  self : HashSet[K],
  other : HashSet[K],
) -> Bool {
  guard self.length() <= other.length() else { return false }
  for entry in self.entries {
    if entry is Some({ key, hash, .. }) && !other.contains_with_hash(key, hash) {
      return false
    }
  }
  true
}

///|
/// Returns `true` if every element of `other` is also in `self`.
pub fn[K : Eq] HashSet::is_superset(
  self : HashSet[K],
  other : HashSet[K],
) -> Bool {
  other.is_subset(self)
}

///|
/// Intersection of two hash sets.
pub impl[K : Eq] BitAnd for HashSet[K] with fn land(self, other) {
  self.intersection(other)
}

///|
/// Union of two hash sets.
pub impl[K : Eq] BitOr for HashSet[K] with fn lor(self, other) {
  self.union(other)
}

///|
/// Symmetric difference of two hash sets.
pub impl[K : Eq] BitXOr for HashSet[K] with fn lxor(self, other) {
  self.symmetric_difference(other)
}

///|
/// Difference of two hash sets.
pub impl[K : Eq] Sub for HashSet[K] with fn sub(self, other) {
  self.difference(other)
}

///|
/// Keeps only the elements for which `f` returns `true`, removing the rest in
/// place.
///
/// `true` means *keep*, as with `HashSet::filter`, which returns a new set
/// and leaves `self` unchanged; use `retain` when the original is no longer
/// needed. `f` must not modify the set.
#locals(f)
pub fn[K] HashSet::retain(self : HashSet[K], f : (K) -> Bool) -> Unit {
  guard self.size > 0 else { return }
  // Scan the table once, starting just after an empty slot. `shift_back`
  // moves entries back only within a cluster, and a cluster never spans an
  // empty slot, so an entry is never shifted from an already-visited slot
  // into one still to be visited. Starting at slot 0 instead breaks when a
  // cluster wraps around the end of the table: removing the entry in the last
  // slot shifts the wrapped entry from slot 0 back into it, and `f` sees that
  // entry twice. The table grows at 13/16 full (`calc_grow_threshold`), so
  // an empty slot always exists. If the growth threshold is ever raised to
  // 100%, start instead at an entry sitting in its home slot (`psl == 0`),
  // which is also a cluster boundary.
  let mask = self.capacity_mask
  let start = for i = 0 {
    if self.entries[i] is None {
      break i
    }
    continue i + 1
  }
  for k in 1..<=mask {
    let i = (start + k) & mask
    while self.entries[i] is Some(entry) {
      if f(entry.key) {
        break
      } else {
        self.shift_back(i)
        self.size -= 1
      }
    }
  }
}

///|
/// Returns a new hash set holding the elements for which `f` returns `true`.
/// `self` is unchanged.
///
/// `true` means *keep*, as with `Array::filter`. To filter in place instead,
/// use `HashSet::retain`.
///
/// The result is sized for the elements kept, like `@hashset.from_array`. It
/// is faster than rebuilding from a comprehension such as
/// `@hashset.from_array([for k in s if f(k) => k])` because each element's
/// stored hash is reused: elements are never hashed again.
///
/// Example:
///
/// ```mbt check
/// test {
///   let set = @hashset.from_array([1, 2, 3, 4])
///   let even = set.filter(x => x % 2 == 0)
///   inspect(even.length(), content="2")
///   inspect(even.contains(2), content="true")
///   inspect(even.contains(3), content="false")
///   inspect(set.length(), content="4")
/// }
/// ```
pub fn[K] HashSet::filter(
  self : HashSet[K],
  f : (K) -> Bool raise?,
) -> HashSet[K] raise? {
  // Collect first so the result can be sized for exactly the kept elements:
  // a stored hash fits a table of any size. The entries are fresh because
  // `psl` belongs to the table an entry sits in.
  let kept : Array[Entry[K]] = []
  for entry in self.entries {
    if entry is Some({ key, hash, .. }) && f(key) {
      kept.push({ psl: 0, key, hash, })
    }
  }
  let other = new_hashset(
    default_init_capacity.max(capacity_for_length(kept.length())),
  )
  for entry in kept {
    other.rehash_place_entry(entry)
  }
  other.size = kept.length()
  other
}

///|
fn calc_grow_threshold(capacity : Int32) -> Int32 {
  capacity * 13 / 16
}

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

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

///|
impl Hash for MyString with fn hash_combine(self, hasher) {
  let MyString(self) = self
  hasher.combine_string(self)
}

///|
test "set" {
  let m : HashSet[MyString] = new_hashset(default_init_capacity)
  m.add("a")
  m.add("b")
  m.add("bc")
  m.add("abc")
  m.add("cd")
  m.add("c")
  m.add("d")
  inspect(m.size, content="7")
}

///|
test "remove" {
  let m : HashSet[MyString] = new_hashset(default_init_capacity)
  fn i(s) {
    MyString::MyString(s)
  }

  m.add("a" |> i)
  m.add("ab" |> i)
  m.add("bc" |> i)
  m.add("cd" |> i)
  m.add("abc" |> i)
  m.add("abcdef" |> i)
  m.remove("ab" |> i)
  inspect(m.length(), content="5")
}

///|
test "remove_unexist_key" {
  let m : HashSet[MyString] = new_hashset(default_init_capacity)
  fn i(s) {
    MyString::MyString(s)
  }

  m.add("a" |> i)
  m.add("ab" |> i)
  m.add("abc" |> i)
  m.remove("d" |> i)
  inspect(m.length(), content="3")
}

///|
test "grow" {
  let m : HashSet[MyString] = new_hashset(default_init_capacity)
  fn i(s) {
    MyString::MyString(s)
  }

  m.add("C" |> i)
  m.add("Go" |> i)
  m.add("C++" |> i)
  m.add("Java" |> i)
  m.add("Scala" |> i)
  m.add("Julia" |> i)
  inspect(m.size, content="6")
  inspect(m.capacity, content="8")
  m.add("Cobol" |> i)
  inspect(m.size, content="7")
  inspect(m.capacity, content="16")
  m.add("Python" |> i)
  m.add("Haskell" |> i)
  m.add("Rescript" |> i)
  inspect(m.size, content="10")
  inspect(m.capacity, content="16")
}

///|
test "clear" {
  let m : HashSet[MyString] = new_hashset(default_init_capacity)
  m.clear()
  inspect(m.length(), content="0")
  inspect(m.capacity(), content="8")
  for entry in m.entries {
    @test.assert_same_object(entry, None)
  }
}

///|
/// Insert a key into the hash set and returns whether the key was successfully added.
///
/// Parameters:
///
/// * `self` : The hash set to modify.
/// * `key` : The key to insert. Must implement `Hash` and `Eq` traits.
///
/// Returns `true` if the key was successfully added (i.e., it wasn't already present),
/// `false` if the key already existed in the set.
///
/// Example:
///
/// ```mbt check
/// test {
///   let set : @hashset.HashSet[String] = HashSet([])
///   inspect(set.add_and_check("key"), content="true") // First insertion
///   inspect(set.add_and_check("key"), content="false") // Already exists
///   inspect(set.length(), content="1")
/// }
/// ```
pub fn[K : Hash + Eq] HashSet::add_and_check(
  self : HashSet[K],
  key : K,
) -> Bool {
  let old_size = self.length()
  self.add(key)
  self.length() > old_size
}

///|
/// Remove a key from the hash set and returns whether the key was successfully removed.
///
/// Parameters:
///
/// * `self` : The hash set to modify.
/// * `key` : The key to remove. Must implement `Hash` and `Eq` traits.
///
/// Returns `true` if the key was successfully removed (i.e., it was present),
/// `false` if the key didn't exist in the set.
///
/// Example:
///
/// ```mbt check
/// test {
///   let set = @hashset.from_array(["a", "b"])
///   inspect(set.remove_and_check("a"), content="true") // Successfully removed
///   inspect(set.remove_and_check("a"), content="false") // Already removed
///   inspect(set.length(), content="1")
/// }
/// ```
pub fn[K : Hash + Eq] HashSet::remove_and_check(
  self : HashSet[K],
  key : K,
) -> Bool {
  let old_size = self.size
  self.remove(key)
  self.size < old_size
}

///|
/// Copy the set, creating a new set with the same keys.
#alias(clone, deprecated)
pub fn[K] HashSet::copy(self : HashSet[K]) -> HashSet[K] {
  let other = {
    capacity: self.capacity,
    entries: FixedArray::make(self.capacity, None),
    size: self.size,
    capacity_mask: self.capacity_mask,
    grow_at: self.grow_at,
  }
  // Rebuild each entry rather than blitting the references: `Entry::psl` is
  // mutable and `shift_back` decrements it, so sharing entries would let a
  // removal on one set corrupt the probe sequences of the other.
  for i in 0.. key
  ]
}

///|
/// Decodes a hash set from a JSON array, the form `to_json` produces. A
/// repeated element is kept once, as in `@hashset.from_array`.
///
/// # Example
///
/// ```mbt check
/// test {
///   let set : @hashset.HashSet[Int32] = @json.from_json([3, 1, 3, 2])
///   inspect(set.length(), content="3")
///   inspect(set.contains(3), content="true")
/// }
/// ```
pub impl[X : @json.FromJson + Hash + Eq] @json.FromJson for HashSet[X] with fn from_json(
  json,
  path,
) {
  guard json is Array(arr) else {
    raise JsonDecodeError((path, "@hashset.from_json: expected array"))
  }
  // Sized the way `@hashset.from_array` sizes itself for this many elements.
  let res : HashSet[X] = new_hashset(
    default_init_capacity.max(capacity_for_length(arr.length())),
  )
  for i, x in arr {
    res.add(@json.FromJson::from_json(x, path.add_index(i)))
  }
  res
}

///|
/// Default implementation for hashset
pub impl[K] Default for HashSet[K] with fn default() {
  new_hashset(default_init_capacity)
}

///|