f9edc5e1f96e88e841ad89f43e1b677d50b0302a
[rubyvote] / lib / runoff.rb
1 require 'election'
2
3 class InstantRunoffVote < ElectionVote
4   def initialize(votes=nil)
5     @candidates = Array.new
6     votes.each do |vote|
7       @candidates = vote.uniq if vote.uniq.length > candidates.length
8     end
9     super(votes)
10     @candidates.each do |candidate|
11       @votes[candidate] = [0, Hash.new] unless @votes.has_key?(candidate)
12     end
13   end
14
15   def result
16     InstantRunoffResult.new(self)
17   end
18   
19   protected
20   def tally_vote(vote)
21     votecopy = vote.dup
22     candidate = votecopy.shift
23     votes[candidate] = [0, Hash.new] unless votes.has_key?(candidate)
24     votes[candidate][0] += 1
25     if votes[candidate][1].has_key?(votecopy)
26       votes[candidate][1][votecopy] += 1
27     else
28       votes[candidate][1][votecopy] = 1
29     end
30   end
31
32   def verify_vote(vote=nil)
33     vote.instance_of?( Array ) and
34       vote == vote.uniq
35   end
36 end
37
38 class InstantRunoffResult < ElectionResult
39   attr_reader :ranked_candidates
40
41   def initialize(voteobj=nil)
42     unless voteobj and voteobj.kind_of?( InstantRunoffVote )
43       raise ArgumentError, "You must pass an InstantRunoffVote array.", caller
44     end
45     super(voteobj)
46
47     votes = @election.votes.clone
48     candidates = @election.candidates
49     majority = votes.inject(0) {|n, value| n + value[1][0]}/2 + 1
50     @ranked_candidates = Array.new()
51     ranked_candidates = Array.new()
52
53     loop do
54       ranked_candidates = votes.sort do |a, b|
55         b[1][0] <=> a[1][0]
56       end.collect {|i| i[0]}
57       @winners = ranked_candidates.find_all do |i|
58         votes[i][0] >= majority
59       end
60       
61       loser = ranked_candidates[-1]
62       break if self.winner? or votes[loser][0] == votes[ranked_candidates[-2]][0]
63
64       @ranked_candidates.unshift(loser)
65       runoff(votes, loser) 
66     end
67     @ranked_candidates.unshift(*ranked_candidates)
68   end
69
70   def runoff(votes, loser)
71     votes.each_pair do |candidate, morevotes|
72       hash = morevotes[1]
73       hash.each_pair do |vote, count|
74         hash.delete(vote)
75         vote.delete(loser)
76         hash[vote] = count
77       end
78     end
79     votes[loser][1].each_pair do |vote, count|
80       candidate = vote.shift
81       votes[candidate][0] += count
82       if votes[candidate][1].has_key?(vote)
83         votes[candidate][1][vote] += count
84       else
85         votes[candidate][1][vote] = count
86       end
87     end
88     votes.delete(loser)
89   end
90 end

Benjamin Mako Hill || Want to submit a patch?