#filter_out and PureCondorcet weren't getting along well for sparse elections
[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     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

Benjamin Mako Hill || Want to submit a patch?