Michaelc\Voting\STV\ElectionRunner

Complexity

Total Complexity

43

Size/Duplication

Total Lines	466
Duplicated Lines	0 %

Coupling/Cohesion

Components	1
Dependencies	5

Test Coverage

Coverage

98.03%

Importance

Changes

0

16 Methods

Rating	Name	Duplication	Size	Complexity
A	__construct()	0	10	1
A	run()	0	19	1
A	firstStep()	0	14	2
A	processReallocationRounds()	0	19	4
B	checkCandidates()	0	34	5
A	electCandidates()	0	8	2
B	allocateVotes()	0	27	3
A	transferSurplusVotes()	0	15	3
A	transferEliminatedVotes()	0	16	3
A	electCandidate()	0	20	3
A	eliminateCandidates()	0	15	1
A	getLowestCandidates()	0	18	4
A	rejectInvalidBallots()	0	17	3
B	checkBallotValidity()	0	24	4
A	reallocateRemainingVotes()	0	16	3
A	getQuota()	0	12	1

<?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 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
     */
    protected $electedCandidates;

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

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

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

    /**
     * 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();
    }

    /**
     * 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()));

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

        $this->firstStep();

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

        $this->processReallocationRounds($candidates);
        $this->reallocateRemainingVotes($candidates);

        $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->allocateVotes($ballot);
        }

        $this->logger->notice('Step 1 complete',
            ['candidatesStatus' => $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)) {
                $this->eliminateCandidates($candidates);
            }

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

            $counter++;

            $this->logger->notice("Step $counter complete",
                ['candidatesStatus' => $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]);

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

        $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)
    {
        foreach ($candidates as $i => $candidate) {
            $this->electCandidate($candidate);
        }

        return;
    }

    /**
     * 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 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");
            }

Blank line found at end of control structure

        }

        return;
    }

    /**
     * Eliminate the candidate with the lowest number of votes
     * and reallocated their votes.
     *
     * @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);

        $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.
     *
     * @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.
     *
     * @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;
    }

    /**
     * Reallocate any remaining votes
     *
     * @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 an un-eliminated but remaining candidate as no more seats to fill');
            }

            $this->electCandidates($candidates);
        }

        return;
    }

    /**
     * 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;
    }
}