import std.range, std.array, std.traits, std.exception, std.random;

/**
Returns a delegate that generates random numbers similarly to $(D dice()) but
in $(BIGOH log N) time per number generated, where $(D N) is the number of
possible values.  In exchange, it requires $(BIGOH N) auxiliary space and
$(BIGOH N) upfront initialization time.
*/
size_t delegate() fastDice(R)(R range)
if(isInputRange!R && isNumeric!(ElementType!R)) {
    auto sorted = makeSortedSums(range);

    size_t generate() {
        return generateFastDice(rndGen, sorted);
    }

    return &generate;
}

/// Ditto
size_t delegate() fastDice(R, Random)(R range, Random gen)
if(isInputRange!R && isNumeric!(ElementType!R)) {
    auto sorted = makeSortedSums(range);

    size_t generate() {
        return generateFastDice(gen, sorted);
    }

    return &generate;
}

private size_t generateFastDice(Random, R)(ref Random gen, R range) {
    immutable point = uniform(0.0, cast(double) range.back, gen);
    return range.lowerBound(point).length;
}

// Helper function to make the range of sums.
private auto makeSortedSums(R)(R range) {
    auto sums = array(range);
    foreach(i, ref elem; sums) {
        enforce(elem >= 0, "Can't have negative probabilities for fastDice.");
        elem += sums[i - 1];
    }

    return assumeSorted(sums);
}

unittest {
    auto i = fastDice([0.0, 100.0])();
    assert(i == 1);
    i = fastDice([100.0, 0.0])();
    assert(i == 0);
}