///|
// BFS at an edge-strength threshold gives an independently replayable bottleneck-path witness.
fn find_path(
  matrix : Array[Array[Int32]],
  source : Int32,
  target : Int32,
  minimum : Int32,
) -> Array[Int32] {
  let previous = Array::make(matrix.length(), -1)
  previous[source] = source
  let queue = [source]
  let mut head = 0
  while head < queue.length() {
    let from = queue[head]
    head = head + 1
    for to = 0; to < matrix.length(); to = to + 1 {
      if matrix[from][to] < minimum || previous[to] >= 0 {
        continue
      }
      previous[to] = from
      queue.push(to)
    }
  }
  if previous[target] < 0 {
    return []
  }
  let path = [target]
  let mut cursor = target
  while cursor != source {
    cursor = previous[cursor]
    path.push(cursor)
  }
  path.rev()
}

///|
/// Schulze winning-votes variant. Returns the full unbeaten winner set; no hidden tie-break.
pub fn Election::schulze(self : Election) -> SchulzeResult {
  let n = self.candidates.length()
  let direct = self.pairwise.map(row => row.copy())
  for i = 0; i < n; i = i + 1 {
    for j = 0; j < n; j = j + 1 {
      if i == j || self.pairwise[i][j] <= self.pairwise[j][i] {
        direct[i][j] = 0
      }
    }
  }
  let p = direct.map(row => row.copy())
  for k = 0; k < n; k = k + 1 {
    for i = 0; i < n; i = i + 1 {
      if i != k {
        for j = 0; j < n; j = j + 1 {
          if j != i && j != k {
            p[i][j] = p[i][j].max(p[i][k].min(p[k][j]))
          }
        }
      }
    }
  }
  let winners : Array[String] = []
  let witnesses : Array[Beatpath] = []
  for i, id in self.candidates {
    let mut unbeaten = true
    for j = 0; j < n; j = j + 1 {
      if i == j {
        continue
      }
      if p[i][j] < p[j][i] {
        unbeaten = false
      }
      if p[i][j] > 0 {
        witnesses.push({
          from: id,
          to: self.candidates[j],
          strength: p[i][j],
          path: find_path(direct, i, j, p[i][j]).map(k => self.candidates[k]),
        })
      }
    }
    if unbeaten && self.nonblank > 0 {
      winners.push(id)
    }
  }
  { winners, strengths: p, witnesses, }
}

///|
/// Ranked Pairs variant: margin descending, winning votes descending, then lexical IDs.
/// The deterministic equal-strength priority is explicit and is not parallel-universe RP.
pub fn Election::ranked_pairs(self : Election) -> RankedPairsResult {
  let n = self.candidates.length()
  let edges : Array[(Int32, Int32, Int32, Int32)] = []
  for i = 0; i < n; i = i + 1 {
    for j = 0; j < n; j = j + 1 {
      if self.pairwise[i][j] > self.pairwise[j][i] {
        edges.push(
          (i, j, self.pairwise[i][j] - self.pairwise[j][i], self.pairwise[i][j]),
        )
      }
    }
  }
  edges.sort_by_key(e => {
    (-e.2, -e.3, self.candidates[e.0], self.candidates[e.1])
  })
  let locked = self.candidates.map(_ => Array::make(n, 0))
  let decisions : Array[LockedEdge] = []
  for e in edges {
    let cycle = find_path(locked, e.1, e.0, 1)
    let accepted = cycle.length() == 0
    if accepted {
      locked[e.0][e.1] = 1
    }
    decisions.push({
      from: self.candidates[e.0],
      to: self.candidates[e.1],
      margin: e.2,
      winning_votes: e.3,
      locked: accepted,
      cycle_path: cycle.map(i => self.candidates[i]),
    })
  }
  let winners : Array[String] = []
  for i, id in self.candidates {
    let mut source = true
    for j = 0; j < n; j = j + 1 {
      if locked[j][i] > 0 {
        source = false
      }
    }
    if source && self.nonblank > 0 {
      winners.push(id)
    }
  }
  { winners, decisions, }
}