aboutsummaryrefslogtreecommitdiff
path: root/src/stv/gregory/transfers.rs
blob: 88338af9c0d722dac873ce77a7fe4d39e13b2b85 (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
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
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
18#[cfg(not(target_arch = "wasm32"))]
19use prettytable::{Cell, Row, Table};
20#[cfg(target_arch = "wasm32")]
21use super::prettytable_html::{Cell, Row, Table};
22
23use crate::election::{Candidate, CountState};
24use crate::numbers::Number;
25use crate::stv::{STVOptions, SumSurplusTransfersMode};
26
27use std::collections::HashMap;
28
29/// Table describing vote transfers during a surplus distribution or exclusion
30pub struct TransferTable<'e, N: Number> {
31	/// Continuing candidates
32	pub hopefuls: Vec<&'e Candidate>,
33	
34	/// Columns in the table
35	pub columns: Vec<TransferTableColumn<'e, N>>,
36	
37	/// Total column
38	pub total: TransferTableColumn<'e, N>,
39	
40	/// Size of surplus, or `None` if an exclusion
41	pub surplus: Option<N>,
42	/// Surplus fraction, or `None` if votes not reweighted/an exclusion (for display/optimisation only)
43	pub surpfrac: Option<N>,
44	/// Numerator of surplus fraction, or `None` if votes not reweighted/an exclusion
45	pub surpfrac_numer: Option<N>,
46	/// Denominator of surplus fraction, or `None`
47	pub surpfrac_denom: Option<N>,
48}
49
50impl<'e, N: Number> TransferTable<'e, N> {
51	/// Return a new [TransferTable] for an exclusion
52	pub fn new_exclusion(hopefuls: Vec<&'e Candidate>) -> Self {
53		TransferTable {
54			hopefuls,
55			columns: Vec::new(),
56			total: TransferTableColumn {
57				value_fraction: N::new(),
58				cells: HashMap::new(),
59				exhausted: TransferTableCell { ballots: N::new(), votes_in: N::new(), votes_out: N::new() },
60				total: TransferTableCell { ballots: N::new(), votes_in: N::new(), votes_out: N::new() },
61			},
62			surplus: None,
63			surpfrac: None,
64			surpfrac_numer: None,
65			surpfrac_denom: None,
66		}
67	}
68	
69	/// Return a new [TransferTable] for a surplus distribution
70	pub fn new_surplus(hopefuls: Vec<&'e Candidate>, surplus: N, surpfrac: Option<N>, surpfrac_numer: Option<N>, surpfrac_denom: Option<N>) -> Self {
71		TransferTable {
72			hopefuls,
73			columns: Vec::new(),
74			total: TransferTableColumn {
75				value_fraction: N::new(),
76				cells: HashMap::new(),
77				exhausted: TransferTableCell { ballots: N::new(), votes_in: N::new(), votes_out: N::new() },
78				total: TransferTableCell { ballots: N::new(), votes_in: N::new(), votes_out: N::new() },
79			},
80			surplus: Some(surplus),
81			surpfrac,
82			surpfrac_numer,
83			surpfrac_denom,
84		}
85	}
86	
87	/// Record the specified transfer
88	pub fn add_transfers(&mut self, value_fraction: &N, candidate: &'e Candidate, ballots: &N) {
89		for col in self.columns.iter_mut() {
90			if &col.value_fraction == value_fraction {
91				col.add_transfers(candidate, ballots);
92				return;
93			}
94		}
95		
96		let mut col = TransferTableColumn {
97			value_fraction: value_fraction.clone(),
98			cells: HashMap::new(),
99			exhausted: TransferTableCell { ballots: N::new(), votes_in: N::new(), votes_out: N::new() },
100			total: TransferTableCell { ballots: N::new(), votes_in: N::new(), votes_out: N::new() },
101		};
102		col.add_transfers(candidate, ballots);
103		self.columns.push(col);
104	}
105	
106	/// Record the specified exhaustion
107	pub fn add_exhausted(&mut self, value_fraction: &N, ballots: &N) {
108		for col in self.columns.iter_mut() {
109			if &col.value_fraction == value_fraction {
110				col.exhausted.ballots += ballots;
111				return;
112			}
113		}
114		
115		let col = TransferTableColumn {
116			value_fraction: value_fraction.clone(),
117			cells: HashMap::new(),
118			exhausted: TransferTableCell { ballots: ballots.clone(), votes_in: N::new(), votes_out: N::new() },
119			total: TransferTableCell { ballots: N::new(), votes_in: N::new(), votes_out: N::new() },
120		};
121		self.columns.push(col);
122	}
123	
124	/// Calculate the votes to be transferred according to this table
125	pub fn calculate(&mut self, opts: &STVOptions) {
126		// Use weighted rules if exclusion or WIGM
127		let is_weighted = self.surplus.is_none() || opts.surplus.is_weighted();
128		
129		// Iterate through columns
130		for column in self.columns.iter_mut() {
131			let mut new_value_fraction = N::new();
132			if self.surplus.is_some() && opts.sum_surplus_transfers == SumSurplusTransfersMode::PerBallot {
133				if is_weighted {
134					new_value_fraction = column.value_fraction.clone();
135					// If surplus, multiply by surplus fraction
136					if let Some(n) = &self.surpfrac_numer {
137						new_value_fraction *= n;
138					}
139				} else {
140					if let Some(n) = &self.surpfrac_numer {
141						new_value_fraction = n.clone();
142					} else {
143						// Transferred at original value
144						new_value_fraction = column.value_fraction.clone();
145					}
146				}
147				
148				if let Some(n) = &self.surpfrac_denom {
149					new_value_fraction /= n;
150				}
151				
152				// Round if required
153				if let Some(dps) = opts.round_values {
154					new_value_fraction.floor_mut(dps);
155				}
156			}
157			
158			// Candidate votes
159			for (candidate, cell) in column.cells.iter_mut() {
160				column.total.ballots += &cell.ballots;
161				self.total.add_transfers(*candidate, &cell.ballots);
162				self.total.total.ballots += &cell.ballots;
163				
164				let votes_in = cell.ballots.clone() * &column.value_fraction;
165				cell.votes_in += &votes_in;
166				column.total.votes_in += &votes_in;
167				self.total.cells.get_mut(*candidate).unwrap().votes_in += &votes_in;
168				self.total.total.votes_in += votes_in;
169				
170				if self.surplus.is_some() && opts.sum_surplus_transfers == SumSurplusTransfersMode::PerBallot {
171					let votes_out = cell.ballots.clone() * &new_value_fraction;
172					cell.votes_out += &votes_out;
173					column.total.votes_out += &votes_out;
174					self.total.cells.get_mut(*candidate).unwrap().votes_out += &votes_out;
175					self.total.total.votes_out += votes_out;
176				}
177			}
178			
179			// Exhausted votes
180			column.total.ballots += &column.exhausted.ballots;
181			self.total.exhausted.ballots += &column.exhausted.ballots;
182			self.total.total.ballots += &column.exhausted.ballots;
183			
184			let votes_in = column.exhausted.ballots.clone() * &column.value_fraction;
185			column.exhausted.votes_in += &votes_in;
186			column.total.votes_in += &votes_in;
187			self.total.exhausted.votes_in += &votes_in;
188			self.total.total.votes_in += votes_in;
189			
190			if self.surplus.is_some() && opts.sum_surplus_transfers == SumSurplusTransfersMode::PerBallot {
191				if !opts.transferable_only {
192					let votes_out = column.exhausted.ballots.clone() * &new_value_fraction;
193					column.exhausted.votes_out += &votes_out;
194					column.total.votes_out += &votes_out;
195					self.total.exhausted.votes_out += &votes_out;
196					self.total.total.votes_out += votes_out;
197				}
198			}
199		}
200		
201		// Need to calculate votes_out?
202		if self.surplus.is_none() || opts.sum_surplus_transfers == SumSurplusTransfersMode::ByValue {
203			for (_candidate, cell) in self.total.cells.iter_mut() {
204				let mut votes_out;
205				if is_weighted {
206					votes_out = cell.votes_in.clone();
207				} else {
208					votes_out = cell.ballots.clone();
209				}
210				
211				// If surplus, multiply by surplus fraction
212				if let Some(n) = &self.surpfrac_numer {
213					votes_out *= n;
214				}
215				if let Some(n) = &self.surpfrac_denom {
216					votes_out /= n;
217				}
218				
219				cell.votes_out = votes_out; // Rounded later
220			}
221			
222			if self.surplus.is_none() || !opts.transferable_only {
223				let mut votes_out;
224				if is_weighted {
225					votes_out = self.total.exhausted.votes_in.clone();
226				} else {
227					votes_out = self.total.exhausted.ballots.clone();
228				}
229				
230				// If surplus, multiply by surplus fraction
231				if let Some(n) = &self.surpfrac_numer {
232					votes_out *= n;
233				}
234				if let Some(n) = &self.surpfrac_denom {
235					votes_out /= n;
236				}
237				
238				self.total.exhausted.votes_out = votes_out; // Rounded later
239			}
240		}
241		
242		// Round if required
243		if let Some(dps) = opts.round_votes {
244			for (_candidate, cell) in self.total.cells.iter_mut() {
245				cell.votes_out.floor_mut(dps);
246			}
247			
248			self.total.exhausted.votes_out.floor_mut(dps);
249		}
250	}
251	
252	/// Apply the transfers described in the table to the count sheet
253	///
254	/// Credit continuing candidates and exhausted pile with the appropriate number of ballot papers and votes.
255	pub fn apply_to(&self, state: &mut CountState<N>, opts: &STVOptions) -> N {
256		let mut checksum = N::new();
257		
258		// Credit transferred votes
259		for (candidate, count_card) in state.candidates.iter_mut() {
260			if let Some(cell) = self.total.cells.get(candidate) {
261				count_card.transfer(&cell.votes_out);
262				count_card.ballot_transfers += &cell.ballots;
263				checksum += &cell.votes_out;
264			}
265		}
266		
267		// Credit exhausted votes
268		// If exclusion or not --transferable-only
269		if self.surplus.is_none() || !opts.transferable_only {
270			// Standard rules
271			state.exhausted.transfer(&self.total.exhausted.votes_out);
272			state.exhausted.ballot_transfers += &self.total.exhausted.ballots;
273			checksum += &self.total.exhausted.votes_out;
274		} else {
275			// Credit only nontransferable difference
276			if self.surpfrac_numer.is_none() {
277				// TODO: Is there a purer way of calculating this?
278				let difference = self.surplus.as_ref().unwrap().clone() - &checksum;
279				state.exhausted.transfer(&difference);
280				checksum += difference;
281				
282				for column in self.columns.iter() {
283					state.exhausted.ballot_transfers += &column.exhausted.ballots;
284				}
285			} else {
286				// No ballots exhaust
287			}
288		}
289		
290		return checksum;
291	}
292	
293	/// Render table as [Table]
294	fn render(&self, opts: &STVOptions) -> Table {
295		let mut table = Table::new();
296		set_table_format(&mut table);
297		
298		let show_transfers_per_ballot = self.surpfrac.is_some() && opts.sum_surplus_transfers == SumSurplusTransfersMode::PerBallot;
299		
300		let num_cols;
301		if show_transfers_per_ballot {
302			num_cols = self.columns.len() * 3 + 4;
303		} else {
304			if self.surpfrac.is_none() {
305				num_cols = self.columns.len() * 2 + 3;
306			} else {
307				num_cols = self.columns.len() * 2 + 4;
308			}
309		}
310		
311		// ----------
312		// Header row
313		
314		let mut row = Vec::with_capacity(num_cols);
315		row.push(Cell::new("Preference"));
316		for column in self.columns.iter() {
317			row.push(Cell::new(&format!("Ballots @ {:.dps$}", column.value_fraction, dps=opts.pp_decimals)).style_spec("cH2"));
318			
319			if show_transfers_per_ballot {
320				row.push(Cell::new(&format!("× {:.dps$}", self.surpfrac.as_ref().unwrap(), dps=opts.pp_decimals)).style_spec("r"));
321			}
322		}
323		row.push(Cell::new("Total").style_spec("cH2"));
324		if self.surpfrac.is_some() {
325			row.push(Cell::new(&format!("× {:.dps$}", self.surpfrac.as_ref().unwrap(), dps=opts.pp_decimals)).style_spec("r"));
326		}
327		table.set_titles(Row::new(row));
328		
329		// --------------
330		// Candidate rows
331		
332		for candidate in self.hopefuls.iter() {
333			let mut row = Vec::with_capacity(num_cols);
334			row.push(Cell::new(&candidate.name));
335			for column in self.columns.iter() {
336				if let Some(cell) = column.cells.get(candidate) {
337					row.push(Cell::new(&format!("{:.0}", cell.ballots)).style_spec("r"));
338					row.push(Cell::new(&format!("{:.dps$}", cell.votes_in, dps=opts.pp_decimals)).style_spec("r"));
339					if show_transfers_per_ballot {
340						row.push(Cell::new(&format!("{:.dps$}", cell.votes_out, dps=opts.pp_decimals)).style_spec("r"));
341					}
342				} else {
343					row.push(Cell::new(""));
344					row.push(Cell::new(""));
345					if show_transfers_per_ballot {
346						row.push(Cell::new(""));
347					}
348				}
349			}
350			
351			// Totals
352			if let Some(cell) = self.total.cells.get(candidate) {
353				row.push(Cell::new(&format!("{:.0}", cell.ballots)).style_spec("r"));
354				row.push(Cell::new(&format!("{:.dps$}", cell.votes_in, dps=opts.pp_decimals)).style_spec("r"));
355				if self.surpfrac.is_some() {
356					row.push(Cell::new(&format!("{:.dps$}", cell.votes_out, dps=opts.pp_decimals)).style_spec("r"));
357				}
358			} else {
359				row.push(Cell::new(""));
360				row.push(Cell::new(""));
361				if self.surpfrac.is_some() {
362					row.push(Cell::new(""));
363				}
364			}
365			
366			table.add_row(Row::new(row));
367		}
368		
369		// -------------
370		// Exhausted row
371		
372		let mut row = Vec::with_capacity(num_cols);
373		row.push(Cell::new("Exhausted"));
374		for column in self.columns.iter() {
375			if !column.exhausted.ballots.is_zero() {
376				row.push(Cell::new(&format!("{:.0}", column.exhausted.ballots)).style_spec("r"));
377				row.push(Cell::new(&format!("{:.dps$}", column.exhausted.votes_in, dps=opts.pp_decimals)).style_spec("r"));
378				if show_transfers_per_ballot {
379					if column.exhausted.votes_out.is_zero() {
380						row.push(Cell::new("-").style_spec("c"));
381					} else {
382						row.push(Cell::new(&format!("{:.dps$}", column.exhausted.votes_out, dps=opts.pp_decimals)).style_spec("r"));
383					}
384				}
385			} else {
386				row.push(Cell::new(""));
387				row.push(Cell::new(""));
388				if show_transfers_per_ballot {
389					row.push(Cell::new(""));
390				}
391			}
392		}
393		
394		// Totals
395		if !self.total.exhausted.ballots.is_zero() {
396			row.push(Cell::new(&format!("{:.0}", self.total.exhausted.ballots)).style_spec("r"));
397			row.push(Cell::new(&format!("{:.dps$}", self.total.exhausted.votes_in, dps=opts.pp_decimals)).style_spec("r"));
398			if self.surpfrac.is_some() {
399				if self.total.exhausted.votes_out.is_zero() {
400					row.push(Cell::new("-").style_spec("c"));
401				} else {
402					row.push(Cell::new(&format!("{:.dps$}", self.total.exhausted.votes_out, dps=opts.pp_decimals)).style_spec("r"));
403				}
404			}
405		} else {
406			row.push(Cell::new(""));
407			row.push(Cell::new(""));
408			if self.surpfrac.is_some() {
409				row.push(Cell::new(""));
410			}
411		}
412		
413		table.add_row(Row::new(row));
414		
415		// ----------
416		// Totals row
417		
418		let mut row = Vec::with_capacity(num_cols);
419		row.push(Cell::new("Total"));
420		
421		for column in self.columns.iter() {
422			row.push(Cell::new(&format!("{:.0}", column.total.ballots)).style_spec("r"));
423			row.push(Cell::new(&format!("{:.dps$}", column.total.votes_in, dps=opts.pp_decimals)).style_spec("r"));
424			if show_transfers_per_ballot {
425				row.push(Cell::new(&format!("{:.dps$}", column.total.votes_out, dps=opts.pp_decimals)).style_spec("r"));
426			}
427		}
428		
429		// Grand total cell
430		
431		let mut gt_ballots = N::new();
432		let mut gt_votes_in = N::new();
433		let mut gt_votes_out = N::new();
434		
435		for candidate in self.hopefuls.iter() {
436			if let Some(cell) = self.total.cells.get(candidate) {
437				gt_ballots += &cell.ballots;
438				gt_votes_in += &cell.votes_in;
439				gt_votes_out += &cell.votes_out;
440			}
441		}
442		gt_ballots += &self.total.exhausted.ballots;
443		gt_votes_in += &self.total.exhausted.votes_in;
444		gt_votes_out += &self.total.exhausted.votes_out;
445		
446		row.push(Cell::new(&format!("{:.0}", gt_ballots)).style_spec("r"));
447		row.push(Cell::new(&format!("{:.dps$}", gt_votes_in, dps=opts.pp_decimals)).style_spec("r"));
448		if self.surpfrac.is_some() {
449			row.push(Cell::new(&format!("{:.dps$}", gt_votes_out, dps=opts.pp_decimals)).style_spec("r"));
450		}
451		
452		table.add_row(Row::new(row));
453		
454		return table;
455	}
456	
457	/// Render table as plain text
458	//#[cfg(not(target_arch = "wasm32"))]
459	pub fn render_text(&self, opts: &STVOptions) -> String {
460		return self.render(opts).to_html();
461	}
462	
463	// Render table as HTML
464	//pub fn render_html(&self, opts: &STVOptions) -> String {
465	//	return self.render(opts).to_string();
466	//}
467}
468
469/// Column in a [TransferTable]
470pub struct TransferTableColumn<'e, N: Number> {
471	/// Value fraction of ballots counted in this column
472	pub value_fraction: N,
473	
474	/// Cells in this column
475	pub cells: HashMap<&'e Candidate, TransferTableCell<N>>,
476	
477	/// Exhausted cell
478	pub exhausted: TransferTableCell<N>,
479	
480	/// Totals cell
481	pub total: TransferTableCell<N>,
482}
483
484impl<'e, N: Number> TransferTableColumn<'e, N> {
485	/// Record the specified transfer
486	pub fn add_transfers(&mut self, candidate: &'e Candidate, ballots: &N) {
487		if let Some(cell) = self.cells.get_mut(candidate) {
488			cell.ballots += ballots;
489		} else {
490			let cell = TransferTableCell {
491				ballots: ballots.clone(),
492				votes_in: N::new(),
493				votes_out: N::new(),
494			};
495			self.cells.insert(candidate, cell);
496		}
497	}
498}
499
500/// Cell in a [TransferTable], representing transfers to one candidate at a particular value
501pub struct TransferTableCell<N: Number> {
502	/// Ballots expressing a next preference for the continuing candidate
503	pub ballots: N,
504	/// Value of votes when received by the transferring candidate
505	pub votes_in: N,
506	/// Votes transferred to the continuing candidate
507	pub votes_out: N,
508}
509
510#[cfg(not(target_arch = "wasm32"))]
511fn set_table_format(table: &mut Table) {
512	table.set_format(*prettytable::format::consts::FORMAT_NO_LINESEP_WITH_TITLE);
513}
514
515#[cfg(target_arch = "wasm32")]
516fn set_table_format(_table: &mut Table) {
517	// No op
518}
Contact (issues, pull requests, etc.) at git@yingtongli.me. Generated by cgit.