import java.util.ArrayList;
import java.util.Scanner;
import java.util.Set;

/**
 * Runs an instant runoff election.
 * In an instant runoff election each voter submits a list of candidates,
 * in order of preference.  The first name on the list is the voter's 
 * first choice, the second the voter's second choice, etc.  The voter 
 * need not list all of the candidates.
 * 
 * The election is conducted in rounds.  Each voter's first choice is
 * tallied, and the candidate with the fewest first-place votes is 
 * eliminated.  (If there is a tie one of the lowest vote-getters is chosen 
 * at random to be eliminated.)  In each round the voter's top choice 
 * amongst the remaining candidates gets that voter's vote for that round.
 * If no current candidate is on a voter's list that voter casts no vote
 * for this round.
 * 
 * The process ends when there is a single candidate left, who is declared
 * the winner.
 * 
 * This version is written in a more OO style.
 * 
 * @author Scot Drysdale
 */
public class InstantRunoffOO {
	
	private static boolean debugOn = true;    // Print debugging output?
	
	/**
	 * Picks random item from a list
	 * @list the list to choose from
	 * @return an item chosen randomly from list
	 */
	public static String pickRandomItem(ArrayList<String> list) {
		return list.get((int) (Math.random()*list.size()));
	}
	
	/**
	 * Runs an instant-runoff election
	 * @param ballots the ballots for this election
	 * @return winner of the election
	 */
	public static String runInstantRunoffElection(Election ballots) {
		Set<String> candidates = ballots.getInitialCandidates();
	
		// Run rounds until down to a single candidate
		while(candidates.size() > 1) {
			VoteTally tally = ballots.countRunoffVotes(candidates);
			String loser = pickRandomItem(tally.getLosers());
			candidates.remove(loser);
			
			if(debugOn) {
				System.out.println("Vote tally:\n" + tally);
				System.out.println("Loser: " + loser);
			}
		}
		
		if(candidates.size() > 0)
		  return candidates.iterator().next(); // Return the surviving candidate
		else
		  return null;
	}

	/**
	 * Test program
	 */
	public static void main(String[] args) {
		Election ballots = new Election();
		
		System.out.println("Enter candidate names in order of preference,");
		System.out.println("separated by spaces.  End with a blank line.");
		Ballot ballot; 
		Scanner in = new Scanner(System.in);
		
		System.out.print("Enter a ballot: ");
		String line = in.nextLine();
		while(!line.equals("")) {
			ballot = new Ballot();
			Scanner inLine = new Scanner(line);
			
			while(inLine.hasNext()) {
				String candidate = inLine.next();
				ballot.addCandidate(candidate);
			}
			ballots.addBallot(ballot);
			
			System.out.print("Enter a ballot: ");
			line = in.nextLine();
		}
		
		String winner = runInstantRunoffElection(ballots);
		if (winner != null)
	    System.out.println("The winner of the instant runoff election is: " + 
		    winner);
		else
			System.out.println("No valid votes cast");
	}
}