VoteHandler::eliminateCandidates() - Code Metrics - Inspection of "A series of updates and bug fixes to the vote hand..." - michaelcullum/voting-lib - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 7d0f5c...bcb4e0 )

by Michael

created 2016-08-19 17:17 UTC

VoteHandler::eliminateCandidates() A

↳ Parent: VoteHandler

Complexity

Conditions	2
Paths	2

Size

Total Lines	13
Code Lines	7

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	0
CRAP Score	6

Importance

Changes

Metric	Value
dl	0
loc	13
ccs	0
cts	7
cp	0
rs	9.4285
c	0
b	0
f	0
cc	2
eloc	7
nc	2
nop	1
crap	6

<?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;

class VoteHandler
{
    /**
     * 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
     */
    protected $electedCandidates;

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

    /**
     * Logger.
     *
     * @var \Psr\Log\LoggerInterface
     */
    protected $logger;

    protected $validBallots;

    /**
     * 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->validBallots = $this->election->getNumBallots();
    }

    /**
     * Run the election.
     *
     * @return \MichaelC\Voting\STV\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()));

        $this->rejectInvalidBallots();
        $this->quota = $this->getQuota();

        $this->firstStep();

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

        while ($this->electedCandidates < $this->election->getWinnersCount()) {
            if (!$this->checkCandidates($candidates)) {
                $this->eliminateCandidates($candidates);
            }

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

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

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

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

        foreach ($this->ballots as $i => $ballot) {
            $this->logger->debug("Processing ballot $i in stage 1");

            $this->allocateVotes($ballot);
        }

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

        return;
    }

    /**
     * Check if any candidates have reached the quota and can be elected.
     *
     * @param array $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) {
            $votes = $candidate->getVotes();

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

            if ($votes >= $this->quota) {
                $candidatesToElect[] = $candidate;
                $elected = true;
            }
        }

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

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

        return $elected;
    }

    /**
     * Allocate the next votes from a Ballot.
     *
     * @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();
        $weight = $ballot->setWeight(($currentWeight * $multiplier) / $divisor);
        $candidate = $ballot->getNextChoice();

        // TODO: Check if candidate is withdrawn

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

        if ($candidate !== null) {
            $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.
     *
     * @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");

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

        return;
    }

    /**
     * Elect a candidate after they've passed the threshold.
     *
     * @param \Michaelc\Voting\STV\Candidate $candidate
     */
    protected function electCandidate(Candidate $candidate)
    {
        if ($candidate->getVotes() < $this->quota) {
            throw new VotingException("We shouldn't be electing someone who hasn't met the quota");
        }

        $this->logger->notice("Electing a candidate: $candidate");

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

        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.
     *
     * TODO: Eliminate all lowest candidates after step one, then
     * randomly choose.
     *
     * @param \Michaelc\Voting\STV\Candidate[] $candidates
     *                                                     Array of active candidates
     *
     * @return int Number of candidates eliminated
     */
    protected function eliminateCandidates(array $candidates): int
    {
        $minimumCandidates = $this->getLowestCandidates($candidates);

        foreach ($minimumCandidates as $minimumCandidate) {
            $this->logger->notice("Eliminating a candidate: $minimumCandidate");

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

        return count($minimumCandidates);
    }

    /**
     * Get candidates with the lowest number of votes.
     *
     * @param \Michaelc\Voting\STV\Candidate[] $candidates
     *                                                     Array of active candidates
     *
     * @return \Michaelc\Voting\STV\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;
            }
        }

        $count = count($minimumCandidates);

        $this->logger->info("Calculated the joint lowest candidates ($count)");

        return $minimumCandidates;
    }

    /**
     * Reject any invalid ballots.
     *
     * @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
    {
        if (count($ballot->getRanking()) > $this->election->getCandidateCount()) {
            $this->logger->debug('Invalid ballot - number of candidates', ['ballot' => $ballot]);

            return false;
        } else {
            $candidateIds = $this->election->getCandidateIds();

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

                    return false;
                }
            }
        }

        // TODO: Check for candidates multiple times on the same ballot paper

        $this->logger->debug('Ballot is valid', ['ballot' => $ballot]);

        return true;
    }

    /**
     * Get the quota to win.
     *
     * @return int
     */
    public function getQuota(): int
    {
        $quota = floor(
            ($this->validBallots /
                ($this->election->getWinnersCount() + 1)
            )
            + 1);

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

        return $quota;
    }
}


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		class VoteHandler
10		{
11		/**
12		* Election object.
13		*
14		* @var \Michaelc\Voting\STV\Election;
15		*/
16		protected $election;
17
18		/**
19		* Array of all ballots in election.
20		*
21		* @var \MichaelC\Voting\STV\Ballot[]
22		*/
23		protected $ballots;
24
25		/**
26		* Quota of votes needed for a candidate to be elected.
27		*
28		* @var int
29		*/
30		protected $quota;
31
32		/**
33		* Number of candidates elected so far.
34		*
35		* @var int
36		*/
37		protected $electedCandidates;
38
39		/**
40		* Invalid ballots.
41		*
42		* @var \MichaelC\Voting\STV\Ballot[]
43		*/
44		protected $rejectedBallots;
45
46		/**
47		* Logger.
48		*
49		* @var \Psr\Log\LoggerInterface
50		*/
51		protected $logger;
52
53		protected $validBallots;
54
55		/**
56		* Constructor.
57		*
58		* @param Election $election
59		*/
60	2	public function __construct(Election $election, Logger $logger)
61		{
62	2	$this->logger = $logger;
63	2	$this->election = $election;
64	2	$this->ballots = $this->election->getBallots();
65	2	$this->rejectedBallots = [];
66
67	2	$this->validBallots = $this->election->getNumBallots();
68	2	}
69
70		/**
71		* Run the election.
72		*
73		* @return \MichaelC\Voting\STV\Candidate[] Winning candidates
74		*/
75		public function run()
76		{
77		$this->logger->notice('Starting to run an election');
78		$this->logger->notice(sprintf('There are %d candidates, %d ballots and to be %d winners', $this->election->getCandidateCount(), $this->validBallots, $this->election->getWinnersCount()));
79
80		$this->rejectInvalidBallots();
81		$this->quota = $this->getQuota();
82
83		$this->firstStep();
84
85		$candidates = $this->election->getActiveCandidates();
86
87		while ($this->electedCandidates < $this->election->getWinnersCount()) {
88		if (!$this->checkCandidates($candidates)) {
89		$this->eliminateCandidates($candidates);
90		}
91
92		$candidates = $this->election->getActiveCandidates();
93		}
94
95		$this->logger->notice('Election complete');
96
97		return $this->election->getElectedCandidates();
98		}
99
100		/**
101		* Perform the initial vote allocation.
102		*
103		* @return
104		*/
105		protected function firstStep()
106		{
107		$this->logger->info('Beginning the first step');
108
109		foreach ($this->ballots as $i => $ballot) {
110		$this->logger->debug("Processing ballot $i in stage 1");
111
112		$this->allocateVotes($ballot);
113		}
114
115		$this->logger->notice('First step complete',
116		['candidatesStatus' => $this->election->getCandidatesStatus()]
117		);
118
119		return;
120		}
121
122		/**
123		* Check if any candidates have reached the quota and can be elected.
124		*
125		* @param array $candidates Array of active candidates to check
126		*
127		* @return bool Whether any candidates were changed to elected
128		*/
129		protected function checkCandidates(array $candidates): bool
130		{
131		$elected = false;
132		$candidatesToElect = [];
133
134		$this->logger->info('Checking if candidates have passed quota');
135
136		if (empty($candidates))
137		{
138		throw new LogicException("There are no more candidates left");
139		}
140
141		foreach ($candidates as $i => $candidate) {
142		$votes = $candidate->getVotes();
143
144		$this->logger->debug("Checking candidate ($candidate) with $votes", ['candidate' => $candidate]);
145
146		if ($votes >= $this->quota) {
147		$candidatesToElect[] = $candidate;
148		$elected = true;
149		}
150		}
151
152		foreach ($candidatesToElect as $i => $candidate) {
153		$this->electCandidate($candidate);
154		}
155
156		$this->logger->info(('Candidate checking complete. Elected: ' . count($candidatesToElect)));
157
158		return $elected;
159		}
160
161		/**
162		* Allocate the next votes from a Ballot.
163		*
164		* @param Ballot $ballot The ballot to allocate the votes from
165		* @param float $multiplier Number to multiply the weight by (surplus)
166		* @param float $divisor The divisor of the weight (Total number of
167		* candidate votes)
168		*
169		* @return Ballot The same ballot passed in modified
170		*/
171		protected function allocateVotes(Ballot $ballot, float $multiplier = 1.0, float $divisor = 1.0): Ballot
172		{
173		$currentWeight = $ballot->getWeight();
174		$weight = $ballot->setWeight(($currentWeight * $multiplier) / $divisor);
175		$candidate = $ballot->getNextChoice();
176
177		// TODO: Check if candidate is withdrawn
178
179		$this->logger->debug("Allocating vote of weight $weight to $candidate. Previous weight: $currentWeight", array(
180		'ballot' => $ballot,
181		));
182
183		if ($candidate !== null) {
184		$this->election->getCandidate($candidate)->addVotes($weight);
185		$ballot->incrementLevelUsed();
186		$this->logger->debug('Vote added to candidate');
187
188		// If the candidate is no longer running due to being defeated or
189		// elected then we re-allocate their vote again.
190		if (!in_array($candidate, $this->election->getActiveCandidateIds()))
191		{
192		$this->allocateVotes($ballot);
193		}
194		}
195
196		return $ballot;
197		}
198
199		/**
200		* Transfer the votes from one candidate to other candidates.
201		*
202		* @param float $surplus The number of surplus votes to transfer
203		* @param Candidate $candidate The candidate being elected to transfer
204		* the votes from
205		*
206		* @return
207		*/
208		protected function transferSurplusVotes(float $surplus, Candidate $candidate)
209		{
210		$totalVotes = $candidate->getVotes();
211		$candidateId = $candidate->getId();
212
213		$this->logger->info('Transfering surplus votes');
214
215		foreach ($this->ballots as $i => $ballot) {
216		if ($ballot->getLastChoice() == $candidateId) {
217		$this->allocateVotes($ballot, $surplus, $totalVotes);
218		}
219		}
220
221		return;
222		}
223
224		/**
225		* Transfer the votes from one eliminated candidate to other candidates.
226		*
227		* @param Candidate $candidate Candidate being eliminated to transfer
228		* the votes from
229		*
230		* @return
231		*/
232		protected function transferEliminatedVotes(Candidate $candidate)
233		{
234		$candidateId = $candidate->getId();
235
236		$votes = $candidate->getVotes();
237
238		$this->logger->info("Transfering votes from eliminated candidate ($candidate) with $votes votes");
239
240		foreach ($this->ballots as $i => $ballot) {
241		if ($ballot->getLastChoice() == $candidateId) {
242		$this->allocateVotes($ballot);
243		}
244		}
245
246		return;
247		}
248
249		/**
250		* Elect a candidate after they've passed the threshold.
251		*
252		* @param \Michaelc\Voting\STV\Candidate $candidate
253		*/
254		protected function electCandidate(Candidate $candidate)
255		{
256		if ($candidate->getVotes() < $this->quota) {
257		throw new VotingException("We shouldn't be electing someone who hasn't met the quota");
258		}
259
260		$this->logger->notice("Electing a candidate: $candidate");
261
262		$candidate->setState(Candidate::ELECTED);
263		++$this->electedCandidates;
264
265		if ($this->electedCandidates < $this->election->getWinnersCount()) {
266		$surplus = $candidate->getVotes() - $this->quota;
267		if ($surplus > 0) {
268		$this->transferSurplusVotes($surplus, $candidate);
269		} else {
270		$this->logger->notice("No surplus votes from $candidate to reallocate");
271		}
272
		0 ignored issues – show Coding Style introduced 2016-08-19 17:20 UTC by Report Bug Copy Issue Report Blank line found at end of control structure Loading history...
273		}
274
275		return;
276		}
277
278		/**
279		* Eliminate the candidate with the lowest number of votes
280		* and reallocated their votes.
281		*
282		* TODO: Eliminate all lowest candidates after step one, then
283		* randomly choose.
284		*
285		* @param \Michaelc\Voting\STV\Candidate[] $candidates
286		* Array of active candidates
287		*
288		* @return int Number of candidates eliminated
289		*/
290		protected function eliminateCandidates(array $candidates): int
291		{
292		$minimumCandidates = $this->getLowestCandidates($candidates);
293
294		foreach ($minimumCandidates as $minimumCandidate) {
295		$this->logger->notice("Eliminating a candidate: $minimumCandidate");
296
297		$this->transferEliminatedVotes($minimumCandidate);
298		$minimumCandidate->setState(Candidate::DEFEATED);
299		}
300
301		return count($minimumCandidates);
302		}
303
304		/**
305		* Get candidates with the lowest number of votes.
306		*
307		* @param \Michaelc\Voting\STV\Candidate[] $candidates
308		* Array of active candidates
309		*
310		* @return \Michaelc\Voting\STV\Candidate[]
311		* Candidates with lowest score
312		*/
313		public function getLowestCandidates(array $candidates): array
314		{
315		$minimum = count($this->election->getBallots());
316		$minimumCandidates = [];
317
318		foreach ($candidates as $i => $candidate) {
319		if ($candidate->getVotes() < $minimum) {
320		$minimum = $candidate->getVotes();
321		unset($minimumCandidates);
322		$minimumCandidates[] = $candidate;
323		} elseif ($candidate->getVotes() == $minimum) {
324		$minimumCandidates[] = $candidate;
325		}
326		}
327
328		$count = count($minimumCandidates);
329
330		$this->logger->info("Calculated the joint lowest candidates ($count)");
331
332		return $minimumCandidates;
333		}
334
335		/**
336		* Reject any invalid ballots.
337		*
338		* @return int Number of rejected ballots
339		*/
340		protected function rejectInvalidBallots(): int
341		{
342		foreach ($this->ballots as $i => $ballot) {
343		if (!$this->checkBallotValidity($ballot)) {
344		$this->rejectedBallots[] = clone $ballot;
345		unset($this->ballots[$i]);
346		}
347		}
348
349		$count = count($this->rejectedBallots);
350
351		$this->logger->notice("Found $count rejected ballots");
352
353		$this->validBallots = $this->validBallots - $count;
354
355		return $count;
356		}
357
358		/**
359		* Check if ballot is valid.
360		*
361		* @param Ballot $ballot Ballot to test
362		*
363		* @return bool True if valid, false if invalid
364		*/
365	1	public function checkBallotValidity(Ballot $ballot): bool
366		{
367	1	if (count($ballot->getRanking()) > $this->election->getCandidateCount()) {
368	1	$this->logger->debug('Invalid ballot - number of candidates', ['ballot' => $ballot]);
369
370	1	return false;
371		} else {
372	1	$candidateIds = $this->election->getCandidateIds();
373
374	1	foreach ($ballot->getRanking() as $i => $candidate) {
375	1	if (!in_array($candidate, $candidateIds)) {
376	1	$this->logger->debug('Invalid ballot - invalid candidate');
377
378	1	return false;
379		}
380		}
381		}
382
383		// TODO: Check for candidates multiple times on the same ballot paper
384
385	1	$this->logger->debug('Ballot is valid', ['ballot' => $ballot]);
386
387	1	return true;
388		}
389
390		/**
391		* Get the quota to win.
392		*
393		* @return int
394		*/
395		public function getQuota(): int
396		{
397		$quota = floor(
398		($this->validBallots /
399		($this->election->getWinnersCount() + 1)
400		)
401		+ 1);
402
403		$this->logger->info(sprintf("Quota set at %d based on %d winners and %d valid ballots", $quota, $this->election->getWinnersCount(), $this->validBallots));
404
405		return $quota;
406		}
407		}
408

michaelcullum / voting-lib

Push — master ( 7d0f5c...bcb4e0 )

VoteHandler::eliminateCandidates() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like