Comment #0 by peter.alexander.au — 2014-02-17T12:20:14Z
The constraints says it requires bidirectional, but it actually requires random access due to this line:
reverse(takeExactly(retro(range), n));
'reverse' requires a bidirectional range, but 'takeExactly' on a bidirectional range returns a forward range. You need to provide a random access range to 'takeExactly' to get bidirectional, so this becomes a requirement of 'nextPermutation'.
nextPermutation must be modified to support bidirectional ranges. Changing the constraint to random access is not an acceptable fix.
Here's a simple test case where a bidirectional range fails:
---------------------
import std.algorithm, std.array;
struct MyRange
{
int[] a = [1, 2, 3];
@property
{
auto ref front() { return a.front; }
auto ref back() { return a.back; }
auto empty() { return a.empty; }
auto save() { return MyRange(a); }
}
void popFront() { a.popFront(); }
void popBack() { a.popBack(); }
}
void main()
{
MyRange r;
nextPermutation(r);
}
---------------------
Comment #1 by peter.alexander.au — 2014-02-18T12:51:15Z
BTW, you may already know this, but it's impossible to solve this with the current range primitives. See the discussion here:
http://www.digitalmars.com/d/archives/digitalmars/D/Retrieving_the_traversed_range_116085.html#N116085
To summarise the discussion: it is impossible currently, and Andrei recommends two approaches:
1. Just make it random access only for now.
2. Define a new primitive: allBefore, like this:
R allBefore(R)(R all, R tail) if (isRandomAccessRange!R && hasLength!R)
{
// assume tail starts somewhere inside all and ends where all ends
enforce(all.length >= tail.length);
return all[0 .. all.length - tail.length);
}
R allBefore(R)(R all, R tail)
if (isBidirectionalRange!R &&
is(typeof(all.allBeforeImpl(tail)) : R))
{
return all.allBeforeImpl(tail);
}
And require that for nextPermutation
Comment #2 by hsteoh — 2014-02-18T13:14:25Z
Hmm this sucks. It didn't occur to me that takeN on a bidirectional range doesn't return a bidirectional range. :-( In retrospect, it makes sense (takeN doesn't know the internals of the range, so it has no way to know what .back and .popBack should do when only the first N elements are desired).
Comment #3 by andrei — 2014-08-11T15:07:30Z
It's easy to implement allBefore to return a new range type distinct (e.g. Voldemort) from R. That range would keep the two ranges as state and would say it's empty when whole.sameHead(right).
Comment #4 by peter.alexander.au — 2014-08-11T15:12:47Z
(In reply to Andrei Alexandrescu from comment #3)
> It's easy to implement allBefore to return a new range type distinct (e.g.
> Voldemort) from R. That range would keep the two ranges as state and would
> say it's empty when whole.sameHead(right).
If I've understood you correctly, the range you describe can't be bidirectional, which is what we need here.
Comment #5 by andrei — 2014-08-11T15:16:47Z
Oh, yah, never mind.
Comment #6 by hsteoh — 2014-09-12T18:21:07Z
Well, I'm out of ideas. Seems the only way around this is to make nextPermutation require a random access range. :-(
Comment #7 by robert.schadek — 2024-12-01T16:20:15Z