summaryrefslogtreecommitdiff
path: root/lib/iter
diff options
context:
space:
mode:
authorQuentin Carbonneaux <quentin@c9x.me>2018-01-15 21:11:02 +0000
committerOri Bernstein <ori@markovcorp.com>2018-01-15 14:59:50 -0800
commit012c761ef5952366fe4c9be95ad8aa250afe6154 (patch)
tree6975e47d783ce18e57c9c59f15f86a53ffd5df9d /lib/iter
parent8aef13f0d3a760760a3843245f6d5b1f62c2a142 (diff)
downloadmc-012c761ef5952366fe4c9be95ad8aa250afe6154.tar.gz
Fix iter.byperm when there are duplicates.
Eh, I'm trying to get back in business. Cheers.
Diffstat (limited to 'lib/iter')
-rw-r--r--lib/iter/perm.myr17
-rw-r--r--lib/iter/test/perm.myr17
2 files changed, 27 insertions, 7 deletions
diff --git a/lib/iter/perm.myr b/lib/iter/perm.myr
index 2105463..0ac8cb6 100644
--- a/lib/iter/perm.myr
+++ b/lib/iter/perm.myr
@@ -47,12 +47,12 @@ impl iterable permiter(@a) -> @a[:] =
if j == 0
-> false
;;
- match itp.cmp(seq[j - 1], seq[j])
- | `std.After: j--
- | _: break
+ j--
+ match itp.cmp(seq[j], seq[j + 1])
+ | `std.Before: break
+ | _:
;;
;;
- j--
/*
Find highest i s.t. seq[j] < seq[i]. This
@@ -62,9 +62,12 @@ impl iterable permiter(@a) -> @a[:] =
*/
i = seq.len - 1
while true
- if i <= j
- -> false
- ;;
+ /*
+ By the previous loop, we know that
+ seq[j] < seg[j + 1], thus, in this loop,
+ we always have j + 1 <= i, and the array
+ accesses are always in bounds.
+ */
match itp.cmp(seq[j], seq[i])
| `std.Before: break
| _: i--
diff --git a/lib/iter/test/perm.myr b/lib/iter/test/perm.myr
index cfebb03..5e80a87 100644
--- a/lib/iter/test/perm.myr
+++ b/lib/iter/test/perm.myr
@@ -8,6 +8,7 @@ const main = {
[.name = "byperm-01", .fn = byperm01],
[.name = "byperm-02", .fn = byperm02],
[.name = "byperm-03", .fn = byperm03],
+ [.name = "byperm-04", .fn = byperm04],
][:])
}
@@ -52,3 +53,19 @@ const byperm03 = {c
var actual : byte[:] = std.sbfin(sb)
testr.check(c, std.eq(expected, actual), "expected “{}”, got “{}”", expected, actual)
}
+
+const byperm04 = {c
+ var v : int[:] = [ 0, 3, 1, 1 ][:]
+ var nperm = 0
+
+ for w : iter.byperm(v, std.numcmp)
+ nperm++
+ ;;
+
+ /*
+ There are 24 permutations for 4 elements, but we get only
+ half because two elements are equal.
+ */
+ const expected = 12
+ testr.check(c, std.eq(expected, nperm), "expected “{}”, got “{}”", expected, nperm)
+}