import javafx.util.Pair;

import java.util.*;
import java.util.function.Consumer;
import java.util.stream.Collectors;

import static java.lang.Math.max;

public class Main {

    private static final int FRACTIONAL_DENOMINATOR_TO_KEEP = 1000;

    /**
     * The predicate that determines if an item shall be removed from the list.
     * In this example we are looking for extreme cases, so we chose a predicate
     * that removes all but every 1000 items.
     *
     * @param i
     * @return true iff the item i shall be removed
     */
    private static boolean predicate(int i) {
        return i % FRACTIONAL_DENOMINATOR_TO_KEEP != 0;
    }

    public static void main(String[] args) {
        warmUpJit();
        computeAll();
    }

    private static void warmUpJit() {
        computeComparativeGraphData(1000, 10_000, 1000);  // compute and throw away results
    }

    private static void computeAll() {
        final int step = FRACTIONAL_DENOMINATOR_TO_KEEP;
        final int start = step;
        final int end = 150 * step;

        final Map<Integer, Pair<Long, Long>> results = computeComparativeGraphData(start, end, step);
        printResults("Actual times", results);
        System.out.println("  --- 8< ---");
        printResults("Normalized times", normalize(results));
    }

    private static void printResults(String title, Map<Integer, Pair<Long, Long>> results) {
        System.out.println(title);
        System.out.println("Length, Iterator, removeIf");

        results.entrySet().stream().sorted((e1, e2) -> e1.getKey() - e2.getKey())
                .forEach(entry -> {
                    final Pair<Long, Long> p = entry.getValue();
                    System.out.println("" + entry.getKey() + ", " +
                            p.getKey() + ", " +
                            p.getValue()
                    );
                });
    }

    /**
     * Normalize value pairs to make max values equal.
     *
     * @param results a Map from Integer to a Pair of Longs representing
     *                execution times for two different designs.
     *
     * @return a new map with normalized values, where max values are equal
     */
    private static Map<Integer, Pair<Long, Long>> normalize(Map<Integer, Pair<Long, Long>> results) {
        final Pair<Long, Long> maxValues = results.values().stream().
                reduce(new Pair<>(0L, 0L),
                        (s, v) -> new Pair<>(
                                max(s.getKey(), v.getKey()),
                                max(s.getValue(), v.getValue())
                        )
                );

        final double maxInteratorTime = maxValues.getKey().doubleValue();
        final double maxRemoveIfTime = maxValues.getValue().doubleValue();
        double factor = maxInteratorTime / maxRemoveIfTime;

        System.out.println("Iterator is " + factor + " times slower than removeIf()");

        double scalingFactor = factor * 0.5;  // we scale the faster times up half the way

        return results.entrySet().stream().
                collect(Collectors.toMap(
                        Map.Entry::getKey,
                        p -> new Pair<>(
                                p.getValue().getKey(),
                                (long) (p.getValue().getValue() * scalingFactor)
                        ))
                );
    }

    /**
     * Create a map from array size to a pair of execution times - (iterator, removeIf)
     *
     * @param start start array size
     * @param end ending array size
     * @param step step between sizes
     * @return a mapping (array size) -> (iterator execution time, removeIf execution time)
     */
    private static Map<Integer, Pair<Long, Long>> computeComparativeGraphData(int start, int end, int step) {
        Map<Integer, Pair<Long, Long>> results = new HashMap<>();
        for (int n = start; n <= end; n += step) {
            results.put(n, new Pair<>(timeIterator(n), timeRemoveIf(n)));
        }
        return results;
    }


    private static long timeRemoveIf(int n) {
        return timeMany(n, l -> l.removeIf(i -> predicate(i)));
    }

    private static long timeIterator(int n) {
        return timeMany(n, l -> {
                    for (Iterator<Integer> it = l.iterator(); it.hasNext();) {
                        if (predicate(it.next())) {
                            it.remove();
                        }
                    }
                }
        );
    }

    /**
     * Create and fill an array, then apply a consumer to all elements and measure average execution time
     *
     * @param size the size of the array to be created
     * @param filter the list consumer to be evaluated
     * @return average execution time in some unit of time (
     */
    private static long timeMany(int size, Consumer<List<Integer>> filter) {
        final int skipped = 5; // extreme values to be removed before averaging
        final int n = skipped * 8; // total number of runs

        long[] results = new long[n];
        for (int i=0; i<n; i++) {
            results[i] = timeOnce(buildList(size), filter);
        }
        Arrays.sort(results);

        long tailSum = Arrays.stream(results).skip(n - skipped).sum();
        long midAndTailSum = Arrays.stream(results).skip(skipped).sum();

        return midAndTailSum - tailSum;
    }

    private static List<Integer> buildList(int size) {
        ArrayList<Integer> numbers = new ArrayList<>(size);
        for (int i=0; i < size; i++) {
            numbers.add(i);
        }
        return numbers;
    }

    private static <T> long timeOnce(List<T> list, Consumer<List<T>> filter) {
        int lengthBefore = list.size();
        System.gc();
        long start = System.nanoTime();
        filter.accept(list);
        long time = System.nanoTime() - start;
        assert list.size() == lengthBefore / FRACTIONAL_DENOMINATOR_TO_KEEP;
        return time;
    }
}