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     unless votes.length > 0
  91       @winners=[]
  92       return
  93     end
  94
  95     begin
  96       ranked_candidates = votes.sort do |a, b|
  97         b[1][0] <=> a[1][0]
  98       end.collect {|i| i[0]}
  99       @winners = ranked_candidates.find_all do |i|
 100         votes[i][0] >= @majority
 101       end
 102     end while not self.winner? and next_round(votes, ranked_candidates)
 103     @ranked_candidates.unshift(*ranked_candidates)
 104   end
 105
 106 protected
 107   def apply_candidate_count(votes, candidate_count)
 108     if votes.size > candidate_count
 109       losers = votes.sort do |a, b|
 110         b[1][0] <=> a[1][0]
 111       end.collect {|i| i[0]}.last(votes.size - candidate_count)
 112       @ranked_candidates.unshift(losers) unless losers.empty?
 113       losers.each { |loser| remove_candidate(votes, loser) }
 114     end
 115   end
 116
 117   def apply_vote_minimum(votes, vote_minimum)
 118     losers = votes.find_all do |i|
 119       i[1][0] < vote_minimum
 120     end.collect {|i| i[0]}
 121     if losers.length == votes.size
 122       votes.clear
 123     else
 124       @ranked_candidates.unshift(losers) unless losers.empty?
 125       losers.each { |loser| remove_candidate(votes, loser) }
 126     end
 127   end
 128
 129   def apply_retention(votes, retention)
 130     losers = votes.sort do |a, b|
 131       b[1][0] <=> a[1][0]
 132     end.collect {|i| i[0]}
 133     partial_sum = 0
 134     while partial_sum < retention
 135       partial_sum += votes[losers.shift][0]
 136     end
 137     @ranked_candidates.unshift(losers) unless losers.empty?
 138     losers.each { |loser| remove_candidate(votes, loser) }
 139   end
 140
 141   def next_round(votes, ranked_candidates)
 142     loser = ranked_candidates[-1]
 143     if votes.empty? or votes[loser][0] == votes[ranked_candidates[-2]][0]
 144       false
 145     else
 146       @ranked_candidates.unshift(loser)
 147       remove_candidate(votes, loser)
 148       true
 149     end
 150   end
 151
 152   def remove_candidate(votes, loser)
 153     votes.each_pair do |candidate, morevotes|
 154       hash = morevotes[1]
 155       hash.each_pair do |vote, count|
 156         hash.delete(vote)
 157         vote.delete(loser)
 158         hash[vote] = count
 159       end
 160     end
 161     votes[loser][1].each_pair do |vote, count|
 162       candidate = vote.shift
 163       votes[candidate][0] += count
 164       if votes[candidate][1].has_key?(vote)
 165         votes[candidate][1][vote] += count
 166       else
 167         votes[candidate][1][vote] = count
 168       end
 169     end
 170     votes.delete(loser)
 171   end
 172 end
 173
 174 class InstantRunoffLogicResult < InstantRunoffResult
 175   def next_round(votes, ranked_candidates)
 176     losers = ranked_candidates.find_all do |i|
 177       votes[i][0] == votes[ranked_candidates[-1]][0]
 178     end
 179     if losers.inject(0) {|n, loser| n + votes[loser][0]} >= @majority
 180       false
 181     else
 182       @ranked_candidates.unshift(losers)
 183       losers.each do |loser|
 184         remove_candidate(votes, loser)
 185       end
 186       true
 187     end
 188   end
 189 end
 190
 191 class InstantRunoffFirstRoundResult < InstantRunoffResult
 192   def next_round(votes, ranked_candidates)
 193     losers = ranked_candidates.find_all do |i|
 194       votes[i][0] == votes[ranked_candidates[-1]][0]
 195     end
 196     loser = losers.sort do |a, b|
 197       @election.votes[a][0] <=> @election.votes[b][0]
 198     end.last
 199     @ranked_candidates.unshift(loser)
 200     remove_candidate(votes, loser)
 201   end
 202 end
 203
 204 class InstantRunoffAllResult < InstantRunoffResult
 205   def next_round(votes, ranked_candidates)
 206     losers = ranked_candidates.find_all do |i|
 207       votes[i][0] == votes[ranked_candidates[-1]][0]
 208     end
 209     if losers.length == ranked_candidates.length
 210       false
 211     else
 212       @ranked_candidates.unshift(losers)
 213       losers.each do |loser|
 214         remove_candidate(votes, loser)
 215       end
 216       true
 217     end
 218   end
 219 end
 220
 221 class InstantRunoffRandomResult < InstantRunoffResult
 222   def next_round(votes, ranked_candidates)
 223     losers = ranked_candidates.find_all do |i|
 224       votes[i][0] == votes[ranked_candidates[-1]][0]
 225     end
 226     loser = losers[rand(losers.length)]
 227     @ranked_candidates.unshift(loser)
 228     remove_candidate(votes, loser)
 229   end
 230 end