blob: 3bd2aa87eb8507da9d5352e7df0302cf2490caff [file] [log] [blame]
// Copyright 2014 The Flutter Authors. 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';
/// A list optimized for the observer pattern when there are small numbers of
/// observers.
///
/// Consider using an [ObserverList] instead of a [List] when the number of
/// [contains] calls dominates the number of [add] and [remove] calls.
///
/// This class will include in the [iterator] each added item in the order it
/// was added, as many times as it was added.
///
/// If there will be a large number of observers, consider using
/// [HashedObserverList] instead. It has slightly different iteration semantics,
/// but serves a similar purpose, while being more efficient for large numbers
/// of observers.
///
/// See also:
///
/// * [HashedObserverList] for a list that is optimized for larger numbers of
/// observers.
// TODO(ianh): Use DelegatingIterable, possibly moving it from the collection
// package to foundation, or to dart:collection.
class ObserverList<T> extends Iterable<T> {
final List<T> _list = <T>[];
bool _isDirty = false;
HashSet<T> _set;
/// Adds an item to the end of this list.
///
/// This operation has constant time complexity.
void add(T item) {
_isDirty = true;
_list.add(item);
}
/// Removes an item from the list.
///
/// This is O(N) in the number of items in the list.
///
/// Returns whether the item was present in the list.
bool remove(T item) {
_isDirty = true;
_set?.clear(); // Clear the set so that we don't leak items.
return _list.remove(item);
}
@override
bool contains(Object element) {
if (_list.length < 3)
return _list.contains(element);
if (_isDirty) {
if (_set == null) {
_set = HashSet<T>.from(_list);
} else {
_set.addAll(_list);
}
_isDirty = false;
}
return _set.contains(element);
}
@override
Iterator<T> get iterator => _list.iterator;
@override
bool get isEmpty => _list.isEmpty;
@override
bool get isNotEmpty => _list.isNotEmpty;
}
/// A list optimized for the observer pattern, but for larger numbers of observers.
///
/// For small numbers of observers (e.g. less than 10), use [ObserverList] instead.
///
/// The iteration semantics of the this class are slightly different from
/// [ObserverList]. This class will only return an item once in the [iterator],
/// no matter how many times it was added, although it does require that an item
/// be removed as many times as it was added for it to stop appearing in the
/// [iterator]. It will return them in the order the first instance of an item
/// was originally added.
///
/// See also:
///
/// * [ObserverList] for a list that is fast for small numbers of observers.
class HashedObserverList<T> extends Iterable<T> {
final LinkedHashMap<T, int> _map = LinkedHashMap<T, int>();
/// Adds an item to the end of this list.
///
/// This has constant time complexity.
void add(T item) {
_map[item] = (_map[item] ?? 0) + 1;
}
/// Removes an item from the list.
///
/// This operation has constant time complexity.
///
/// Returns whether the item was present in the list.
bool remove(T item) {
final int value = _map[item];
if (value == null) {
return false;
}
if (value == 1) {
_map.remove(item);
} else {
_map[item] = value - 1;
}
return true;
}
@override
bool contains(Object element) => _map.containsKey(element);
@override
Iterator<T> get iterator => _map.keys.iterator;
@override
bool get isEmpty => _map.isEmpty;
@override
bool get isNotEmpty => _map.isNotEmpty;
}