Comment #0 by bearophile_hugs — 2015-01-18T13:25:00Z
This is part of randomCover code:
struct RandomCover(Range, UniformRNG = void)
if (isRandomAccessRange!Range && (isUniformRNG!UniformRNG || is(UniformRNG == void)))
{
private Range _input;
private bool[] _chosen;
private size_t _current;
private size_t _alreadyChosen = 0;
static if (is(UniformRNG == void))
{
this(Range input)
{
_input = input;
_chosen.length = _input.length;
if (_chosen.length == 0)
{
_alreadyChosen = 1;
}
}
}
...
auto randomCover(Range, UniformRNG)(Range r, auto ref UniformRNG rng)
if (isRandomAccessRange!Range && isUniformRNG!UniformRNG)
{
return RandomCover!(Range, UniformRNG)(r, rng);
}
auto randomCover(Range)(Range r)
if (isRandomAccessRange!Range)
{
return RandomCover!(Range, void)(r);
}
Currently randomCover can't be @nogc because of the random generator, but also because of that allocation of _chosen inside the struct constructor. To solve this problem I suggest to remove the allocation of _chosen from the struct constructor and move it inside the helper functions. And then add two more overloads for the helper functions, something like this:
auto randomCover(Range, UniformRNG)(Range r, auto ref UniformRNG rng)
if (isRandomAccessRange!Range && isUniformRNG!UniformRNG)
{
return RandomCover!(Range, UniformRNG)(r, rng, new bool[r.length]);
}
auto randomCover(Range)(Range r)
if (isRandomAccessRange!Range)
{
return RandomCover!(Range, void)(r, new bool[r.length]);
}
auto randomCover(Range, UniformRNG)(Range r, auto ref UniformRNG rng, bool[] buf) @nogc
if (isRandomAccessRange!Range && isUniformRNG!UniformRNG)
{
if (buf.length < r.length) {
// Is this correct in presence of chaining?
static immutable err = new Error("Not sufficient 'buf' size");
throw err;
}
return RandomCover!(Range, UniformRNG)(r, rng, buf[0 .. r.length]);
}
auto randomCover(Range)(Range r, bool[] buf) @nogc
if (isRandomAccessRange!Range)
{
if (buf.length < r.length) {
static immutable err = new Error("Not sufficient 'buf' size");
throw err;
}
return RandomCover!(Range, void)(r, buf[0 .. r.length]);
}
The two more overloads take an extra "buf" input, that will be used by the RandomCover. If the buf is not long enough, an error is raised.
Optionally randomCover could take a std.bitmanip.BitArray instead.
Comment #1 by bearophile_hugs — 2015-01-18T13:31:31Z
In many use cases you don't need allocations, if you reserve a size_t inside the RandomCover struct, and you use such size_t as a bit array, you can manage the cases where the input 'r' is up to 32 or 64 items long without need of any array buf.
Comment #2 by n8sh.secondary — 2018-08-10T21:42:18Z