import java.util.*;

public class TRAII_25_X6_test {

    static TRAII_25_X6 mySolution = new TRAII_25_X6_skeleton();

    static Random rnd = new Random();

    public static void main(String[] args) {

        // new seed every time
        rnd.setSeed(System.currentTimeMillis());

        // amount of printing
        int print = 2;

        int nTest = 5;  // how many tests for each input type
        int totalDiff = 0;
        int allTests = 0;
        long start = System.currentTimeMillis();

        boolean ok = true; // becomes false if any test fails to give a valid partition.

        // some smaller tests
        int diff = testX6repeat(8, 100, 2, 0.3f, 0, nTest, 1, print);
        if (diff < 0) ok = false;
        else {
            totalDiff += diff;
            allTests += nTest;
        }


        // a bit larger
        diff = testX6repeat(12, 200, 3, 0.3f, 0, nTest, 2, print);
        if (diff < 0) ok = false;
        else {
            totalDiff += diff;
            allTests += nTest;
        }


        // a bit larger
        diff = testX6repeat(24, 500, 4, 0.4f, 0, nTest, 2, print);
        if (diff < 0) ok = false;
        else {
            totalDiff += diff;
            allTests += nTest;
        }


        // still larger
        diff = testX6repeat(100, 10000, 5, 0.4f, 0, nTest, 2, print-1);
        if (diff < 0) ok = false;
        else {
            totalDiff += diff;
            allTests += nTest;
        }


        diff = testX6repeat(1000, 100000, 10, 0.4f, 0, nTest, 2, print-1);
        if (diff < 0) ok = false;
        else {
            totalDiff += diff;
            allTests += nTest;
        }


        // even larger inputs
        diff = testX6repeat(5000, 1000000, 20, 0.4f, 0, nTest, 3, print-1);
        if (diff < 0) ok = false;
        else {
            totalDiff += diff;
            allTests += nTest;
        }


        // still larger inputs
        diff = testX6repeat(20000, 50000000, 20, 0.4f, 0, nTest, 5, print-1);
        if (diff < 0) ok = false;
        else {
            totalDiff += diff;
            allTests += nTest;
        }


        // summary of tests

        if (ok)
            System.out.format(
                    "%nDifference to zero in all %d tests average  %.2f%n",
                    allTests, 1.0 * totalDiff / allTests);
        else System.out.println("\nSome tests gave an invalid result.");

        long aika = System.currentTimeMillis() - start;
        System.out.format(
                "Time used %.2f sec, %.2f sec/test (including input generation and output checks)",
                aika / 1000.0, aika / (1000.0 * allTests));
    }

    /**
     * Test X6 repeatedly with similar parameters
     * @param N number of elements in input (approximate)
     * @param binWeight average sum of weights of elements in one result bin
     * @param bins number of output bins
     * @param variation how much numbers differ
     * @param extra how much extra in addition to equals (not used yet)
     * @param repeats how many tests
     * @param maxTime max time for each test
     * @param print how much to print
     * @return sum of max bin sum difference
     */
    static int testX6repeat(
            int N, int binWeight, int bins, float variation, int extra, int repeats, int maxTime, int print) {
        boolean ok = true;
        if (print > 0) System.out.println("----------------------\nTestset starts");
        int diffTotal = 0;
        for (int i = 0; i < repeats; i++) {
            int diff = testX6(N, binWeight, bins, variation, extra, maxTime, print);
            if (diff < 0) ok = false;
            else diffTotal += diff;
        }
        if (ok)
            System.out.format("Test set results: n = ~%d, binWeight = %d, bins = %d, extra = %d, result average %.2f difference%n",
                    N, binWeight, bins, extra, 1.0 * diffTotal / repeats);
        else System.out.println("\nN = " + N + ": Some tests gave invalid result");
        if (print > 0) System.out.println("----------------------");

        return ok ? diffTotal : -1;
    }

    static int testX6(int inputSize, int binWeight, int bins, float variation, int extra,
                      int maxTime, int print) {
        int avgCandiesForBin = inputSize / bins;
        int avgCandyWeight = binWeight / avgCandiesForBin;
        int minCandyWeight = (int) (avgCandyWeight * variation);
        int maxCandyWeight = avgCandyWeight * 2 - minCandyWeight;
        ArrayList<Integer> input = makeCandyInput(inputSize, bins, extra, rnd, minCandyWeight, maxCandyWeight);
        return testX6(input, bins, maxTime, print);
    }

    static int testX6(
            ArrayList<Integer> input, int bins, int maxTime, int print) {

        int diff = 0;
        long inputSum = sumElements(input);

        int extra = 0; // TODO

        if (print > 0)
            System.out.format(
                    "%nTest, n=%d sum=%d bins=%d avgElemWeight=%.2f extra=%d maxTime=%d%n",
                    input.size(),
                    inputSum,
                    bins,
                    (inputSum * 1.0 / input.size()),
                    extra,
                    maxTime);

        if (print > 1 && input.size() <= 30)
            System.out.println("Input: " + input);

        Iterator<Integer> li = input.iterator();
        ArrayList<ArrayList<Integer>> result = makeEmptyOutputBins(bins);

        // measure time, note if overtime
        long startTime = System.currentTimeMillis();

        // call the algorithm
        mySolution.partition(input, result, maxTime);

        long aika = System.currentTimeMillis() - startTime;
        if (aika > maxTime * 1300L) // 30% headroom
            System.out.println("Too long execution: " + (aika / 1000.0) + "s (max=" + maxTime + "s)");

        if (print > 1 && input.size() <= 50) {
            System.out.println("Result:");
            printBins(result);
        }

        // test if input has been changed
        long inputSumAfter = sumElements(input);
        if (inputSum != inputSumAfter) {
            System.out.println("  Input changed!");
            diff = -1;
        }

        try {
            boolean hN = li.hasNext();
        } catch (ConcurrentModificationException e) {
            System.out.println("  Input changed!");
            diff = -1;
        }

        if (diff < 0)
            return diff;

        // check for content

        diff = checkElements(input, result, print);
        if (diff < 0) {
            System.out.println("Result does not match input!");
            diff = -1;
        } else
            if (print > 0) System.out.println("Difference between smallest and largest bin sum: " + diff);

        return diff;
    }

    static void printBins(ArrayList<ArrayList<Integer>> result) {
        for (List<Integer> bin : result) {
            long sum = sumElements(bin);
            System.out.print(bin);
            System.out.println(" (sum = " + sum + ")");
        }
    }


    static ArrayList<ArrayList<Integer>> makeEmptyOutputBins(int k) {
        ArrayList<ArrayList<Integer>> bins = new ArrayList<>(k);
        for (int i = 0; i < k; i++)
            bins.add(new ArrayList<>());
        return bins;
    }


    /**
     * Sum of elements
     *
     * @param L input collection
     * @return sum of all elements
     */
    static long sumElements(Collection<Integer> L) {
        long s = 0;
        for (int x : L)
            s += x;
        return s;
    }

    /**
     * Generate an input.
     *
     * @param n     Number of elements generated (approximate)
     * @param bins  how many bins are used
     * @param extra how much extra weight in addition to even
     * @param rnd   random number generator
     * @param minW  minumun weight for value (not strict)
     * @param maxW  maximum weight for values (not strict)
     * @return list of integers
     */
    static ArrayList<Integer> makeCandyInput(
            int n, int bins, int extra, Random rnd, int minW, int maxW) {

        if (extra > 0) System.out.println("Extra not yet implemented.");

        ArrayList<Integer> input = new ArrayList<>(n);
        long[] bW = new long[bins];

        int i = 0;
        while (i < n*0.7) {
            int elem = rnd.nextInt(maxW - minW + 1) + minW;
            input.add(elem);
            bW[rnd.nextInt(bins)] += elem;
            i++;
        }

        while (i < n-bins+1) {
            int elem = rnd.nextInt(maxW - minW + 1) + minW;
            input.add(elem);
            bW[smallestIndex(bW)] += elem;
            i++;
        }

        long largest = bW[largestIndex(bW)];
        for (int i1 = 0; i1 < bins; i1++) {
            int elem = (int)(largest - bW[i1]);
            if (elem > 0) {
                input.add(elem);
                bW[i1] += elem;
            }
        }

        Collections.shuffle(input, rnd);

        return input;
    } // makeCandyInput()

    static int smallestIndex(long[] bins) {
        long min = Long.MAX_VALUE;
        int index = -1;
        for (int i = 0; i < bins.length; i++) {
            long v = bins[i];
            if (v < min) {
                min = v;
                index = i;
            }
        }
        return index;
    }

    static int largestIndex(long[] bins) {
        long max = Long.MIN_VALUE;
        int index = -1;
        for (int i = 0; i < bins.length; i++) {
            long v = bins[i];
            if (v > max) {
                max = v;
                index = i;
            }
        }
        return index;
    }



    /**
     * Check if all of the elements are in result
     * and return the difference
     *
     * @param input  all the elements
     * @param result list of lists of the elements
     * @param print  amount of error print
     * @return difference of largest and smallest bin sum if result lists have exactly the same elements as input, -1 otherwise
     */
    static int checkElements(ArrayList<Integer> input, ArrayList<ArrayList<Integer>> result, int print) {
        HashMap<Integer, Integer> MInput = new HashMap<>(input.size() * 2);
        HashMap<Integer, Integer> MResult = new HashMap<>(input.size() * 2);
        boolean ok = true;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (Integer x : input)
            MInput.compute(x, (k, v) -> v == null ? 1 : v + 1);
        for (List<Integer> C : result) {
            int sum = 0;
            for (Integer x : C) {
                MResult.compute(x, (k, v) -> v == null ? 1 : v + 1);
                sum += x;
            }
            if (sum < min) min = sum;
            if (sum > max) max = sum;
        }

        ok = MInput.equals(MResult);

        if (!ok && print > 0) {

            boolean more = false;
            boolean less = false;
            if (!MInput.keySet().containsAll(MResult.keySet()))
                System.out.println("Result has some elements that are not in input at all!");

            for (Map.Entry<Integer, Integer> e : MInput.entrySet()) {
                int resCount = MResult.getOrDefault(e.getKey(), 0);
                int inputCount = e.getValue();

                if (resCount < inputCount && print > 1) {
                    System.out.println("Result is missing element " + e.getKey() + " of input");
                    less = true;
                } else if (resCount > inputCount && print > 1) {
                    System.out.println("Result has an extra element " + e.getKey() + " compared to input");
                    more = true;
                }
            }

            if (print >= 1 && less)
                System.out.println("Result has fewer copies of some element than input");
            if (print >= 1 && more)
                System.out.println("Result has more copies some element than input");

        }

        return ok ? (max-min) : -1;
    }
}