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

Side by Side Diff: tests/corelib_strong/shuffle_test.dart

Issue 2771453003: Format all tests. (Closed)
Patch Set: Format files Created 3 years, 8 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 unified diff | Download patch
OLDNEW
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file
2 // for details. All rights reserved. Use of this source code is governed by a 2 // for details. All rights reserved. Use of this source code is governed by a
3 // BSD-style license that can be found in the LICENSE file. 3 // BSD-style license that can be found in the LICENSE file.
4 4
5 // Dart test for List.shuffle. 5 // Dart test for List.shuffle.
6 library shuffle_test; 6 library shuffle_test;
7
7 import "dart:typed_data"; 8 import "dart:typed_data";
8 import "dart:math" show Random; 9 import "dart:math" show Random;
9 import "package:expect/expect.dart"; 10 import "package:expect/expect.dart";
10 11
11 main() { 12 main() {
12 for (int size in [0, 1, 2, 3, 7, 15, 99, 1023]) { 13 for (int size in [0, 1, 2, 3, 7, 15, 99, 1023]) {
13 var numbers = new List<int>.generate(size, (x) => x); 14 var numbers = new List<int>.generate(size, (x) => x);
14 testShuffle(numbers.toList(growable: true)); 15 testShuffle(numbers.toList(growable: true));
15 testShuffle(numbers.toList(growable: false)); 16 testShuffle(numbers.toList(growable: false));
16 testShuffle(new Uint32List(size)..setAll(0, numbers)); 17 testShuffle(new Uint32List(size)..setAll(0, numbers));
17 testShuffle(new Int32List(size)..setAll(0, numbers)); 18 testShuffle(new Int32List(size)..setAll(0, numbers));
18 testShuffle(new Uint16List(size)..setAll(0, numbers)); 19 testShuffle(new Uint16List(size)..setAll(0, numbers));
19 testShuffle(new Int16List(size)..setAll(0, numbers)); 20 testShuffle(new Int16List(size)..setAll(0, numbers));
20 // Some numbers will be truncated in the following two. 21 // Some numbers will be truncated in the following two.
21 testShuffle(new Uint8List(size)..setAll(0, numbers)); 22 testShuffle(new Uint8List(size)..setAll(0, numbers));
22 testShuffle(new Int8List(size)..setAll(0, numbers)); 23 testShuffle(new Int8List(size)..setAll(0, numbers));
23 //testShuffle(numbers.map((x) => "$x").toList()); 24 //testShuffle(numbers.map((x) => "$x").toList());
24 } 25 }
25 26
26 // Check that it actually can keep the same list (regression test). 27 // Check that it actually can keep the same list (regression test).
27 List l = [1, 2]; 28 List l = [1, 2];
28 success: { 29 success:
30 {
29 for (int i = 0; i < 266; i++) { 31 for (int i = 0; i < 266; i++) {
30 int first = l.first; 32 int first = l.first;
31 l.shuffle(); 33 l.shuffle();
32 if (l.first == first) break success; // List didn't change. 34 if (l.first == first) break success; // List didn't change.
33 } 35 }
34 // Chance of changing 266 times in a row should be < 1:1e80. 36 // Chance of changing 266 times in a row should be < 1:1e80.
35 Expect.fail("List changes every time."); 37 Expect.fail("List changes every time.");
36 } 38 }
37 39
38 testRandom(); 40 testRandom();
39 } 41 }
40 42
41 void testShuffle(list) { 43 void testShuffle(list) {
42 List copy = list.toList(); 44 List copy = list.toList();
43 list.shuffle(); 45 list.shuffle();
44 if (list.length < 2) { 46 if (list.length < 2) {
45 Expect.listEquals(copy, list); 47 Expect.listEquals(copy, list);
46 return; 48 return;
47 } 49 }
48 // Test that the list after shuffling has the same elements as before, 50 // Test that the list after shuffling has the same elements as before,
49 // without considering order. 51 // without considering order.
50 Map seen = {}; 52 Map seen = {};
51 for (var e in list) { 53 for (var e in list) {
52 seen[e] = seen.putIfAbsent(e, () => 0) + 1; 54 seen[e] = seen.putIfAbsent(e, () => 0) + 1;
53 } 55 }
54 for (var e in copy) { 56 for (var e in copy) {
55 int remaining = seen[e]; 57 int remaining = seen[e];
56 remaining -= 1; // Throws if e was not in map at all. 58 remaining -= 1; // Throws if e was not in map at all.
57 if (remaining == 0) { 59 if (remaining == 0) {
58 seen.remove(e); 60 seen.remove(e);
59 } else { 61 } else {
60 seen[e] = remaining; 62 seen[e] = remaining;
61 } 63 }
62 } 64 }
63 Expect.isTrue(seen.isEmpty); 65 Expect.isTrue(seen.isEmpty);
64 // Test that shuffle actually does make a change. Repeat until the probability 66 // Test that shuffle actually does make a change. Repeat until the probability
65 // of a proper shuffling hitting the same list again is less than 10^80 67 // of a proper shuffling hitting the same list again is less than 10^80
66 // (arbitrary bignum - approx. number of atoms in the universe). 68 // (arbitrary bignum - approx. number of atoms in the universe).
67 // 69 //
68 // The probablility of shuffling a list of length n into the same list is 70 // The probablility of shuffling a list of length n into the same list is
69 // 1/n!. If one shuffle didn't change the list, repeat shuffling until 71 // 1/n!. If one shuffle didn't change the list, repeat shuffling until
70 // probability of randomly hitting the same list every time is less than 72 // probability of randomly hitting the same list every time is less than
71 // 1/1e80. 73 // 1/1e80.
72 74
73 bool listsDifferent() { 75 bool listsDifferent() {
74 for (int i = 0; i < list.length; i++) { 76 for (int i = 0; i < list.length; i++) {
75 if (list[i] != copy[i]) return true; 77 if (list[i] != copy[i]) return true;
76 } 78 }
77 return false; 79 return false;
78 } 80 }
79 if (list.length < 59) { // 59! > 1e80. 81
82 if (list.length < 59) {
83 // 59! > 1e80.
80 double limit = 1e80; 84 double limit = 1e80;
81 double fact = 1.0; 85 double fact = 1.0;
82 for (int i = 2; i < list.length; i++) fact *= i; 86 for (int i = 2; i < list.length; i++) fact *= i;
83 double combos = fact; 87 double combos = fact;
84 88
85 while (!listsDifferent() && combos < limit) { 89 while (!listsDifferent() && combos < limit) {
86 list.shuffle(); 90 list.shuffle();
87 combos *= fact; 91 combos *= fact;
88 } 92 }
89 } 93 }
90 if (!listsDifferent()) { 94 if (!listsDifferent()) {
91 Expect.fail("Didn't shuffle at all, p < 1:1e80: $list"); 95 Expect.fail("Didn't shuffle at all, p < 1:1e80: $list");
92 } 96 }
93 } 97 }
94 98
95
96 // Checks that the "random" argument to shuffle is used. 99 // Checks that the "random" argument to shuffle is used.
97 testRandom() { 100 testRandom() {
98 List<int> randomNums = [37, 87, 42, 157, 252, 17]; 101 List<int> randomNums = [37, 87, 42, 157, 252, 17];
99 List numbers = new List.generate(25, (x) => x); 102 List numbers = new List.generate(25, (x) => x);
100 List l1 = numbers.toList()..shuffle(new MockRandom(randomNums)); 103 List l1 = numbers.toList()..shuffle(new MockRandom(randomNums));
101 for (int i = 0; i < 50; i++) { 104 for (int i = 0; i < 50; i++) {
102 // With same random sequence, we get the same shuffling each time. 105 // With same random sequence, we get the same shuffling each time.
103 List l2 = numbers.toList()..shuffle(new MockRandom(randomNums)); 106 List l2 = numbers.toList()..shuffle(new MockRandom(randomNums));
104 Expect.listEquals(l1, l2); 107 Expect.listEquals(l1, l2);
105 } 108 }
106 } 109 }
107 110
108 class MockRandom implements Random { 111 class MockRandom implements Random {
109 final List<int> _values; 112 final List<int> _values;
110 int index = 0; 113 int index = 0;
111 MockRandom(this._values); 114 MockRandom(this._values);
112 115
113 int get _next { 116 int get _next {
114 int next = _values[index]; 117 int next = _values[index];
115 index = (index + 1) % _values.length; 118 index = (index + 1) % _values.length;
116 return next; 119 return next;
117 } 120 }
118 121
119 int nextInt(int limit) => _next % limit; 122 int nextInt(int limit) => _next % limit;
120 123
121 double nextDouble() => _next / 256.0; 124 double nextDouble() => _next / 256.0;
122 125
123 bool nextBool() => _next.isEven; 126 bool nextBool() => _next.isEven;
124 } 127 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698