A Groovy Election

Question

Implementing the July 2015 Community Challenge seemed relevant considering it is election time.

I decided to go with the strategy pattern as this can be implemented in many different ways. I did my own implementation of this first, and then later also added a "PascalElection" strategy, as that code was translated and adapted from a Pascal implementation (not included for review here)

Overview of code:

• ElectionStrategy: Interface for the Strategy Pattern
• Election: Class to hold data about the votes and nominees. Also contains a static method to perform an election.
• ElectionResult: (static class within Election) Represents the result of an election.
• CandidateState: (static class within Election) Represents several states a candidate can be in (my strategy only uses three of them, the PascalElection strategy uses all of them).
• SimonElection: My own implementation of the election strategy
• Round: As the STV voting system is an iterative one, this represents a single 'round' in the voting. This can be used to plot a graph over the results. (The code to produce the graphs is not included in this post)

This project is also available on GitHub: Zomis/StackSTV

Example graphs showing election results:

My strategy:

The pascal strategy:

Code

ElectionStrategy:

interface ElectionStrategy {

    Election.ElectionResult elect(Election election)

}

Election:

class Election {

    final List<Candidate> candidates = new ArrayList<>()
    final List<Vote> votes = new ArrayList<>()
    int availablePositions
    int maxChoices

    private Election(int availablePositions) {
        this.availablePositions = availablePositions
    }

    void addVote(Vote vote) {
        this.votes << vote
        this.maxChoices = Math.max(maxChoices, vote.preferences.length)
    }

    void addCandidate(String name) {
        this.candidates.add(new Candidate(name: name))
    }

    double calculateQuota(double excess) {
        (votes.size() - excess) / (availablePositions + 1)
    }

    static class ElectionResult {
        List<Round> rounds
        List<Candidate> candidateResults

        List<Candidate> getCandidates(CandidateState state) {
            candidateResults.stream()
                .filter({it.state == state})
                .collect(Collectors.toList())
        }
    }

    ElectionResult elect(ElectionStrategy strategy) {
        strategy.elect(this)
    }

    static enum CandidateState {
        HOPEFUL, EXCLUDED, ALMOST, NEWLY_ELECTED, ELECTED
    }

    @ToString(includeNames = true, includePackage = false)
    static class Candidate {
        String name
        double weighting = 1
        double votes
        CandidateState state = CandidateState.HOPEFUL

        Candidate copy() {
            new Candidate(name: name, weighting: weighting, votes: votes, state: state)
        }
    }

    @ToString
    static class Vote {
        int numVotes
        Candidate[] preferences

        static Vote fromLine(String line, Election election) {
            String[] data = line.split()
            Vote vote = new Vote()
            vote.numVotes = data[0] as int
            int candidateVotes = data.length - 2
            vote.preferences = new Candidate[candidateVotes]
            for (int i = 0; i < vote.preferences.length; i++) {
                int candidate = data[i + 1] as int
                if (candidate > 0) {
                    vote.preferences[i] = election.candidates.get(candidate - 1)
                }
            }
            vote
        }

        void distribute(Round round) {
            double remaining = numVotes
            int choiceIndex = 0
            preferences.eachWithIndex { Candidate entry, int i ->
                if (entry) {
                    double myScore = remaining * entry.weighting
                    entry.votes += myScore
                    remaining -= myScore
                    round.usedVotes[choiceIndex++] += myScore
                }
            }
            round.excess += remaining
        }
    }

    static final ElectionResult fromURL(URL url, ElectionStrategy strategy) {
        BufferedReader reader = url.newReader()
        String[] head = reader.readLine().split()
        int candidates = head[0] as int
        Election stv = new Election(head[1] as int)
        for (int i = 0; i < candidates; i++) {
            stv.addCandidate("Candidate $i") // use a temporary name at first. real names are at the end of the file
        }

        String line = reader.readLine();
        while (line != '0') {
            Vote vote = Vote.fromLine(line, stv)
            stv.addVote(vote)
            line = reader.readLine();
        }
        for (int i = 0; i < candidates; i++) {
            String name = reader.readLine()
            stv.candidates.get(i).name = name
        }
        stv.elect(strategy)
    }

}

SimonElection:

class SimonElection implements ElectionStrategy {

    @Override
    Election.ElectionResult elect(Election election) {
        List<Round> rounds = new ArrayList<>()

        int electedCount = 0
        int roundsCount = 0
        double previousExcess = 0
        while (electedCount < election.availablePositions) {
            Round round = new Round(roundsCount, election.maxChoices)
            rounds << round
            double roundQuota = election.calculateQuota(previousExcess)
            roundsCount++
            round.quota = roundQuota
            election.candidates*.votes = 0
            election.votes*.distribute(round)
            List<Election.Candidate> elected = election.candidates.stream()
                    .filter({candidate -> candidate.votes > roundQuota})
                    .collect(Collectors.toList())
            elected.each {
                if (it.state != Election.CandidateState.ELECTED) {
                    electedCount++
                }
                it.state = Election.CandidateState.ELECTED
                it.weighting *= roundQuota / it.votes
            }
            if (elected.isEmpty()) {
                Election.Candidate loser = election.candidates.stream()
                        .filter({it.state == Election.CandidateState.HOPEFUL})
                        .min(Comparator.comparingDouble({it.votes})).get()
                loser.state = Election.CandidateState.EXCLUDED
                loser.weighting = 0
            }
            round.candidates = election.candidates.collect {it.copy()}
            previousExcess = round.excess
        }
        new Election.ElectionResult(rounds: rounds, candidateResults: election.candidates)
    }

}

Round:

@ToString
class Round {

    int round
    List<Election.Candidate> candidates = new ArrayList<>()
    double quota
    double[] usedVotes
    double excess

    Round(int round, int maxChoices) {
        this.round = round
        this.usedVotes = new double[maxChoices]
    }

}

Running the code

Tests are available on the GitHub repository, I am currently only running the code in a test, using election data from the most recent Stack Overflow election

Primary Concerns

I'm mostly interested in the way I'm using Groovy, and what Groovy things I could do instead of, or in addition to(?), using Java 8. Should I use some Java stuff instead of some Groovy stuff, or should I use more Groovy instead of Java?

Any other comments welcome.

Answer 1

Being biased toward Groovy, I say do more Groovy stuff :)

There are a number of things you can do to make your code more Grooooooovy.

def is your friend

The def keyword makes it a cinch to declare variables and it makes your declarations easier on the eyes.

// Eeewwww
String s1 = 'hello'
double d1 = Math.floor(10.34)
ArrayList<Integer> l1 = new ArrayList<Integer>()
l1.add(1)
l1.add(2)
l1.add(3)

// Much better.
def s2 = 'hello'
def d2 = Math.floor(10.34)
def l2 = [1, 2, 3]

// It's all the same
assert s1 == s2  // == calls me.equals(other)
assert s1.is(s2) // me.is(other) is Java's reference equality
assert d1 == d2
assert l1 == l2

assert s1.class == s2.class
assert d1.class == d2.class
assert l1.class == l2.class

The code above also demonstrates that Groovy determines identity differently than Java. Also notice that primitives are auto-boxed. In fact, Groovy doesn't have primitives. Everything is an Object.

for loops are basically pointless...

In Groovy code for loops are rare because there are much better ways of accomplishing the same thing.

// This is the same...
for (int i = 0; i < candidates; i++) {
    String name = reader.readLine()
    stv.candidates.get(i).name = name
}

// ...as this, which uses Number.times(Closure)...
candidates.times {
    String name = reader.readLine()
    stv.candidates.get(i).name = name
}

// ...and as this, which uses Range.each{Closure).
(0..<candidates).each {
    String name = reader.readLine()
    stv.candidates.get(i).name = name
}

Not only are these constructs pleasant to work with, they eliminate the possibility of handling the incrementation incorrectly. If it can't be touched, it can't be broken.

...and so are Java Streams

Groovy enhances Java Collections in such a powerful way that it makes Java 8 Streams look like Fortran (as long as you don't need the laziness provided by Java 8 Streams).

Java 8 Streams

candidateResults.stream()
    .filter({it.state == state})
    .collect(Collectors.toList())

election.candidates.stream()
    .filter({candidate -> candidate.votes > roundQuota})
    .collect(Collectors.toList())

election.candidates.stream()
    .filter({it.state == Election.CandidateState.HOPEFUL})
    .min(Comparator.comparingDouble({it.votes})).get()    

the Groovy way

candidateResults.findAll {it.state == state}

election.candidates
    .findAll {candidate -> candidate.votes > roundQuota}

election.candidates
    .findAll {it.state == Election.CandidateState.HOPEFUL}
    .min {it.votes}

multiple classes per file

You can place multiple Groovy classes in the same *.groovy file. No more static inner classes :)

roll your own enhancements

Just as Groovy enhances Java through its GDK, you can enhance Java and Groovy classes through meta-programming. Here's an example of an enhancement I made to Election.fromURL():

before

/* Iterates through two sections of the file.
 * The first section is handled with the 'while loop',
 * and the second in the 'for loop'
 */
while (line != '0') {
    Vote vote = Vote.fromLine(line, stv)
    stv.addVote(vote)
    line = reader.readLine()
}

for (int i = 0; i < candidates; i++) {
    String name = reader.readLine()
    stv.candidates.get(i).name = name
}

after

/* Also iterates through two sections of the file,
 * but by using an Iterator.while(Closure condition) method
 * added through meta-programming.
 *
 * The first section is handled with the 'while()/call() loop',
 * and the second in the 'upto() loop'
 */
use(IteratorCategory) {
    reader.iterator().while { line -> line != '0' }.call { line ->
        stv << Vote.fromLine(line, stv)
    }.upto(candidates) { line, i -> 
        stv.candidates.get(i).name = line 
    }
}

I created this construct because it makes it easier to see the intention of the code.

explanation

The added method Iterator.while(Closure) expects a Closure which when called returns a value that can be evaluated by the Groovy Truth. The value the Closure returns is used to determine whether to continue iterating or not.

The Iterator.while(Closure) method returns yet another Closure. This Closure initiates the iteration when called. The Closure expects yet a third Closure, which is called with each element provided by the iterator. Until iteration aborts.

Finally, when the iteration completes, the Iterator is returned, ready for additional iterating.

Iterator.while(Closure) (and Iterator.upto(Integer, Closure)) are made possible by Groovy's meta-programming. In this case, implemented by the Groovy Category shown below:

package net.zomis.meta

/*
 * Adds useful methods to Iterator.
 */
@groovy.lang.Category(Iterator)
class IteratorCategory {

    /*
     * Returns a Closure which iterates while the condition Closure 
     * evaluates to true. The returned Closure expects another Closure, 
     * an action closure, as its single argument.
     * This 'action' Closure is called during each iteration and is passed 
     * the Iterator.next()value. 
     * When the iteration is complete, the Iterator is returned.
     *
     * Example usage: 
     * use(IteratorCategory) {
     *   def iter = reader.iterator().while { it != 'end' }.call { println it }
     * }
     *
     * @param condition Closure to evaluate on each iteration.
     * @return a Closure
     */
    Closure 'while'(Closure condition) {
        {Iterator iter, Closure closure ->
            while(iter.hasNext()) {
                def it = iter.next()

                if(condition(it)) {
                    closure(it)
                } else {
                    break
                }
            }

            return iter
        }.curry(this)
    }

    /*
     * Similar to Number.upto(Number, Closure), executes the Closure
     * UP TO a specified number of times. However, instead of returning
     * the Closure's return value, it returns the Iterator where
     * it left off.
     *
     * Example usage:
     * use(IteratorCategory) {
     *   def iter = reader.iterator().upto(5) {it, i -> println "$i - $it" }
     * }
     *
     * @param to number of times to iterate
     * @param closure to execute. Called with Iterator.next() and index.
     * @return Iterator
     */
    Iterator upto(int to, Closure closure) {
        int i = 0

        while(this.hasNext() && i < to) {
            closure this.next(), i
            i++
        }

        return this
    }
}

all done

I hope this helps you make your Groovy code more... Groooovy.

Check out most of StackSTV already Groovy-fied right here.