gt:           String winner = tiebreak.selectCandidate();
context: /*
   * Universal RCV Tabulator
   * Copyright (c) 2017-2020 Bright Spots Developers.
   *
   * This program is free software: you can redistribute it and/or modify it under the terms of the
   * GNU Affero General Public License as published by the Free Software Foundation, either version 3
   * of the License, or (at your option) any later version.
   *
   * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
   * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
   * the GNU Affero General Public License for more details.
   *
   * You should have received a copy of the GNU Affero General Public License along with this
   * program.  If not, see <http://www.gnu.org/licenses/>.
   */
  
  /*
   * Purpose:
   * Perform ranked choice tabulation calculations. Round-by-round tabulation of votes to
   * each candidate. Handles overvote / undervote decisions batch elimination and tiebreaks. Results
   * are logged to console and audit file.
   */
  
  package network.brightspots.rcv;
  
  import static network.brightspots.rcv.Utils.isNullOrBlank;
  
  import java.io.IOException;
  import java.math.BigDecimal;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Map;
  import java.util.Random;
  import java.util.Set;
  import java.util.SortedMap;
  import java.util.TreeMap;
  import network.brightspots.rcv.CastVoteRecord.VoteOutcomeType;
  import network.brightspots.rcv.ResultsWriter.RoundSnapshotDataMissingException;
  
  class Tabulator {
  
    static final String OVERVOTE_RULE_ALWAYS_SKIP_TEXT = "Always skip to next rank";
    static final String OVERVOTE_RULE_EXHAUST_IMMEDIATELY_TEXT = "Exhaust immediately";
    static final String OVERVOTE_RULE_EXHAUST_IF_MULTIPLE_TEXT = "Exhaust if multiple continuing";
    // When the CVR contains an overvote we "normalize" it to use this string
    static final String EXPLICIT_OVERVOTE_LABEL = "overvote";
    // Similarly, we normalize undeclared write-ins to use this string
    static final String UNDECLARED_WRITE_IN_OUTPUT_LABEL = "Undeclared Write-ins";
    // cast vote records parsed from CVR input files
    private final List<CastVoteRecord> castVoteRecords;
    // all candidate IDs for this contest parsed from the contest config
    private final Set<String> candidateIds;
    // contest config contains specific rules and file paths to be used during tabulation
    private final ContestConfig config;
    // roundTallies is a map from round number to a map from candidate ID to vote total for the round
    // e.g. roundTallies[1] contains a map of all candidate ID -> votes for each candidate in round 1
    // this structure is computed over the course of tabulation
    private final Map<Integer, Map<String, BigDecimal>> roundTallies = new HashMap<>();
    // precinctRoundTallies is a map from precinct to roundTallies for that precinct
    private final Map<String, Map<Integer, Map<String, BigDecimal>>> precinctRoundTallies =
        new HashMap<>();
    // candidateToRoundEliminated is a map from candidate ID to round in which they were eliminated
    private final Map<String, Integer> candidateToRoundEliminated = new HashMap<>();
    // map from candidate ID to the round in which they won
    private final Map<String, Integer> winnerToRound = new HashMap<>();
    // tracks vote transfer summaries (usable by external visualizer software)
    private final TallyTransfers tallyTransfers = new TallyTransfers();
    private final Map<String, TallyTransfers> precinctTallyTransfers = new HashMap<>();
    // tracks residual surplus from multi-seat contest vote transfers
    private final Map<Integer, BigDecimal> roundToResidualSurplus = new HashMap<>();
    // precincts which may appear in the cast vote records
    private final Set<String> precinctNames;
    // tracks the current round (and when tabulation is completed, the total number of rounds)
    private int currentRound = 0;
    // tracks required winning threshold
    private BigDecimal winningThreshold;
  
    Tabulator(List<CastVoteRecord> castVoteRecords, ContestConfig config, Set<String> precinctNames) {
      this.castVoteRecords = castVoteRecords;
      this.candidateIds = config.getCandidateCodeList();
      this.config = config;
      this.precinctNames = precinctNames;
      if (config.isTabulateByPrecinctEnabled()) {
        initPrecinctRoundTallies();
      }
    }
  
    // Utility function to "invert" the input roundTally map into a sorted map of tally
    // to List of candidate IDs. A list is used because multiple candidates may have the same tally.
    // This is used to determine when winners are selected and for running tiebreak logic.
    // param: roundTally input map of candidate ID to tally for a particular round
    // param candidatesToInclude: list of candidate IDs which may be included in the output.
    //   This filters out candidates when running a tiebreak tabulation which relies
    //   on the tied candidate's previous round totals to break the tie.
    // param: shouldLog is set to log to console and log file
    static SortedMap<BigDecimal, LinkedList<String>> buildTallyToCandidates(
        Map<String, BigDecimal> roundTally, Set<String> candidatesToInclude, boolean shouldLog) {
      SortedMap<BigDecimal, LinkedList<String>> tallyToCandidates = new TreeMap<>();
      // for each candidate record their vote total into the countToCandidates object
      for (String candidate : candidatesToInclude) {
        BigDecimal votes = roundTally.get(candidate);
        if (shouldLog) {
          Logger.info("Candidate \"%s\" got %s vote(s).", candidate, votes);
        }
        LinkedList<String> candidates =
            tallyToCandidates.computeIfAbsent(votes, k -> new LinkedList<>());
        candidates.add(candidate);
      }
      return tallyToCandidates;
    }
  
    // run the main tabulation routine to determine contest results
    // returns: set containing winner(s)
    Set<String> tabulate() throws TabulationCancelledException {
      if (config.needsRandomSeed()) {
        Random random = new Random(config.getRandomSeed());
        if (config.getTiebreakMode() == TiebreakMode.GENERATE_PERMUTATION) {
          // sort candidate permutation first for reproducibility
          Collections.sort(config.getCandidatePermutation());
          // every day I'm shuffling
          Collections.shuffle(config.getCandidatePermutation(), random);
        } else {
          Tiebreak.setRandom(random);
        }
      }
  
      logSummaryInfo();
  
      // Loop until we've found our winner(s), with a couple exceptions:
      // - If continueUntilTwoCandidatesRemain is true, we loop until only two
      // candidates remain even if we've already found our winner.
      // - If winnerElectionMode is "Bottoms-up using percentage threshold", we loop until all
      // remaining candidates have vote shares that meet or exceed that threshold.
      //
      // At each iteration, we'll either a) identify one or more
      // winners and transfer their votes to the remaining candidates (if we still need to find more
      // winners), or b) eliminate one or more candidates and gradually transfer votes to the
      // remaining candidates.
      while (shouldContinueTabulating()) {
        currentRound++;
        Logger.info("Round: %d", currentRound);
  
        // currentRoundCandidateToTally is a map of candidate ID to vote tally for the current round.
        // At each iteration of this loop that involves eliminating candidates, the eliminatedRound
        // object will gain entries.
        // Conversely, the currentRoundCandidateToTally object returned here will contain fewer
        // entries, each of which will have as many or more votes than they did in prior rounds.
        // Eventually the winner(s) will be chosen.
        Map<String, BigDecimal> currentRoundCandidateToTally = computeTalliesForRound(currentRound);
        roundTallies.put(currentRound, currentRoundCandidateToTally);
        roundToResidualSurplus.put(
            currentRound,
            currentRound == 1 ? BigDecimal.ZERO : roundToResidualSurplus.get(currentRound - 1));
  
        // The winning threshold in a standard multi-seat contest is based on the number of active
        // votes in the first round.
        // In a single-seat contest or in the special multi-seat bottoms-up threshold mode, it's based
        // on the number of active votes in the current round.
        if (currentRound == 1 || config.getNumberOfWinners() <= 1) {
          setWinningThreshold(currentRoundCandidateToTally);
        }
  
        // "invert" map and look for winners
        SortedMap<BigDecimal, LinkedList<String>> currentRoundTallyToCandidates =
            buildTallyToCandidates(
                currentRoundCandidateToTally, currentRoundCandidateToTally.keySet(), true);
        List<String> winners =
            identifyWinners(currentRoundCandidateToTally, currentRoundTallyToCandidates);
  
        if (winners.size() > 0) {
          for (String winner : winners) {
            winnerToRound.put(winner, currentRound);
          }
          // In multi-seat contests, we always redistribute the surplus (if any) unless bottoms-up
          // is enabled.
          if (config.getNumberOfWinners() > 1 && !config.isMultiSeatBottomsUpUntilNWinnersEnabled()) {
            for (String winner : winners) {
              BigDecimal candidateVotes = currentRoundCandidateToTally.get(winner);
              // number that were surplus (beyond the required threshold)
              BigDecimal extraVotes = candidateVotes.subtract(winningThreshold);
              // fractional transfer percentage
              BigDecimal surplusFraction =
                  extraVotes.signum() == 1
                      ? config.divide(extraVotes, candidateVotes)
                      : BigDecimal.ZERO;
              Logger.info(
                  "Candidate \"%s\" was elected with a surplus fraction of %s.",
                  winner, surplusFraction);
              for (CastVoteRecord cvr : castVoteRecords) {
                if (winner.equals(cvr.getCurrentRecipientOfVote())) {
                  cvr.recordCurrentRecipientAsWinner(surplusFraction, config);
                }
              }
            }
          }
        } else if (winnerToRound.size() < config.getNumberOfWinners()
            || (config.isContinueUntilTwoCandidatesRemainEnabled()
            && candidateToRoundEliminated.size() < config.getNumCandidates() - 2)
            || config.isMultiSeatBottomsUpWithThresholdEnabled()) {
          // We need to make more eliminations if
          // a) we haven't found all the winners yet, or
          // b) we've found our winner, but we're continuing until we have only two candidates
          // c) not all remaining candidates meet the bottoms-up threshold
  
          List<String> eliminated;
          // Four mutually exclusive ways to eliminate candidates.
          // 1. Some races contain undeclared write-ins that should be dropped immediately.
          eliminated = dropUndeclaredWriteIns(currentRoundCandidateToTally);
          // 2. If there's a minimum vote threshold, drop all candidates below that threshold.
          if (eliminated.isEmpty()) {
            eliminated = dropCandidatesBelowThreshold(currentRoundTallyToCandidates);
          }
          // 3. Otherwise, try batch elimination.
          if (eliminated.isEmpty()) {
            eliminated = doBatchElimination(currentRoundTallyToCandidates);
          }
          // 4. If we didn't do batch elimination, eliminate the remaining candidate with the lowest
          //    tally, breaking a tie if needed.
          if (eliminated.isEmpty()) {
            eliminated = doRegularElimination(currentRoundTallyToCandidates);
          }
  
          assert !eliminated.isEmpty();
          for (String loser : eliminated) {
            candidateToRoundEliminated.put(loser, currentRound);
          }
        }
  
        if (config.getNumberOfWinners() > 1) {
          updatePastWinnerTallies();
        }
      }
      return winnerToRound.keySet();
    }
  
    // log some basic info about the contest before starting tabulation
    private void logSummaryInfo() {
      Logger.info(
          "There are %d declared candidates for this contest:", config.getNumDeclaredCandidates());
      for (String candidate : candidateIds) {
        if (!candidate.equals(UNDECLARED_WRITE_IN_OUTPUT_LABEL)) {
          Logger.info(
              "%s%s",
              candidate, config.candidateIsExcluded(candidate) ? " (excluded from tabulation)" : "");
        }
      }
  
      if (config.getTiebreakMode() == TiebreakMode.GENERATE_PERMUTATION) {
        Logger.info("Randomly generated candidate permutation for tie-breaking:");
        for (String candidateId : config.getCandidatePermutation()) {
          Logger.info("%s", candidateId);
        }
      }
    }
  
    // function: updateWinnerTallies
    // purpose: Update the tally for the just-completed round to reflect the tallies for candidates
    // who won in a past round (in a multi-winner contest). We do this because the regular tally
    // logic only accumulates votes for continuing candidates (not past winners).
    // We do this computation once for each previous round winner to account for transfers. In
    // subsequent rounds, we can just copy the number from the previous round, since it won't change.
    private void updatePastWinnerTallies() {
      Map<String, BigDecimal> roundTally = roundTallies.get(currentRound);
      Map<String, BigDecimal> previousRoundTally = roundTallies.get(currentRound - 1);
      List<String> winnersToProcess = new LinkedList<>();
      Set<String> winnersRequiringComputation = new HashSet<>();
      for (String winner : winnerToRound.keySet()) {
        // skip someone who won in the current round (we only care about previous round winners)
        int winningRound = winnerToRound.get(winner);
        if (winningRound == currentRound) {
          continue;
        }
        winnersToProcess.add(winner);
        if (winningRound == currentRound - 1) {
          winnersRequiringComputation.add(winner);
        }
      }
  
      // initialize or populate overall tally
      for (String winner : winnersToProcess) {
        roundTally.put(
            winner,
            winnersRequiringComputation.contains(winner)
                ? BigDecimal.ZERO
                : previousRoundTally.get(winner));
      }
  
      // initialize or populate precinct tallies
      if (config.isTabulateByPrecinctEnabled()) {
        for (String precinct : precinctRoundTallies.keySet()) {
          // this is all the tallies for the given precinct
          Map<Integer, Map<String, BigDecimal>> roundTalliesForPrecinct =
              precinctRoundTallies.get(precinct);
          // and this is the tally for the current round for the precinct
          Map<String, BigDecimal> roundTallyForPrecinct = roundTalliesForPrecinct.get(currentRound);
          for (String winner : winnersToProcess) {
            roundTallyForPrecinct.put(
                winner,
                winnersRequiringComputation.contains(winner)
                    ? BigDecimal.ZERO
                    : roundTalliesForPrecinct.get(currentRound - 1).get(winner));
          }
        }
      }
  
      // process all the CVRs if needed (if we have any winners from the previous round to process)
      if (winnersRequiringComputation.size() > 0) {
        for (CastVoteRecord cvr : castVoteRecords) {
          // the record of winners who got partial votes from this CVR
          Map<String, BigDecimal> winnerToFractionalValue = cvr.getWinnerToFractionalValue();
          for (String winner : winnerToFractionalValue.keySet()) {
            if (!winnersRequiringComputation.contains(winner)) {
              continue;
            }
            BigDecimal fractionalTransferValue = winnerToFractionalValue.get(winner);
  
            incrementTally(roundTally, fractionalTransferValue, winner);
            if (config.isTabulateByPrecinctEnabled() && cvr.getPrecinct() != null) {
              incrementTally(
                  precinctRoundTallies.get(cvr.getPrecinct()).get(currentRound),
                  fractionalTransferValue,
                  winner);
            }
          }
        }
  
        // We need to handle residual surplus (fractional surplus that can't be transferred due to
        // rounding).
        // For each winner from the previous round, record the residual surplus and then update
        // the winner's new total to be exactly the winning threshold value.
        for (String winner : winnersRequiringComputation) {
          BigDecimal winnerTally = roundTally.get(winner);
          BigDecimal winnerResidual = winnerTally.subtract(winningThreshold);
          if (winnerResidual.signum() == 1) {
            Logger.info("%s had residual surplus of %s.", winner, winnerResidual);
            roundToResidualSurplus.put(
                currentRound, roundToResidualSurplus.get(currentRound).add(winnerResidual));
            roundTally.put(winner, winningThreshold);
            tallyTransfers.addTransfer(
                currentRound, winner, TallyTransfers.RESIDUAL_TARGET, winnerResidual);
          }
        }
      }
    }
  
    // determine and store the threshold to win
    private void setWinningThreshold(Map<String, BigDecimal> currentRoundCandidateToTally) {
      BigDecimal currentRoundTotalVotes = BigDecimal.ZERO;
      for (BigDecimal numVotes : currentRoundCandidateToTally.values()) {
        currentRoundTotalVotes = currentRoundTotalVotes.add(numVotes);
      }
  
      if (config.isMultiSeatBottomsUpWithThresholdEnabled()) {
        winningThreshold =
            currentRoundTotalVotes.multiply(config.getMultiSeatBottomsUpPercentageThreshold());
      } else {
        // divisor for threshold is num winners + 1 (unless archaic Hare quota option is enabled, in
        // which case it's just num winners)
        BigDecimal divisor =
            new BigDecimal(
                config.isHareQuotaEnabled()
                    ? config.getNumberOfWinners()
                    : config.getNumberOfWinners() + 1);
        if (config.isNonIntegerWinningThresholdEnabled()) {
          // threshold = (votes / (num_winners + 1)) + 10^(-1 * decimalPlacesForVoteArithmetic)
          BigDecimal augend =
              config.divide(
                  BigDecimal.ONE, BigDecimal.TEN.pow(config.getDecimalPlacesForVoteArithmetic()));
          winningThreshold = config.divide(currentRoundTotalVotes, divisor).add(augend);
        } else {
          // threshold = floor(votes / (num_winners + 1)) + 1
          winningThreshold =
              currentRoundTotalVotes.divideToIntegralValue(divisor).add(BigDecimal.ONE);
        }
      }
      Logger.info("Winning threshold set to %s.", winningThreshold);
    }
  
    // determine if we should continue tabulating based on how many winners have been
    // selected and if continueUntilTwoCandidatesRemain is true.
    private boolean shouldContinueTabulating() {
      int numEliminatedCandidates = candidateToRoundEliminated.keySet().size();
      int numWinnersDeclared = winnerToRound.size();
      // apply config setting if specified
      if (config.isContinueUntilTwoCandidatesRemainEnabled()) {
        // Keep going if there are more than two candidates alive. Also make sure we tabulate one last
        // round after we've made our final elimination.
        return numEliminatedCandidates + numWinnersDeclared + 1 < config.getNumCandidates()
            || candidateToRoundEliminated.containsValue(currentRound);
      } else if (config.isMultiSeatBottomsUpWithThresholdEnabled()) {
        // in this mode, we're done as soon as we've declared any winners
        return numWinnersDeclared == 0;
      } else {
        // If there are more seats to fill, we should keep going, of course.
        // But also: if we've selected all the winners in a multi-seat contest, we should tabulate one
        // extra round in order to show the effect of redistributing the final surpluses... unless
        // bottoms-up is enabled, in which case we can stop as soon as we've declared the winners.
        return numWinnersDeclared < config.getNumberOfWinners()
            || (config.getNumberOfWinners() > 1
            && winnerToRound.containsValue(currentRound)
            && !config.isMultiSeatBottomsUpUntilNWinnersEnabled());
      }
    }
  
    // This handles continued tabulation after a winner has been chosen when
    // continueUntilTwoCandidatesRemain is true.
    private boolean isCandidateContinuing(String candidate) {
      CandidateStatus status = getCandidateStatus(candidate);
      return status == CandidateStatus.CONTINUING
          || (status == CandidateStatus.WINNER && config.isContinueUntilTwoCandidatesRemainEnabled());
    }
  
    // returns candidate status (continuing, eliminated or winner)
    private CandidateStatus getCandidateStatus(String candidate) {
      CandidateStatus status = CandidateStatus.CONTINUING;
      if (config.candidateIsExcluded(candidate)) {
        status = CandidateStatus.EXCLUDED;
      } else if (winnerToRound.containsKey(candidate)) {
        status = CandidateStatus.WINNER;
      } else if (candidateToRoundEliminated.containsKey(candidate)) {
        status = CandidateStatus.ELIMINATED;
      } else if (candidate.equals(EXPLICIT_OVERVOTE_LABEL)) {
        status = CandidateStatus.INVALID;
      }
      return status;
    }
  
    // determine if one or more winners have been identified in this round
    // param: currentRoundCandidateToTally map of candidate ID to their tally in a particular round
    // param: currentRoundTallyToCandidates map of tally to candidate ID(s) for a particular round
    // return: list of winning candidates in this round (if any)
    private List<String> identifyWinners(
        Map<String, BigDecimal> currentRoundCandidateToTally,
        SortedMap<BigDecimal, LinkedList<String>> currentRoundTallyToCandidates)
        throws TabulationCancelledException {
      List<String> selectedWinners = new LinkedList<>();
  
      if (config.isMultiSeatBottomsUpWithThresholdEnabled()) {
        // if everyone meets the threshold, select them all as winners
        boolean allMeet = true;
        for (BigDecimal tally : currentRoundCandidateToTally.values()) {
          if (tally.compareTo(winningThreshold) < 0) {
            allMeet = false;
            break;
          }
        }
        if (allMeet) {
          selectedWinners.addAll(currentRoundCandidateToTally.keySet());
        }
      } else {
        // We should only look for more winners if we haven't already filled all the seats.
        if (winnerToRound.size() < config.getNumberOfWinners()) {
          // If the number of continuing candidates equals the number of seats to fill, everyone wins.
          if (currentRoundCandidateToTally.size()
              == config.getNumberOfWinners() - winnerToRound.size()) {
            selectedWinners.addAll(currentRoundCandidateToTally.keySet());
          } else if (!config.isMultiSeatBottomsUpUntilNWinnersEnabled()) {
            // We see if anyone has met/exceeded the threshold (unless bottoms-up is enabled, in which
            // case we just wait until there are numWinners candidates remaining and then declare all
            // of them as winners simultaneously).
            // tally indexes over all tallies to find any winners
            for (BigDecimal tally : currentRoundTallyToCandidates.keySet()) {
              if (tally.compareTo(winningThreshold) >= 0) {
                // we have winner(s)
                List<String> winningCandidates = currentRoundTallyToCandidates.get(tally);
                for (String candidate : winningCandidates) {
                  // The undeclared write-in placeholder can't win!
                  if (!candidate.equals(UNDECLARED_WRITE_IN_OUTPUT_LABEL)) {
                    selectedWinners.add(candidate);
                  }
                }
              }
            }
          }
        }
  
        // Edge case: if we've identified multiple winners in this round but we're only supposed to
        // elect one winner per round, pick the top vote-getter and defer the others to subsequent
        // rounds.
        if (config.isMultiSeatAllowOnlyOneWinnerPerRoundEnabled() && selectedWinners.size() > 1) {
          // currentRoundTallyToCandidates is sorted from low to high, so just look at the last key
          BigDecimal maxVotes = currentRoundTallyToCandidates.lastKey();
          selectedWinners = currentRoundTallyToCandidates.get(maxVotes);
          // But if there are multiple candidates tied for the max tally, we need to break the tie.
          if (selectedWinners.size() > 1) {
            Tiebreak tiebreak =
                new Tiebreak(
                    true,
                    selectedWinners,
                    config.getTiebreakMode(),
                    currentRound,
                    maxVotes,
                    roundTallies,
                    config.getCandidatePermutation());
  