Bug 13594 – std.algorithm.nextPermutation should accept ranges of lvalues
Status
RESOLVED
Resolution
FIXED
Severity
normal
Priority
P1
Component
phobos
Product
D
Version
D2
Platform
x86
OS
Windows
Creation time
2014-10-10T10:13:00Z
Last change time
2015-02-18T03:39:37Z
Keywords
pull
Assigned to
nobody
Creator
bearophile_hugs
Comments
Comment #0 by bearophile_hugs — 2014-10-10T10:13:00Z
This is correct code:
void main() {
import std.stdio: writeln;
import std.algorithm: nextPermutation;
int[] a = [1, 2, 3];
do {
a.writeln;
} while (a.nextPermutation);
}
In many cases in my code the number of items to permute is known at compile-time, so for both memory efficiency and to not throw away precious compile-time knowledge of the array length, I'd like to permute a fixed-length array too:
void main() {
import std.stdio: writeln;
import std.algorithm: nextPermutation;
int[3] a = [1, 2, 3];
do {
a.writeln;
} while (a.nextPermutation);
}
But this is refused by dmd 2.067apha:
test.d(7,15): Error: template std.algorithm.nextPermutation cannot deduce function from argument types !()(int[3]), candidates are:
...\dmd2\src\phobos\std\algorithm.d(13186,6): std.algorithm.nextPermutation(alias less = "a<b", BidirectionalRange)(ref BidirectionalRange range) if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange)
And even slicing (a common workaround for silly Phobos functions that force me to throw away the compile-time knowledge of the array length) can't be used because nextPermutation takes its argument by reference:
void main() {
import std.stdio: writeln;
import std.algorithm: nextPermutation;
int[3] a = [1, 2, 3];
do {
a.writeln;
} while (a[].nextPermutation);
}
test.d(7,17): Error: template std.algorithm.nextPermutation cannot deduce function from argument types !()(int[]), candidates are:
...\dmd2\src\phobos\std\algorithm.d(13186,6): std.algorithm.nextPermutation(alias less = "a<b", BidirectionalRange)(ref BidirectionalRange range) if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange)
So I'd like nextPermutation to accept a fixed-size array, because there's nothing in a permutation algorithm that requires it to have run-time length of its random-access input. Alternatively, I'd like nextPermutation to take the dynamic array by value (and not mutate the length but only the contents positions with swaps).
The permutation algorithm needs to iterate over subarrays of varying lengths anyway, so losing the compile-time length of the overall array isn't that big of a deal.
Comment #4 by schveiguy — 2014-10-31T19:54:38Z
I'm changing the requirements. Bearophile's second attempt with the slice operator should compile. There is no need to require the range itself to be an lvalue, just that its elements are lvalues.
I also consider it a bug that this isn't the case.
Comment #5 by github-bugzilla — 2014-11-02T13:47:28Z