Add List.shuffle().

tests/corelib/shuffle_test.dart

+// 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 "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.");
+  }
+}
+
+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 elemental particles 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");
+  }
+}