tallystick 0.4.3

use super::check_duplicate;
use super::plurality::PluralityTally;
use super::result::CountedCandidates;
use super::result::RankedCandidate;
use super::result::RankedWinners;
use super::Numeric;
use super::TallyError;
use hashbrown::HashMap;
use hashbrown::HashSet;
use num_traits::Num;
use num_traits::NumCast;
use std::hash::Hash;
use std::ops::AddAssign;

// We often convert `C` (vote count types) to and from small integers.
// If we can't sucessfully convert a small integer into `C`, we panic since converting from a small is trivial.
const C_FROM_PANIC: &str = "Cannot convert integer to C, this is likely caused by a bug in the ToPrimitive impl for the count type.";

/// Specifies method used to assign points to ranked candidates.
pub enum Variant<C> {
    /// The standard Borda count where each candidate is assigned a number of points equal to the number of candidates ranked lower than them.
    /// It is known as the "Starting at 0" Borda count since the least-significantly ranked candidate is given zero points.
    /// Each candidate is given points according to:
    ///
    /// ```number-candidates - candidate-position - 1```
    ///
    /// Example point allocation for a single ballot:
    ///
    /// | Position on ballot  | Candiate | Points |
    /// | --------------------|----------|--------|
    /// | 0                   | Alice    | 3      |
    /// | 1                   | Bob      | 2      |
    /// | 2                   | Carlos   | 1      |
    /// | 3                   | Dave     | 0      |
    Borda,

    /// The classic Borda count as defined in Jean-Charles de Borda's [original proposal](http://gerardgreco.free.fr/IMG/pdf/MA_c_moire-Borda-1781.pdf).
    /// It is known as the "Starting at 1" Borda count since the least-significantly ranked candidate is given one point.
    /// Each candidate is given points according to:
    ///
    /// ```number-candidates - candidate-position```
    ///
    /// Example point allocation for a single ballot:
    ///
    /// | Position on ballot  | Candiate | Points |
    /// | --------------------|----------|--------|
    /// | 0                   | Alice    | 4      |
    /// | 1                   | Bob      | 3      |
    /// | 2                   | Carlos   | 2      |
    /// | 3                   | Dave     | 1      |
    ClassicBorda,

    /// In the Dowdall system, the highest-ranked candidate obtains 1 point, while the 2nd-ranked candidate receives ½ a point, the 3rd-ranked candidate receives ⅓ of a point, etc.
    /// An important difference of this method from the others is that the number of points assigned to each preference does not depend on the number of candidates.
    /// Each candidate is given points according to:
    ///
    /// ```1 / (candidate-position + 1)```
    ///
    /// If Dowdall is selected, tallystick will panic if an integer count type is used in the tally. This variant should only be used with a float or rational tally.
    ///
    /// Example point allocation for a single ballot:
    ///
    /// | Position on ballot  | Candiate | Points |
    /// | --------------------|----------|--------|
    /// | 0                   | Alice    | 1      |
    /// | 1                   | Bob      | ½      |
    /// | 2                   | Carlos   | ⅓      |
    /// | 3                   | Dave     | ¼      |
    ///
    /// Example:
    /// ```
    /// use tallystick::borda::BordaTally;
    /// use tallystick::borda::Variant;
    ///
    /// // Note use of `f64` as our count type.
    /// let mut tally = BordaTally::<&str, f64>::new(1, Variant::Dowdall);
    /// tally.add(vec!["Barak Obama", "John McCain"]);
    /// tally.add(vec!["Barak Obama", "Mitt Romney"]);
    /// let _winners = tally.winners();
    /// ```
    Dowdall,

    /// In a modified Borda count, the number of points given for a voter's first and subsequent preferences is determined by the total number of candidates they have actually ranked, rather than the total number listed.
    /// This is to say, typically, on a ballot of `n` candidates, if a voter casts only `m` preferences (where `n ≥ m ≥ 1`), a first preference gets `m` points, a second preference `m – 1` points, and so on.
    /// Modified Borda counts are used to counteract the problem of [bullet voting](https://en.wikipedia.org/wiki/Bullet_voting).
    /// Each candidate is given points according to:
    ///
    /// ```number-marked - candidate-position```
    ModifiedClassicBorda,

    /// Custom point assignment using a boxed closure. Takes a closure of the form:
    ///
    /// ```fn(candidate_position: usize, num_candidates: usize, num_marked: usize) -> C```
    ///
    /// Example:
    /// ```
    /// use tallystick::borda::BordaTally;
    /// use tallystick::borda::Variant;
    ///
    /// let boxed_func = Box::new(|candidate_position, num_candidates, num_marked| {
    ///   if num_marked == 1 {
    ///     return 1;
    ///   }
    ///   else {
    ///     return num_marked - candidate_position - 1;
    ///   }
    /// });
    /// let mut tally = BordaTally::<&str, usize>::new(1, Variant::Custom(boxed_func));
    /// ```
    Custom(Box<dyn Fn(usize, usize, usize) -> C>),
}

impl<C: Numeric + Num + NumCast> Variant<C> {
    /// Get the number of points for a candidate at a certain position on a ballot.
    ///
    /// - `candidate_position` is the position of the candidate on the marked ballot. It is `0` for the 1st candidate, `1` for the second candidate etc.
    /// - `num_candidates` is the total number of candidates in this election.
    /// - `num_marked` is the total number of candidates marked on the ballot.
    ///
    /// This method will panic if using [`Variant::Dowdall`](#variant.Dowdall) with an integer based vote-count type.
    pub fn points(&self, candidate_position: usize, num_candidates: usize, num_marked: usize) -> C {
        // Unwrapping options SHOULD be good here. It's very unlikely that C can't represent a small unsigned integer.
        // If it is the case that a small integer can't be represented in C, that's a bug.
        match self {
            Variant::Borda => C::from(num_candidates - candidate_position - 1).expect(C_FROM_PANIC),
            Variant::ClassicBorda => C::from(num_candidates - candidate_position).expect(C_FROM_PANIC),
            Variant::Dowdall => {
                if !C::fraction() {
                    panic!(
                        "tallystick::borda::Variant::Dowdall cannot be used with an integer count type. Please use a float or a rational."
                    )
                }
                C::one() / C::from(candidate_position + 1).expect(C_FROM_PANIC)
            }
            Variant::ModifiedClassicBorda => C::from(num_marked - candidate_position).expect(C_FROM_PANIC),
            Variant::Custom(boxed_func) => boxed_func(candidate_position, num_candidates, num_marked),
        }
    }
}

/// A borda tally using `u64` integers to count votes.
/// `DefaultBordaTally` is generally preferred over `BordaTally`, except when using the `Variant::Dowdall` variant.
/// Since this is an alias, refer to [`BordaTally`](struct.BordaTally.html) for method documentation.
///
/// # Example
/// ```
///    use tallystick::borda::DefaultBordaTally;
///    use tallystick::borda::Variant;
///
///    // What is your favourite colour?
///    // A vote with hexadecimal colour candidates and a single-winner.
///    let red = 0xff0000;
///    let blue = 0x00ff00;
///    let green = 0x0000ff;
///    let mut tally = DefaultBordaTally::<u32>::new(1, Variant::Borda);
///    tally.add(vec![green, blue, red]);
///    tally.add(vec![red, green, blue]);
///    tally.add(vec![blue, green, red]);
///    tally.add(vec![blue, red, green]);
///    tally.add(vec![blue, red, green]);
///
///    let winners = tally.winners().into_unranked();
///
///    // Blue wins!
///    assert!(winners[0] == 0x00ff00);
/// ```
pub type DefaultBordaTally<T> = BordaTally<T, u64>;

/// A generic borda tally.
///
/// Generics:
/// - `T`: The candidate type.
/// - `C`: The count type. `u64` is recommended, but can be modified to use a different type for counting votes (eg `f64` for fractional vote weights). If using [`Variant::Dowdall`](enum.Variant.html#variant.Dowdall) then a float, a [`rational`](https://rust-num.github.io/num/num_rational/index.html), or anyting that implements [`Real`](https://docs.rs/num-traits/0.2.6/num_traits/real/trait.Real.html) must be used.
///
/// Example:
/// ```
///    use tallystick::borda::BordaTally;
///    use tallystick::borda::Variant;
///
///    // A tally with string candidates, one winner, `f64` counting, using the Dowall point system.
///    let mut tally = BordaTally::<&str, f64>::new(1, Variant::Dowdall);
///    tally.add(vec!["Alice", "Bob", "Carlos"]);
///    tally.add(vec!["Bob", "Carlos", "Alice"]);
///    tally.add(vec!["Alice", "Carlos", "Bob"]);
///    tally.add(vec!["Alice", "Bob", "Carlos"]);
///
///    let winners = tally.winners();
/// ```
pub struct BordaTally<T, C = u64>
where
    T: Eq + Clone + Hash,                             // Candidate
    C: Copy + PartialOrd + AddAssign + Num + NumCast, // Vote count type
{
    running_total: HashMap<Vec<T>, C>,
    candidates: HashSet<T>,
    num_winners: usize,
    variant: Variant<C>,
}

impl<T, C> BordaTally<T, C>
where
    T: Eq + Clone + Hash,                             // Candidate
    C: Copy + PartialOrd + AddAssign + Num + NumCast, // Vote count type
{
    /// Create a new `BordaTally` with the given number of winners.
    ///
    /// If there is a tie, the number of winners might be more than `num_winners`.
    /// (See [`winners()`](#method.winners) for more information on ties.)
    pub fn new(num_winners: usize, variant: Variant<C>) -> Self {
        BordaTally {
            running_total: HashMap::new(),
            candidates: HashSet::new(),
            num_winners: num_winners,
            variant: variant,
        }
    }

    /// Create a new `BordaTally` with the given number of winners, and number of expected candidates.
    pub fn with_capacity(num_winners: usize, variant: Variant<C>, expected_candidates: usize) -> Self {
        BordaTally {
            running_total: HashMap::with_capacity(expected_candidates),
            candidates: HashSet::with_capacity(expected_candidates),
            num_winners: num_winners,
            variant: variant,
        }
    }

    /// Add a new vote
    ///
    /// Votes are represented as a vector of ranked candidates, ordered by preference.
    /// An error will only be returned if `vote` contains duplicate candidates.
    pub fn add(&mut self, vote: Vec<T>) -> Result<(), TallyError> {
        self.add_weighted(vote, C::one())
    }

    /// Add a new vote by reference
    pub fn add_ref(&mut self, vote: &[T]) -> Result<(), TallyError> {
        self.add_weighted_ref(vote, C::one())
    }

    /// Add a weighted vote.
    /// By default takes a weight as a `usize` integer, but can be customized by using `BordaTally` with a custom vote type.
    pub fn add_weighted(&mut self, vote: Vec<T>, weight: C) -> Result<(), TallyError> {
        check_duplicate(&vote)?;

        for candidate in vote.iter() {
            if !self.candidates.contains(candidate) {
                self.candidates.insert(candidate.clone());
            }
        }

        let entry = self.running_total.entry(vote);
        *entry.or_insert(C::zero()) += weight;

        Ok(())
    }

    /// Add a weighted vote by reference
    pub fn add_weighted_ref(&mut self, vote: &[T], weight: C) -> Result<(), TallyError> {
        check_duplicate(vote)?;

        for candidate in vote.iter() {
            if !self.candidates.contains(candidate) {
                self.candidates.insert(candidate.clone());
            }
        }

        let entry = self.running_total.entry(vote.to_vec());
        *entry.or_insert(C::zero()) += weight;

        Ok(())
    }

    /// Get a ranked list of winners. Winners with the same rank are tied.
    /// The number of winners might be greater than the requested `num_winners` if there is a tie.
    /// In a borda count, the winners are determine by what candidate obtains the most points.
    pub fn winners(&self) -> RankedWinners<T> {
        let mut counted = CountedCandidates::new();
        for (candidate, votecount) in self.totals().iter() {
            counted.push(candidate.clone(), *votecount);
        }

        counted.into_ranked(self.num_winners)
    }

    /// Get a ranked list of all candidates. Candidates with the same rank are tied.
    pub fn ranked(&self) -> Vec<RankedCandidate<T>> {
        let mut counted = CountedCandidates::new();
        for (candidate, votecount) in self.totals().iter() {
            counted.push(candidate.clone(), *votecount);
        }

        counted.into_ranked(0).into_vec()
    }

    /// Get point totals for this tally.
    ///
    /// This will return a vector with the number of borda points for each candidate.
    ///
    /// # Example
    /// ```
    ///    use tallystick::borda::DefaultBordaTally;
    ///    use tallystick::borda::Variant;
    ///
    ///    let mut tally = DefaultBordaTally::new(1, Variant::ClassicBorda);
    ///    for _ in 0..30 { tally.add(vec!["Alice", "Bob"]).unwrap() }
    ///    for _ in 0..10 { tally.add(vec!["Bob", "Alice"]).unwrap() }
    ///
    ///    for (candidate, num_points) in tally.totals().iter() {
    ///       println!("{} has {} points", candidate, num_points);
    ///    }
    ///    // Prints:
    ///    //   Alice has 70 points
    ///    //   Bob has 30 points
    /// ```
    pub fn totals(&self) -> Vec<(T, C)> {
        // Make a little plurality tally and use borda points as weights
        let mut plurality = PluralityTally::with_capacity(self.num_winners, self.candidates.len());
        for (selection, votecount) in self.running_total.iter() {
            let num_marked = selection.len();
            for (position, candidate) in selection.iter().enumerate() {
                let points: C = self.variant.points(position, self.candidates.len(), num_marked);
                plurality.add_weighted_ref(candidate, *votecount * points);
            }
        }

        plurality.totals()
    }

    /// Get a list of all candidates seen by this tally.
    /// Candidates are returned in no particular order.
    pub fn candidates(&self) -> Vec<T> {
        self.candidates.iter().cloned().collect()
    }
}

/// TODO: Stub
#[allow(dead_code)]
pub type DefaultNansonTally<T> = NansonTally<T, u64>;

/// TODO: Stub
#[allow(dead_code)]
pub struct NansonTally<T, C = u64>
where
    T: Eq + Clone + Hash,                             // Candidate
    C: Copy + PartialOrd + AddAssign + Num + NumCast, // Vote count type
{
    borda: BordaTally<T, C>,
}

/// TODO: Stub
#[allow(dead_code)]
pub type DefaultBaldwinTally<T> = BaldwinTally<T, u64>;

/// TODO: Stub
#[allow(dead_code)]
pub struct BaldwinTally<T, C = u64>
where
    T: Eq + Clone + Hash,                             // Candidate
    C: Copy + PartialOrd + AddAssign + Num + NumCast, // Vote count type
{
    borda: BordaTally<T, C>,
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn borda_test() -> Result<(), TallyError> {
        // From: https://en.wikipedia.org/wiki/Borda_count
        let mut borda_tally = DefaultBordaTally::new(1, Variant::Borda);
        borda_tally.add_weighted(vec!["Andrew", "Catherine", "Brian", "David"], 51)?;
        borda_tally.add_weighted(vec!["Catherine", "Brian", "David", "Andrew"], 5)?;
        borda_tally.add_weighted(vec!["Brian", "Catherine", "David", "Andrew"], 23)?;
        borda_tally.add_weighted(vec!["David", "Catherine", "Brian", "Andrew"], 21)?;

        assert!(borda_tally.totals() == vec![("Catherine", 205), ("Andrew", 153), ("Brian", 151), ("David", 91)]);
        assert!(borda_tally.winners().into_unranked() == vec!["Catherine"]);

        let mut classic_tally = DefaultBordaTally::new(1, Variant::ClassicBorda);
        classic_tally.add_weighted(vec!["Andrew", "Catherine", "Brian", "David"], 51)?;
        classic_tally.add_weighted(vec!["Catherine", "Brian", "David", "Andrew"], 5)?;
        classic_tally.add_weighted(vec!["Brian", "Catherine", "David", "Andrew"], 23)?;
        classic_tally.add_weighted(vec!["David", "Catherine", "Brian", "Andrew"], 21)?;

        assert!(classic_tally.totals() == vec![("Catherine", 305), ("Andrew", 253), ("Brian", 251), ("David", 191)]);
        assert!(classic_tally.winners().into_unranked() == vec!["Catherine"]);

        let mut dowdall_tally = BordaTally::<&str, f64>::new(1, Variant::Dowdall);
        dowdall_tally.add_weighted(vec!["Andrew", "Catherine", "Brian", "David"], 51.0)?;
        dowdall_tally.add_weighted(vec!["Catherine", "Brian", "David", "Andrew"], 5.0)?;
        dowdall_tally.add_weighted(vec!["Brian", "Catherine", "David", "Andrew"], 23.0)?;
        dowdall_tally.add_weighted(vec!["David", "Catherine", "Brian", "Andrew"], 21.0)?;

        let totals = dowdall_tally.totals();
        assert_eq!(totals[0], ("Andrew", 63.25));
        assert_eq!(totals[1], ("Catherine", 52.5));
        assert_eq!(totals[2], ("Brian", 49.5));
        assert_eq!(totals[3].0, "David"); // TODO: fix this when this bug in rust is fixed: https://github.com/rust-lang/rust/issues/62175
        assert!(dowdall_tally.winners().into_unranked() == vec!["Andrew"]);

        let mut tally = DefaultBordaTally::new(1, Variant::Borda);
        tally.add_weighted(vec!["Memphis", "Nashville", "Chattanooga", "Knoxville"], 42)?;
        tally.add_weighted(vec!["Nashville", "Chattanooga", "Knoxville", "Memphis"], 26)?;
        tally.add_weighted(vec!["Chattanooga", "Knoxville", "Nashville", "Memphis"], 15)?;
        tally.add_weighted(vec!["Knoxville", "Chattanooga", "Nashville", "Memphis"], 17)?;
        assert!(tally.totals() == vec![("Nashville", 194), ("Chattanooga", 173), ("Memphis", 126), ("Knoxville", 107)]);
        assert!(tally.winners().into_unranked() == vec!["Nashville"]);

        // Testing Modified Borda
        let mut tally = DefaultBordaTally::new(1, Variant::ModifiedClassicBorda);
        tally.add(vec!["Alice", "Bob", "Carlos"])?;
        tally.add(vec!["Alice", "Bob"])?;
        tally.add(vec!["Bob", "Carlos"])?;

        let totals = tally.totals();
        assert!(totals == vec![("Alice", 5), ("Bob", 5), ("Carlos", 2)] || totals == vec![("Bob", 5), ("Alice", 5), ("Carlos", 2)]);
        let ranked = tally.ranked();
        assert!(ranked == vec![("Alice", 0), ("Bob", 0), ("Carlos", 1)] || ranked == vec![("Bob", 0), ("Alice", 0), ("Carlos", 1)]);
        assert!(tally.candidates().len() == 3);

        // Testing custom - just assign every candidate a "1" turning this borda into appproval voting.
        let boxed_func = Box::new(|_candidate_position, _num_candidates, _num_marked| 1);
        let mut tally = DefaultBordaTally::new(1, Variant::Custom(boxed_func));
        tally.add(vec!["Alice", "Bob", "Carlos"])?;
        tally.add(vec!["Alice", "Bob"])?;
        tally.add(vec!["Bob", "Carlos"])?;
        let totals = tally.totals();
        assert!(totals == vec![("Bob", 3), ("Alice", 2), ("Carlos", 2)] || totals == vec![("Bob", 3), ("Carlos", 2), ("Alice", 2)]);
        let ranked = tally.ranked();
        assert!(ranked == vec![("Bob", 0), ("Alice", 1), ("Carlos", 1)] || ranked == vec![("Bob", 0), ("Carlos", 1), ("Alice", 1)]);
        assert!(tally.candidates().len() == 3);

        // Testin adding ref
        let vote_1 = vec!["Alice", "Bob", "Carlos"];
        let vote_2 = vec!["Alice", "Bob"];
        let mut tally = DefaultBordaTally::with_capacity(1, Variant::Borda, 3);
        tally.add_ref(&vote_1)?;
        tally.add_ref(&vote_2)?;
        assert!(tally.totals() == vec![("Alice", 4), ("Bob", 2), ("Carlos", 0)]);
        assert!(tally.ranked() == vec![("Alice", 0), ("Bob", 1), ("Carlos", 2)]);
        assert!(tally.candidates().len() == 3);

        Ok(())
    }

    #[test]
    #[should_panic]
    fn borda_panic_test() {
        // Dowdall should panic when using integers
        let _points: u64 = Variant::Dowdall.points(0, 4, 4);
    }
}