RunasSudo
/
OpenTally
1
Fork 0
Code Issues 3 Pull Requests Activity

Implement constraints (guard-doom method) for CLI

This commit is contained in:
RunasSudo 2021-06-27 21:57:24 +10:00
parent c563654ace
commit 38eef74e77
Signed by: RunasSudo
GPG Key ID: 7234E476BF21C61A
14 changed files with 578 additions and 95 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

1
html/index.js
View File

@ -119,6 +119,7 @@ async function clickCount() {
document.getElementById('chkBulkExclusion').checked,
document.getElementById('chkDeferSurpluses').checked,
document.getElementById('chkMeekImmediateElect').checked,
"guard_doom",
parseInt(document.getElementById('txtPPDP').value),
];

296
src/constraints.rs
View File

@ -15,27 +15,155 @@
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
use crate::election::{Candidate, CandidateState, CountCard, Election};
use crate::numbers::Number;
use ndarray::{Array, Dimension, IxDyn};
use std::collections::HashMap;
use std::fmt;
use std::ops;
/// Constraints for an [crate::election::Election]
#[derive(Debug)]
enum ConstraintError {
pub struct Constraints(pub Vec<Constraint>);
impl Constraints {
/// Parse the given CON file and return a [Constraints]
pub fn from_con<I: Iterator<Item=String>>(lines: I) -> Self {
let mut constraints = Constraints(Vec::new());
for line in lines {
let mut bits = line.split(" ").peekable();
// Read constraint category
let mut constraint_name = String::new();
let x = bits.next().expect("Syntax Error");
if x.starts_with('"') {
if x.ends_with('"') {
constraint_name.push_str(&x[1..x.len()-1]);
} else {
constraint_name.push_str(&x[1..]);
while !bits.peek().expect("Syntax Error").ends_with('"') {
constraint_name.push_str(" ");
constraint_name.push_str(bits.next().unwrap());
}
let x = bits.next().unwrap();
constraint_name.push_str(" ");
constraint_name.push_str(&x[..x.len()-1]);
}
} else {
constraint_name.push_str(x);
}
// Read constraint group
let mut group_name = String::new();
let x = bits.next().expect("Syntax Error");
if x.starts_with('"') {
if x.ends_with('"') {
group_name.push_str(&x[1..x.len()-1]);
} else {
group_name.push_str(&x[1..]);
while !bits.peek().expect("Syntax Error").ends_with('"') {
group_name.push_str(" ");
group_name.push_str(bits.next().unwrap());
}
let x = bits.next().unwrap();
group_name.push_str(" ");
group_name.push_str(&x[..x.len()-1]);
}
} else {
group_name.push_str(x);
}
// Read min, max
let min: usize = bits.next().expect("Syntax Error").parse().expect("Syntax Error");
let max: usize = bits.next().expect("Syntax Error").parse().expect("Syntax Error");
// Read candidates
let mut candidates: Vec<usize> = Vec::new();
for x in bits {
candidates.push(x.parse::<usize>().expect("Syntax Error") - 1);
}
// Insert constraint/group
let constraint = match constraints.0.iter_mut().filter(|c| c.name == constraint_name).next() {
Some(c) => { c }
None => {
let c = Constraint {
name: constraint_name,
groups: Vec::new(),
};
constraints.0.push(c);
constraints.0.last_mut().unwrap()
}
};
if constraint.groups.iter().any(|g| g.name == group_name) {
panic!("Duplicate group \"{}\" in constraint \"{}\"", group_name, constraint.name);
}
constraint.groups.push(ConstrainedGroup {
name: group_name,
candidates: candidates,
min: min,
max: max,
});
}
// TODO: Validate constraints
return constraints;
}
}
/// A single dimension of constraint
#[derive(Debug)]
pub struct Constraint {
/// Name of this constraint
pub name: String,
/// Groups of candidates within this constraint
pub groups: Vec<ConstrainedGroup>,
}
/// A group of candidates, of which a certain minimum and maximum must be elected
#[derive(Debug)]
pub struct ConstrainedGroup {
/// Name of this group
pub name: String,
/// Indexes of [crate::election::Candidate]s to constrain
pub candidates: Vec<usize>,
/// Minimum number to elect
pub min: usize,
/// Maximum number to elect
pub max: usize,
}
/// Error reaching a stable state when processing constraints
#[derive(Debug)]
pub enum ConstraintError {
/// No conformant result is possible
NoConformantResult,
}
/// Cell in a [ConstraintMatrix]
#[derive(Clone)]
struct ConstraintMatrixCell {
elected: usize,
min: usize,
max: usize,
cands: usize,
pub struct ConstraintMatrixCell {
/// Number of elected candidates in this cell
pub elected: usize,
/// Minimum number of candidates which must be elected from this cell for a conformant result
pub min: usize,
/// Maximum number of candidates which may be elected from this cell for a conformant result
pub max: usize,
/// Total number of elected or hopeful candidates in this cell
pub cands: usize,
}
struct ConstraintMatrix(Array<ConstraintMatrixCell, IxDyn>);
/// Hypercube/tensor of [ConstraintMatrixCell]s representing the conformant combinations of elected candidates
pub struct ConstraintMatrix(pub Array<ConstraintMatrixCell, IxDyn>);
impl ConstraintMatrix {
/// Return a new [ConstraintMatrix], with the specified number of groups for each constraint dimension
pub fn new(constraints: &mut [usize]) -> Self {
// Add 1 to dimensions for totals cells
for c in constraints.iter_mut() {
@ -53,9 +181,8 @@ impl ConstraintMatrix {
));
}
/// Initialise the matrix once the number of candidates in each innermost cell, and min/max for each constraint group, have been specified
pub fn init(&mut self) {
let indices: Vec<IxDyn> = ndarray::indices(self.0.shape()).into_iter().collect();
// Compute candidate totals
self.recount_cands();
@ -64,30 +191,68 @@ impl ConstraintMatrix {
self.0[&idx].max = self.0[&idx].cands;
// Initialise max for inner cells (>=2 zeroes)
for idx in indices.iter() {
for idx in ndarray::indices(self.0.shape()) {
if (0..idx.ndim()).fold(0, |acc, d| if idx[d] != 0 { acc + 1 } else { acc }) < 2 {
continue;
}
self.0[idx].max = self.0[idx].cands;
self.0[&idx].max = self.0[&idx].cands;
}
// NB: Bounds on min, max, etc. will be further refined in initial step() calls
}
/// Update cands/elected in innermost cells based on the provided [CountState::candidates]
pub fn update_from_state<N: Number>(&mut self, election: &Election<N>, candidates: &HashMap<&Candidate, CountCard<N>>) {
let constraints = election.constraints.as_ref().unwrap();
// Reset innermost cells
for idx in ndarray::indices(self.0.shape()) {
if (0..idx.ndim()).fold(0, |acc, d| if idx[d] == 0 { acc + 1 } else { acc }) != 0 {
continue;
}
self.0[&idx].cands = 0;
self.0[&idx].elected = 0;
}
for (i, candidate) in election.candidates.iter().enumerate() {
let idx: Vec<usize> = constraints.0.iter().map(|c| {
for (j, group) in c.groups.iter().enumerate() {
if group.candidates.contains(&i) {
return j + 1;
}
}
panic!("Candidate \"{}\" not represented in constraint \"{}\"", candidate.name, c.name);
}).collect();
let cell = &mut self[&idx[..]];
let count_card = candidates.get(candidate).unwrap();
match count_card.state {
CandidateState::Hopeful | CandidateState::Guarded => {
cell.cands += 1;
}
CandidateState::Elected => {
cell.cands += 1;
cell.elected += 1;
}
CandidateState::Withdrawn | CandidateState::Doomed | CandidateState::Excluded => {}
}
}
}
/// Recompute [self::cands] and [self::elected] for totals cells based on the innermost cells
pub fn recount_cands(&mut self) {
let shape = Vec::from(self.0.shape());
let indices: Vec<IxDyn> = ndarray::indices(self.0.shape()).into_iter().collect();
// Compute cands/elected totals
for nzeroes in 1..self.0.ndim()+1 {
for idx in indices.iter() {
for idx in ndarray::indices(self.0.shape()) {
// First compute totals cells with 1 zero, then 2 zeroes, ... then grand total (all zeroes)
if (0..idx.ndim()).fold(0, |acc, d| if idx[d] == 0 { acc + 1 } else { acc }) != nzeroes {
continue;
}
self.0[idx].cands = 0;
self.0[idx].elected = 0;
self.0[&idx].cands = 0;
self.0[&idx].elected = 0;
// The axis along which to sum - if multiple, just pick the first, as these should agree
let zero_axis = (0..idx.ndim()).filter(|d| idx[*d] == 0).next().unwrap();
@ -96,19 +261,22 @@ impl ConstraintMatrix {
let mut idx2 = idx.clone();
for coord in 1..shape[zero_axis] {
idx2[zero_axis] = coord;
self.0[idx].cands += self.0[&idx2].cands;
self.0[idx].elected += self.0[&idx2].elected;
self.0[&idx].cands += self.0[&idx2].cands;
self.0[&idx].elected += self.0[&idx2].elected;
}
}
}
}
/// Attempt to advance the matrix one step towards a stable state
///
/// Returns `Ok(true)` if in a stable state, `Ok(false)` if not, and `ConstraintError` on an error.
///
pub fn step(&mut self) -> Result<bool, ConstraintError> {
let shape = Vec::from(self.0.shape());
let indices: Vec<IxDyn> = ndarray::indices(self.0.shape()).into_iter().collect();
for idx in indices.iter() {
let cell = &mut self.0[idx];
for idx in ndarray::indices(self.0.shape()) {
let cell = &mut self.0[&idx];
// Rule 1: Ensure elected < min < max < cands
if cell.min < cell.elected {
@ -125,7 +293,7 @@ impl ConstraintMatrix {
let nzeroes = (0..idx.ndim()).fold(0, |acc, d| if idx[d] == 0 { acc + 1 } else { acc });
// Rule 2/3: Ensure min/max is possible in inner cells
// Rule 2/3: Ensure min/max is possible in innermost cells
if nzeroes == 0 {
for axis in 0..self.0.ndim() {
let mut idx2 = idx.clone();
@ -148,12 +316,12 @@ impl ConstraintMatrix {
let this_max = (axis_max as i32) - (other_min as i32);
let this_min = (axis_min as i32) - (other_max as i32);
if this_max < (self.0[idx].max as i32) {
self.0[idx].max = this_max as usize;
if this_max < (self.0[&idx].max as i32) {
self.0[&idx].max = this_max as usize;
return Ok(false);
}
if this_min > (self.0[idx].min as i32) {
self.0[idx].min = this_min as usize;
if this_min > (self.0[&idx].min as i32) {
self.0[&idx].min = this_min as usize;
return Ok(false);
}
}
@ -173,12 +341,12 @@ impl ConstraintMatrix {
return (acc_max + self.0[&idx2].max, acc_min + self.0[&idx2].min);
});
if axis_max < self.0[idx].max {
self.0[idx].max = axis_max;
if axis_max < self.0[&idx].max {
self.0[&idx].max = axis_max;
return Ok(false);
}
if axis_min > self.0[idx].min {
self.0[idx].min = axis_min;
if axis_min > self.0[&idx].min {
self.0[&idx].min = axis_min;
return Ok(false);
}
}
@ -195,49 +363,93 @@ impl fmt::Display for ConstraintMatrix {
let mut result = String::new();
// TODO: ≠2 dimensions
for y in 0..shape[1] {
// TODO: >2 dimensions
if shape.len() == 1 {
result.push_str("+");
for _ in 0..shape[0] {
result.push_str(if y == 1 { "=============+" } else { "-------------+" });
result.push_str("-------------+");
}
result.push_str("\n");
result.push_str("|");
for x in 0..shape[0] {
result.push_str(&format!(" Elected: {:2}", self[&[x, y]].elected));
result.push_str(&format!(" Elected: {:2}", self[&[x]].elected));
result.push_str(if x == 0 { " ‖" } else { " |" });
}
result.push_str("\n");
result.push_str("|");
for x in 0..shape[0] {
result.push_str(&format!(" Min: {:2}", self[&[x, y]].min));
result.push_str(&format!(" Min: {:2}", self[&[x]].min));
result.push_str(if x == 0 { " ‖" } else { " |" });
}
result.push_str("\n");
result.push_str("|");
for x in 0..shape[0] {
result.push_str(&format!(" Max: {:2}", self[&[x, y]].max));
result.push_str(&format!(" Max: {:2}", self[&[x]].max));
result.push_str(if x == 0 { " ‖" } else { " |" });
}
result.push_str("\n");
result.push_str("|");
for x in 0..shape[0] {
result.push_str(&format!(" Cands: {:2}", self[&[x, y]].cands));
result.push_str(&format!(" Cands: {:2}", self[&[x]].cands));
result.push_str(if x == 0 { " ‖" } else { " |" });
}
result.push_str("\n");
result.push_str("+");
for _ in 0..shape[0] {
result.push_str("-------------+");
}
result.push_str("\n");
} else if shape.len() == 2 {
for y in 0..shape[1] {
result.push_str("+");
for _ in 0..shape[0] {
result.push_str(if y == 1 { "=============+" } else { "-------------+" });
}
result.push_str("\n");
result.push_str("|");
for x in 0..shape[0] {
result.push_str(&format!(" Elected: {:2}", self[&[x, y]].elected));
result.push_str(if x == 0 { " ‖" } else { " |" });
}
result.push_str("\n");
result.push_str("|");
for x in 0..shape[0] {
result.push_str(&format!(" Min: {:2}", self[&[x, y]].min));
result.push_str(if x == 0 { " ‖" } else { " |" });
}
result.push_str("\n");
result.push_str("|");
for x in 0..shape[0] {
result.push_str(&format!(" Max: {:2}", self[&[x, y]].max));
result.push_str(if x == 0 { " ‖" } else { " |" });
}
result.push_str("\n");
result.push_str("|");
for x in 0..shape[0] {
result.push_str(&format!(" Cands: {:2}", self[&[x, y]].cands));
result.push_str(if x == 0 { " ‖" } else { " |" });
}
result.push_str("\n");
}
result.push_str("+");
for _ in 0..shape[0] {
result.push_str("-------------+");
}
result.push_str("\n");
} else {
todo!();
}
result.push_str("+");
for _ in 0..shape[0] {
result.push_str("-------------+");
}
result.push_str("\n");
return f.write_str(&result);
}
}

31
src/election.rs
View File

@ -15,6 +15,7 @@
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
use crate::constraints::{Constraints, ConstraintMatrix};
use crate::logger::Logger;
use crate::numbers::Number;
use crate::sharandom::SHARandom;
@ -33,6 +34,8 @@ pub struct Election<N> {
pub withdrawn_candidates: Vec<usize>,
/// [Vec] of [Ballot]s cast in the election
pub ballots: Vec<Ballot<N>>,
/// Constraints on candidates
pub constraints: Option<Constraints>,
}
impl<N: Number> Election<N> {
@ -51,6 +54,7 @@ impl<N: Number> Election<N> {
candidates: Vec::with_capacity(num_candidates),
withdrawn_candidates: Vec::new(),
ballots: Vec::new(),
constraints: None,
};
// Read ballots
@ -169,6 +173,9 @@ pub struct CountState<'a, N: Number> {
/// Number of candidates who have been declared excluded
pub num_excluded: usize,
/// [ConstraintMatrix] for constrained elections
pub constraint_matrix: Option<ConstraintMatrix>,
/// The type of stage being counted
///
/// For example, "Surplus of", "Exclusion of"
@ -195,6 +202,7 @@ impl<'a, N: Number> CountState<'a, N> {
vote_required_election: None,
num_elected: 0,
num_excluded: 0,
constraint_matrix: None,
kind: None,
title: String::new(),
logger: Logger { entries: Vec::new() },
@ -208,6 +216,29 @@ impl<'a, N: Number> CountState<'a, N> {
state.candidates.get_mut(&election.candidates[*withdrawn_idx]).unwrap().state = CandidateState::Withdrawn;
}
if let Some(constraints) = &election.constraints {
let mut num_groups: Vec<usize> = constraints.0.iter().map(|c| c.groups.len()).collect();
let mut cm = ConstraintMatrix::new(&mut num_groups[..]);
// Init constraint matrix total cells min/max
for (i, constraint) in constraints.0.iter().enumerate() {
for (j, group) in constraint.groups.iter().enumerate() {
let mut idx = vec![0; constraints.0.len()];
idx[i] = j + 1;
let mut cell = &mut cm[&idx];
cell.min = group.min;
cell.max = group.max;
}
}
// Fill in grand total, etc.
cm.update_from_state(&state.election, &state.candidates);
cm.init();
//println!("{}", cm);
state.constraint_matrix = Some(cm);
}
return state;
}

76
src/main.rs
View File

@ -15,9 +15,10 @@
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
use opentally::stv;
use opentally::constraints::Constraints;
use opentally::election::{Candidate, CandidateState, CountCard, CountState, CountStateOrRef, Election, StageResult};
use opentally::numbers::{Fixed, GuardedFixed, NativeFloat64, Number, Rational};
use opentally::stv;
use clap::{AppSettings, Clap};
@ -156,6 +157,17 @@ struct STV {
#[clap(help_heading=Some("COUNT OPTIMISATIONS"), long)]
meek_immediate_elect: bool,
// -----------------
// -- Constraints --
/// Path to a CON file specifying constraints
#[clap(help_heading=Some("CONSTRAINTS"), long)]
constraints: Option<String>,
/// Mode of handling constraints
#[clap(help_heading=Some("CONSTRAINTS"), long, possible_values=&["guard_doom"], default_value="guard_doom")]
constraint_mode: String,
// ----------------------
// -- Display settings --
@ -183,23 +195,37 @@ fn main() {
// Create and count election according to --numbers
if cmd_opts.numbers == "rational" {
let election: Election<Rational> = Election::from_blt(lines.map(|r| r.expect("IO Error").to_string()).into_iter());
let mut election: Election<Rational> = Election::from_blt(lines.map(|r| r.expect("IO Error").to_string()).into_iter());
maybe_load_constraints(&mut election, &cmd_opts.constraints);
// Must specify ::<N> here and in a few other places because ndarray causes E0275 otherwise
count_election::<Rational>(election, cmd_opts);
} else if cmd_opts.numbers == "float64" {
let election: Election<NativeFloat64> = Election::from_blt(lines.map(|r| r.expect("IO Error").to_string()).into_iter());
let mut election: Election<NativeFloat64> = Election::from_blt(lines.map(|r| r.expect("IO Error").to_string()).into_iter());
maybe_load_constraints(&mut election, &cmd_opts.constraints);
count_election::<NativeFloat64>(election, cmd_opts);
} else if cmd_opts.numbers == "fixed" {
Fixed::set_dps(cmd_opts.decimals);
let election: Election<Fixed> = Election::from_blt(lines.map(|r| r.expect("IO Error").to_string()).into_iter());
let mut election: Election<Fixed> = Election::from_blt(lines.map(|r| r.expect("IO Error").to_string()).into_iter());
maybe_load_constraints(&mut election, &cmd_opts.constraints);
count_election::<Fixed>(election, cmd_opts);
} else if cmd_opts.numbers == "gfixed" {
GuardedFixed::set_dps(cmd_opts.decimals);
let election: Election<GuardedFixed> = Election::from_blt(lines.map(|r| r.expect("IO Error").to_string()).into_iter());
let mut election: Election<GuardedFixed> = Election::from_blt(lines.map(|r| r.expect("IO Error").to_string()).into_iter());
maybe_load_constraints(&mut election, &cmd_opts.constraints);
count_election::<GuardedFixed>(election, cmd_opts);
}
}
fn maybe_load_constraints<N: Number>(election: &mut Election<N>, constraints: &Option<String>) {
if let Some(c) = constraints {
let file = File::open(c).expect("IO Error");
let lines = io::BufReader::new(file).lines();
election.constraints = Some(Constraints::from_con(lines.map(|r| r.expect("IO Error").to_string()).into_iter()));
}
}
fn count_election<N: Number>(mut election: Election<N>, cmd_opts: STV)
where
for<'r> &'r N: ops::Sub<&'r N, Output=N>,
@ -230,6 +256,7 @@ where
cmd_opts.bulk_exclude,
cmd_opts.defer_surpluses,
cmd_opts.meek_immediate_elect,
&cmd_opts.constraint_mode,
cmd_opts.pp_decimals,
);
@ -290,23 +317,34 @@ where
fn print_candidates<'a, N: 'a + Number, I: Iterator<Item=(&'a Candidate, &'a CountCard<'a, N>)>>(candidates: I, cmd_opts: &STV) {
for (candidate, count_card) in candidates {
if count_card.state == CandidateState::Elected {
if let Some(kv) = &count_card.keep_value {
println!("- {}: {:.dps$} ({:.dps$}) - ELECTED {} (kv = {:.dps2$})", candidate.name, count_card.votes, count_card.transfers, count_card.order_elected, kv, dps=cmd_opts.pp_decimals, dps2=max(cmd_opts.pp_decimals, 2));
} else {
println!("- {}: {:.dps$} ({:.dps$}) - ELECTED {}", candidate.name, count_card.votes, count_card.transfers, count_card.order_elected, dps=cmd_opts.pp_decimals);
match count_card.state {
CandidateState::Hopeful => {
println!("- {}: {:.dps$} ({:.dps$})", candidate.name, count_card.votes, count_card.transfers, dps=cmd_opts.pp_decimals);
}
} else if count_card.state == CandidateState::Excluded {
// If --hide-excluded, hide unless nonzero votes or nonzero transfers
if !cmd_opts.hide_excluded || !count_card.votes.is_zero() || !count_card.transfers.is_zero() {
println!("- {}: {:.dps$} ({:.dps$}) - Excluded {}", candidate.name, count_card.votes, count_card.transfers, -count_card.order_elected, dps=cmd_opts.pp_decimals);
CandidateState::Guarded => {
println!("- {}: {:.dps$} ({:.dps$}) - Guarded", candidate.name, count_card.votes, count_card.transfers, dps=cmd_opts.pp_decimals);
}
} else if count_card.state == CandidateState::Withdrawn {
if !cmd_opts.hide_excluded || !count_card.votes.is_zero() || !count_card.transfers.is_zero() {
println!("- {}: {:.dps$} ({:.dps$}) - Withdrawn", candidate.name, count_card.votes, count_card.transfers, dps=cmd_opts.pp_decimals);
CandidateState::Elected => {
if let Some(kv) = &count_card.keep_value {
println!("- {}: {:.dps$} ({:.dps$}) - ELECTED {} (kv = {:.dps2$})", candidate.name, count_card.votes, count_card.transfers, count_card.order_elected, kv, dps=cmd_opts.pp_decimals, dps2=max(cmd_opts.pp_decimals, 2));
} else {
println!("- {}: {:.dps$} ({:.dps$}) - ELECTED {}", candidate.name, count_card.votes, count_card.transfers, count_card.order_elected, dps=cmd_opts.pp_decimals);
}
}
CandidateState::Doomed => {
println!("- {}: {:.dps$} ({:.dps$}) - Doomed", candidate.name, count_card.votes, count_card.transfers, dps=cmd_opts.pp_decimals);
}
CandidateState::Withdrawn => {
if !cmd_opts.hide_excluded || !count_card.votes.is_zero() || !count_card.transfers.is_zero() {
println!("- {}: {:.dps$} ({:.dps$}) - Withdrawn", candidate.name, count_card.votes, count_card.transfers, dps=cmd_opts.pp_decimals);
}
}
CandidateState::Excluded => {
// If --hide-excluded, hide unless nonzero votes or nonzero transfers
if !cmd_opts.hide_excluded || !count_card.votes.is_zero() || !count_card.transfers.is_zero() {
println!("- {}: {:.dps$} ({:.dps$}) - Excluded {}", candidate.name, count_card.votes, count_card.transfers, -count_card.order_elected, dps=cmd_opts.pp_decimals);
}
}
} else {
println!("- {}: {:.dps$} ({:.dps$})", candidate.name, count_card.votes, count_card.transfers, dps=cmd_opts.pp_decimals);
}
}
}

4
src/stv/gregory.rs
View File

@ -360,6 +360,8 @@ where
count_card.state = CandidateState::Excluded;
state.num_excluded += 1;
count_card.order_elected = -(order_excluded as isize);
super::update_constraints(state, opts);
}
}
@ -518,6 +520,8 @@ where
state.num_excluded += 1;
count_card.order_elected = -(order_excluded as isize);
}
super::update_constraints(state, opts);
}
// Reset count

244
src/stv/mod.rs
View File

@ -27,11 +27,12 @@ pub mod meek;
pub mod wasm;
use crate::numbers::Number;
use crate::election::{Candidate, CandidateState, CountCard, CountState, Vote};
use crate::election::{Candidate, CandidateState, CountCard, CountState, Election, Vote};
use crate::sharandom::SHARandom;
use crate::ties::TieStrategy;
use itertools::Itertools;
use ndarray::Dimension;
use wasm_bindgen::prelude::wasm_bindgen;
use std::collections::HashMap;
@ -79,6 +80,8 @@ pub struct STVOptions {
pub defer_surpluses: bool,
/// (Meek STV) Immediately elect candidates even if keep values have not converged
pub meek_immediate_elect: bool,
/// Mode of handling constraints
pub constraint_mode: ConstraintMode,
/// Print votes to specified decimal places in results report
pub pp_decimals: usize,
}
@ -107,6 +110,7 @@ impl STVOptions {
bulk_exclude: bool,
defer_surpluses: bool,
meek_immediate_elect: bool,
constraint_mode: &str,
pp_decimals: usize,
) -> Self {
return STVOptions {
@ -171,6 +175,11 @@ impl STVOptions {
bulk_exclude,
defer_surpluses,
meek_immediate_elect,
constraint_mode: match constraint_mode {
"guard_doom" => ConstraintMode::GuardDoom,
"rollback" => ConstraintMode::Rollback,
_ => panic!("Invalid --constraint-mode"),
},
pp_decimals,
};
}
@ -382,6 +391,14 @@ impl ExclusionMethod {
}
}
/// Enum of options for [STVOptions::constraint_mode]
pub enum ConstraintMode {
/// Guard or doom candidates as soon as required to secure a conformant result
GuardDoom,
/// TODO: NYI
Rollback,
}
/// An error during the STV count
#[wasm_bindgen]
#[derive(Debug)]
@ -442,6 +459,14 @@ where
return Ok(false);
}
// Exclude doomed candidates
if exclude_doomed(&mut state, &opts)? {
calculate_quota(&mut state, opts);
elect_meeting_quota(&mut state, opts);
update_tiebreaks(&mut state, opts);
return Ok(false);
}
// Distribute surpluses
if distribute_surpluses(&mut state, &opts)? {
calculate_quota(&mut state, opts);
@ -681,43 +706,153 @@ fn meets_quota<N: Number>(quota: &N, count_card: &CountCard<N>, opts: &STVOption
/// Declare elected all candidates meeting the quota
fn elect_meeting_quota<N: Number>(state: &mut CountState<N>, opts: &STVOptions) -> bool {
let vote_req = state.vote_required_election.as_ref().unwrap(); // Have to do this or else the borrow checker gets confused
let vote_req = state.vote_required_election.as_ref().unwrap().clone(); // Have to do this or else the borrow checker gets confused
let mut cands_meeting_quota: Vec<&Candidate> = state.election.candidates.iter()
.filter(|c| { let cc = state.candidates.get(c).unwrap(); cc.state == CandidateState::Hopeful && meets_quota(vote_req, cc, opts) })
.filter(|c| {
let cc = state.candidates.get(c).unwrap();
return (cc.state == CandidateState::Hopeful || cc.state == CandidateState::Guarded) && meets_quota(&vote_req, cc, opts);
})
.collect();
if !cands_meeting_quota.is_empty() {
// Sort by votes
cands_meeting_quota.sort_unstable_by(|a, b| state.candidates.get(a).unwrap().votes.cmp(&state.candidates.get(b).unwrap().votes));
// Sort by votes
cands_meeting_quota.sort_unstable_by(|a, b| state.candidates.get(a).unwrap().votes.cmp(&state.candidates.get(b).unwrap().votes));
let elected = !cands_meeting_quota.is_empty();
while !cands_meeting_quota.is_empty() {
// Declare elected in descending order of votes
for candidate in cands_meeting_quota.into_iter().rev() {
let count_card = state.candidates.get_mut(candidate).unwrap();
count_card.state = CandidateState::Elected;
state.num_elected += 1;
count_card.order_elected = state.num_elected as isize;
state.logger.log_smart(
"{} meets the quota and is elected.",
"{} meet the quota and are elected.",
vec![&candidate.name]
);
if opts.quota_mode == QuotaMode::ERS97 {
// Vote required for election may have changed
calculate_quota(state, opts);
}
let candidate = cands_meeting_quota.pop().unwrap();
let count_card = state.candidates.get_mut(candidate).unwrap();
count_card.state = CandidateState::Elected;
state.num_elected += 1;
count_card.order_elected = state.num_elected as isize;
state.logger.log_smart(
"{} meets the quota and is elected.",
"{} meet the quota and are elected.",
vec![&candidate.name]
);
if update_constraints(state, opts) {
// Recheck as some candidates may have been doomed
cands_meeting_quota = state.election.candidates.iter()
.filter(|c| { let cc = state.candidates.get(c).unwrap(); cc.state == CandidateState::Hopeful && meets_quota(&vote_req, cc, opts) })
.collect();
cands_meeting_quota.sort_unstable_by(|a, b| state.candidates.get(a).unwrap().votes.cmp(&state.candidates.get(b).unwrap().votes));
}
if opts.quota_mode == QuotaMode::ERS97 {
// Vote required for election may have changed
calculate_quota(state, opts);
}
if opts.quota_mode == QuotaMode::ERS97 {
// Repeat in case vote required for election has changed
//calculate_quota(state, opts);
elect_meeting_quota(state, opts);
}
return true;
}
return false;
return elected;
}
fn candidates_in_constraint_cell<'a, N: Number>(election: &'a Election<N>, candidates: &HashMap<&Candidate, CountCard<N>>, idx: &[usize]) -> Vec<&'a Candidate> {
let mut result: Vec<&Candidate> = Vec::new();
for (i, candidate) in election.candidates.iter().enumerate() {
let cc = candidates.get(candidate).unwrap();
if cc.state != CandidateState::Hopeful {
continue;
}
// Is this candidate within this constraint cell?
let mut matches = true;
for (coord, constraint) in idx.iter().zip(election.constraints.as_ref().unwrap().0.iter()) {
let group = &constraint.groups[coord - 1]; // The group referred to by this constraint cell
if !group.candidates.contains(&i) {
matches = false;
break;
}
}
if matches {
result.push(candidate);
}
}
return result;
}
fn update_constraints<N: Number>(state: &mut CountState<N>, opts: &STVOptions) -> bool {
if state.constraint_matrix.is_none() {
return false;
}
let cm = state.constraint_matrix.as_mut().unwrap();
// Update cands/elected
cm.update_from_state(&state.election, &state.candidates);
cm.recount_cands();
// Iterate for stable state
//println!("{}", cm);
while !cm.step().expect("No conformant result") {
//println!("{}", cm);
}
//println!("{}", cm);
// TODO: Refactor and move this to constraints module?
match opts.constraint_mode {
ConstraintMode::GuardDoom => {
// Check for guarded or doomed candidates
let mut guarded_or_doomed = false;
for idx in ndarray::indices(cm.0.shape()) {
if (0..idx.ndim()).fold(0, |acc, d| if idx[d] == 0 { acc + 1 } else { acc }) != 0 {
continue;
}
let cell = &cm.0[&idx];
if cell.elected == cell.max {
// Doom remaining candidates in this cell
let doomed = candidates_in_constraint_cell(state.election, &state.candidates, idx.slice());
if !doomed.is_empty() {
for candidate in doomed.iter() {
state.candidates.get_mut(candidate).unwrap().state = CandidateState::Doomed;
}
state.logger.log_smart(
"{} must be doomed to comply with constraints.",
"{} must be doomed to comply with constraints.",
doomed.iter().map(|c| c.name.as_str()).collect()
);
guarded_or_doomed = true;
}
}
if cell.cands == cell.min {
// Guard remaining candidates in this cell
let guarded = candidates_in_constraint_cell(state.election, &state.candidates, idx.slice());
if !guarded.is_empty() {
for candidate in guarded.iter() {
state.candidates.get_mut(candidate).unwrap().state = CandidateState::Guarded;
}
state.logger.log_smart(
"{} must be guarded to comply with constraints.",
"{} must be guarded to comply with constraints.",
guarded.iter().map(|c| c.name.as_str()).collect()
);
guarded_or_doomed = true;
}
}
}
return guarded_or_doomed;
}
_ => { todo!() }
}
//return false;
}
/// Determine whether the transfer of all surpluses can be deferred
@ -777,7 +912,10 @@ fn bulk_elect<N: Number>(state: &mut CountState<N>, opts: &STVOptions) -> Result
// Bulk elect all remaining candidates
let mut hopefuls: Vec<&Candidate> = state.election.candidates.iter()
.filter(|c| state.candidates.get(c).unwrap().state == CandidateState::Hopeful)
.filter(|c| {
let cc = state.candidates.get(c).unwrap();
return cc.state == CandidateState::Hopeful || cc.state == CandidateState::Guarded;
})
.collect();
while !hopefuls.is_empty() {
@ -810,6 +948,8 @@ fn bulk_elect<N: Number>(state: &mut CountState<N>, opts: &STVOptions) -> Result
);
hopefuls.remove(hopefuls.iter().position(|c| *c == candidate).unwrap());
update_constraints(state, opts);
}
return Ok(true);
@ -817,6 +957,53 @@ fn bulk_elect<N: Number>(state: &mut CountState<N>, opts: &STVOptions) -> Result
return Ok(false);
}
fn exclude_doomed<'a, N: Number>(state: &mut CountState<'a, N>, opts: &STVOptions) -> Result<bool, STVError>
where
for<'r> &'r N: ops::Sub<&'r N, Output=N>,
for<'r> &'r N: ops::Mul<&'r N, Output=N>,
for<'r> &'r N: ops::Div<&'r N, Output=N>,
{
let mut doomed: Vec<(&Candidate, &CountCard<N>)> = state.election.candidates.iter() // Present in order in case of tie
.map(|c| (c, state.candidates.get(c).unwrap()))
.filter(|(_, cc)| cc.state == CandidateState::Doomed)
.collect();
if !doomed.is_empty() {
let excluded_candidates;
if opts.bulk_exclude {
excluded_candidates = doomed.into_iter().map(|(c, _)| c).collect();
} else {
// Exclude only the lowest-ranked doomed candidate
// Sort by votes
doomed.sort_by(|a, b| a.1.votes.cmp(&b.1.votes));
// Handle ties
if doomed.len() > 1 && doomed[0].1.votes == doomed[1].1.votes {
let min_votes = &doomed[0].1.votes;
let doomed = doomed.into_iter().filter_map(|(c, cc)| if &cc.votes == min_votes { Some(c) } else { None }).collect();
excluded_candidates = vec![choose_lowest(state, opts, doomed)?];
} else {
excluded_candidates = vec![&doomed[0].0];
}
}
let names: Vec<&str> = excluded_candidates.iter().map(|c| c.name.as_str()).collect();
state.kind = Some("Exclusion of");
state.title = names.join(", ");
state.logger.log_smart(
"Doomed candidate, {}, is excluded.",
"Doomed candidates, {}, are excluded.",
names
);
exclude_candidates(state, opts, excluded_candidates);
return Ok(true);
}
return Ok(false);
}
/// Determine which continuing candidates could be excluded in a bulk exclusion
///
/// The value of [STVOptions::bulk_exclude] is not taken into account and must be handled by the caller
@ -893,8 +1080,7 @@ where
}
}
let mut names: Vec<&str> = excluded_candidates.iter().map(|c| c.name.as_str()).collect();
names.sort();
let names: Vec<&str> = excluded_candidates.iter().map(|c| c.name.as_str()).collect();
state.kind = Some("Exclusion of");
state.title = names.join(", ");
state.logger.log_smart(

6
src/stv/wasm.rs
View File

@ -188,7 +188,7 @@ impl STVOptions {
round_votes: Option<usize>,
round_quota: Option<usize>,
sum_surplus_transfers: &str,
meek_surplus_limit: &str,
meek_surplus_tolerance: &str,
normalise_ballots: bool,
quota: &str,
quota_criterion: &str,
@ -204,6 +204,7 @@ impl STVOptions {
bulk_exclude: bool,
defer_surpluses: bool,
meek_immediate_elect: bool,
constraint_mode: &str,
pp_decimals: usize,
) -> Self {
Self(stv::STVOptions::new(
@ -212,7 +213,7 @@ impl STVOptions {
round_votes,
round_quota,
sum_surplus_transfers,
meek_surplus_limit,
meek_surplus_tolerance,
normalise_ballots,
quota,
quota_criterion,
@ -228,6 +229,7 @@ impl STVOptions {
bulk_exclude,
defer_surpluses,
meek_immediate_elect,
constraint_mode,
pp_decimals,
))
}

1
tests/aec.rs
View File

@ -75,6 +75,7 @@ fn aec_tas19_rational() {
bulk_exclude: true,
defer_surpluses: false,
meek_immediate_elect: false,
constraint_mode: stv::ConstraintMode::GuardDoom,
pp_decimals: 2,
};
utils::validate_election::<Rational>(stages, records, election, stv_opts, None, &["exhausted", "lbf"]);

1
tests/csm.rs
View File

@ -43,6 +43,7 @@ fn csm15_float64() {
bulk_exclude: true,
defer_surpluses: false,
meek_immediate_elect: false,
constraint_mode: stv::ConstraintMode::GuardDoom,
pp_decimals: 2,
};
utils::read_validate_election::<NativeFloat64>("tests/data/CSM15.csv", "tests/data/CSM15.blt", stv_opts, Some(6), &["quota"]);

1
tests/ers97.rs
View File

@ -43,6 +43,7 @@ fn ers97_rational() {
bulk_exclude: true,
defer_surpluses: true,
meek_immediate_elect: false,
constraint_mode: stv::ConstraintMode::GuardDoom,
pp_decimals: 2,
};
utils::read_validate_election::<Rational>("tests/data/ers97.csv", "tests/data/ers97.blt", stv_opts, None, &["nt", "vre"]);

3
tests/meek.rs
View File

@ -48,6 +48,7 @@ fn meek87_ers97_float64() {
bulk_exclude: false,
defer_surpluses: false,
meek_immediate_elect: false,
constraint_mode: stv::ConstraintMode::GuardDoom,
pp_decimals: 2,
};
utils::read_validate_election::<NativeFloat64>("tests/data/ers97_meek.csv", "tests/data/ers97.blt", stv_opts, Some(2), &["exhausted", "quota"]);
@ -77,6 +78,7 @@ fn meek06_ers97_fixed12() {
bulk_exclude: false,
defer_surpluses: true,
meek_immediate_elect: true,
constraint_mode: stv::ConstraintMode::GuardDoom,
pp_decimals: 2,
};
Fixed::set_dps(12);
@ -151,6 +153,7 @@ fn meeknz_ers97_fixed12() {
bulk_exclude: false,
defer_surpluses: true,
meek_immediate_elect: true,
constraint_mode: stv::ConstraintMode::GuardDoom,
pp_decimals: 2,
};
Fixed::set_dps(12);

1
tests/prsa.rs
View File

@ -43,6 +43,7 @@ fn prsa1_rational() {
bulk_exclude: false,
defer_surpluses: false,
meek_immediate_elect: false,
constraint_mode: stv::ConstraintMode::GuardDoom,
pp_decimals: 2,
};
utils::read_validate_election::<Rational>("tests/data/prsa1.csv", "tests/data/prsa1.blt", stv_opts, None, &["exhausted", "lbf"]);

2
tests/scotland.rs
View File

@ -50,6 +50,7 @@ fn scotland_linn07_fixed5() {
bulk_exclude: false,
defer_surpluses: false,
meek_immediate_elect: false,
constraint_mode: stv::ConstraintMode::GuardDoom,
pp_decimals: 5,
};
Fixed::set_dps(5);
@ -79,6 +80,7 @@ fn scotland_linn07_gfixed5() {
bulk_exclude: false,
defer_surpluses: false,
meek_immediate_elect: false,
constraint_mode: stv::ConstraintMode::GuardDoom,
pp_decimals: 5,
};
GuardedFixed::set_dps(5);

6
tests/utils/mod.rs
View File

@ -142,11 +142,11 @@ where
if candidate_state == "" {
}
else if candidate_state == "H" {
assert!(count_card.state == CandidateState::Hopeful);
assert!(count_card.state == CandidateState::Hopeful, "Unexpected state for \"{}\" at index {}", candidate.name, idx);
} else if candidate_state == "EL" || candidate_state == "PEL" {
assert!(count_card.state == CandidateState::Elected);
assert!(count_card.state == CandidateState::Elected, "Unexpected state for \"{}\" at index {}", candidate.name, idx);
} else if candidate_state == "EX" || candidate_state == "EXCLUDING" {
assert!(count_card.state == CandidateState::Excluded);
assert!(count_card.state == CandidateState::Excluded, "Unexpected state for \"{}\" at index {}", candidate.name, idx);
} else {
panic!("Unknown state descriptor {}", candidate_state);
}