326 lines
10 KiB
Rust
326 lines
10 KiB
Rust
/* OpenTally: Open-source election vote counting
|
||
* Copyright © 2021–2022 Lee Yingtong Li (RunasSudo)
|
||
*
|
||
* This program is free software: you can redistribute it and/or modify
|
||
* it under the terms of the GNU Affero General Public License as published by
|
||
* the Free Software Foundation, either version 3 of the License, or
|
||
* (at your option) any later version.
|
||
*
|
||
* This program is distributed in the hope that it will be useful,
|
||
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
||
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
||
* GNU Affero General Public License for more details.
|
||
*
|
||
* You should have received a copy of the GNU Affero General Public License
|
||
* along with this program. If not, see <https://www.gnu.org/licenses/>.
|
||
*/
|
||
|
||
use crate::election::{Candidate, CountState};
|
||
use crate::logger::smart_join;
|
||
use crate::numbers::Number;
|
||
use crate::stv::{STVError, STVOptions};
|
||
|
||
#[allow(unused_imports)]
|
||
use wasm_bindgen::prelude::wasm_bindgen;
|
||
|
||
#[allow(unused_imports)]
|
||
use std::io::{stdin, stdout, Write};
|
||
|
||
/// Strategy for breaking ties
|
||
#[derive(Clone, PartialEq)]
|
||
pub enum TieStrategy {
|
||
/// Break ties according to the candidate who first had more/fewer votes
|
||
Forwards,
|
||
/// Break ties according to the candidate who most recently had more/fewer votes
|
||
Backwards,
|
||
/// Break ties randomly (see [crate::sharandom])
|
||
Random(String),
|
||
/// Prompt the user to break ties
|
||
Prompt,
|
||
}
|
||
|
||
/// Get a [Vec] of [TieStrategy] based on string representations
|
||
pub fn from_strs<S: AsRef<str>>(strs: Vec<S>, mut random_seed: Option<String>) -> Vec<TieStrategy> {
|
||
strs.into_iter().map(|t| match t.as_ref() {
|
||
"forwards" => TieStrategy::Forwards,
|
||
"backwards" => TieStrategy::Backwards,
|
||
"random" => TieStrategy::Random(random_seed.take().expect("Must provide a --random-seed if using --ties random")),
|
||
"prompt" => TieStrategy::Prompt,
|
||
_ => panic!("Invalid --ties"),
|
||
}).collect()
|
||
}
|
||
|
||
impl TieStrategy {
|
||
/// Convert to CLI argument representation
|
||
pub fn describe(&self) -> String {
|
||
match self {
|
||
Self::Forwards => "forwards",
|
||
Self::Backwards => "backwards",
|
||
Self::Random(_) => "random",
|
||
Self::Prompt => "prompt",
|
||
}.to_string()
|
||
}
|
||
|
||
/// Break a tie between the given candidates, selecting the highest candidate
|
||
///
|
||
/// The given candidates are assumed to be tied in this round
|
||
pub fn choose_highest<'c, N: Number>(&self, state: &mut CountState<N>, opts: &STVOptions, candidates: &[&'c Candidate], prompt_text: &str) -> Result<&'c Candidate, STVError> {
|
||
match self {
|
||
Self::Forwards => {
|
||
match &state.forwards_tiebreak {
|
||
Some(tb) => {
|
||
let mut candidates: Vec<&Candidate> = candidates.iter().copied().collect();
|
||
// Compare b to a to sort high-to-low
|
||
candidates.sort_unstable_by(|a, b| tb[b].cmp(&tb[a]));
|
||
if tb[candidates[0]] == tb[candidates[1]] {
|
||
return Err(STVError::UnresolvedTie);
|
||
} else {
|
||
state.logger.log_literal(format!("Tie between {} broken forwards.", smart_join(&candidates.iter().map(|c| c.name.as_str()).collect())));
|
||
return Ok(candidates[0]);
|
||
}
|
||
}
|
||
None => {
|
||
// First stage
|
||
return Err(STVError::UnresolvedTie);
|
||
}
|
||
}
|
||
}
|
||
Self::Backwards => {
|
||
match &state.backwards_tiebreak {
|
||
Some(tb) => {
|
||
let mut candidates: Vec<&Candidate> = candidates.iter().copied().collect();
|
||
candidates.sort_unstable_by(|a, b| tb[b].cmp(&tb[a]));
|
||
if tb[candidates[0]] == tb[candidates[1]] {
|
||
return Err(STVError::UnresolvedTie);
|
||
} else {
|
||
state.logger.log_literal(format!("Tie between {} broken backwards.", smart_join(&candidates.iter().map(|c| c.name.as_str()).collect())));
|
||
return Ok(candidates[0]);
|
||
}
|
||
}
|
||
None => {
|
||
// First stage
|
||
return Err(STVError::UnresolvedTie);
|
||
}
|
||
}
|
||
}
|
||
Self::Random(_) => {
|
||
state.logger.log_literal(format!("Tie between {} broken at random.", smart_join(&candidates.iter().map(|c| c.name.as_str()).collect())));
|
||
return Ok(candidates[state.random.as_mut().unwrap().next(candidates.len())]);
|
||
}
|
||
Self::Prompt => {
|
||
match prompt(state, opts, candidates, prompt_text) {
|
||
Ok(c) => {
|
||
state.logger.log_literal(format!("Tie between {} broken by manual intervention.", smart_join(&candidates.iter().map(|c| c.name.as_str()).collect())));
|
||
return Ok(c);
|
||
}
|
||
Err(e) => { return Err(e); }
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
/// Break a tie between the given candidates, selecting the lowest candidate
|
||
///
|
||
/// The given candidates are assumed to be tied in this round
|
||
pub fn choose_lowest<'c, N: Number>(&self, state: &mut CountState<N>, opts: &STVOptions, candidates: &[&'c Candidate], prompt_text: &str) -> Result<&'c Candidate, STVError> {
|
||
match self {
|
||
Self::Forwards => {
|
||
let mut candidates: Vec<&Candidate> = candidates.iter().copied().collect();
|
||
candidates.sort_unstable_by(|a, b|
|
||
state.forwards_tiebreak.as_ref().unwrap()[a]
|
||
.cmp(&state.forwards_tiebreak.as_ref().unwrap()[b])
|
||
);
|
||
if state.forwards_tiebreak.as_ref().unwrap()[candidates[0]] == state.forwards_tiebreak.as_ref().unwrap()[candidates[1]] {
|
||
return Err(STVError::UnresolvedTie);
|
||
} else {
|
||
state.logger.log_literal(format!("Tie between {} broken forwards.", smart_join(&candidates.iter().map(|c| c.name.as_str()).collect())));
|
||
return Ok(candidates[0]);
|
||
}
|
||
}
|
||
Self::Backwards => {
|
||
let mut candidates: Vec<&Candidate> = candidates.iter().copied().collect();
|
||
candidates.sort_unstable_by(|a, b|
|
||
state.backwards_tiebreak.as_ref().unwrap()[a]
|
||
.cmp(&state.backwards_tiebreak.as_ref().unwrap()[b])
|
||
);
|
||
if state.backwards_tiebreak.as_ref().unwrap()[candidates[0]] == state.backwards_tiebreak.as_ref().unwrap()[candidates[1]] {
|
||
return Err(STVError::UnresolvedTie);
|
||
} else {
|
||
state.logger.log_literal(format!("Tie between {} broken backwards.", smart_join(&candidates.iter().map(|c| c.name.as_str()).collect())));
|
||
return Ok(candidates[0]);
|
||
}
|
||
}
|
||
Self::Random(_seed) => {
|
||
return self.choose_highest(state, opts, candidates, prompt_text);
|
||
}
|
||
Self::Prompt => {
|
||
return self.choose_highest(state, opts, candidates, prompt_text);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
/// Return all maximal items according to the given key
|
||
pub fn multiple_max_by<E: Copy, K, C: Ord>(items: &[E], key: K) -> Vec<E>
|
||
where
|
||
K: Fn(&E) -> C
|
||
{
|
||
let mut max_key = None;
|
||
let mut max_items = Vec::new();
|
||
for item in items.iter() {
|
||
let item_key = key(item);
|
||
match &max_key {
|
||
Some(v) => {
|
||
if &item_key > v {
|
||
max_key = Some(item_key);
|
||
max_items.clear();
|
||
max_items.push(*item);
|
||
} else if &item_key == v {
|
||
max_items.push(*item);
|
||
}
|
||
}
|
||
None => {
|
||
max_key = Some(item_key);
|
||
max_items.clear();
|
||
max_items.push(*item);
|
||
}
|
||
}
|
||
}
|
||
return max_items;
|
||
}
|
||
|
||
/// Return all minimal items according to the given key
|
||
pub fn multiple_min_by<E: Copy, K, C: Ord>(items: &[E], key: K) -> Vec<E>
|
||
where
|
||
K: Fn(&E) -> C
|
||
{
|
||
let mut min_key = None;
|
||
let mut min_items = Vec::new();
|
||
for item in items.iter() {
|
||
let item_key = key(item);
|
||
match &min_key {
|
||
Some(v) => {
|
||
if &item_key < v {
|
||
min_key = Some(item_key);
|
||
min_items.clear();
|
||
min_items.push(*item);
|
||
} else if &item_key == v {
|
||
min_items.push(*item);
|
||
}
|
||
}
|
||
None => {
|
||
min_key = Some(item_key);
|
||
min_items.clear();
|
||
min_items.push(*item);
|
||
}
|
||
}
|
||
}
|
||
return min_items;
|
||
}
|
||
|
||
/// Prompt the candidate for input, depending on CLI or WebAssembly target
|
||
#[cfg(not(target_arch = "wasm32"))]
|
||
pub fn prompt<'c, N: Number>(state: &CountState<N>, opts: &STVOptions, candidates: &[&'c Candidate], prompt_text: &str) -> Result<&'c Candidate, STVError> {
|
||
// Show intrastage progress if required
|
||
if !state.logger.entries.is_empty() {
|
||
// Print stage details
|
||
println!("Tie during: {}", state.title);
|
||
println!("{}", state.logger.render().join(" "));
|
||
|
||
// Print candidates
|
||
print!("{}", state.describe_candidates(opts));
|
||
|
||
// Print summary rows
|
||
print!("{}", state.describe_summary(opts));
|
||
|
||
println!();
|
||
}
|
||
|
||
println!("Multiple tied candidates:");
|
||
for (i, candidate) in candidates.iter().enumerate() {
|
||
println!("{}. {}", i + 1, candidate.name);
|
||
}
|
||
let mut buffer = String::new();
|
||
loop {
|
||
print!("{} [1-{}] ", prompt_text, candidates.len());
|
||
stdout().flush().expect("IO Error");
|
||
stdin().read_line(&mut buffer).expect("IO Error");
|
||
match buffer.trim().parse::<usize>() {
|
||
Ok(val) => {
|
||
if val >= 1 && val <= candidates.len() {
|
||
println!();
|
||
return Ok(candidates[val - 1]);
|
||
} else {
|
||
println!("Invalid selection");
|
||
continue;
|
||
}
|
||
}
|
||
Err(_) => {
|
||
println!("Invalid selection");
|
||
continue;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
#[cfg(target_arch = "wasm32")]
|
||
#[wasm_bindgen]
|
||
extern "C" {
|
||
fn get_user_input(s: &str) -> Option<String>;
|
||
}
|
||
|
||
/// Prompt the candidate for input, depending on CLI or WebAssembly target
|
||
#[cfg(target_arch = "wasm32")]
|
||
pub fn prompt<'c, N: Number>(state: &CountState<N>, opts: &STVOptions, candidates: &[&'c Candidate], prompt_text: &str) -> Result<&'c Candidate, STVError> {
|
||
let mut message = String::new();
|
||
|
||
// Show intrastage progress if required
|
||
if !state.logger.entries.is_empty() {
|
||
// Print stage details
|
||
message.push_str(&format!("Tie during: {}\n", state.title));
|
||
message.push_str(&state.logger.render().join(" "));
|
||
message.push('\n');
|
||
|
||
// Print candidates
|
||
message.push_str(&state.describe_candidates(opts));
|
||
message.push('\n');
|
||
|
||
// Print summary rows
|
||
message.push_str(&state.describe_summary(opts));
|
||
message.push('\n');
|
||
}
|
||
|
||
message.push_str(&"Multiple tied candidates:\n");
|
||
for (i, candidate) in candidates.iter().enumerate() {
|
||
message.push_str(&format!("{}. {}\n", i + 1, candidate.name));
|
||
}
|
||
message.push_str(&format!("{} [1-{}] ", prompt_text, candidates.len()));
|
||
|
||
loop {
|
||
let response = get_user_input(&message);
|
||
|
||
match response {
|
||
Some(response) => {
|
||
match response.trim().parse::<usize>() {
|
||
Ok(val) => {
|
||
if val >= 1 && val <= candidates.len() {
|
||
return Ok(candidates[val - 1]);
|
||
} else {
|
||
// Invalid selection
|
||
continue;
|
||
}
|
||
}
|
||
Err(_) => {
|
||
// Invalid selection
|
||
continue;
|
||
}
|
||
}
|
||
}
|
||
None => {
|
||
// No available user input in buffer - stack will be unwound
|
||
unreachable!();
|
||
}
|
||
}
|
||
}
|
||
}
|