import std.stdio;
import std.random;
import std.c.stdlib;

struct RandomNumbers(Rnd = Random)
{
    private int[] _items;
    private int _offset = 0;
    private Rnd _rnd;

    this(int max, Rnd rnd = Rnd.init, int[] buffer = null) // should be 'rnd = Rnd()' but doesn't work
    {
        _items = buffer;
        _items.length = max;

        _rnd = rnd;
        gen();
    }

    int head()
    {
        return at(_offset);
    }

    void next()
    {
        int len = _items.length - 1;
        if (len != 0) {
            _items[_offset] = at(len) - _offset;
            _items.length = len;
            gen();
        } else {
            _items.length = 0;
        }
    }

    bool empty()
    {
        return length == 0;
    }
    
    int length()
    {
        return _items.length;
    }
    
    private void gen()
    {
        _offset = _rnd.next() % length;
    }
    
    private int at(int index)
    {
        return index + _items[index];
    }
}

struct RandomItems(Range, Rnd = Random)
{
    private RandomNumbers!(Rnd) _gen;
    private Range _range;

  // bug: the following doesn't compile:
  //this(Range range, Rnd random = Rnd.init, typeof(range[0])[] buffer = null) 
    this(Range range, Rnd random = Rnd.init, typeof(_range[0])[] buffer = null) 
    {
        _range = range;
        _gen = RandomNumbers!(Rnd)(range.length, random, buffer);
    }

    typeof(_range[0]) head()
    {
        return _range[_gen.head];
    }

    void next()
    {
        _gen.next();
    }

    bool empty()
    {
        return _gen.empty;
    }
    
    int length()
    {
        return _gen.length;
    }
}

auto shuffledCopy(Range)(Range range)
{
    // Not an essential part - create a temporary buffer so that RandomItems don't allocate
    int* ptr = cast(int*)alloca(int.sizeof * range.length);
    int[] buffer = (ptr is null) ? new int[range.length] : ptr[0..range.length];

    // BUG: Uncomment the following line and it will crash at runtime:
    // Random rnd;
    auto gen = RandomItems!(Range)(range, Random.init, buffer);
    typeof(range[0])[] copy = new typeof(range[0])[range.length]; // TODO: allocate uninitialized memory block?

    foreach (ref elem; copy) {
        elem = gen.head;
        gen.next();
    }

    return copy;
}

void main()
{
    Random rnd;
    auto gen = RandomNumbers!(Random)(10, rnd); // allocates

    foreach (n; gen) {
        writefln(n);
    }

    writefln("----");

    auto items = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
    auto gen2 = RandomItems!(typeof(items))(items);

    foreach (n; gen2) {
        writefln(n);
    }
    
    writefln("----");
    
    auto shuffled = shuffledCopy(items);
    foreach (n; shuffled) {
        writefln(n);
    }
}