wybr 0.0.6

//! Minimax method
//!
//! [Minimax](https://en.wikipedia.org/wiki/Minimax_Condorcet_method) gives each candidate a
//! penalty score depending on how they were maximally defeated in pairwise comparisons.
//!
//! The winner is a candidate with smallest such score; ties are broken at random.
//!
//! # Examples
//!
//! ```
//! use wybr::{Tally,Minimax,Outcome};
//!
//! //Load the Tennessee Wikipedia example
//! let tally=Tally::from_blt_file("examples/tennessee.blt").unwrap();
//!
//! //Use the default Winning votes scoring
//! let outcome=Minimax::new(&tally).run().unwrap();
//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
//!
//! //Use margin votes, which does not change the outcome
//! use wybr::PairScore;
//! let outcome=Minimax::new(&tally).pair_score(PairScore::Margin).run().unwrap();
//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
//!
//! ```

use crate::common::PairScore::*;
use crate::common::{ElectionError, PairScore};
use crate::outcome::GenericOutcome;
use crate::prng::Prng;
use crate::tally::{Tally, VoteMatrix};
use std::cmp::max;
use std::collections::HashMap;

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

impl<'a> Minimax<'a> {
    ///Acquire reference to a vote matrix tally and initiate default configuration, which can be altered
    ///with other builder methods.
    ///The default configuration involves using Winning pair scoring and random seed of 21.
    pub fn new(tally: &'a VoteMatrix) -> Self {
        Self {
            tally,
            pair_score: Winning,
            seed: 21,
        }
    }

    ///Alters the random seed potentially used by the election algorithm to break ties.
    pub fn pair_score(&mut self, pair_score: PairScore) -> &mut Self {
        self.pair_score = pair_score;
        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 MiniMax election, return winner ID or an `ElectionError`.
    ///
    /// The method considers candidates worse defeats, that is the maximal score of their opponent in
    /// one-to-one comparisons, established using given scoring mode.
    /// The winner is the candidate with smallest such worse defeat; in case of a tie, it is broken at
    /// random based on seed.
    ///
    /// # Errors
    /// * `NotEnoughCandidates`, in case there is no candidates.
    /// * `ArithmeticOverflow`, when u64 count in tally is larger than i64 max.
    ///
    /// # Notes
    /// This is not a good method, yet very simple.
    pub fn run(&self) -> Result<GenericOutcome<'a>, ElectionError> {
        let mut rnd = Prng::new(self.seed);
        let mut greatest_defeats: HashMap<u32, i64> = match self.pair_score {
            Winning => (0..self.tally.get_candidates()).map(|e| (e, 0)).collect(),
            _ => HashMap::new(),
        };
        //If winning_votes, put zero for each candidate

        for ((_runner, opponent), (uwin, uopp)) in self.tally.pairs() {
            let win = if uwin <= i64::MAX as u64 {
                uwin as i64
            } else {
                return Err(ElectionError::ArithmeticOverflow);
            };
            let opp = if uopp <= i64::MAX as u64 {
                uopp as i64
            } else {
                return Err(ElectionError::ArithmeticOverflow);
            };
            let v = match self.pair_score {
                Winning => {
                    if win > opp {
                        win
                    } else {
                        0
                    }
                }
                Opposition => win,
                Margin => win - opp,
            };
            greatest_defeats
                .entry(opponent)
                .and_modify(|defeat| *defeat = max(*defeat, v))
                .or_insert(v);
        }

        let minimax_defeat = greatest_defeats.values().min();
        let mut winners: Vec<u32> = greatest_defeats
            .iter()
            .filter_map(|(c, &s)| {
                minimax_defeat.and_then(|&ms| if s == ms { Some(*c) } else { None })
            })
            .collect();
        if !winners.is_empty() {
            winners.sort_unstable();
            let winner = rnd.only_or_random(&winners).unwrap();
            Ok(GenericOutcome::new(
                Some(winner),
                None,
                self.tally.get_candidates(),
                rnd.sealed(),
                self.tally.get_meta(),
            ))
        } else {
            Err(ElectionError::NotEnoughCandidates)
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::Outcome;
    #[test]
    fn minimax_basic() {
        use crate::PairScore::*;
        let x: VoteMatrix = VoteMatrix::with_vector_bycol(
            //Tennessee
            &vec![58, 58, 58, 42, 32, 32, 42, 68, 17, 42, 68, 83],
        );
        for ps in vec![Winning, Margin, Opposition] {
            assert_eq!(
                Minimax::new(&x)
                    .pair_score(ps)
                    .run()
                    .unwrap()
                    .winner()
                    .unwrap(),
                1
            );
        }
    }
    #[test]
    fn overflows() {
        use crate::ElectionError;
        let x: VoteMatrix = VoteMatrix::with_vector_bycol(&vec![u64::max_value(), 1]);
        match Minimax::new(&x).run().unwrap_err() {
            ElectionError::ArithmeticOverflow => (),
            _ => unreachable!(),
        }
    }
    #[test]
    fn no_cands() {
        use crate::ElectionError;
        let x: VoteMatrix = VoteMatrix::with_vector_bycol(&vec![]);
        match Minimax::new(&x).run().unwrap_err() {
            ElectionError::NotEnoughCandidates => (),
            _ => unreachable!(),
        }
    }
}