1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
// 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;
}