Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(902)

Unified Diff: test/codegen/corelib/shuffle_test.dart

Issue 1945153002: Add corelib tests (Closed) Base URL: https://github.com/dart-lang/dev_compiler@master
Patch Set: error_test and range_error_test now pass Created 4 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « test/codegen/corelib/set_to_string_test.dart ('k') | test/codegen/corelib/sort_helper.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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;
+}
« no previous file with comments | « test/codegen/corelib/set_to_string_test.dart ('k') | test/codegen/corelib/sort_helper.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698