package com.ease.gsms.server.services.dispatch;

public class BinBalancer {

    /**
     * Adds a number of items to bins in a way that balances them
     * as much as possible
     * @param additional how many items to add
     * @param bins existing bins with item counts
     * @return balanced bins, in same order as the original bins
     */
    public static int[] balance(int additional, int[] bins) {

        int binCount = bins.length;

        if (binCount == 0) {

            return new int[0];

        } else if (binCount == 1) {

            return new int[] { bins[0] + additional };

        }

        if (additional < 0) {

            throw new IllegalArgumentException("Algorithm only works with natural (positive) numbers");

        }

        int[] copiedBins = new int[binCount];

        System.arraycopy(bins, 0, copiedBins, 0, binCount);

        bins = copiedBins;

        int[] permutations = new int[binCount];

        for (int i=0; i<binCount; i++) {

            permutations[i] = i; // at the beginning, we're in order

        }

        permutationAwareQuickSort(bins, permutations); // we now have our bins sorted from emptiest to fullest

        int lastAdditional = -1;

        while (lastAdditional != additional) { // while we're not balanced yet (either all elements are equal or there are no additional elements to place)
            int consecutiveEqualBins = 0, startingValue = bins[0];
            for (; consecutiveEqualBins < binCount && bins[consecutiveEqualBins] == startingValue; consecutiveEqualBins++); // figured out how many bins have the same value
            int delta, maxDelta = additional / consecutiveEqualBins;
            if (consecutiveEqualBins < binCount) { // there is a greater bin
                delta = Math.min(bins[consecutiveEqualBins] - startingValue, maxDelta); // how much we need to add to reach the value of the first bin that's greater than the first <consecutiveEqualBins> - without exceeding additional
            } else {
                delta = maxDelta;
            }
            for (int i=0; i<consecutiveEqualBins; i++) {
                bins[i] += delta;
            }
            lastAdditional = additional;
            additional -= delta * consecutiveEqualBins;
        }

        bins[0] += additional; // put any remaining leftovers in the first bin

        int[] inInitialOrder = new int[binCount];

        for (int i=0; i<binCount; i++) {
            inInitialOrder[permutations[i]] = bins[i];
        }

        return inInitialOrder;
    }

    /**
     * Adds a number of items to bins in a way that balances them
     * as much as possible
     * @param additional how many items to add
     * @param bins existing bins with item counts
     * @return balanced bins, in same order as the original bins
     */
    public static int[] balanceDelta(int additional, int[] bins) {

        int binCount = bins.length;

        int[] delta = new int[binCount];

        int[] distributed = balance(additional, bins);

        for (int i=0; i<binCount; i++) {

            delta[i] = distributed[i] - bins[i];

        }

        return delta;

    }

    private static void permutationAwareQuickSort(int[] array, int[] permutations) {

        // check if already in order

        int high = array.length - 1;

        boolean inOrder = true;

        for (int i = 0; inOrder && i<high; i++) {

            inOrder = array[i] <= array[i+1];

        }

        if (!inOrder) {

            permutationAwareQuickSort(array, permutations, 0, high);

        }

    }

    private static void permutationAwareQuickSort(int[] array, int[] permutations, int low, int high) {

        if (low < high) {

            // partitioning start

            int pivot = array[high];
            int i = (low - 1);

            for (int j=low; j<=high-1; j++) {
                if (array[j] < pivot) {
                    swap(array, permutations, ++i, j);
                }
            }

            swap(array, permutations, i + 1, high);

            // partitioning end

            permutationAwareQuickSort(array, permutations, low, i);
            permutationAwareQuickSort(array, permutations, i + 2, high);

        }

    }

    private static void swap(int[] array, int[] permutations, int i, int j) {

        int t = array[j], tp = permutations[j];

        array[j] = array[i];

        permutations[j] = permutations[i];

        array[i] = t;

        permutations[i] = tp;

    }

}
