COS126

• Download Election.java

/***********************************************************************
 * 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));
    }
}