HareNiemayer.java

package elections;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
import java.util.stream.IntStream;

import org.apache.commons.collections.MapUtils;
import org.apache.commons.lang3.ArrayUtils;

public class HareNiemayer {

    private static String[] partyNames = new String[] {"РБ", "ГЕРБ", "АТАКА", "ББЦ", "АБВ", "ДПС", "БСП", "ПФ"};
    
    public static void main(String[] args) {
        
        int[] constituencySeats = {11, 14, 15, 8, 4, 6, 4, 6, 5, 4, 5, 5, 9, 4, 9, 11, 11, 4, 8, 4, 6, 4, 16, 12, 14, 8, 11, 4, 8, 6, 4};
        
        int[] rb = {10033, 11245, 17377, 7863, 2637, 3705, 3249, 4498, 1668, 2941, 3983, 6071, 6592, 5019, 8305, 13763, 7563, 3014, 7733, 3163, 4172, 2152, 43192, 32308, 21691, 7333, 9357, 3378, 15565, 4024, 2689, 15523};
        int[] gerb = {50752, 63625, 69636, 32736, 12256, 21486, 21604, 23391, 11984, 20150, 19459, 17063, 36208, 19955, 32542, 61249, 46471, 10161, 30105, 16314, 25821, 18424, 74865, 59545, 65604, 36320, 49062, 11937, 34381, 21870, 18647, 38868};
        int[] ataka = {5609, 4111, 8834, 5960, 2373, 5039, 3570, 3756, 791, 3996, 3431, 4937, 6621, 3464, 7459, 5652, 5728, 1143, 5410, 1425, 4269, 1753, 8444, 7404, 8721, 5187, 7301, 1511, 4515, 2909, 4510, 2429};
        int[] bbc = {8075, 7936, 10016, 6150, 3485, 8729, 3283, 5621, 1138, 7539, 3716, 8683, 6475, 5630, 9824, 8242, 9814, 1469, 6025, 2295, 4481, 3900, 4483, 4147, 6665, 9513, 10598, 2507, 7499, 3395, 3933, 1672};
        int[] abv = {5456, 5475, 9876, 5862, 1272, 5514, 2192, 3399, 709, 2364, 2672, 3620, 3994, 5177, 6727, 5707, 5602, 925, 3815, 2113, 2953, 1260, 9933, 6844, 9078, 4546, 5900, 2453, 3009, 2896, 2243, 2637};
        int[] dps = {23025, 27298, 15798, 11685, 2425, 10626, 2931, 15855, 59881, 864, 8883, 4928, 17348, 1012, 10384, 5820, 14695, 33334, 12807, 21007, 7644, 12218, 1934, 2043, 2539, 5773, 14938, 26240, 20680, 28858, 3723, 59938};
        int[] bsp = {19170, 21617, 24711, 19612, 11089, 16818, 9464, 12224, 4926, 14367, 12056, 10670, 19499, 9030, 21596, 19786, 28316, 5324, 13455, 8015, 12476, 9748, 32199, 23415, 24264, 21306, 28563, 7554, 16087, 10701, 13834, 3635};
        int[] pf = {9424, 24627, 17551, 9632, 1720, 5521, 3969, 6834, 1753, 2668, 4460, 2532, 5475, 2870, 10955, 12992, 10538, 2563, 10086, 4182, 5589, 2335, 12290, 10317, 11711, 7275, 12394, 3224, 8685, 5576, 4203, 5150};
        int[][] partyResults = new int[][] {rb, gerb, ataka, bbc, abv, dps, bsp, pf};
        
        int rbTotal = IntStream.of(rb).sum();
        int gerbTotal = IntStream.of(gerb).sum();
        int atakaTotal = IntStream.of(ataka).sum();
        int bbcTotal = IntStream.of(bbc).sum();
        int abvTotal = IntStream.of(abv).sum();
        int dpsTotal = IntStream.of(dps).sum();
        int bspTotal = IntStream.of(bsp).sum();
        int pfTotal = IntStream.of(pf).sum();
        
        int total = rbTotal + gerbTotal + atakaTotal + bbcTotal + abvTotal + dpsTotal + bspTotal + pfTotal;
        
        Map<Integer, Map<Integer, Integer>> markedRemainders = new LinkedHashMap<>();
        Map<Integer, Map<Integer, Integer>> allRemainders = new LinkedHashMap<>();
        
        int[] partySeats = assignSeats(partyResults, total, 240, -1, markedRemainders, allRemainders);
        System.out.println(Arrays.toString(partySeats));
        
        int totalPreliminary = 0;
        int[][] constituencyPartySeats = new int[constituencySeats.length][];
        for (int i = 0; i < constituencySeats.length; i ++) {
            int constituencyTotal = 0;
            for (int k = 0; k < partyResults.length; k ++) {
                constituencyTotal += partyResults[k][i];
            }
            
            int[] seats = assignSeats(partyResults, constituencyTotal, constituencySeats[i], i, markedRemainders, allRemainders);
            
            constituencyPartySeats[i] = seats;
            totalPreliminary += IntStream.of(seats).sum();
            System.out.println(Arrays.toString(seats));
        }
        
        Set<Integer> excludedConstituencies = new LinkedHashSet<>();
        
        // needed for assigning seats, as the process can't use the dynamic "marked remainders"
        Map<Integer, Map<Integer, Integer>> originalNonAwardedRemainders = new HashMap<>();
        for (Map.Entry<Integer, Map<Integer, Integer>> constituencyEntry : allRemainders.entrySet()) {
            originalNonAwardedRemainders.put(constituencyEntry.getKey(), new LinkedHashMap<>());
            for (Map.Entry<Integer, Integer> partyEntry : constituencyEntry.getValue().entrySet()) {
                if (!markedRemainders.get(constituencyEntry.getKey()).containsKey(partyEntry.getKey())) {
                    originalNonAwardedRemainders.get(constituencyEntry.getKey())
                        .put(partyEntry.getKey(), partyEntry.getValue());
                }
            }
        }
        
        while (needsReassignment(constituencySeats, partySeats, constituencyPartySeats)) {
            System.out.println("Нужно е преразпределение на мандати");
            // looping all constituencies
            int[] currentPartySeats = calculatePartySeats(constituencySeats, constituencyPartySeats);
            
            System.out.println("Мандати преди преразпределение: " + Arrays.toString(currentPartySeats));
            System.out.println("Всички остатъци: " + allRemainders);
            System.out.println("Маркирани остатъци: " + markedRemainders);
            
            Map<Integer, Map<Integer, Integer>> smallestPartyRemainders = new LinkedHashMap<>();
            for (int party = 0; party < partyNames.length; party++) {
                if (currentPartySeats[party] > partySeats[party]) {
                    int partyMarkedRemainders = 0;
                    for (int constituency = 0; constituency < constituencySeats.length; constituency++) {
                        if (excludedConstituencies.contains(constituency)) {
                            continue;
                        }
                        Integer markedRemainder = markedRemainders.get(constituency).get(party);
                        if (markedRemainder != null && markedRemainder > 0) {
                            partyMarkedRemainders++;
                        }
                    }
                    if (partyMarkedRemainders == 0) {
                        for (int constituency = 0; constituency < constituencySeats.length; constituency++) {
                            if (excludedConstituencies.contains(constituency)) {
                                continue;
                            }
                            // marking all remainders of parties that has more than seats than assigned nation-wide
                            // but does not have any additionally obtained seats
                            Integer remainder = allRemainders.get(constituency).get(party);
                            if (remainder != null && remainder > 0) {
                                markedRemainders.get(constituency).put(party, remainder);
                            }
                        }
                    }
                    // find the smallest remainders per party
                    int min = Integer.MAX_VALUE;
                    for (int c = 0; c < constituencySeats.length; c++) {
                        if (excludedConstituencies.contains(c)) {
                            continue;
                        }
                        Integer remainder = markedRemainders.get(c).get(party);
                        if (remainder != null && remainder < min && remainder > 0) {
                            min = remainder;
                        }
                    }

                    // smallestPartyRemainders only relevant to parties that got MORE than they should get
                    smallestPartyRemainders.put(party, new LinkedHashMap<>());
                    // find all constituencies with the same minimum remainder
                    for (int c = 0; c < constituencySeats.length; c++) {
                        if (excludedConstituencies.contains(c)) {
                            continue;
                        }
                        Integer remainder = markedRemainders.get(c).get(party);
                        if (remainder != null && remainder == min) {
                            smallestPartyRemainders.get(party).put(c, remainder);
                        }
                    }
                } else if (currentPartySeats[party] < partySeats[party]) {
                    boolean allRemaindersMarked = true;
                    for (int constituency = 0; constituency < constituencySeats.length; constituency++) {
                        if (!markedRemainders.get(constituency).containsKey(party)) {
                            if (allRemainders.get(constituency).get(party) != 0) {
                                allRemaindersMarked = false;
                                break;
                            }
                        }
                    }
                    if (allRemaindersMarked) {
                        for (int constituency = 0; constituency < constituencySeats.length; constituency++) {
                            markedRemainders.get(constituency).remove(party);
                        }
                    }
                }
            }
            
            System.out.println("Търсене на МИР с най-нисък остатък");
            System.out.println("Изкючени МИР " + excludedConstituencies);
            
            int lowest = Integer.MAX_VALUE;
            int partyWithLowestRemainder = -1;
            int constituencyWithLowestRemainder = -1;
            int iterations = 0;
            do  {
                System.out.println(smallestPartyRemainders);
                for (Map.Entry<Integer, Map<Integer, Integer>> partyRemainderEntry : smallestPartyRemainders.entrySet()) {
                    for (Map.Entry<Integer, Integer> constituencyPartyRemainders : partyRemainderEntry.getValue().entrySet()) {
                        if (constituencyPartyRemainders.getValue() < lowest && constituencyPartyRemainders.getValue() != 0) {
                            if (!excludedConstituencies.contains(constituencyPartyRemainders.getKey())) {
                                lowest = constituencyPartyRemainders.getValue();
                                partyWithLowestRemainder = partyRemainderEntry.getKey();
                                constituencyWithLowestRemainder = constituencyPartyRemainders.getKey();
                            }
                        }
                    }
                }
                
                Map<Integer, Integer> markedConstituencyRemainders = markedRemainders.get(constituencyWithLowestRemainder);
                // this means no non-zero remainder is left in this constituency (except for the lowest one of the current party)
                if (lowest == Integer.MAX_VALUE || 
                        markedConstituencyRemainders.size() == allRemainders.get(constituencyWithLowestRemainder).size()) {
                    excludedConstituencies.add(constituencyWithLowestRemainder);
                } else {
                    break;
                }
                iterations++;
                if (iterations > constituencySeats.length) {
                    break;
                }
            } while (true);
            
            if (partyWithLowestRemainder == -1) {
                break;
            }
            System.out.println("Стойност на най-малкия остатък: " + lowest);
            System.out.println("Партия с най-малък маркиран остатък: " + partyNames[partyWithLowestRemainder]);
            System.out.println("МИР с най-малък остатък: " + (constituencyWithLowestRemainder + 1));
            
            if (incrementRunnerUp(originalNonAwardedRemainders.get(constituencyWithLowestRemainder),
                    markedRemainders.get(constituencyWithLowestRemainder),
                    constituencyPartySeats[constituencyWithLowestRemainder],
                    partyWithLowestRemainder, currentPartySeats, partySeats)) {
                
                constituencyPartySeats[constituencyWithLowestRemainder][partyWithLowestRemainder]--;
                
                // removing the remainders of the party whose results were decreased
                markedRemainders.get(constituencyWithLowestRemainder).remove(partyWithLowestRemainder);
                allRemainders.get(constituencyWithLowestRemainder).remove(partyWithLowestRemainder);
            } else {
                excludedConstituencies.add(constituencyWithLowestRemainder);
            }
            
            
            System.out.println("--------------------------------------");
            
        }
        
        System.out.println("Всички остатъци: " + allRemainders);
        System.out.println("Маркирани остатъци: " + markedRemainders);
        
        System.out.println("Окончателни мандати: " + Arrays.toString(calculatePartySeats(constituencySeats, constituencyPartySeats)));
        
        for (int i = 0; i < constituencyPartySeats.length; i++) {
            System.out.println((i + 1) + ":" + Arrays.toString(constituencyPartySeats[i]));
        }
        System.out.println("Done");
        
    }

    public static void reportInitialRemainders(Map<Integer, Map<Integer, Integer>> allRemainders) {
        for (Map.Entry<Integer, Map<Integer, Integer>> e : allRemainders.entrySet()) {
            
            System.out.println((e.getKey() + 1) + ":" );
            int i = 0;
            Map<Integer, Integer> nonAwarded = new LinkedHashMap<>(e.getValue());

            int[] remainders = new int[nonAwarded.size()];
            Map<Integer, Integer> index = MapUtils.invertMap(nonAwarded);
            for (Map.Entry<Integer, Integer> e1 : nonAwarded.entrySet()) {
                remainders[i++] = e1.getValue();
            }
            Arrays.sort(remainders);
            ArrayUtils.reverse(remainders);
            
            for (int r : remainders) {
                System.out.println((index.get(r) + 1) + " = " + r);
            }
        }
    }

    private static boolean incrementRunnerUp(Map<Integer, Integer> nonAwardedConstituencyRemainders, 
            Map<Integer, Integer> markedConstituencyRemainders, int[] currentPartySeats, 
            int partyWithLowestRemainder, int[] currentGlobalPartySeats, int[] partySeats) {
        Map.Entry<Integer, Integer> runnerUp = null;
        Set<Integer> nonAwardedPartiesRemainders = nonAwardedConstituencyRemainders.keySet();
        int[] remainders = new int[nonAwardedPartiesRemainders.size()];
        if (remainders.length == 0) {
            return false;
        }
        Iterator<Integer> iterator = nonAwardedPartiesRemainders.iterator();
        for (int i = 0; i < remainders.length; i++) {
            remainders[i] = nonAwardedConstituencyRemainders.get(iterator.next());
        }
        Arrays.sort(remainders);
        ArrayUtils.reverse(remainders);
        
        for (Map.Entry<Integer, Integer> entry : nonAwardedConstituencyRemainders.entrySet()) {
            if (entry.getValue() == remainders[0]) { 
                runnerUp = entry;
                break;
            }                
        }
       
        if (runnerUp != null) {
            int party = runnerUp.getKey();
            System.out.println("Партия с най-голям неудовлетворен с мандат остатък: " + partyNames[party]);
            System.out.println("Стойност на най-големия неудовлетворен остатък: " + runnerUp.getValue());
            currentPartySeats[party]++;
            markedConstituencyRemainders.put(party, runnerUp.getValue());
            nonAwardedConstituencyRemainders.remove(runnerUp.getKey());
            return true;
        } else {
            return false;
        }
        
    }

    private static int[] calculatePartySeats(int[] constituencySeats, int[][] constituencyPartySeats) {
        int[] currentPartySeats = new int[partyNames.length];
        
        for (int c = 0; c < constituencyPartySeats.length; c++) {
            for (int p = 0; p < constituencyPartySeats[c].length; p++) {
                currentPartySeats[p] = currentPartySeats[p] + constituencyPartySeats[c][p];
            }
        }
        return currentPartySeats;
    }

    public static boolean needsReassignment(int[] constituencySeats, int[] partySeats, int[][] constituencyPartySeats) {
        for (int party = 0; party < partySeats.length; party ++) {
            int partySeatsSum = 0;
            for (int i = 0; i < constituencySeats.length; i ++) {
                partySeatsSum += constituencyPartySeats[i][party];
            }
            if (partySeats[party] != partySeatsSum) {
                return true;
            }
        }
        return false;
    }

    public static int[] assignSeats(int[][] partyResults, int total, int seats, int constituency, 
            Map<Integer, Map<Integer, Integer>> globalRemainders, 
            Map<Integer, Map<Integer, Integer>> allRemainders) {
        double quota = total / (double) seats;
        
        System.out.println(constituency + " : " + quota + " : " + total);
        
        int[] partySeats = new int[partyResults.length];
        int[] remainders = new int[partyResults.length];
        int[] integerRemainders = new int[partyResults.length];
        
        Map<Integer, Integer> remainderIndex = new LinkedHashMap<>();
        for (int i = 0; i < partyResults.length; i ++) {
            //System.out.println(partyNames[i] + ":" + partyResults[i].length);
            int partyTotal = 0;
            if (constituency > -1) {
                if (i == 31) { // no quotas for abroad
                    break;
                }
                partyTotal = partyResults[i][constituency];
                System.out.println("МИР " + (constituency + 1) + " Партия " + partyNames[i] + "=" + partyTotal);
            } else {
                partyTotal = IntStream.of(partyResults[i]).sum();
            }
            partySeats[i] = (int) (partyTotal / quota);
            remainders[i] = (int) (((partyTotal / quota) - partySeats[i]) * 1000000);
            remainderIndex.put(remainders[i], i);
        }
        Arrays.sort(remainders);
        ArrayUtils.reverse(remainders);
        
        int remaining = seats - IntStream.of(partySeats).sum();
        Map<Integer, Integer> markedRemainders = new LinkedHashMap<>();
        for (int i = 0; i < remaining ; i++) {
            int idx = remainderIndex.get(remainders[i]);
            partySeats[idx] = partySeats[idx] + 1;
            markedRemainders.put(idx, remainders[i]);
        }
        
        globalRemainders.put(constituency, markedRemainders);
        allRemainders.put(constituency, MapUtils.invertMap(remainderIndex));
        
        return partySeats;
    }
}