Introduce new LinkedList to dart:collection.

tests/lib/collection/linked_list_test.dart

Index: tests/lib/collection/linked_list_test.dart
diff --git a/tests/lib/collection/linked_list_test.dart b/tests/lib/collection/linked_list_test.dart
new file mode 100644
index 0000000000000000000000000000000000000000..3b0a29ad5d4158b62250756bbb9fd5dfaef17f41
--- /dev/null
+++ b/tests/lib/collection/linked_list_test.dart
@@ -0,0 +1,157 @@
+// Copyright (c) 2013, 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.
+
+import 'dart:collection';
+import "package:expect/expect.dart";
+
+class MyEntry extends LinkedListEntry<MyEntry> {
+  final int value;
+
+  MyEntry(int this.value);
+
+  String toString() => value.toString();
+}
+
+
+testInsert() {
+  // Insert last.
+  var list = new LinkedList<MyEntry>();
+  for (int i = 0; i < 10; i++) {
+    list.add(new MyEntry(i));
+  }
+
+  Expect.equals(10, list.length);
+
+  int i = 0;
+  for (var entry in list) {
+    Expect.equals(i++, entry.value);
+  }
+
+  Expect.equals(10, i);
+
+  list.clear();
+
+  // Insert first.
+  for (int i = 0; i < 10; i++) {
+    list.addFirst(new MyEntry(i));
+  }
+
+  Expect.equals(10, list.length);
+
+  i = 10;
+  for (var entry in list) {
+    Expect.equals(--i, entry.value);
+  }
+  Expect.equals(0, i);
+
+  list.clear();
+
+  // Insert after.
+  list.addFirst(new MyEntry(0));
+  for (int i = 1; i < 10; i++) {
+    list.last.insertAfter(new MyEntry(i));
+  }
+
+  Expect.equals(10, list.length);
+
+  i = 0;
+  for (var entry in list) {
+    Expect.equals(i++, entry.value);

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

Please move post-increment out of test.

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+  }
+
+  Expect.equals(10, i);
+
+  list.clear();
+
+  // Insert before.
+  list.addFirst(new MyEntry(0));
+  for (int i = 1; i < 10; i++) {
+    list.first.insertBefore(new MyEntry(i));
+  }
+
+  Expect.equals(10, list.length);
+
+  i = 10;
+  for (var entry in list) {
+    Expect.equals(--i, entry.value);
+  }
+  Expect.equals(0, i);
+
+  list.clear();
+}
+
+
+testRemove() {
+  var list = new LinkedList<MyEntry>();
+  for (int i = 0; i < 10; i++) {
+    list.add(new MyEntry(i));
+  }
+
+  Expect.equals(10, list.length);
+
+  list.remove(list.skip(5).first);
+
+  Expect.equals(9, list.length);
+
+  int i = 0;
+  for (var entry in list) {
+    if (i == 5) i++;
+    Expect.equals(i++, entry.value);

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

Please move post-increment out of test.

You can also use
 Expect.listEquals([0, 1, 2, 3, 4, 6, 7, 8, 9], list.toList());

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+  }

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

Add test for removing the last element of a list (i.e., when the list has length
1).

Test that removing element that is not in list works as expected (throws).

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+}
+
+
+testBadAdd() {
+  var list1 = new LinkedList<MyEntry>();
+  list1.addFirst(new MyEntry(0));
+
+  var list2 = new LinkedList<MyEntry>();
+  Expect.throws(() => list2.addFirst(list1.first));
+}
+
+testConcurrentModificationError() {
+
+  test(function(LinkedList ll)) {
+    var ll = new LinkedList<MyEntry>();
+    for (int i = 0; i < 10; i++) {
+      ll.add(new MyEntry(i));
+    }
+    Expect.throws(() => function(ll));

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

Make this be
  Expect.throws(() => function(ll), (e) => e is ConcurrentModificationError);

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+  }
+  test((ll) { for(x in ll) { ll.remove(x); } });
+  test((ll) { ll.forEach((x) { ll.remove(x); }); });
+  test((ll) { ll.any((x) { ll.remove(x); return false; }); });
+  test((ll) { ll.every((x) { ll.remove(x); return true; }); });
+  test((ll) { ll.fold((x, y) { ll.remove(y); return x; }); });
+  test((ll) { ll.reduce(0, (x, y) { ll.remove(y); return x; }); });
+  test((ll) { ll.where((x) { ll.remove(x); return true; }).length; });

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

Change all the .length to .forEach((_){}), just to be sure.

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+  test((ll) { ll.map((x) { ll.remove(x); return x; }).forEach((x) {}); });
+  test((ll) { ll.expand((x) { ll.remove(x); return[x];}).length; });
+  test((ll) { ll.takeWhile((x) { ll.remove(x); return true;}).length; });
+  test((ll) { ll.skipWhile((x) { ll.remove(x); return true;}).length; });
+  test((ll) {
+    bool first = true;
+    ll.firstWhere((x) {
+      ll.remove(x);
+      if (!first) return true;
+      return first = false;
+    }).length;

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

Remove .length.
I think this would throw a NoSuchMethodError if it got so far.

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+  });
+  test((ll) { ll.lastWhere((x) { ll.remove(x); return true;}).length; });

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

Ditto.

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+  test((ll) {
+    first = true;
+    ll.singleWhere((x) {
+      ll.remove(x);
+      if (!first) return false;
+      return !(first = false);
+    }).length;

[Lasse Reichstein Nielsen, 2013/06/13 11:36:59]

Ditto.

[Anders Johnsen, 2013/06/13 11:54:08]

Done.

+  });
+}
+
+main() {
+  testInsert();
+  testRemove();
+  testBadAdd();
+  testConcurrentModificationError();
+}