/**
 * 最大余数分摊算法
 * @author xhan
 *{@link=http://en.wikipedia.org/wiki/Largest_remainder_method}
 */
public class ShareCalculator {

    public static  double[] calculate(double[] votes , double totalSeats) {
        double[] seats = new double[votes.length];
        double[] reminders = new double[votes.length];
        
        double totalVotes = 0;
        for (double vote : votes) {
            totalVotes += vote;
        }
        
        double hareQuota = totalVotes / totalSeats ;
        double allocatedSeats = 0;
        
        for(int i = 0; i < votes.length ;i++) {
            double voteDivHareQuota = votes[i] / hareQuota;
            seats[i] = Math.floor(voteDivHareQuota);
            reminders[i] = voteDivHareQuota - seats[i];
            allocatedSeats += seats[i];
        }

        double leftSeats = totalSeats - allocatedSeats;
        
        //allocate left seats to party with largest reminder 
        for (int i = 0; i < leftSeats; i++) {
            double max = 0;
            int maxIndex = 0;
            for (int j = 0; j < reminders.length; j++) {
                if(reminders[j] > max) {
                    max = reminders[j];
                    maxIndex = j;
                }
            }
            seats[maxIndex] += 1;
            reminders[maxIndex] = 0;
        }
        
        return seats;
    }
}