sainte_lague/
lib.rs

1#![forbid(unsafe_code, unstable_features, missing_docs)]
2#![deny(
3    warnings,
4    unused_extern_crates,
5    missing_copy_implementations,
6    missing_debug_implementations
7)]
8
9//! A rust implementation of the **[Sainte-Laguë](https://en.wikipedia.org/wiki/Webster/Sainte-Lagu%C3%AB_method)** (also known as **Webster** or **Schepers**) method. Parliament seat allocation algorithm used in multiple countries such as Germany, Latvia, New Zealand etc…
10//!
11//! *Attention: Since some countries (like Latvia or Norway) use a modification of the algorithm instead of this vanilla version, you should check your country's electoral legislature. Furthermore, I don't take any responsibility for the accuracy of the calculated numbers, even though I'm pretty confident with my implementation.*
12
13use rand::seq::SliceRandom;
14use std::error;
15use std::fmt;
16
17/// Possible error cases of [`distribute`].
18#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
19pub enum DistributionError {
20    /// A distribution couldn't be determined because multiple parties were tied for the last seat. You can tell [`distribute`] to make a draw in these situations to prevent this error case.
21    Tied,
22
23    /// The given seat count was not larger than zero.
24    InvalidSeatCount,
25
26    /// The given list of votes contained negative values.
27    NegativeVotes,
28
29    /// The given list of votes contained no values or the sum of all values was zero.
30    NoVotes,
31}
32
33impl fmt::Display for DistributionError {
34    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
35        match self {
36            &DistributionError::Tied => write!(
37                f,
38                "Tie detected, could only be resolved by randomly awarding a seat to one party."
39            ),
40            &DistributionError::InvalidSeatCount => {
41                write!(f, "Invalid seat count, must be an integer larger than 0.")
42            }
43            &DistributionError::NegativeVotes => write!(
44                f,
45                "Invalid votes, all parties must have at least zero votes."
46            ),
47            &DistributionError::NoVotes => {
48                write!(f, "Invalid votes, one party must have at least one vote.")
49            }
50        }
51    }
52}
53
54impl error::Error for DistributionError {}
55
56#[derive(Clone)]
57struct PartyQuotient {
58    party: usize,
59    quotient: f64,
60}
61
62/// Calculate the **[Sainte-Laguë](https://en.wikipedia.org/wiki/Webster/Sainte-Lagu%C3%AB_method)** distribution for the given `votes` and a parliament of size `seat_count`. Note that while votes are usually restricted to integers in normal elections, this function expects floating point numbers, allowing additional use cases.
63///
64/// The `draw_on_tie` flag should be used to indicate if the method should randomly assign seats in case of a draw or return an error instead.
65///
66/// Check [`DistributionError`] for a list of all possible error cases.
67///
68/// # Examples
69///
70/// Note that, while you would usually use the absolute vote counts to calculate a distribution, as explained before, the method is not restricted to integer input, so you can also use relative vote shares, as in in this example:
71///
72/// ```
73/// use sainte_lague::distribute;
74///
75/// let votes_german_bundestag_2013 = [41.5, 25.7, 8.6, 8.4];
76/// let seats_german_bundestag_2013 = 631;
77/// let draw_on_tie = false;
78///
79/// let distribution = distribute(&votes_german_bundestag_2013, &seats_german_bundestag_2013, &draw_on_tie);
80/// let parliament: Vec<usize> = vec![311, 193, 64, 63];
81/// assert_eq!(distribution, Ok(parliament));
82/// ```
83///
84/// The `draw_on_tie` flag is relevant in case of a draw:
85///
86/// ```
87/// use sainte_lague::{distribute, DistributionError};
88///
89/// let votes = [3.0, 3.0, 1.0];
90/// let seats = 8;
91///
92/// let distribution_without_draw = distribute(&votes, &seats, &false);
93/// assert_eq!(distribution_without_draw, Err(DistributionError::Tied));
94///
95/// let distribution_with_draw = distribute(&votes, &seats, &true);
96/// let parliament_draw_possibility_a: Vec<usize> = vec![4, 3, 1];
97/// let parliament_draw_possibility_b: Vec<usize> = vec![3, 4, 1];
98/// assert_eq!(
99///     [Ok(parliament_draw_possibility_a), Ok(parliament_draw_possibility_b)]
100///         .iter()
101///         .any(|x| x == &distribution_with_draw),
102///     true
103/// );
104/// ```
105pub fn distribute(
106    votes: &[f64],
107    seat_count: &usize,
108    draw_on_tie: &bool,
109) -> Result<Vec<usize>, DistributionError> {
110    // @todo this is certainly far from an optimal implementation, it is just a copy of
111    // https://github.com/juliuste/sainte-lague for now, which should at least work correctly
112
113    // validate prerequisites
114    if seat_count < &1 {
115        return Err(DistributionError::InvalidSeatCount);
116    }
117    let has_negative_votes = votes.iter().any(|v| v < &0.0);
118    if has_negative_votes {
119        return Err(DistributionError::NegativeVotes);
120    }
121    let total_votes: f64 = votes.iter().sum();
122    if total_votes == 0.0 {
123        return Err(DistributionError::NoVotes);
124    }
125
126    let mut party_quotients: Vec<PartyQuotient> = votes
127        .iter()
128        .enumerate()
129        .flat_map(|(i, v)| {
130            let divisors = (1..=(seat_count.clone() as i64)).map(|d| (d as f64) - 0.5);
131            return divisors.map(move |d| PartyQuotient {
132                party: i,
133                quotient: v / d,
134            });
135        })
136        .collect();
137
138    party_quotients.sort_by(|a, b| {
139        b.quotient
140            .partial_cmp(&a.quotient)
141            .unwrap_or(std::cmp::Ordering::Equal)
142    });
143
144    let last_winning_quotient = party_quotients
145        .get(seat_count.clone() - 1)
146        .map(|pq| pq.quotient)
147        .unwrap_or(0.0);
148    let mut winners: Vec<PartyQuotient> = party_quotients
149        .iter()
150        .filter(|pq| pq.quotient > last_winning_quotient)
151        .cloned()
152        .collect();
153    let mut possible_winners: Vec<PartyQuotient> = party_quotients
154        .iter()
155        .filter(|pq| pq.quotient == last_winning_quotient)
156        .cloned()
157        .collect();
158
159    // check if the "last" winner had the same quotient as the "first" loser, if so we need
160    // to make a draw to resolve the tie or return an error
161    let seats_too_many =
162        (winners.len() as i64) + (possible_winners.len() as i64) - (seat_count.clone() as i64);
163
164    if seats_too_many > 0 {
165        if !draw_on_tie {
166            return Err(DistributionError::Tied);
167        }
168        let number_of_draws = (possible_winners.len() as i64) - seats_too_many;
169        let mut drawn_winners: Vec<PartyQuotient> = (&possible_winners)
170            .choose_multiple(&mut rand::thread_rng(), number_of_draws.max(0) as usize)
171            .cloned()
172            .collect();
173        winners.append(&mut drawn_winners);
174    } else {
175        winners.append(&mut possible_winners);
176    }
177
178    let mut distribution: Vec<usize> = vec![0; votes.len()];
179    for pq in winners.iter() {
180        distribution[pq.party] += 1 // @todo
181    }
182
183    return Ok(distribution);
184}
185
186#[cfg(test)]
187mod tests {
188    use super::distribute;
189    use super::DistributionError;
190
191    #[test]
192    fn german_bundestag_2013() {
193        let votes = [41.5, 25.7, 8.6, 8.4];
194        let seats = 631;
195
196        let distribution = distribute(&votes, &seats, &false);
197        let parliament = vec![311, 193, 64, 63];
198        assert_eq!(distribution, Ok(parliament));
199    }
200
201    #[test]
202    fn rhineland_palatinate_201x() {
203        let votes = [362.0, 318.0, 126.0, 62.0, 53.0];
204        let seats = 101;
205
206        let distribution = distribute(&votes, &seats, &false);
207        let parliament = vec![39, 35, 14, 7, 6];
208        assert_eq!(distribution, Ok(parliament));
209    }
210
211    #[test]
212    fn schleswig_holstein_201x() {
213        let votes = [308.0, 304.0, 132.0, 82.0, 82.0, 46.0];
214        let seats = 69;
215
216        let distribution = distribute(&votes, &seats, &false);
217        let parliament = vec![22, 22, 10, 6, 6, 3];
218        assert_eq!(distribution, Ok(parliament));
219    }
220
221    #[test]
222    fn equal_but_no_draw_required() {
223        let votes = [415.0, 257.0, 85.0, 85.0];
224        let seats = 631;
225
226        let distribution = distribute(&votes, &seats, &false);
227        let parliament = vec![311, 192, 64, 64];
228        assert_eq!(distribution, Ok(parliament));
229    }
230
231    #[test]
232    fn equal_and_draw_required() {
233        let votes = [3.0, 3.0, 1.0];
234        let seats = 8;
235
236        let distribution_without_draw = distribute(&votes, &seats, &false);
237        assert_eq!(distribution_without_draw, Err(DistributionError::Tied));
238
239        let distribution_with_draw = distribute(&votes, &seats, &true);
240        let parliament_draw_a: Vec<usize> = vec![4, 3, 1];
241        let parliament_draw_b: Vec<usize> = vec![3, 4, 1];
242        assert_eq!(
243            [Ok(parliament_draw_a), Ok(parliament_draw_b)]
244                .iter()
245                .any(|x| x == &distribution_with_draw),
246            true
247        );
248    }
249
250    #[test]
251    fn small_parliament_no_draw_required() {
252        let votes = [2.0, 2.0];
253        let seats = 2;
254
255        let distribution_without_draw = distribute(&votes, &seats, &false);
256        assert_eq!(distribution_without_draw, Ok(vec![1, 1]));
257
258        let distribution_with_draw = distribute(&votes, &seats, &true);
259        assert_eq!(distribution_with_draw, Ok(vec![1, 1]));
260    }
261
262    #[test]
263    fn only_one_party() {
264        let votes = [3.0];
265        let seats = 10;
266
267        let distribution = distribute(&votes, &seats, &false);
268        let parliament = vec![10];
269        assert_eq!(distribution, Ok(parliament));
270    }
271
272    #[test]
273    fn invalid_seat_count() {
274        let votes = [3.0];
275        let seats = 0;
276
277        let distribution = distribute(&votes, &seats, &false);
278        assert_eq!(distribution, Err(DistributionError::InvalidSeatCount));
279    }
280
281    #[test]
282    fn no_votes() {
283        let seats = 50;
284
285        let distribution_empty_votes = distribute(&[], &seats, &false);
286        assert_eq!(distribution_empty_votes, Err(DistributionError::NoVotes));
287
288        let distribution_zero_votes = distribute(&[0.0, 0.0], &seats, &false);
289        assert_eq!(distribution_zero_votes, Err(DistributionError::NoVotes));
290
291        let distribution_valid_votes = distribute(&[0.0, 3.0], &seats, &false);
292        assert_eq!(distribution_valid_votes, Ok(vec![0, seats]));
293    }
294
295    #[test]
296    fn negative_votes() {
297        let seats = 50;
298
299        let distribution_negative_votes = distribute(&[-3.0], &seats, &false);
300        assert_eq!(
301            distribution_negative_votes,
302            Err(DistributionError::NegativeVotes)
303        );
304
305        let distribution_negative_votes_sum_zero = distribute(&[4.0, -4.0], &seats, &false);
306        assert_eq!(
307            distribution_negative_votes_sum_zero,
308            Err(DistributionError::NegativeVotes)
309        );
310    }
311}
sainte_lague/lib.rs

sainte_lague/
lib.rs
