Repository: passsy/kt.dart (dart)

Issue:
KMutableIterator.remove() doesn't remove item from collection
```dart
var abc = mutableListOf(["a", "b", "c"]);
final KMutableIterator<String> i = abc.iterator();
assert(i.next() == "a");
i.remove();
assert(abc[0] == "b"); // Failed assertion: 'abc[0] == "b"': is not true.
```

`abc[0]` is still `"a"` because remove doesn't remove the item from the actual collection. Instead, it gets removed from the internal copy inside the iterator.

To fix this problem a big refactoring is required so that remove actually removed the item from the original collection.

This is how kotlin [solves this](https://github.com/JetBrains/kotlin/blob/ba6da7c40a6cc502508faf6e04fa105b96bc7777/libraries/stdlib/js/src/kotlin/collections/InternalHashCodeMap.kt)

Pull request:
Looks like the comment message is no longer relevant, because _list appears to be the underlying list and not the copy (at least in most basic scenarios).

This implements removeAllWhere(), retailAllWhere() and fixes #5.

Please tell me if you need any changes in my implementation.

Patch:
diff --git a/lib/src/collection/impl/iterator.dart b/lib/src/collection/impl/iterator.dart
index aabe94f..f7b7ee2 100644
--- a/lib/src/collection/impl/iterator.dart
+++ b/lib/src/collection/impl/iterator.dart
@@ -51,12 +51,10 @@ class InterOpKtListIterator<T>
 
   @override
   void remove() {
-    // removing from list is wrong because is is a copy of the original list.
-    // remove should modify the underlying list, not the copy
-    // see how kotlin solved this:
-    // https://github.com/JetBrains/kotlin/blob/ba6da7c40a6cc502508faf6e04fa105b96bc7777/libraries/stdlib/js/src/kotlin/collections/InternalHashCodeMap.kt
-    throw UnimplementedError(
-        "remove() in not yet implemented. Please vote for https://github.com/passsy/dart_kollection/issues/5 for prioritization");
+    _ensureHasLastReturnedElement();
+    _list.removeAt(_lastRet);
+    _cursor = _lastRet;
+    _lastRet = -1;
   }
 
   @override
@@ -84,10 +82,14 @@ class InterOpKtListIterator<T>
 
   @override
   void set(T element) {
+    _ensureHasLastReturnedElement();
+    _list.replaceRange(_lastRet, _lastRet + 1, [element]);
+  }
+
+  void _ensureHasLastReturnedElement() {
     if (_lastRet < 0) {
       throw const IndexOutOfBoundsException(
           "illegal cursor state -1. next() or previous() not called");
     }
-    _list.replaceRange(_lastRet, _lastRet + 1, [element]);
   }
 }
diff --git a/lib/src/collection/impl/map_mutable.dart b/lib/src/collection/impl/map_mutable.dart
index 28b7630..056c779 100644
--- a/lib/src/collection/impl/map_mutable.dart
+++ b/lib/src/collection/impl/map_mutable.dart
@@ -101,6 +101,9 @@ class DartMutableMap<K, V> extends Object implements KtMutableMap<K, V> {
     return true;
   }
 
+  @override
+  KtMutableIterator<KtMutableMapEntry<K, V>> iterator() => _MapIterator(this);
+
   @override
   int get hashCode => hashObjects(_map.keys
       .map((key) => hash2(key.hashCode, _map[key].hashCode))
@@ -152,3 +155,34 @@ class _MutableEntry<K, V> implements KtMutableMapEntry<K, V> {
   @override
   KtPair<K, V> toPair() => KtPair(_key, _value);
 }
+
+class _MapIterator<K, V> implements KtMutableIterator<KtMutableMapEntry<K, V>> {
+  _MapIterator(this.map) : _entriesIterator = map.entries.iterator();
+
+  // used to distinguish `null` (a valid key) from no key
+  static final Object _noKey = Object();
+
+  final DartMutableMap<K, V> map;
+  final KtMutableIterator<KtMutableMapEntry<K, V>> _entriesIterator;
+  Object? _lastReturnedKey = _noKey;
+
+  @override
+  bool hasNext() => _entriesIterator.hasNext();
+
+  @override
+  KtMutableMapEntry<K, V> next() {
+    final nextEntry = _entriesIterator.next();
+    _lastReturnedKey = nextEntry.key;
+    return nextEntry;
+  }
+
+  @override
+  void remove() {
+    final lastReturnedKey = _lastReturnedKey;
+    if (lastReturnedKey == _noKey) {
+      throw StateError("next() must be called before remove()");
+    }
+    map.remove(lastReturnedKey as K);
+    _lastReturnedKey = _noKey;
+  }
+}
diff --git a/lib/src/collection/impl/set_mutable.dart b/lib/src/collection/impl/set_mutable.dart
index 5e00de8..fe8dfd7 100644
--- a/lib/src/collection/impl/set_mutable.dart
+++ b/lib/src/collection/impl/set_mutable.dart
@@ -103,19 +103,24 @@ class DartMutableSet<T> extends Object implements KtMutableSet<T> {
 }
 
 class _MutableSetIterator<T> extends KtMutableIterator<T> {
-  _MutableSetIterator(KtMutableSet<T> set)
-      : _iterator = set.iter.iterator,
-        lastReturned = null {
+  _MutableSetIterator(this.set)
+      :
+        // copy to set to avoid concurrent modification
+        _iterator = set.toSet().iter.iterator {
     _hasNext = _iterator.moveNext();
     if (_hasNext) {
-      nextValue = _iterator.current;
+      _nextValue = _iterator.current;
     }
   }
 
+  // used to distinguish `null` from no value returned
+  static final Object _noValue = Object();
+
   final Iterator<T> _iterator;
-  T? nextValue;
-  T? lastReturned;
+  T? _nextValue;
+  Object? _lastReturned = _noValue;
   bool _hasNext = false;
+  final KtMutableSet<T> set;
 
   @override
   bool hasNext() => _hasNext;
@@ -123,22 +128,22 @@ class _MutableSetIterator<T> extends KtMutableIterator<T> {
   @override
   T next() {
     if (!_hasNext) throw const NoSuchElementException();
-    final e = nextValue;
+    final e = _nextValue;
     _hasNext = _iterator.moveNext();
     if (_hasNext) {
-      nextValue = _iterator.current;
+      _nextValue = _iterator.current;
     }
-    lastReturned = e;
+    _lastReturned = e;
     return e as T;
   }
 
   @override
   void remove() {
-    // removing from list is wrong because is is a copy of the original list.
-    // remove should modify the underlying list, not the copy
-    // see how kotlin solved this:
-    // https://github.com/JetBrains/kotlin/blob/ba6da7c40a6cc502508faf6e04fa105b96bc7777/libraries/stdlib/js/src/kotlin/collections/InternalHashCodeMap.kt
-    throw UnimplementedError(
-        "remove() in not yet implemented. Please vote for https://github.com/passsy/dart_kollection/issues/5 for prioritization");
+    final lastReturned = _lastReturned;
+    if (lastReturned == _noValue) {
+      throw StateError('remove() must be called after next()');
+    }
+    set.remove(lastReturned as T);
+    _lastReturned = _noValue;
   }
 }
diff --git a/lib/src/collection/kt_map_mutable.dart b/lib/src/collection/kt_map_mutable.dart
index e5c289a..5ebfb42 100644
--- a/lib/src/collection/kt_map_mutable.dart
+++ b/lib/src/collection/kt_map_mutable.dart
@@ -25,6 +25,8 @@ abstract class KtMutableMap<K, V> implements KtMap<K, V> {
   @override
   Map<K, V> asMap();
 
+  KtMutableIterator<KtMutableMapEntry<K, V>> iterator();
+
   // Modification Operations
   /// Associates the specified [value] with the specified [key] in the map.
   ///
@@ -96,9 +98,6 @@ extension KtMutableMapExtensions<K, V> on KtMutableMap<K, V> {
     return answer;
   }
 
-  /// Returns an [Iterator] over the entries in the [Map].
-  KtMutableIterator<KtMutableMapEntry<K, V>> iterator() => entries.iterator();
-
   /// Puts all the given [pairs] into this [KtMutableMap] with the first component in the pair being the key and the second the value.
   void putAllPairs(KtIterable<KtPair<K, V>> pairs) {
     for (final value in pairs.iter) {


Test patch:
diff --git a/test/collection/iterable_mutable_extensions_test.dart b/test/collection/iterable_mutable_extensions_test.dart
index cff1e97..93fd596 100644
--- a/test/collection/iterable_mutable_extensions_test.dart
+++ b/test/collection/iterable_mutable_extensions_test.dart
@@ -2,8 +2,6 @@ import "package:kt_dart/collection.dart";
 import "package:kt_dart/src/collection/impl/iterable.dart";
 import "package:test/test.dart";
 
-import "../test/assert_dart.dart";
-
 void main() {
   group("KtMutableIterableExtensions", () {
     group("mutableIterable", () {
@@ -45,27 +43,23 @@ void main() {
 void testIterable(KtMutableIterable<T> Function<T>() emptyIterable,
     KtMutableIterable<T> Function<T>(Iterable<T> iterable) mutableIterableOf,
     {bool ordered = true}) {
-  group("removal functions throw", () {});
-
   group("removeAllWhere", () {
     test("removeAllWhere", () {
-      final iterable = mutableIterableOf(["paul", "john", "max", "lisa"]);
-      final e = catchException(
-          () => iterable.removeAllWhere((it) => it.endsWith("x")));
-      // TODO remove error assertion once implemented
-      expect(e, const TypeMatcher<UnimplementedError>());
-      //expect(iterable.toList(), listOf("paul", "john", "lisa"));
+      final mutableIterable =
+          mutableIterableOf(["paul", "john", "max", "lisa"]);
+      mutableIterable.removeAllWhere((it) => it.endsWith("x"));
+
+      expect(mutableIterable.toSet(), setOf("paul", "john", "lisa"));
     });
   });
 
   group("retainAllWhere", () {
     test("retainAllWhere", () {
-      final iterable = mutableIterableOf(["paul", "john", "max", "lisa"]);
-      final e = catchException(
-          () => iterable.retainAllWhere((it) => it.endsWith("x")));
-      // TODO remove error assertion once implemented
-      expect(e, const TypeMatcher<UnimplementedError>());
-      //expect(iterable.toList(), listOf("max"));
+      final mutableIterable =
+          mutableIterableOf(["paul", "john", "max", "lisa"]);
+      mutableIterable.retainAllWhere((it) => it.endsWith("x"));
+
+      expect(mutableIterable.toSet(), setOf("max"));
     });
   });
 }
diff --git a/test/collection/iterator_test.dart b/test/collection/iterator_test.dart
index 5020da1..5822374 100644
--- a/test/collection/iterator_test.dart
+++ b/test/collection/iterator_test.dart
@@ -51,10 +51,37 @@ void main() {
       expect(e, const TypeMatcher<IndexOutOfBoundsException>());
     });
 
-    test("remove is not implemented", () {
-      final i = InterOpKtListIterator(["a", "b"], 0);
-      final e = catchException(() => i.remove());
-      expect(e, const TypeMatcher<UnimplementedError>());
+    test("remove() removes last returned element", () {
+      final list = mutableListOf("a", "b", "c");
+      final iterator = list.iterator();
+      iterator.next();
+      iterator.remove();
+      expect(list, listOf("b", "c"));
+    });
+
+    test("remove() can delete multiple elements", () {
+      final list = mutableListOf("a", "b", "c");
+      final iterator = list.iterator();
+      iterator.next();
+      iterator.remove();
+      iterator.next();
+      iterator.next();
+      iterator.remove();
+      expect(list, listOf("b"));
+    });
+
+    test("remove() throws when there is no last returned element", () {
+      final iterator = mutableListOf("a", "b", "c").iterator();
+      final exception = catchException(() => iterator.remove());
+      expect(exception, const TypeMatcher<IndexOutOfBoundsException>());
+    });
+
+    test("remove() throws when called multiple times in a row", () {
+      final iterator = mutableListOf("a", "b", "c").iterator();
+      iterator.next();
+      iterator.remove();
+      final exception = catchException(() => iterator.remove());
+      expect(exception, const TypeMatcher<IndexOutOfBoundsException>());
     });
 
     test("add adds item to underlying list", () {
diff --git a/test/collection/list_mutable_extensions_test.dart b/test/collection/list_mutable_extensions_test.dart
index 84a93ab..ef7d15c 100644
--- a/test/collection/list_mutable_extensions_test.dart
+++ b/test/collection/list_mutable_extensions_test.dart
@@ -312,4 +312,41 @@ void testList(
       expect(firstList, isNot(equals(secondList)));
     });
   });
+
+  test("remove item from list via iterator", () {
+    final pokemon = mutableListOf(
+      "Bulbasaur",
+      "Ivysaur",
+    );
+    final iterator = pokemon.iterator();
+    expect(iterator.hasNext(), isTrue);
+    final next = iterator.next();
+    expect(next, "Bulbasaur");
+
+    iterator.remove();
+    // removed first item
+    expect(pokemon, listOf("Ivysaur"));
+  });
+
+  test("remove handles null value", () {
+    final pokemon = mutableListOf(
+      null,
+      "Bulbasaur",
+      "Ivysaur",
+    );
+    final KtMutableIterator<String?> i = pokemon.iterator();
+    expect(i.hasNext(), isTrue);
+    expect(i.next(), null);
+    i.remove(); // remove null
+
+    expect(i.hasNext(), isTrue);
+    expect(i.next(), "Bulbasaur");
+
+    expect(i.hasNext(), isTrue);
+    expect(i.next(), "Ivysaur");
+
+    expect(i.hasNext(), isFalse);
+
+    expect(pokemon, listOf("Bulbasaur", "Ivysaur"));
+  });
 }
diff --git a/test/collection/map_mutable_extensions_test.dart b/test/collection/map_mutable_extensions_test.dart
index de40155..2bad956 100644
--- a/test/collection/map_mutable_extensions_test.dart
+++ b/test/collection/map_mutable_extensions_test.dart
@@ -1,8 +1,6 @@
 import "package:kt_dart/collection.dart";
 import "package:test/test.dart";
 
-import "../test/assert_dart.dart";
-
 void main() {
   group("KtMutableMapExtensions", () {
     group("mutableMapFrom", () {
@@ -189,7 +187,7 @@ void testMutableMap(KtMutableMap<K, V> Function<K, V>() emptyMap,
   });
 
   group("iterator", () {
-    test("iterator is iterates", () {
+    test("iterator iterates", () {
       final pokemon = mutableMapFrom({
         1: "Bulbasaur",
         2: "Ivysaur",
@@ -208,24 +206,59 @@ void testMutableMap(KtMutableMap<K, V> Function<K, V>() emptyMap,
       expect(i.hasNext(), isFalse);
     });
 
-    group("remove doesn't work", () {
-      test("iterator is iterates", () {
-        final pokemon = mutableMapFrom({
-          1: "Bulbasaur",
-          2: "Ivysaur",
-        });
-        final KtMutableIterator<KtMapEntry<int, String>> i = pokemon.iterator();
-        expect(i.hasNext(), isTrue);
+    test("remove() handles null keys", () {
+      final pokemon = mutableMapFrom({
+        null: "Missingno",
+        1: "Bulbasaur",
+        2: "Ivysaur",
+      });
+      final KtMutableIterator<KtMapEntry<int?, String>> i = pokemon.iterator();
+      while (i.hasNext()) {
         final next = i.next();
-        expect(next.key, 1);
-        expect(next.value, "Bulbasaur");
+        if (next.key == null) {
+          // remove Missingno
+          i.remove();
+          break;
+        }
+      }
+      expect(pokemon, mapFrom({1: "Bulbasaur", 2: "Ivysaur"}));
+    });
+
+    test("remove item from map via iterator", () {
+      final pokemon = mutableMapFrom({
+        1: "Bulbasaur",
+        2: "Ivysaur",
+      });
+      final iterator = pokemon.iterator();
+      expect(iterator.hasNext(), isTrue);
+      final next = iterator.next();
+      expect(next.key, 1);
+      expect(next.value, "Bulbasaur");
+
+      iterator.remove();
+      // removed first item
+      expect(pokemon, mapFrom({2: "Ivysaur"}));
+    });
+
+    test("iterator throws when remove() is called before next()", () {
+      final map = mutableMapFrom({
+        1: "Bulbasaur",
+        2: "Ivysaur",
+      });
+
+      expect(() => map.iterator().remove(), throwsStateError);
+    });
 
-        // TODO replace error assertion with value assertion when https://github.com/passsy/dart_kollection/issues/5 has been fixed
-        final e = catchException(() => i.remove());
-        expect(e, equals(const TypeMatcher<UnimplementedError>()));
-        // removed first item
-        //expect(pokemon, mapFrom({2: "Ivysaur"}));
+    test("iterator throws when remove() is called multiple times in a row", () {
+      final map = mutableMapFrom({
+        1: "Bulbasaur",
+        2: "Ivysaur",
       });
+      final iterator = map.iterator();
+      iterator.next();
+      iterator.remove();
+
+      expect(() => iterator.remove(), throwsStateError);
     });
   });
 
diff --git a/test/collection/set_mutable_extensions_test.dart b/test/collection/set_mutable_extensions_test.dart
index f3a916f..02ede76 100644
--- a/test/collection/set_mutable_extensions_test.dart
+++ b/test/collection/set_mutable_extensions_test.dart
@@ -45,4 +45,40 @@ void testSet(
       expect(dartList, {1});
     });
   });
+
+  test("remove item from ser via iterator", () {
+    final pokemon = mutableSetOf(
+      "Bulbasaur",
+      "Ivysaur",
+    );
+    final iterator = pokemon.iterator();
+    expect(iterator.hasNext(), isTrue);
+    final next = iterator.next();
+    iterator.remove();
+
+    // order is unknown, catch both cases
+    if (next == "Bulbasaur") {
+      expect(pokemon, setOf("Ivysaur"));
+    } else {
+      expect(pokemon, setOf("Bulbasaur"));
+    }
+  });
+
+  test("remove() handles null value", () {
+    final pokemon = mutableSetOf(
+      null,
+      "Bulbasaur",
+      "Ivysaur",
+    );
+    final KtMutableIterator<String?> i = pokemon.iterator();
+    while (i.hasNext()) {
+      final next = i.next();
+      if (next == null) {
+        // remove null
+        i.remove();
+        break;
+      }
+    }
+    expect(pokemon, setOf("Bulbasaur", "Ivysaur"));
+  });
 }
diff --git a/test/collection/set_mutable_test.dart b/test/collection/set_mutable_test.dart
index 326e9c2..1a2785e 100644
--- a/test/collection/set_mutable_test.dart
+++ b/test/collection/set_mutable_test.dart
@@ -71,6 +71,34 @@ void testMutableSet(
     expect(set.size, 3);
   });
 
+  test("iterator().remove() removes last returned element", () {
+    final set = mutableSetOf("a", "b", "c");
+    final iterator = set.iterator();
+    final lastReturnedValue = iterator.next();
+    iterator.remove();
+
+    expect(set.contains(lastReturnedValue), false);
+  });
+
+  test("iterator().remove() throws when there is no last returned value", () {
+    final set = mutableSetOf("a", "b", "c");
+    final iterator = set.iterator();
+    final e = catchException(() => iterator.remove());
+
+    expect(e, const TypeMatcher<StateError>());
+  });
+
+  test("iterator().remove() throws when called multiple times in a row", () {
+    final set = mutableSetOf("a", "b", "c");
+    final iterator = set.iterator();
+    iterator.next();
+    iterator.next();
+    iterator.remove();
+    final e = catchException(() => iterator.remove());
+
+    expect(e, const TypeMatcher<StateError>());
+  });
+
   if (ordered) {
     test("mutableSetOf iterates in order as specified", () {
       final set = mutableSetOf("a", "b", "c");