Implement --exclusion by_source

docs/options.md

@@ -81,9 +81,10 @@ Other surplus transfer methods, such as non-fractional transfers (e.g. random sa
 
 ### Exclusion method (--exclusion)
 
-* *Exclude in one round* (default): When excluding candidate(s), transfer all their ballot papers in one stage.
-* *Exclude by parcel (by order)*: When excluding a candidate, transfer their ballot papers one parcel at a time, in the order each was received. Each parcel forms a separate stage, i.e. if a transfer allows another candidate to meet the quota criterion, no further papers are transferred to that candidate. This option cannot be combined with bulk exclusion.
-* *Exclude by value*: When excluding candidate(s), transfer their ballot papers in descending order of accumulated transfer value. Each transfer of all ballots of a certain transfer value forms a separate stage.
+* *Single stage* (default): When excluding candidate(s), transfer all their ballot papers in one stage.
+* *By value*: When excluding candidate(s), transfer their ballot papers in descending order of accumulated transfer value. Each transfer of all ballots of a certain transfer value forms a separate stage, i.e. if a transfer allows another candidate to meet the quota criterion, no further papers are transferred to that candidate.
+* *By source*: When excluding candidate(s), transfer their ballot papers according to the candidate from which those papers were received, in the order received, i.e. in the order the transferring candidates were elected or excluded. Each transfer of all ballots received from a certain candidate forms a separate stage.
+* *By parcel (by order)*: When excluding a candidate, transfer their ballot papers one parcel at a time, in the order each was received. Each parcel forms a separate stage. This option cannot be combined with bulk exclusion.
 * *Wright method (re-iterate)*: When excluding candidate(s), reset the count from the distribution of first preferences, disregarding the excluded candidates.
 
 When *Surplus method* is set to *Meek method*, this setting is ignored, and the Meek method is instead applied.

html/index.html

@@ -114,6 +114,7 @@
 							<select id="selExclusion">
 								<option value="single_stage" selected>Single stage</option>
 								<option value="by_value">By value</option>
+								<option value="by_source">By source</option>
 								<option value="parcels_by_order">By parcel (by order)</option>
 								<option value="wright">Wright method (re-iterate)</option>
 							</select>

src/election.rs

@@ -305,10 +305,25 @@ impl<'a, N: Number> CountCard<'a, N> {
 		//self.orig_votes = self.votes.clone();
 		self.transfers = N::new();
 	}
+	
+	/// Concatenate all parcels into a single parcel, leaving [parcels](CountCard::parcels) empty
+	pub fn concat_parcels(&mut self) -> Vec<Vote<'a, N>> {
+		let mut result = Vec::new();
+		for parcel in self.parcels.iter_mut() {
+			result.append(&mut parcel.votes);
+		}
+		return result;
+	}
 }
 
 /// Parcel of [Vote]s during a count
-pub type Parcel<'a, N> = Vec<Vote<'a, N>>;
+#[derive(Clone)]
+pub struct Parcel<'a, N> {
+	/// [Vote]s in this parcel
+	pub votes: Vec<Vote<'a, N>>,
+	/// Order for sorting with [opentally::stv::ExclusionMethod::BySource]
+	pub source_order: usize,
+}
 
 /// Represents a [Ballot] with an associated value
 #[derive(Clone)]

src/main.rs

@@ -131,7 +131,7 @@ struct STV {
 	transferable_only: bool,
 	
 	/// Method of exclusions
-	#[clap(help_heading=Some("STV VARIANTS"), long, possible_values=&["single_stage", "by_value", "parcels_by_order", "wright"], default_value="single_stage", value_name="method")]
+	#[clap(help_heading=Some("STV VARIANTS"), long, possible_values=&["single_stage", "by_value", "by_source", "parcels_by_order", "wright"], default_value="single_stage", value_name="method")]
 	exclusion: String,
 	
 	/// (Meek STV) NZ Meek STV behaviour: Iterate keep values one round before candidate exclusion

src/stv/gregory.rs

@@ -39,14 +39,20 @@ pub fn distribute_first_preferences<N: Number>(state: &mut CountState<N>) {
 	
 	// Transfer candidate votes
 	for (candidate, entry) in result.candidates.into_iter() {
-		let parcel = entry.votes as Parcel<N>;
+		let parcel = Parcel {
+			votes: entry.votes,
+			source_order: 0,
+		};
 		let count_card = state.candidates.get_mut(candidate).unwrap();
 		count_card.parcels.push(parcel);
 		count_card.transfer(&entry.num_votes);
 	}
 	
 	// Transfer exhausted votes
-	let parcel = result.exhausted.votes as Parcel<N>;
+	let parcel = Parcel {
+		votes: result.exhausted.votes,
+		source_order: 0,
+	};
 	state.exhausted.parcels.push(parcel);
 	state.exhausted.transfer(&result.exhausted.num_votes);
 	
@@ -66,7 +72,7 @@ where
 	let has_surplus: Vec<&Candidate> = state.election.candidates.iter() // Present in order in case of tie
 		.filter(|c| {
 			let cc = &state.candidates[c];
-			&cc.votes > quota && cc.parcels.iter().any(|p| !p.is_empty())
+			&cc.votes > quota && cc.parcels.iter().any(|p| !p.votes.is_empty())
 		})
 		.collect();
 	
@@ -232,12 +238,12 @@ where
 	match opts.surplus {
 		SurplusMethod::WIG | SurplusMethod::UIG => {
 			// Inclusive Gregory
-			votes = count_card.parcels.concat();
+			votes = state.candidates.get_mut(elected_candidate).unwrap().concat_parcels();
 		}
 		SurplusMethod::EG => {
 			// Exclusive Gregory
 			// Should be safe to unwrap() - or else how did we get a quota!
-			votes = state.candidates.get_mut(elected_candidate).unwrap().parcels.pop().unwrap();
+			votes = state.candidates.get_mut(elected_candidate).unwrap().parcels.pop().unwrap().votes;
 		}
 		_ => { panic!("Invalid --surplus for Gregory method"); }
 	}
@@ -302,10 +308,13 @@ where
 		count_card.transfer(&candidate_transfers);
 		checksum += candidate_transfers;
 		
-		let mut parcel = entry.votes as Parcel<N>;
+		let mut parcel = Parcel {
+			votes: entry.votes,
+			source_order: state.num_elected + state.num_excluded,
+		};
 		
 		// Reweight votes
-		for vote in parcel.iter_mut() {
+		for vote in parcel.votes.iter_mut() {
 			vote.value = reweight_vote(&vote.value, &vote.ballot.orig_value, &surplus, is_weighted, &surplus_fraction, &surplus_denom, opts.round_tvs, opts.round_weights);
 		}
 		
@@ -333,7 +342,10 @@ where
 	checksum += exhausted_transfers;
 	
 	// Transfer exhausted votes
-	let parcel = result.exhausted.votes as Parcel<N>;
+	let parcel = Parcel {
+		votes: result.exhausted.votes,
+		source_order: state.num_elected + state.num_excluded,
+	};
 	state.exhausted.parcels.push(parcel);
 	
 	// Finalise candidate votes
@@ -379,7 +391,7 @@ where
 			// Exclude in one round
 			for excluded_candidate in excluded_candidates.iter() {
 				let count_card = state.candidates.get_mut(excluded_candidate).unwrap();
-				votes.append(&mut count_card.parcels.concat());
+				votes.append(&mut count_card.concat_parcels());
 				count_card.parcels.clear();
 				
 				// Update votes
@@ -399,7 +411,7 @@ where
 				// If candidates to exclude still having votes, select only those with the greatest value
 				let max_value = excluded_with_votes.iter()
 					.map(|c| state.candidates[*c].parcels.iter()
-						.map(|p| p.iter().map(|v| &v.value / &v.ballot.orig_value).max().unwrap())
+						.map(|p| p.votes.iter().map(|v| &v.value / &v.ballot.orig_value).max().unwrap())
 						.max().unwrap())
 					.max().unwrap();
 				
@@ -411,7 +423,7 @@ where
 					// Filter out just those votes with max_value
 					let mut remaining_votes = Vec::new();
 					
-					let cand_votes = count_card.parcels.concat();
+					let cand_votes = count_card.concat_parcels();
 					
 					let mut votes_transferred = N::new();
 					for vote in cand_votes.into_iter() {
@@ -428,7 +440,58 @@ where
 					}
 					
 					// Leave remaining votes with candidate (as one parcel)
-					count_card.parcels = vec![remaining_votes];
+					count_card.parcels = vec![Parcel {
+						votes: remaining_votes,
+						source_order: 0, // Unused in this mode
+					}];
+					
+					// Update votes
+					checksum -= &votes_transferred;
+					count_card.transfer(&-votes_transferred);
+				}
+			}
+		}
+		ExclusionMethod::BySource => {
+			// Exclude by source candidate
+			let excluded_with_votes: Vec<&&Candidate> = excluded_candidates.iter().filter(|c| !state.candidates[*c].parcels.is_empty()).collect();
+			
+			if excluded_with_votes.is_empty() {
+				votes_remain = false;
+			} else {
+				// If candidates to exclude still having votes, select only those from the earliest elected/excluded source candidate
+				let min_order = excluded_with_votes.iter()
+					.map(|c| state.candidates[*c].parcels.iter()
+						.map(|p| p.source_order)
+						.min().unwrap())
+					.min().unwrap();
+				
+				votes_remain = false;
+				
+				for excluded_candidate in excluded_with_votes.iter() {
+					let count_card = state.candidates.get_mut(*excluded_candidate).unwrap();
+					
+					// Filter out just those votes with min_order
+					let mut remaining_parcels = Vec::new();
+					
+					let mut votes_transferred = N::new();
+					while !count_card.parcels.is_empty() {
+						let parcel = count_card.parcels.pop().unwrap();
+						if parcel.source_order == min_order {
+							for vote in parcel.votes {
+								votes_transferred += &vote.value;
+								votes.push(vote);
+							}
+						} else {
+							remaining_parcels.push(parcel);
+						}
+					}
+					
+					if !remaining_parcels.is_empty() {
+						votes_remain = true;
+					}
+					
+					// Leave remaining parcels with candidate
+					count_card.parcels = remaining_parcels;
 					
 					// Update votes
 					checksum -= &votes_transferred;
@@ -439,6 +502,7 @@ where
 		ExclusionMethod::ParcelsByOrder => {
 			// Exclude by parcel by order
 			if excluded_candidates.len() > 1 {
+				// TODO: We can probably support this actually
 				panic!("--exclusion parcels_by_order is incompatible with --bulk-exclude");
 			}
 			
@@ -447,7 +511,7 @@ where
 			if count_card.parcels.is_empty() {
 				votes_remain = false;
 			} else {
-				votes = count_card.parcels.remove(0);
+				votes = count_card.parcels.remove(0).votes;
 				votes_remain = !count_card.parcels.is_empty();
 				
 				// Update votes
@@ -481,7 +545,10 @@ where
 		
 		// Transfer candidate votes
 		for (candidate, entry) in result.candidates.into_iter() {
-			let parcel = entry.votes as Parcel<N>;
+			let parcel = Parcel {
+				votes: entry.votes,
+				source_order: state.num_elected + state.num_excluded,
+			};
 			let count_card = state.candidates.get_mut(candidate).unwrap();
 			count_card.parcels.push(parcel);
 			
@@ -495,7 +562,10 @@ where
 		}
 		
 		// Transfer exhausted votes
-		let parcel = result.exhausted.votes as Parcel<N>;
+		let parcel = Parcel {
+			votes: result.exhausted.votes,
+			source_order: state.num_elected + state.num_excluded,
+		};
 		state.exhausted.parcels.push(parcel);
 		
 		let mut exhausted_transfers = result.exhausted.num_votes;

src/stv/mod.rs

@@ -170,6 +170,7 @@ impl STVOptions {
 			exclusion: match exclusion {
 				"single_stage" => ExclusionMethod::SingleStage,
 				"by_value" => ExclusionMethod::ByValue,
+				"by_source" => ExclusionMethod::BySource,
 				"parcels_by_order" => ExclusionMethod::ParcelsByOrder,
 				"wright" => ExclusionMethod::Wright,
 				_ => panic!("Invalid --exclusion"),
@@ -388,6 +389,8 @@ pub enum ExclusionMethod {
 	SingleStage,
 	/// Transfer the ballot papers of an excluded candidate in descending order of accumulated transfer value
 	ByValue,
+	/// Transfer the ballot papers of an excluded candidate according to the candidate who transferred the papers to the excluded candidate, in the order the transferring candidates were elected or excluded
+	BySource,
 	/// Transfer the ballot papers of an excluded candidate parcel by parcel in the order received
 	ParcelsByOrder,
 	/// Wright method (re-iterate)
@@ -400,6 +403,7 @@ impl ExclusionMethod {
 		match self {
 			ExclusionMethod::SingleStage => "--exclusion single_stage",
 			ExclusionMethod::ByValue => "--exclusion by_value",
+			ExclusionMethod::BySource => "--exclusion by_source",
 			ExclusionMethod::ParcelsByOrder => "--exclusion parcels_by_order",
 			ExclusionMethod::Wright => "--exclusion wright",
 		}.to_string()
@@ -1040,7 +1044,7 @@ where
 {
 	// Cannot filter by raw vote count, as candidates may have 0.00 votes but still have recorded ballot papers
 	let mut excluded_with_votes: Vec<(&&Candidate, &CountCard<N>)> = state.candidates.iter()
-		.filter(|(_, cc)| cc.state == CandidateState::Excluded && cc.parcels.iter().any(|p| !p.is_empty()))
+		.filter(|(_, cc)| cc.state == CandidateState::Excluded && cc.parcels.iter().any(|p| !p.votes.is_empty()))
 		.collect();
 	
 	if !excluded_with_votes.is_empty() {
@@ -1086,7 +1090,7 @@ where
 				}
 			}
 		}
-		ExclusionMethod::ByValue | ExclusionMethod::ParcelsByOrder => {
+		ExclusionMethod::ByValue | ExclusionMethod::BySource | ExclusionMethod::ParcelsByOrder => {
 			// Exclusion in parts compatible only with Gregory method
 			gregory::exclude_candidates(state, opts, excluded_candidates);
 		}