wybr 0.0.6

//! Instant run-off method
//!
//! [Instant run-off](https://en.wikipedia.org/wiki/Instant-runoff_voting) is a simple STV method
//! in which votes are transferred discretely to the most preferred candidate that is not
//! eliminated.
//!
//! If some candidate gets a majority of available votes this way, they are elected and the
//! algorithm ends; if not, a candidate with a smallest number of votes is eliminated and votes are
//! recalculated.
//! Ties are broken at random.
//!
//! # Examples
//!
//! ```
//! use wybr::{Tally,Irv,Outcome};
//!
//! //Load the Tennessee Wikipedia example
//! let tally=Tally::from_blt_file("examples/tennessee.blt").unwrap();
//! let mut outcome=Irv::new(&tally).run().unwrap();
//! assert_eq!(outcome.winner_name().unwrap(),"Knoxville");
//! ```

use crate::common::ElectionError;
use crate::outcome::GenericOutcome;
use crate::prng::Prng;
use crate::tally::{Tally, VoteTree};
use std::collections::HashSet;

///A builder for the setup of an instant-runoff count
///
///See [the module level documentation](index.html) for more.
///
///Default configuration can be generated with `Irv::new(&tally)`, where `tally` is a `VoteTree`
///object.
///Count is triggered by the `run()` method, which returns a solitary winner, or an error.
pub struct Irv<'a> {
    tally: &'a VoteTree,
    withdrawn: HashSet<u32>,
    seed: u32,
}

impl<'a> Irv<'a> {
    ///Acquire reference to a vote tally and initiate default configuration, which can be altered
    ///with other builder methods.
    ///The default configuration involved using withdraw list pulled from the tally and seed equal to 21.
    pub fn new(tally: &'a VoteTree) -> Self {
        let mut withdrawn: HashSet<u32> = HashSet::new();
        tally.map_withdrawn(|c| {
            withdrawn.insert(c);
        });
        Self {
            tally,
            withdrawn,
            seed: 21,
        }
    }
    ///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.insert(e);
        }
        self
    }
    ///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
    }

    /// Performs Instant-runoff STV election
    ///
    /// # Errors
    /// * `NotEnoughCandidates`, in case there is less candidates then seats or no votes
    pub fn run(&self) -> Result<GenericOutcome<'a>, ElectionError> {
        let candidates = self.tally.get_candidates();
        let mut eliminated = self.withdrawn.clone();
        let mut rnd = Prng::new(self.seed);

        let winner = loop {
            //First, eagerly assign tally passing through eliminated candidates
            let (excess, mut score) = self.tally.assign_votes(&eliminated);
            //Scores lack elements for which there is not direct vote; we have to supply
            //for elimination to verbosely mention them.
            //Otherwise, some candidate may appear on one round after it should be eliminated.
            for i in 0..candidates {
                if !eliminated.contains(&i) {
                    score.entry(i).or_insert(0);
                }
            }
            let quota = (self.tally.ballot_count() - excess) / 2;
            let max_score = score.values().max();
            let mut winners: Vec<u32> = score
                .iter()
                //Possible winner must have best score which is better than quota
                .filter(|(_, &s)| max_score.map_or(false, |&ms| s == ms && s > quota))
                .map(|(&c, _)| c)
                .collect();

            if !winners.is_empty() {
                //We have a winner; or few...
                winners.sort_unstable();
                let final_winner = rnd.only_or_random(&winners).unwrap();
                break final_winner;
            } else {
                //We need another round; to this end, we need to select a set of
                // candidates with a minimal score, and eliminate one of them
                let min_score = score.values().min();
                let mut worse: Vec<u32> = score
                    .iter()
                    .filter(|(_, &s)| min_score.map_or(false, |&ms| s == ms))
                    .map(|(&c, _)| c)
                    .collect();

                if worse.is_empty() {
                    return Err(ElectionError::NotEnoughCandidates);
                }
                worse.sort_unstable();
                let looser = rnd.only_or_random(&worse).unwrap();
                eliminated.insert(looser);
            }
        };
        Ok(GenericOutcome::new(
            Some(winner),
            self.withdrawn.iter().cloned(),
            candidates,
            rnd.sealed(),
            self.tally.get_meta(),
        ))
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::Outcome;
    #[test]
    fn basic() {
        let x = [
            (1, vec![0, 1]),
            (2, vec![0, 2]),
            (3, vec![1, 0]),
            (2, vec![1, 2]),
            (2, vec![2, 0]),
            (2, vec![2, 1]),
            (1, vec![4, 3, 2]),
        ]
        .iter()
        .collect();
        let ans = Irv::new(&x).run().unwrap();
        assert_eq!(ans.winner().unwrap(), 2);
    }
    #[test]
    fn empty() {
        let x = [].iter().collect();
        match Irv::new(&x).run().unwrap_err() {
            ElectionError::NotEnoughCandidates => (),
            _ => unreachable!(),
        }
    }
}