#![forbid(unsafe_code, unstable_features, missing_docs)]
#![deny(
warnings,
unused_extern_crates,
missing_copy_implementations,
missing_debug_implementations
)]
use rand::seq::SliceRandom;
use std::error;
use std::fmt;
#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
pub enum DistributionError {
Tied,
InvalidSeatCount,
NegativeVotes,
NoVotes,
}
impl fmt::Display for DistributionError {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
&DistributionError::Tied => write!(
f,
"Tie detected, could only be resolved by randomly awarding a seat to one party."
),
&DistributionError::InvalidSeatCount => {
write!(f, "Invalid seat count, must be an integer larger than 0.")
}
&DistributionError::NegativeVotes => write!(
f,
"Invalid votes, all parties must have at least zero votes."
),
&DistributionError::NoVotes => {
write!(f, "Invalid votes, one party must have at least one vote.")
}
}
}
}
impl error::Error for DistributionError {}
#[derive(Clone)]
struct PartyQuotient {
party: usize,
quotient: f64,
}
pub fn distribute(
votes: &[f64],
seat_count: &usize,
draw_on_tie: &bool,
) -> Result<Vec<usize>, DistributionError> {
if seat_count < &1 {
return Err(DistributionError::InvalidSeatCount);
}
let has_negative_votes = votes.iter().any(|v| v < &0.0);
if has_negative_votes {
return Err(DistributionError::NegativeVotes);
}
let total_votes: f64 = votes.iter().sum();
if total_votes == 0.0 {
return Err(DistributionError::NoVotes);
}
let mut party_quotients: Vec<PartyQuotient> = votes
.iter()
.enumerate()
.flat_map(|(i, v)| {
let divisors = (1..=(seat_count.clone() as i64)).map(|d| (d as f64) - 0.5);
return divisors.map(move |d| PartyQuotient {
party: i,
quotient: v / d,
});
})
.collect();
party_quotients.sort_by(|a, b| {
b.quotient
.partial_cmp(&a.quotient)
.unwrap_or(std::cmp::Ordering::Equal)
});
let last_winning_quotient = party_quotients
.get(seat_count.clone() - 1)
.map(|pq| pq.quotient)
.unwrap_or(0.0);
let mut winners: Vec<PartyQuotient> = party_quotients
.iter()
.filter(|pq| pq.quotient > last_winning_quotient)
.cloned()
.collect();
let mut possible_winners: Vec<PartyQuotient> = party_quotients
.iter()
.filter(|pq| pq.quotient == last_winning_quotient)
.cloned()
.collect();
let seats_too_many =
(winners.len() as i64) + (possible_winners.len() as i64) - (seat_count.clone() as i64);
if seats_too_many > 0 {
if !draw_on_tie {
return Err(DistributionError::Tied);
}
let number_of_draws = (possible_winners.len() as i64) - seats_too_many;
let mut drawn_winners: Vec<PartyQuotient> = (&possible_winners)
.choose_multiple(&mut rand::thread_rng(), number_of_draws.max(0) as usize)
.cloned()
.collect();
winners.append(&mut drawn_winners);
} else {
winners.append(&mut possible_winners);
}
let mut distribution: Vec<usize> = vec![0; votes.len()];
for pq in winners.iter() {
distribution[pq.party] += 1
}
return Ok(distribution);
}
#[cfg(test)]
mod tests {
use super::distribute;
use super::DistributionError;
#[test]
fn german_bundestag_2013() {
let votes = [41.5, 25.7, 8.6, 8.4];
let seats = 631;
let distribution = distribute(&votes, &seats, &false);
let parliament = vec![311, 193, 64, 63];
assert_eq!(distribution, Ok(parliament));
}
#[test]
fn rhineland_palatinate_201x() {
let votes = [362.0, 318.0, 126.0, 62.0, 53.0];
let seats = 101;
let distribution = distribute(&votes, &seats, &false);
let parliament = vec![39, 35, 14, 7, 6];
assert_eq!(distribution, Ok(parliament));
}
#[test]
fn schleswig_holstein_201x() {
let votes = [308.0, 304.0, 132.0, 82.0, 82.0, 46.0];
let seats = 69;
let distribution = distribute(&votes, &seats, &false);
let parliament = vec![22, 22, 10, 6, 6, 3];
assert_eq!(distribution, Ok(parliament));
}
#[test]
fn equal_but_no_draw_required() {
let votes = [415.0, 257.0, 85.0, 85.0];
let seats = 631;
let distribution = distribute(&votes, &seats, &false);
let parliament = vec![311, 192, 64, 64];
assert_eq!(distribution, Ok(parliament));
}
#[test]
fn equal_and_draw_required() {
let votes = [3.0, 3.0, 1.0];
let seats = 8;
let distribution_without_draw = distribute(&votes, &seats, &false);
assert_eq!(distribution_without_draw, Err(DistributionError::Tied));
let distribution_with_draw = distribute(&votes, &seats, &true);
let parliament_draw_a: Vec<usize> = vec![4, 3, 1];
let parliament_draw_b: Vec<usize> = vec![3, 4, 1];
assert_eq!(
[Ok(parliament_draw_a), Ok(parliament_draw_b)]
.iter()
.any(|x| x == &distribution_with_draw),
true
);
}
#[test]
fn small_parliament_no_draw_required() {
let votes = [2.0, 2.0];
let seats = 2;
let distribution_without_draw = distribute(&votes, &seats, &false);
assert_eq!(distribution_without_draw, Ok(vec![1, 1]));
let distribution_with_draw = distribute(&votes, &seats, &true);
assert_eq!(distribution_with_draw, Ok(vec![1, 1]));
}
#[test]
fn only_one_party() {
let votes = [3.0];
let seats = 10;
let distribution = distribute(&votes, &seats, &false);
let parliament = vec![10];
assert_eq!(distribution, Ok(parliament));
}
#[test]
fn invalid_seat_count() {
let votes = [3.0];
let seats = 0;
let distribution = distribute(&votes, &seats, &false);
assert_eq!(distribution, Err(DistributionError::InvalidSeatCount));
}
#[test]
fn no_votes() {
let seats = 50;
let distribution_empty_votes = distribute(&[], &seats, &false);
assert_eq!(distribution_empty_votes, Err(DistributionError::NoVotes));
let distribution_zero_votes = distribute(&[0.0, 0.0], &seats, &false);
assert_eq!(distribution_zero_votes, Err(DistributionError::NoVotes));
let distribution_valid_votes = distribute(&[0.0, 3.0], &seats, &false);
assert_eq!(distribution_valid_votes, Ok(vec![0, seats]));
}
#[test]
fn negative_votes() {
let seats = 50;
let distribution_negative_votes = distribute(&[-3.0], &seats, &false);
assert_eq!(
distribution_negative_votes,
Err(DistributionError::NegativeVotes)
);
let distribution_negative_votes_sum_zero = distribute(&[4.0, -4.0], &seats, &false);
assert_eq!(
distribution_negative_votes_sum_zero,
Err(DistributionError::NegativeVotes)
);
}
}