blob: 536072d3c13fcdcfc21ee4c194d6924696a43817 [file] [log] [blame]
// 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;
}