Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
13459002:
Introduce new LinkedList to dart:collection. (Closed)
|
Created:
7 years, 8 months ago by Anders Johnsen Modified:
7 years, 6 months ago CC:
reviews_dartlang.org Visibility:
Public. |
DescriptionIntroduce new LinkedList to dart:collection.
LinkedList required the element to extend LinkedListEntry. This is
useful for implementation that want to remove/unlink a entry in O(1), given the
entry.
BUG=
R=floitsch@google.com, lrn@google.com
Committed: https://code.google.com/p/dart/source/detail?r=23969
Patch Set 1 #
Total comments: 22
Patch Set 2 : Add test, clean up implementation and add insertLast, insertFirst, insertAfter and insertBefore. #Patch Set 3 : #Patch Set 4 : #
Total comments: 30
Patch Set 5 : Fix naming, concurrent modification and further tests. #
Total comments: 28
Patch Set 6 : Add documentation. #Patch Set 7 : Review updates. #
Messages
Total messages: 10 (0 generated)
https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... File sdk/lib/collection/linked_list.dart (right): https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:7: class LinkedList <E extends LinkedListEntry> https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:16: _next = _prev = _list = this; No need for _list here. https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:19: void add(LinkedListEntry entry) { (E entry) https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:21: _length++; void remove(E entry) { if (entry._list != this) return; entry._unlink(); _length--; } https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:24: void _insertAfter(_LinkedListEntry entry, _LinkedListEntry newEntry) { Last _LinkedListEntry -> E https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:25: newEntry._list = this; assert(newEntry.list == null); https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:39: class _LinkedListIterator implements Iterator<LinkedListEntry> { _LinkedListIterator<E extends LinkedListEntry> implements Itertator<E> ensure correct return type E for 'current'. https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:41: _LinkedListEntry _current; Consider having: E _current = null; _LinkedListEntry _next; _LinkedListITerator(LinkedList<E> list) : _list = list, _next = list._next; moveNext() { if (identical(_next, _list)) { _current = null; return false; } _current = _next; _next = _next._next; return true; } One extra field, but simpler logic. https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:54: if (_current._next == _list) return false; if (identical(_current._next, _list) { _current = null; return false; } https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:61: LinkedList _list; Move to LinkedListEntry https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:81: } Make a "list" getter, so you can go from an element to the list it is part of.
https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... File sdk/lib/collection/linked_list.dart (right): https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:7: class LinkedList On 2013/04/02 08:23:44, Lasse Reichstein Nielsen wrote: > <E extends LinkedListEntry> Done. https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:16: _next = _prev = _list = this; On 2013/04/02 08:23:44, Lasse Reichstein Nielsen wrote: > No need for _list here. Done. https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:19: void add(LinkedListEntry entry) { On 2013/04/02 08:23:44, Lasse Reichstein Nielsen wrote: > (E entry) Done. https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:21: _length++; On 2013/04/02 08:23:44, Lasse Reichstein Nielsen wrote: > void remove(E entry) { > if (entry._list != this) return; > entry._unlink(); > _length--; > } Done. https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:24: void _insertAfter(_LinkedListEntry entry, _LinkedListEntry newEntry) { On 2013/04/02 08:23:44, Lasse Reichstein Nielsen wrote: > Last _LinkedListEntry -> E Done. https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:25: newEntry._list = this; On 2013/04/02 08:23:44, Lasse Reichstein Nielsen wrote: > assert(newEntry.list == null); Done. https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:39: class _LinkedListIterator implements Iterator<LinkedListEntry> { On 2013/04/02 08:23:44, Lasse Reichstein Nielsen wrote: > _LinkedListIterator<E extends LinkedListEntry> implements Itertator<E> > ensure correct return type E for 'current'. Done. https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:41: _LinkedListEntry _current; On 2013/04/02 08:23:44, Lasse Reichstein Nielsen wrote: > Consider having: > E _current = null; > _LinkedListEntry _next; > _LinkedListITerator(LinkedList<E> list) : _list = list, _next = list._next; > moveNext() { > if (identical(_next, _list)) { > _current = null; > return false; > } > _current = _next; > _next = _next._next; > return true; > } > One extra field, but simpler logic. Done. https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:54: if (_current._next == _list) return false; On 2013/04/02 08:23:44, Lasse Reichstein Nielsen wrote: > if (identical(_current._next, _list) { > _current = null; > return false; > } Done. https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:61: LinkedList _list; On 2013/04/02 08:23:44, Lasse Reichstein Nielsen wrote: > Move to LinkedListEntry Done. https://codereview.chromium.org/13459002/diff/1/sdk/lib/collection/linked_lis... sdk/lib/collection/linked_list.dart:81: } On 2013/04/02 08:23:44, Lasse Reichstein Nielsen wrote: > Make a "list" getter, so you can go from an element to the list it is part of. Done.
PTAL. Will document once we agree on the API.
LGTM with comments. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... File sdk/lib/collection/linked_list.dart (right): https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:32: if (entry._list != this) return; Shouldn't we throw here? https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:39: 'LinkedListEntry is already present in a LinkedList'); is already in a LinkedList https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:41: newEntry._list = this; I think this would read easier as follows (or use "previous", "next"): _LinkedListEntry predecessor = entry; _LinkedListEntry successor = entry._next; predecessor._next = newEntry; newEntry._prev = predecessor; newEntry._next = successor; successor._prev = newEntry; https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:58: for (var entry in this) { This looks dangerous. I would prefer not to use an iterator. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:94: if (identical(_next, _list)) { Is it on purpose that you don't check the length (or maybe even more) for concurrentModificationErrors ? If I'm not wrong for (var x in linkedList) linkedList.remove(x.next); would crash. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:105: class _LinkedListEntry { Call it something else. _LinkedListLink ? https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:127: LinkedListEntry get prev { usually we don't abbreviate. Should "prev" really be an exception? https://codereview.chromium.org/13459002/diff/9001/tests/standalone/standalon... File tests/standalone/standalone.status (right): https://codereview.chromium.org/13459002/diff/9001/tests/standalone/standalon... tests/standalone/standalone.status:103: io/url_encoding_test: Skip # Importing code with external keyword Looks unrelated.
LGTM with concurrent modification errors and more tests. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... File sdk/lib/collection/linked_list.dart (right): https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:13: _LinkedListEntry _prev; You need a modification count to catch concurrent modifications. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:32: if (entry._list != this) return; I think returning is fine. We don't throw in other collections if removing an element that isn't there. It should probably return a boolean that is true if it removes something. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:58: for (var entry in this) { Agree. _LinkedListEntry next = _this._next; while (!identical(next, this)) { _LinkedListEntry entry = next; next = entry._next; entry._next = entry._prev = entry._list = null; } _next = _prev = this; _length = 0; https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:77: } E get single { if (identical(_prev, this)) { throw new StateError('No such element'); } if (!identical(_prev, _next)) { throw new StateError('Too many elements'); } return _next; } https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:78: Implement forEach without an iterator too. Remember concurrent modifications. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:105: class _LinkedListEntry { _ListLink? https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:127: LinkedListEntry get prev { I don't think so. I generally write it out (both "previous" and "_previous"). https://codereview.chromium.org/13459002/diff/9001/tests/lib/collection/linke... File tests/lib/collection/linked_list_test.dart (right): https://codereview.chromium.org/13459002/diff/9001/tests/lib/collection/linke... tests/lib/collection/linked_list_test.dart:7: import "package:expect/expect.dart"; and use Expect instead of throws. https://codereview.chromium.org/13459002/diff/9001/tests/lib/collection/linke... tests/lib/collection/linked_list_test.dart:120: Test concurrent modification throws for all iterations: for(x in ll) { ll.remove(x); } ll.forEach((x) { ll.remove(x); }) ll.any((x) { ll.remove(x); return false; }) ll.every((x) { ll.remove(x); return true; }) ll.fold((x, y) { ll.remove(y); return x; }) ll.reduce(0, (x, y) { ll.remove(y); return x; }) ll.where((x) { ll.remove(x); return true; }).last ll.map((x) { ll.remove(x); return x;}).last ll.expand((x) { ll.remove(x); return[x];}).last ll.takeWhile((x) { ll.remove(x); return true;}).last ll.skipWhile((x) { ll.remove(x); return true;}).last bool first = true; ll.firstWhere((x) { ll.remove(x); if (!first) return true; return first = false;}).last ll.lastWhere((x) { ll.remove(x); return true;}).last first = true; ll.singleWhere((x) { ll.remove(x); if (!first) return false; return !(first = false);}).last (or something similar). All should throw ConcurrentModificationError on lists of length two or more.
On 2013/05/24 08:42:45, Lasse Reichstein Nielsen wrote: > LGTM with concurrent modification errors and more tests. > > https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... > File sdk/lib/collection/linked_list.dart (right): > > https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... > sdk/lib/collection/linked_list.dart:13: _LinkedListEntry _prev; > You need a modification count to catch concurrent modifications. > > https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... > sdk/lib/collection/linked_list.dart:32: if (entry._list != this) return; > I think returning is fine. We don't throw in other collections if removing an > element that isn't there. > > It should probably return a boolean that is true if it removes something. > > https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... > sdk/lib/collection/linked_list.dart:58: for (var entry in this) { > Agree. > > _LinkedListEntry next = _this._next; > while (!identical(next, this)) { > _LinkedListEntry entry = next; > next = entry._next; > entry._next = entry._prev = entry._list = null; > } > _next = _prev = this; > _length = 0; > > https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... > sdk/lib/collection/linked_list.dart:77: } > E get single { > if (identical(_prev, this)) { > throw new StateError('No such element'); > } > if (!identical(_prev, _next)) { > throw new StateError('Too many elements'); > } > return _next; > } > > https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... > sdk/lib/collection/linked_list.dart:78: > Implement forEach without an iterator too. > Remember concurrent modifications. > > https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... > sdk/lib/collection/linked_list.dart:105: class _LinkedListEntry { > _ListLink? > > https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... > sdk/lib/collection/linked_list.dart:127: LinkedListEntry get prev { > I don't think so. I generally write it out (both "previous" and "_previous"). > > https://codereview.chromium.org/13459002/diff/9001/tests/lib/collection/linke... > File tests/lib/collection/linked_list_test.dart (right): > > https://codereview.chromium.org/13459002/diff/9001/tests/lib/collection/linke... > tests/lib/collection/linked_list_test.dart:7: > import "package:expect/expect.dart"; > and use Expect instead of throws. > > https://codereview.chromium.org/13459002/diff/9001/tests/lib/collection/linke... > tests/lib/collection/linked_list_test.dart:120: > Test concurrent modification throws for all iterations: > for(x in ll) { ll.remove(x); } > ll.forEach((x) { ll.remove(x); }) > ll.any((x) { ll.remove(x); return false; }) > ll.every((x) { ll.remove(x); return true; }) > ll.fold((x, y) { ll.remove(y); return x; }) > ll.reduce(0, (x, y) { ll.remove(y); return x; }) > ll.where((x) { ll.remove(x); return true; }).last > ll.map((x) { ll.remove(x); return x;}).last > ll.expand((x) { ll.remove(x); return[x];}).last > ll.takeWhile((x) { ll.remove(x); return true;}).last > ll.skipWhile((x) { ll.remove(x); return true;}).last > bool first = true; > ll.firstWhere((x) { ll.remove(x); if (!first) return true; return first = > false;}).last > ll.lastWhere((x) { ll.remove(x); return true;}).last > first = true; > ll.singleWhere((x) { ll.remove(x); if (!first) return false; return !(first = > false);}).last > > (or something similar). > All should throw ConcurrentModificationError on lists of length two or more. You could also consider adding `removeWhere`, and `retainWhere`.
PTAL https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... File sdk/lib/collection/linked_list.dart (right): https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:13: _LinkedListEntry _prev; On 2013/05/24 08:42:45, Lasse Reichstein Nielsen wrote: > You need a modification count to catch concurrent modifications. Done. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:32: if (entry._list != this) return; On 2013/05/24 08:42:45, Lasse Reichstein Nielsen wrote: > I think returning is fine. We don't throw in other collections if removing an > element that isn't there. > > It should probably return a boolean that is true if it removes something. Done. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:39: 'LinkedListEntry is already present in a LinkedList'); On 2013/05/23 19:01:26, floitsch wrote: > is already in a LinkedList Done. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:41: newEntry._list = this; On 2013/05/23 19:01:26, floitsch wrote: > I think this would read easier as follows (or use "previous", "next"): > _LinkedListEntry predecessor = entry; > _LinkedListEntry successor = entry._next; > predecessor._next = newEntry; > newEntry._prev = predecessor; > newEntry._next = successor; > successor._prev = newEntry; Done. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:58: for (var entry in this) { On 2013/05/24 08:42:45, Lasse Reichstein Nielsen wrote: > Agree. > > _LinkedListEntry next = _this._next; > while (!identical(next, this)) { > _LinkedListEntry entry = next; > next = entry._next; > entry._next = entry._prev = entry._list = null; > } > _next = _prev = this; > _length = 0; Done. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:77: } On 2013/05/24 08:42:45, Lasse Reichstein Nielsen wrote: > E get single { > if (identical(_prev, this)) { > throw new StateError('No such element'); > } > if (!identical(_prev, _next)) { > throw new StateError('Too many elements'); > } > return _next; > } Done. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:78: On 2013/05/24 08:42:45, Lasse Reichstein Nielsen wrote: > Implement forEach without an iterator too. > Remember concurrent modifications. Done. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:94: if (identical(_next, _list)) { On 2013/05/23 19:01:26, floitsch wrote: > Is it on purpose that you don't check the length (or maybe even more) for > concurrentModificationErrors ? > If I'm not wrong > for (var x in linkedList) linkedList.remove(x.next); > would crash. Done. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:105: class _LinkedListEntry { On 2013/05/24 08:42:45, Lasse Reichstein Nielsen wrote: > _ListLink? Done. https://codereview.chromium.org/13459002/diff/9001/sdk/lib/collection/linked_... sdk/lib/collection/linked_list.dart:127: LinkedListEntry get prev { On 2013/05/24 08:42:45, Lasse Reichstein Nielsen wrote: > I don't think so. I generally write it out (both "previous" and "_previous"). Done. https://codereview.chromium.org/13459002/diff/9001/tests/lib/collection/linke... File tests/lib/collection/linked_list_test.dart (right): https://codereview.chromium.org/13459002/diff/9001/tests/lib/collection/linke... tests/lib/collection/linked_list_test.dart:7: On 2013/05/24 08:42:45, Lasse Reichstein Nielsen wrote: > import "package:expect/expect.dart"; > and use Expect instead of throws. Done. https://codereview.chromium.org/13459002/diff/9001/tests/lib/collection/linke... tests/lib/collection/linked_list_test.dart:120: On 2013/05/24 08:42:45, Lasse Reichstein Nielsen wrote: > Test concurrent modification throws for all iterations: > for(x in ll) { ll.remove(x); } > ll.forEach((x) { ll.remove(x); }) > ll.any((x) { ll.remove(x); return false; }) > ll.every((x) { ll.remove(x); return true; }) > ll.fold((x, y) { ll.remove(y); return x; }) > ll.reduce(0, (x, y) { ll.remove(y); return x; }) > ll.where((x) { ll.remove(x); return true; }).last > ll.map((x) { ll.remove(x); return x;}).last > ll.expand((x) { ll.remove(x); return[x];}).last > ll.takeWhile((x) { ll.remove(x); return true;}).last > ll.skipWhile((x) { ll.remove(x); return true;}).last > bool first = true; > ll.firstWhere((x) { ll.remove(x); if (!first) return true; return first = > false;}).last > ll.lastWhere((x) { ll.remove(x); return true;}).last > first = true; > ll.singleWhere((x) { ll.remove(x); if (!first) return false; return !(first = > false);}).last > > (or something similar). > All should throw ConcurrentModificationError on lists of length two or more. Done. https://codereview.chromium.org/13459002/diff/9001/tests/standalone/standalon... File tests/standalone/standalone.status (right): https://codereview.chromium.org/13459002/diff/9001/tests/standalone/standalon... tests/standalone/standalone.status:103: io/url_encoding_test: Skip # Importing code with external keyword On 2013/05/23 19:01:26, floitsch wrote: > Looks unrelated. Done.
lgtm https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... File sdk/lib/collection/linked_list.dart (right): https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... sdk/lib/collection/linked_list.dart:8: class LinkedList<E extends LinkedListEntry<E>> Documentation of for class? https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... sdk/lib/collection/linked_list.dart:21: void addFirst(E entry) { And documentation for all public methods? https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... sdk/lib/collection/linked_list.dart:30: entries.forEach(add); Consider having an internal method, e.g., called "_add", and have both this method and the "add" method call that. If someone extends LinkedList (which is likely), they can override add and also affect this method by accident. (Or, as general rule, don't call overridable methods from other methods unless it's explicitly documented and intentional). Also consider having a special case if entries is LinkedList where you just link all its elements into this in one operation. https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... sdk/lib/collection/linked_list.dart:64: return new _LinkedListIterator(this); Iterator<E> get iterator => new _LinkedListIterator<E>(this); https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... sdk/lib/collection/linked_list.dart:107: void forEach(void action(E entry)) { Mention that it is an error to remove or add elements during an iteration. https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... sdk/lib/collection/linked_list.dart:158: abstract class LinkedListEntry<E> extends _LinkedListLink { Consider implementing _LinkedListLink instead of extending it. You'll have to add the fields here again, but then this class can be used as a mixin! https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... File tests/lib/collection/linked_list_test.dart (right): https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:60: Expect.equals(i++, entry.value); Please move post-increment out of test. https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:100: Expect.equals(i++, entry.value); Please move post-increment out of test. You can also use Expect.listEquals([0, 1, 2, 3, 4, 6, 7, 8, 9], list.toList()); https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:101: } 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). https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:120: Expect.throws(() => function(ll)); Make this be Expect.throws(() => function(ll), (e) => e is ConcurrentModificationError); https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:128: test((ll) { ll.where((x) { ll.remove(x); return true; }).length; }); Change all the .length to .forEach((_){}), just to be sure. https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:139: }).length; Remove .length. I think this would throw a NoSuchMethodError if it got so far. https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:141: test((ll) { ll.lastWhere((x) { ll.remove(x); return true;}).length; }); Ditto. https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:148: }).length; Ditto.
https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... File sdk/lib/collection/linked_list.dart (right): https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... sdk/lib/collection/linked_list.dart:8: class LinkedList<E extends LinkedListEntry<E>> On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > Documentation of for class? Done. https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... sdk/lib/collection/linked_list.dart:21: void addFirst(E entry) { On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > And documentation for all public methods? Done. https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... sdk/lib/collection/linked_list.dart:30: entries.forEach(add); On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > Consider having an internal method, e.g., called "_add", and have both this > method and the "add" method call that. > > If someone extends LinkedList (which is likely), they can override add and also > affect this method by accident. > (Or, as general rule, don't call overridable methods from other methods unless > it's explicitly documented and intentional). > > Also consider having a special case if entries is LinkedList where you just link > all its elements into this in one operation. Done. https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... sdk/lib/collection/linked_list.dart:64: return new _LinkedListIterator(this); On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > Iterator<E> get iterator => new _LinkedListIterator<E>(this); Done. https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... sdk/lib/collection/linked_list.dart:107: void forEach(void action(E entry)) { On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > Mention that it is an error to remove or add elements during an iteration. Done. https://codereview.chromium.org/13459002/diff/19001/sdk/lib/collection/linked... sdk/lib/collection/linked_list.dart:158: abstract class LinkedListEntry<E> extends _LinkedListLink { On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > Consider implementing _LinkedListLink instead of extending it. > You'll have to add the fields here again, but then this class can be used as a > mixin! Done. https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... File tests/lib/collection/linked_list_test.dart (right): https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:60: Expect.equals(i++, entry.value); On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > Please move post-increment out of test. Done. https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:100: Expect.equals(i++, entry.value); On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > Please move post-increment out of test. > > You can also use > Expect.listEquals([0, 1, 2, 3, 4, 6, 7, 8, 9], list.toList()); Done. https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:101: } On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > 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). Done. https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:120: Expect.throws(() => function(ll)); On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > Make this be > Expect.throws(() => function(ll), (e) => e is ConcurrentModificationError); Done. https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:128: test((ll) { ll.where((x) { ll.remove(x); return true; }).length; }); On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > Change all the .length to .forEach((_){}), just to be sure. Done. https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:139: }).length; On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > Remove .length. > I think this would throw a NoSuchMethodError if it got so far. Done. https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:141: test((ll) { ll.lastWhere((x) { ll.remove(x); return true;}).length; }); On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > Ditto. Done. https://codereview.chromium.org/13459002/diff/19001/tests/lib/collection/link... tests/lib/collection/linked_list_test.dart:148: }).length; On 2013/06/13 11:36:59, Lasse Reichstein Nielsen wrote: > Ditto. Done.
Message was sent while issue was closed.
Committed patchset #7 manually as r23969 (presubmit successful). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
