wybr 0.0.6

//! Nanson's method
//!
//! [Nanson's method](https://en.wikipedia.org/wiki/Nanson's_method) is an extension of Borda count
//! in which candidates are progressively eliminated rather than ranked once.
//! Namely, in each round all candidates with Borda scores smaller or equal than average are eliminated, so
//! that the ballots are shifted giving more points to other candidates.
//! Such procedure is repeated until one winner is left.
//!
//! There can be a tie, in this case random tie breaking is used among candidates which reached the
//! final round.
//!
//! # Examples
//!
//! ```
//! use wybr::{Tally,Nanson,Outcome};
//!
//! //Load the Tennessee Wikipedia example
//! let tally=Tally::from_blt_file("examples/tennessee.blt").unwrap();
//! let mut nanson=Nanson::new(&tally);
//!
//! //Perform simple election with default, Borda1 rules
//! let outcome=Nanson::new(&tally).run().unwrap();
//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
//! ```

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

use BordaKind::*;

pub struct Nanson<'a> {
    tally: &'a VoteTree,
    borda_kind: BordaKind,
    withdraw: HashSet<u32>,
    max_rank: Option<u32>,
    seed: u32,
}

///A builder for the setup of a Nanson count.
///
///See [the module level documentation](index.html) for more.
///
///Default configuration can be generated with `Nanson::new(&tally)`, where `tally` is a `VoteTree`
///object.
///Count is triggered by the `run()` method, which returns a solitary winner, or an error.
impl<'a> Nanson<'a> {
    ///Acquire reference to a vote tally and initiate default configuration, which can be altered
    ///with other builder methods.
    ///The default configuration involves using `Borda1` kind, withdraw list pulled from the tally,
    ///maximal rank equal to the actual maximal rank found in the tally, finally for seed equal to 21.
    pub fn new(tally: &'a VoteTree) -> Self {
        let mut withdraw: HashSet<u32> = HashSet::new();
        tally.map_withdrawn(|c| {
            withdraw.insert(c);
        });
        Self {
            tally,
            borda_kind: Borda1,
            withdraw,
            max_rank: None,
            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
    }
    ///Alter the Borda election kind; see `BordaKind` type for details.
    pub fn kind(&mut self, kind: BordaKind) -> &mut Self {
        self.borda_kind = kind;
        self
    }
    ///Alter the maximal rank used for election; ranks are count from zero, so when this value is
    ///x, up to (x + 1)-th vote is considered, while the later ones are discarded.
    ///
    ///Note that withdraws act before this filter, so vote A B C with `max_rank` 1 and B withdrawn
    ///is interpreted as first preference is A, second is no-one.
    pub fn max_rank(&mut self, max_rank: u32) -> &mut Self {
        self.max_rank = Some(max_rank);
        self
    }
    ///Alter a list of withdrawn candidates, which are not considered in count.
    ///
    ///A vote A B C with B withdrawn is interpreted as first preference is A, second is C, third is
    ///no-one.
    pub fn withdraw<I>(&mut self, withdraw: I) -> &mut Self
    where
        I: IntoIterator<Item = u32>,
    {
        self.withdraw.clear();
        for e in withdraw.into_iter() {
            self.withdraw.insert(e);
        }
        self
    }

    /// Performs Nanson election; returns the ID of a winner, or an `ElectionError`.
    ///
    /// # Notes
    /// Nanson's method is essentially an iterated Borda election; on each iteration all candidates
    /// with Borda score lower or equal than average are eliminated.
    /// All parameters of the Nanson method are identical to these of the Borda method.
    ///
    /// # Errors
    /// * `ArithmeticOverflow`, when score numbers are too large to fit in u64; this is especially
    ///   likely with `Nauru` kind and insane `max_rank`, like 40+.
    /// * `NotEnoughCandidates`, when there is no candidates or no votes.
    pub fn run(&self) -> Result<GenericOutcome<'a>, ElectionError> {
        let mut rnd = Prng::new(self.seed);
        use crate::methods::borda::Borda;
        let mut borda = Borda::new(self.tally);
        borda.kind(self.borda_kind);
        if let Some(mr) = self.max_rank {
            borda.max_rank(mr);
        };

        let mut eliminated: HashSet<u32> = HashSet::new();
        for e in self.withdraw.iter() {
            eliminated.insert(*e);
        }

        let winner = loop {
            let scores = borda.withdraw(eliminated.iter().cloned()).scores()?;
            if scores.is_empty() {
                return Err(ElectionError::NotEnoughCandidates);
            }
            let average = (scores.values().map(|x| u128::from(*x)).sum::<u128>()
                / (scores.len() as u128)) as u64;
            let mut elim_c: usize = 0;
            let mut winner: Option<u32> = None;
            for (c, s) in &scores {
                if *s <= average {
                    eliminated.insert(*c);
                    elim_c += 1;
                } else if winner.is_none() {
                    winner = Some(*c);
                } else {
                    winner = None;
                }
            }
            //Maybe we only have one candidate left?
            if let Some(x) = winner {
                break x;
            }

            //Maybe we have eliminated everyone?
            if elim_c == scores.len() {
                //This means there is a tie and we need to back-track elimination
                //and select random one from the start of this round
                let mut winners: Vec<u32> = scores.keys().cloned().collect();
                winners.sort_unstable();
                //We have checked earlier, so someone is in winners
                break rnd.only_or_random(&winners).unwrap();
            };
        };

        Ok(GenericOutcome::new(
            Some(winner),
            self.withdraw.iter().cloned(),
            self.tally.get_candidates(),
            rnd.sealed(),
            self.tally.get_meta(),
        ))
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::outcome::Outcome;
    #[test]
    fn demo() {
        //Load the Tennessee Wikipedia example
        let tally = Tally::from_blt_file("examples/tennessee.blt").unwrap();
        //Perform simple election with default, Borda1 rules
        let outcome = Nanson::new(&tally).run().unwrap();
        assert!(outcome.deterministic());
        assert_eq!(outcome.winner_name().unwrap(), "Nashville");
    }
    #[test]
    fn with_tie() {
        let x = [
            (10, vec![0, 1]),
            (10, vec![1, 0]),
            (5, vec![2, 3]),
            (5, vec![3, 2]),
        ]
        .iter()
        .collect();
        let mut stub = Nanson::new(&x);
        stub.seed(97);
        let ans = stub.kind(Borda0).run().unwrap();
        assert!(!ans.deterministic());
        assert_eq!(ans.winner().unwrap(), 1);
        stub.seed(99);
        assert_eq!(stub.kind(Borda0).run().unwrap().winner().unwrap(), 0);
        assert_eq!(stub.kind(Nauru).run().unwrap().winner().unwrap(), 0);
        assert_eq!(stub.kind(Borda1).run().unwrap().winner().unwrap(), 0);
    }
    #[test]
    fn single_cand() {
        let x = [(10, vec![0])].iter().collect();
        let ans = Nanson::new(&x).run().unwrap();
        assert!(ans.deterministic());
        assert_eq!(ans.winner().unwrap(), 0);
    }
    #[test]
    fn empty() {
        let x = [].iter().collect();
        match Nanson::new(&x).run().unwrap_err() {
            ElectionError::NotEnoughCandidates => (),
            _ => unreachable!(),
        }
    }
}