PHP Implementation of Vose's Alias Method

alias.php

<?php
    /**
     * Implementation of Vose's Alias Method
     *
     * @param array $probabilities An array of probabilities
     *
     * @return int
     */
    public function aliasMethod(array $probabilities)
    {
        $small = $large = $prob = $alias = [];
        $n = count($probabilities);

        $probabilities = array_map(function($p) use ($n) {
            return $p * $n; // Scale each probability by n
        }, $probabilities);

        for ($i = 0; $i < $n; ++$i) {
            if ($probabilities[$i] < 1) {
                $small[] = $i;
            } else {
                $large[] = $i;
            }
        }

        while (!empty($small) && !empty($large)) {
            $l = array_shift($small);
            $g = array_shift($large);

            $prob[$l] = $probabilities[$l];
            $alias[$l] = $g;

            $probabilities[$g] = ($probabilities[$g] + $probabilities[$l]) - 1;
            if ($probabilities[$g] < 1) {
                $small[] = $g;
            } else {
                $large[] = $g;
            }
        }

        while (!empty($large)) {
            $prob[array_shift($large)] = 1;
        }

        while (!empty($small)) {
            $prob[array_shift($small)] = 1;
        }

        $i = mt_rand(0, $n-1);
        $coinToss = 1 * mt_rand() / mt_getrandmax() < $prob[$i];

        return $coinToss ? $i : $alias[$i];
    }