wybr 0.0.6

//! Meek STV method
//!
//! [Meek STV](http://www.dia.govt.nz/diawebsite.NSF/Files/meekm/%24file/meekm.pdf) is a popular
//! form of Single Transferable Vote election; it allows for electing multiple candidates.
//!
//! In this method, vote is spread across candidates specified on the ballot, and this spread is
//! adjusted in a number of rounds as candidates are progressively eliminated or elected.
//! Undecided candidates get the whole part of vote that reaches them, eliminated get none, finally
//! elected are only given enough for its total support to reach quota.
//! Part of vote that reaches the end of the ballot goes to excess and lowers the quota.
//!
//! In each round, votes are spread, total supports are gathered, and candidates which reach the
//! quota are elected; if all seats are taken, the algorithm stops.
//! If no-one can be elected, candidate with a lowest support is eliminated.
//! Finally, the algorithm loops back to the next round.
//!
//! This implementation uses fixed point arithmetic with a customisable amount of decimal digits.
//! Similarly, it can use various quota functions; Hagenbach-Bischoff which is used in the AS123
//! paper, Hare or Droop.
//!
//! # Examples
//! ```
//! use wybr::{Tally,Meek,Outcome};
//!
//! //Load the example from the AS123 paper
//! let tally=Tally::from_blt_file("examples/a123.blt").unwrap();
//!
//! //Perform election with default parameters
//! let outcome=Meek::new(&tally).run().unwrap();
//! let mut winners:Vec<String>=outcome.elected_names().collect();
//! //Even though outcome is deterministic...
//! assert!(outcome.deterministic());
//! //...order may depend on HashSet order, hence we sort to compare
//! winners.sort_unstable();
//! assert_eq!(winners,vec!["Adam","Donald"]);
//!
//! //Perform election ignoring the withdrawal of Basil from the blt file
//! let outcome=Meek::new(&tally).withdraw(vec![]).run().unwrap();
//! let mut winners:Vec<String>=outcome.elected_names().collect();
//! winners.sort_unstable();
//! assert_eq!(winners,vec!["Adam","Charlotte"]);
//!
//! //Also change quota to Hare
//! use wybr::Quota;
//! let outcome=Meek::new(&tally).withdraw(vec![]).quota(Quota::Hare).run().unwrap();
//! let mut winners:Vec<String>=outcome.elected_names().collect();
//! winners.sort_unstable();
//! assert_eq!(winners,vec!["Adam","Basil"]);
//!
//! //Perform Warren election with default parameters
//! use wybr::Transfer;
//! let outcome=Meek::new(&tally).transfer(Transfer::Warren).run().unwrap();
//! let mut winners:Vec<String>=outcome.elected_names().collect();
//! winners.sort_unstable();
//! assert_eq!(winners,vec!["Adam","Donald"]);
//! ```

use self::ElectionError::*;
use self::Quota::*;
use crate::common::{ElectionError, Quota, Transfer};
use crate::outcome::GenericOutcome;
use crate::prng::Prng;
use crate::tally::{Tally, VoteTree};
use std::collections::{HashMap, HashSet};

///A builder for the setup of a Meek count.
///
///See [the module level documentation](index.html) for more.
///
///Default configuration can be generated with `Meek::new(tally)`, where `tally` is a
///`VoteTree` object.  Count is triggered by the `run()` method, which returns a vector of winners,
///or an error.
pub struct Meek<'a> {
    tally: &'a VoteTree,
    seats: Option<u32>,
    withdrawn: Vec<u32>,
    transfer: Transfer,
    quota: Quota,
    digits: u32,
    seed: u32,
}

impl<'a> Meek<'a> {
    ///Acquire reference to a vote tally and initiate default configuration, which can be altered
    ///with other builder methods.
    ///The default configuration involves using Hagenbach-Bischoff quota, Meek vote transfer mode,
    ///seats number and withdraw list pulled from the tally, 6 digits of fixed-point arithmetic,
    ///finally seed set to 21.
    pub fn new(tally: &'a VoteTree) -> Self {
        let mut withdrawn: Vec<u32> = Vec::new();
        tally.map_withdrawn(|c| {
            withdrawn.push(c);
        });
        Self {
            tally,
            quota: HagenbachBischoff,
            transfer: Transfer::Meek,
            withdrawn,
            seats: Some(tally.get_seats()),
            digits: 6,
            seed: 21,
        }
    }
    ///Alters the random seed potentially used by the election algorithm to break ties.
    pub fn seed(&mut self, seed: u32) -> &mut Self {
        self.seed = seed;
        self
    }
    ///Alters the number of seats (candidates to be elected).
    pub fn seats(&mut self, seats: u32) -> &mut Self {
        self.seats = Some(seats);
        self
    }
    ///Alters the number of fixed-point digits used.
    ///
    ///Seventeen is max (enforced in `run()`); also, 10 ^ digits * total votes in tally must be smaller
    ///than 2 ^ 64.
    pub fn digits(&mut self, digits: u32) -> &mut Self {
        self.digits = digits;
        self
    }
    ///Alter the quota calculation method; see `Quota` type for details.
    ///
    ///The default is `HagenbachBischoff` in compatibility with [Algorithm 123](http://www.prsa.org.au/meek_algorithm_1987.pdf),
    ///but it is good to consider using `Hare` in order to get most of STV.
    pub fn quota(&mut self, quota: Quota) -> &mut Self {
        self.quota = quota;
        self
    }
    ///Alter the vote transfer method; see `Transfer` type for details.
    ///
    ///In general, Meek algorithm is Meek with the default `Transfer::Meek`; with
    ///`Transfer::Warren` is becomes Warren STV.
    ///The naming in wybr reflects the fact that Warren proposed a relatively small change to the
    ///Meek idea; not insignificant, however.
    ///Also because this method is much more recognisable as Meek STV.
    pub fn transfer(&mut self, transfer: Transfer) -> &mut Self {
        self.transfer = transfer;
        self
    }
    ///Alter a list of withdrawn candidates, which are not considered in count.
    pub fn withdraw<I>(&mut self, withdraw: I) -> &mut Self
    where
        I: IntoIterator<Item = u32>,
    {
        self.withdrawn.clear();
        for e in withdraw.into_iter() {
            self.withdrawn.push(e);
        }
        self
    }

    /// Performs Meek STV election, returns `Vec<u32>` with IDs of winners, or an `ElectionError`.
    ///
    /// Aims to be compatible with [Algorithm 123](http://www.prsa.org.au/meek_algorithm_1987.pdf),
    /// though uses fixed-point arithmetic.
    ///
    /// # Errors
    /// * `NotEnoughCandidates`, in case there is less candidates then seats or no votes,
    /// * `FixedPointDigitsTooMany`, in case there is too many ballots for a given `digits` value, or
    ///   when `digits` is higher than 17, which is somewhat insane.
    ///
    /// # Notes
    /// In a pathological case, it may take a lot of time, but not infinite (at most ~ number of
    /// candidates ^ 2 * 10 ^ digits).
    /// Fixed point stuff works by multiplying almost everything by 10^base and fitting the result in
    /// u64; when you have like billions of ballots and `digits` of 9, it may become tight.
    ///
    /// Votes are also compared to be greater or equal with quota, even when `quota` is `HagenbachBischoff`; when
    /// it seems that more candidates then seats are going to be elected, random tie breaking is used.
    ///
    /// For seats==1, result will be almost certainly identical to this of `irv`, depending on the
    /// quota method (IRV effectively uses `Hare`).
    pub fn run(&self) -> Result<GenericOutcome<'a>, ElectionError> {
        let seats = self.seats.unwrap_or(1);
        let candidates = self.tally.get_candidates();
        if self.digits > 17 {
            return Err(FixedPointDigitsTooMany);
        }
        let base = 10_u64.pow(self.digits);
        if self.tally.ballot_count().checked_mul(base).is_none() {
            return Err(FixedPointDigitsTooMany);
        }

        let mut elected: Vec<u32> = Vec::new();
        let mut resolved: HashSet<u32> = HashSet::new();

        //Initial weights are 1, so base/base
        let mut weights: HashMap<u32, u64> = (0..candidates).map(|c| (c, base)).collect();
        //Remove withdrawn, effectively zeroing their weight
        for c in &self.withdrawn {
            weights.remove(c);
            resolved.insert(*c);
        }
        if weights.len() < seats as usize {
            return Err(NotEnoughCandidates);
        }

        let mut rnd = Prng::new(self.seed);

        loop {
            //We have to adjust weights for the elected candidates
            let (_excess, mut score, quota) = loop {
                let (excess, score) = self.tally.transfer_votes_fp(&weights, base, Transfer::Meek);
                let useful_votes = score.values().sum();
                let quota = match self.quota {
                    Hare => (useful_votes, u64::from(seats)),
                    HareInt => (((useful_votes / u64::from(seats)) / base) * base, 1),
                    Droop => (
                        ((useful_votes / (u64::from(seats) + 1)) / base + 1) * base,
                        1,
                    ),
                    HagenbachBischoff => (useful_votes, u64::from(seats) + 1),
                };
                let mut stable = true;
                for ec in &elected {
                    //Weights cannot go up, so we enforce that over truncation errors
                    if quota.0 > quota.1 * score[ec] {
                        continue;
                    }
                    let new_weight = (weights[ec] * quota.0) / (quota.1 * score[ec]);
                    stable = stable
                        && weights
                            .insert(*ec, new_weight)
                            .map_or(false, |old_weight| old_weight == new_weight)
                }
                if stable {
                    break (excess, score, quota);
                }
            };

            score.retain(|c, _| !resolved.contains(c));
            let mut electable: Vec<u32> = score
                .iter()
                .filter_map(|(&c, &s)| {
                    if s * quota.1 >= quota.0 {
                        Some(c)
                    } else {
                        None
                    }
                })
                .collect();

            if !electable.is_empty() {
                //We have candidates to elect; but maybe too many due to low quota?
                while electable.len() + elected.len() > seats as usize {
                    let to_remove = rnd.random_usindex(electable.len());
                    electable.swap_remove(to_remove);
                }
                //We're clear now to elect
                for &e in &electable {
                    elected.push(e);
                    resolved.insert(e);
                }
                //Maybe we're done?
                if elected.len() == seats as usize {
                    return Ok(GenericOutcome::new(
                        elected.iter().cloned(),
                        self.withdrawn.iter().cloned(),
                        candidates,
                        rnd.sealed(),
                        self.tally.get_meta(),
                    ));
                }
            } else {
                //No one to elect, someone has to be removed
                let min_score = score.values().min();
                let mut worse: Vec<u32> = score
                    .iter()
                    .filter_map(|(c, &s)| {
                        min_score.and_then(|&ms| if s == ms { Some(*c) } else { None })
                    })
                    .collect();
                if worse.is_empty() {
                    return Err(NotEnoughCandidates);
                } else {
                    worse.sort_unstable(); //For stable random selection
                    let looser = rnd.only_or_random(&worse).unwrap();
                    weights.remove(&looser);
                }
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::Outcome;
    #[test]
    fn meek_withdrawn() {
        let x = [
            (3, vec![0, 2, 3]),
            (4, vec![0, 2, 1]),
            (2, vec![3, 0, 2]),
            (1, vec![1]),
            (2, vec![1, 3, 2, 0]),
            (1, vec![2, 3, 1]),
        ]
        .iter()
        .collect();
        assert_eq!(
            Meek::new(&x)
                .seats(2)
                .withdraw(vec![1])
                .quota(Quota::Hare)
                .run()
                .unwrap()
                .elected()
                .collect::<Vec<u32>>(),
            vec![0, 3]
        );
    }
    #[test]
    fn meek_alts() {
        let x = [
            (3, vec![0, 2, 3]),
            (4, vec![0, 2, 1]),
            (2, vec![3, 0, 2]),
            (1, vec![1]),
            (2, vec![1, 3, 2, 0]),
            (1, vec![2, 3, 1]),
        ]
        .iter()
        .collect();
        let mut stub = Meek::new(&x);
        stub.seats(2).digits(6).seed(97);
        assert_eq!(
            stub.run().unwrap().elected().collect::<Vec<u32>>(),
            vec![0, 2]
        );
        assert_eq!(
            stub.quota(Quota::Hare)
                .run()
                .unwrap()
                .elected()
                .collect::<Vec<u32>>(),
            vec![0, 1]
        );
        assert_eq!(
            stub.transfer(Transfer::Warren)
                .run()
                .unwrap()
                .elected()
                .collect::<Vec<u32>>(),
            vec![0, 1]
        );
    }
    #[test]
    fn meek_alts_more() {
        let x = [
            (3, vec![0, 2, 3]),
            (4, vec![0, 2, 1]),
            (2, vec![3, 0, 2]),
            (1, vec![1]),
            (2, vec![1, 3, 2, 0]),
            (1, vec![2, 3, 1]),
        ]
        .iter()
        .collect();
        let mut stub = Meek::new(&x);
        stub.seats(2).digits(6).seed(97);
        use Quota::*;
        for quota in vec![Hare, HareInt, Droop, HagenbachBischoff] {
            for transfer in vec![Transfer::Warren, Transfer::Meek] {
                assert!(stub.quota(quota).transfer(transfer).run().is_ok());
            }
        }
    }
    #[test]
    fn meek_empty() {
        let x = [].iter().collect();
        match Meek::new(&x).run().unwrap_err() {
            ElectionError::NotEnoughCandidates => (),
            _ => unreachable!(),
        };
    }
}