package com.crm.rely.backend.util;

import java.security.SecureRandom;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @Author houn
 * @Date 2023/8/11 14:49
 * @PackageName:com.crm.rely.backend.util
 * @ClassName: AliasMethodUtil
 * @Description: TODO
 */
public class AliasMethodUtil {

    /*
    The random
    number generator
    used to
    sample from
    the distribution.*/
    private final Random random;

    /* The probability and alias tables. */
    private final int[] alias;
    private final double[] probability;

    /**
     * Constructs a new AliasMethod to sample from a discrete distribution and
     * hand back outcomes based on the probability distribution.
     * <p/>
     * Given as input a list of probabilities corresponding to outcomes 0, 1,
     * ..., n - 1, this constructor creates the probability and alias tables
     * needed to efficiently sample from this distribution.
     *
     * @param probabilities The list of probabilities.
     */
    public AliasMethodUtil(List<Double> probabilities) {
        this(probabilities, new Random());
    }

    /**
     * Constructs a new AliasMethod to sample from a discrete distribution and
     * hand back outcomes based on the probability distribution.
     * <p/>
     * Given as input a list of probabilities corresponding to outcomes 0, 1,
     * ..., n - 1, along with the random number generator that should be used
     * as the underlying generator, this constructor creates the probability
     * and alias tables needed to efficiently sample from this distribution.
     *
     * @param probabilities The list of probabilities.
     * @param random        The random number generator
     */
    public AliasMethodUtil(List<Double> probabilities, Random random) {
        /* Begin by doing basic structural checks on the inputs. */
        if (probabilities == null || random == null) {
            throw new NullPointerException();
        }
        if (probabilities.size() == 0) {
            throw new IllegalArgumentException("Probability vector must be nonempty.");
        }

        /* Allocate space for the probability and alias tables. */
        probability = new double[probabilities.size()];
        alias = new int[probabilities.size()];

        /* Store the underlying generator. */
        this.random = random;

        /* Compute the average probability and cache it for later use. */
        double average = 1.0 / probabilities.size();

        /* Make a copy of the probabilities list, since we will be making
         * changes to it.
         */
        probabilities = new ArrayList<Double>(probabilities);

        /* Create two stacks to act as worklists as we populate the tables. */
        Deque<Integer> small = new ArrayDeque<Integer>();
        Deque<Integer> large = new ArrayDeque<Integer>();

        /* Populate the stacks with the input probabilities. */
        for (int i = 0; i < probabilities.size(); ++i) {
            /* If the probability is below the average probability, then we add
             * it to the small list; otherwise we add it to the large list.
             */
            if (probabilities.get(i) >= average) {
                large.add(i);
            } else {
                small.add(i);
            }
        }

        /* As a note: in the mathematical specification of the algorithm, we
         * will always exhaust the small list before the big list.  However,
         * due to floating point inaccuracies, this is not necessarily true.
         * Consequently, this inner loop (which tries to pair small and large
         * elements) will have to check that both lists aren't empty.
         */
        while (!small.isEmpty() && !large.isEmpty()) {
            /* Get the index of the small and the large probabilities. */
            int less = small.removeLast();
            int more = large.removeLast();

            /* These probabilities have not yet been scaled up to be such that
             * 1/n is given weight 1.0.  We do this here instead.
             */
            probability[less] = probabilities.get(less) * probabilities.size();
            alias[less] = more;

            /* Decrease the probability of the larger one by the appropriate
             * amount.
             */
            probabilities.set(more,
                    (probabilities.get(more) + probabilities.get(less)) - average);

            /* If the new probability is less than the average, add it into the
             * small list; otherwise add it to the large list.
             */
            if (probabilities.get(more) >= 1.0 / probabilities.size()) {
                large.add(more);
            } else {
                small.add(more);
            }
        }

        /* At this point, everything is in one list, which means that the
         * remaining probabilities should all be 1/n.  Based on this, set them
         * appropriately.  Due to numerical issues, we can't be sure which
         * stack will hold the entries, so we empty both.
         */
        while (!small.isEmpty()) {
            probability[small.removeLast()] = 1.0;
        }
        while (!large.isEmpty()) {
            probability[large.removeLast()] = 1.0;
        }
    }

    /**
     * Samples a value from the underlying distribution.
     *
     * @return A random value sampled from the underlying distribution.
     */
    public int next() {
        /* Generate a fair die roll to determine which column to inspect. */
        int column = random.nextInt(probability.length);

        /* Generate a biased coin toss to determine which option to pick. */
        boolean coinToss = random.nextDouble() < probability[column];

        /* Based on the outcome, return either the column or its alias. */
       /* Log.i("1234","column="+column);
        Log.i("1234","coinToss="+coinToss);
        Log.i("1234","alias[column]="+coinToss);*/
        return coinToss ? column : alias[column];
    }

    public static void main(String[] args) {
        TreeMap<Integer, Double> map = new TreeMap<Integer, Double>();
//        map.put(0, 0.0);
//        map.put(1, 0.889);
//        map.put(5, 0.08);
//        map.put(10, 0.021);
//        map.put(20, 0.01);
//        map.put(50, 0.0);
//        map.put(100, 0.0);
//        map.put(200, 0.0);

//        map.put(0, 0.55);
//        map.put(1, 0.392);
//        map.put(5, 0.035);
//        map.put(10, 0.012);
//        map.put(20, 0.008);
//        map.put(50, 0.003);
//        map.put(100, 0.0);
//        map.put(200, 0.0);

        map.put(0, 0.65);
        map.put(1, 0.33);
        map.put(5, 0.01);
        map.put(10, 0.005);
        map.put(20, 0.003);
        map.put(50, 0.002);
        map.put(100, 0.0);
        map.put(200, 0.0);

        List<Double> list = new ArrayList<Double>(map.values());
        List<Integer> gifts = new ArrayList<Integer>(map.keySet());

        AliasMethodUtil method = new AliasMethodUtil(list, new SecureRandom());

        Map<Integer, AtomicInteger> resultMap = new HashMap<Integer, AtomicInteger>();
        Integer tAmount = 0;
        for (int i = 0; i < 100; i++) {
            Integer amount = 0;
            for (int j = 0; j < 10; j++) {
                int index = method.next();
                Integer key = gifts.get(index);
                if (!resultMap.containsKey(key)) {
                    amount += key;
                }
            }
            tAmount += amount;
            System.out.println(amount);
        }
        System.out.println(tAmount / 100.0);


//        for (int i = 0; i < 10000000; i++) {
//            int index = method.next();
//            Integer key = gifts.get(index);
//            if (!resultMap.containsKey(key)) {
//                resultMap.put(key, new AtomicInteger());
//            }
//            resultMap.get(key).incrementAndGet();
//        }
//        for (Integer key : resultMap.keySet()) {
//            System.out.println(key + "==" + resultMap.get(key));
//        }

    }
}
