Add forwards tie breaking

docs/options.md

@@ -118,11 +118,12 @@ Other surplus transfer methods, such as non-fractional transfers (e.g. random sa
 
 This dropdown allows you to select how ties (in surplus transfer or exclusion) are broken. The options are:
 
-* *Backwards*: Ties are broken according to which tied candidate had the most/fewest votes at the end of the last stage where one tied candidate had more/fewer votes than the others, if such a stage exists.
+* *Backwards*: Ties are broken according to which tied candidate had the most/fewest votes at the end of the *most recent* stage where one tied candidate had more/fewer votes than the others, if such a stage exists.
+* *Fowards*: Ties are broken according to which tied candidate had the most/fewest votes at the end of the *earliest* stage where one tied candidate had more/fewer votes than the others, if such a stage exists.
 * *Random*: Ties are broken at random (see *Random seed*).
 * *Prompt*: The user is prompted to break the tie.
 
-Multiple tie breaking methods can be specified. If the first method cannot resolve the tie, the next is tried, and so on. In the web application, 2 options are available (‘*Backwards then random*’ and ‘*Random*’). On the Python command line, the `--ties` option can be specified multiple times (e.g. `--ties backwards --ties random`).
+Multiple tie breaking methods can be specified. If the first method cannot resolve the tie, the next is tried, and so on. In the web application, 4 options are available (‘*Backwards then random*’, ‘*Forwards then random*’, ‘*Random*’ and ‘*Prompt*’). On the Python command line, the `--ties` option can be specified multiple times (e.g. `--ties backwards --ties random`).
 
 ## Random seed (--random-seed)
 

html/index.html

@@ -184,6 +184,7 @@
 				Ties:
 				<select id="selTies">
 					<option value="backwards_random" selected>Backwards then random</option>
+					<option value="forwards_random">Forwards then random</option>
 					<option value="random">Random</option>
 					<option value="prompt">Prompt</option>
 				</select>

html/index.js

@@ -145,7 +145,7 @@ function changePreset() {
 		document.getElementById('selTransfers').value = 'eg';
 		document.getElementById('selPapers').value = 'transferable';
 		document.getElementById('selExclusion').value = 'by_value';
-		document.getElementById('selTies').value = 'backwards_random';
+		document.getElementById('selTies').value = 'forwards_random';
 	}
 }
 

html/worker.js

@@ -52,6 +52,8 @@ onmessage = function(evt) {
 		
 		if (evt.data.data.options['ties'] === 'backwards_random') {
 			counter.options['ties'] = [py.pyRCV2.ties.TiesBackwards(counter), py.pyRCV2.ties.TiesRandom(evt.data.data.seed)];
+		} else if (evt.data.data.options['ties'] === 'forwards_random') {
+			counter.options['ties'] = [py.pyRCV2.ties.TiesForwards(counter), py.pyRCV2.ties.TiesRandom(evt.data.data.seed)];
 		} else if (evt.data.data.options['ties'] === 'random') {
 			counter.options['ties'] = [py.pyRCV2.ties.TiesRandom(evt.data.data.seed)];
 		} else if (evt.data.data.options['ties'] === 'prompt') {

pyRCV2/cli/stv.py

@@ -19,7 +19,7 @@ import pyRCV2.model
 import pyRCV2.numbers
 
 from pyRCV2.method.base_stv import UIGSTVCounter, WIGSTVCounter, EGSTVCounter
-from pyRCV2.ties import TiesBackwards, TiesPrompt, TiesRandom
+from pyRCV2.ties import TiesBackwards, TiesForwards, TiesPrompt, TiesRandom
 
 import sys
 
@@ -44,7 +44,7 @@ def add_parser(subparsers):
 	parser.add_argument('--method', '-m', choices=['wig', 'uig', 'eg'], default='wig', help='method of transferring surpluses (default: wig - weighted inclusive Gregory)')
 	parser.add_argument('--transferable-only', action='store_true', help='examine only transferable papers during surplus distributions')
 	parser.add_argument('--exclusion', choices=['one_round', 'parcels_by_order', 'by_value', 'wright'], default='one_round', help='how to perform exclusions (default: one_round)')
-	parser.add_argument('--ties', '-t', action='append', choices=['backwards', 'prompt', 'random'], default=None, help='how to resolve ties (default: backwards then random)')
+	parser.add_argument('--ties', '-t', action='append', choices=['backwards', 'forwards', 'prompt', 'random'], default=None, help='how to resolve ties (default: backwards then random)')
 	parser.add_argument('--random-seed', default=None, help='arbitrary string used to seed the RNG for random tie breaking')
 	parser.add_argument('--hide-excluded', action='store_true', help='hide excluded candidates from results report')
 	parser.add_argument('--sort-votes', action='store_true', help='sort candidates by votes in results report')
@@ -117,6 +117,8 @@ def main(args):
 	for t in args.ties:
 		if t == 'backwards':
 			counter.options['ties'].append(TiesBackwards(counter))
+		elif t == 'forwards':
+			counter.options['ties'].append(TiesForwards(counter))
 		elif t == 'prompt':
 			counter.options['ties'].append(TiesPrompt())
 		elif t == 'random':

pyRCV2/ties.py

@@ -1,5 +1,5 @@
 #   pyRCV2: Preferential vote counting
-#   Copyright © 2020  Lee Yingtong Li (RunasSudo)
+#   Copyright © 2020–2021  Lee Yingtong Li (RunasSudo)
 #
 #   This program is free software: you can redistribute it and/or modify
 #   it under the terms of the GNU Affero General Public License as published by
@@ -106,6 +106,37 @@ class TiesBackwards:
 			__pragma__('noopov')
 		return None
 
+# FIXME: This is untested!
+class TiesForwards:
+	"""
+	Break ties based on the candidate who had the highest/lowest total at the end
+	of the earliest stage where one candidate had a higher/lower total than
+	all other tied candidates, if such a stage exists
+	"""
+	
+	def __init__(self, counter):
+		self.counter = counter
+	
+	def choose_lowest(self, l):
+		for result in self.counter.step_results:
+			__pragma__('opov')
+			l2 = [(x, result.candidates[x[0]].votes) for x in l]
+			l2.sort(key=lambda x: x[1])
+			if l2[0][1] < l2[1][1]: # Did one candidate have fewer votes than the others?
+				return l2[0][0]
+			__pragma__('noopov')
+		return None
+	
+	def choose_highest(self, l):
+		for result in self.counter.step_results:
+			__pragma__('opov')
+			l2 = [(x, result.candidates[x[0]].votes) for x in l]
+			l2.sort(key=lambda x: x[1], reverse=True)
+			if l2[0][1] > l2[1][1]: # Did one candidate have more votes than the others?
+				return l2[0][0]
+			__pragma__('noopov')
+		return None
+
 class TiesRandom:
 	"""Break ties randomly, using the SHARandom deterministic RNG"""