aboutsummaryrefslogtreecommitdiff
path: root/src/election.rs
blob: 2521ec49b876ee678ed880dc6a1bed2d3d1d3d46 (plain)
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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
1/*  OpenTally: Open-source election vote counting
2 *  Copyright © 2021 Lee Yingtong Li (RunasSudo)
3 *
4 *  This program is free software: you can redistribute it and/or modify
5 *  it under the terms of the GNU Affero General Public License as published by
6 *  the Free Software Foundation, either version 3 of the License, or
7 *  (at your option) any later version.
8 *
9 *  This program is distributed in the hope that it will be useful,
10 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
11 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12 *  GNU Affero General Public License for more details.
13 *
14 *  You should have received a copy of the GNU Affero General Public License
15 *  along with this program.  If not, see <https://www.gnu.org/licenses/>.
16 */
17
18use crate::constraints::{Constraints, ConstraintMatrix};
19use crate::logger::Logger;
20use crate::numbers::Number;
21use crate::sharandom::SHARandom;
22
23use std::collections::HashMap;
24
25/// An election to be counted
26pub struct Election<N> {
27	/// Name of the election
28	pub name: String,
29	/// Number of candidates to be elected
30	pub seats: usize,
31	/// [Vec] of [Candidate]s in the election
32	pub candidates: Vec<Candidate>,
33	/// Indexes of withdrawn candidates
34	pub withdrawn_candidates: Vec<usize>,
35	/// [Vec] of [Ballot]s cast in the election
36	pub ballots: Vec<Ballot<N>>,
37	/// Constraints on candidates
38	pub constraints: Option<Constraints>,
39}
40
41impl<N: Number> Election<N> {
42	/// Parse the given BLT file and return an [Election]
43	pub fn from_blt<I: Iterator<Item=String>>(mut lines: I) -> Self {
44		// Read first line
45		let line = lines.next().expect("Unexpected EOF");
46		let mut bits = line.split(" ");
47		let num_candidates = bits.next().expect("Syntax Error").parse().expect("Syntax Error");
48		let seats: usize = bits.next().expect("Syntax Error").parse().expect("Syntax Error");
49		
50		// Initialise the Election object
51		let mut election = Election {
52			name: String::new(),
53			seats: seats,
54			candidates: Vec::with_capacity(num_candidates),
55			withdrawn_candidates: Vec::new(),
56			ballots: Vec::new(),
57			constraints: None,
58		};
59		
60		// Read ballots
61		for line in &mut lines {
62			if line == "0" {
63				break;
64			}
65			
66			let mut bits = line.split(" ");
67			
68			if line.starts_with("-") {
69				// Withdrawn candidates
70				for bit in bits.into_iter() {
71					let val = bit[1..bit.len()].parse::<usize>().expect("Syntax Error");
72					election.withdrawn_candidates.push(val - 1);
73				}
74				continue;
75			}
76			
77			let value = N::parse(bits.next().expect("Syntax Error"));
78			
79			let mut ballot = Ballot {
80				orig_value: value,
81				preferences: Vec::new(),
82			};
83			
84			for preference in bits {
85				if preference != "0" {
86					let preference = preference.parse::<usize>().expect("Syntax Error");
87					ballot.preferences.push(preference - 1);
88				}
89			}
90			
91			election.ballots.push(ballot);
92		}
93		
94		// Read candidates
95		for line in lines.by_ref().take(num_candidates) {
96			let mut line = &line[..];
97			if line.starts_with("\"") && line.ends_with("\"") {
98				line = &line[1..line.len()-1];
99			}
100			
101			election.candidates.push(Candidate { name: line.to_string() });
102		}
103		
104		// Read name
105		let line = lines.next().expect("Syntax Error");
106		let mut line = &line[..];
107		if line.starts_with("\"") && line.ends_with("\"") {
108			line = &line[1..line.len()-1];
109		}
110		election.name.push_str(line);
111		
112		return election;
113	}
114	
115	/// Convert ballots with weight >1 to multiple ballots of weight 1
116	pub fn normalise_ballots(&mut self) {
117		let mut normalised_ballots = Vec::new();
118		for ballot in self.ballots.iter() {
119			let mut n = N::new();
120			let one = N::one();
121			while n < ballot.orig_value {
122				let new_ballot = Ballot {
123					orig_value: N::one(),
124					preferences: ballot.preferences.clone(),
125				};
126				normalised_ballots.push(new_ballot);
127				n += &one;
128			}
129		}
130		self.ballots = normalised_ballots;
131	}
132}
133
134/// A candidate in an [Election]
135#[derive(PartialEq, Eq, Hash)]
136pub struct Candidate {
137	/// Name of the candidate
138	pub name: String,
139}
140
141/// The current state of counting an [Election]
142//#[derive(Clone)]
143pub struct CountState<'a, N: Number> {
144	/// Pointer to the [Election] being counted
145	pub election: &'a Election<N>,
146	
147	/// [HashMap] of [CountCard]s for each [Candidate] in the election
148	pub candidates: HashMap<&'a Candidate, CountCard<'a, N>>,
149	/// [CountCard] representing the exhausted pile
150	pub exhausted: CountCard<'a, N>,
151	/// [CountCard] representing loss by fraction
152	pub loss_fraction: CountCard<'a, N>,
153	
154	/// [crate::stv::meek::BallotTree] for Meek STV
155	pub ballot_tree: Option<crate::stv::meek::BallotTree<'a, N>>,
156	
157	/// Values used to break ties, based on forwards tie-breaking
158	pub forwards_tiebreak: Option<HashMap<&'a Candidate, usize>>,
159	/// Values used to break ties, based on backwards tie-breaking
160	pub backwards_tiebreak: Option<HashMap<&'a Candidate, usize>>,
161	/// [SHARandom] for random tie-breaking
162	pub random: Option<SHARandom<'a>>,
163	
164	/// Quota for election
165	pub quota: Option<N>,
166	/// Vote required for election
167	///
168	/// Only used in ERS97/ERS76.
169	pub vote_required_election: Option<N>,
170	
171	/// Number of candidates who have been declared elected
172	pub num_elected: usize,
173	/// Number of candidates who have been declared excluded
174	pub num_excluded: usize,
175	
176	/// [ConstraintMatrix] for constrained elections
177	pub constraint_matrix: Option<ConstraintMatrix>,
178	
179	/// The type of stage being counted
180	///
181	/// For example, "Surplus of", "Exclusion of"
182	pub kind: Option<&'a str>,
183	/// The description of the stage being counted, excluding [CountState::kind]
184	pub title: String,
185	/// [Logger] for this stage of the count
186	pub logger: Logger<'a>,
187}
188
189impl<'a, N: Number> CountState<'a, N> {
190	/// Construct a new blank [CountState] for the given [Election]
191	pub fn new(election: &'a Election<N>) -> Self {
192		let mut state = CountState {
193			election: &election,
194			candidates: HashMap::new(),
195			exhausted: CountCard::new(),
196			loss_fraction: CountCard::new(),
197			ballot_tree: None,
198			forwards_tiebreak: None,
199			backwards_tiebreak: None,
200			random: None,
201			quota: None,
202			vote_required_election: None,
203			num_elected: 0,
204			num_excluded: 0,
205			constraint_matrix: None,
206			kind: None,
207			title: String::new(),
208			logger: Logger { entries: Vec::new() },
209		};
210		
211		for candidate in election.candidates.iter() {
212			state.candidates.insert(candidate, CountCard::new());
213		}
214		
215		for withdrawn_idx in election.withdrawn_candidates.iter() {
216			state.candidates.get_mut(&election.candidates[*withdrawn_idx]).unwrap().state = CandidateState::Withdrawn;
217		}
218		
219		if let Some(constraints) = &election.constraints {
220			let mut num_groups: Vec<usize> = constraints.0.iter().map(|c| c.groups.len()).collect();
221			let mut cm = ConstraintMatrix::new(&mut num_groups[..]);
222			
223			// Init constraint matrix total cells min/max
224			for (i, constraint) in constraints.0.iter().enumerate() {
225				for (j, group) in constraint.groups.iter().enumerate() {
226					let mut idx = vec![0; constraints.0.len()];
227					idx[i] = j + 1;
228					let mut cell = &mut cm[&idx];
229					cell.min = group.min;
230					cell.max = group.max;
231				}
232			}
233			
234			// Fill in grand total, etc.
235			cm.update_from_state(&state.election, &state.candidates);
236			cm.init();
237			//println!("{}", cm);
238			
239			// Require correct number of candidates to be elected
240			let idx = vec![0; constraints.0.len()];
241			cm[&idx].min = election.seats;
242			cm[&idx].max = election.seats;
243			
244			state.constraint_matrix = Some(cm);
245		}
246		
247		return state;
248	}
249	
250	/// [Step](CountCard::step) every [CountCard] to prepare for the next stage
251	pub fn step_all(&mut self) {
252		for (_, count_card) in self.candidates.iter_mut() {
253			count_card.step();
254		}
255		self.exhausted.step();
256		self.loss_fraction.step();
257	}
258}
259
260/// Current state of a [Candidate] during an election count
261#[derive(Clone)]
262pub struct CountCard<'a, N> {
263	/// State of the candidate
264	pub state: CandidateState,
265	/// Order of election or exclusion
266	///
267	/// Positive integers represent order of election; negative integers represent order of exclusion
268	pub order_elected: isize,
269	
270	//pub orig_votes: N,
271	/// Net votes transferred to this candidate in this stage
272	pub transfers: N,
273	/// Votes of the candidate at the end of this stage
274	pub votes: N,
275	
276	/// Parcels of ballots assigned to this candidate
277	pub parcels: Vec<Parcel<'a, N>>,
278	
279	/// Candidate's keep value (Meek STV)
280	pub keep_value: Option<N>,
281}
282
283impl<'a, N: Number> CountCard<'a, N> {
284	/// Returns a new blank [CountCard]
285	pub fn new() -> Self {
286		return CountCard {
287			state: CandidateState::Hopeful,
288			order_elected: 0,
289			//orig_votes: N::new(),
290			transfers: N::new(),
291			votes: N::new(),
292			parcels: Vec::new(),
293			keep_value: None,
294		};
295	}
296	
297	/// Transfer the given number of votes to this [CountCard], incrementing [transfers](CountCard::transfers) and [votes](CountCard::votes)
298	pub fn transfer(&mut self, transfer: &'_ N) {
299		self.transfers += transfer;
300		self.votes += transfer;
301	}
302	
303	/// Set [transfers](CountCard::transfers) to 0
304	pub fn step(&mut self) {
305		//self.orig_votes = self.votes.clone();
306		self.transfers = N::new();
307	}
308	
309	/// Concatenate all parcels into a single parcel, leaving [parcels](CountCard::parcels) empty
310	pub fn concat_parcels(&mut self) -> Vec<Vote<'a, N>> {
311		let mut result = Vec::new();
312		for parcel in self.parcels.iter_mut() {
313			result.append(&mut parcel.votes);
314		}
315		return result;
316	}
317}
318
319/// Parcel of [Vote]s during a count
320#[derive(Clone)]
321pub struct Parcel<'a, N> {
322	/// [Vote]s in this parcel
323	pub votes: Vec<Vote<'a, N>>,
324	/// Order for sorting with [opentally::stv::ExclusionMethod::BySource]
325	pub source_order: usize,
326}
327
328/// Represents a [Ballot] with an associated value
329#[derive(Clone)]
330pub struct Vote<'a, N> {
331	/// Ballot from which the vote is derived
332	pub ballot: &'a Ballot<N>,
333	/// Current value of the ballot
334	pub value: N,
335	/// Index of the next preference to examine
336	pub up_to_pref: usize,
337}
338
339/// A record of a voter's preferences
340pub struct Ballot<N> {
341	/// Original value/weight of the ballot
342	pub orig_value: N,
343	/// Indexes of candidates preferenced on the ballot
344	pub preferences: Vec<usize>,
345}
346
347/// State of a [Candidate] during a count
348#[allow(dead_code)]
349#[derive(PartialEq)]
350#[derive(Clone)]
351pub enum CandidateState {
352	/// Hopeful (continuing candidate)
353	Hopeful,
354	/// Required by constraints to be guarded from exclusion
355	Guarded,
356	/// Declared elected
357	Elected,
358	/// Required by constraints to be doomed to be excluded
359	Doomed,
360	/// Withdrawn candidate
361	Withdrawn,
362	/// Declared excluded
363	Excluded,
364}
Contact (issues, pull requests, etc.) at git@yingtongli.me. Generated by cgit.