<?php

/**
 * 加权随机算法
 * aliases为桶列表.
 * CLASS WeightRandom
 * 使用方式1 $obj->load($data)->initAliases()->getRandom()
 * 使用方式2 $obj->load($data)->setAliases($aliases)->getRandom, 其中 $aliases 可使用 getAliases 获取, 要获取需先执行 initAliases. 此功能可配合跨请求缓存使用
 */
class WeightRandom
{
    public $aliases = [];
    private $keys = []; // 键的数组
    private $vals = []; // 值的数组

    /**
     * 加载数据
     * @param array $data
     * @return $this
     */
    public function load(array $data) {
        $this->keys = array_keys($data);
        $this->vals = array_values($data);
        return $this;
    }

    /**
     * 计算 aliases
     * @return $this
     */
    public function initAliases() {
        // 初始化别名表.在多次抽取不放回情况下很有必要.
        $this->aliases = [];

        $data = $this->vals;
        $length = count($data);
        // 小于两个的情况懒得处理.直接抛错误了.小于两个就是1个.调用方直接返回即可
        if($length < 2) {
            throw new \Exception('数量过少,无法筛选');
        }

        // 整理数据
        $total = array_sum($data);
        $listSmall = $listBig = [];
        foreach($data as $k=>$v) {
            // 元素除以总数为百分比.乘以长度可以达到最终结果为每个桶都足够1.
            $v = $v / $total * $length;
            // 一条数据.小于1放入小值列表.大于1放入大值列表
            $info = [$k, $v];
            if($v <= 1) {
                $listSmall[] = $info;
            } else {
                $listBig[] = $info;
            }
        }

        // 循环.放入桶中.
        // 要求每个桶的值最多有两个.桶内所有值的和为1.这样可以随机取出每个桶.
        // 桶内的值两部分组成.[0]=key,[1]=0到1范围内的权重
        // 这样计算的时候.先随机取桶.然后生成0到1的随机数.与桶内的值做判断.确定取第一个值还是第二个值
        $indexSmall = $indexBig = 0;
        for($i=0; $i<$length; $i++) {
            if(empty($listBig)) {
                // 如果没有big列表. 则表示不需要整理.独占一个桶.
                // 注意,中断程序
                $nowSmall = $listSmall[$indexSmall];
                $this->aliases[$i][] = [$nowSmall[0], 1];
                break;
            }

            if(empty($listSmall)) {
                // 如果没有small列表. 则表示不需要整理.独占一个桶.
                // 注意,中断程序
                $nowBig = $listBig[$indexBig];
                $this->aliases[$i][] = [$nowBig[0], 1];
                break;
            }

            $nowSmall = $listSmall[$indexSmall];
            // 先将当前小值写入桶列表
            $this->aliases[$i][] = $nowSmall;

            // 计算需要补全的另一个值.从大值里面获取.
            $nowBig = $listBig[$indexBig];
            $nowBigDiff = 1 - $nowSmall[1];
            $this->aliases[$i][] = [$nowBig[0], $nowBigDiff];

            // 重新计算大值.如果小于1.放入小值列表(大值列表删除).否则改变值后.依然在大值列表中.
            $nowBig[1] = $nowBig[1] - $nowBigDiff;
            if($nowBig[1] <= 1) {
                $listSmall[] = $nowBig;
                unset($listBig[$indexBig]);
                $indexBig++;
            } else {
                $listBig[$indexBig] = $nowBig;
            }
            unset($listSmall[$indexSmall]);
            $indexSmall++;
        }
        return $this;
    }

    /**
     * 设置 aliases 列表
     * @param array $aliases
     * @return $this
     */
    public function setAliases(array $aliases) {
        $this->aliases = $aliases;
        return $this;
    }

    /**
     * 获取 aliases 列表
     * @return array
     */
    public function getAliases() {
        return $this->aliases;
    }

    public function getRandom() {
        // 随意取一个桶.
        $nowKey = array_rand($this->aliases);
        $now = $this->aliases[$nowKey];

        // 计算一个0-1的随机数,然后与桶内的第一个值做判断.小于第一个值则选第一个值.否则选第二个值.
        $random = mt_rand() / mt_getrandmax();

        if($random <= $now[0][1]) {
            $indexKey = $now[0][0];
        } else {
            $indexKey = $now[1][0];
        }
        $key = $this->keys[$indexKey];
        return $key;
    }
}