Completed
Push — master ( bcb4e0...95db08 )
by Michael
02:54
created

VoteHandler::transferSurplusVotes()   A

Complexity

Conditions 3
Paths 3

Size

Total Lines 15
Code Lines 8

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 8
CRAP Score 3

Importance

Changes 0
Metric Value
c 0
b 0
f 0
dl 0
loc 15
ccs 8
cts 8
cp 1
rs 9.4285
cc 3
eloc 8
nc 3
nop 2
crap 3
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
    protected $candidatesToElect;
56
57
    /**
58
     * Constructor.
59
     *
60
     * @param Election $election
61
     */
62 2
    public function __construct(Election $election, Logger $logger)
63
    {
64 2
        $this->logger = $logger;
65 2
        $this->election = $election;
66 2
        $this->ballots = $this->election->getBallots();
67 2
        $this->rejectedBallots = [];
68 2
        $this->candidatesToElect = $this->election->getWinnersCount();
69
70 2
        $this->validBallots = $this->election->getNumBallots();
71 2
    }
72
73
    /**
74
     * Run the election.
75
     *
76
     * @return \MichaelC\Voting\STV\Candidate[] Winning candidates
77
     */
78 1
    public function run()
79
    {
80 1
        $this->logger->notice('Starting to run an election');
81 1
        $this->logger->notice(sprintf('There are %d candidates, %d ballots and to be %d winners', $this->election->getCandidateCount(), $this->validBallots, $this->election->getWinnersCount()));
82
83 1
        $this->rejectInvalidBallots();
84 1
        $this->quota = $this->getQuota();
85
86 1
        $this->firstStep();
87
88 1
        $candidates = $this->election->getActiveCandidates();
89
90 1
        while (($this->candidatesToElect > 0) && ($this->election->getActiveCandidateCount() > $this->candidatesToElect)) {
91 1
            if (!$this->checkCandidates($candidates)) {
92 1
                $this->eliminateCandidates($candidates);
93
            }
94
95 1
            $candidates = $this->election->getActiveCandidates();
96
        }
97
98 1
        if (!empty($candidates))
99
        {
100 1
            $this->logger->info('All votes re-allocated. Electing all remaining candidates');
101
102 1
            foreach ($candidates as $i => $candidate) {
103 1
                $this->electCandidate($candidate);
104
            }
105
        }
106
107
108 1
        $this->logger->notice('Election complete');
109
110 1
        return $this->election->getElectedCandidates();
111
    }
112
113
    /**
114
     * Perform the initial vote allocation.
115
     *
116
     * @return
117
     */
118 1
    protected function firstStep()
119
    {
120 1
        $this->logger->info('Beginning the first step');
121
122 1
        foreach ($this->ballots as $i => $ballot) {
123 1
            $this->logger->debug("Processing ballot $i in stage 1");
124
125 1
            $this->allocateVotes($ballot);
126
        }
127
128 1
        $this->logger->notice('First step complete',
129 1
            ['candidatesStatus' => $this->election->getCandidatesStatus()]
130
        );
131
132 1
        return;
133
    }
134
135
    /**
136
     * Check if any candidates have reached the quota and can be elected.
137
     *
138
     * @param array $candidates Array of active candidates to check
139
     *
140
     * @return bool Whether any candidates were changed to elected
141
     */
142 1
    protected function checkCandidates(array $candidates): bool
143
    {
144 1
        $elected = false;
145 1
        $candidatesToElect = [];
146
147 1
        $this->logger->info('Checking if candidates have passed quota');
148
149 1
        if (empty($candidates))
150
        {
151
            throw new LogicException("There are no more candidates left");
152
        }
153
154 1
        foreach ($candidates as $i => $candidate) {
155 1
            $votes = $candidate->getVotes();
156
157 1
            $this->logger->debug("Checking candidate ($candidate) with $votes", ['candidate' => $candidate]);
158
159 1
            if ($votes >= $this->quota) {
160 1
                $candidatesToElect[] = $candidate;
161 1
                $elected = true;
162
            }
163
        }
164
165 1
        foreach ($candidatesToElect as $i => $candidate) {
166 1
            $this->electCandidate($candidate);
167
        }
168
169 1
        $this->logger->info(('Candidate checking complete. Elected: ' . count($candidatesToElect)));
170
171 1
        return $elected;
172
    }
173
174
    /**
175
     * Allocate the next votes from a Ballot.
176
     *
177
     * @param Ballot $ballot     The ballot to allocate the votes from
178
     * @param float  $multiplier Number to multiply the weight by (surplus)
179
     * @param float  $divisor    The divisor of the weight (Total number of
180
     *                           candidate votes)
181
     *
182
     * @return Ballot The same ballot passed in modified
183
     */
184 1
    protected function allocateVotes(Ballot $ballot, float $multiplier = 1.0, float $divisor = 1.0): Ballot
185
    {
186 1
        $currentWeight = $ballot->getWeight();
187 1
        $weight = $ballot->setWeight(($currentWeight * $multiplier) / $divisor);
188 1
        $candidate = $ballot->getNextChoice();
189
190
        // TODO: Check if candidate is withdrawn
191
192 1
        $this->logger->debug("Allocating vote of weight $weight to $candidate. Previous weight: $currentWeight", array(
193 1
            'ballot' => $ballot,
194
        ));
195
196 1
        if ($candidate !== null) {
197 1
            $this->election->getCandidate($candidate)->addVotes($weight);
198 1
            $ballot->incrementLevelUsed();
199 1
            $this->logger->debug('Vote added to candidate');
200
201
            // If the candidate is no longer running due to being defeated or
202
            // elected then we re-allocate their vote again.
203 1
            if (!in_array($candidate, $this->election->getActiveCandidateIds()))
204
            {
205 1
                $this->allocateVotes($ballot);
206
            }
207
        }
208
209 1
        return $ballot;
210
    }
211
212
    /**
213
     * Transfer the votes from one candidate to other candidates.
214
     *
215
     * @param float     $surplus   The number of surplus votes to transfer
216
     * @param Candidate $candidate The candidate being elected to transfer
217
     *                             the votes from
218
     *
219
     * @return
220
     */
221 1
    protected function transferSurplusVotes(float $surplus, Candidate $candidate)
222
    {
223 1
        $totalVotes = $candidate->getVotes();
224 1
        $candidateId = $candidate->getId();
225
226 1
        $this->logger->info('Transfering surplus votes');
227
228 1
        foreach ($this->ballots as $i => $ballot) {
229 1
            if ($ballot->getLastChoice() == $candidateId) {
230 1
                $this->allocateVotes($ballot, $surplus, $totalVotes);
231
            }
232
        }
233
234 1
        return;
235
    }
236
237
    /**
238
     * Transfer the votes from one eliminated candidate to other candidates.
239
     *
240
     * @param Candidate $candidate Candidate being eliminated to transfer
241
     *                             the votes from
242
     *
243
     * @return
244
     */
245 1
    protected function transferEliminatedVotes(Candidate $candidate)
246
    {
247 1
        $candidateId = $candidate->getId();
248
249 1
        $votes = $candidate->getVotes();
250
251 1
        $this->logger->info("Transfering votes from eliminated candidate ($candidate) with $votes votes");
252
253 1
        foreach ($this->ballots as $i => $ballot) {
254 1
            if ($ballot->getLastChoice() == $candidateId) {
255 1
                $this->allocateVotes($ballot);
256
            }
257
        }
258
259 1
        return;
260
    }
261
262
    /**
263
     * Elect a candidate after they've passed the threshold.
264
     *
265
     * @param \Michaelc\Voting\STV\Candidate $candidate
266
     */
267 1
    protected function electCandidate(Candidate $candidate)
268
    {
269 1
        $this->logger->notice("Electing a candidate: $candidate");
270
271 1
        $candidate->setState(Candidate::ELECTED);
272 1
        $this->electedCandidates++;
273 1
        $this->candidatesToElect--;
274
275 1
        if ($this->electedCandidates < $this->election->getWinnersCount()) {
276 1
            $surplus = $candidate->getVotes() - $this->quota;
277 1
            if ($surplus > 0) {
278 1
                $this->transferSurplusVotes($surplus, $candidate);
279
            } else {
280 1
                $this->logger->notice("No surplus votes from $candidate to reallocate");
281
            }
282
0 ignored issues
show
Coding Style introduced by
Blank line found at end of control structure
Loading history...
283
        }
284
285 1
        return;
286
    }
287
288
    /**
289
     * Eliminate the candidate with the lowest number of votes
290
     * and reallocated their votes.
291
     *
292
     * @param \Michaelc\Voting\STV\Candidate[] $candidates Array of active candidates
293
     *
294
     * @return int Number of candidates eliminated
295
     */
296 1
    protected function eliminateCandidates(array $candidates): int
297
    {
298 1
        $minimumCandidates = $this->getLowestCandidates($candidates);
299 1
        $count = count($minimumCandidates);
300
301 1
        $minimumCandidate = $minimumCandidates[(array_rand($minimumCandidates))];
302
303 1
        $this->logger->notice(sprintf("There were %d joint lowest candidates,
304 1
            %d was randomly selected to be eliminated", $count, $minimumCandidate->getId()));
305
306 1
        $this->transferEliminatedVotes($minimumCandidate);
307 1
        $minimumCandidate->setState(Candidate::DEFEATED);
308
309 1
        return count($minimumCandidates);
310
    }
311
312
    /**
313
     * Get candidates with the lowest number of votes.
314
     *
315
     * @param \Michaelc\Voting\STV\Candidate[] $candidates
316
     *                                                     Array of active candidates
317
     *
318
     * @return \Michaelc\Voting\STV\Candidate[]
319
     *                                          Candidates with lowest score
320
     */
321 1
    public function getLowestCandidates(array $candidates): array
322
    {
323 1
        $minimum = count($this->election->getBallots());
324 1
        $minimumCandidates = [];
325
326 1
        foreach ($candidates as $i => $candidate) {
327 1
            if ($candidate->getVotes() < $minimum) {
328 1
                $minimum = $candidate->getVotes();
329 1
                unset($minimumCandidates);
330 1
                $minimumCandidates[] = $candidate;
331 1
            } elseif ($candidate->getVotes() == $minimum) {
332 1
                $minimumCandidates[] = $candidate;
333 1
                $this->logger->info("Calculated as a lowest candidate: $candidate");
334
            }
335
        }
336
337 1
        $count = count($minimumCandidates);
0 ignored issues
show
Unused Code introduced by
$count is not used, you could remove the assignment.

This check looks for variable assignements that are either overwritten by other assignments or where the variable is not used subsequently.

$myVar = 'Value';
$higher = false;

if (rand(1, 6) > 3) {
    $higher = true;
} else {
    $higher = false;
}

Both the $myVar assignment in line 1 and the $higher assignment in line 2 are dead. The first because $myVar is never used and the second because $higher is always overwritten for every possible time line.

Loading history...
338
339 1
        return $minimumCandidates;
340
    }
341
342
    /**
343
     * Reject any invalid ballots.
344
     *
345
     * @return int Number of rejected ballots
346
     */
347 1
    protected function rejectInvalidBallots(): int
348
    {
349 1
        foreach ($this->ballots as $i => $ballot) {
350 1
            if (!$this->checkBallotValidity($ballot)) {
351 1
                $this->rejectedBallots[] = clone $ballot;
352 1
                unset($this->ballots[$i]);
353
            }
354
        }
355
356 1
        $count = count($this->rejectedBallots);
357
358 1
        $this->logger->notice("Found $count rejected ballots");
359
360 1
        $this->validBallots = $this->validBallots - $count;
361
362 1
        return $count;
363
    }
364
365
    /**
366
     * Check if ballot is valid.
367
     *
368
     * @param Ballot $ballot Ballot to test
369
     *
370
     * @return bool True if valid, false if invalid
371
     */
372 2
    public function checkBallotValidity(Ballot $ballot): bool
373
    {
374 2
        if (count($ballot->getRanking()) > $this->election->getCandidateCount()) {
375 2
            $this->logger->debug('Invalid ballot - number of candidates', ['ballot' => $ballot]);
376
377 2
            return false;
378
        } else {
379 2
            $candidateIds = $this->election->getCandidateIds();
380
381 2
            foreach ($ballot->getRanking() as $i => $candidate) {
382 2
                if (!in_array($candidate, $candidateIds)) {
383 2
                    $this->logger->debug('Invalid ballot - invalid candidate');
384
385 2
                    return false;
386
                }
387
            }
388
        }
389
390
        // TODO: Check for candidates multiple times on the same ballot paper
391
392 2
        $this->logger->debug('Ballot is valid', ['ballot' => $ballot]);
393
394 2
        return true;
395
    }
396
397
    /**
398
     * Get the quota to win.
399
     *
400
     * @return int
401
     */
402 1
    public function getQuota(): int
403
    {
404 1
        $quota = floor(
405 1
            ($this->validBallots /
406 1
                ($this->election->getWinnersCount() + 1)
407
            )
408 1
            + 1);
409
410 1
        $this->logger->info(sprintf("Quota set at %d based on %d winners and %d valid ballots", $quota, $this->election->getWinnersCount(), $this->validBallots));
411
412 1
        return $quota;
413
    }
414
}
415