blob: ae7200688d0e1dbd17f537da86fb1f06c2198b5c [file] [log] [blame]
// Copyright (c) 2017, 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 'combined_iterable.dart';
/// Returns a new map that represents maps flattened into a single map.
/// All methods and accessors treat the new map as-if it were a single
/// concatenated map, but the underlying implementation is based on lazily
/// 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 (`[]`) 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 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.
V? operator [](Object? key) {
for (var map in _maps) {
// Avoid two hash lookups on a positive hit.
var value = map[key];
if (value != null || map.containsKey(value)) {
return value;
return null;
/// The keys of [this].
/// 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.
/// 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 => _DeduplicatingIterableView(
CombinedIterableView( => 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>();
T get current => _iterator.current;
bool moveNext() {
while (_iterator.moveNext()) {
if (_emitted.add(current)) {
return true;
return false;