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
5import '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.
27class 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 final bool removed = _list.remove(item);
47 if (removed) {
48 _isDirty = true;
49 _set.clear(); // Clear the set so that we don't leak items.
50 }
51 return removed;
52 }
53
54 /// Removes all items from the [ObserverList].
55 void clear() {
56 _isDirty = false;
57 _list.clear();
58 _set.clear();
59 }
60
61 @override
62 bool contains(Object? element) {
63 if (_list.length < 3) {
64 return _list.contains(element);
65 }
66
67 if (_isDirty) {
68 _set.addAll(_list);
69 _isDirty = false;
70 }
71
72 return _set.contains(element);
73 }
74
75 @override
76 Iterator<T> get iterator => _list.iterator;
77
78 @override
79 bool get isEmpty => _list.isEmpty;
80
81 @override
82 bool get isNotEmpty => _list.isNotEmpty;
83
84 /// Creates a List containing the elements of the [ObserverList].
85 ///
86 /// Overrides the default implementation of the [Iterable] to reduce number
87 /// of allocations.
88 @override
89 List<T> toList({bool growable = true}) {
90 return _list.toList(growable: growable);
91 }
92}
93
94/// A list optimized for the observer pattern, but for larger numbers of observers.
95///
96/// For small numbers of observers (e.g. less than 10), use [ObserverList] instead.
97///
98/// The iteration semantics of the this class are slightly different from
99/// [ObserverList]. This class will only return an item once in the [iterator],
100/// no matter how many times it was added, although it does require that an item
101/// be removed as many times as it was added for it to stop appearing in the
102/// [iterator]. It will return them in the order the first instance of an item
103/// was originally added.
104///
105/// See also:
106///
107/// * [ObserverList] for a list that is fast for small numbers of observers.
108class HashedObserverList<T> extends Iterable<T> {
109 final Map<T, int> _map = <T, int>{};
110
111 /// Adds an item to the end of this list.
112 ///
113 /// This has constant time complexity.
114 void add(T item) {
115 _map[item] = (_map[item] ?? 0) + 1;
116 }
117
118 /// Removes an item from the list.
119 ///
120 /// This operation has constant time complexity.
121 ///
122 /// Returns whether the item was present in the list.
123 bool remove(T item) {
124 final int? value = _map[item];
125 if (value == null) {
126 return false;
127 }
128 if (value == 1) {
129 _map.remove(item);
130 } else {
131 _map[item] = value - 1;
132 }
133 return true;
134 }
135
136 /// Removes all items from the [HashedObserverList].
137 void clear() => _map.clear();
138
139 @override
140 bool contains(Object? element) => _map.containsKey(element);
141
142 @override
143 Iterator<T> get iterator => _map.keys.iterator;
144
145 @override
146 bool get isEmpty => _map.isEmpty;
147
148 @override
149 bool get isNotEmpty => _map.isNotEmpty;
150
151 /// Creates a List containing the elements of the [HashedObserverList].
152 ///
153 /// Overrides the default implementation of [Iterable] to reduce number of
154 /// allocations.
155 @override
156 List<T> toList({bool growable = true}) {
157 final Iterator<T> iterator = _map.keys.iterator;
158 return List<T>.generate(_map.length, (_) => (iterator..moveNext()).current, growable: growable);
159 }
160}
161