From: Benjamin Mako Hill <mako@atdot.cc>
Date: Fri, 3 Mar 2006 01:44:54 +0000 (+0000)
Subject: Added support for instant run-off voting with a patch from
X-Git-Url: https://projects.mako.cc/source/rubyvote/commitdiff_plain/863282d853f14245e6b494a5556e98e461b856cb

Added support for instant run-off voting with a patch from
Alexis Darrasse <alexis@ortsa.com>.

Thanks Alexis!



git-svn-id: svn://rubyforge.org/var/svn/rubyvote/trunk@6 1440c7f4-e209-0410-9a04-881b5eb134a8
---

diff --git a/lib/runoff.rb b/lib/runoff.rb
new file mode 100644
index 0000000..f9edc5e
--- /dev/null
+++ b/lib/runoff.rb
@@ -0,0 +1,90 @@
+require 'election'
+
+class InstantRunoffVote < ElectionVote
+  def initialize(votes=nil)
+    @candidates = Array.new
+    votes.each do |vote|
+      @candidates = vote.uniq if vote.uniq.length > candidates.length
+    end
+    super(votes)
+    @candidates.each do |candidate|
+      @votes[candidate] = [0, Hash.new] unless @votes.has_key?(candidate)
+    end
+  end
+
+  def result
+    InstantRunoffResult.new(self)
+  end
+  
+  protected
+  def tally_vote(vote)
+    votecopy = vote.dup
+    candidate = votecopy.shift
+    votes[candidate] = [0, Hash.new] unless votes.has_key?(candidate)
+    votes[candidate][0] += 1
+    if votes[candidate][1].has_key?(votecopy)
+      votes[candidate][1][votecopy] += 1
+    else
+      votes[candidate][1][votecopy] = 1
+    end
+  end
+
+  def verify_vote(vote=nil)
+    vote.instance_of?( Array ) and
+      vote == vote.uniq
+  end
+end
+
+class InstantRunoffResult < ElectionResult
+  attr_reader :ranked_candidates
+
+  def initialize(voteobj=nil)
+    unless voteobj and voteobj.kind_of?( InstantRunoffVote )
+      raise ArgumentError, "You must pass an InstantRunoffVote array.", caller
+    end
+    super(voteobj)
+
+    votes = @election.votes.clone
+    candidates = @election.candidates
+    majority = votes.inject(0) {|n, value| n + value[1][0]}/2 + 1
+    @ranked_candidates = Array.new()
+    ranked_candidates = Array.new()
+
+    loop do
+      ranked_candidates = votes.sort do |a, b|
+        b[1][0] <=> a[1][0]
+      end.collect {|i| i[0]}
+      @winners = ranked_candidates.find_all do |i|
+        votes[i][0] >= majority
+      end
+      
+      loser = ranked_candidates[-1]
+      break if self.winner? or votes[loser][0] == votes[ranked_candidates[-2]][0]
+
+      @ranked_candidates.unshift(loser)
+      runoff(votes, loser) 
+    end
+    @ranked_candidates.unshift(*ranked_candidates)
+  end
+
+  def runoff(votes, loser)
+    votes.each_pair do |candidate, morevotes|
+      hash = morevotes[1]
+      hash.each_pair do |vote, count|
+        hash.delete(vote)
+        vote.delete(loser)
+        hash[vote] = count
+      end
+    end
+    votes[loser][1].each_pair do |vote, count|
+      candidate = vote.shift
+      votes[candidate][0] += count
+      if votes[candidate][1].has_key?(vote)
+        votes[candidate][1][vote] += count
+      else
+        votes[candidate][1][vote] = count
+      end
+    end
+    votes.delete(loser)
+  end
+end
diff --git a/test.rb b/test.rb
index 3be4176..f87e41d 100755
--- a/test.rb
+++ b/test.rb
@@ -21,6 +21,7 @@
 require 'election'
 require 'condorcet'
 require 'positional'
+require 'runoff'
 
 def print_winner(result)
   if not result.winner?
@@ -128,6 +129,60 @@ def approval_test1
   print_winner( ApprovalVote.new(vote_array).result )
 end
 
+def runoff_test1
+  puts "USING RUNOFF..."
+  puts "The winner shold be: A"
+
+  vote_array = Array.new
+  142.times {vote_array << "ABCD".split("")}
+  26.times {vote_array << "BCDA".split("")}
+  15.times {vote_array << "CDBA".split("")}
+  17.times {vote_array << "DCBA".split("")}
+
+  print_winner( InstantRunoffVote.new(vote_array).result )
+end
+
+def runoff_test2
+  puts "USING RUNOFF..."
+  puts "The winner shold be: D"
+
+  vote_array = Array.new
+  42.times {vote_array << "ABCD".split("")}
+  26.times {vote_array << "BCDA".split("")}
+  15.times {vote_array << "CDBA".split("")}
+  17.times {vote_array << "DCBA".split("")}
+
+  print_winner( InstantRunoffVote.new(vote_array).result )
+end
+
+def runoff_test3
+  puts "USING RUNOFF..."
+  puts "The winner shold be: C"
+
+  vote_array = Array.new
+  42.times {vote_array << "ABCD".split("")}
+  26.times {vote_array << "ACBD".split("")}
+  15.times {vote_array << "BACD".split("")}
+  32.times {vote_array << "BCAD".split("")}
+  14.times {vote_array << "CABD".split("")}
+  49.times {vote_array << "CBAD".split("")}
+  17.times {vote_array << "ABDC".split("")}
+  23.times {vote_array << "BADC".split("")}
+  37.times {vote_array << "BCDA".split("")}
+  11.times {vote_array << "CADB".split("")}
+  16.times {vote_array << "CBDA".split("")}
+  54.times {vote_array << "ADBC".split("")}
+  36.times {vote_array << "BDCA".split("")}
+  42.times {vote_array << "CDAB".split("")}
+  13.times {vote_array << "CDBA".split("")}
+  51.times {vote_array << "DABC".split("")}
+  33.times {vote_array << "DBCA".split("")}
+  39.times {vote_array << "DCAB".split("")}
+  12.times {vote_array << "DCBA".split("")}
+
+  print_winner( InstantRunoffVote.new(vote_array).result )
+end
+
 condorcet_test1()
 ssd_test1()
 ssd_test2()
@@ -135,4 +190,6 @@ ssd_test3()
 borda_test1()
 plurality_test1()
 approval_test1()
-
+runoff_test1()
+runoff_test2()
+runoff_test3()