projects.mako.cc - selectricity/blob - lib/rubyvote/irv.rb

   1 class InstantRunoffVote < ElectionVote
   2   def initialize(votes=nil)
   3     @candidates = Array.new
   4     votes.each do |vote|
   5       @candidates = vote.uniq if vote.uniq.length > candidates.length
   6     end
   7     super(votes)
   8     @candidates.each do |candidate|
   9       @votes[candidate] = [0, Hash.new] unless @votes.has_key?(candidate)
  10     end
  11   end
  12
  13   def result(params={})
  14     InstantRunoffResult.new(self, params)
  15   end
  16
  17   protected
  18   def tally_vote(vote)
  19     votecopy = vote.dup
  20     candidate = votecopy.shift
  21     votes[candidate] = [0, Hash.new] unless votes.has_key?(candidate)
  22     votes[candidate][0] += 1
  23     if votes[candidate][1].has_key?(votecopy)
  24       votes[candidate][1][votecopy] += 1
  25     else
  26       votes[candidate][1][votecopy] = 1
  27     end
  28   end
  29
  30   def verify_vote(vote=nil)
  31     vote.instance_of?( Array ) and
  32       vote == vote.uniq
  33   end
  34 end
  35
  36 class InstantRunoffLogicVote < InstantRunoffVote
  37   def result(params={})
  38     InstantRunoffLogicResult.new(self, params)
  39   end
  40 end
  41
  42 class InstantRunoffFirstRoundVote < InstantRunoffVote
  43   def result(params={})
  44     InstantRunoffFirstRoundResult.new(self, params)
  45   end
  46 end
  47
  48 class InstantRunoffAllVote < InstantRunoffVote
  49   def result(params={})
  50     InstantRunoffAllResult.new(self, params)
  51   end
  52 end
  53
  54 class InstantRunoffRandomVote < InstantRunoffVote
  55   def result(params={})
  56     InstantRunoffRandomResult.new(self, params)
  57   end
  58 end
  59
  60 class InstantRunoffResult < ElectionResult
  61   attr_reader :ranked_candidates
  62
  63   def initialize(voteobj=nil, params={})
  64     unless voteobj and voteobj.kind_of?( InstantRunoffVote )
  65       raise ArgumentError, "You must pass an InstantRunoffVote array.", caller
  66     end
  67     super(voteobj)
  68
  69     votes = @election.votes.clone
  70     candidates = @election.candidates
  71     votes_sum = votes.inject(0) {|n, value| n + value[1][0]}
  72     @majority = votes_sum/2 + 1
  73     @ranked_candidates = Array.new()
  74     ranked_candidates = Array.new()
  75     losers = Array.new()
  76
  77     if params.has_key?('candidate_count')
  78       apply_candidate_count(votes, params['candidate_count'])
  79     end
  80     if params.has_key?('vote_minimum')
  81       apply_vote_minimum(votes, params['vote_minimum'])
  82     end
  83     if params.has_key?('percent_minimum')
  84       apply_vote_minimum(votes, votes_sum * params['percent_minimum'])
  85     end
  86     if params.has_key?('percent_retention')
  87       apply_retention(votes, votes_sum * params['percent_retention'])
  88     end
  89
  90     begin
  91       ranked_candidates = votes.sort do |a, b|
  92         b[1][0] <=> a[1][0]
  93       end.collect {|i| i[0]}
  94       @winners = ranked_candidates.find_all do |i|
  95         votes[i][0] >= @majority
  96       end
  97     end while not self.winner? and next_round(votes, ranked_candidates)
  98     @ranked_candidates.unshift(*ranked_candidates)
  99   end
 100
 101 protected
 102   def apply_candidate_count(votes, candidate_count)
 103     if votes.size > candidate_count
 104       losers = votes.sort do |a, b|
 105         b[1][0] <=> a[1][0]
 106       end.collect {|i| i[0]}.last(votes.size - candidate_count)
 107       @ranked_candidates.unshift(losers) unless losers.empty?
 108       losers.each { |loser| remove_candidate(votes, loser) }
 109     end
 110   end
 111
 112   def apply_vote_minimum(votes, vote_minimum)
 113     losers = votes.find_all do |i|
 114       i[1][0] < vote_minimum
 115     end.collect {|i| i[0]}
 116     if losers.length == votes.size
 117       votes.clear
 118     else
 119       @ranked_candidates.unshift(losers) unless losers.empty?
 120       losers.each { |loser| remove_candidate(votes, loser) }
 121     end
 122   end
 123
 124   def apply_retention(votes, retention)
 125     losers = votes.sort do |a, b|
 126       b[1][0] <=> a[1][0]
 127     end.collect {|i| i[0]}
 128     partial_sum = 0
 129     while partial_sum < retention
 130       partial_sum += votes[losers.shift][0]
 131     end
 132     @ranked_candidates.unshift(losers) unless losers.empty?
 133     losers.each { |loser| remove_candidate(votes, loser) }
 134   end
 135
 136   def next_round(votes, ranked_candidates)
 137     loser = ranked_candidates[-1]
 138     if votes.empty? or votes[loser][0] == votes[ranked_candidates[-2]][0]
 139       false
 140     else
 141       @ranked_candidates.unshift(loser)
 142       remove_candidate(votes, loser)
 143       true
 144     end
 145   end
 146
 147   def remove_candidate(votes, loser)
 148     votes.each_pair do |candidate, morevotes|
 149       hash = morevotes[1]
 150       hash.each_pair do |vote, count|
 151         hash.delete(vote)
 152         vote.delete(loser)
 153         hash[vote] = count
 154       end
 155     end
 156     votes[loser][1].each_pair do |vote, count|
 157       candidate = vote.shift
 158       votes[candidate][0] += count
 159       if votes[candidate][1].has_key?(vote)
 160         votes[candidate][1][vote] += count
 161       else
 162         votes[candidate][1][vote] = count
 163       end
 164     end
 165     votes.delete(loser)
 166   end
 167 end
 168
 169 class InstantRunoffLogicResult < InstantRunoffResult
 170   def next_round(votes, ranked_candidates)
 171     losers = ranked_candidates.find_all do |i|
 172       votes[i][0] == votes[ranked_candidates[-1]][0]
 173     end
 174     if losers.inject(0) {|n, loser| n + votes[loser][0]} >= @majority
 175       false
 176     else
 177       @ranked_candidates.unshift(losers)
 178       losers.each do |loser|
 179         remove_candidate(votes, loser)
 180       end
 181       true
 182     end
 183   end
 184 end
 185
 186 class InstantRunoffFirstRoundResult < InstantRunoffResult
 187   def next_round(votes, ranked_candidates)
 188     losers = ranked_candidates.find_all do |i|
 189       votes[i][0] == votes[ranked_candidates[-1]][0]
 190     end
 191     loser = losers.sort do |a, b|
 192       @election.votes[a][0] <=> @election.votes[b][0]
 193     end.last
 194     @ranked_candidates.unshift(loser)
 195     remove_candidate(votes, loser)
 196   end
 197 end
 198
 199 class InstantRunoffAllResult < InstantRunoffResult
 200   def next_round(votes, ranked_candidates)
 201     losers = ranked_candidates.find_all do |i|
 202       votes[i][0] == votes[ranked_candidates[-1]][0]
 203     end
 204     if losers.length == ranked_candidates.length
 205       false
 206     else
 207       @ranked_candidates.unshift(losers)
 208       losers.each do |loser|
 209         remove_candidate(votes, loser)
 210       end
 211       true
 212     end
 213   end
 214 end
 215
 216 class InstantRunoffRandomResult < InstantRunoffResult
 217   def next_round(votes, ranked_candidates)
 218     losers = ranked_candidates.find_all do |i|
 219       votes[i][0] == votes[ranked_candidates[-1]][0]
 220     end
 221     loser = losers[rand(losers.length)]
 222     @ranked_candidates.unshift(loser)
 223     remove_candidate(votes, loser)
 224   end
 225 end