package org.roaringbitmap.buffer;

import me.lemire.integercompression.synth.ClusteredDataGenerator;
import org.apache.commons.math3.distribution.IntegerDistribution;
import org.apache.commons.math3.distribution.UniformIntegerDistribution;
import org.apache.commons.math3.random.Well19937c;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;

import java.nio.ShortBuffer;
import java.util.Arrays;
import java.util.concurrent.TimeUnit;

/**
 * The experiment to test the threshold when it is worth to use galloping strategy of intersecting sorted lists.
 * It allows to generate sample lists where first is *param* times bigger than other one.
 * Both lists can be generated used uniform or clustered distribution.
 * The methodology and results are presented in the issue #63 on Github.
 */
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@State(Scope.Benchmark)
public class UtilBenchmark {

    @Param({"0", "1"})           // use {"0", "1"} to test both uniform and clustered combinations
    public int smallType;   // 0 - uniform, 1 - clustered
    @Param({"0", "1"})           // use {"0", "1"} to test both uniform and clustered combinations
    public int bigType;     // 0 - uniform, 1 - clustered
    @Param({"0", "1", "2", "3", "4"})           // use {"0", "1", "2"} for three experiments. Update GENERATE_EXAMPLES if changing this
    public int index;
    @Param({"10" ,"15", "21", "23", "25", "26", "28", "30", "35", "40", "60", "90"})          // use {"20", "25", "30"} to check different thresholds
    public int param;

    private static final int GENERATE_EXAMPLES = 5;
    public static BenchmarkData data;

    @Setup
    public void setup() {
        data = BenchmarkDataGenerator.generate(param, GENERATE_EXAMPLES, smallType, bigType);
    }

    @Benchmark
    public void galloping() {
        BenchmarkContainer small = data.small[index];
        BenchmarkContainer big = data.big[index];
        BufferUtil.unsignedOneSidedGallopingIntersect2by2(small.content, small.length, big.content, big.length, data.dest);
    }

    @Benchmark
    public void local() {
        BenchmarkContainer small = data.small[index];
        BenchmarkContainer big = data.big[index];
        BufferUtil.unsignedLocalIntersect2by2(small.content, small.length, big.content, big.length, data.dest);
    }
}

class BenchmarkData {
    BenchmarkData(BenchmarkContainer[] small, BenchmarkContainer[] big) {
        this.small = small;
        this.big = big;
        this.dest = new short[Short.MAX_VALUE];
    }

    final BenchmarkContainer[] small;
    final BenchmarkContainer[] big;
    final short[] dest;
}

class BenchmarkContainer {
    BenchmarkContainer(short[] content) {
        this.content = ShortBuffer.wrap(content);
        this.length = content.length;
    }

    final ShortBuffer content;
    final int length;
}

/**
 * Deterministic generator for benchmark data.
 * For given *param* it generates *howmany* entries
 */
class BenchmarkDataGenerator {
    static BenchmarkData generate(int param, int howMany, int smallType, int bigType) {
        IntegerDistribution ud = new UniformIntegerDistribution(new Well19937c(param + 17), Short.MIN_VALUE, Short.MAX_VALUE);
        ClusteredDataGenerator cd = new ClusteredDataGenerator();
        IntegerDistribution p = new UniformIntegerDistribution(new Well19937c(param + 123), SMALLEST_ARRAY, BIGGEST_ARRAY / param);
        BenchmarkContainer[] smalls = new BenchmarkContainer[howMany];
        BenchmarkContainer[] bigs = new BenchmarkContainer[howMany];
        for (int i = 0; i < howMany; i++) {
            int smallSize = p.sample();
            int bigSize = smallSize * param;
            short[] small = smallType == 0 ? generateUniform(ud, smallSize) : generateClustered(cd, smallSize);
            short[] big = bigType == 0 ? generateUniform(ud, bigSize) : generateClustered(cd, bigSize);
            smalls[i] = new BenchmarkContainer(small);
            bigs[i] = new BenchmarkContainer(big);
        }
        return new BenchmarkData(smalls, bigs);
    }

    private static short[] intArrayToShortArraySorted(int[] source) {
        short[] result = new short[source.length];
        for (int i = 0; i < source.length; i++) {
            result[i] = (short) source[i];
        }
        Arrays.sort(result);
        return result;
    }

    private static short[] generateClustered(ClusteredDataGenerator cd, int howMany) {
        int[] half1raw = cd.generateClustered(howMany / 2, Short.MAX_VALUE);
        for (int i = 0; i < half1raw.length; i++) {
            half1raw[i] = -half1raw[i];
        }
        short[] half1 = intArrayToShortArraySorted(half1raw);
        short[] half2 = intArrayToShortArraySorted(cd.generateClustered(howMany / 2, Short.MAX_VALUE));
        short[] result = new short[half1.length + half2.length];
        System.arraycopy(half1, 0, result, 0, half1.length);
        System.arraycopy(half2, 0, result, half1.length, half2.length);
        return result;
    }

    private static short[] generateUniform(IntegerDistribution ud, int howMany) {
        return intArrayToShortArraySorted(ud.sample(howMany));
    }

    private final static int SMALLEST_ARRAY = 2;
    private final static int BIGGEST_ARRAY = 4096;
}



@@ -1558,16 +1558,41 @@
 %223%22, %224%22
+, %225%22, %226%22, %227%22, %228%22, %229%22
 %7D)      
@@ -1723,60 +1723,60 @@
 m(%7B%22
-10%22 ,%2215
+25%22, %2226
 %22, %222
-1
+8
 %22, %22
-2
 3
+0
 %22, %22
-25
+31
 %22, %22
+3
 2
-6
 %22, %22
-28
+33
 %22, %223
-0
+4
 %22, %2235%22,
  %2240
@@ -1775,16 +1775,22 @@
 35%22,
+ %2238%22,
  %2240%22, %22
 60%22,
@@ -1789,15 +1789,27 @@
 %22, %22
-60
+44
 %22, %22
-9
+49%22, %2255%22, %226
 0%22%7D)
@@ -1946,17 +1946,18 @@
 MPLES = 
-5
+10
 ;%0A    pu

verify most possible cases