//          A performance test of different approaches to look for
//      a minimum in a continually updated array of values. Subjects to test
//      are a naive linear search, TreeSet and PriorityQueue data structures
//      and specially constructed Binary Heap associated with the work array.
//          Work done with idea to use the best approach in the Hungarian algorithm.

import java.util.*;

public class Test_Performance_Array_Set_Queue {

    //private static final long seed = 1610104421273L;
    //private static final long seed = 1610113642540L;
    //private static final long seed = 1610116812045L;
    private static final long seed = System .currentTimeMillis ();
    private static final Random rng = new Random (seed);

    private static final int workSize = 150;
    private static final int packSize = 5;
    private static final int maxValue = 30;
    private static final int dataSize = 5000000;
    private static final int [] testData_Indices = new int [dataSize];
    private static final int [] testData_Values  = new int [dataSize];

    private static final int iterationsNumber = 17;
    private static final double [] iterationsTimes = new double [iterationsNumber];
    private static final double [] workTimes = new double [8];

    private static final boolean debug = false;
    private static final boolean advanced = false;

    private static int queueMaxSize;

    public static void main (String [] args) {
        int k;
        long startTime, stopTime, result;
        double workTime;

        result = 0;
        System .out .println ("Seed: " + seed);
        System .out .println ();

        startTime = System .nanoTime ();
        generateTestData ();
        stopTime  = System .nanoTime ();
        System .out .println ("Generation time (ms): " + (1e-6 * (stopTime - startTime)));
        System .out .println ();

        for (k = 0; iterationsNumber > k; ++k) {
            startTime = System .nanoTime ();
            result = testArray ();
            stopTime  = System .nanoTime ();
            workTime  = 1e-6 * (stopTime - startTime);
            iterationsTimes [k] = workTime;
            System .out .println ("Array test time (ms): " + workTime);
        }
        System .out .println ("Result: " + result);
        processStats (0);
        System .out .println ();
        //*
        for (k = 0; iterationsNumber > k; ++k) {
            startTime = System .nanoTime ();
            result = testSet ();
            stopTime  = System .nanoTime ();
            workTime  = 1e-6 * (stopTime - startTime);
            iterationsTimes [k] = workTime;
            System .out .println ("Sorted set test time (ms): " + workTime);
        }
        System .out .println ("Result: " + result);
        processStats (2);
        System .out .println ();

        for (k = 0; iterationsNumber > k; ++k) {
            startTime = System .nanoTime ();
            result = testQueue ();
            stopTime  = System .nanoTime ();
            workTime  = 1e-6 * (stopTime - startTime);
            iterationsTimes [k] = workTime;
            System .out .println ("Priority queue test time (ms): " + workTime);
        }
        System .out .println ("Result: " + result);
        System .out .println ("Queue maximum size: " + queueMaxSize);
        processStats (4);
        System .out .println ();
        //*/

        for (k = 0; iterationsNumber > k; ++k) {
            startTime = System .nanoTime ();
            result = testHeap ();
            stopTime  = System .nanoTime ();
            workTime  = 1e-6 * (stopTime - startTime);
            iterationsTimes [k] = workTime;
            System .out .println ("Binary heap test time (ms): " + workTime);
        }
        System .out .println ("Result: " + result);
        processStats (6);
        System .out .println ();

        System .out .print (String .format ("%16d %6d %10d", seed, workSize, dataSize));
        for (k = 0; 8 > k; ++k) {
            if (0 == (k & 1)) {
                System .out .print (String .format (Locale .UK, " %8.2f", workTimes [k]));
            } else {
                System .out .print (String .format (Locale .UK, " %5.2f", workTimes [k]));
            }
        }
        System .out .println ();
    }

    private static void generateTestData () {
        int k, l, m, index;
        int [] lockedIndices;
        boolean flag;

        lockedIndices = new int [packSize];
        Arrays .fill (lockedIndices, -1);

        m = 0;
        for (k = 0; dataSize > k; ) {
            index = rng .nextInt (workSize);
            flag = false;
            for (l = 0; packSize > l; ++l) {
                if (lockedIndices [l] == index) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                continue;
            }
            lockedIndices    [m] = index;
            testData_Indices [k] = index;
            testData_Values  [k] = rng .nextInt (maxValue);
            ++m;
            if (packSize == m) {
                m = 0;
            }
//            System .out .println (String .format ("%4d%4d%4d", k, index, testData_Values [k]));
            ++k;
        }
    }

    @SuppressWarnings("unused")
    private static void processStats (int index) {
        int k, limit;
        double value, sum1, sum2;

        if (5 > iterationsNumber) {
            return;
        }

        Arrays .sort (iterationsTimes);
        value = 2.0 * iterationsTimes [iterationsNumber / 2];
        value -= iterationsTimes [1];

        limit = -1;

        for (k = iterationsNumber / 2; iterationsNumber > k; ++k) {
            if (value > iterationsTimes [k]) {
                limit = k;
            } else {
                break;
            }
        }

        sum1 = 0.0;
        sum2 = 0.0;

        for (k = 1; limit > k; ++k) {
            value = iterationsTimes [k];
            sum1 += value;
            sum2 += value * value;
        }
        sum1 /= limit - 1;
        sum2 -= sum1 * sum1 * (limit - 1);
        sum2 = Math .sqrt (sum2 / (limit - 2));
        workTimes [index + 0] = sum1;
        workTimes [index + 1] = sum2;
        System .out .println (sum1 + " " + sum2);
    }

    private static long testArray () {
        int k, l, dataIndex, index, value, bestValue, bestIndex;
        long result;
        boolean [] usedFlags;
        int [] auxMinima;

        dataIndex = 0;
        result    = 0;
        usedFlags = new boolean [workSize];
        auxMinima = new int     [workSize];

        while (dataSize > dataIndex) {

            Arrays .fill (usedFlags, false);
            Arrays .fill (auxMinima, Integer .MAX_VALUE);

            for (k = 0; workSize > k; ++k) {

                for (l = 0; packSize > l && dataSize > dataIndex; ++l, ++dataIndex) {
                    index = testData_Indices [dataIndex];
                    if (usedFlags [index]) {
                        continue;
                    }
                    value = testData_Values  [dataIndex];
                    if (auxMinima [index] > value) {
                        auxMinima [index] = value;
                    }
                }

                bestValue = Integer .MAX_VALUE;
                bestIndex = -1;

                for (l = 0; workSize > l; ++l) {
                    if (usedFlags [l]) {
                        continue;
                    }
                    value = auxMinima [l];
                    if (bestValue > value) {
                        bestValue = value;
                        bestIndex = l;
                    }
                }

                if (-1 == bestIndex) {
                    break;
                }

                result += bestValue;
                usedFlags [bestIndex] = true;

                if (debug) {
                    if (advanced) {
                        displayArray (auxMinima, usedFlags);
                    }
                    System .out .println (dataIndex + "  " + bestIndex + "  " + bestValue + "  " + result);
                }
            }
        }

        return result;
    }

    private static long testSet () {
        int k, l, dataIndex, index, value, bestValue, bestIndex;
        long result;
        boolean [] usedFlags;
        int [] auxMinima;
        SortedSet <Integer> sortedMinima;

        dataIndex = 0;
        result    = 0;
        usedFlags = new boolean [workSize];
        auxMinima = new int     [workSize];
        sortedMinima = new TreeSet <> (new Comparator <Integer> () {
            @Override
            public int compare (Integer arg1, Integer arg2) {
                int difference = auxMinima [arg1] - auxMinima [arg2];
                if (0 != difference) {
                    return difference;
                }
                return arg1 - arg2;
            }
        });

        while (dataSize > dataIndex) {

            Arrays .fill (usedFlags, false);
            Arrays .fill (auxMinima, Integer .MAX_VALUE);

            for (k = 0; workSize > k; ++k) {

                for (l = 0; packSize > l && dataSize > dataIndex; ++l, ++dataIndex) {
                    index = testData_Indices [dataIndex];
                    if (usedFlags [index]) {
                        continue;
                    }
                    value = testData_Values  [dataIndex];
                    if (auxMinima [index] > value) {
                        sortedMinima .remove (index);
                        auxMinima [index] = value;
                        sortedMinima .add (index);
                    }
                }

                if (sortedMinima .isEmpty ()) {
                    break;
                }

                bestIndex = sortedMinima .first ();
                bestValue = auxMinima [bestIndex];
                sortedMinima .remove (bestIndex);
//                if (usedFlags [bestIndex]) {
//                    throw new IllegalArgumentException ("\n\nImpossible algorithm error.\n");
//                }
                usedFlags [bestIndex] = true;
                result += bestValue;

//                displayArray (auxMinima, usedFlags);
//                System .out .println (dataIndex + "  " + bestValue + "  " + result);
            }
        }

        return result;
    }

    private static long testQueue () {
        int k, l, dataIndex, index, value, bestValue, bestIndex;
        long result;
        boolean [] usedFlags;
        int [] auxMinima;
        Queue <ValueRecord> sortedMinima;
        ValueRecord valueRecord;

        dataIndex = 0;
        result    = 0;
        usedFlags = new boolean [workSize];
        auxMinima = new int     [workSize];
        sortedMinima = new PriorityQueue <> ();
        queueMaxSize = 0;

        while (dataSize > dataIndex) {

            Arrays .fill (usedFlags, false);
            Arrays .fill (auxMinima, Integer .MAX_VALUE);

            for (k = 0; workSize > k; ++k) {

                for (l = 0; packSize > l && dataSize > dataIndex; ++l, ++dataIndex) {
                    index = testData_Indices [dataIndex];
                    if (usedFlags [index]) {
                        continue;
                    }
                    value = testData_Values  [dataIndex];
                    if (auxMinima [index] > value) {
                        auxMinima [index] = value;
                        sortedMinima .add (new ValueRecord (value, index));
                    }
                }

                if (queueMaxSize < sortedMinima .size ()) {
                    queueMaxSize = sortedMinima .size ();
                }

                bestValue = Integer .MAX_VALUE;
                bestIndex = -1;

                while (!sortedMinima .isEmpty ()) {
                    valueRecord = sortedMinima .poll ();
                    if (usedFlags [valueRecord .index]) {
                        continue;
                    }
                    if (auxMinima [valueRecord .index] != valueRecord .value) {
                        continue;
                    }
                    bestValue = valueRecord .value;
                    bestIndex = valueRecord .index;
                    break;
                }

                if (-1 == bestIndex) {
                    break;
                }

                usedFlags [bestIndex] = true;
                result += bestValue;

//                displayArray (auxMinima, usedFlags);
//                System .out .println (dataIndex + "  " + bestValue + "  " + result);
            }
        }

        return result;
    }

    @SuppressWarnings("unused")
    private static long testHeap () {
        int k, l, dataIndex, heapSize, valueIndex, value, auxIndex, nextAuxIndex, heapIndex;
        int bestValue, bestIndex, nextValue, childAuxIndex, childHeapIndex, childValue;
        long result;
        boolean flag;
        boolean [] usedFlags;
        int [] auxMinima, auxIndices, binaryHeap;

        dataIndex  = 0;
        result     = 0;
        usedFlags  = new boolean [workSize];
        auxMinima  = new int     [workSize];
        auxIndices = new int     [workSize];
        binaryHeap = new int     [workSize];
        auxIndex   = 0;

        while (dataSize > dataIndex) {

            Arrays .fill (usedFlags, false);
            Arrays .fill (auxMinima, Integer .MAX_VALUE);
            Arrays .fill (auxIndices, -1);
            heapSize = 0;

            for (k = 0; workSize > k; ++k) {

                for (l = 0; packSize > l && dataSize > dataIndex; ++l, ++dataIndex) {
                    valueIndex = testData_Indices [dataIndex];
                    if (usedFlags [valueIndex]) {
                        continue;
                    }
                    value = testData_Values  [dataIndex];
                    flag = true;
                    if (-1 == auxIndices [valueIndex]) {
                        auxIndex = heapSize;
                        ++heapSize;
                        flag = false;
                    } else if (auxMinima [valueIndex] > value) {
                        auxIndex = auxIndices [valueIndex];
                        flag = false;
                    }
                    if (flag) {
                        continue;
                    }
                    auxMinima [valueIndex] = value;
                    while (0 < auxIndex) {
                        nextAuxIndex = (auxIndex - 1) / 2;
                        heapIndex = binaryHeap [nextAuxIndex];
                        nextValue = auxMinima [heapIndex];
                        if (value > nextValue || value == nextValue && valueIndex >= heapIndex) {
                            break;
                        }
                        binaryHeap [auxIndex] = heapIndex;
                        auxIndices [heapIndex] = auxIndex;
                        auxIndex = nextAuxIndex;
                    }
                    binaryHeap [auxIndex] = valueIndex;
                    auxIndices [valueIndex] = auxIndex;
                }

                if (debug && advanced) {
                    displayArray (auxIndices);
                }

                if (0 == heapSize) {
                    break;
                }

                bestIndex = binaryHeap [0];
                bestValue = auxMinima [bestIndex];
                auxIndices [bestIndex] = -1;
                --heapSize;
                valueIndex = binaryHeap [heapSize];
                value = auxMinima [valueIndex];
                auxIndex = 0;
                //binaryHeap [0] = valueIndex;

                while (true) {
                    nextValue = value;
                    heapIndex = valueIndex;
                    nextAuxIndex = auxIndex;
                    childAuxIndex = 2 * auxIndex + 1;
                    if (heapSize > childAuxIndex) {
                        childHeapIndex = binaryHeap [childAuxIndex];
                        childValue = auxMinima [childHeapIndex];
                        if (nextValue > childValue || nextValue == childValue && heapIndex > childHeapIndex) {
                            nextValue = childValue;
                            heapIndex = childHeapIndex;
                            nextAuxIndex = childAuxIndex;
                        }
                    }
                    ++childAuxIndex;
                    if (heapSize > childAuxIndex) {
                        childHeapIndex = binaryHeap [childAuxIndex];
                        childValue = auxMinima [childHeapIndex];
                        if (nextValue > childValue || nextValue == childValue && heapIndex > childHeapIndex) {
                            heapIndex = childHeapIndex;
                            nextAuxIndex = childAuxIndex;
                        }
                    }
                    if (auxIndex == nextAuxIndex) {
                        break;
                    }
                    binaryHeap [auxIndex] = heapIndex;
                    auxIndices [heapIndex] = auxIndex;
                    auxIndex = nextAuxIndex;
                }
                binaryHeap [auxIndex] = valueIndex;
                auxIndices [valueIndex] = auxIndex;

                result += bestValue;
                usedFlags [bestIndex] = true;

                if (debug) {
                    if (advanced) {
                        displayArray (auxMinima, usedFlags);
                        displayArray (auxIndices);
                    }
                    System .out .println (dataIndex + "  " + bestIndex + "  " + bestValue + "  " + result);
                }
            }
        }

        return result;
    }

    private static void displayArray (int [] array, boolean [] flags) {
        int k, value;

        for (k = 0; workSize > k; ++k) {
            value = array [k];
            if (Integer .MAX_VALUE == value) {
                if (flags [k]) {
                    System .out .print (" ####");
                } else {
                    System .out .print ("   - ");
                }
            } else {
                if (flags [k]) {
                    System .out .print (String .format ("%4s<", ">" + value));
                } else {
                    System .out .print (String .format ("%4d ", value));
                }
            }
        }
        System .out .println ();
    }

    private static void displayArray (int [] array) {
        int k, value;

        for (k = 0; workSize > k; ++k) {
            value = array [k];
            if (-1 == value) {
                System .out .print ("   - ");
            } else {
                System .out .print (String .format ("%4d ", value));
            }
        }
        System .out .println ();
    }

    private static class ValueRecord implements Comparable <ValueRecord> {

        private int value, index;

        public ValueRecord (int argValue, int argIndex) {
            value = argValue;
            index = argIndex;
        }

        @Override
        public int compareTo (ValueRecord arg) {
            int difference = value - arg .value;
            if (0 != difference) {
                return difference;
            }
            return index - arg .index;
        }
    }
}