CombinedMapView.keys fix (#110)
Fixes https://github.com/dart-lang/collection/issues/109
Adds a custom iterable/iterator that can filter out duplicates and use that for the `CombineMapView.keys` getter.
Updates tests to contain duplicates in maps, and ensure the keys/values from the earlier maps are the ones that are returned.
Updates the changelog and docs to no longer claim `O(maps)` for the length getter. This now requires iteration of all items and is `O(total map entries)`.
Prepare to publish as 1.14.12
diff --git a/CHANGELOG.md b/CHANGELOG.md
index f806f93..b5db991 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,12 @@
+## 1.14.12
+
+* Fix `CombinedMapView.keys`, `CombinedMapView.length`,
+ `CombinedMapView.forEach`, and `CombinedMapView.values` to work as specified
+ and not repeat duplicate items from the maps.
+ * As a result of this fix the `length` getter now must iterate all maps in
+ order to remove duplicates and return an accurate length, so it is no
+ longer `O(maps)`.
+
## 1.14.11
* Set max SDK version to `<3.0.0`.
diff --git a/lib/src/combined_wrappers/combined_map.dart b/lib/src/combined_wrappers/combined_map.dart
index aa86b5d..386a6de 100644
--- a/lib/src/combined_wrappers/combined_map.dart
+++ b/lib/src/combined_wrappers/combined_map.dart
@@ -13,14 +13,16 @@
/// accessing individual map instances. In the occasion where a key occurs in
/// multiple maps the first value is returned.
///
-/// The resulting map has an index operator (`[]`) and `length` property that
-/// are both `O(maps)`, rather than `O(1)`, and the map is unmodifiable - but
-/// underlying changes to these maps are still accessible from the resulting
-/// map.
+/// The resulting map has an index operator (`[]`) that is `O(maps)`, rather
+/// than `O(1)`, and the map is unmodifiable, but underlying changes to these
+/// maps are still accessible from the resulting map.
+///
+/// The `length` getter is `O(M)` where M is the total number of entries in
+/// all maps, since it has to remove duplicate entries.
class CombinedMapView<K, V> extends UnmodifiableMapBase<K, V> {
final Iterable<Map<K, V>> _maps;
- /// Create a new combined view into multiple maps.
+ /// Create a new combined view of multiple maps.
///
/// The iterable is accessed lazily so it should be collection type like
/// [List] or [Set] rather than a lazy iterable produced by `map()` et al.
@@ -39,8 +41,11 @@
/// The keys of [this].
///
- /// The returned iterable has efficient `length` and `contains` operations,
- /// based on [length] and [containsKey] of the individual maps.
+ /// The returned iterable has efficient `contains` operations, assuming the
+ /// iterables returned by the wrapped maps have efficient `contains` operations
+ /// for their `keys` iterables.
+ ///
+ /// The `length` must do deduplication and thus is not optimized.
///
/// The order of iteration is defined by the individual `Map` implementations,
/// but must be consistent between changes to the maps.
@@ -48,5 +53,45 @@
/// Unlike most [Map] implementations, modifying an individual map while
/// iterating the keys will _sometimes_ throw. This behavior may change in
/// the future.
- Iterable<K> get keys => CombinedIterableView<K>(_maps.map((m) => m.keys));
+ Iterable<K> get keys => _DeduplicatingIterableView(
+ CombinedIterableView(_maps.map((m) => m.keys)));
+}
+
+/// A view of an iterable that skips any duplicate entries.
+class _DeduplicatingIterableView<T> extends IterableBase<T> {
+ final Iterable<T> _iterable;
+
+ const _DeduplicatingIterableView(this._iterable);
+
+ Iterator<T> get iterator => _DeduplicatingIterator(_iterable.iterator);
+
+ // Special cased contains/isEmpty since many iterables have an efficient
+ // implementation instead of running through the entire iterator.
+ //
+ // Note: We do not do this for `length` because we have to remove the
+ // duplicates.
+
+ bool contains(Object element) => _iterable.contains(element);
+
+ bool get isEmpty => _iterable.isEmpty;
+}
+
+/// An iterator that wraps another iterator and skips duplicate values.
+class _DeduplicatingIterator<T> implements Iterator<T> {
+ final Iterator<T> _iterator;
+
+ final _emitted = HashSet<T>();
+
+ _DeduplicatingIterator(this._iterator);
+
+ T get current => _iterator.current;
+
+ bool moveNext() {
+ while (_iterator.moveNext()) {
+ if (_emitted.add(current)) {
+ return true;
+ }
+ }
+ return false;
+ }
}
diff --git a/pubspec.yaml b/pubspec.yaml
index d8775b2..95759b8 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: collection
-version: 1.14.12-dev
+version: 1.14.12
description: Collections and utilities functions and classes related to collections.
author: Dart Team <misc@dartlang.org>
diff --git a/test/combined_wrapper/map_test.dart b/test/combined_wrapper/map_test.dart
index 605c0be..ad6ccc2 100644
--- a/test/combined_wrapper/map_test.dart
+++ b/test/combined_wrapper/map_test.dart
@@ -2,6 +2,8 @@
// 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:collection/collection.dart';
import 'package:test/test.dart';
@@ -11,13 +13,23 @@
var map1 = const {1: 1, 2: 2, 3: 3};
var map2 = const {4: 4, 5: 5, 6: 6};
var map3 = const {7: 7, 8: 8, 9: 9};
- var concat = <int, int>{}..addAll(map1)..addAll(map2)..addAll(map3);
+ var map4 = const {1: -1, 2: -2, 3: -3};
+ var concat = SplayTreeMap<int, int>()
+ // The duplicates map appears first here but last in the CombinedMapView
+ // which has the opposite semantics of `concat`. Keys/values should be
+ // returned from the first map that contains them.
+ ..addAll(map4)
+ ..addAll(map1)
+ ..addAll(map2)
+ ..addAll(map3);
// In every way possible this should test the same as an UnmodifiableMapView.
common.testReadMap(
- concat, CombinedMapView([map1, map2, map3]), 'CombinedMapView');
+ concat, CombinedMapView([map1, map2, map3, map4]), 'CombinedMapView');
- common.testReadMap(concat, CombinedMapView([map1, {}, map2, {}, map3, {}]),
+ common.testReadMap(
+ concat,
+ CombinedMapView([map1, {}, map2, {}, map3, {}, map4, {}]),
'CombinedMapView (some empty)');
test('should function as an empty map when no maps are passed', () {
@@ -50,4 +62,10 @@
backing1.addAll(map1);
expect(combined, map1);
});
+
+ test('re-iterating keys produces same result', () {
+ var combined = CombinedMapView([map1, map2, map3, map4]);
+ var keys = combined.keys;
+ expect(keys.toList(), keys.toList());
+ });
}
