| OLD | NEW |
| 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 } |
| OLD | NEW |