Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
78.19% covered (warning)
78.19%
147 / 188
64.29% covered (warning)
64.29%
9 / 14
CRAP
0.00% covered (danger)
0.00%
0 / 1
STVTallier
78.19% covered (warning)
78.19%
147 / 188
64.29% covered (warning)
64.29%
9 / 14
58.44
0.00% covered (danger)
0.00%
0 / 1
 __construct
100.00% covered (success)
100.00%
4 / 4
100.00% covered (success)
100.00%
1 / 1
2
 addVote
100.00% covered (success)
100.00%
11 / 11
100.00% covered (success)
100.00%
1 / 1
3
 loadJSONResult
0.00% covered (danger)
0.00%
0 / 2
0.00% covered (danger)
0.00%
0 / 1
2
 getJSONResult
0.00% covered (danger)
0.00%
0 / 4
0.00% covered (danger)
0.00%
0 / 1
2
 getHtmlResult
0.00% covered (danger)
0.00%
0 / 21
0.00% covered (danger)
0.00%
0 / 1
2
 getTextResult
0.00% covered (danger)
0.00%
0 / 13
0.00% covered (danger)
0.00%
0 / 1
2
 finishTally
100.00% covered (success)
100.00%
15 / 15
100.00% covered (success)
100.00%
1 / 1
1
 calculateRound
97.67% covered (success)
97.67%
42 / 43
0.00% covered (danger)
0.00%
0 / 1
4
 distributeVotes
100.00% covered (success)
100.00%
26 / 26
100.00% covered (success)
100.00%
1 / 1
7
 calculateDroopQuota
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 calculateKeepFactors
100.00% covered (success)
100.00%
8 / 8
100.00% covered (success)
100.00%
1 / 1
4
 calculateSurplus
100.00% covered (success)
100.00%
5 / 5
100.00% covered (success)
100.00%
1 / 1
2
 declareWinners
100.00% covered (success)
100.00%
5 / 5
100.00% covered (success)
100.00%
1 / 1
3
 declareEliminated
100.00% covered (success)
100.00%
30 / 30
100.00% covered (success)
100.00%
1 / 1
10
1<?php
2
3namespace MediaWiki\Extension\SecurePoll\Talliers;
4
5use MediaWiki\Extension\SecurePoll\Context;
6use MediaWiki\Extension\SecurePoll\Entities\Question;
7use MediaWiki\Extension\SecurePoll\Talliers\STVFormatter\HtmlFormatter;
8use MediaWiki\Extension\SecurePoll\Talliers\STVFormatter\WikitextFormatter;
9use OOUI\StackLayout;
10
11/**
12 * A STVTallier class,
13 * This implementation is based mainly on
14 * https://web.archive.org/web/20210225045400/https://prfound.org/resources/reference/reference-meek-rule/
15 * and
16 * Hill's programmatic implementation - We follow NZ implementation found in this paper
17 * https://web.archive.org/web/20210723092928/https://ucid.es/system/files/meekm_0.pdf
18 * Major differences being
19 * 1. We do not use pseudo random elimination of candidates.
20 *
21 * Other sources
22 * https://web.archive.org/web/20210723092923/https://rangevoting.org/MeekSTV2.html
23 * https://web.archive.org/web/20200712142326/http://www.votingmatters.org.uk/ISSUE1/P1.HTM
24 */
25class STVTallier extends Tallier {
26
27    /**
28     * An array of vote combinations keyed by underscore-delimited
29     * and ranked options. Each vote has a rank array (which allows
30     * index-1 access to each ranked option) and a count
31     * @var array
32     */
33    public $rankedVotes = [];
34
35    /**
36     * An array of results, gets populated per round
37     * holds current round, both elected and eliminated candidate and the total votes per round.
38     * @var array[]
39     */
40    public $resultsLog = [
41        'elected' => [],
42        'eliminated' => [],
43        'rounds' => []
44    ];
45
46    /**
47     * Number of seats to be filled.
48     * @var int
49     */
50    private $seats;
51
52    /**
53     * An array of all candidates in the election.
54     * @var array<int, string>
55     */
56    private $candidates = [];
57
58    /**
59     * @param Context $context
60     * @param ElectionTallier $electionTallier
61     * @param Question $question
62     */
63    public function __construct( $context, $electionTallier, $question ) {
64        parent::__construct( $context, $electionTallier, $question );
65        foreach ( $question->getOptions() as $option ) {
66            $this->candidates[ $option->getId() ] = $option->getMessage( 'text' );
67        }
68        $this->seats = $question->getProperty( 'min-seats' );
69    }
70
71    /**
72     * @inheritDoc
73     */
74    public function addVote( $scores ) {
75        $id = implode( '_', $scores );
76        $rank = [];
77        foreach ( $scores as $ranked => $optionId ) {
78            $rank[ $ranked + 1 ] = $optionId;
79        }
80
81        if ( !isset( $this->rankedVotes[ $id ] ) ) {
82            $this->rankedVotes[ $id ] = [
83                'count' => 1,
84                'rank' => $rank,
85            ];
86        } else {
87            $this->rankedVotes[ $id ][ 'count' ] += 1;
88        }
89
90        return true;
91    }
92
93    public function loadJSONResult( array $data ) {
94        $this->resultsLog = $data['resultsLog'];
95        $this->rankedVotes = $data['rankedVotes'];
96    }
97
98    public function getJSONResult() {
99        return [
100            'resultsLog' => $this->resultsLog,
101            'rankedVotes' => $this->rankedVotes,
102        ];
103    }
104
105    public function getHtmlResult() {
106        $htmlFormatter = new HtmlFormatter(
107            $this->resultsLog,
108            $this->rankedVotes,
109            $this->seats,
110            $this->candidates
111        );
112        $htmlPreamble = $htmlFormatter->formatPreamble(
113            $this->resultsLog['elected'],
114            $this->resultsLog['eliminated']
115        );
116        $htmlRounds = $htmlFormatter->formatRoundsPreamble();
117        $htmlRounds->appendContent( $htmlFormatter->formatRound() );
118        return new StackLayout( [
119            'items' => [
120                $htmlPreamble,
121                $htmlRounds,
122            ],
123            'continuous' => true,
124            'expanded' => false,
125            'classes' => [ 'election-tally-results--stv' ]
126        ] );
127    }
128
129    public function getTextResult() {
130        $wikitextFormatter = new WikitextFormatter(
131            $this->resultsLog,
132            $this->rankedVotes,
133            $this->seats,
134            $this->candidates
135        );
136        $wikitext = $wikitextFormatter->formatPreamble(
137            $this->resultsLog['elected'],
138            $this->resultsLog['eliminated']
139        );
140        $wikitext .= $wikitextFormatter->formatRoundsPreamble();
141        $wikitext .= $wikitextFormatter->formatRound();
142        return $wikitext;
143    }
144
145    /**
146     * @inheritDoc
147     */
148    public function finishTally() {
149        // Instantiate first round for the iterator
150        $keepFactors = array_fill_keys( array_keys( $this->candidates ), 1 );
151        $voteCount = $this->distributeVotes( $this->rankedVotes, $keepFactors );
152        $quota = $this->calculateDroopQuota( $voteCount['totalVotes'], $this->seats );
153        $round = [
154            'round' => 1,
155            'surplus' => 0,
156            'rankings' => $voteCount['ranking'],
157            'totalVotes' => $voteCount['totalVotes'],
158            'keepFactors' => $keepFactors,
159            'quota' => $quota,
160            'elected' => [],
161            'eliminated' => []
162        ];
163        $this->resultsLog['rounds'][] = $round;
164
165        // Iterate
166        $this->calculateRound( $round );
167    }
168
169    /**
170     * @param array $prevRound
171     */
172    private function calculateRound( $prevRound ) {
173        if ( count( $this->resultsLog['elected'] ) >= $this->seats ) {
174            return;
175        }
176
177        // Advance the round
178        $round = [
179            'round' => $prevRound['round'] + 1,
180            'elected' => [],
181            'eliminated' => [],
182            'surplus' => 0,
183        ];
184
185        $keepFactors =
186            $round['keepFactors'] =
187            $this->calculateKeepFactors(
188                $this->candidates,
189                $prevRound['quota'],
190                $prevRound['keepFactors'],
191                $this->resultsLog['elected'],
192                $this->resultsLog['eliminated'],
193                $prevRound['rankings']
194            );
195
196        $voteCount = $this->distributeVotes( $this->rankedVotes, $keepFactors, $prevRound['rankings'] );
197        $round['quota'] = $this->calculateDroopQuota( $voteCount['totalVotes'], $this->seats );
198        $round['rankings'] = $voteCount['ranking'];
199        $round['totalVotes'] = $voteCount['totalVotes'];
200
201        // Check for unique winners
202        $allWinners = $this->declareWinners( $round['rankings'], $round['quota'] );
203        $roundWinners = $round['elected'] = array_diff( $allWinners, $this->resultsLog['elected'] );
204
205        // If no winners, check for eliminated (no distribution happens here)
206        $round['surplus'] = $this->calculateSurplus( $round['rankings'], $allWinners, $round['quota'] );
207        $allEliminated = $this->declareEliminated(
208            $round['rankings'],
209            $round['surplus'],
210            $this->resultsLog['eliminated'],
211            $this->resultsLog['elected'],
212            $prevRound['surplus']
213        );
214        $roundEliminated = $round['eliminated'] = !$roundWinners ?
215            array_diff( $allEliminated, $this->resultsLog['eliminated'] ) : [];
216
217        $this->resultsLog['rounds'][] = $round;
218        $this->resultsLog['elected'] = array_merge( $this->resultsLog['elected'], $roundWinners );
219        $this->resultsLog['eliminated'] = array_merge( $this->resultsLog['eliminated'], $roundEliminated );
220
221        // Recurse?
222        $hopefuls = array_diff(
223            array_keys( $this->candidates ),
224            array_merge( $this->resultsLog['elected'], $this->resultsLog['eliminated'] )
225        );
226        if ( $hopefuls ) {
227            $this->calculateRound( $round );
228        }
229    }
230
231    /**
232     * Distribute votes per ballot
233     * For each ballot: set ballot weight($weight) to 1,
234     * and then for each candidate,
235     * in order of rank on that ballot:
236     * add $weight multiplied by the keep factor ($voteValue)  of the candidate ($keepFactors[$candidate])
237     * to that candidate’s vote $voteTotals[$candidate]['total'], and reduce $weight by $voteValue,
238     * until no further candidate remains on the ballot.
239     * @param array $ballots
240     * @param array $keepFactors
241     * @param null $prevDistribution
242     * @return array
243     */
244    private function distributeVotes( $ballots, $keepFactors, $prevDistribution = null ): array {
245        $voteTotals = [];
246        $totalVotes = 0;
247        foreach ( $keepFactors as $candidate => $kf ) {
248            $voteTotals[$candidate] = [
249                'votes' => 0,
250                'earned' => 0,
251                'total' => 0,
252            ];
253        }
254
255        // Apply previous round's votes to the count to get "earned" votes
256        if ( $prevDistribution ) {
257            foreach ( $prevDistribution as $candidate => $candidateVotes ) {
258                $voteTotals[$candidate]['votes'] = $candidateVotes['total'];
259                $voteTotals[$candidate]['earned'] -= $candidateVotes['total'];
260            }
261
262        }
263
264        foreach ( $ballots as $ballot ) {
265            $weight = 1;
266            foreach ( $ballot['rank'] as $candidate ) {
267                if ( $weight > 0 ) {
268                    $voteValue = $weight * $keepFactors[$candidate];
269                    $voteTotals[$candidate]['earned'] += ( $voteValue * $ballot['count'] );
270                    $voteTotals[$candidate]['total'] += ( $voteValue * $ballot['count'] );
271                    $weight -= $voteValue;
272                    $totalVotes += ( $voteValue * $ballot['count'] );
273                } else {
274                    break;
275                }
276            }
277
278        }
279
280        return [
281            'ranking' => $voteTotals,
282            'totalVotes' => $totalVotes,
283        ];
284    }
285
286    /**
287     * @param int|float $votes
288     * @param int $seats
289     * @return float
290     */
291    private function calculateDroopQuota( $votes, $seats ): float {
292        return ( $votes / ( (float)$seats + 1 ) ) + 0.000001;
293    }
294
295    /**
296     * Calculates keep factors of all elected candidate at every round
297     * calculated as: current keepfactor multiplied by current quota divided by candidates current vote($voteTotals)
298     * @param array $candidates
299     * @param float $quota
300     * @param array $currentFactors
301     * @param array $winners
302     * @param array $eliminated
303     * @param array $voteTotals
304     * @return array
305     */
306    private function calculateKeepFactors( $candidates, $quota, $currentFactors, $winners, $eliminated, $voteTotals ) {
307        $keepFactors = [];
308        foreach ( $candidates as $candidateId => $candidateName ) {
309            $keepFactors[$candidateId] = in_array( $candidateId, $eliminated ) ? 0 : 1;
310        }
311
312        foreach ( $winners as $winner ) {
313            $voteCount = $voteTotals[$winner]['total'];
314            $prevKeepFactor = $currentFactors[$winner];
315            $keepFactors[$winner] = ( $prevKeepFactor * $quota ) / $voteCount;
316        }
317        return $keepFactors;
318    }
319
320    /**
321     * @param array $ranking
322     * @param array $winners
323     * @param float $quota
324     * @return int|float
325     */
326    private function calculateSurplus( $ranking, $winners, $quota ) {
327        $voteSurplus = 0;
328        foreach ( $winners as $winner ) {
329            $voteTotal = $ranking[$winner]['total'];
330            $voteSurplus += $voteTotal - $quota;
331        }
332        return $voteSurplus;
333    }
334
335    /**
336     * @param array $ranking
337     * @param float $quota
338     * @return array
339     */
340    private function declareWinners( $ranking, $quota ) {
341        $winners = [];
342        foreach ( $ranking as $option => $votes ) {
343            if ( $votes['total'] >= $quota ) {
344                $winners[] = $option;
345            }
346        }
347        return $winners;
348    }
349
350    /**
351     * @param array $ranking
352     * @param int|float $surplus
353     * @param array $eliminated
354     * @param array $elected
355     * @param int|float $prevSurplus
356     * @return array
357     */
358    private function declareEliminated( $ranking, $surplus, $eliminated, $elected, $prevSurplus ) {
359        // Make sure it's ordered by vote totals
360        uksort(
361            $ranking,
362            static function ( $aKey, $bKey ) use ( $ranking ) {
363                $a = $ranking[$aKey];
364                $b = $ranking[$bKey];
365                if ( $a['total'] === $b['total'] ) {
366                    // ascending sort
367                    return $aKey <=> $bKey;
368                }
369                // descending sort
370                return $b['total'] <=> $a['total'];
371            }
372        );
373
374        // Remove anyone who was already eliminated or elected
375        $ranking = array_filter( $ranking, static function ( $key ) use ( $eliminated ) {
376            return !in_array( $key, $eliminated );
377        }, ARRAY_FILTER_USE_KEY );
378
379        // Manually implement array_unique with higher precision than the default function
380        $voteTotals = [];
381        foreach ( $ranking as $candidate ) {
382            // Since it's already been ordered by vote totals, we only need to check the
383            // difference against the last recorded unique value
384            if ( count( $voteTotals ) === 0 ) {
385                // First value is always unique
386                $voteTotals[] = $candidate['total'];
387            } elseif ( isset( $voteTotals[ count( $voteTotals ) - 1 ] ) ) {
388                if ( abs( $candidate['total'] - $voteTotals[ count( $voteTotals ) - 1 ] ) > PHP_FLOAT_EPSILON ) {
389                    $voteTotals[] = $candidate['total'];
390                }
391            }
392        }
393
394        // If everyone left is tied and no one made quota
395        // Everyone left gets eliminated
396        if ( count( $voteTotals ) === 1 ) {
397            return array_keys( $ranking );
398        }
399
400        // Get the lowest ranking candidates
401        [ $secondLowest, $lowest ] = array_slice( $voteTotals, -2 );
402
403        // Check if we can eliminate the lowest candidate
404        // using Hill's surplus-based short circuit elimination
405        $lastPlace = array_keys( array_filter( $ranking, static function ( $ranked ) use ( $lowest, $elected ) {
406            return abs( $ranked['total'] - $lowest ) < PHP_FLOAT_EPSILON && !in_array( key( $ranked ), $elected );
407        } ) );
408        if ( ( $lowest * count( $lastPlace ) ) + $surplus < $secondLowest ||
409            abs( $surplus - $prevSurplus ) < PHP_FLOAT_EPSILON ) {
410            return $lastPlace;
411        }
412        return [];
413    }
414}