ElectionRunner::allocateVotes() - Code Metrics - michaelcullum/voting-lib - Measure and Improve Code Quality continuously with Scrutinizer

ElectionRunner::allocateVotes() B
last analyzed 2016-08-20 15:40 UTC

↳ Parent: ElectionRunner

Complexity

Conditions	3
Paths	3

Size

Total Lines	35
Code Lines	13

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	13
CRAP Score	3

Importance

Changes

Metric	Value
dl	0
loc	35
ccs	13
cts	13
cp	1
rs	8.8571
c	0
b	0
f	0
cc	3
eloc	13
nc	3
nop	3
crap	3

<?php

namespace Michaelc\Voting\STV;

use Psr\Log\LoggerInterface as Logger;
use Michaelc\Voting\Exception\VotingLogicException as LogicException;
use Michaelc\Voting\Exception\VotingRuntimeException as RuntimeException;

/**
 * This class will calculate the outcome of an election.
 *
 * References throughout are provided as to what is going on.
 * It follows a system similar to Scottish STV and all paragraph
 * references are for: http://www.legislation.gov.uk/sdsi/2011/9780111014639/pdfs/sdsi_9780111014639_en.pdf
 */
class ElectionRunner
{
    /**
     * Logger.
     *
     * @var \Psr\Log\LoggerInterface
     */
    protected $logger;

    /**
     * Election object.
     *
     * @var \Michaelc\Voting\STV\Election;
     */
    protected $election;

    /**
     * Array of all ballots in election.
     *
     * @var \MichaelC\Voting\STV\Ballot[]
     */
    protected $ballots;

    /**
     * Quota of votes needed for a candidate to be elected.
     *
     * @var int
     */
    protected $quota;

    /**
     * Number of candidates elected so far.
     *
     * @var int
     */
    public $electedCandidates;

    /**
     * Invalid ballots.
     *
     * @var \MichaelC\Voting\STV\Ballot[]
     */
    public $rejectedBallots;

    /**
     * Number of valid ballots.
     *
     * @var int
     */
    public $validBallots;

    /**
     * Number of winners to still be elected (at current stage).
     *
     * @var int
     */
    public $candidatesToElect;

    /**
     * Array of each stage of the election and the vote totals of each candidate
     *
     * @var array
     */
    protected $steps;

    /**
     * Constructor.
     *
     * @param Election $election
     */
    public function __construct(Election $election, Logger $logger)
    {
        $this->logger = $logger;
        $this->election = $election;

        $this->ballots = $this->election->getBallots();
        $this->rejectedBallots = [];
        $this->candidatesToElect = $this->election->getWinnersCount();
        $this->validBallots = $this->election->getNumBallots();
        $this->steps = [];
    }

    /**
     * Run the election.
     *
     * @return Candidate[] Winning candidates
     */
    public function run()
    {
        $this->logger->notice('Starting to run an election');
        $this->logger->notice(sprintf('There are %d candidates, %d ballots and to be %d winners', $this->election->getCandidateCount(), $this->validBallots, $this->election->getWinnersCount()));

        // Reject invalid ballots, then calculate the quota based on remaining valid ballots
        // p. 46(3) and p 47
        $this->rejectInvalidBallots();
        $this->setQuota();

        // First step of standard allocation of ballots
        // p. 46(1) and 46(2)
        $this->firstStep();

        $candidates = $this->election->getActiveCandidates();

        // All the re-allocation rounds until we have filled all seats or
        // have the same number of seats left to fill and candidates remaining
        // (then elect them).
        $this->processReallocationRounds($candidates);
        // p. 53
        $this->reallocateRemainingVotes($candidates);

        $this->logger->notice('Election complete');

        return $this->election->getElectedCandidates();
    }

    /**
     * Perform the initial vote allocation.
     * p. 46.
     *
     * @return
     */
    protected function firstStep()
    {
        $this->logger->info('Beginning the first step');

        // Allocate all the ballots
        foreach ($this->ballots as $i => $ballot) {
            $this->allocateVotes($ballot);
        }

        $this->logger->notice('Step 1 complete',
            ['candidatesStatus' => $this->election->getCandidatesStatus()]
        );

        $this->steps[1] = $this->election->getCandidatesStatus();

        return;
    }

    /**
     * Process re-allocation rounds (elimination re-allocations and surplus re-allocations).
     *
     * @param Candidate[] $candidates All active candidates to elect
     *
     * @return Candidate[]
     */
    protected function processReallocationRounds(array &$candidates): array
    {
        $counter = 1;
        while (($this->candidatesToElect > 0) && ($this->election->getActiveCandidateCount() > $this->candidatesToElect)) {
            if (!$this->checkCandidates($candidates)) {
                // p. 51(1)
                $this->eliminateCandidates($candidates);
            }

            $candidates = $this->election->getActiveCandidates();

            ++$counter;

            $this->logger->notice("Step $counter complete",
                ['candidatesStatus' => $this->election->getCandidatesStatus()]
            );

            $this->steps[$counter] = $this->election->getCandidatesStatus();
        }

        return $candidates;
    }

    /**
     * Check if any candidates have reached the quota and can be elected.
     *
     * @param Candidate[] $candidates Array of active candidates to check
     *
     * @return bool Whether any candidates were changed to elected
     */
    protected function checkCandidates(array $candidates): bool
    {
        $elected = false;
        $candidatesToElect = [];

        $this->logger->info('Checking if candidates have passed quota');

        if (empty($candidates)) {
            throw new LogicException('There are no more candidates left');
        }

        foreach ($candidates as $i => $candidate) {
            if ($candidate->getState() !== Candidate::RUNNING) {
                throw new LogicException('Candidate is not marked as not running but has not been excluded');
            }

            $votes = $candidate->getVotes();

            $this->logger->debug("Checking candidate ($candidate) with $votes", ['candidate' => $candidate]);

            // p. 48(1)
            // Immediately elect a candidate if they hit the quota
            // We check all the candidates, see who has hit the quota,
            // add them to a queue, then elect those who have hit the quota to prevent
            // surplus allocations pushing a candidate over the quota early.
            if ($votes >= $this->quota) {
                $candidatesToElect[] = $candidate;
                $elected = true;
            }
        }

        // TODO: Put this in a try, and catch the RuntimeError.
        // Then sort by the surplus, and fill available seats.
        // If have same surplus then select randomly (Contary to Scottish STV)
        // p. 50
        $this->electCandidates($candidatesToElect);

        $this->logger->info(('Candidate checking complete. Elected: '.count($candidatesToElect)));

        return $elected;
    }

    /**
     * Elect an array of candidates.
     *
     * @param Candidate[] $candidates Array of candidates to elect
     *
     * @return
     */
    protected function electCandidates(array $candidates)
    {
        if ($this->candidatesToElect < count($candidates)) {
            throw new RuntimeException('Cannot elect candidate as not enough seats to fill');
        }

        foreach ($candidates as $i => $candidate) {
            $this->electCandidate($candidate);
        }

        return;
    }

    /**
     * Allocate the next votes from a Ballot.
     * p. 49.
     *
     * @param Ballot $ballot     The ballot to allocate the votes from
     * @param float  $multiplier Number to multiply the weight by (surplus)
     * @param float  $divisor    The divisor of the weight (Total number of
     *                           candidate votes)
     *
     * @return Ballot The same ballot passed in modified
     */
    protected function allocateVotes(Ballot $ballot, float $multiplier = 1.0, float $divisor = 1.0): Ballot
    {
        $currentWeight = $ballot->getWeight();
        // p. 49(3)
        // "A divided by B" Where A = the value which is calculated
        // by multiplying the surplus of the transferring candidate
        // by the value of the ballot paper when received by that candidate; and
        // B = the total number of votes credited to that candidate
        $weight = $ballot->setWeight(($currentWeight * $multiplier) / $divisor);

        // Get the next candidate on their ballot paper which has not been assigned
        // a vote this could be the first candidate in round 1
        $candidate = $ballot->getNextChoice();

        $this->logger->debug("Allocating vote of weight $weight to $candidate. Previous weight: $currentWeight", array(
            'ballot' => $ballot,
        ));

        // Check there was a next candidate, if only x candidates where listed where
        // x < the number of candidates standing this will occur.
        if ($candidate !== null) {
            // Allocate those surplus votes. p. 49(1) and p. 49(2)
            $this->election->getCandidate($candidate)->addVotes($weight);
            $ballot->incrementLevelUsed();
            $this->logger->debug('Vote added to candidate');

            // If the candidate is no longer running due to being defeated or
            // elected then we re-allocate their vote again.
            if (!in_array($candidate, $this->election->getActiveCandidateIds())) {
                $this->allocateVotes($ballot);
            }
        }

        return $ballot;
    }

    /**
     * Transfer the votes from one candidate to other candidates.
     *
     * @param float     $surplus   The number of surplus votes to transfer
     * @param Candidate $candidate The candidate being elected to transfer
     *                             the votes from
     *
     * @return
     */
    protected function transferSurplusVotes(float $surplus, Candidate $candidate)
    {
        $totalVotes = $candidate->getVotes();
        $candidateId = $candidate->getId();

        $this->logger->info('Transfering surplus votes');

        foreach ($this->ballots as $i => $ballot) {
            if ($ballot->getLastChoice() == $candidateId) {
                $this->allocateVotes($ballot, $surplus, $totalVotes);
            }
        }

        return;
    }

    /**
     * Transfer the votes from one eliminated candidate to other candidates.
     * p. 51(2).
     *
     * @param Candidate $candidate Candidate being eliminated to transfer
     *                             the votes from
     *
     * @return
     */
    protected function transferEliminatedVotes(Candidate $candidate)
    {
        $candidateId = $candidate->getId();

        $votes = $candidate->getVotes();

        $this->logger->info("Transfering votes from eliminated candidate ($candidate) with $votes votes");

        // p. 51(2)(a) - Sort into next preference candidates
        // p. 51(3) - Add votes to candidates
        // p. 51(4) - Use previous weighting
        foreach ($this->ballots as $i => $ballot) {
            if ($ballot->getLastChoice() == $candidateId) {
                $this->allocateVotes($ballot);
            }
        }

        return;
    }

    /**
     * Elect a candidate after they've passed the threshold.
     *
     * @param Candidate $candidate
     */
    protected function electCandidate(Candidate $candidate)
    {
        $this->logger->notice("Electing a candidate: $candidate");

        $candidate->setState(Candidate::ELECTED);
        ++$this->electedCandidates;
        --$this->candidatesToElect;

        if ($this->electedCandidates < $this->election->getWinnersCount()) {
            $surplus = $candidate->getVotes() - $this->quota;
            if ($surplus > 0) {
                $this->transferSurplusVotes($surplus, $candidate);
            } else {
                $this->logger->notice("No surplus votes from $candidate to reallocate");
            }
        }

        return;
    }

    /**
     * Eliminate the candidate with the lowest number of votes
     * and reallocated their votes.
     * p. 51.
     *
     * @param Candidate[] $candidates Array of active candidates
     *
     * @return int Number of candidates eliminated
     */
    protected function eliminateCandidates(array $candidates): int
    {
        $minimumCandidates = $this->getLowestCandidates($candidates);
        $count = count($minimumCandidates);

        // p. 52(2)(b) - the returning officer shall decide, by lot, which of those
        // candidates is to be excluded.
        // We do not look back on previous rounds at all as per p. 52(2)(a)
        $minimumCandidate = $minimumCandidates[(array_rand($minimumCandidates))];

        $this->logger->notice(sprintf('There were %d joint lowest candidates,
            %d was randomly selected to be eliminated', $count, $minimumCandidate->getId()));

        $this->transferEliminatedVotes($minimumCandidate);
        $minimumCandidate->setState(Candidate::DEFEATED);

        return count($minimumCandidates);
    }

    /**
     * Get candidates with the lowest number of votes
     * p. 51 and p. 52(1).
     *
     * @param Candidate[] $candidates
     *                                Array of active candidates
     *
     * @return Candidate[]
     *                     Candidates with lowest score
     */
    public function getLowestCandidates(array $candidates): array
    {
        $minimum = count($this->election->getBallots());
        $minimumCandidates = [];

        foreach ($candidates as $i => $candidate) {
            if ($candidate->getVotes() < $minimum) {
                $minimum = $candidate->getVotes();
                unset($minimumCandidates);
                $minimumCandidates[] = $candidate;
            } elseif ($candidate->getVotes() == $minimum) {
                $minimumCandidates[] = $candidate;
                $this->logger->info("Calculated as a lowest candidate: $candidate");
            }
        }

        return $minimumCandidates;
    }

    /**
     * Reject any invalid ballots.
     * p. 46(3).
     *
     * @return int Number of rejected ballots
     */
    protected function rejectInvalidBallots(): int
    {
        foreach ($this->ballots as $i => $ballot) {
            if (!$this->checkBallotValidity($ballot)) {
                $this->rejectedBallots[] = clone $ballot;
                unset($this->ballots[$i]);
            }
        }

        $count = count($this->rejectedBallots);

        $this->logger->notice("Found $count rejected ballots");

        $this->validBallots = $this->validBallots - $count;

        return $count;
    }

    /**
     * Check if ballot is valid.
     *
     * @param Ballot $ballot Ballot to test
     *
     * @return bool True if valid, false if invalid
     */
    public function checkBallotValidity(Ballot $ballot): bool
    {
        $ranking = $ballot->getRanking();

        if (!$this->checkCandidateCountValidity($ranking) || !$this->checkBallotVoteDuplicationValidity($ranking) || !$this->checkAllBallotCandidatesValid($ranking))
        {
            return false;
        }

        $this->logger->debug('Ballot is valid');

        return true;
    }

    /**
     * Reallocate any remaining votes
     * p. 53.
     *
     * @param Candidate[] $candidates All remaining candidates to elect
     *
     * @return
     */
    protected function reallocateRemainingVotes(array &$candidates)
    {
        if (!empty($candidates)) {
            $this->logger->info('All votes re-allocated. Electing all remaining candidates');

            if ($this->candidatesToElect < count($candidates)) {
                throw new LogicException('Cannot elect candidate as no more seats to fill');
            }

            $this->electCandidates($candidates);
        }

        return;
    }

    /**
     * Get the quota to win.
     * p. 47.
     *
     * TODO: Move this out of this method and use params/args
     *
     * @return int
     */
    public function setQuota(): int
    {
        $this->quota = (int) floor(
            ($this->validBallots /
                ($this->election->getWinnersCount() + 1)
            ) // p. 47 (1)
            + 1); // p. 47 (2)

        $this->logger->info(sprintf('Quota set at %d based on %d winners and %d valid ballots', $this->quota, $this->election->getWinnersCount(), $this->validBallots));

        return $this->quota;
    }

    /**
     * Return the quota for the election
     *
     * @return int
     */
    public function getQuota(): int
    {
        return $this->quota;
    }

    /**
     * Gets an array of the state of all candidates at the end of each
     * phase/step
     *
     * @return array
     */
    public function getSteps(): array
    {
        return $this->steps;
    }

    /**
     * Check that a ballot's ranking doesn't have more elements than
     * we have candidates
     *
     * @param  array  $ranking Ballot ranking
     *
     * @return bool   False if invalid, True if valid
     */
    protected function checkCandidateCountValidity(array $ranking): bool
    {
        if (count($ranking) > $this->election->getCandidateCount()) {
            $this->logger->debug('Invalid ballot - number of candidates');

            return false;
        }

        return true;
    }

    /**
     * Check that a ballot doesn't duplicate votes for any candidates (where
     * a candidate is listed twice in one ranking)
     *
     * @param  array  $ranking Ballot ranking
     *
     * @return bool   False if invalid, True if valid
     */
    protected function checkBallotVoteDuplicationValidity(array $ranking): bool
    {
        if (count($ranking) !== count(array_unique($ranking))) {
            return false;
        }

        return true;
    }

    /**
     * Check that a ballot only contains candidate id numbers that are integers
     * and correspond to valid candidates.
     *
     * @param  array  $ranking Ballot ranking
     *
     * @return bool   False if invalid, True if valid
     */
    protected function checkAllBallotCandidatesValid(array $ranking): bool
    {
        $candidateIds = $this->election->getCandidateIds();

        foreach ($ranking as $candidate) {
            if (!in_array($candidate, $candidateIds)) {
                $this->logger->debug('Invalid ballot - invalid candidate');

                return false;
            }
        }

        return true;
    }
}


1		<?php
2
3		namespace Michaelc\Voting\STV;
4
5		use Psr\Log\LoggerInterface as Logger;
6		use Michaelc\Voting\Exception\VotingLogicException as LogicException;
7		use Michaelc\Voting\Exception\VotingRuntimeException as RuntimeException;
8
9		/**
10		* This class will calculate the outcome of an election.
11		*
12		* References throughout are provided as to what is going on.
13		* It follows a system similar to Scottish STV and all paragraph
14		* references are for: http://www.legislation.gov.uk/sdsi/2011/9780111014639/pdfs/sdsi_9780111014639_en.pdf
15		*/
16		class ElectionRunner
17		{
18		/**
19		* Logger.
20		*
21		* @var \Psr\Log\LoggerInterface
22		*/
23		protected $logger;
24
25		/**
26		* Election object.
27		*
28		* @var \Michaelc\Voting\STV\Election;
29		*/
30		protected $election;
31
32		/**
33		* Array of all ballots in election.
34		*
35		* @var \MichaelC\Voting\STV\Ballot[]
36		*/
37		protected $ballots;
38
39		/**
40		* Quota of votes needed for a candidate to be elected.
41		*
42		* @var int
43		*/
44		protected $quota;
45
46		/**
47		* Number of candidates elected so far.
48		*
49		* @var int
50		*/
51		public $electedCandidates;
52
53		/**
54		* Invalid ballots.
55		*
56		* @var \MichaelC\Voting\STV\Ballot[]
57		*/
58		public $rejectedBallots;
59
60		/**
61		* Number of valid ballots.
62		*
63		* @var int
64		*/
65		public $validBallots;
66
67		/**
68		* Number of winners to still be elected (at current stage).
69		*
70		* @var int
71		*/
72		public $candidatesToElect;
73
74		/**
75		* Array of each stage of the election and the vote totals of each candidate
76		*
77		* @var array
78		*/
79		protected $steps;
80
81		/**
82		* Constructor.
83		*
84		* @param Election $election
85		*/
86	2	public function __construct(Election $election, Logger $logger)
87		{
88	2	$this->logger = $logger;
89	2	$this->election = $election;
90
91	2	$this->ballots = $this->election->getBallots();
92	2	$this->rejectedBallots = [];
93	2	$this->candidatesToElect = $this->election->getWinnersCount();
94	2	$this->validBallots = $this->election->getNumBallots();
95	2	$this->steps = [];
96	2	}
97
98		/**
99		* Run the election.
100		*
101		* @return Candidate[] Winning candidates
102		*/
103	1	public function run()
104		{
105	1	$this->logger->notice('Starting to run an election');
106	1	$this->logger->notice(sprintf('There are %d candidates, %d ballots and to be %d winners', $this->election->getCandidateCount(), $this->validBallots, $this->election->getWinnersCount()));
107
108		// Reject invalid ballots, then calculate the quota based on remaining valid ballots
109		// p. 46(3) and p 47
110	1	$this->rejectInvalidBallots();
111	1	$this->setQuota();
112
113		// First step of standard allocation of ballots
114		// p. 46(1) and 46(2)
115	1	$this->firstStep();
116
117	1	$candidates = $this->election->getActiveCandidates();
118
119		// All the re-allocation rounds until we have filled all seats or
120		// have the same number of seats left to fill and candidates remaining
121		// (then elect them).
122	1	$this->processReallocationRounds($candidates);
123		// p. 53
124	1	$this->reallocateRemainingVotes($candidates);
125
126	1	$this->logger->notice('Election complete');
127
128	1	return $this->election->getElectedCandidates();
129		}
130
131		/**
132		* Perform the initial vote allocation.
133		* p. 46.
134		*
135		* @return
136		*/
137	1	protected function firstStep()
138		{
139	1	$this->logger->info('Beginning the first step');
140
141		// Allocate all the ballots
142	1	foreach ($this->ballots as $i => $ballot) {
143	1	$this->allocateVotes($ballot);
144		}
145
146	1	$this->logger->notice('Step 1 complete',
147	1	['candidatesStatus' => $this->election->getCandidatesStatus()]
148		);
149
150	1	$this->steps[1] = $this->election->getCandidatesStatus();
151
152	1	return;
153		}
154
155		/**
156		* Process re-allocation rounds (elimination re-allocations and surplus re-allocations).
157		*
158		* @param Candidate[] $candidates All active candidates to elect
159		*
160		* @return Candidate[]
161		*/
162	1	protected function processReallocationRounds(array &$candidates): array
163		{
164	1	$counter = 1;
165	1	while (($this->candidatesToElect > 0) && ($this->election->getActiveCandidateCount() > $this->candidatesToElect)) {
166	1	if (!$this->checkCandidates($candidates)) {
167		// p. 51(1)
168	1	$this->eliminateCandidates($candidates);
169		}
170
171	1	$candidates = $this->election->getActiveCandidates();
172
173	1	++$counter;
174
175	1	$this->logger->notice("Step $counter complete",
176	1	['candidatesStatus' => $this->election->getCandidatesStatus()]
177		);
178
179	1	$this->steps[$counter] = $this->election->getCandidatesStatus();
180		}
181
182	1	return $candidates;
183		}
184
185		/**
186		* Check if any candidates have reached the quota and can be elected.
187		*
188		* @param Candidate[] $candidates Array of active candidates to check
189		*
190		* @return bool Whether any candidates were changed to elected
191		*/
192	1	protected function checkCandidates(array $candidates): bool
193		{
194	1	$elected = false;
195	1	$candidatesToElect = [];
196
197	1	$this->logger->info('Checking if candidates have passed quota');
198
199	1	if (empty($candidates)) {
200		throw new LogicException('There are no more candidates left');
201		}
202
203	1	foreach ($candidates as $i => $candidate) {
204	1	if ($candidate->getState() !== Candidate::RUNNING) {
205		throw new LogicException('Candidate is not marked as not running but has not been excluded');
206		}
207
208	1	$votes = $candidate->getVotes();
209
210	1	$this->logger->debug("Checking candidate ($candidate) with $votes", ['candidate' => $candidate]);
211
212		// p. 48(1)
213		// Immediately elect a candidate if they hit the quota
214		// We check all the candidates, see who has hit the quota,
215		// add them to a queue, then elect those who have hit the quota to prevent
216		// surplus allocations pushing a candidate over the quota early.
217	1	if ($votes >= $this->quota) {
218	1	$candidatesToElect[] = $candidate;
219	1	$elected = true;
220		}
221		}
222
223		// TODO: Put this in a try, and catch the RuntimeError.
224		// Then sort by the surplus, and fill available seats.
225		// If have same surplus then select randomly (Contary to Scottish STV)
226		// p. 50
227	1	$this->electCandidates($candidatesToElect);
228
229	1	$this->logger->info(('Candidate checking complete. Elected: '.count($candidatesToElect)));
230
231	1	return $elected;
232		}
233
234		/**
235		* Elect an array of candidates.
236		*
237		* @param Candidate[] $candidates Array of candidates to elect
238		*
239		* @return
240		*/
241	1	protected function electCandidates(array $candidates)
242		{
243	1	if ($this->candidatesToElect < count($candidates)) {
244		throw new RuntimeException('Cannot elect candidate as not enough seats to fill');
245		}
246
247	1	foreach ($candidates as $i => $candidate) {
248	1	$this->electCandidate($candidate);
249		}
250
251	1	return;
252		}
253
254		/**
255		* Allocate the next votes from a Ballot.
256		* p. 49.
257		*
258		* @param Ballot $ballot The ballot to allocate the votes from
259		* @param float $multiplier Number to multiply the weight by (surplus)
260		* @param float $divisor The divisor of the weight (Total number of
261		* candidate votes)
262		*
263		* @return Ballot The same ballot passed in modified
264		*/
265	1	protected function allocateVotes(Ballot $ballot, float $multiplier = 1.0, float $divisor = 1.0): Ballot
266		{
267	1	$currentWeight = $ballot->getWeight();
268		// p. 49(3)
269		// "A divided by B" Where A = the value which is calculated
270		// by multiplying the surplus of the transferring candidate
271		// by the value of the ballot paper when received by that candidate; and
272		// B = the total number of votes credited to that candidate
273	1	$weight = $ballot->setWeight(($currentWeight * $multiplier) / $divisor);
274
275		// Get the next candidate on their ballot paper which has not been assigned
276		// a vote this could be the first candidate in round 1
277	1	$candidate = $ballot->getNextChoice();
278
279	1	$this->logger->debug("Allocating vote of weight $weight to $candidate. Previous weight: $currentWeight", array(
280	1	'ballot' => $ballot,
281		));
282
283		// Check there was a next candidate, if only x candidates where listed where
284		// x < the number of candidates standing this will occur.
285	1	if ($candidate !== null) {
286		// Allocate those surplus votes. p. 49(1) and p. 49(2)
287	1	$this->election->getCandidate($candidate)->addVotes($weight);
288	1	$ballot->incrementLevelUsed();
289	1	$this->logger->debug('Vote added to candidate');
290
291		// If the candidate is no longer running due to being defeated or
292		// elected then we re-allocate their vote again.
293	1	if (!in_array($candidate, $this->election->getActiveCandidateIds())) {
294	1	$this->allocateVotes($ballot);
295		}
296		}
297
298	1	return $ballot;
299		}
300
301		/**
302		* Transfer the votes from one candidate to other candidates.
303		*
304		* @param float $surplus The number of surplus votes to transfer
305		* @param Candidate $candidate The candidate being elected to transfer
306		* the votes from
307		*
308		* @return
309		*/
310	1	protected function transferSurplusVotes(float $surplus, Candidate $candidate)
311		{
312	1	$totalVotes = $candidate->getVotes();
313	1	$candidateId = $candidate->getId();
314
315	1	$this->logger->info('Transfering surplus votes');
316
317	1	foreach ($this->ballots as $i => $ballot) {
318	1	if ($ballot->getLastChoice() == $candidateId) {
319	1	$this->allocateVotes($ballot, $surplus, $totalVotes);
320		}
321		}
322
323	1	return;
324		}
325
326		/**
327		* Transfer the votes from one eliminated candidate to other candidates.
328		* p. 51(2).
329		*
330		* @param Candidate $candidate Candidate being eliminated to transfer
331		* the votes from
332		*
333		* @return
334		*/
335	1	protected function transferEliminatedVotes(Candidate $candidate)
336		{
337	1	$candidateId = $candidate->getId();
338
339	1	$votes = $candidate->getVotes();
340
341	1	$this->logger->info("Transfering votes from eliminated candidate ($candidate) with $votes votes");
342
343		// p. 51(2)(a) - Sort into next preference candidates
344		// p. 51(3) - Add votes to candidates
345		// p. 51(4) - Use previous weighting
346	1	foreach ($this->ballots as $i => $ballot) {
347	1	if ($ballot->getLastChoice() == $candidateId) {
348	1	$this->allocateVotes($ballot);
349		}
350		}
351
352	1	return;
353		}
354
355		/**
356		* Elect a candidate after they've passed the threshold.
357		*
358		* @param Candidate $candidate
359		*/
360	1	protected function electCandidate(Candidate $candidate)
361		{
362	1	$this->logger->notice("Electing a candidate: $candidate");
363
364	1	$candidate->setState(Candidate::ELECTED);
365	1	++$this->electedCandidates;
366	1	--$this->candidatesToElect;
367
368	1	if ($this->electedCandidates < $this->election->getWinnersCount()) {
369	1	$surplus = $candidate->getVotes() - $this->quota;
370	1	if ($surplus > 0) {
371	1	$this->transferSurplusVotes($surplus, $candidate);
372		} else {
373	1	$this->logger->notice("No surplus votes from $candidate to reallocate");
374		}
375		}
376
377	1	return;
378		}
379
380		/**
381		* Eliminate the candidate with the lowest number of votes
382		* and reallocated their votes.
383		* p. 51.
384		*
385		* @param Candidate[] $candidates Array of active candidates
386		*
387		* @return int Number of candidates eliminated
388		*/
389	1	protected function eliminateCandidates(array $candidates): int
390		{
391	1	$minimumCandidates = $this->getLowestCandidates($candidates);
392	1	$count = count($minimumCandidates);
393
394		// p. 52(2)(b) - the returning officer shall decide, by lot, which of those
395		// candidates is to be excluded.
396		// We do not look back on previous rounds at all as per p. 52(2)(a)
397	1	$minimumCandidate = $minimumCandidates[(array_rand($minimumCandidates))];
398
399	1	$this->logger->notice(sprintf('There were %d joint lowest candidates,
400	1	%d was randomly selected to be eliminated', $count, $minimumCandidate->getId()));
401
402	1	$this->transferEliminatedVotes($minimumCandidate);
403	1	$minimumCandidate->setState(Candidate::DEFEATED);
404
405	1	return count($minimumCandidates);
406		}
407
408		/**
409		* Get candidates with the lowest number of votes
410		* p. 51 and p. 52(1).
411		*
412		* @param Candidate[] $candidates
413		* Array of active candidates
414		*
415		* @return Candidate[]
416		* Candidates with lowest score
417		*/
418	1	public function getLowestCandidates(array $candidates): array
419		{
420	1	$minimum = count($this->election->getBallots());
421	1	$minimumCandidates = [];
422
423	1	foreach ($candidates as $i => $candidate) {
424	1	if ($candidate->getVotes() < $minimum) {
425	1	$minimum = $candidate->getVotes();
426	1	unset($minimumCandidates);
427	1	$minimumCandidates[] = $candidate;
428	1	} elseif ($candidate->getVotes() == $minimum) {
429	1	$minimumCandidates[] = $candidate;
430	1	$this->logger->info("Calculated as a lowest candidate: $candidate");
431		}
432		}
433
434	1	return $minimumCandidates;
435		}
436
437		/**
438		* Reject any invalid ballots.
439		* p. 46(3).
440		*
441		* @return int Number of rejected ballots
442		*/
443	1	protected function rejectInvalidBallots(): int
444		{
445	1	foreach ($this->ballots as $i => $ballot) {
446	1	if (!$this->checkBallotValidity($ballot)) {
447	1	$this->rejectedBallots[] = clone $ballot;
448	1	unset($this->ballots[$i]);
449		}
450		}
451
452	1	$count = count($this->rejectedBallots);
453
454	1	$this->logger->notice("Found $count rejected ballots");
455
456	1	$this->validBallots = $this->validBallots - $count;
457
458	1	return $count;
459		}
460
461		/**
462		* Check if ballot is valid.
463		*
464		* @param Ballot $ballot Ballot to test
465		*
466		* @return bool True if valid, false if invalid
467		*/
468	2	public function checkBallotValidity(Ballot $ballot): bool
469		{
470	2	$ranking = $ballot->getRanking();
471
472	2	if (!$this->checkCandidateCountValidity($ranking) \|\| !$this->checkBallotVoteDuplicationValidity($ranking) \|\| !$this->checkAllBallotCandidatesValid($ranking))
473		{
474	2	return false;
475		}
476
477	2	$this->logger->debug('Ballot is valid');
478
479	2	return true;
480		}
481
482		/**
483		* Reallocate any remaining votes
484		* p. 53.
485		*
486		* @param Candidate[] $candidates All remaining candidates to elect
487		*
488		* @return
489		*/
490	1	protected function reallocateRemainingVotes(array &$candidates)
491		{
492	1	if (!empty($candidates)) {
493	1	$this->logger->info('All votes re-allocated. Electing all remaining candidates');
494
495	1	if ($this->candidatesToElect < count($candidates)) {
496		throw new LogicException('Cannot elect candidate as no more seats to fill');
497		}
498
499	1	$this->electCandidates($candidates);
500		}
501
502	1	return;
503		}
504
505		/**
506		* Get the quota to win.
507		* p. 47.
508		*
509		* TODO: Move this out of this method and use params/args
510		*
511		* @return int
512		*/
513	1	public function setQuota(): int
514		{
515	1	$this->quota = (int) floor(
516	1	($this->validBallots /
517	1	($this->election->getWinnersCount() + 1)
518		) // p. 47 (1)
519	1	+ 1); // p. 47 (2)
520
521	1	$this->logger->info(sprintf('Quota set at %d based on %d winners and %d valid ballots', $this->quota, $this->election->getWinnersCount(), $this->validBallots));
522
523	1	return $this->quota;
524		}
525
526		/**
527		* Return the quota for the election
528		*
529		* @return int
530		*/
531	1	public function getQuota(): int
532		{
533	1	return $this->quota;
534		}
535
536		/**
537		* Gets an array of the state of all candidates at the end of each
538		* phase/step
539		*
540		* @return array
541		*/
542	1	public function getSteps(): array
543		{
544	1	return $this->steps;
545		}
546
547		/**
548		* Check that a ballot's ranking doesn't have more elements than
549		* we have candidates
550		*
551		* @param array $ranking Ballot ranking
552		*
553		* @return bool False if invalid, True if valid
554		*/
555	2	protected function checkCandidateCountValidity(array $ranking): bool
556		{
557	2	if (count($ranking) > $this->election->getCandidateCount()) {
558	2	$this->logger->debug('Invalid ballot - number of candidates');
559
560	2	return false;
561		}
562
563	2	return true;
564		}
565
566		/**
567		* Check that a ballot doesn't duplicate votes for any candidates (where
568		* a candidate is listed twice in one ranking)
569		*
570		* @param array $ranking Ballot ranking
571		*
572		* @return bool False if invalid, True if valid
573		*/
574	2	protected function checkBallotVoteDuplicationValidity(array $ranking): bool
575		{
576	2	if (count($ranking) !== count(array_unique($ranking))) {
577	1	return false;
578		}
579
580	2	return true;
581		}
582
583		/**
584		* Check that a ballot only contains candidate id numbers that are integers
585		* and correspond to valid candidates.
586		*
587		* @param array $ranking Ballot ranking
588		*
589		* @return bool False if invalid, True if valid
590		*/
591	2	protected function checkAllBallotCandidatesValid(array $ranking): bool
592		{
593	2	$candidateIds = $this->election->getCandidateIds();
594
595	2	foreach ($ranking as $candidate) {
596	2	if (!in_array($candidate, $candidateIds)) {
597	2	$this->logger->debug('Invalid ballot - invalid candidate');
598
599	2	return false;
600		}
601		}
602
603	2	return true;
604		}
605		}
606

michaelcullum / voting-lib

ElectionRunner::allocateVotes() B last analyzed 2016-08-20 15:40 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

ElectionRunner::allocateVotes() B
last analyzed 2016-08-20 15:40 UTC