Author: tchemit Date: 2012-06-26 08:54:58 +0200 (Tue, 26 Jun 2012) New Revision: 3566 Url: http://chorem.org/repositories/revision/pollen/3566 Log: refs #541 fix algorithm Modified: trunk/pollen-votecounting-strategy-instant-runoff/src/main/java/org/chorem/pollen/votecounting/strategy/InstantRunoffStrategy.java Modified: trunk/pollen-votecounting-strategy-instant-runoff/src/main/java/org/chorem/pollen/votecounting/strategy/InstantRunoffStrategy.java =================================================================== --- trunk/pollen-votecounting-strategy-instant-runoff/src/main/java/org/chorem/pollen/votecounting/strategy/InstantRunoffStrategy.java 2012-06-26 05:03:04 UTC (rev 3565) +++ trunk/pollen-votecounting-strategy-instant-runoff/src/main/java/org/chorem/pollen/votecounting/strategy/InstantRunoffStrategy.java 2012-06-26 06:54:58 UTC (rev 3566) @@ -23,19 +23,16 @@ package org.chorem.pollen.votecounting.strategy; import com.google.common.collect.Lists; -import com.google.common.collect.Maps; import com.google.common.collect.Sets; +import org.apache.commons.collections.CollectionUtils; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; import org.chorem.pollen.votecounting.model.ChoiceScore; import org.chorem.pollen.votecounting.model.ChoiceToVoteRenderType; import org.chorem.pollen.votecounting.model.VoteCountingResult; -import org.chorem.pollen.votecounting.model.VoteForChoice; import org.chorem.pollen.votecounting.model.Voter; -import java.math.BigDecimal; import java.util.Collections; -import java.util.Comparator; import java.util.Iterator; import java.util.List; import java.util.Map; @@ -52,13 +49,12 @@ */ public class InstantRunoffStrategy extends AbstractVoteCountingStrategy { - public static final int ID = 6; + public static final int ID = 5; /** Logger. */ private static final Log log = LogFactory.getLog(InstantRunoffStrategy.class); - public static final BigDecimal ZERO_D = BigDecimal.valueOf(0.); @Override public int getId() { @@ -128,140 +124,160 @@ // get empty result by choice SortedMap<String, ChoiceScore> resultByChoice = votersToResult(voters); - // nb of choices - int nbChoices = resultByChoice.keySet().size(); - - // calcul pour chaque votant de ses choix préférés - Map<Voter, Set<String>> topRankChoices = buildVoterTopRank(voters); - - // ajout des poids pondérés pour chaque vainqueur - for (Map.Entry<Voter, Set<String>> entry : topRankChoices.entrySet()) { - Voter voter = entry.getKey(); - Set<String> ids = entry.getValue(); - double voterWeight = voter.getWeight(); - for (String id : ids) { - ChoiceScore choiceScore = resultByChoice.get(id); - choiceScore.addScoreValue(voterWeight); - } - } - - // calcul de la valeur pour atteindre la majorité absolue + // calcul du score minimum pour atteindre la majorité absolue double totalWeight = 0.; for (Voter voter : voters) { totalWeight += voter.getWeight(); } totalWeight /= 2; - // recopy choices to run rounds on it and eliminates choices until - // there is a choice > 50 - List<ChoiceScore> results = Lists.newArrayList(resultByChoice.values()); + // calcul pour chaque votant de ses choix préférés + Map<Voter, List<Set<String>>> topRankChoices = + buildVoterSortedChoices(voters); - // trie des scores - Collections.sort(results); + Set<String> choiceIdsToExclude = Sets.newHashSet(); + Set<String> choiceIdsToKeep = Sets.newHashSet(resultByChoice.keySet()); - // on supprime tout score à 0 - Iterator<ChoiceScore> itr = results.iterator(); - while (itr.hasNext()) { - ChoiceScore choiceScore = itr.next(); - if (choiceScore.getScoreValue() == null || - ZERO_D.equals(choiceScore.getScoreValue())) { - itr.remove(); - } else { - // score > 0 on peut s'arreter - break; - } - } + round(topRankChoices, + choiceIdsToExclude, + choiceIdsToKeep, + resultByChoice, + totalWeight); - // compute - computeWinner(results, totalWeight); - - // transform map of result to list of them (and sort them) VoteCountingResult result = resultToList(resultByChoice); return result; } - public void computeWinner(List<ChoiceScore> results, double totalWeight) { + public void round(Map<Voter, List<Set<String>>> topRankChoices, + Set<String> idsToExclude, + Set<String> idsToInclude, + SortedMap<String, ChoiceScore> resultByChoice, + double totalWeight) { - ChoiceScore bestChoice = results.get(results.size() - 1); + List<ChoiceScore> results = applyScores(topRankChoices, + idsToExclude, + idsToInclude, + resultByChoice); - double max = bestChoice.getScoreValue().doubleValue(); + if (!results.isEmpty()) { - if (max >= totalWeight) { + // get best score + double max = + results.get(results.size() - 1).getScoreValue().doubleValue(); - // on a trouvé une majorité absolue - return; - } + if (max < totalWeight) { - // pas de majorité absolue, on prend le plus petit score - double min = results.get(0).getScoreValue().doubleValue(); - double scoreToAdd = 0; - // on supprimme tout les score à min - Iterator<ChoiceScore> itr = results.iterator(); - while (itr.hasNext()) { - ChoiceScore choiceScore = itr.next(); - if (min == choiceScore.getScoreValue().doubleValue()) { - //FIXME-tchemit-2012-06-25 : voir si on doit supprimer cette valeur ? - //choiceScore.setScoreValue(ZERO_D); - itr.remove(); - scoreToAdd += min; + // pas de majorité absolue, il faut éliminer le(s) choix les plus mauvais + + guessChoiceIdsToRemove(idsToExclude, results); + + + // on ne veux plus utiliser ces choix dans le tour suivant + idsToInclude.removeAll(idsToExclude); + + // nouveau tour + round(topRankChoices, + idsToExclude, + idsToInclude, + resultByChoice, + totalWeight); + } else { - // score > min on peut s'arreter - break; + + // majorité absolue trouvée plus rien à faire en fait :) } } + } - if (!results.isEmpty()) { + public List<ChoiceScore> applyScores(Map<Voter, List<Set<String>>> topRankChoices, + Set<String> idsToExclude, + Set<String> idsToInclude, + SortedMap<String, ChoiceScore> resultByChoice) { - // on ajoute scoreToAdd au premier score - results.get(0).addScoreValue(scoreToAdd); + if (CollectionUtils.isNotEmpty(idsToExclude)) { - // trie des scores - Collections.sort(results); + // on supprime des classements les ids données - // redo a round - computeWinner(results, totalWeight); + for (List<Set<String>> choicesByLevel : topRankChoices.values()) { + Iterator<Set<String>> itr = choicesByLevel.iterator(); + while (itr.hasNext()) { + Set<String> choiceIds = itr.next(); + choiceIds.removeAll(idsToExclude); + if (choiceIds.isEmpty()) { + + // remove this level + itr.remove(); + } + } + } } - } - public Map<Voter, Set<String>> buildVoterTopRank(Set<Voter> voters) { + // on remet à zero les scores pour les ids a conserver + for (String id : idsToInclude) { + resultByChoice.get(id).setScoreValue(null); + } - VoteForChoiceComparator comparator = new VoteForChoiceComparator(); + // on calcule les scores à partir des classements - Map<Voter, Set<String>> result = Maps.newHashMap(); + for (Map.Entry<Voter, List<Set<String>>> entry : topRankChoices.entrySet()) { + List<Set<String>> idsByLevel = entry.getValue(); + if (!idsByLevel.isEmpty()) { - for (Voter voter : voters) { + Set<String> winnerIds = idsByLevel.get(0); + Voter voter = entry.getKey(); + double voterWeight = voter.getWeight(); + for (String id : winnerIds) { + if (idsToInclude.contains(id)) { + ChoiceScore choiceScore = resultByChoice.get(id); + choiceScore.addScoreValue(voterWeight); + } + } + } + } - Set<String> topChoices = getTopRank( - voter.getVoteForChoices(), comparator); - result.put(voter, topChoices); + // recopy choices to run rounds on it and eliminates choices until + // there is a choice > 50 + List<ChoiceScore> results = Lists.newArrayList(); + + for (String id : idsToInclude) { + results.add(resultByChoice.get(id)); } - return result; + + Collections.sort(results); + + // on supprime tout score à 0 + Iterator<ChoiceScore> itr = results.iterator(); + while (itr.hasNext()) { + ChoiceScore choiceScore = itr.next(); + if (choiceScore.getScoreValue() == null || + ZERO_D.equals(choiceScore.getScoreValue())) { + itr.remove(); + } else { + // score > 0 on peut s'arreter + break; + } + } + return results; } - public Set<String> getTopRank(Set<VoteForChoice> voteForChoices, - Comparator<VoteForChoice> comparator) { - // get sort vote for choices - List<VoteForChoice> sortedChoices = Lists.newArrayList(voteForChoices); - Collections.sort(sortedChoices, comparator); + public void guessChoiceIdsToRemove(Set<String> idsToExclude, + List<ChoiceScore> results) { - // build top rank + double min = results.get(0).getScoreValue().doubleValue(); - Set<String> result = Sets.newHashSet(); - VoteForChoice lastVoteForChoice = null; - for (VoteForChoice voteForChoice : sortedChoices) { - if (lastVoteForChoice != null && - comparator.compare(lastVoteForChoice, voteForChoice) != 0) { + idsToExclude.clear(); - // new rank found - // skip other values + for (ChoiceScore choiceScore : results) { + + if (min == choiceScore.getScoreValue().doubleValue()) { + + idsToExclude.add(choiceScore.getChoiceId()); + } else { + // value > min, on peut s'arreter là break; } - - result.add(voteForChoice.getChoiceId()); - lastVoteForChoice = voteForChoice; } - return result; } }