wybr 0.0.6

//! Borda count method
//!
//! [Borda count](https://en.wikipedia.org/wiki/Borda_count) is a method in which candidates are
//! scored depending on their position on a ballot (their rank) -- first candidate has rank 0,
//! second 1 and so on.
//! There is some maximal rank, say n, that is the highest (worse) rank in the tally, which is used
//! for score calculation.
//!
//! Ranks are converted into points depending on the kind of Borda count; in the original
//! formulation (`BordaKind::Borda1`), first candidates gets n+1 points, second n, n-th 1.
//!
//! The simpler alternative counts from n to 0, `BordaKind::Borda0`.
//! There is also Dowdall/Nauru system in which each candidates gets 1/(its rank+1) points; it is
//! triggered using `BordaKind::Nauru` as a kind.
//! While wybr avoids using floating-point arithmetic, this kind uses integer absolute points which
//! lead to the same outcome.
//!
//! # Examples
//!
//! ```
//! use wybr::{Tally,Borda,Outcome};
//!
//! //Load the Tennessee Wikipedia example
//! let tally=Tally::from_blt_file("examples/tennessee.blt").unwrap();
//! let mut borda=Borda::new(&tally);
//!
//! //Perform simple election with default, Borda1 rules
//! let outcome=Borda::new(&tally).run().unwrap();
//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
//!
//! //Change scoring to Dowdall/Nauru; this won't change the outcome, though
//! use wybr::BordaKind;
//! let outcome=borda.kind(BordaKind::Nauru).run().unwrap();
//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
//!
//! //Limit maximal considered rank to 0; this will degenerate count into plurality voting on first
//! //choices, and hence change winner to Memphis
//! let outcome=borda.max_rank(0).run().unwrap();
//! assert_eq!(outcome.winner_name().unwrap(),"Memphis");
//! ```

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

fn gcd(a: u64, b: u64) -> u64 {
    let mut a = a;
    let mut b = b;
    if b > a {
        std::mem::swap(&mut a, &mut b);
    }
    loop {
        let m = a % b;
        if m == 0 {
            break b;
        } else {
            a = b;
            b = m;
        }
    }
}
fn lcm(a: u64, b: u64) -> u64 {
    a * b / gcd(a, b)
}
fn multi(n: u64) -> Option<u64> {
    if n > 42 {
        None
    } else {
        Some((2..=(n + 1)).fold(1, lcm))
    }
}

///A builder for the setup of a Borda-style count.
///
///See [the module level documentation](index.html) for more.
///
///Default configuration can be generated with `Borda::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 Borda<'a> {
    tally: &'a VoteTree,
    kind: BordaKind,
    withdraw: HashSet<u32>,
    max_rank: Option<u32>,
    seed: u32,
}

impl<'a> Borda<'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,
            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.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
    }
    pub(super) fn scores(&self) -> Result<HashMap<u32, u64>, ElectionError> {
        let counts = self.tally.count_ranks(&self.withdraw);
        let max_rank = self
            .max_rank
            .unwrap_or_else(|| *(counts.keys().map(|(_, r)| r).max().unwrap_or(&0)));

        let denominator = if let Nauru = self.kind {
            match multi(u64::from(max_rank)) {
                Some(x) => x,
                None => return Err(ElectionError::ArithmeticOverflow),
            }
        } else {
            1
        };

        let mut scores: HashMap<u32, u64> = HashMap::new();
        for (&(cand, rank), &count) in &counts {
            if rank <= max_rank {
                if let Some(score) = count.checked_mul(match self.kind {
                    Borda0 => {
                        if max_rank > 0 {
                            u64::from(max_rank - rank)
                        } else {
                            1
                        }
                    }
                    Borda1 => u64::from(max_rank - rank + 1),
                    Nauru => denominator / u64::from(rank + 1),
                }) {
                    let val = scores.entry(cand).or_insert(0);
                    if let Some(nv) = (*val).checked_add(score) {
                        *val = nv;
                    } else {
                        return Err(ElectionError::ArithmeticOverflow);
                    }
                } else {
                    return Err(ElectionError::ArithmeticOverflow);
                }
            }
        }
        Ok(scores)
    }
    /// Performs Borda election; returns the ID of a winner, or an `ElectionError`.
    ///
    /// # Notes
    /// Wybr internally shifts votes leftmost, both when parsing inputs and in data representation;
    /// hence, one cannot have vote like A (no-one) B C, at most A B C (no-one) (no-one).
    /// In such case of truncated votes, the omitted ranks simply generate zero points, and no
    /// adjustments are made to the rest of the candidates on a ballot.
    ///
    /// Dowdall/Nauru system uses multiplication instead of division to assure accurate integer
    /// calculation; counts are multiplied by lcm(1,2,..,max_rank) and then divided by rank.
    /// Consequently, Nauru with max_rank equal to 43 and more returns error immediately.
    ///
    /// For max_rank equal to 0 (either given explicitly or calculated) and Borda0 kind, scores are
    /// multiplied by 1 rather than 0.
    ///
    /// # 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);
        let scores = self.scores()?;

        let best_score = scores.values().max();
        let mut winners: Vec<u32> = scores
            .iter()
            .filter_map(|(c, &s)| best_score.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),
                self.withdraw.iter().cloned(),
                self.tally.get_candidates(),
                rnd.sealed(),
                self.tally.get_meta(),
            ))
        } else {
            Err(ElectionError::NotEnoughCandidates)
        }
    }
}

#[cfg(test)]
mod tests {
    use self::BordaKind::*;
    use super::*;
    use crate::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 = Borda::new(&tally).run().unwrap();
        assert_eq!(outcome.winner_name().unwrap(), "Nashville");
    }
    #[test]
    fn borda_multi() {
        fn check(max_rank: u64) {
            let mlt = multi(max_rank).unwrap();
            for e in 2..=(max_rank + 1) {
                assert_eq!(mlt % e, 0);
            }
        }
        for e in 3..11 {
            check(e);
        }
        assert_eq!(multi(0).unwrap(), 1);
        assert_eq!(multi(1).unwrap(), 1 * 2);
        assert_eq!(multi(2).unwrap(), 1 * 2 * 3);
        assert_eq!(multi(3).unwrap(), 1 * 3 * 4);
        assert_eq!(multi(4).unwrap(), 1 * 3 * 4 * 5);
        assert_eq!(multi(5).unwrap(), 1 * 3 * 5 * 4);
        assert!(multi(50).is_none());
    }
    #[test]
    fn borda_simple() {
        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 mut stub = Borda::new(&x);
        stub.seed(97);
        assert_eq!(stub.kind(Borda0).run().unwrap().winner().unwrap(), 1);
        assert_eq!(stub.kind(Nauru).run().unwrap().winner().unwrap(), 1);
        //TODO: Here we have 1=2 21 votes tie
        assert_eq!(stub.kind(Borda1).run().unwrap().winner().unwrap(), 2);
        assert_eq!(
            Borda::new(&x)
                .kind(Borda1)
                .withdraw(vec![0, 2])
                .run()
                .unwrap()
                .winner()
                .unwrap(),
            1
        );
    }
    #[test]
    fn borda_wiki() {
        let x = [
            (51, vec![0, 2, 1, 3]),
            (5, vec![2, 1, 3, 0]),
            (23, vec![1, 2, 3, 0]),
            (21, vec![3, 2, 1, 0]),
        ]
        .iter()
        .collect();
        let mut stub = Borda::new(&x);
        stub.seed(97);
        assert_eq!(stub.kind(Borda0).run().unwrap().winner().unwrap(), 2);
        assert_eq!(stub.kind(Borda1).run().unwrap().winner().unwrap(), 2);
        assert_eq!(stub.kind(Nauru).run().unwrap().winner().unwrap(), 0);
    }
    #[test]
    fn borda_empty() {
        let x = [].iter().collect();
        match Borda::new(&x).run().unwrap_err() {
            ElectionError::NotEnoughCandidates => (),
            _ => unreachable!(),
        }
    }
}