wybr 0.0.6

//! Schulze method
//!
//! [Schulze](https://en.wikipedia.org/wiki/Schulze_method) method expands the beat graph with
//! widest beat-paths between candidates, and then attempts to find a Condorcet winner.
//!
//! # Examples
//!
//! ```
//! use wybr::{Tally,Schulze,Outcome};
//!
//! //Load the Tennessee Wikipedia example
//! let tally=Tally::from_blt_file("examples/tennessee.blt").unwrap();
//!
//! //Perform simple election with default parameters
//! let outcome=Schulze::new(&tally).run().unwrap();
//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
//!
//! //Change pair score to `Margin`; this won't change the outcome, though
//! use wybr::PairScore;
//! let outcome=Schulze::new(&tally).pair_score(PairScore::Margin).run().unwrap();
//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
//! ```
use self::PairScore::*;
use crate::common::{ElectionError, PairScore};
use crate::outcome::GenericOutcome;
use crate::tally::{Tally, VoteMatrix};
use std::collections::HashMap;

pub struct Schulze<'a> {
    tally: &'a VoteMatrix,
    pair_score: PairScore,
}

fn strongest_paths<S: ::std::hash::BuildHasher>(n: u32, x: &mut HashMap<(u32, u32), u64, S>) {
    use std::cmp::{max, min};
    for i in 0..n {
        for j in 0..n {
            for k in 0..n {
                if i != j && i != k && j != k {
                    if let Some(&pji) = x.get(&(j, i)) {
                        if let Some(&pik) = x.get(&(i, k)) {
                            let alt = min(pji, pik);
                            x.entry((j, k))
                                .and_modify(|e| *e = max(*e, alt))
                                .or_insert(alt);
                        }
                    }
                }
            }
        }
    }
    //Retain winning paths only
    for i in 1..n {
        for j in 0..i {
            if let Some(&vij) = x.get(&(i, j)) {
                if let Some(&vji) = x.get(&(j, i)) {
                    if vij >= vji {
                        x.remove(&(j, i));
                    }
                    if vji >= vij {
                        x.remove(&(i, j));
                    }
                }
            }
        }
    }
}

///A builder for the setup of Schulze method
///
///See [the module level documentation](index.html) for more.
///
///Default configuration can be generated with `Schulze::new(&tally)`, where `tally` is a
///`VoteMatrix` object.
///Count is triggered by the `run()` method, which returns a solitary winner, or an error.
impl<'a> Schulze<'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.
    pub fn new(tally: &'a VoteMatrix) -> Self {
        Self {
            tally,
            pair_score: Winning,
        }
    }

    ///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
    }

    /// Performs a Schulze (beat-path) election
    ///
    /// # Errors
    /// * `NotEnoughCandidates`, in case there is no candidates.
    /// * `DegeneratedElectionGraph`, in case when there is no winner in the final graph.
    ///   Anyhow, such situation happens extremely rarely in practice, especially when indifferent votes
    ///   are disallowed (this is what wybr does).
    ///
    /// # Notes
    /// This is a basic version of the Schulze method, with no tie-breaking at all; there is also a
    /// more sophisticated version with forbidden links which fends off some ties, and even more
    /// complex one that uses a random ballot to break ties.
    /// Hence, it does not use pseudo-random generator at all.
    pub fn run(&self) -> Result<GenericOutcome<'a>, ElectionError> {
        if self.tally.get_candidates() == 0 {
            return Err(ElectionError::NotEnoughCandidates);
        }
        //Initiate pairs with winning votes
        let mut paths: HashMap<(u32, u32), u64> = self
            .tally
            .pairs()
            .filter_map(|((runner, opponent), (win, opposition))| {
                let score: u64 = match (win > opposition, self.pair_score) {
                    (true, Margin) => win - opposition,
                    (true, Winning) => win,
                    (_, Opposition) => win,
                    _ => 0,
                };
                if score > 0 {
                    Some(((runner, opponent), score))
                } else {
                    None
                }
            })
            .collect();
        //Complete paths to strongest paths
        strongest_paths(self.tally.get_candidates(), &mut paths);

        //Establish who can be a Condorcet winner
        let mut is_winner: HashMap<u32, bool> = HashMap::new();
        for (&(winner, looser), _) in paths.iter() {
            is_winner.entry(winner).or_insert(true);
            is_winner.insert(looser, false);
        }
        let mut winner_iter = is_winner
            .iter()
            .filter_map(|(&c, &w)| if w { Some(c) } else { None });
        if let Some(final_winner) = winner_iter.next() {
            if winner_iter.next().is_none() {
                Ok(GenericOutcome::new(
                    Some(final_winner),
                    None,
                    self.tally.get_candidates(),
                    true,
                    self.tally.get_meta(),
                ))
            } else {
                //Winner list is > 1
                Err(ElectionError::DegeneratedElectionGraph)
            }
        } else {
            //Winner list is empty
            Err(ElectionError::DegeneratedElectionGraph)
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::ElectionError;
    use crate::Outcome;
    #[test]
    fn schulze_basic() {
        let x = VoteMatrix::with_vector_bycol(
            //Tennessee
            &vec![58, 58, 58, 42, 32, 32, 42, 68, 17, 42, 68, 83],
        );

        assert_eq!(Schulze::new(&x).run().unwrap().winner().unwrap(), 1);
    }
    #[test]
    fn schulze_wiki() {
        let x = VoteMatrix::with_vector_bycol(&vec![
            25, 0, 0, 23, 0, 29, 0, 27, 26, 0, 28, 0, 30, 33, 0, 31, 0, 0, 24, 0,
        ]);
        assert_eq!(Schulze::new(&x).run().unwrap().winner().unwrap(), 4);
    }

    #[test]
    fn schulze_no_wins() {
        let x = VoteMatrix::with_vector_bycol(&vec![3, 3, 3, 3, 3, 3]);
        match Schulze::new(&x).run().unwrap_err() {
            ElectionError::DegeneratedElectionGraph => (),
            _ => unreachable!(),
        }
    }
    #[test]
    fn schulze_no_cands() {
        let x: VoteMatrix = VoteMatrix::with_vector_bycol(&vec![]);
        match Schulze::new(&x).run().unwrap_err() {
            ElectionError::NotEnoughCandidates => (),
            _ => unreachable!(),
        }
    }
}