/***********************************************************************
* Name: COS 126 Staff
* NetID: cos126
* Precept: P99
*
* Election: A library of methods for a reverse instant runoff voting election
*
* Dependencies: Ballot, ST
*/
public class Election {
// find maximum value in symbol table
public static int maxValue(ST<String, Integer> st) {
int result = Integer.MIN_VALUE;
// enhanced for loop, through all keys
for (String s : st)
// update using value
result = Math.max(result, st.get(s));
return result;
}
// get top or bottom counts
public static ST<String, Integer> counts(Ballot[] a, boolean countTop) {
// create a new symbol table
ST<String, Integer> result = new ST<String, Integer>();
// for each voter,
for (int i = 0; i < a.length; i++) {
// who are we incrementing?
String who;
if (countTop)
who = a[i].top();
else
who = a[i].bottom();
// do the increment
if (!result.contains(who))
result.put(who, 1);
else
result.put(who, 1 + result.get(who));
}
return result;
}
// search ST for target value, return associated key. exception if not found
private static String find(ST<String, Integer> st, int target) {
// enhanced for loop - iterate through all keys
for (String key : st) {
if (st.get(key) == target)
return key;
}
throw new RuntimeException("Not found!");
}
// winner's name, or null if no majority yet
public static String winner(Ballot[] a) {
ST<String, Integer> topCounts = counts(a, true);
// what's the max # top() votes anyone has?
int max = maxValue(topCounts);
// strict majority? return that person
if (max > a.length/2.0)
return find(topCounts, max);
else
// no majority
return null;
}
// which person has the most bottom ballots?
public static String loser(Ballot[] a) {
ST<String, Integer> bottomCounts = counts(a, false);
// what's the max # bottom() votes anyone has?
int max = maxValue(bottomCounts);
// return the person acheiving that maximum
return find(bottomCounts, max);
}
public static void main(String[] args) {
// test maxValue()
ST<String, Integer> st = new ST<String, Integer>();
st.put("someKey", 5);
st.put("anotherKey", 8);
st.put("thirdKey", 6);
StdOut.println("max value should be 8: " + maxValue(st));
StdOut.println();
// create 3 ballots with these preferences
String[] prf1 = {"Claude", "David", "Ada", "Bjarne"};
String[] prf2 = {"Bjarne", "Ada", "Claude", "David"};
String[] prf3 = {"Ada", "David", "Claude", "Bjarne"};
Ballot[] a = {new Ballot(prf1), new Ballot(prf2), new Ballot(prf3)};
// test counts()
ST<String, Integer> topCounts = counts(a, true);
StdOut.println("topCounts - should be Ada 1, Bjarne 1, Claude 1: ");
for (String cand : topCounts)
StdOut.println(cand + " " + topCounts.get(cand));
StdOut.println();
ST<String, Integer> bottomCounts = counts(a, false);
StdOut.println("bottomCounts - should be Bjarne 2, David 1: ");
for (String cand : bottomCounts)
StdOut.println(cand + " " + bottomCounts.get(cand));
StdOut.println();
// test winner() when no majority
StdOut.println("winner() should be null, actually: " + winner(a));
// test loser()
StdOut.println("loser() should be Bjarne, actually: " + loser(a));
StdOut.println("eliminating Bjarne");
for (Ballot b : a)
b.cut("Bjarne");
/* at this point, the ballots should be
* Claude > David > Ada
* Ada > Claude > David
* Ada > David > Claude */
// test winner() with majority
StdOut.println("winner() should be Ada, actually: " + winner(a));
}
}