Author: tchemit Date: 2012-06-26 00:51:43 +0200 (Tue, 26 Jun 2012) New Revision: 3557 Url: http://chorem.org/repositories/revision/pollen/3557 Log: refs #590 : finish implementation of condorcet strategy Modified: trunk/pollen-votecounting-strategy-condorcet/pom.xml trunk/pollen-votecounting-strategy-condorcet/src/main/java/org/chorem/pollen/votecounting/CondorcetStrategy.java trunk/pollen-votecounting-strategy-condorcet/src/test/java/org/chorem/pollen/votecounting/CondorcetStrategyTest.java Modified: trunk/pollen-votecounting-strategy-condorcet/pom.xml =================================================================== --- trunk/pollen-votecounting-strategy-condorcet/pom.xml 2012-06-25 17:56:45 UTC (rev 3556) +++ trunk/pollen-votecounting-strategy-condorcet/pom.xml 2012-06-25 22:51:43 UTC (rev 3557) @@ -38,6 +38,10 @@ <artifactId>nuiton-i18n</artifactId> </dependency> <dependency> + <groupId>org.nuiton</groupId> + <artifactId>nuiton-utils</artifactId> + </dependency> + <dependency> <groupId>org.slf4j</groupId> <artifactId>slf4j-log4j12</artifactId> <scope>test</scope> Modified: trunk/pollen-votecounting-strategy-condorcet/src/main/java/org/chorem/pollen/votecounting/CondorcetStrategy.java =================================================================== --- trunk/pollen-votecounting-strategy-condorcet/src/main/java/org/chorem/pollen/votecounting/CondorcetStrategy.java 2012-06-25 17:56:45 UTC (rev 3556) +++ trunk/pollen-votecounting-strategy-condorcet/src/main/java/org/chorem/pollen/votecounting/CondorcetStrategy.java 2012-06-25 22:51:43 UTC (rev 3557) @@ -22,12 +22,22 @@ */ package org.chorem.pollen.votecounting; -import com.google.common.base.Preconditions; +import com.google.common.collect.Lists; +import com.google.common.collect.Maps; +import com.google.common.collect.Sets; +import org.apache.commons.logging.Log; +import org.apache.commons.logging.LogFactory; +import org.chorem.pollen.votecounting.model.ChoiceIdAble; import org.chorem.pollen.votecounting.model.ChoiceScore; import org.chorem.pollen.votecounting.model.VoteCountingResult; import org.chorem.pollen.votecounting.model.VoteForChoice; import org.chorem.pollen.votecounting.model.Voter; +import java.io.Serializable; +import java.math.BigDecimal; +import java.util.Arrays; +import java.util.Comparator; +import java.util.List; import java.util.Map; import java.util.Set; @@ -43,6 +53,9 @@ public static final int ID = 2; + /** Logger. */ + private static final Log log = LogFactory.getLog(CondorcetStrategy.class); + @Override public int getId() { return ID; @@ -59,18 +72,14 @@ } @Override - public VoteCountingResult votecount(Set<Voter> voters) { + public String getTotalVoteValueNotValidMessage() { + // no validation on total value, so no message + return null; + } - // get empty result by choice - Map<String, ChoiceScore> resultByChoice = votersToResult(voters); - - for (Voter voter : voters) { - // add this voter votes to result - addVoterChoices(voter, resultByChoice); - } - // transform map of result to list of them (and sort them) - VoteCountingResult result = resultToList(null, resultByChoice); - return result; + @Override + public String getVoteValueNotValidMessage() { + return n_("pollen.error.vote.invalidCondorcetVoteValue"); } @Override @@ -79,6 +88,11 @@ } @Override + public ChoiceToVoteRenderType getRenderType() { + return ChoiceToVoteRenderType.TEXTFIELD; + } + + @Override public boolean isChoiceInVote(Integer voteValue) { return voteValue != null && voteValue > 0 && voteValue < 100; } @@ -89,11 +103,6 @@ } @Override - public ChoiceToVoteRenderType getRenderType() { - return ChoiceToVoteRenderType.TEXTFIELD; - } - - @Override public boolean isDisplayResultsByChoice() { return false; } @@ -110,62 +119,213 @@ } @Override - public String getTotalVoteValueNotValidMessage() { - // no validation on total value, so no message - return null; - } + public VoteCountingResult votecount(Set<Voter> voters) { - @Override - public String getVoteValueNotValidMessage() { - return n_("pollen.error.vote.invalidCondorcetVoteValue"); - } + // get empty result by choice + Map<String, ChoiceScore> resultByChoice = votersToResult(voters); - public void addVoterChoices(Voter voter, - Map<String, ChoiceScore> resultByChoice) { + // get order over choices (needed to get coordinates over matrix) + List<String> choiceIds = Lists.newArrayList(resultByChoice.keySet()); - double voterWeight = voter.getWeight(); + // nb of choices + int nbChoices = choiceIds.size(); - Set<VoteForChoice> voteForChoices = voter.getVoteForChoices(); + //matrix of pairwise + double[][] matrix = new double[nbChoices][nbChoices]; - for (VoteForChoice voteForChoice : voteForChoices) { + // compute pairwise battle matrix and try to have a direct winner(s) + Set<String> winners = computePairWiseMatrix(choiceIds, voters, matrix); - Double voteValue = voteForChoice.getVoteValue(); + // compute nb battles wins for each choice + // and store it as choice score value + computeNbBattlesByChoice(resultByChoice, choiceIds, matrix); - if (voteValue != null) { + // get choice score ordered by their number of win battles + List<ChoiceScore> choiceScores = toChoiceScore(resultByChoice); - // get nb victories for this choice among voter choices - int victories = getVictories(voteForChoice, voteForChoices); + if (winners != null) { - // get score for choice - String choiceId = voteForChoice.getChoiceId(); + // there is winner(s), re-add them to + + if (log.isDebugEnabled()) { + log.debug("Direct winners : " + winners); + } + for (String choiceId : winners) { ChoiceScore choiceScore = resultByChoice.get(choiceId); + choiceScores.remove(choiceScore); + choiceScores.add(0, choiceScore); + } + } else { - // compute score to add - double scoreToAdd = (double) victories * voterWeight; + // no direct winner, must resolv conflicts - // add to score this weighted vote - choiceScore.addScoreValue(scoreToAdd); + resolvConflicts(choiceScores, matrix); + } + + // transform map of result to list of them (and sort them) + VoteCountingResult result = resultToList(null, resultByChoice); + return result; + } + + protected void resolvConflicts(List<ChoiceScore> choiceScores, + double[][] matrix) { + + // for the moment we use only number of win battles + // so nothing more to do here... + } + + protected void computeNbBattlesByChoice(Map<String, ChoiceScore> resultByChoice, + List<String> choiceIds, + double[][] matrix) { + + int nbChoices = choiceIds.size(); + + for (String choiceId : choiceIds) { + + int i = choiceIds.indexOf(choiceId); + + double nbBattles = 0; + for (int j = 0; j < nbChoices; j++) { + double aRow = matrix[i][j]; + nbBattles += aRow; } + + resultByChoice.get(choiceId).setScoreValue( + BigDecimal.valueOf(nbBattles)); + + if (log.isDebugEnabled()) { + log.debug("Nb battle wins for choice " + choiceId + ": " + nbBattles); + } } } - public int getVictories(VoteForChoice voteForChoice, - Set<VoteForChoice> voteForChoices) { - int result = 0; - Preconditions.checkNotNull(voteForChoice); - Double refValue = voteForChoice.getVoteValue(); - Preconditions.checkNotNull(refValue); - String currentCHoiceId = voteForChoice.getChoiceId(); - for (VoteForChoice forChoice : voteForChoices) { - if (!currentCHoiceId.equals(forChoice.getChoiceId())) { - Double voteValue = forChoice.getVoteValue(); - if (voteValue == null || refValue < voteValue) { + private Set<String> computePairWiseMatrix(List<String> choiceIds, + Set<Voter> voters, + double[][] matrix) { - // ref choice wins against current choice - result++; + int nbChoices = choiceIds.size(); + + Set<String> winners = null; + + VoteForChoiceComparator comparator = new VoteForChoiceComparator(); + + double[] currentVoteWinner = new double[choiceIds.size()]; + + boolean firstVoter = true; + for (Voter voter : voters) { + + if (log.isDebugEnabled()) { + log.debug("Start count for voter " + voter.getVoterId()); + } + double voterWeight = voter.getWeight(); + + Arrays.fill(currentVoteWinner, 0); + + Map<String, VoteForChoice> voteByChoiceIds = + Maps.uniqueIndex(voter.getVoteForChoices(), + new ChoiceIdAble.ChoiceIdAbleById()); + + double maxBattleWins = 0; + + for (String choiceId : choiceIds) { + + // get vote for this choice + VoteForChoice voteForChoice = voteByChoiceIds.get(choiceId); + + int x = choiceIds.indexOf(choiceId); + + for (VoteForChoice voteForChoice1 : voter.getVoteForChoices()) { + + String choiceId1 = voteForChoice1.getChoiceId(); + if (choiceId.equals(choiceId1)) { + + // can not battle same choice + continue; + } + + int y = choiceIds.indexOf(choiceId1); + + int compare = comparator.compare(voteForChoice, + voteForChoice1); + + if (compare > 0) { + + // voteForChoice wins his battle + + int pos = x * nbChoices + y; + + matrix[x][y] = matrix[x][y] + voterWeight; + if (log.isTraceEnabled()) { + log.trace("battle [" + choiceId + "<" + + voteForChoice.getVoteValue() + "> - " + + choiceId1 + "<" + + voteForChoice1.getVoteValue() + + ">] wins (store to " + pos + + ", new value=" + matrix[x][y] + ")"); + } + maxBattleWins = Math.max( + maxBattleWins, + currentVoteWinner[x] = + currentVoteWinner[x] + voterWeight); + } } } + + if (firstVoter || winners != null) { + + // still have a winner, le'ts compute current winner + Set<String> currentVoteWinners = Sets.newHashSet(); + + // find winners of this vote + for (int i = 0; i < currentVoteWinner.length; i++) { + if (maxBattleWins == currentVoteWinner[i]) { + + // this is a winner for this vote + String choiceId = choiceIds.get(i); + currentVoteWinners.add(choiceId); + } + } + if (log.isDebugEnabled()) { + log.debug("Winners of this vote : " + currentVoteWinners); + } + + + if (firstVoter) { + + // keep this first result + winners = currentVoteWinners; + } else if (!winners.equals(currentVoteWinners)) { + + // current vote has not same winners than previous, + // so will need resolution + winners = null; + + if (log.isDebugEnabled()) { + log.debug("Dismatch winners (will need resolv...)"); + } + } + } + + firstVoter = false; } - return result; + return winners; } + + public static class VoteForChoiceComparator implements Comparator<VoteForChoice>, Serializable { + + private static final long serialVersionUID = 1L; + + @Override + public int compare(VoteForChoice o1, VoteForChoice o2) { + Double v1 = o1.getVoteValue(); + Double v2 = o2.getVoteValue(); + if (v1 == null) { + v1 = Double.MAX_VALUE; + } + if (v2 == null) { + v2 = Double.MAX_VALUE; + } + return v2.intValue() - v1.intValue(); + } + } } Modified: trunk/pollen-votecounting-strategy-condorcet/src/test/java/org/chorem/pollen/votecounting/CondorcetStrategyTest.java =================================================================== --- trunk/pollen-votecounting-strategy-condorcet/src/test/java/org/chorem/pollen/votecounting/CondorcetStrategyTest.java 2012-06-25 17:56:45 UTC (rev 3556) +++ trunk/pollen-votecounting-strategy-condorcet/src/test/java/org/chorem/pollen/votecounting/CondorcetStrategyTest.java 2012-06-25 22:51:43 UTC (rev 3557) @@ -72,6 +72,42 @@ // Simple poll (all weight to 1) // 1 (a=1 b=2 c=null) + // 2 (a=1 b=3 c=2) + // 3 (a=1 b=null c=2) + // Result (a=6 b=1 c=2) + + Set<Voter> voters = new VoterBuilder(). + newVoter("1", 1.). + addVoteForChoice(CHOICE_A, 1.). + addVoteForChoice(CHOICE_B, 2.). + addVoteForChoice(CHOICE_C, null). + newVoter("2", 1.). + addVoteForChoice(CHOICE_A, 1.). + addVoteForChoice(CHOICE_B, 3.). + addVoteForChoice(CHOICE_C, 2.). + newVoter("3", 1.). + addVoteForChoice(CHOICE_A, 1.). + addVoteForChoice(CHOICE_B, null). + addVoteForChoice(CHOICE_C, 2.). + getVoters(); + + VoteCountingResult result = strategy.votecount(voters); + + Assert.assertNotNull(result); + List<ChoiceScore> scores = result.getScores(); + Assert.assertNotNull(scores); + Assert.assertEquals(3, scores.size()); + + assertChoiceScore(scores.get(0), CHOICE_A, BigDecimal.valueOf(6.)); + assertChoiceScore(scores.get(1), CHOICE_C, BigDecimal.valueOf(2.)); + assertChoiceScore(scores.get(2), CHOICE_B, BigDecimal.valueOf(1.)); + } + + @Test + public void simpleVotecount0() throws Exception { + + // Simple poll (all weight to 1) + // 1 (a=1 b=2 c=null) // 2 (a=3 b=2 c=1) // 3 (a=1 b=null c=2) // Result (a=4 b=2 c=3) @@ -94,7 +130,6 @@ VoteCountingResult result = strategy.votecount(voters); Assert.assertNotNull(result); - Assert.assertNull(result.getVoter()); List<ChoiceScore> scores = result.getScores(); Assert.assertNotNull(scores); Assert.assertEquals(3, scores.size()); @@ -131,7 +166,6 @@ VoteCountingResult result = strategy.votecount(voters); Assert.assertNotNull(result); - Assert.assertNull(result.getVoter()); List<ChoiceScore> scores = result.getScores(); Assert.assertNotNull(scores); Assert.assertEquals(3, scores.size()); @@ -170,7 +204,6 @@ VoteCountingResult result = strategy.votecount(voters); Assert.assertNotNull(result); - Assert.assertNull(result.getVoter()); List<ChoiceScore> scores = result.getScores(); Assert.assertNotNull(scores); Assert.assertEquals(3, scores.size()); @@ -210,7 +243,6 @@ VoteCountingResult result = strategy.votecount(voters); Assert.assertNotNull(result); - Assert.assertNull(result.getVoter()); List<ChoiceScore> scores = result.getScores(); Assert.assertNotNull(scores); Assert.assertEquals(3, scores.size()); @@ -249,7 +281,6 @@ VoteCountingResult result = strategy.votecount(voters); Assert.assertNotNull(result); - Assert.assertNull(result.getVoter()); List<ChoiceScore> scores = result.getScores(); Assert.assertNotNull(scores); Assert.assertEquals(3, scores.size());