OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 part of dart.collection; | 5 part of dart.collection; |
6 | 6 |
7 typedef bool _Predicate<T>(T value); | 7 typedef bool _Predicate<T>(T value); |
8 | 8 |
9 /** | 9 /** |
10 * A node in a splay tree. It holds the sorting key and the left | 10 * A node in a splay tree. It holds the sorting key and the left |
(...skipping 18 matching lines...) Expand all Loading... |
29 } | 29 } |
30 | 30 |
31 /** | 31 /** |
32 * A splay tree is a self-balancing binary search tree. | 32 * A splay tree is a self-balancing binary search tree. |
33 * | 33 * |
34 * It has the additional property that recently accessed elements | 34 * It has the additional property that recently accessed elements |
35 * are quick to access again. | 35 * are quick to access again. |
36 * It performs basic operations such as insertion, look-up and | 36 * It performs basic operations such as insertion, look-up and |
37 * removal, in O(log(n)) amortized time. | 37 * removal, in O(log(n)) amortized time. |
38 */ | 38 */ |
39 abstract class _SplayTree<K> { | 39 abstract class _SplayTree<K, Node extends _SplayTreeNode<K>> { |
40 // The root node of the splay tree. It will contain either the last | 40 // The root node of the splay tree. It will contain either the last |
41 // element inserted or the last element looked up. | 41 // element inserted or the last element looked up. |
42 _SplayTreeNode<K> _root; | 42 Node get _root; |
| 43 set _root(Node newValue); |
43 | 44 |
44 // The dummy node used when performing a splay on the tree. Reusing it | 45 // The dummy node used when performing a splay on the tree. Reusing it |
45 // avoids allocating a node each time a splay is performed. | 46 // avoids allocating a node each time a splay is performed. |
46 _SplayTreeNode<K> _dummy = new _SplayTreeNode<K>(null); | 47 Node get _dummy; |
47 | 48 |
48 // Number of elements in the splay tree. | 49 // Number of elements in the splay tree. |
49 int _count = 0; | 50 int _count = 0; |
50 | 51 |
51 /** | 52 /** |
52 * Counter incremented whenever the keys in the map changes. | 53 * Counter incremented whenever the keys in the map changes. |
53 * | 54 * |
54 * Used to detect concurrent modifications. | 55 * Used to detect concurrent modifications. |
55 */ | 56 */ |
56 int _modificationCount = 0; | 57 int _modificationCount = 0; |
57 | 58 |
58 /** | 59 /** |
59 * Counter incremented whenever the tree structure changes. | 60 * Counter incremented whenever the tree structure changes. |
60 * | 61 * |
61 * Used to detect that an in-place traversal cannot use | 62 * Used to detect that an in-place traversal cannot use |
62 * cached information that relies on the tree structure. | 63 * cached information that relies on the tree structure. |
63 */ | 64 */ |
64 int _splayCount = 0; | 65 int _splayCount = 0; |
65 | 66 |
| 67 /** The comparator that is used for this splay tree. */ |
| 68 Comparator<K> get _comparator; |
| 69 |
| 70 /** The predicate to determine that a given object is a valid key. */ |
| 71 _Predicate get _validKey; |
| 72 |
66 /** Comparison used to compare keys. */ | 73 /** Comparison used to compare keys. */ |
67 int _compare(K key1, K key2); | 74 int _compare(K key1, K key2); |
68 | 75 |
69 Comparator<K> get _comparator; | |
70 | |
71 _Predicate<Object> get _validKey; | |
72 | |
73 /** | 76 /** |
74 * Perform the splay operation for the given key. Moves the node with | 77 * Perform the splay operation for the given key. Moves the node with |
75 * the given key to the top of the tree. If no node has the given | 78 * the given key to the top of the tree. If no node has the given |
76 * key, the last node on the search path is moved to the top of the | 79 * key, the last node on the search path is moved to the top of the |
77 * tree. This is the simplified top-down splaying algorithm from: | 80 * tree. This is the simplified top-down splaying algorithm from: |
78 * "Self-adjusting Binary Search Trees" by Sleator and Tarjan. | 81 * "Self-adjusting Binary Search Trees" by Sleator and Tarjan. |
79 * | 82 * |
80 * Returns the result of comparing the new root of the tree to [key]. | 83 * Returns the result of comparing the new root of the tree to [key]. |
81 * Returns -1 if the table is empty. | 84 * Returns -1 if the table is empty. |
82 */ | 85 */ |
83 int _splay(K key) { | 86 int _splay(K key) { |
84 if (_root == null) return -1; | 87 if (_root == null) return -1; |
85 | 88 |
86 // The right child of the dummy node will hold | 89 // The right child of the dummy node will hold |
87 // the L tree of the algorithm. The left child of the dummy node | 90 // the L tree of the algorithm. The left child of the dummy node |
88 // will hold the R tree of the algorithm. Using a dummy node, left | 91 // will hold the R tree of the algorithm. Using a dummy node, left |
89 // and right will always be nodes and we avoid special cases. | 92 // and right will always be nodes and we avoid special cases. |
90 _SplayTreeNode<K> left = _dummy; | 93 Node left = _dummy; |
91 _SplayTreeNode<K> right = _dummy; | 94 Node right = _dummy; |
92 _SplayTreeNode<K> current = _root; | 95 Node current = _root; |
93 int comp; | 96 int comp; |
94 while (true) { | 97 while (true) { |
95 comp = _compare(current.key, key); | 98 comp = _compare(current.key, key); |
96 if (comp > 0) { | 99 if (comp > 0) { |
97 if (current.left == null) break; | 100 if (current.left == null) break; |
98 comp = _compare(current.left.key, key); | 101 comp = _compare(current.left.key, key); |
99 if (comp > 0) { | 102 if (comp > 0) { |
100 // Rotate right. | 103 // Rotate right. |
101 _SplayTreeNode<K> tmp = current.left; | 104 _SplayTreeNode<K> tmp = current.left; |
102 current.left = tmp.right; | 105 current.left = tmp.right; |
103 tmp.right = current; | 106 tmp.right = current; |
104 current = tmp; | 107 current = tmp; |
105 if (current.left == null) break; | 108 if (current.left == null) break; |
106 } | 109 } |
107 // Link right. | 110 // Link right. |
108 right.left = current; | 111 right.left = current; |
109 right = current; | 112 right = current; |
110 current = current.left; | 113 current = current.left; |
111 } else if (comp < 0) { | 114 } else if (comp < 0) { |
112 if (current.right == null) break; | 115 if (current.right == null) break; |
113 comp = _compare(current.right.key, key); | 116 comp = _compare(current.right.key, key); |
114 if (comp < 0) { | 117 if (comp < 0) { |
115 // Rotate left. | 118 // Rotate left. |
116 _SplayTreeNode<K> tmp = current.right; | 119 Node tmp = current.right; |
117 current.right = tmp.left; | 120 current.right = tmp.left; |
118 tmp.left = current; | 121 tmp.left = current; |
119 current = tmp; | 122 current = tmp; |
120 if (current.right == null) break; | 123 if (current.right == null) break; |
121 } | 124 } |
122 // Link left. | 125 // Link left. |
123 left.right = current; | 126 left.right = current; |
124 left = current; | 127 left = current; |
125 current = current.right; | 128 current = current.right; |
126 } else { | 129 } else { |
(...skipping 10 matching lines...) Expand all Loading... |
137 _dummy.right = null; | 140 _dummy.right = null; |
138 _dummy.left = null; | 141 _dummy.left = null; |
139 _splayCount++; | 142 _splayCount++; |
140 return comp; | 143 return comp; |
141 } | 144 } |
142 | 145 |
143 // Emulates splaying with a key that is smaller than any in the subtree | 146 // Emulates splaying with a key that is smaller than any in the subtree |
144 // anchored at [node]. | 147 // anchored at [node]. |
145 // and that node is returned. It should replace the reference to [node] | 148 // and that node is returned. It should replace the reference to [node] |
146 // in any parent tree or root pointer. | 149 // in any parent tree or root pointer. |
147 _SplayTreeNode<K> _splayMin(_SplayTreeNode<K> node) { | 150 Node _splayMin(Node node) { |
148 _SplayTreeNode current = node; | 151 Node current = node; |
149 while (current.left != null) { | 152 while (current.left != null) { |
150 _SplayTreeNode left = current.left; | 153 Node left = current.left; |
151 current.left = left.right; | 154 current.left = left.right; |
152 left.right = current; | 155 left.right = current; |
153 current = left; | 156 current = left; |
154 } | 157 } |
155 return current; | 158 return current; |
156 } | 159 } |
157 | 160 |
158 // Emulates splaying with a key that is greater than any in the subtree | 161 // Emulates splaying with a key that is greater than any in the subtree |
159 // anchored at [node]. | 162 // anchored at [node]. |
160 // After this, the largest element in the tree is the root of the subtree, | 163 // After this, the largest element in the tree is the root of the subtree, |
161 // and that node is returned. It should replace the reference to [node] | 164 // and that node is returned. It should replace the reference to [node] |
162 // in any parent tree or root pointer. | 165 // in any parent tree or root pointer. |
163 _SplayTreeNode<K> _splayMax(_SplayTreeNode<K> node) { | 166 Node _splayMax(Node node) { |
164 _SplayTreeNode current = node; | 167 Node current = node; |
165 while (current.right != null) { | 168 while (current.right != null) { |
166 _SplayTreeNode right = current.right; | 169 Node right = current.right; |
167 current.right = right.left; | 170 current.right = right.left; |
168 right.left = current; | 171 right.left = current; |
169 current = right; | 172 current = right; |
170 } | 173 } |
171 return current; | 174 return current; |
172 } | 175 } |
173 | 176 |
174 _SplayTreeNode _remove(K key) { | 177 Node _remove(K key) { |
175 if (_root == null) return null; | 178 if (_root == null) return null; |
176 int comp = _splay(key); | 179 int comp = _splay(key); |
177 if (comp != 0) return null; | 180 if (comp != 0) return null; |
178 _SplayTreeNode result = _root; | 181 Node result = _root; |
179 _count--; | 182 _count--; |
180 // assert(_count >= 0); | 183 // assert(_count >= 0); |
181 if (_root.left == null) { | 184 if (_root.left == null) { |
182 _root = _root.right; | 185 _root = _root.right; |
183 } else { | 186 } else { |
184 _SplayTreeNode<K> right = _root.right; | 187 Node right = _root.right; |
185 // Splay to make sure that the new root has an empty right child. | 188 // Splay to make sure that the new root has an empty right child. |
186 _root = _splayMax(_root.left); | 189 _root = _splayMax(_root.left); |
187 // Insert the original right child as the right child of the new | 190 // Insert the original right child as the right child of the new |
188 // root. | 191 // root. |
189 _root.right = right; | 192 _root.right = right; |
190 } | 193 } |
191 _modificationCount++; | 194 _modificationCount++; |
192 return result; | 195 return result; |
193 } | 196 } |
194 | 197 |
195 /** | 198 /** |
196 * Adds a new root node with the given [key] or [value]. | 199 * Adds a new root node with the given [key] or [value]. |
197 * | 200 * |
198 * The [comp] value is the result of comparing the existing root's key | 201 * The [comp] value is the result of comparing the existing root's key |
199 * with key. | 202 * with key. |
200 */ | 203 */ |
201 void _addNewRoot(_SplayTreeNode<K> node, int comp) { | 204 void _addNewRoot(Node node, int comp) { |
202 _count++; | 205 _count++; |
203 _modificationCount++; | 206 _modificationCount++; |
204 if (_root == null) { | 207 if (_root == null) { |
205 _root = node; | 208 _root = node; |
206 return; | 209 return; |
207 } | 210 } |
208 // assert(_count >= 0); | 211 // assert(_count >= 0); |
209 if (comp < 0) { | 212 if (comp < 0) { |
210 node.left = _root; | 213 node.left = _root; |
211 node.right = _root.right; | 214 node.right = _root.right; |
212 _root.right = null; | 215 _root.right = null; |
213 } else { | 216 } else { |
214 node.right = _root; | 217 node.right = _root; |
215 node.left = _root.left; | 218 node.left = _root.left; |
216 _root.left = null; | 219 _root.left = null; |
217 } | 220 } |
218 _root = node; | 221 _root = node; |
219 } | 222 } |
220 | 223 |
221 _SplayTreeNode get _first { | 224 Node get _first { |
222 if (_root == null) return null; | 225 if (_root == null) return null; |
223 _root = _splayMin(_root); | 226 _root = _splayMin(_root); |
224 return _root; | 227 return _root; |
225 } | 228 } |
226 | 229 |
227 _SplayTreeNode get _last { | 230 Node get _last { |
228 if (_root == null) return null; | 231 if (_root == null) return null; |
229 _root = _splayMax(_root); | 232 _root = _splayMax(_root); |
230 return _root; | 233 return _root; |
231 } | 234 } |
232 | 235 |
233 void _clear() { | 236 void _clear() { |
234 _root = null; | 237 _root = null; |
235 _count = 0; | 238 _count = 0; |
236 _modificationCount++; | 239 _modificationCount++; |
237 } | 240 } |
238 } | 241 } |
239 | 242 |
| 243 class _TypeTest<T> { |
| 244 bool test(v) => v is T; |
| 245 } |
| 246 |
240 /** | 247 /** |
241 * A [Map] of objects that can be ordered relative to each other. | 248 * A [Map] of objects that can be ordered relative to each other. |
242 * | 249 * |
243 * The map is based on a self-balancing binary tree. It allows most operations | 250 * The map is based on a self-balancing binary tree. It allows most operations |
244 * in amortized logarithmic time. | 251 * in amortized logarithmic time. |
245 * | 252 * |
246 * Keys of the map are compared using the `compare` function passed in | 253 * Keys of the map are compared using the `compare` function passed in |
247 * the constructor, both for ordering and for equality. | 254 * the constructor, both for ordering and for equality. |
248 * If the map contains only the key `a`, then `map.containsKey(b)` | 255 * If the map contains only the key `a`, then `map.containsKey(b)` |
249 * will return `true` if and only if `compare(a, b) == 0`, | 256 * will return `true` if and only if `compare(a, b) == 0`, |
250 * and the value of `a == b` is not even checked. | 257 * and the value of `a == b` is not even checked. |
251 * If the compare function is omitted, the objects are assumed to be | 258 * If the compare function is omitted, the objects are assumed to be |
252 * [Comparable], and are compared using their [Comparable.compareTo] method. | 259 * [Comparable], and are compared using their [Comparable.compareTo] method. |
253 * Non-comparable objects (including `null`) will not work as keys | 260 * Non-comparable objects (including `null`) will not work as keys |
254 * in that case. | 261 * in that case. |
255 * | 262 * |
256 * To allow calling [operator[]], [remove] or [containsKey] with objects | 263 * To allow calling [operator[]], [remove] or [containsKey] with objects |
257 * that are not supported by the `compare` function, an extra `isValidKey` | 264 * that are not supported by the `compare` function, an extra `isValidKey` |
258 * predicate function can be supplied. This function is tested before | 265 * predicate function can be supplied. This function is tested before |
259 * using the `compare` function on an argument value that may not be a [K] | 266 * using the `compare` function on an argument value that may not be a [K] |
260 * value. If omitted, the `isValidKey` function defaults to testing if the | 267 * value. If omitted, the `isValidKey` function defaults to testing if the |
261 * value is a [K]. | 268 * value is a [K]. |
262 */ | 269 */ |
263 class SplayTreeMap<K, V> extends _SplayTree<K> implements Map<K, V> { | 270 class SplayTreeMap<K, V> extends _SplayTree<K, _SplayTreeMapNode<K, V>> |
| 271 implements Map<K, V> { |
| 272 _SplayTreeMapNode<K, V> _root; |
| 273 final _SplayTreeMapNode<K, V> _dummy = |
| 274 new _SplayTreeMapNode<K, V>(null, null); |
| 275 |
264 Comparator<K> _comparator; | 276 Comparator<K> _comparator; |
265 _Predicate<Object> _validKey; | 277 _Predicate _validKey; |
266 | 278 |
267 SplayTreeMap([int compare(K key1, K key2), | 279 SplayTreeMap([int compare(K key1, K key2), bool isValidKey(potentialKey)]) |
268 bool isValidKey(Object potentialKey)]) | 280 : _comparator = compare ?? Comparable.compare as Comparator<K>, |
269 : _comparator = (compare == null) ? Comparable.compare : compare, | 281 _validKey = isValidKey ?? ((v) => v is K); |
270 _validKey = (isValidKey != null) ? isValidKey : ((v) => v is K); | |
271 | 282 |
272 /** | 283 /** |
273 * Creates a [SplayTreeMap] that contains all key/value pairs of [other]. | 284 * Creates a [SplayTreeMap] that contains all key/value pairs of [other]. |
274 */ | 285 */ |
275 factory SplayTreeMap.from(Map other, | 286 factory SplayTreeMap.from(Map other, |
276 [int compare(K key1, K key2), | 287 [int compare(K key1, K key2), |
277 bool isValidKey(Object potentialKey)]) { | 288 bool isValidKey(potentialKey)]) { |
278 SplayTreeMap<K, V> result = new SplayTreeMap<K, V>(); | 289 SplayTreeMap<K, V> result = new SplayTreeMap<K, V>(compare, isValidKey); |
279 other.forEach((k, v) { result[k] = v; }); | 290 other.forEach((k, v) { result[k as K] = v as V; }); |
280 return result; | 291 return result; |
281 } | 292 } |
282 | 293 |
283 /** | 294 /** |
284 * Creates a [SplayTreeMap] where the keys and values are computed from the | 295 * Creates a [SplayTreeMap] where the keys and values are computed from the |
285 * [iterable]. | 296 * [iterable]. |
286 * | 297 * |
287 * For each element of the [iterable] this constructor computes a key/value | 298 * For each element of the [iterable] this constructor computes a key/value |
288 * pair, by applying [key] and [value] respectively. | 299 * pair, by applying [key] and [value] respectively. |
289 * | 300 * |
290 * The keys of the key/value pairs do not need to be unique. The last | 301 * The keys of the key/value pairs do not need to be unique. The last |
291 * occurrence of a key will simply overwrite any previous value. | 302 * occurrence of a key will simply overwrite any previous value. |
292 * | 303 * |
293 * If no functions are specified for [key] and [value] the default is to | 304 * If no functions are specified for [key] and [value] the default is to |
294 * use the iterable value itself. | 305 * use the iterable value itself. |
295 */ | 306 */ |
296 factory SplayTreeMap.fromIterable(Iterable iterable, | 307 factory SplayTreeMap.fromIterable(Iterable iterable, |
297 {K key(element), | 308 {K key(element), |
298 V value(element), | 309 V value(element), |
299 int compare(K key1, K key2), | 310 int compare(K key1, K key2), |
300 bool isValidKey(Object potentialKey) }) { | 311 bool isValidKey(potentialKey) }) { |
301 SplayTreeMap<K, V> map = new SplayTreeMap<K, V>(compare, isValidKey); | 312 SplayTreeMap<K, V> map = new SplayTreeMap<K, V>(compare, isValidKey); |
302 Maps._fillMapWithMappedIterable(map, iterable, key, value); | 313 Maps._fillMapWithMappedIterable(map, iterable, key, value); |
303 return map; | 314 return map; |
304 } | 315 } |
305 | 316 |
306 /** | 317 /** |
307 * Creates a [SplayTreeMap] associating the given [keys] to [values]. | 318 * Creates a [SplayTreeMap] associating the given [keys] to [values]. |
308 * | 319 * |
309 * This constructor iterates over [keys] and [values] and maps each element of | 320 * This constructor iterates over [keys] and [values] and maps each element of |
310 * [keys] to the corresponding element of [values]. | 321 * [keys] to the corresponding element of [values]. |
311 * | 322 * |
312 * If [keys] contains the same object multiple times, the last occurrence | 323 * If [keys] contains the same object multiple times, the last occurrence |
313 * overwrites the previous value. | 324 * overwrites the previous value. |
314 * | 325 * |
315 * It is an error if the two [Iterable]s don't have the same length. | 326 * It is an error if the two [Iterable]s don't have the same length. |
316 */ | 327 */ |
317 factory SplayTreeMap.fromIterables(Iterable<K> keys, Iterable<V> values, | 328 factory SplayTreeMap.fromIterables(Iterable<K> keys, Iterable<V> values, |
318 [int compare(K key1, K key2), bool isValidKey(Object potentialKey)]) { | 329 [int compare(K key1, K key2), bool isValidKey(potentialKey)]) { |
319 SplayTreeMap<K, V> map = new SplayTreeMap<K, V>(compare, isValidKey); | 330 SplayTreeMap<K, V> map = new SplayTreeMap<K, V>(compare, isValidKey); |
320 Maps._fillMapWithIterables(map, keys, values); | 331 Maps._fillMapWithIterables(map, keys, values); |
321 return map; | 332 return map; |
322 } | 333 } |
323 | 334 |
324 int _compare(K key1, K key2) => _comparator(key1, key2); | 335 int _compare(K key1, K key2) => _comparator(key1, key2); |
325 | 336 |
326 SplayTreeMap._internal(); | 337 SplayTreeMap._internal(); |
327 | 338 |
328 V operator [](Object key) { | 339 V operator [](Object key) { |
329 if (key == null) throw new ArgumentError(key); | |
330 if (!_validKey(key)) return null; | 340 if (!_validKey(key)) return null; |
331 if (_root != null) { | 341 if (_root != null) { |
332 int comp = _splay(key); | 342 int comp = _splay(key as K); |
333 if (comp == 0) { | 343 if (comp == 0) { |
334 _SplayTreeMapNode mapRoot = _root; | 344 return _root.value; |
335 return mapRoot.value; | |
336 } | 345 } |
337 } | 346 } |
338 return null; | 347 return null; |
339 } | 348 } |
340 | 349 |
341 V remove(Object key) { | 350 V remove(Object key) { |
342 if (!_validKey(key)) return null; | 351 if (!_validKey(key)) return null; |
343 _SplayTreeMapNode mapRoot = _remove(key); | 352 _SplayTreeMapNode<K, V> mapRoot = _remove(key as K); |
344 if (mapRoot != null) return mapRoot.value; | 353 if (mapRoot != null) return mapRoot.value; |
345 return null; | 354 return null; |
346 } | 355 } |
347 | 356 |
348 void operator []=(K key, V value) { | 357 void operator []=(K key, V value) { |
349 if (key == null) throw new ArgumentError(key); | 358 if (key == null) throw new ArgumentError(key); |
350 // Splay on the key to move the last node on the search path for | 359 // Splay on the key to move the last node on the search path for |
351 // the key to the root of the tree. | 360 // the key to the root of the tree. |
352 int comp = _splay(key); | 361 int comp = _splay(key); |
353 if (comp == 0) { | 362 if (comp == 0) { |
354 _SplayTreeMapNode mapRoot = _root; | 363 _root.value = value; |
355 mapRoot.value = value; | |
356 return; | 364 return; |
357 } | 365 } |
358 _addNewRoot(new _SplayTreeMapNode(key, value), comp); | 366 _addNewRoot(new _SplayTreeMapNode(key, value), comp); |
359 } | 367 } |
360 | 368 |
361 | 369 |
362 V putIfAbsent(K key, V ifAbsent()) { | 370 V putIfAbsent(K key, V ifAbsent()) { |
363 if (key == null) throw new ArgumentError(key); | 371 if (key == null) throw new ArgumentError(key); |
364 int comp = _splay(key); | 372 int comp = _splay(key); |
365 if (comp == 0) { | 373 if (comp == 0) { |
366 _SplayTreeMapNode mapRoot = _root; | 374 return _root.value; |
367 return mapRoot.value; | |
368 } | 375 } |
369 int modificationCount = _modificationCount; | 376 int modificationCount = _modificationCount; |
370 int splayCount = _splayCount; | 377 int splayCount = _splayCount; |
371 V value = ifAbsent(); | 378 V value = ifAbsent(); |
372 if (modificationCount != _modificationCount) { | 379 if (modificationCount != _modificationCount) { |
373 throw new ConcurrentModificationError(this); | 380 throw new ConcurrentModificationError(this); |
374 } | 381 } |
375 if (splayCount != _splayCount) { | 382 if (splayCount != _splayCount) { |
376 comp = _splay(key); | 383 comp = _splay(key); |
377 // Key is still not there, otherwise _modificationCount would be changed. | 384 // Key is still not there, otherwise _modificationCount would be changed. |
(...skipping 24 matching lines...) Expand all Loading... |
402 | 409 |
403 int get length { | 410 int get length { |
404 return _count; | 411 return _count; |
405 } | 412 } |
406 | 413 |
407 void clear() { | 414 void clear() { |
408 _clear(); | 415 _clear(); |
409 } | 416 } |
410 | 417 |
411 bool containsKey(Object key) { | 418 bool containsKey(Object key) { |
412 return _validKey(key) && _splay(key) == 0; | 419 return _validKey(key) && _splay(key as K) == 0; |
413 } | 420 } |
414 | 421 |
415 bool containsValue(Object value) { | 422 bool containsValue(Object value) { |
416 bool found = false; | 423 bool found = false; |
417 int initialSplayCount = _splayCount; | 424 int initialSplayCount = _splayCount; |
418 bool visit(_SplayTreeMapNode node) { | 425 bool visit(_SplayTreeMapNode node) { |
419 while (node != null) { | 426 while (node != null) { |
420 if (node.value == value) return true; | 427 if (node.value == value) return true; |
421 if (initialSplayCount != _splayCount) { | 428 if (initialSplayCount != _splayCount) { |
422 throw new ConcurrentModificationError(this); | 429 throw new ConcurrentModificationError(this); |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
481 if (comp > 0) return _root.key; | 488 if (comp > 0) return _root.key; |
482 _SplayTreeNode<K> node = _root.right; | 489 _SplayTreeNode<K> node = _root.right; |
483 if (node == null) return null; | 490 if (node == null) return null; |
484 while (node.left != null) { | 491 while (node.left != null) { |
485 node = node.left; | 492 node = node.left; |
486 } | 493 } |
487 return node.key; | 494 return node.key; |
488 } | 495 } |
489 } | 496 } |
490 | 497 |
491 abstract class _SplayTreeIterator<T> implements Iterator<T> { | 498 abstract class _SplayTreeIterator<K, T> implements Iterator<T> { |
492 final _SplayTree _tree; | 499 final _SplayTree<K, _SplayTreeNode<K>> _tree; |
493 /** | 500 /** |
494 * Worklist of nodes to visit. | 501 * Worklist of nodes to visit. |
495 * | 502 * |
496 * These nodes have been passed over on the way down in a | 503 * These nodes have been passed over on the way down in a |
497 * depth-first left-to-right traversal. Visiting each node, | 504 * depth-first left-to-right traversal. Visiting each node, |
498 * and their right subtrees will visit the remainder of | 505 * and their right subtrees will visit the remainder of |
499 * the nodes of a full traversal. | 506 * the nodes of a full traversal. |
500 * | 507 * |
501 * Only valid as long as the original tree isn't reordered. | 508 * Only valid as long as the original tree isn't reordered. |
502 */ | 509 */ |
503 final List<_SplayTreeNode> _workList = <_SplayTreeNode>[]; | 510 final List<_SplayTreeNode<K>> _workList = <_SplayTreeNode<K>>[]; |
504 | 511 |
505 /** | 512 /** |
506 * Original modification counter of [_tree]. | 513 * Original modification counter of [_tree]. |
507 * | 514 * |
508 * Incremented on [_tree] when a key is added or removed. | 515 * Incremented on [_tree] when a key is added or removed. |
509 * If it changes, iteration is aborted. | 516 * If it changes, iteration is aborted. |
510 * | 517 * |
511 * Not final because some iterators may modify the tree knowingly, | 518 * Not final because some iterators may modify the tree knowingly, |
512 * and they update the modification count in that case. | 519 * and they update the modification count in that case. |
513 */ | 520 */ |
514 int _modificationCount; | 521 int _modificationCount; |
515 | 522 |
516 /** | 523 /** |
517 * Count of splay operations on [_tree] when [_workList] was built. | 524 * Count of splay operations on [_tree] when [_workList] was built. |
518 * | 525 * |
519 * If the splay count on [_tree] increases, [_workList] becomes invalid. | 526 * If the splay count on [_tree] increases, [_workList] becomes invalid. |
520 */ | 527 */ |
521 int _splayCount; | 528 int _splayCount; |
522 | 529 |
523 /** Current node. */ | 530 /** Current node. */ |
524 _SplayTreeNode _currentNode; | 531 _SplayTreeNode<K> _currentNode; |
525 | 532 |
526 _SplayTreeIterator(_SplayTree tree) | 533 _SplayTreeIterator(_SplayTree<K, _SplayTreeNode<K>> tree) |
527 : _tree = tree, | 534 : _tree = tree, |
528 _modificationCount = tree._modificationCount, | 535 _modificationCount = tree._modificationCount, |
529 _splayCount = tree._splayCount { | 536 _splayCount = tree._splayCount { |
530 _findLeftMostDescendent(tree._root); | 537 _findLeftMostDescendent(tree._root); |
531 } | 538 } |
532 | 539 |
533 _SplayTreeIterator.startAt(_SplayTree tree, var startKey) | 540 _SplayTreeIterator.startAt(_SplayTree<K, _SplayTreeNode<K>> tree, K startKey) |
534 : _tree = tree, | 541 : _tree = tree, |
535 _modificationCount = tree._modificationCount { | 542 _modificationCount = tree._modificationCount { |
536 if (tree._root == null) return; | 543 if (tree._root == null) return; |
537 int compare = tree._splay(startKey); | 544 int compare = tree._splay(startKey); |
538 _splayCount = tree._splayCount; | 545 _splayCount = tree._splayCount; |
539 if (compare < 0) { | 546 if (compare < 0) { |
540 // Don't include the root, start at the next element after the root. | 547 // Don't include the root, start at the next element after the root. |
541 _findLeftMostDescendent(tree._root.right); | 548 _findLeftMostDescendent(tree._root.right); |
542 } else { | 549 } else { |
543 _workList.add(tree._root); | 550 _workList.add(tree._root); |
544 } | 551 } |
545 } | 552 } |
546 | 553 |
547 T get current { | 554 T get current { |
548 if (_currentNode == null) return null; | 555 if (_currentNode == null) return null; |
549 return _getValue(_currentNode); | 556 return _getValue(_currentNode); |
550 } | 557 } |
551 | 558 |
552 void _findLeftMostDescendent(_SplayTreeNode node) { | 559 void _findLeftMostDescendent(_SplayTreeNode<K> node) { |
553 while (node != null) { | 560 while (node != null) { |
554 _workList.add(node); | 561 _workList.add(node); |
555 node = node.left; | 562 node = node.left; |
556 } | 563 } |
557 } | 564 } |
558 | 565 |
559 /** | 566 /** |
560 * Called when the tree structure of the tree has changed. | 567 * Called when the tree structure of the tree has changed. |
561 * | 568 * |
562 * This can be caused by a splay operation. | 569 * This can be caused by a splay operation. |
563 * If the key-set changes, iteration is aborted before getting | 570 * If the key-set changes, iteration is aborted before getting |
564 * here, so we know that the keys are the same as before, it's | 571 * here, so we know that the keys are the same as before, it's |
565 * only the tree that has been reordered. | 572 * only the tree that has been reordered. |
566 */ | 573 */ |
567 void _rebuildWorkList(_SplayTreeNode currentNode) { | 574 void _rebuildWorkList(_SplayTreeNode<K> currentNode) { |
568 assert(!_workList.isEmpty); | 575 assert(!_workList.isEmpty); |
569 _workList.clear(); | 576 _workList.clear(); |
570 if (currentNode == null) { | 577 if (currentNode == null) { |
571 _findLeftMostDescendent(_tree._root); | 578 _findLeftMostDescendent(_tree._root); |
572 } else { | 579 } else { |
573 _tree._splay(currentNode.key); | 580 _tree._splay(currentNode.key); |
574 _findLeftMostDescendent(_tree._root.right); | 581 _findLeftMostDescendent(_tree._root.right); |
575 assert(!_workList.isEmpty); | 582 assert(!_workList.isEmpty); |
576 } | 583 } |
577 } | 584 } |
(...skipping 12 matching lines...) Expand all Loading... |
590 return false; | 597 return false; |
591 } | 598 } |
592 if (_tree._splayCount != _splayCount && _currentNode != null) { | 599 if (_tree._splayCount != _splayCount && _currentNode != null) { |
593 _rebuildWorkList(_currentNode); | 600 _rebuildWorkList(_currentNode); |
594 } | 601 } |
595 _currentNode = _workList.removeLast(); | 602 _currentNode = _workList.removeLast(); |
596 _findLeftMostDescendent(_currentNode.right); | 603 _findLeftMostDescendent(_currentNode.right); |
597 return true; | 604 return true; |
598 } | 605 } |
599 | 606 |
600 T _getValue(_SplayTreeMapNode node); | 607 T _getValue(_SplayTreeNode<K> node); |
601 } | 608 } |
602 | 609 |
603 class _SplayTreeKeyIterable<K> extends IterableBase<K> | 610 class _SplayTreeKeyIterable<K> extends Iterable<K> |
604 implements EfficientLength { | 611 implements EfficientLength { |
605 _SplayTree<K> _tree; | 612 _SplayTree<K, _SplayTreeNode<K>> _tree; |
606 _SplayTreeKeyIterable(this._tree); | 613 _SplayTreeKeyIterable(this._tree); |
607 int get length => _tree._count; | 614 int get length => _tree._count; |
608 bool get isEmpty => _tree._count == 0; | 615 bool get isEmpty => _tree._count == 0; |
609 Iterator<K> get iterator => new _SplayTreeKeyIterator<K>(_tree); | 616 Iterator<K> get iterator => new _SplayTreeKeyIterator<K>(_tree); |
610 | 617 |
611 Set<K> toSet() { | 618 Set<K> toSet() { |
612 var setOrMap = _tree; // Both have _comparator and _validKey. | |
613 SplayTreeSet<K> set = | 619 SplayTreeSet<K> set = |
614 new SplayTreeSet<K>(setOrMap._comparator, setOrMap._validKey); | 620 new SplayTreeSet<K>(_tree._comparator, _tree._validKey); |
615 set._count = _tree._count; | 621 set._count = _tree._count; |
616 set._root = set._copyNode(_tree._root); | 622 set._root = set._copyNode(_tree._root); |
617 return set; | 623 return set; |
618 } | 624 } |
619 } | 625 } |
620 | 626 |
621 class _SplayTreeValueIterable<K, V> extends IterableBase<V> | 627 class _SplayTreeValueIterable<K, V> extends Iterable<V> |
622 implements EfficientLength { | 628 implements EfficientLength { |
623 SplayTreeMap<K, V> _map; | 629 SplayTreeMap<K, V> _map; |
624 _SplayTreeValueIterable(this._map); | 630 _SplayTreeValueIterable(this._map); |
625 int get length => _map._count; | 631 int get length => _map._count; |
626 bool get isEmpty => _map._count == 0; | 632 bool get isEmpty => _map._count == 0; |
627 Iterator<V> get iterator => new _SplayTreeValueIterator<K, V>(_map); | 633 Iterator<V> get iterator => new _SplayTreeValueIterator<K, V>(_map); |
628 } | 634 } |
629 | 635 |
630 class _SplayTreeKeyIterator<K> extends _SplayTreeIterator<K> { | 636 class _SplayTreeKeyIterator<K> extends _SplayTreeIterator<K, K> { |
631 _SplayTreeKeyIterator(_SplayTree<K> map): super(map); | 637 _SplayTreeKeyIterator(_SplayTree<K, _SplayTreeNode<K>> map): super(map); |
632 K _getValue(_SplayTreeNode node) => node.key; | 638 K _getValue(_SplayTreeNode<K> node) => node.key; |
633 } | 639 } |
634 | 640 |
635 class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<V> { | 641 class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<K, V> { |
636 _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map); | 642 _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map); |
637 V _getValue(_SplayTreeMapNode node) => node.value; | 643 V _getValue(_SplayTreeNode<K> node) { |
| 644 _SplayTreeMapNode<K, V> mapNode = node as _SplayTreeMapNode<K, V>; |
| 645 return mapNode.value; |
| 646 } |
638 } | 647 } |
639 | 648 |
640 class _SplayTreeNodeIterator<K> | 649 class _SplayTreeNodeIterator<K> |
641 extends _SplayTreeIterator<_SplayTreeNode<K>> { | 650 extends _SplayTreeIterator<K, _SplayTreeNode<K>> { |
642 _SplayTreeNodeIterator(_SplayTree<K> tree): super(tree); | 651 _SplayTreeNodeIterator(_SplayTree<K, _SplayTreeNode<K>> tree): super(tree); |
643 _SplayTreeNodeIterator.startAt(_SplayTree<K> tree, var startKey) | 652 _SplayTreeNodeIterator.startAt( |
| 653 _SplayTree<K, _SplayTreeNode<K>> tree, K startKey) |
644 : super.startAt(tree, startKey); | 654 : super.startAt(tree, startKey); |
645 _SplayTreeNode<K> _getValue(_SplayTreeNode node) => node; | 655 _SplayTreeNode<K> _getValue(_SplayTreeNode<K> node) => node; |
646 } | 656 } |
647 | 657 |
648 | 658 |
649 /** | 659 /** |
650 * A [Set] of objects that can be ordered relative to each other. | 660 * A [Set] of objects that can be ordered relative to each other. |
651 * | 661 * |
652 * The set is based on a self-balancing binary tree. It allows most operations | 662 * The set is based on a self-balancing binary tree. It allows most operations |
653 * in amortized logarithmic time. | 663 * in amortized logarithmic time. |
654 * | 664 * |
655 * Elements of the set are compared using the `compare` function passed in | 665 * Elements of the set are compared using the `compare` function passed in |
656 * the constructor, both for ordering and for equality. | 666 * the constructor, both for ordering and for equality. |
657 * If the set contains only an object `a`, then `set.contains(b)` | 667 * If the set contains only an object `a`, then `set.contains(b)` |
658 * will return `true` if and only if `compare(a, b) == 0`, | 668 * will return `true` if and only if `compare(a, b) == 0`, |
659 * and the value of `a == b` is not even checked. | 669 * and the value of `a == b` is not even checked. |
660 * If the compare function is omitted, the objects are assumed to be | 670 * If the compare function is omitted, the objects are assumed to be |
661 * [Comparable], and are compared using their [Comparable.compareTo] method. | 671 * [Comparable], and are compared using their [Comparable.compareTo] method. |
662 * Non-comparable objects (including `null`) will not work as an element | 672 * Non-comparable objects (including `null`) will not work as an element |
663 * in that case. | 673 * in that case. |
664 */ | 674 */ |
665 class SplayTreeSet<E> extends _SplayTree<E> with IterableMixin<E>, SetMixin<E> { | 675 class SplayTreeSet<E> extends _SplayTree<E, _SplayTreeNode<E>> |
| 676 with IterableMixin<E>, SetMixin<E> { |
| 677 _SplayTreeNode<E> _root; |
| 678 final _SplayTreeNode<E> _dummy = new _SplayTreeNode<E>(null); |
| 679 |
666 Comparator<E> _comparator; | 680 Comparator<E> _comparator; |
667 _Predicate<Object> _validKey; | 681 _Predicate _validKey; |
668 | 682 |
669 /** | 683 /** |
670 * Create a new [SplayTreeSet] with the given compare function. | 684 * Create a new [SplayTreeSet] with the given compare function. |
671 * | 685 * |
672 * If the [compare] function is omitted, it defaults to [Comparable.compare], | 686 * If the [compare] function is omitted, it defaults to [Comparable.compare], |
673 * and the elements must be comparable. | 687 * and the elements must be comparable. |
674 * | 688 * |
675 * A provided `compare` function may not work on all objects. It may not even | 689 * A provided `compare` function may not work on all objects. It may not even |
676 * work on all `E` instances. | 690 * work on all `E` instances. |
677 * | 691 * |
678 * For operations that add elements to the set, the user is supposed to not | 692 * For operations that add elements to the set, the user is supposed to not |
679 * pass in objects that doesn't work with the compare function. | 693 * pass in objects that doesn't work with the compare function. |
680 * | 694 * |
681 * The methods [contains], [remove], [lookup], [removeAll] or [retainAll] | 695 * The methods [contains], [remove], [lookup], [removeAll] or [retainAll] |
682 * are typed to accept any object(s), and the [isValidKey] test can used to | 696 * are typed to accept any object(s), and the [isValidKey] test can used to |
683 * filter those objects before handing them to the `compare` function. | 697 * filter those objects before handing them to the `compare` function. |
684 * | 698 * |
685 * If [isValidKey] is provided, only values satisfying `isValidKey(other)` | 699 * If [isValidKey] is provided, only values satisfying `isValidKey(other)` |
686 * are compared using the `compare` method in the methods mentioned above. | 700 * are compared using the `compare` method in the methods mentioned above. |
687 * If the `isValidKey` function returns false for an object, it is assumed to | 701 * If the `isValidKey` function returns false for an object, it is assumed to |
688 * not be in the set. | 702 * not be in the set. |
689 * | 703 * |
690 * If omitted, the `isValidKey` function defaults to checking against the | 704 * If omitted, the `isValidKey` function defaults to checking against the |
691 * type parameter: `other is E`. | 705 * type parameter: `other is E`. |
692 */ | 706 */ |
693 SplayTreeSet([int compare(E key1, E key2), | 707 SplayTreeSet([int compare(E key1, E key2), bool isValidKey(potentialKey)]) |
694 bool isValidKey(Object potentialKey)]) | 708 : _comparator = compare ?? Comparable.compare as Comparator<E>, |
695 : _comparator = (compare == null) ? Comparable.compare : compare, | 709 _validKey = isValidKey ?? ((v) => v is E); |
696 _validKey = (isValidKey != null) ? isValidKey : ((v) => v is E); | |
697 | 710 |
698 /** | 711 /** |
699 * Creates a [SplayTreeSet] that contains all [elements]. | 712 * Creates a [SplayTreeSet] that contains all [elements]. |
700 * | 713 * |
701 * The set works as if created by `new SplayTreeSet<E>(compare, isValidKey)`. | 714 * The set works as if created by `new SplayTreeSet<E>(compare, isValidKey)`. |
702 * | 715 * |
703 * All the [elements] should be valid as arguments to the [compare] function. | 716 * All the [elements] should be valid as arguments to the [compare] function. |
704 */ | 717 */ |
705 factory SplayTreeSet.from(Iterable elements, | 718 factory SplayTreeSet.from(Iterable elements, |
706 [int compare(E key1, E key2), | 719 [int compare(E key1, E key2), |
707 bool isValidKey(Object potentialKey)]) { | 720 bool isValidKey(potentialKey)]) { |
708 SplayTreeSet<E> result = new SplayTreeSet<E>(compare, isValidKey); | 721 SplayTreeSet<E> result = new SplayTreeSet<E>(compare, isValidKey); |
709 for (final E element in elements) { | 722 for (final element in elements) { |
710 result.add(element); | 723 result.add(element as E); |
711 } | 724 } |
712 return result; | 725 return result; |
713 } | 726 } |
714 | 727 |
715 int _compare(E e1, E e2) => _comparator(e1, e2); | 728 int _compare(E e1, E e2) => _comparator(e1, e2); |
716 | 729 |
717 // From Iterable. | 730 // From Iterable. |
718 | 731 |
719 Iterator<E> get iterator => new _SplayTreeKeyIterator<E>(this); | 732 Iterator<E> get iterator => new _SplayTreeKeyIterator<E>(this); |
720 | 733 |
(...skipping 12 matching lines...) Expand all Loading... |
733 } | 746 } |
734 | 747 |
735 E get single { | 748 E get single { |
736 if (_count == 0) throw IterableElementError.noElement(); | 749 if (_count == 0) throw IterableElementError.noElement(); |
737 if (_count > 1) throw IterableElementError.tooMany(); | 750 if (_count > 1) throw IterableElementError.tooMany(); |
738 return _root.key; | 751 return _root.key; |
739 } | 752 } |
740 | 753 |
741 // From Set. | 754 // From Set. |
742 bool contains(Object object) { | 755 bool contains(Object object) { |
743 return _validKey(object) && _splay(object) == 0; | 756 return _validKey(object) && _splay(object as E) == 0; |
744 } | 757 } |
745 | 758 |
746 bool add(E element) { | 759 bool add(E element) { |
747 int compare = _splay(element); | 760 int compare = _splay(element); |
748 if (compare == 0) return false; | 761 if (compare == 0) return false; |
749 _addNewRoot(new _SplayTreeNode(element), compare); | 762 _addNewRoot(new _SplayTreeNode(element), compare); |
750 return true; | 763 return true; |
751 } | 764 } |
752 | 765 |
753 bool remove(Object object) { | 766 bool remove(Object object) { |
754 if (!_validKey(object)) return false; | 767 if (!_validKey(object)) return false; |
755 return _remove(object) != null; | 768 return _remove(object as E) != null; |
756 } | 769 } |
757 | 770 |
758 void addAll(Iterable<E> elements) { | 771 void addAll(Iterable<E> elements) { |
759 for (E element in elements) { | 772 for (E element in elements) { |
760 int compare = _splay(element); | 773 int compare = _splay(element); |
761 if (compare != 0) { | 774 if (compare != 0) { |
762 _addNewRoot(new _SplayTreeNode(element), compare); | 775 _addNewRoot(new _SplayTreeNode(element), compare); |
763 } | 776 } |
764 } | 777 } |
765 } | 778 } |
766 | 779 |
767 void removeAll(Iterable<Object> elements) { | 780 void removeAll(Iterable<Object> elements) { |
768 for (Object element in elements) { | 781 for (Object element in elements) { |
769 if (_validKey(element)) _remove(element); | 782 if (_validKey(element)) _remove(element as E); |
770 } | 783 } |
771 } | 784 } |
772 | 785 |
773 void retainAll(Iterable<Object> elements) { | 786 void retainAll(Iterable<Object> elements) { |
774 // Build a set with the same sense of equality as this set. | 787 // Build a set with the same sense of equality as this set. |
775 SplayTreeSet<E> retainSet = new SplayTreeSet<E>(_comparator, _validKey); | 788 SplayTreeSet<E> retainSet = new SplayTreeSet<E>(_comparator, _validKey); |
776 int modificationCount = _modificationCount; | 789 int modificationCount = _modificationCount; |
777 for (Object object in elements) { | 790 for (Object object in elements) { |
778 if (modificationCount != _modificationCount) { | 791 if (modificationCount != _modificationCount) { |
779 // The iterator should not have side effects. | 792 // The iterator should not have side effects. |
780 throw new ConcurrentModificationError(this); | 793 throw new ConcurrentModificationError(this); |
781 } | 794 } |
782 // Equivalent to this.contains(object). | 795 // Equivalent to this.contains(object). |
783 if (_validKey(object) && _splay(object) == 0) retainSet.add(_root.key); | 796 if (_validKey(object) && _splay(object as E) == 0) { |
| 797 retainSet.add(_root.key); |
| 798 } |
784 } | 799 } |
785 // Take over the elements from the retained set, if it differs. | 800 // Take over the elements from the retained set, if it differs. |
786 if (retainSet._count != _count) { | 801 if (retainSet._count != _count) { |
787 _root = retainSet._root; | 802 _root = retainSet._root; |
788 _count = retainSet._count; | 803 _count = retainSet._count; |
789 _modificationCount++; | 804 _modificationCount++; |
790 } | 805 } |
791 } | 806 } |
792 | 807 |
793 E lookup(Object object) { | 808 E lookup(Object object) { |
794 if (!_validKey(object)) return null; | 809 if (!_validKey(object)) return null; |
795 int comp = _splay(object); | 810 int comp = _splay(object as E); |
796 if (comp != 0) return null; | 811 if (comp != 0) return null; |
797 return _root.key; | 812 return _root.key; |
798 } | 813 } |
799 | 814 |
800 Set<E> intersection(Set<Object> other) { | 815 Set<E> intersection(Set<Object> other) { |
801 Set<E> result = new SplayTreeSet<E>(_comparator, _validKey); | 816 Set<E> result = new SplayTreeSet<E>(_comparator, _validKey); |
802 for (E element in this) { | 817 for (E element in this) { |
803 if (other.contains(element)) result.add(element); | 818 if (other.contains(element)) result.add(element); |
804 } | 819 } |
805 return result; | 820 return result; |
(...skipping 25 matching lines...) Expand all Loading... |
831 return new _SplayTreeNode<E>(node.key)..left = _copyNode(node.left) | 846 return new _SplayTreeNode<E>(node.key)..left = _copyNode(node.left) |
832 ..right = _copyNode(node.right); | 847 ..right = _copyNode(node.right); |
833 } | 848 } |
834 | 849 |
835 void clear() { _clear(); } | 850 void clear() { _clear(); } |
836 | 851 |
837 Set<E> toSet() => _clone(); | 852 Set<E> toSet() => _clone(); |
838 | 853 |
839 String toString() => IterableBase.iterableToFullString(this, '{', '}'); | 854 String toString() => IterableBase.iterableToFullString(this, '{', '}'); |
840 } | 855 } |
OLD | NEW |