///|
fn Election::strict(self : Election) -> Unit raise TallyError {
  guard self.candidates.length() <= 16 else {
    raise Limit("IRV supports at most 16 candidates")
  }
  for ballot in self.ballots {
    for rank in ballot.ranking {
      guard rank.length() == 1 else {
        raise Invalid(
          "IRV requires strict rankings; tied ranks remain supported by pairwise methods",
        )
      }
    }
  }
}

///|
fn Election::round(self : Election, mask : Int32) -> Round {
  let active : Array[String] = []
  let counts : Map[String, Int32] = Map([])
  for i, id in self.candidates {
    if (mask & (1 << i)) != 0 {
      active.push(id)
      counts[id] = 0
    }
  }
  let mut continuing_weight = 0
  for ballot in self.ballots {
    for rank in ballot.ranking {
      if counts.get(rank[0]) is Some(n) {
        counts[rank[0]] = n + ballot.weight
        continuing_weight = continuing_weight + ballot.weight
        break
      }
    }
  }
  let mut minimum = 1000000001
  for _, count in counts {
    minimum = minimum.min(count)
  }
  let tied_lowest = active.filter(id => counts.get(id) == Some(minimum))
  {
    active,
    counts,
    continuing_weight,
    exhausted_weight: self.total - continuing_weight,
    tied_lowest,
    eliminated: "",
  }
}

///|
fn majority(round : Round) -> Array[String] {
  let winners : Array[String] = []
  for id in round.active {
    if round.counts.get(id).unwrap_or(0) > round.continuing_weight / 2 {
      winners.push(id)
    }
  }
  winners
}

///|
/// Without an explicit full tie-order permutation, an elimination tie is returned unresolved.
pub fn Election::irv(
  self : Election,
  tie_order : Array[String],
) -> IrvResult raise TallyError {
  self.strict()
  if tie_order.length() > 0 {
    let sorted = tie_order.copy()
    sorted.sort()
    guard sorted == self.candidates else {
      raise Invalid(
        "tie_order must be a candidate permutation, earliest eliminated first",
      )
    }
  }
  let mut mask = (1 << self.candidates.length()) - 1
  let rounds : Array[Round] = []
  while mask > 0 {
    let round = self.round(mask)
    let winners = majority(round)
    if winners.length() > 0 || round.continuing_weight == 0 {
      rounds.push(round)
      return { winners, rounds, needs_tiebreak: false, }
    }
    if round.tied_lowest.length() > 1 && tie_order.length() == 0 {
      rounds.push(round)
      return { winners: [], rounds, needs_tiebreak: true, }
    }
    let mut eliminated = round.tied_lowest[0]
    if round.tied_lowest.length() > 1 {
      for id in tie_order {
        if round.tied_lowest.contains(id) {
          eliminated = id
          break
        }
      }
    }
    rounds.push({ ..round, eliminated, })
    for i, id in self.candidates {
      if id == eliminated {
        mask = mask ^ (1 << i)
      }
    }
  }
  { winners: [], rounds, needs_tiebreak: false, }
}

///|
/// Enumerates all legal single-elimination tie resolutions, memoizing active-candidate masks.
/// A state budget exhaustion returns Limit rather than an incomplete winner set.
pub fn Election::irv_possibilities(
  self : Election,
  max_states : Int32,
) -> IrvPossibilities raise TallyError {
  self.strict()
  guard max_states >= 1 && max_states <= 65535 else {
    raise Invalid("state budget must be 1..65535")
  }
  let cache : Map[Int32, Array[TieWitness]] = Map([])
  let visited = Ref(0)
  fn visit(mask : Int32) -> Array[TieWitness] raise TallyError {
    if cache.get(mask) is Some(found) {
      return found
    }
    visited.val = visited.val + 1
    guard visited.val <= max_states else {
      raise Limit("IRV tie exploration exceeds requested state budget")
    }
    let round = self.round(mask)
    let winners = majority(round)
    let result : Array[TieWitness] = []
    if winners.length() > 0 {
      for winner in winners {
        result.push({ winner, eliminations: [], })
      }
    } else if round.continuing_weight > 0 {
      let by_winner : Map[String, TieWitness] = Map([])
      for eliminated in round.tied_lowest {
        let mut next = mask
        for i, id in self.candidates {
          if id == eliminated {
            next = mask ^ (1 << i)
          }
        }
        for witness in visit(next) {
          if !by_winner.contains(witness.winner) {
            let eliminations = [eliminated]
            eliminations.append(witness.eliminations)
            by_winner[witness.winner] = {
              winner: witness.winner,
              eliminations,
            }
          }
        }
      }
      let ids = by_winner.keys().to_array()
      ids.sort()
      for id in ids {
        if by_winner.get(id) is Some(witness) {
          result.push(witness)
        }
      }
    }
    cache[mask] = result
    result
  }
  let witnesses = visit((1 << self.candidates.length()) - 1)
  {
    possible_winners: witnesses.map(w => w.winner),
    explored_states: visited.val,
    witnesses,
  }
}