Add similar hackish "fix" for IRVL deadlocking on empty vote
[rubyvote] / 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=[nil]
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

Benjamin Mako Hill || Want to submit a patch?