// -*-c++-*-
// $Id: RankedOrderDetails.cc 488 2008-04-10 20:37:22Z dflater $

#include "Types.hh"
#include "Exceptions.hh"
#include "BorderLogic.hh"
#include <algorithm>


void reportTallies (const TallyVector &tallies,
		    const ChoiceDescriptionMap &choices);


// StrictWeakOrdering to sort tallies into descending order.
static bool tallyGreaterThan (const Tally &i,
			      const Tally &j) {
  return i.tally > j.tally;
}


// stuck is set to true if at least one ballot has been "exhausted."
// Otherwise, tallies_out is valid and is sorted into descending order.
static void calculateRankedOrderTallies (const ScaledROVoteMap &votes,
					 const ChoiceDescriptionMap &choices,
					 bool &stuck,
					 TallyVector &tallies_out) {
  tallies_out.clear();

  // Initialize tallies for all available choices.
  std::map<const choiceId_t, tally_t> tallies;
  for (ChoiceDescriptionMap::const_iterator it = choices.begin();
       it != choices.end();
       ++it)
    tallies[it->first] = 0;

  // Count votes.
  for (ScaledROVoteMap::const_iterator it = votes.begin();
       it != votes.end();
       ++it) {
    if (it->second.vote.empty()) {
      stuck = true;
      return;
    }
    tallies[it->second.vote.front()] += it->second.scale;
  }

  // Copy to vector and resort by descending tally.
  for (std::map<const choiceId_t, tally_t>::iterator it = tallies.begin();
       it != tallies.end();
       ++it)
    tallies_out.push_back ((Tally) {it->first, it->second});
  std::sort (tallies_out.begin(), tallies_out.end(), tallyGreaterThan);
}


// Find winners and losers and ties.  Tallies are assumed to be already
// sorted into descending order.
static void minAndMaxTally (const TallyVector &tallies,
			    Tally &max_out,
			    Tally &min_out,
			    bool &max_tied_out,
			    bool &min_tied_out) {
  const TallyVector::size_type s (tallies.size());
  if (s < 1)
    throw NoTallies();
  max_out = tallies[0];
  min_out = tallies[s-1];
  if (s == 1)
    max_tied_out = min_tied_out = false;
  else {
    max_tied_out = (max_out.tally == tallies[1].tally);
    min_tied_out = (min_out.tally == tallies[s-2].tally);
  }
}


// The effective quota is the Hagenbach-Bischoff quota plus epsilon
// (an arbitrarily small positive quantity).
static tally_t hagenbachBischoffQuota (unsigned long numberOfBallotsCast,
				       unsigned long seatsToFill) {
  return (tally_t)numberOfBallotsCast / ((tally_t)seatsToFill + 1);
}


// Expunge all votes for a given choice and remove that choice from
// choiceMap.
static void eliminate (choiceId_t choiceToEliminate,
		       ScaledROVoteMap &voteMap,
		       ChoiceDescriptionMap &choiceMap) {
  for (ScaledROVoteMap::iterator it = voteMap.begin();
       it != voteMap.end();
       ++it) {
    RankedOrderVote &v (it->second.vote);
    RankedOrderVote::iterator badVote (find (v.begin(),
					     v.end(),
					     choiceToEliminate));
    if (badVote != v.end())
      v.erase (badVote);
  }
  choiceMap.erase (choiceToEliminate);
}


// Transfer surplus votes after someone is declared elected and
// eliminate that choice.
static void elect (const Tally &winner,
		   tally_t quota,
		   ScaledROVoteMap &voteMap,
		   ChoiceDescriptionMap &choiceMap) {
  if (winner.tally <= quota || quota <= 0)
    throw PreconditionViolation ("elect: winner.tally <= quota || quota <= 0");
  scale_t scaleFactor ((winner.tally - quota) / winner.tally);
  choiceId_t winnerChoice (winner.choiceId);
  for (ScaledROVoteMap::iterator it = voteMap.begin();
       it != voteMap.end();
       ++it) {
    RankedOrderVote &v (it->second.vote);
    if (v.empty())
      throw UnexpectedBallotExhaustion();
    if (v.front() == winnerChoice)
      it->second.scale *= scaleFactor;
  }
  eliminate (winnerChoice, voteMap, choiceMap);
}


void doRankedOrderContest (const ContestStruct &contest,
			   constString contextName,
			   bool verbose) {
  if (!contextName)
    throw PreconditionViolation ("doRankedOrderContest: contextName is NULL");

  std::cout << std::endl << contest.contestDescription << std::endl;

  ChoiceDescriptionMap choiceMap;
  fetchChoicesInContest (contest.contestId, choiceMap);
  ScaledROVoteMap voteMap;
  fetchRankedOrderVotes (contest.contestId, contextName, voteMap);

  long seatsFilled (0);
  bool stuck (false);
  const long N (contest.N);
  const tally_t quota (hagenbachBischoffQuota (voteMap.size(), N));

  // std::cout << "Trying to elect " << N << " choices.\n";
  std::cout << "Have " << voteMap.size() << " valid votes.\n";
  std::cout << "Quota is " << quota << " plus epsilon.\n";

  for (unsigned long round (1); seatsFilled < N && !stuck; ++round) {
    if (verbose)
      std::cout << "Current state:\n" << voteMap;

    long surplusChoices (choiceMap.size() - N + seatsFilled);
    if (surplusChoices < 0) {
      std::cout << "Stuck:  Not enough choices.\n";
      stuck = true;
    } else if (surplusChoices == 0) {
      std::cout << "All remaining choices are elected.\n";
      seatsFilled = N;
    } else {
      TallyVector tallies;
      calculateRankedOrderTallies (voteMap, choiceMap, stuck, tallies);
      if (!stuck) {
	std::cout << "Round " << round << " tallies:\n";
	reportTallies (tallies, choiceMap);

	Tally winner, loser;
	bool tiedWinner, tiedLoser;
	minAndMaxTally (tallies, winner, loser, tiedWinner, tiedLoser);

	if (winner.tally > quota) {
	  if (tiedWinner) {
	    std::cout << "Stuck:  Tie among potential winners."
		      << std::endl;
	    stuck = true;
	  } else {
	    std::cout << choiceMap[winner.choiceId]
		      << " is elected.\n";
	    elect (winner, quota, voteMap, choiceMap);
	    ++seatsFilled;
	  }
	} else {
	  if (tiedLoser) {
	    std::cout << "Stuck:  Tie among candidates for elimination."
		      << std::endl;
	    stuck = true;
	  } else {
	    std::cout << choiceMap[loser.choiceId]
		      << " is eliminated.\n";
	    eliminate (loser.choiceId, voteMap, choiceMap);
	  }
	}
      } else
	std::cout << "Stuck:  Ballot exhausted.\n";
    }
  }
  if (verbose)
    std::cout << "End state:\n" << voteMap;
}
