use std::collections::{HashMap, HashSet};
pub const MAX_CANDIDATES: usize = 256;
pub const MAX_BALLOTS: usize = 10_000;
pub const MAX_IDENTIFIER_CHARS: usize = 256;
#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
pub struct Ballot {
pub voter_id: String,
pub rankings: Vec<Vec<String>>,
}
impl Ballot {
pub fn new(voter_id: impl Into<String>, ranking: Vec<String>) -> Self {
let rankings = ranking.into_iter().map(|c| vec![c]).collect();
Self {
voter_id: voter_id.into(),
rankings,
}
}
pub fn with_ties(voter_id: impl Into<String>, groups: Vec<Vec<String>>) -> Self {
Self {
voter_id: voter_id.into(),
rankings: groups,
}
}
}
#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
pub struct PairwiseResult {
pub candidate_a: String,
pub candidate_b: String,
pub a_preferred: i32,
pub b_preferred: i32,
}
#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
pub struct SchulzeRanking {
pub candidate: String,
pub rank: usize,
pub wins: usize,
pub losses: usize,
}
#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
pub struct ElectionResult {
pub winner: Option<String>,
pub ranking: Vec<SchulzeRanking>,
pub pairwise_matrix: Vec<Vec<i32>>,
pub strongest_paths: Vec<Vec<i32>>,
pub candidates: Vec<String>,
pub ballot_count: usize,
pub has_condorcet_winner: bool,
pub ties: Vec<(String, String)>,
}
pub struct SchulzeElection {
candidates: Vec<String>,
index: HashMap<String, usize>,
ballots: Vec<Ballot>,
}
impl SchulzeElection {
pub fn new(candidates: Vec<String>) -> Result<Self, &'static str> {
if candidates.is_empty() {
return Err("candidates must be non-empty");
}
if candidates.len() > MAX_CANDIDATES {
return Err("too many candidates");
}
if candidates.iter().any(|candidate| {
candidate.is_empty() || candidate.chars().count() > MAX_IDENTIFIER_CHARS
}) {
return Err("candidate identifiers must contain 1 to 256 characters");
}
let unique: HashSet<&str> = candidates.iter().map(String::as_str).collect();
if unique.len() != candidates.len() {
return Err("candidates must be unique");
}
let index: HashMap<String, usize> = candidates
.iter()
.enumerate()
.map(|(i, c)| (c.clone(), i))
.collect();
Ok(Self {
candidates,
index,
ballots: Vec::new(),
})
}
pub fn candidates(&self) -> &[String] {
&self.candidates
}
pub fn ballot_count(&self) -> usize {
self.ballots.len()
}
pub fn add_ballot(&mut self, ballot: Ballot) -> Result<(), &'static str> {
if self.ballots.len() >= MAX_BALLOTS {
return Err("too many ballots");
}
if ballot.voter_id.is_empty() || ballot.voter_id.chars().count() > MAX_IDENTIFIER_CHARS {
return Err("voter identifiers must contain 1 to 256 characters");
}
if ballot.rankings.is_empty() {
return Err("rankings must be non-empty");
}
let mut seen = HashSet::new();
for group in &ballot.rankings {
if group.is_empty() {
return Err("ranking groups must be non-empty");
}
for candidate in group {
if !self.index.contains_key(candidate) {
return Err("ballot contains an unknown candidate");
}
if !seen.insert(candidate.as_str()) {
return Err("ballot candidates must be unique");
}
}
}
self.ballots.push(ballot);
Ok(())
}
pub fn compute(&self) -> ElectionResult {
let n = self.candidates.len();
if self.ballots.is_empty() {
return ElectionResult {
winner: None,
ranking: Vec::new(),
pairwise_matrix: vec![vec![0; n]; n],
strongest_paths: vec![vec![0; n]; n],
candidates: self.candidates.clone(),
ballot_count: 0,
has_condorcet_winner: false,
ties: Vec::new(),
};
}
let d = self.build_pairwise_matrix();
let p = self.compute_strongest_paths(&d);
let (ranking, ties) = self.determine_ranking(&p);
let winner = ranking.first().map(|r| r.candidate.clone());
let has_condorcet = winner.as_ref().is_some_and(|w| self.check_condorcet(&d, w));
ElectionResult {
winner,
ranking,
pairwise_matrix: d,
strongest_paths: p,
candidates: self.candidates.clone(),
ballot_count: self.ballots.len(),
has_condorcet_winner: has_condorcet,
ties,
}
}
fn build_pairwise_matrix(&self) -> Vec<Vec<i32>> {
let n = self.candidates.len();
let mut d = vec![vec![0i32; n]; n];
for ballot in &self.ballots {
self.apply_grouped_ballot(&mut d, ballot);
}
d
}
fn apply_grouped_ballot(&self, d: &mut [Vec<i32>], ballot: &Ballot) {
let n = self.candidates.len();
let mut position: HashMap<&str, usize> = HashMap::new();
let mut rank = 0;
for group in &ballot.rankings {
for cid in group {
if self.index.contains_key(cid.as_str()) {
position.insert(cid.as_str(), rank);
}
}
rank += 1;
}
for cid in &self.candidates {
position.entry(cid.as_str()).or_insert(rank);
}
for i in 0..n {
for j in (i + 1)..n {
let pi = position[self.candidates[i].as_str()];
let pj = position[self.candidates[j].as_str()];
if pi < pj {
d[i][j] += 1;
} else if pj < pi {
d[j][i] += 1;
}
}
}
}
#[allow(clippy::needless_range_loop)]
fn compute_strongest_paths(&self, d: &[Vec<i32>]) -> Vec<Vec<i32>> {
let n = self.candidates.len();
let mut p = vec![vec![0i32; n]; n];
for i in 0..n {
for j in 0..n {
if i != j && d[i][j] > d[j][i] {
p[i][j] = d[i][j];
}
}
}
for k in 0..n {
for i in 0..n {
if i == k {
continue;
}
for j in 0..n {
if j == i || j == k {
continue;
}
let via_k = p[i][k].min(p[k][j]);
if via_k > p[i][j] {
p[i][j] = via_k;
}
}
}
}
p
}
#[allow(clippy::needless_range_loop)]
fn determine_ranking(&self, p: &[Vec<i32>]) -> (Vec<SchulzeRanking>, Vec<(String, String)>) {
let n = self.candidates.len();
let mut ties: Vec<(String, String)> = Vec::new();
let mut wins = vec![0usize; n];
let mut losses = vec![0usize; n];
for i in 0..n {
for j in 0..n {
if i != j {
if p[i][j] > p[j][i] {
wins[i] += 1;
losses[j] += 1;
} else if p[i][j] == p[j][i] && p[i][j] > 0 {
ties.push((self.candidates[i].clone(), self.candidates[j].clone()));
}
}
}
}
for i in 0..n {
for j in (i + 1)..n {
if p[i][j] == p[j][i] && p[i][j] == 0 {
let pair = (self.candidates[i].clone(), self.candidates[j].clone());
if !ties.contains(&pair) {
ties.push(pair);
}
}
}
}
let mut indices: Vec<usize> = (0..n).collect();
indices.sort_by(|&a, &b| wins[b].cmp(&wins[a]));
let mut rankings: Vec<SchulzeRanking> = Vec::with_capacity(n);
let mut current_rank = 1;
for (pos, &idx) in indices.iter().enumerate() {
if pos > 0 {
let prev_idx = indices[pos - 1];
if wins[idx] < wins[prev_idx] {
current_rank = pos + 1;
}
}
rankings.push(SchulzeRanking {
candidate: self.candidates[idx].clone(),
rank: current_rank,
wins: wins[idx],
losses: losses[idx],
});
}
let mut seen: HashSet<(String, String)> = HashSet::new();
let mut deduped: Vec<(String, String)> = Vec::new();
for (a, b) in ties {
let key = if a < b {
(a.clone(), b.clone())
} else {
(b.clone(), a.clone())
};
if seen.insert(key.clone()) {
deduped.push(key);
}
}
(rankings, deduped)
}
#[allow(clippy::needless_range_loop)]
fn check_condorcet(&self, d: &[Vec<i32>], winner: &str) -> bool {
let Some(&wi) = self.index.get(winner) else {
return false;
};
for j in 0..self.candidates.len() {
if j != wi && d[wi][j] <= d[j][wi] {
return false;
}
}
true
}
}
#[cfg(test)]
mod tests {
use super::*;
fn cands(names: &[&str]) -> Vec<String> {
names.iter().map(ToString::to_string).collect()
}
#[test]
fn test_empty_candidates() {
assert!(SchulzeElection::new(Vec::new()).is_err());
}
#[test]
fn test_duplicate_candidates() {
let result = SchulzeElection::new(cands(&["a", "b", "a"]));
assert!(result.is_err());
}
#[test]
fn election_candidate_limits_are_inclusive() {
let maximum: Vec<String> = (0..MAX_CANDIDATES)
.map(|index| format!("c{index}"))
.collect();
assert!(SchulzeElection::new(maximum).is_ok());
let excessive: Vec<String> = (0..=MAX_CANDIDATES)
.map(|index| format!("c{index}"))
.collect();
assert_eq!(
SchulzeElection::new(excessive).err(),
Some("too many candidates")
);
assert!(SchulzeElection::new(vec![String::new()]).is_err());
assert!(SchulzeElection::new(vec!["x".repeat(MAX_IDENTIFIER_CHARS + 1)]).is_err());
}
#[test]
fn test_no_ballots() {
let election = SchulzeElection::new(cands(&["a", "b", "c"])).unwrap();
let result = election.compute();
assert!(result.winner.is_none());
assert_eq!(result.ballot_count, 0);
}
#[test]
fn test_single_ballot() {
let mut election = SchulzeElection::new(cands(&["a", "b", "c"])).unwrap();
election
.add_ballot(Ballot::new("v1", cands(&["b", "a", "c"])))
.unwrap();
let result = election.compute();
assert_eq!(result.winner.as_deref(), Some("b"));
assert_eq!(result.ballot_count, 1);
assert!(result.has_condorcet_winner);
}
#[test]
fn unknown_ballot_candidate_is_rejected_without_state_mutation() {
let mut election = SchulzeElection::new(cands(&["a", "b"])).unwrap();
assert_eq!(
election.add_ballot(Ballot::new("v1", cands(&["a", "typo"]))),
Err("ballot contains an unknown candidate")
);
assert_eq!(election.ballot_count(), 0);
assert!(election.compute().winner.is_none());
}
#[test]
fn malformed_ballots_are_rejected_without_state_mutation() {
let mut election = SchulzeElection::new(cands(&["a", "b"])).unwrap();
let malformed = [
Ballot::with_ties("v1", Vec::new()),
Ballot::with_ties("v1", vec![Vec::new()]),
Ballot::with_ties("v1", vec![cands(&["a"]), cands(&["a"])]),
Ballot::new("", cands(&["a"])),
Ballot::new("v".repeat(MAX_IDENTIFIER_CHARS + 1), cands(&["a"])),
];
for ballot in malformed {
assert!(election.add_ballot(ballot).is_err());
assert_eq!(election.ballot_count(), 0);
}
}
#[test]
fn ballot_limit_is_enforced_before_mutation() {
let mut election = SchulzeElection::new(cands(&["a"])).unwrap();
election.ballots = vec![Ballot::new("v", cands(&["a"])); MAX_BALLOTS];
assert_eq!(
election.add_ballot(Ballot::new("last", cands(&["a"]))),
Err("too many ballots")
);
assert_eq!(election.ballot_count(), MAX_BALLOTS);
}
#[test]
fn test_condorcet_winner() {
let mut election = SchulzeElection::new(cands(&["a", "b", "c"])).unwrap();
election
.add_ballot(Ballot::new("v1", cands(&["b", "a", "c"])))
.unwrap();
election
.add_ballot(Ballot::new("v2", cands(&["b", "c", "a"])))
.unwrap();
election
.add_ballot(Ballot::new("v3", cands(&["a", "b", "c"])))
.unwrap();
let result = election.compute();
assert_eq!(result.winner.as_deref(), Some("b"));
assert!(result.has_condorcet_winner);
}
#[test]
fn test_tied_groups_ballot() {
let mut election = SchulzeElection::new(cands(&["a", "b", "c"])).unwrap();
election
.add_ballot(Ballot::with_ties(
"v1",
vec![cands(&["a", "b"]), cands(&["c"])],
))
.unwrap();
let result = election.compute();
let a_idx = 0;
let b_idx = 1;
let c_idx = 2;
assert_eq!(result.pairwise_matrix[a_idx][c_idx], 1);
assert_eq!(result.pairwise_matrix[b_idx][c_idx], 1);
assert_eq!(result.pairwise_matrix[a_idx][b_idx], 0);
assert_eq!(result.pairwise_matrix[b_idx][a_idx], 0);
}
#[test]
fn test_strongest_paths_match_python() {
let mut election = SchulzeElection::new(cands(&["a", "b", "c", "d"])).unwrap();
for _ in 0..3 {
election
.add_ballot(Ballot::new("v", cands(&["a", "b", "c", "d"])))
.unwrap();
}
for _ in 0..2 {
election
.add_ballot(Ballot::new("v", cands(&["d", "c", "b", "a"])))
.unwrap();
}
let result = election.compute();
assert_eq!(result.winner.as_deref(), Some("a"));
assert!(result.has_condorcet_winner);
assert_eq!(result.pairwise_matrix[0][1], 3); assert_eq!(result.pairwise_matrix[1][0], 2); }
#[test]
fn test_schulze_ranking_order() {
let mut election = SchulzeElection::new(cands(&["a", "b", "c"])).unwrap();
election
.add_ballot(Ballot::new("v1", cands(&["c", "b", "a"])))
.unwrap();
election
.add_ballot(Ballot::new("v2", cands(&["c", "a", "b"])))
.unwrap();
election
.add_ballot(Ballot::new("v3", cands(&["b", "c", "a"])))
.unwrap();
let result = election.compute();
assert_eq!(result.winner.as_deref(), Some("c"));
assert_eq!(result.ranking[0].candidate, "c");
assert_eq!(result.ranking[0].rank, 1);
}
#[test]
fn test_unranked_candidates_at_bottom() {
let mut election = SchulzeElection::new(cands(&["a", "b", "c"])).unwrap();
election
.add_ballot(Ballot::new("v1", cands(&["a"])))
.unwrap();
let result = election.compute();
assert_eq!(result.winner.as_deref(), Some("a"));
assert_eq!(result.pairwise_matrix[0][1], 1); assert_eq!(result.pairwise_matrix[0][2], 1); assert_eq!(result.pairwise_matrix[1][2], 0);
assert_eq!(result.pairwise_matrix[2][1], 0);
}
}