Another implementation of std.random.RandomCover. It is faster than std.random.RandomCover in average time.

randomcover.d

/**
 * Another implementation of std.random.RandomCover
 *
 * Execution time for popFront (n: length):
 *  std.random: O(n)
 *  this      : O(1)
 *
 * Memory consumption:
 *  std.random: O(n)
 *  this      : O(n)
 */
struct RandomCover(Range, Random)
if(isRandomAccessRange!Range && hasLength!Range && isUniformRNG!Random)
{
    private Range _input;
    private Random _rnd;
    private size_t[] _rest;
    private size_t _current;
    private bool _empty;

    this(Range input, Random rnd)
    {
        _input = input;
        _rnd = rnd;
        _rest = iota(cast(size_t)input.length).array();
        popFront();
    }

    @property size_t length() const pure nothrow
    {
        return _empty ? 0 : _rest.length+1;
    }

    @property auto ref front()
    {
        return _input[_current];
    }

    void popFront()
    {
        if (_rest.empty)
        {
            _empty = true;
            return;
        }
        import std.algorithm;
        auto idx = uniform(0, _rest.length, _rnd);
        _current = _rest[idx];
        swap(_rest[idx], _rest[$-1]);
        _rest.length--;
    }

    @property typeof(this) save()
    {
        auto ret = this;
        ret._input = _input.save;
        ret._rnd = _rnd.save;
        return ret;
    }

    @property bool empty() const pure nothrow { return _empty; }
}

/// Ditto
RandomCover!(Range, Random) randomCover(Range, Random)(Range r, Random rnd)
if(isRandomAccessRange!Range && hasLength!Range && isUniformRNG!Random)
{
    return typeof(return)(r, rnd);
}

unittest
{
    import std.random: Random, unpredictableSeed;
    import std.algorithm;
    import std.conv;

    {
        int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8 ];
        auto rnd = Random(unpredictableSeed);
        RandomCover!(int[], Random) rc = randomCover(a, rnd);
        static assert(isForwardRange!(typeof(rc)));

        int[] b = new int[9];
        uint i;
        foreach (e; rc)
        {
            //writeln(e);
            b[i++] = e;
        }
        sort(b);
        assert(a == b, text(b));
    }

    {
        int[] a = [1];
        auto rnd = Random(unpredictableSeed);
        auto rc = randomCover(a, rnd);
        auto b = rc.array();
        assert(a == b, text(b));
    }
}