<?php

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

    /**
     * 加载数据
     * @param array $data
     * @return $this
     */
    public function load(array $data) {
        $this->keys = $this->vals = [];
        foreach($data as $key=>$val) {
            $this->keys[] = $key;
            $this->vals[] = $val;
        }
        return $this;
    }

    /**
     * 计算 aliases
     * @return $this
     */
    public function initAliases() {
        $data = $this->vals;
        $sumWeight = array_sum($data);
        $length = count($data);
        $this->_length = $length;
        $avg = $sumWeight / $length;

        $aliases = [];
        $listSmall = [];
        $listBig = [];
        $i=0;
        foreach($data as $v) {
            $aliases[] = [1, false];
            if($v < $avg) {
                $listSmall[] = [$i, $v / $avg];
            } else {
                $listBig[] = [$i, $v / $avg];
            }
            $i++;
        }

        $indexSmall = 0;
        $indexBig = 0;
        if(empty($listSmall)) {
            // 当权重全部相同时候.此代码触发.因为全部相同时候 listSmall 为空
            $listSmall = array_splice($listBig, 0, count($listBig) / 2);
        }
        $nowSmall = $listSmall[$indexSmall];
        $nowBig = $listBig[$indexBig];
        while($nowSmall and $nowBig) {
            $aliases[$nowSmall[0]] = [$nowSmall[1], $nowBig[0]];
            $nowBig = [$nowBig[0], $nowBig[1] - (1 - $nowSmall[1])];

            if($nowBig[1] < 1) {
                $nowSmall = $nowBig;
                $indexBig++;
                if(empty($listBig[$indexBig])) {
                    break;
                }
                $nowBig = $listBig[$indexBig];
            } else {
                $indexSmall++;
                if(empty($listSmall[$indexSmall])) {
                    break;
                }
                $nowSmall = $listSmall[$indexSmall];
            }
        }

        $this->aliases = $aliases;
        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() {
        $r = $this->_randomFloat(0, $this->_length-1);
        $i = floor($r);
        $now = $this->aliases[$i];

        $odds = $now[0];
        $alias= $now[1];

        if(($r-$i) > $odds) {
            return $this->keys[$alias];
        } else {
            return $this->keys[$i];
        }
    }

    private function _randomFloat($min = 0, $max = 1) {
        return $min + mt_rand() / mt_getrandmax() * ($max - $min);
    }
}