wybr 0.0.6

//! Alternative Smith/Schwartz method
//!
//! [Tideman alternative methods](https://en.wikipedia.org/wiki/Tideman_alternative_method) first
//! extract the Smith or Schwartz set of candidates and then perform instant-runoff voting inside
//! this set, as all other candidates have been withdrawn.
//! Ties are broken at random.
//!
//! # Examples
//!
//! ```
//! use wybr::{Tally,Alternative,Outcome,SetType};
//!
//! //Load the Tennessee Wikipedia example
//! let tally=Tally::from_blt_file("examples/tennessee.blt").unwrap();
//! let mut outcome=Alternative::new(&tally).set_type(SetType::Smith).run().unwrap();
//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
//! ```

use crate::common::{ElectionError, SetType};
use crate::methods::smith_schwartz::smith_schwartz_condensation;
use crate::outcome::{GenericOutcome, Outcome};
use crate::tally::{Tally, VoteMatrix, VoteTree};
use crate::Irv;
use std::collections::{HashMap, HashSet};

///A builder for the setup of an Tideman alternative count
///
///See [the module level documentation](index.html) for more.
///
///Default configuration can be generated with `Alternative::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 Alternative<'a> {
    tally: &'a VoteTree,
    set_type: SetType,
    seed: u32,
}

impl<'a> Alternative<'a> {
    ///Acquire reference to a vote tally and initiate default configuration, which can be altered
    ///with other builder methods.
    ///The default configuration involved using Smith set and seed equal to 21.
    pub fn new(tally: &'a VoteTree) -> Self {
        Self {
            tally,
            seed: 21,
            set_type: SetType::Smith,
        }
    }
    ///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
    }
    ///Alters set type
    pub fn set_type(&mut self, set_type: SetType) -> &mut Self {
        self.set_type = set_type;
        self
    }

    /// Performs Tideman alternative STV election
    ///
    /// # Errors
    /// * `NotEnoughCandidates`, in case there is less candidates then seats or no votes
    pub fn run(&self) -> Result<GenericOutcome<'a>, ElectionError> {
        let candidates = self.tally.get_candidates();
        let mut vm: HashMap<(u32, u32), u64> = HashMap::new();
        self.tally.stream_ballots(&mut |repeat: u64, vote: &[u32]| {
            let mut ballot: HashMap<u32, usize> = HashMap::new();
            for (pref, &c) in vote.iter().enumerate() {
                ballot.insert(c, pref);
            }
            for c in 0..candidates {
                ballot.entry(c).or_insert(usize::MAX);
            }
            for (&runner, &r_pref) in &ballot {
                for (&opponent, &o_pref) in &ballot {
                    if r_pref < o_pref {
                        *vm.entry((runner, opponent)).or_insert(0) += repeat;
                    }
                }
            }
        });
        let matrix: VoteMatrix = vm.iter().map(|(&(r, o), &s)| (r, o, s)).collect();
        let members = smith_schwartz_condensation(&matrix, self.set_type).get_max();
        if members.is_empty() {
            Err(ElectionError::NotEnoughCandidates)
        } else if members.len() == 1 {
            //We have a Condorcet winner
            Ok(GenericOutcome::new(
                Some(members[0]),
                None,
                candidates,
                true,
                self.tally.get_meta(),
            ))
        } else {
            //Move to IRV
            let mut not_members: HashSet<u32> = (0..candidates).collect();
            for retain in members {
                not_members.remove(&retain);
            }
            let irv_out = Irv::new(self.tally)
                .withdraw(not_members.iter().cloned())
                .seed(self.seed)
                .run()?;
            //Re-write is needed because Irv has no meta
            Ok(GenericOutcome::new(
                Some(irv_out.winner().unwrap()),
                None,
                candidates,
                irv_out.deterministic(),
                self.tally.get_meta(),
            ))
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::Outcome;
    #[test]
    fn alt_basic() {
        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();
        for st in [SetType::Smith, SetType::Schwartz].iter() {
            let ans = Alternative::new(&x).set_type(*st).run().unwrap();
            assert_eq!(ans.winner().unwrap(), 2);
        }
    }
    #[test]
    fn alt_deeper() {
        let x = [(1, vec![0, 1]), (2, vec![1, 2]), (3, vec![2, 0])]
            .iter()
            .collect();
        let ans = Alternative::new(&x).run().unwrap();
        assert_eq!(ans.winner().unwrap(), 2);
    }
    #[test]
    fn alt_empty() {
        let x = [].iter().collect();
        match Alternative::new(&x).run().unwrap_err() {
            ElectionError::NotEnoughCandidates => (),
            _ => unreachable!(),
        }
    }
}