wybr 0.0.6

Collection of preferential voting methods
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195

//! Baldwin's method
//!
//! [Baldwin's method](https://en.wikipedia.org/wiki/Nanson's_method) is an extension of Borda count
//! in which candidates are progressively eliminated rather than ranked once.
//! Namely, in each round one candidate with smallest Borda score is eliminated, so
//! that the ballots are shifted giving more points to other candidates.
//! Such procedure is repeated until one winner is left.
//!
//! There can be a tie, in this case random tie breaking is used to select worse candidate among
//! these with smallest score.
//!
//! # Examples
//!
//! ```
//! use wybr::{Tally,Baldwin,Outcome};
//!
//! //Load the Tennessee Wikipedia example
//! let tally=Tally::from_blt_file("examples/tennessee.blt").unwrap();
//! let mut nanson=Baldwin::new(&tally);
//!
//! //Perform simple election with default, Borda1 rules
//! let outcome=Baldwin::new(&tally).run().unwrap();
//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
//! ```

use crate::common::BordaKind;
use crate::outcome::GenericOutcome;
use crate::prng::Prng;
use crate::tally::Tally;
use crate::ElectionError;
use crate::VoteTree;
use std::collections::HashSet;

use BordaKind::*;

pub struct Baldwin<'a> {
    tally: &'a VoteTree,
    borda_kind: BordaKind,
    withdraw: HashSet<u32>,
    max_rank: Option<u32>,
    seed: u32,
}

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

    /// Performs Baldwin election; returns the ID of a winner, or an `ElectionError`.
    ///
    /// # Notes
    /// Baldwin's method is essentially an iterated Borda election; on each iteration all candidates
    /// with Borda score lower or equal than average are eliminated.
    /// All parameters of the Baldwin method are identical to these of the Borda method.
    ///
    /// # 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);
        use crate::methods::borda::Borda;
        let mut borda = Borda::new(self.tally);
        borda.kind(self.borda_kind);
        if let Some(mr) = self.max_rank {
            borda.max_rank(mr);
        };

        let mut eliminated: HashSet<u32> = HashSet::new();
        for e in self.withdraw.iter() {
            eliminated.insert(*e);
        }

        let winner = loop {
            let scores = borda.withdraw(eliminated.iter().cloned()).scores()?;
            if scores.is_empty() {
                return Err(ElectionError::NotEnoughCandidates);
            }
            if scores.len() == 1 {
                //We have only one candidate, hence it wins
                break *scores.keys().next().unwrap();
            }

            let min = scores.values().min().unwrap();
            let mut loosers: Vec<u32> = scores
                .iter()
                .filter_map(|(c, s)| if s == min { Some(*c) } else { None })
                .collect();
            loosers.sort_unstable();
            let looser = rnd.only_or_random(&loosers).unwrap();

            if scores.len() == 2 {
                //We have one left, it must be a winner
                break *scores.keys().find(|&&c| c != looser).unwrap();
            }
            eliminated.insert(looser);
        };

        Ok(GenericOutcome::new(
            Some(winner),
            self.withdraw.iter().cloned(),
            self.tally.get_candidates(),
            rnd.sealed(),
            self.tally.get_meta(),
        ))
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::outcome::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 = Baldwin::new(&tally).run().unwrap();
        assert!(outcome.deterministic());
        assert_eq!(outcome.winner_name().unwrap(), "Nashville");
    }
    #[test]
    fn with_tie() {
        let x = [
            (10, vec![0, 1]),
            (10, vec![1, 0]),
            (5, vec![2, 3]),
            (5, vec![3, 2]),
        ]
        .iter()
        .collect();
        let mut stub = Baldwin::new(&x);
        stub.max_rank(1);
        stub.seed(97);
        let ans = stub.kind(Borda0).run().unwrap();
        assert!(!ans.deterministic());
        assert_eq!(ans.winner().unwrap(), 1);
        stub.seed(99);
        assert_eq!(stub.kind(Borda0).run().unwrap().winner().unwrap(), 1);
    }
}