///|
/// Per-hospital capacity problems for the hospital/residents mechanism.
/// Kept separate from `ProfileError` because quotas are a second gate:
/// the `Preferences` themselves stay legal, only the capacity table can
/// contradict the market shape.
pub suberror QuotaError {
  QuotaLength(Int, Int)
  NonPositiveQuota(Int, Int)
} derive(Debug)

///|
pub extend QuotaError with @debug.Debug::{to_repr}

///|
pub impl Show for QuotaError with fn output(self : QuotaError, logger) {
  match self {
    QuotaLength(got, expected) =>
      logger.write_string("got \{got} quotas for \{expected} hospitals")
    NonPositiveQuota(hospital, quota) =>
      logger.write_string(
        "hospital \{hospital} has quota \{quota}, quotas must be positive",
      )
  }
}

///|
pub extend QuotaError with Show::{to_string, output}

///|
/// The outcome of a hospital/residents run: residents see one hospital
/// (or -1), hospitals see a list of residents up to their quota.
pub struct HRAssignment {
  preferences : Preferences
  quotas : Array[Int]
  proposer_to_receiver : Array[Int]
  receiver_holders : Array[Array[Int]]
} derive(Eq, Debug)

///|
pub extend HRAssignment with Eq::{not_equal, equal}

///|
pub extend HRAssignment with @debug.Debug::{to_repr}

///|
fn worst_holder(holders : Array[Int], ranks : Array[Int]) -> Int {
  let mut w = holders[0]
  for x in holders {
    if ranks[x] > ranks[w] {
      w = x
    }
  }
  w
}

///|
/// Remove `elem` (which must be present) from `holders`. MoonBit's
/// `Array::remove` takes an index, so the position is found first.
fn evict(holders : Array[Int], elem : Int) -> Unit {
  let mut i = 0
  while holders[i] != elem {
    i = i + 1
  }
  ignore(holders.remove(i))
}

///|
/// True when hospital `r` would rather hold proposer `p` than its
/// current situation: a free seat, or a ranking above its worst holder.
fn hospital_prefers(
  holders : Array[Int],
  ranks : Array[Int],
  p : Int,
  quota : Int,
) -> Bool {
  if holders.length() < quota {
    true
  } else {
    ranks[p] < ranks[worst_holder(holders, ranks)]
  }
}

///|
/// Deferred acceptance with many-to-one receivers (Roth & Sotomayor
/// 1990, the algorithm behind US resident matching): identical to
/// `deferred_acceptance` when every quota is 1; otherwise a hospital
/// holds its best `quota` offers instead of just one.
pub fn Preferences::hospital_residents(
  self : Preferences,
  quotas : Array[Int],
) -> HRAssignment raise QuotaError {
  let n = self.proposer_prefs.length()
  let m = self.receiver_prefs.length()
  if quotas.length() != m {
    raise QuotaLength(quotas.length(), m)
  }
  for j in 0.. Array[(Int, Int)] {
  let p_ranks = ranks_of(self.preferences.proposer_prefs)
  let r_ranks = ranks_of(self.preferences.receiver_prefs)
  let n = self.proposer_to_receiver.length()
  let m = self.receiver_holders.length()
  let out = Array(capacity=0)
  for p in 0.. Bool {
  self.blocking_pairs().length() == 0
}