Index: test/codegen/corelib/shuffle_test.dart |
diff --git a/test/codegen/corelib/shuffle_test.dart b/test/codegen/corelib/shuffle_test.dart |
new file mode 100644 |
index 0000000000000000000000000000000000000000..536072d3c13fcdcfc21ee4c194d6924696a43817 |
--- /dev/null |
+++ b/test/codegen/corelib/shuffle_test.dart |
@@ -0,0 +1,126 @@ |
+// Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file |
+// for details. All rights reserved. Use of this source code is governed by a |
+// BSD-style license that can be found in the LICENSE file. |
+ |
+// Dart test for List.shuffle. |
+library shuffle_test; |
+import "dart:typed_data"; |
+import "dart:math" show Random; |
+import "package:expect/expect.dart"; |
+ |
+main() { |
+ List mkList(int n) => new List.generate(n, (x) => x); |
+ |
+ for (int size in [0, 1, 2, 3, 7, 15, 99, 1023]) { |
+ List numbers = new List.generate(size, (x) => x); |
+ testShuffle(numbers.toList(growable: true)); |
+ testShuffle(numbers.toList(growable: false)); |
+ testShuffle(new Uint32List(size)..setAll(0, numbers)); |
+ testShuffle(new Int32List(size)..setAll(0, numbers)); |
+ testShuffle(new Uint16List(size)..setAll(0, numbers)); |
+ testShuffle(new Int16List(size)..setAll(0, numbers)); |
+ // Some numbers will be truncated in the following two. |
+ testShuffle(new Uint8List(size)..setAll(0, numbers)); |
+ testShuffle(new Int8List(size)..setAll(0, numbers)); |
+ testShuffle(numbers.map((x) => "$x").toList()); |
+ } |
+ |
+ // Check that it actually can keep the same list (regression test). |
+ List l = [1, 2]; |
+ success: { |
+ for (int i = 0; i < 266; i++) { |
+ int first = l.first; |
+ l.shuffle(); |
+ if (l.first == first) break success; // List didn't change. |
+ } |
+ // Chance of changing 266 times in a row should be < 1:1e80. |
+ Expect.fail("List changes every time."); |
+ } |
+ |
+ testRandom(); |
+} |
+ |
+void testShuffle(list) { |
+ List copy = list.toList(); |
+ list.shuffle(); |
+ if (list.length < 2) { |
+ Expect.listEquals(copy, list); |
+ return; |
+ } |
+ // Test that the list after shuffling has the same elements as before, |
+ // without considering order. |
+ Map seen = {}; |
+ for (var e in list) { |
+ seen[e] = seen.putIfAbsent(e, () => 0) + 1; |
+ } |
+ for (var e in copy) { |
+ int remaining = seen[e]; |
+ remaining -= 1; // Throws if e was not in map at all. |
+ if (remaining == 0) { |
+ seen.remove(e); |
+ } else { |
+ seen[e] = remaining; |
+ } |
+ } |
+ Expect.isTrue(seen.isEmpty); |
+ // Test that shuffle actually does make a change. Repeat until the probability |
+ // of a proper shuffling hitting the same list again is less than 10^80 |
+ // (arbitrary bignum - approx. number of atoms in the universe). |
+ // |
+ // The probablility of shuffling a list of length n into the same list is |
+ // 1/n!. If one shuffle didn't change the list, repeat shuffling until |
+ // probability of randomly hitting the same list every time is less than |
+ // 1/1e80. |
+ |
+ bool listsDifferent() { |
+ for (int i = 0; i < list.length; i++) { |
+ if (list[i] != copy[i]) return true; |
+ } |
+ return false; |
+ } |
+ if (list.length < 59) { // 59! > 1e80. |
+ double limit = 1e80; |
+ double fact = 1.0; |
+ for (int i = 2; i < list.length; i++) fact *= i; |
+ double combos = fact; |
+ |
+ while (!listsDifferent() && combos < limit) { |
+ list.shuffle(); |
+ combos *= fact; |
+ } |
+ } |
+ if (!listsDifferent()) { |
+ Expect.fail("Didn't shuffle at all, p < 1:1e80: $list"); |
+ } |
+} |
+ |
+ |
+// Checks that the "random" argument to shuffle is used. |
+testRandom() { |
+ List randomNums = [37, 87, 42, 157, 252, 17]; |
+ List numbers = new List.generate(25, (x) => x); |
+ List l1 = numbers.toList()..shuffle(new MockRandom(randomNums)); |
+ for (int i = 0; i < 50; i++) { |
+ // With same random sequence, we get the same shuffling each time. |
+ List l2 = numbers.toList()..shuffle(new MockRandom(randomNums)); |
+ Expect.listEquals(l1, l2); |
+ } |
+} |
+ |
+class MockRandom implements Random { |
+ final List<int> _values; |
+ int index = 0; |
+ MockRandom(this._values); |
+ |
+ int get _next { |
+ int next = _values[index]; |
+ index = (index + 1) % _values.length; |
+ return next; |
+ } |
+ |
+ int nextInt(int limit) => _next % limit; |
+ |
+ double nextDouble() => _next / 256.0; |
+ |
+ bool nextBool() => _next.isEven; |
+} |