stv.php

stv.php

<?php
/* Find files */
$files = glob( $argv[1] );
sort( $files );
echo "Reading from: \n- ", implode( "\n- ", $files ), "\n\n";

/* Read Amount of Seats from Command Line */
array_shift( $argv );
array_shift( $argv );
$seats = (int) $argv[0];

/* Read Candidates from Command Line */
array_shift( $argv );
$candidates = $argv;
echo "Candidates (in order of ballot):\n", implode( '  —  ', $candidates ), "\n\n";

/* Read votes */
foreach ( $files as $pref => $file )
{
	$data = unserialize( file_get_contents( $file ) );

	foreach ( $data as $voter => $choices )
	{
		$votes[$voter][$pref] = $candidates[$choices['choices'][0]];
	}
}

/** Options **/
$rejectDuplicatePreferencedVotes = false; // if true, drop the whole vote, otherwise collapse
/*************/

/* Reindex choices in each vote to get rid of original indexes, in case
 * voters picked not all preferences in order */
foreach ( $votes as $voteIdx => $preferences )
{
	$votes[$voteIdx] = array_values( $preferences );

	if ( sizeof( array_count_values( $preferences ) ) != sizeof( $preferences ))
	{
		if ( $rejectDuplicatePreferencedVotes )
		{
			printf(
				"Voter '%s' has duplicates (%s), rejecting\n",
				$voteIdx,
				implode( '  —  ', $preferences )
			);
			unset( $votes[$voteIdx] );
		} else {
			printf(
				"Voter '%s' has duplicates (%s), de-duplicating\n",
				$voteIdx,
				implode( '  —  ', $preferences )
			);
			$deDuplicated = [];

			foreach( $preferences as $pref )
			{
				$deDuplicated[$pref] = 1;
			}

			$preferences = array_keys( $deDuplicated );
			printf(
				"%s %s\n\n",
				str_repeat( ' ', strlen( $voteIdx ) + 24 ),
				implode( '  —  ', $preferences )
			);
			$votes[$voteIdx] = $preferences;
		}
	}
}
echo "\n";

/* Anonymise votes */
$votes = array_values( $votes );

class Stv
{
	private array $elected = [];
	private int   $quorum;
	private int   $currentRound = 1;
	private array $tally;
	private array $firstPreferences;
	private array $eliminated = [];

	function __construct( private array $candidates, private int $seats, private array $votes )
	{
		$this->showVotes();
		$this->prepareTally();
	}

	public function elect() : array
	{
		$this->calculateQuorum();

		do {
			$this->doRound();
		} while ( count( $this->elected ) < $this->seats );

		return $this->elected;
	}

	private function calculateQuorum()
	{
		$cV = count( $this->votes );
		$cC = count( $this->candidates );
		$s  = $this->seats;
		$this->quorum = floor( $cV / ( $s + 1 ) ) + 1;

		echo "Votes:      {$cV}\n";
		echo "Candidates: {$cC}\n";
		echo "Seats:      {$s}\n";
		echo "Quorum:     {$this->quorum}\n";
		echo "\n";
	}

	private function prepareTally()
	{
		foreach ( $this->candidates as $candidate )
		{
			$this->tally[$candidate] = [];
		}

		/* For all votes still in play, calculate count per candidate */
		foreach ( $this->votes as $idx => $vote )
		{
			$this->tally[$vote[0]][] = $idx;
		}

		$this->firstPreferences = array_map( 'count', $this->tally );
	}

	private function rank()
	{
		uksort( $this->tally, function( $a, $b ) {
			$aC = count( $this->tally[$a] );
			$bC = count( $this->tally[$b] );

			if ( $aC !== $bC )
			{
				return -1 * ( count( $this->tally[$a] ) <=> count( $this->tally[$b] ) );
			}

			echo "Vote count for '$a' and '$b' is the same, so use first preference to disambiguate.\n\n";

			return -1 * ( $this->firstPreferences[$a] <=> $this->firstPreferences[$b] );
		} );
	}

	private function distributeWhenOverQuorum()
	{
		foreach ( $this->tally as $candidate => $votes )
		{
			$nextPref = [];
			$countNextPref = 0;

			$voteCount = count( $votes );
			if ( $voteCount <= $this->quorum )
			{
				continue;
			}

			echo "Candidate '{$candidate}' is over quorum ({$this->quorum}) with {$voteCount} votes, redistributing.\n";
			$overQuorum = $voteCount - $this->quorum;

			$this->showVotes();

			/* For the votes in the tally for $candidate, count the next pref,
			 * if it exists */
			foreach ( $this->votes as $voteIdx => $ranking )
			{
				if ( count( $ranking ) < 1 )
				{
					echo "- Vote {$voteIdx} is exhausted.\n";
					continue;
				}

				if ( $ranking[0] == $candidate )
				{
					echo "- Vote {$voteIdx} has $candidate as first preference, ";
			//		array_shift( $this->votes[$voteIdx] );

					if ( count( $this->votes[$voteIdx] ) < 2 )
					{
						echo "but no more preferences left.\n";
						continue;
					}
					echo "and as next preference {$this->votes[$voteIdx][1]}.\n";
					$countNextPref++;
					@$nextPref[ $this->votes[$voteIdx][1] ][] = $voteIdx;
				}
			}

			/* Sort from most to lowest */
			$nextPrefOptions = $nextPref;

			uasort(
				$nextPrefOptions,
				function($a, $b) {
					return -1 * ( count( $a ) <=> count( $b ) );
				}
			);

			/* Create iterators */
			$allI = new MultipleIterator( MultipleIterator::MIT_NEED_ANY );
			foreach ( $nextPrefOptions as $option )
			{
				$allI->attachIterator( new ArrayIterator( $option ) );
			}
			$distributeBallots = [];
			foreach ( $allI as $ballotNrs )
			{
				foreach ( $ballotNrs as $ballotNr )
				{
					if ( $ballotNr === NULL )
					{
						continue;
					}
					$distributeBallots[] = $ballotNr;
				}
			}

			/* Pick as many "over quorom" as needed at strip out first pref */
			for ( $i = 0; $i < $overQuorum; $i++ )
			{
				array_shift( $this->votes[$distributeBallots[0]] );
				array_shift( $this->tally[$candidate] );
				printf(
					"\nDistributing ballot #%s from %s to %s\n\n\n",
					$distributeBallots[0], $candidate, $this->votes[$distributeBallots[0]][0],
				);
			}

			$this->tally[$this->votes[$distributeBallots[0]][0]][] = $distributeBallots[0];

			$this->showTally();
		}
	}

	private function electIfMatchQuorum() : bool
	{
		$anyElected = 0;

		foreach ( $this->tally as $candidate => $votes )
		{
			if ( count( $votes ) >= $this->quorum )
			{
				$this->electCandidate( $candidate );
				unset( $this->tally[$candidate] );
				$anyElected++;
			}
		}

		return !!$anyElected;
	}

	private function electCandidate( string $candidate )
	{
		echo "Candidate '{$candidate}' has reached quorum, and is therefore elected\n\n";

		$this->elected[] = $candidate;
	}

	private function eliminateLowest()
	{
		end( $this->tally );
		$toEliminate = key( $this->tally );
		$votes       = count( $this->tally[$toEliminate] );

		echo "Eliminating '{$toEliminate}' with {$votes} votes\n\n";
		$this->eliminated[] = $toEliminate;

		echo "Distributing votes to next preference:\n";
		$distribution = [];

		foreach ( $this->tally[$toEliminate] as $voteIdx )
		{
skipEliminatedCandidate:
			array_shift( $this->votes[$voteIdx] );

			if ( count( $this->votes[$voteIdx] ) < 1 )
			{
				echo "- Votes for {$voteIdx} exhausted\n";
				continue;
			}

			if ( in_array( $this->votes[$voteIdx][0], $this->eliminated ) )
			{
				echo "- Not distributing {$voteIdx} to {$this->votes[$voteIdx][0]} as candidate has been eliminated.\n";
				goto skipEliminatedCandidate;
			}
			if ( in_array( $this->votes[$voteIdx][0], $this->elected ) )
			{
				echo "- Not distributing {$voteIdx} to {$this->votes[$voteIdx][0]} as candidate has been elected.\n";
				goto skipEliminatedCandidate;
			}

			echo "- Distributing {$voteIdx} to {$this->votes[$voteIdx][0]}.\n";
			@$distribution[ $this->votes[$voteIdx][0] ]++;
			$this->tally[ $this->votes[$voteIdx][0] ][] = $voteIdx;
		}

		if ( count( $distribution ) )
		{
			foreach( $distribution as $candidate => $voteCount )
			{
				echo "- Candidate '{$candidate}': {$voteCount}\n";
			}
		} else {
			echo "- Nothing to distribute\n";
		}

		echo "\nElected candidates:    ", join( ', ', $this->elected ), "\n";
		echo "Eliminated candidates: ", join( ', ', $this->eliminated ), "\n";

		unset( $this->tally[$toEliminate] );
		echo "\n";
	}

	private function doRound()
	{
		echo "Round #{$this->currentRound}\n--------\n\n";

		$this->rank();

		$this->showTally();

		if ( count( $this->tally ) > 1 )
		{
			$this->distributeWhenOverQuorum();
		}
		if ( ! $this->electIfMatchQuorum() )
		{
			$this->eliminateLowest();
		}

		$this->showTally();

		$this->currentRound++;
	}

	private function showVotes()
	{
		echo "Votes:\n";
		foreach ( $this->votes as $voteIdx => $ranking )
		{
			printf( "Vote #%2d: %s\n",
				$voteIdx, implode( '  —  ', $ranking )
			);
		}
		echo "\n";
	}

	private function showTally()
	{
		echo "Tally:\n";
		foreach( $this->tally as $candidate => $items )
		{
			echo "Candidate '{$candidate}': ", count( $items ), ' → ',
				implode( ' ', $items ), "\n";
		}
		echo "\n";
	}
}

$stv = new Stv( $candidates, $seats, $votes );
$elected = $stv->elect();

echo "\n=================================\n\nELECTED:\n\t", implode( "\n\t", $elected ), "\n";