1 | // Copyright 2014 The Flutter Authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style license that can be |
3 | // found in the LICENSE file. |
4 | |
5 | import 'dart:collection'; |
6 | |
7 | /// A list optimized for the observer pattern when there are small numbers of |
8 | /// observers. |
9 | /// |
10 | /// Consider using an [ObserverList] instead of a [List] when the number of |
11 | /// [contains] calls dominates the number of [add] and [remove] calls. |
12 | /// |
13 | /// This class will include in the [iterator] each added item in the order it |
14 | /// was added, as many times as it was added. |
15 | /// |
16 | /// If there will be a large number of observers, consider using |
17 | /// [HashedObserverList] instead. It has slightly different iteration semantics, |
18 | /// but serves a similar purpose, while being more efficient for large numbers |
19 | /// of observers. |
20 | /// |
21 | /// See also: |
22 | /// |
23 | /// * [HashedObserverList] for a list that is optimized for larger numbers of |
24 | /// observers. |
25 | // TODO(ianh): Use DelegatingIterable, possibly moving it from the collection |
26 | // package to foundation, or to dart:collection. |
27 | class ObserverList<T> extends Iterable<T> { |
28 | final List<T> _list = <T>[]; |
29 | bool _isDirty = false; |
30 | late final HashSet<T> _set = HashSet<T>(); |
31 | |
32 | /// Adds an item to the end of this list. |
33 | /// |
34 | /// This operation has constant time complexity. |
35 | void add(T item) { |
36 | _isDirty = true; |
37 | _list.add(item); |
38 | } |
39 | |
40 | /// Removes an item from the list. |
41 | /// |
42 | /// This is O(N) in the number of items in the list. |
43 | /// |
44 | /// Returns whether the item was present in the list. |
45 | bool remove(T item) { |
46 | _isDirty = true; |
47 | _set.clear(); // Clear the set so that we don't leak items. |
48 | return _list.remove(item); |
49 | } |
50 | |
51 | /// Removes all items from the list. |
52 | void clear() { |
53 | _isDirty = false; |
54 | _list.clear(); |
55 | _set.clear(); |
56 | } |
57 | |
58 | @override |
59 | bool contains(Object? element) { |
60 | if (_list.length < 3) { |
61 | return _list.contains(element); |
62 | } |
63 | |
64 | if (_isDirty) { |
65 | _set.addAll(_list); |
66 | _isDirty = false; |
67 | } |
68 | |
69 | return _set.contains(element); |
70 | } |
71 | |
72 | @override |
73 | Iterator<T> get iterator => _list.iterator; |
74 | |
75 | @override |
76 | bool get isEmpty => _list.isEmpty; |
77 | |
78 | @override |
79 | bool get isNotEmpty => _list.isNotEmpty; |
80 | |
81 | @override |
82 | List<T> toList({bool growable = true}) { |
83 | return _list.toList(growable: growable); |
84 | } |
85 | } |
86 | |
87 | /// A list optimized for the observer pattern, but for larger numbers of observers. |
88 | /// |
89 | /// For small numbers of observers (e.g. less than 10), use [ObserverList] instead. |
90 | /// |
91 | /// The iteration semantics of the this class are slightly different from |
92 | /// [ObserverList]. This class will only return an item once in the [iterator], |
93 | /// no matter how many times it was added, although it does require that an item |
94 | /// be removed as many times as it was added for it to stop appearing in the |
95 | /// [iterator]. It will return them in the order the first instance of an item |
96 | /// was originally added. |
97 | /// |
98 | /// See also: |
99 | /// |
100 | /// * [ObserverList] for a list that is fast for small numbers of observers. |
101 | class HashedObserverList<T> extends Iterable<T> { |
102 | final LinkedHashMap<T, int> _map = LinkedHashMap<T, int>(); |
103 | |
104 | /// Adds an item to the end of this list. |
105 | /// |
106 | /// This has constant time complexity. |
107 | void add(T item) { |
108 | _map[item] = (_map[item] ?? 0) + 1; |
109 | } |
110 | |
111 | /// Removes an item from the list. |
112 | /// |
113 | /// This operation has constant time complexity. |
114 | /// |
115 | /// Returns whether the item was present in the list. |
116 | bool remove(T item) { |
117 | final int? value = _map[item]; |
118 | if (value == null) { |
119 | return false; |
120 | } |
121 | if (value == 1) { |
122 | _map.remove(item); |
123 | } else { |
124 | _map[item] = value - 1; |
125 | } |
126 | return true; |
127 | } |
128 | |
129 | @override |
130 | bool contains(Object? element) => _map.containsKey(element); |
131 | |
132 | @override |
133 | Iterator<T> get iterator => _map.keys.iterator; |
134 | |
135 | @override |
136 | bool get isEmpty => _map.isEmpty; |
137 | |
138 | @override |
139 | bool get isNotEmpty => _map.isNotEmpty; |
140 | } |
141 | |