wybr 0.0.6

//! Ranked pairs (Tideman) method
//!
//! [The ranked pairs](https://en.wikipedia.org/wiki/Ranked_pairs) or Tideman method considers each
//! pair of candidates (i,j) and combines it with a score, which depends on how much candidate i
//! beats candidate j in pairwise comparison.
//! Then, pairs are ordered by decreasing score and sequentially either *locked*, that is added as
//! an edge to a directed acyclic graph over candidates, or dropped, in case adding them would have
//! cause a cycle in the graph and violate is DAG property.
//!
//! The winner is the only candidate in the resulting graph that is not beaten; if there are more
//! unbeaten candidates, the election is considered unresolved.  There are three possible modes of
//! scoring pairs, common to most Condorcet methods: `PairScore::Winning`, `PairScore::Margin` and
//! `PairScore::Opposition`.
//!
//! By default, `Margin` option is used, as in the original Tideman formulation.  `Winning` is
//! often seen in this method formulation; still, such approach is often called MAM or MMV.  In
//! case of ties in sort, first the possibly low opposition vote is used, that is the number of
//! votes which prefer j to i, and then pseudo-random order depending on the seed.
//!
//! # Examples
//!
//! ```
//! use wybr::{Tally,RankedPairs,Outcome};
//!
//! //Load the Tennessee Wikipedia example
//! let tally=Tally::from_blt_file("examples/tennessee.blt").unwrap();
//!
//! //Perform simple election with default parameters
//! let outcome=RankedPairs::new(&tally).run().unwrap();
//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
//!
//! //Change pair score to `Winning`; this won't change the outcome, though
//! use wybr::PairScore;
//! let outcome=RankedPairs::new(&tally).pair_score(PairScore::Winning).run().unwrap();
//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
//! ```
mod cand_pair;
mod forced_dag;
use self::PairScore::*;
use crate::common::{ElectionError, PairScore};
use crate::outcome::GenericOutcome;
use crate::prng::Prng;
use crate::tally::{Tally, VoteMatrix};
use cand_pair::CandPair;
use forced_dag::ForcedDag;

///A builder for the setup of a Ranked Pairs count
///
///See [the module level documentation](index.html) for more.
///
///Default configuration can be generated with `RankedPairs::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 RankedPairs<'a> {
    tally: &'a VoteMatrix,
    pair_score: PairScore,
    seed: u32,
}
impl<'a> RankedPairs<'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 pair scoring method.
    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 ranked pairs (Tideman) election, returns winner ID or an `ElectionError`.
    ///
    /// The method considers each pair of candidates (i,j) and combines it with a score, which
    /// depends on the mode.  Then, pairs are ordered by decreasing score and sequentially locked,
    /// that is added as an edge to a directed acyclic graph over candidates, or dropped, in case
    /// adding them would have cause a cycle in the graph and violate is DAG property.  The winner
    /// is the only candidate in the resulting graph that is not beaten; if there are more unbeaten
    /// candidates, the election is considered unresolved and `DegeneratedElectionGraph` error is
    /// emitted.
    ///
    /// The score depends on the mode; also, for mode equal to Winning or Margin only winning pairs
    /// are considered.  In case of ties in sort, first the possibly low opposition vote is used,
    /// that is the number of votes which prefer j to i, and then pseudo-random order depending on
    /// the seed.
    ///
    /// # Errors
    /// * `NotEnoughCandidates`, in case there is no candidates.
    /// * `DegeneratedElectionGraph`, in case when there is no winner in the final graph; this may
    ///   happen for instance when the graph looks like this: `A->B<-C` or has isolated sub-graph,
    ///   like this `A->D->C C->E` -- in both cases, A & B are equally good winners in light of
    ///   ranked pairs method, but may be not equivalent in terms of actual preference, hence we
    ///   don't want to use random tie breaking.  Anyhow, such situation happens extremely rarely in
    ///   practice, especially when indifferent votes are disallowed (this is what wybr does).
    ///
    /// # Notes
    /// Default mode for ranked pairs is `Margin`; `Winning` is often seen in the
    /// definition of this method.  `Opposition` mode is similar to `Winning`, but affects
    /// symmetric links (i & j so that d(i,j)=d(j,i)) -- instead of being thrown away as in other
    /// modes, they are converted into unidirectional ones with a random direction.
    pub fn run(&self) -> Result<GenericOutcome<'a>, ElectionError> {
        if self.tally.get_candidates() < 1 {
            return Err(ElectionError::NotEnoughCandidates);
        }
        let mut rnd = Prng::new(self.seed);
        let mut pairs: Vec<CandPair> = self
            .tally
            .pairs()
            .filter_map(|((runner, opponent), (win, opposition))| {
                let score: u64 = match (win > opposition, self.pair_score) {
                    (true, PairScore::Margin) => win - opposition,
                    (true, PairScore::Winning) => win,
                    (_, PairScore::Opposition) => win,
                    _ => 0,
                };
                if win > opposition {
                    Some(CandPair::new(runner, opponent, score, opposition))
                } else {
                    None
                }
            })
            .collect();

        pairs.sort_unstable();
        let mut dag = ForcedDag::new(self.tally.get_candidates());
        while !pairs.is_empty() {
            //Pull a group of CandPairs that are equivalent; this is usually just one
            let mut group: Vec<CandPair> = Vec::new();
            while group.is_empty() || pairs.ends_with(&group[0..1]) {
                group.push(pairs.pop().unwrap());
            }
            if group.len() == 1 {
                //Short-circuit when there are no determinism quirks
                for x in &group {
                    dag.add_edge(x.runner, x.opponent);
                }
            } else {
                //Remove pairs that cannot be alone added to the graph
                group.retain(|x| dag.try_edge(x.runner, x.opponent));

                //Shuffle the order in group; but save rnd state to reset it if the operation was
                //deterministic after all
                rnd.push();
                rnd.shuffle(&mut group);

                //Add the edges that are left. First edge, if any, must be accepted.
                //If any other edge is rejected, it could be put first and become accepted, hence we
                //have a dependence on the order and the outcome is not deterministic
                //NOTE: This is not equivalent to all, since we need to add all edges and
                //we cannot short-circuit
                #[allow(clippy::unnecessary_fold)]
                if group
                    .iter()
                    .fold(true, |flag, x| flag && dag.add_edge(x.runner, x.opponent))
                {
                    rnd.pop().unwrap();
                }
            }
        }
        if let Ok(winner) = dag.get_winner() {
            Ok(GenericOutcome::new(
                Some(winner),
                None,
                self.tally.get_candidates(),
                rnd.sealed(),
                self.tally.get_meta(),
            ))
        } else {
            Err(ElectionError::DegeneratedElectionGraph)
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::Outcome;
    #[test]
    fn ranked_pairs_basic() {
        //Tennessee
        let x = VoteMatrix::with_vector_bycol(
            //Tennessee
            &vec![58, 58, 58, 42, 32, 32, 42, 68, 17, 42, 68, 83],
        );
        assert_eq!(
            RankedPairs::new(&x)
                .pair_score(PairScore::Margin)
                .run()
                .unwrap()
                .winner()
                .unwrap(),
            1
        );
    }
    #[test]
    fn ranked_pairs_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!(
            RankedPairs::new(&x)
                .pair_score(PairScore::Winning)
                .run()
                .unwrap()
                .winner()
                .unwrap(),
            0
        );
    }
    #[test]
    fn ranked_pairs_no_wins() {
        let x = VoteMatrix::with_vector_bycol(&vec![3, 3, 3, 3, 3, 3]);
        let ans = RankedPairs::new(&x).pair_score(PairScore::Margin).run();
        match ans.unwrap_err() {
            ElectionError::DegeneratedElectionGraph => (),
            _ => unreachable!(),
        };
    }
    #[test]
    fn ranked_pairs_co2() {
        let x = VoteMatrix::with_vector_bycol(&vec![0, 0, 1, 1, 0, 0]);
        let ans = RankedPairs::new(&x).pair_score(PairScore::Margin).run();
        match ans.unwrap_err() {
            ElectionError::DegeneratedElectionGraph => (),
            _ => unreachable!(),
        };
    }
    #[test]
    fn ranked_pairs_determinism() {
        //A->B->C->D is deterministic
        let x = VoteMatrix::with_vector_bycol(&vec![0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1]);
        assert!(RankedPairs::new(&x).run().unwrap().deterministic());

        //A->B->C->D->A is not deterministic
        let x = VoteMatrix::with_vector_bycol(&vec![0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1]);
        assert!(!RankedPairs::new(&x).run().unwrap().deterministic());

        //D=>C A->B->C->D->A is deterministic, though meh
        let x = VoteMatrix::with_vector_bycol(&vec![0, 0, 1, 1, 0, 0, 0, 1, 2, 0, 0, 1]);
        assert!(RankedPairs::new(&x).run().unwrap().deterministic());

        //A=>B D=>C C->A B->D is not deterministic
        let x = VoteMatrix::with_vector_bycol(&vec![0, 1, 0, 2, 0, 0, 0, 0, 2, 0, 1, 0]);
        assert!(!RankedPairs::new(&x).run().unwrap().deterministic());

        //A=>B=>C=>D=>E C->A D->B E->C A->D B->E is deterministic
        let x = VoteMatrix::with_vector_bycol(&vec![
            0, 1, 0, 0, 2, 0, 1, 0, 0, 2, 0, 1, 1, 0, 2, 0, 0, 1, 0, 2,
        ]);
        assert!(RankedPairs::new(&x).run().unwrap().deterministic());
    }
    #[test]
    fn no_cands() {
        use crate::ElectionError;
        let x: VoteMatrix = VoteMatrix::with_vector_bycol(&vec![]);
        match RankedPairs::new(&x).run().unwrap_err() {
            ElectionError::NotEnoughCandidates => (),
            _ => unreachable!(),
        }
    }
}