Implement forwards and backwards tie-breaking

This commit is contained in:
RunasSudo 2021-06-13 00:15:14 +10:00
parent 5d491687b4
commit 2dc5ed963b
Signed by: RunasSudo
GPG Key ID: 7234E476BF21C61A
9 changed files with 316 additions and 68 deletions

View File

@ -131,6 +131,9 @@ pub struct CountState<'a, N> {
pub exhausted: CountCard<'a, N>,
pub loss_fraction: CountCard<'a, N>,
pub forwards_tiebreak: Option<HashMap<&'a Candidate, usize>>,
pub backwards_tiebreak: Option<HashMap<&'a Candidate, usize>>,
pub quota: Option<N>,
pub vote_required_election: Option<N>,
@ -149,6 +152,8 @@ impl<'a, N: Number> CountState<'a, N> {
candidates: HashMap::new(),
exhausted: CountCard::new(),
loss_fraction: CountCard::new(),
forwards_tiebreak: None,
backwards_tiebreak: None,
quota: None,
vote_required_election: None,
num_elected: 0,

View File

@ -104,6 +104,10 @@ struct STV {
// ------------------
// -- STV variants --
/// Tie-breaking method
#[clap(help_heading=Some("STV VARIANTS"), short='t', long, possible_values=&["forwards", "backwards", "random", "prompt"], default_value="prompt", value_name="methods")]
ties: Vec<String>,
/// Method of surplus distributions
#[clap(help_heading=Some("STV VARIANTS"), short='s', long, possible_values=&["wig", "uig", "eg", "meek"], default_value="wig", value_name="method")]
surplus: String,
@ -187,6 +191,7 @@ where
&cmd_opts.quota,
&cmd_opts.quota_criterion,
&cmd_opts.quota_mode,
&cmd_opts.ties,
&cmd_opts.surplus,
&cmd_opts.surplus_order,
cmd_opts.transferable_only,

View File

@ -31,8 +31,7 @@ use std::cmp::max;
use std::collections::HashMap;
use std::ops;
#[wasm_bindgen]
pub struct STVOptions {
pub struct STVOptions<'o> {
pub round_tvs: Option<usize>,
pub round_weights: Option<usize>,
pub round_votes: Option<usize>,
@ -42,6 +41,7 @@ pub struct STVOptions {
pub quota: QuotaType,
pub quota_criterion: QuotaCriterion,
pub quota_mode: QuotaMode,
pub ties: Vec<TieStrategy<'o>>,
pub surplus: SurplusMethod,
pub surplus_order: SurplusOrder,
pub transferable_only: bool,
@ -51,8 +51,7 @@ pub struct STVOptions {
pub pp_decimals: usize,
}
#[wasm_bindgen]
impl STVOptions {
impl<'o> STVOptions<'o> {
pub fn new(
round_tvs: Option<usize>,
round_weights: Option<usize>,
@ -63,6 +62,7 @@ impl STVOptions {
quota: &str,
quota_criterion: &str,
quota_mode: &str,
ties: &Vec<String>,
surplus: &str,
surplus_order: &str,
transferable_only: bool,
@ -100,6 +100,13 @@ impl STVOptions {
"ers97" => QuotaMode::ERS97,
_ => panic!("Invalid --quota-mode"),
},
ties: ties.into_iter().map(|t| match t.as_str() {
"forwards" => TieStrategy::Forwards,
"backwards" => TieStrategy::Backwards,
"random" => todo!(),
"prompt" => TieStrategy::Prompt,
_ => panic!("Invalid --ties"),
}).collect(),
surplus: match surplus {
"wig" => SurplusMethod::WIG,
"uig" => SurplusMethod::UIG,
@ -124,19 +131,18 @@ impl STVOptions {
pp_decimals,
};
}
}
impl STVOptions {
// Not exported to WebAssembly
pub fn describe<N: Number>(&self) -> String {
let mut flags = Vec::new();
let n_str = N::describe_opt(); if n_str.len() > 0 { flags.push(N::describe_opt()) };
let n_str = N::describe_opt(); if !n_str.is_empty() { flags.push(N::describe_opt()) };
if let Some(dps) = self.round_tvs { flags.push(format!("--round-tvs {}", dps)); }
if let Some(dps) = self.round_weights { flags.push(format!("--round-weights {}", dps)); }
if let Some(dps) = self.round_votes { flags.push(format!("--round-votes {}", dps)); }
if let Some(dps) = self.round_quota { flags.push(format!("--round-quota {}", dps)); }
if self.sum_surplus_transfers != SumSurplusTransfersMode::SingleStep { flags.push(self.sum_surplus_transfers.describe()); }
if self.normalise_ballots { flags.push("--normalise-ballots".to_string()); }
let ties_str = self.ties.iter().map(|t| t.describe()).join(" ");
if ties_str != "prompt" { flags.push(format!("--ties {}", ties_str)); }
if self.quota != QuotaType::DroopExact { flags.push(self.quota.describe()); }
if self.quota_criterion != QuotaCriterion::Greater { flags.push(self.quota_criterion.describe()); }
if self.quota_mode != QuotaMode::Static { flags.push(self.quota_mode.describe()); }
@ -286,12 +292,14 @@ impl ExclusionMethod {
#[derive(Debug)]
pub enum STVError {
RequireInput,
UnresolvedTie,
}
pub fn count_init<N: Number>(mut state: &mut CountState<'_, N>, opts: &STVOptions) {
distribute_first_preferences(&mut state);
calculate_quota(&mut state, opts);
elect_meeting_quota(&mut state, opts);
init_tiebreaks(&mut state, opts);
}
pub fn count_one_stage<'a, N: Number>(mut state: &mut CountState<'a, N>, opts: &STVOptions) -> Result<bool, STVError>
@ -312,6 +320,7 @@ where
if continue_exclusion(&mut state, &opts) {
calculate_quota(&mut state, opts);
elect_meeting_quota(&mut state, opts);
update_tiebreaks(&mut state, opts);
return Ok(false);
}
@ -319,11 +328,12 @@ where
if distribute_surpluses(&mut state, &opts)? {
calculate_quota(&mut state, opts);
elect_meeting_quota(&mut state, opts);
update_tiebreaks(&mut state, opts);
return Ok(false);
}
// Attempt bulk election
if bulk_elect(&mut state) {
if bulk_elect(&mut state, &opts)? {
return Ok(false);
}
@ -331,6 +341,7 @@ where
if exclude_hopefuls(&mut state, &opts)? {
calculate_quota(&mut state, opts);
elect_meeting_quota(&mut state, opts);
update_tiebreaks(&mut state, opts);
return Ok(false);
}
@ -562,9 +573,9 @@ fn elect_meeting_quota<N: Number>(state: &mut CountState<N>, opts: &STVOptions)
.filter(|c| { let cc = state.candidates.get(c).unwrap(); cc.state == CandidateState::Hopeful && meets_quota(vote_req, cc, opts) })
.collect();
if cands_meeting_quota.len() > 0 {
if !cands_meeting_quota.is_empty() {
// Sort by votes
cands_meeting_quota.sort_unstable_by(|a, b| state.candidates.get(a).unwrap().votes.partial_cmp(&state.candidates.get(b).unwrap().votes).unwrap());
cands_meeting_quota.sort_unstable_by(|a, b| state.candidates.get(a).unwrap().votes.cmp(&state.candidates.get(b).unwrap().votes));
// Declare elected in descending order of votes
for candidate in cands_meeting_quota.into_iter().rev() {
@ -634,7 +645,7 @@ where
let total_surpluses = has_surplus.iter()
.fold(N::new(), |acc, (_, cc)| acc + &cc.votes - quota);
if has_surplus.len() > 0 {
if !has_surplus.is_empty() {
// Determine if surplues can be deferred
if opts.defer_surpluses {
if can_defer_surpluses(state, opts, &total_surpluses) {
@ -646,10 +657,10 @@ where
match opts.surplus_order {
SurplusOrder::BySize => {
// Compare b with a to sort high-low
has_surplus.sort_by(|a, b| b.1.votes.partial_cmp(&a.1.votes).unwrap());
has_surplus.sort_by(|a, b| b.1.votes.cmp(&a.1.votes));
}
SurplusOrder::ByOrder => {
has_surplus.sort_by(|a, b| a.1.order_elected.partial_cmp(&b.1.order_elected).unwrap());
has_surplus.sort_by(|a, b| a.1.order_elected.cmp(&b.1.order_elected));
}
}
@ -660,9 +671,9 @@ where
if has_surplus.len() > 1 && has_surplus[0].1.votes == has_surplus[1].1.votes {
let max_votes = &has_surplus[0].1.votes;
let has_surplus = has_surplus.into_iter().filter_map(|(c, cc)| if &cc.votes == max_votes { Some(c) } else { None }).collect();
elected_candidate = TieStrategy::Prompt.choose_highest(has_surplus)?;
elected_candidate = choose_highest(state, opts, has_surplus)?;
} else {
elected_candidate = has_surplus.first_mut().unwrap().0;
elected_candidate = has_surplus[0].0;
}
distribute_surplus(state, &opts, elected_candidate);
@ -905,20 +916,35 @@ where
state.loss_fraction.transfer(&-checksum);
}
fn bulk_elect<N: Number>(state: &mut CountState<N>) -> bool {
fn bulk_elect<N: Number>(state: &mut CountState<N>, opts: &STVOptions) -> Result<bool, STVError> {
if state.election.candidates.len() - state.num_excluded <= state.election.seats {
state.kind = None;
state.title = "Bulk election".to_string();
// Bulk elect all remaining candidates
let mut hopefuls: Vec<(&&Candidate, &mut CountCard<N>)> = state.candidates.iter_mut()
.filter(|(_, cc)| cc.state == CandidateState::Hopeful)
let mut hopefuls: Vec<&Candidate> = state.election.candidates.iter()
.filter(|c| state.candidates.get(c).unwrap().state == CandidateState::Hopeful)
.collect();
// TODO: Handle ties
hopefuls.sort_unstable_by(|a, b| a.1.votes.partial_cmp(&b.1.votes).unwrap());
for (candidate, count_card) in hopefuls.into_iter() {
while !hopefuls.is_empty() {
let max_votes = hopefuls.iter()
.max_by(|a, b| state.candidates.get(**a).unwrap().votes.cmp(&state.candidates.get(**b).unwrap().votes))
.unwrap();
let max_votes = &state.candidates.get(max_votes).unwrap().votes;
let max_hopefuls: Vec<&Candidate> = hopefuls.iter()
.filter(|c| &state.candidates.get(**c).unwrap().votes == max_votes)
.map(|c| *c)
.collect();
let candidate;
if max_hopefuls.len() > 1 {
// Handle ties
candidate = choose_highest(state, opts, max_hopefuls)?;
} else {
candidate = max_hopefuls[0];
}
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;
@ -928,11 +954,13 @@ fn bulk_elect<N: Number>(state: &mut CountState<N>) -> bool {
"{} are elected to fill the remaining vacancies.",
vec![&candidate.name]
);
hopefuls.remove(hopefuls.iter().position(|c| *c == candidate).unwrap());
}
return true;
return Ok(true);
}
return false;
return Ok(false);
}
fn hopefuls_to_bulk_exclude<'a, N: Number>(state: &CountState<'a, N>, _opts: &STVOptions) -> Vec<&'a Candidate> {
@ -943,8 +971,8 @@ fn hopefuls_to_bulk_exclude<'a, N: Number>(state: &CountState<'a, N>, _opts: &ST
.collect();
// Sort by votes
// TODO: Handle ties
hopefuls.sort_unstable_by(|a, b| a.1.votes.partial_cmp(&b.1.votes).unwrap());
// NB: Unnecessary to handle ties, as ties will be rejected at "Do not exclude if this could change the order of exclusion"
hopefuls.sort_unstable_by(|a, b| a.1.votes.cmp(&b.1.votes));
let total_surpluses = state.candidates.iter()
.filter(|(_, cc)| &cc.votes > state.quota.as_ref().unwrap())
@ -954,11 +982,6 @@ fn hopefuls_to_bulk_exclude<'a, N: Number>(state: &CountState<'a, N>, _opts: &ST
for i in 0..hopefuls.len() {
let try_exclude = &hopefuls[0..hopefuls.len()-i];
// Do not exclude if this splits tied candidates
if i != 0 && try_exclude.last().unwrap().1.votes == hopefuls[hopefuls.len()-i].1.votes {
continue;
}
// Do not exclude if this leaves insufficient candidates
if state.num_elected + hopefuls.len() - try_exclude.len() < state.election.seats {
continue;
@ -966,7 +989,7 @@ fn hopefuls_to_bulk_exclude<'a, N: Number>(state: &CountState<'a, N>, _opts: &ST
// Do not exclude if this could change the order of exclusion
let total_votes = try_exclude.into_iter().fold(N::new(), |agg, (_, cc)| agg + &cc.votes);
if i != 0 && total_votes + &total_surpluses > hopefuls[hopefuls.len()-i].1.votes {
if i != 0 && total_votes + &total_surpluses >= hopefuls[hopefuls.len()-i].1.votes {
continue;
}
@ -991,22 +1014,22 @@ where
}
// Exclude lowest ranked candidate
if excluded_candidates.len() == 0 {
if excluded_candidates.is_empty() {
let mut hopefuls: 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::Hopeful)
.collect();
// Sort by votes
hopefuls.sort_by(|a, b| a.1.votes.partial_cmp(&b.1.votes).unwrap());
hopefuls.sort_by(|a, b| a.1.votes.cmp(&b.1.votes));
// Handle ties
if hopefuls.len() > 1 && hopefuls[0].1.votes == hopefuls[1].1.votes {
let min_votes = &hopefuls[0].1.votes;
let hopefuls = hopefuls.into_iter().filter_map(|(c, cc)| if &cc.votes == min_votes { Some(c) } else { None }).collect();
excluded_candidates = vec![TieStrategy::Prompt.choose_lowest(hopefuls)?];
excluded_candidates = vec![choose_lowest(state, opts, hopefuls)?];
} else {
excluded_candidates = vec![&hopefuls.first().unwrap().0];
excluded_candidates = vec![&hopefuls[0].0];
}
}
@ -1031,14 +1054,13 @@ where
{
// Cannot filter by raw vote count, as candidates may have 0.00 votes but still have recorded ballot papers
let mut excluded_with_votes: Vec<(&&Candidate, &CountCard<N>)> = state.candidates.iter()
//.filter(|(_, cc)| cc.state == CandidateState::EXCLUDED && !cc.votes.is_zero())
.filter(|(_, cc)| cc.state == CandidateState::Excluded && cc.parcels.iter().any(|p| p.len() > 0))
.filter(|(_, cc)| cc.state == CandidateState::Excluded && cc.parcels.iter().any(|p| !p.is_empty()))
.collect();
if excluded_with_votes.len() > 0 {
excluded_with_votes.sort_unstable_by(|a, b| a.1.order_elected.partial_cmp(&b.1.order_elected).unwrap());
if !excluded_with_votes.is_empty() {
excluded_with_votes.sort_unstable_by(|a, b| a.1.order_elected.cmp(&b.1.order_elected));
let order_excluded = excluded_with_votes.first().unwrap().1.order_elected;
let order_excluded = excluded_with_votes[0].1.order_elected;
let excluded_candidates: Vec<&Candidate> = excluded_with_votes.into_iter()
.filter(|(_, cc)| cc.order_elected == order_excluded)
.map(|(c, _)| *c)
@ -1127,7 +1149,7 @@ where
}
}
if remaining_votes.len() > 0 {
if !remaining_votes.is_empty() {
votes_remain = true;
}
@ -1145,9 +1167,9 @@ where
panic!("--exclusion parcels_by_order is incompatible with --bulk-exclude");
}
let count_card = state.candidates.get_mut(excluded_candidates.first().unwrap()).unwrap();
let count_card = state.candidates.get_mut(excluded_candidates[0]).unwrap();
votes = count_card.parcels.remove(0);
votes_remain = count_card.parcels.len() > 0;
votes_remain = !count_card.parcels.is_empty();
// Update votes
let votes_transferred = votes.iter().fold(N::new(), |acc, v| acc + &v.value);
@ -1156,7 +1178,7 @@ where
}
}
if votes.len() > 0 {
if !votes.is_empty() {
let value = &votes[0].value / &votes[0].ballot.orig_value;
// Count next preferences
@ -1220,3 +1242,155 @@ fn finished_before_stage<N: Number>(state: &CountState<N>) -> bool {
}
return false;
}
fn choose_highest<'c, N: Number>(state: &CountState<N>, opts: &STVOptions, candidates: Vec<&'c Candidate>) -> Result<&'c Candidate, STVError> {
for strategy in opts.ties.iter() {
match strategy.choose_highest(state, &candidates) {
Ok(c) => {
return Ok(c);
}
Err(e) => {
if let STVError::UnresolvedTie = e {
continue;
} else {
return Err(e);
}
}
}
}
panic!("Unable to resolve tie");
}
fn choose_lowest<'c, N: Number>(state: &CountState<N>, opts: &STVOptions, candidates: Vec<&'c Candidate>) -> Result<&'c Candidate, STVError> {
for strategy in opts.ties.iter() {
match strategy.choose_lowest(state, &candidates) {
Ok(c) => {
return Ok(c);
}
Err(e) => {
if let STVError::UnresolvedTie = e {
continue;
} else {
return Err(e);
}
}
}
}
return Err(STVError::UnresolvedTie);
}
fn init_tiebreaks<N: Number>(state: &mut CountState<N>, opts: &STVOptions) {
if !opts.ties.iter().any(|t| t == &TieStrategy::Forwards) && !opts.ties.iter().any(|t| t == &TieStrategy::Backwards) {
return;
}
// Sort candidates in this stage by votes, grouping by ties
let mut sorted_candidates: Vec<(&&Candidate, &CountCard<N>)> = state.candidates.iter().collect();
sorted_candidates.sort_unstable_by(|a, b| a.1.votes.cmp(&b.1.votes));
let sorted_candidates: Vec<Vec<(&&Candidate, &CountCard<N>)>> = sorted_candidates.into_iter()
.group_by(|(_, cc)| &cc.votes)
.into_iter()
.map(|(_, candidates)| candidates.collect())
.collect();
// Update forwards tie-breaking order
if opts.ties.iter().any(|t| t == &TieStrategy::Forwards) {
let mut hm: HashMap<&Candidate, usize> = HashMap::new();
for (i, group) in sorted_candidates.iter().enumerate() {
for (candidate, _) in group.iter() {
hm.insert(candidate, i);
}
}
state.forwards_tiebreak = Some(hm);
}
// Update backwards tie-breaking order
if opts.ties.iter().any(|t| t == &TieStrategy::Backwards) {
let mut hm: HashMap<&Candidate, usize> = HashMap::new();
for (i, group) in sorted_candidates.iter().enumerate() {
for (candidate, _) in group.iter() {
hm.insert(candidate, i);
}
}
state.backwards_tiebreak = Some(hm);
}
}
fn update_tiebreaks<N: Number>(state: &mut CountState<N>, _opts: &STVOptions) {
if let None = state.forwards_tiebreak {
if let None = state.backwards_tiebreak {
return;
}
}
// Sort candidates in this stage by votes, grouping by ties
let mut sorted_candidates: Vec<(&&Candidate, &CountCard<N>)> = state.candidates.iter().collect();
sorted_candidates.sort_unstable_by(|a, b| a.1.votes.cmp(&b.1.votes));
let sorted_candidates: Vec<Vec<&Candidate>> = sorted_candidates.into_iter()
.group_by(|(_, cc)| &cc.votes)
.into_iter()
.map(|(_, candidates)| candidates.map(|(c, _)| *c).collect())
.collect();
// Update forwards tie-breaking order
if let Some(hm) = state.forwards_tiebreak.as_mut() {
// TODO: Check if already completely sorted
let mut sorted_last_round: Vec<(&&Candidate, &usize)> = hm.iter().collect();
sorted_last_round.sort_unstable_by(|a, b| a.1.cmp(b.1));
let sorted_last_round: Vec<Vec<&Candidate>> = sorted_last_round.into_iter()
.group_by(|(_, v)| **v)
.into_iter()
.map(|(_, group)| group.map(|(c, _)| *c).collect())
.collect();
let mut i: usize = 0;
for mut group in sorted_last_round.into_iter() {
if group.len() == 1 {
hm.insert(group[0], i);
i += 1;
continue;
} else {
// Tied in last round - refer to this round
group.sort_unstable_by(|a, b|
sorted_candidates.iter().position(|x| x.contains(a)).unwrap()
.cmp(&sorted_candidates.iter().position(|x| x.contains(b)).unwrap())
);
let tied_last_round = group.into_iter()
.group_by(|c| sorted_candidates.iter().position(|x| x.contains(c)).unwrap());
for (_, group2) in tied_last_round.into_iter() {
for candidate in group2 {
hm.insert(candidate, i);
}
i += 1;
}
}
}
}
// Update backwards tie-breaking order
if let Some(hm) = state.backwards_tiebreak.as_mut() {
let hm_orig = hm.clone();
let mut i: usize = 0;
for group in sorted_candidates.iter() {
if group.len() == 1 {
hm.insert(group[0], i);
i += 1;
continue;
} else {
// Tied in this round - refer to last round
let mut tied_this_round: Vec<&Candidate> = group.into_iter().map(|c| *c).collect();
tied_this_round.sort_unstable_by(|a, b| hm_orig.get(a).unwrap().cmp(hm_orig.get(b).unwrap()));
let tied_this_round = tied_this_round.into_iter()
.group_by(|c| hm_orig.get(c).unwrap());
for (_, group2) in tied_this_round.into_iter() {
for candidate in group2 {
hm.insert(candidate, i);
}
i += 1;
}
}
}
}
}

View File

@ -55,16 +55,17 @@ macro_rules! impl_type {
#[wasm_bindgen]
#[allow(non_snake_case)]
pub fn [<count_init_$type>](state: &mut [<CountState$type>], opts: &stv::STVOptions) {
stv::count_init(&mut state.0, &opts);
pub fn [<count_init_$type>](state: &mut [<CountState$type>], opts: &STVOptionsWrapper) {
stv::count_init(&mut state.0, &opts.0);
}
#[wasm_bindgen]
#[allow(non_snake_case)]
pub fn [<count_one_stage_$type>](state: &mut [<CountState$type>], opts: &stv::STVOptions) -> Result<bool, JsValue> {
match stv::count_one_stage(&mut state.0, &opts) {
pub fn [<count_one_stage_$type>](state: &mut [<CountState$type>], opts: &STVOptionsWrapper) -> Result<bool, JsValue> {
match stv::count_one_stage(&mut state.0, &opts.0) {
Ok(v) => Ok(v),
Err(stv::STVError::RequireInput) => Err("RequireInput".into()),
Err(stv::STVError::UnresolvedTie) => Err("UnresolvedTie".into()),
}
}
@ -72,20 +73,20 @@ macro_rules! impl_type {
#[wasm_bindgen]
#[allow(non_snake_case)]
pub fn [<init_results_table_$type>](election: &[<Election$type>], opts: &stv::STVOptions) -> String {
return init_results_table(&election.0, opts);
pub fn [<init_results_table_$type>](election: &[<Election$type>], opts: &STVOptionsWrapper) -> String {
return init_results_table(&election.0, &opts.0);
}
#[wasm_bindgen]
#[allow(non_snake_case)]
pub fn [<describe_count_$type>](filename: String, election: &[<Election$type>], opts: &stv::STVOptions) -> String {
return describe_count(filename, &election.0, opts);
pub fn [<describe_count_$type>](filename: String, election: &[<Election$type>], opts: &STVOptionsWrapper) -> String {
return describe_count(filename, &election.0, &opts.0);
}
#[wasm_bindgen]
#[allow(non_snake_case)]
pub fn [<update_results_table_$type>](stage_num: usize, state: &[<CountState$type>], opts: &stv::STVOptions) -> Array {
return update_results_table(stage_num, &state.0, opts);
pub fn [<update_results_table_$type>](stage_num: usize, state: &[<CountState$type>], opts: &STVOptionsWrapper) -> Array {
return update_results_table(stage_num, &state.0, &opts.0);
}
#[wasm_bindgen]
@ -139,6 +140,9 @@ impl_type!(Fixed);
impl_type!(NativeFloat64);
impl_type!(Rational);
#[wasm_bindgen]
pub struct STVOptionsWrapper(stv::STVOptions<'static>);
// Reporting
fn init_results_table<N: Number>(election: &Election<N>, opts: &stv::STVOptions) -> String {

View File

@ -15,7 +15,8 @@
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
use crate::election::Candidate;
use crate::election::{Candidate, CountState};
use crate::numbers::Number;
use crate::stv::STVError;
#[allow(unused_imports)]
@ -24,6 +25,7 @@ use wasm_bindgen::prelude::wasm_bindgen;
#[allow(unused_imports)]
use std::io::{stdin, stdout, Write};
#[derive(PartialEq)]
pub enum TieStrategy<'s> {
Forwards,
Backwards,
@ -32,10 +34,42 @@ pub enum TieStrategy<'s> {
}
impl<'s> TieStrategy<'s> {
pub fn choose_highest<'c>(&self, candidates: Vec<&'c Candidate>) -> Result<&'c Candidate, STVError> {
pub fn describe(&self) -> String {
match self {
Self::Forwards => { todo!() }
Self::Backwards => { todo!() }
Self::Forwards => "forwards",
Self::Backwards => "backwards",
Self::Random(_) => todo!(),
Self::Prompt => "prompt",
}.to_string()
}
pub fn choose_highest<'c, N: Number>(&self, state: &CountState<N>, candidates: &Vec<&'c Candidate>) -> Result<&'c Candidate, STVError> {
match self {
Self::Forwards => {
let mut candidates = candidates.clone();
candidates.sort_unstable_by(|a, b|
// Compare b to a to sort high-to-low
state.forwards_tiebreak.as_ref().unwrap().get(b).unwrap()
.cmp(&state.forwards_tiebreak.as_ref().unwrap().get(a).unwrap())
);
if state.forwards_tiebreak.as_ref().unwrap().get(candidates[0]).unwrap() == state.forwards_tiebreak.as_ref().unwrap().get(candidates[1]).unwrap() {
return Err(STVError::UnresolvedTie);
} else {
return Ok(candidates[0]);
}
}
Self::Backwards => {
let mut candidates = candidates.clone();
candidates.sort_unstable_by(|a, b|
state.backwards_tiebreak.as_ref().unwrap().get(b).unwrap()
.cmp(&state.backwards_tiebreak.as_ref().unwrap().get(a).unwrap())
);
if state.backwards_tiebreak.as_ref().unwrap().get(candidates[0]).unwrap() == state.backwards_tiebreak.as_ref().unwrap().get(candidates[1]).unwrap() {
return Err(STVError::UnresolvedTie);
} else {
return Ok(candidates[0]);
}
}
Self::Random(_seed) => { todo!() }
Self::Prompt => {
return prompt(candidates);
@ -43,22 +77,44 @@ impl<'s> TieStrategy<'s> {
}
}
pub fn choose_lowest<'c>(&self, candidates: Vec<&'c Candidate>) -> Result<&'c Candidate, STVError> {
pub fn choose_lowest<'c, N: Number>(&self, state: &CountState<N>, candidates: &Vec<&'c Candidate>) -> Result<&'c Candidate, STVError> {
match self {
Self::Forwards => { todo!() }
Self::Backwards => { todo!() }
Self::Forwards => {
let mut candidates = candidates.clone();
candidates.sort_unstable_by(|a, b|
state.forwards_tiebreak.as_ref().unwrap().get(a).unwrap()
.cmp(&state.forwards_tiebreak.as_ref().unwrap().get(b).unwrap())
);
if state.forwards_tiebreak.as_ref().unwrap().get(candidates[0]).unwrap() == state.forwards_tiebreak.as_ref().unwrap().get(candidates[1]).unwrap() {
return Err(STVError::UnresolvedTie);
} else {
return Ok(candidates[0]);
}
}
Self::Backwards => {
let mut candidates = candidates.clone();
candidates.sort_unstable_by(|a, b|
state.backwards_tiebreak.as_ref().unwrap().get(a).unwrap()
.cmp(&state.backwards_tiebreak.as_ref().unwrap().get(b).unwrap())
);
if state.backwards_tiebreak.as_ref().unwrap().get(candidates[0]).unwrap() == state.backwards_tiebreak.as_ref().unwrap().get(candidates[1]).unwrap() {
return Err(STVError::UnresolvedTie);
} else {
return Ok(candidates[0]);
}
}
Self::Random(_seed) => {
return self.choose_highest(candidates);
return self.choose_highest(state, candidates);
}
Self::Prompt => {
return self.choose_highest(candidates);
return self.choose_highest(state, candidates);
}
}
}
}
#[cfg(not(target_arch = "wasm32"))]
fn prompt<'c>(candidates: Vec<&'c Candidate>) -> Result<&'c Candidate, STVError> {
fn prompt<'c>(candidates: &Vec<&'c Candidate>) -> Result<&'c Candidate, STVError> {
println!("Multiple tied candidates:");
for (i, candidate) in candidates.iter().enumerate() {
println!("{}. {}", i + 1, candidate.name);
@ -93,7 +149,7 @@ extern "C" {
}
#[cfg(target_arch = "wasm32")]
fn prompt<'c>(candidates: Vec<&'c Candidate>) -> Result<&'c Candidate, STVError> {
fn prompt<'c>(candidates: &Vec<&'c Candidate>) -> Result<&'c Candidate, STVError> {
let mut message = String::from("Multiple tied candidates:\n");
for (i, candidate) in candidates.iter().enumerate() {
message.push_str(&format!("{}. {}\n", i + 1, candidate.name));

View File

@ -64,6 +64,7 @@ fn aec_tas19_rational() {
quota: stv::QuotaType::Droop,
quota_criterion: stv::QuotaCriterion::GreaterOrEqual,
quota_mode: stv::QuotaMode::Static,
ties: vec![],
surplus: stv::SurplusMethod::UIG,
surplus_order: stv::SurplusOrder::ByOrder,
transferable_only: false,

View File

@ -38,6 +38,7 @@ fn ers97_rational() {
quota: stv::QuotaType::DroopExact,
quota_criterion: stv::QuotaCriterion::GreaterOrEqual,
quota_mode: stv::QuotaMode::ERS97,
ties: vec![],
surplus: stv::SurplusMethod::EG,
surplus_order: stv::SurplusOrder::BySize,
transferable_only: true,

View File

@ -32,6 +32,7 @@ fn prsa1_rational() {
quota: stv::QuotaType::Droop,
quota_criterion: stv::QuotaCriterion::GreaterOrEqual,
quota_mode: stv::QuotaMode::Static,
ties: vec![],
surplus: stv::SurplusMethod::EG,
surplus_order: stv::SurplusOrder::ByOrder,
transferable_only: true,

View File

@ -39,6 +39,7 @@ fn scotland_linn07_fixed5() {
quota: stv::QuotaType::Droop,
quota_criterion: stv::QuotaCriterion::GreaterOrEqual,
quota_mode: stv::QuotaMode::Static,
ties: vec![],
surplus: stv::SurplusMethod::WIG,
surplus_order: stv::SurplusOrder::BySize,
transferable_only: false,