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 /** | 7 /** |
8 * A node in a splay tree. It holds the sorting key and the left | 8 * A node in a splay tree. It holds the sorting key and the left |
9 * and right children in the tree. | 9 * and right children in the tree. |
10 */ | 10 */ |
(...skipping 18 matching lines...) Expand all Loading... | |
29 /** | 29 /** |
30 * A splay tree is a self-balancing binary search tree. | 30 * A splay tree is a self-balancing binary search tree. |
31 * | 31 * |
32 * It has the additional property that recently accessed elements | 32 * It has the additional property that recently accessed elements |
33 * are quick to access again. | 33 * are quick to access again. |
34 * It performs basic operations such as insertion, look-up and | 34 * It performs basic operations such as insertion, look-up and |
35 * removal, in O(log(n)) amortized time. | 35 * removal, in O(log(n)) amortized time. |
36 */ | 36 */ |
37 abstract class _SplayTree<K> { | 37 abstract class _SplayTree<K> { |
38 // The root node of the splay tree. It will contain either the last | 38 // The root node of the splay tree. It will contain either the last |
39 // element inserted, or the last element looked up. | 39 // element inserted or the last element looked up. |
40 _SplayTreeNode<K> _root; | 40 _SplayTreeNode<K> _root; |
41 | 41 |
42 // The dummy node used when performing a splay on the tree. It is a | 42 // The dummy node used when performing a splay on the tree. Reusing it |
43 // local field of the class to avoid allocating a node each time a | 43 // avoids allocating a node each time a splay is performed. |
44 // splay is performed. | |
45 // TODO(lrn); Should it be a getter backed by a static instead? | |
46 _SplayTreeNode<K> _dummy = new _SplayTreeNode<K>(null); | 44 _SplayTreeNode<K> _dummy = new _SplayTreeNode<K>(null); |
47 | 45 |
48 // Number of elements in the splay tree. | 46 // Number of elements in the splay tree. |
49 int _count = 0; | 47 int _count = 0; |
50 | 48 |
51 /** | 49 /** |
52 * Counter incremented whenever the keys in the map changes. | 50 * Counter incremented whenever the keys in the map changes. |
53 * | 51 * |
54 * Used to detect concurrent modifications. | 52 * Used to detect concurrent modifications. |
55 */ | 53 */ |
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
129 current.left = _dummy.right; | 127 current.left = _dummy.right; |
130 current.right = _dummy.left; | 128 current.right = _dummy.left; |
131 _root = current; | 129 _root = current; |
132 | 130 |
133 _dummy.right = null; | 131 _dummy.right = null; |
134 _dummy.left = null; | 132 _dummy.left = null; |
135 _splayCount++; | 133 _splayCount++; |
136 return comp; | 134 return comp; |
137 } | 135 } |
138 | 136 |
137 // Emulates splaying with a key that is smaller than any in the tree. | |
138 // After this, the least element in the tree is the root. | |
floitsch
2013/03/11 13:34:28
smallest
Lasse Reichstein Nielsen
2013/03/12 12:01:06
Done.
| |
139 void _splayMin() { | |
140 if (_root == null) return; | |
141 _SplayTreeNode current = _root; | |
142 while (current.left != null) { | |
143 _SplayTreeNode left = current.left; | |
144 current.left = left.right; | |
145 left.right = current; | |
146 current = left; | |
147 } | |
148 _root = current; | |
149 } | |
150 | |
151 // Emulates splaying with a key that is greater than any in the tree. | |
152 // After this, the largest element in the tree is the root. | |
153 void _splayMax() { | |
154 if (_root == null) return; | |
155 _SplayTreeNode current = _root; | |
156 while (current.right != null) { | |
157 _SplayTreeNode right = current.right; | |
158 current.right = right.left; | |
159 right.left = current; | |
160 current = right; | |
161 } | |
162 _root = current; | |
163 } | |
164 | |
139 _SplayTreeNode _remove(K key) { | 165 _SplayTreeNode _remove(K key) { |
140 if (_root == null) return null; | 166 if (_root == null) return null; |
141 int comp = _splay(key); | 167 int comp = _splay(key); |
142 if (comp != 0) return null; | 168 if (comp != 0) return null; |
143 _SplayTreeNode result = _root; | 169 _SplayTreeNode result = _root; |
144 _count--; | 170 _count--; |
145 // assert(_count >= 0); | 171 // assert(_count >= 0); |
146 if (_root.left == null) { | 172 if (_root.left == null) { |
147 _root = _root.right; | 173 _root = _root.right; |
148 } else { | 174 } else { |
(...skipping 30 matching lines...) Expand all Loading... | |
179 } else { | 205 } else { |
180 node.right = _root; | 206 node.right = _root; |
181 node.left = _root.left; | 207 node.left = _root.left; |
182 _root.left = null; | 208 _root.left = null; |
183 } | 209 } |
184 _root = node; | 210 _root = node; |
185 } | 211 } |
186 | 212 |
187 _SplayTreeNode get _first { | 213 _SplayTreeNode get _first { |
188 if (_root == null) return null; | 214 if (_root == null) return null; |
189 _SplayTreeNode<K> node = _root; | 215 _splayMin(); |
190 while (node.left != null) { | 216 return _root; |
191 node = node.left; | |
192 } | |
193 // Maybe implement a splay-method that can splay the minimum without | |
194 // performing comparisons. | |
195 _splay(node.key); | |
196 return node; | |
197 } | 217 } |
198 | 218 |
199 _SplayTreeNode get _last { | 219 _SplayTreeNode get _last { |
200 if (_root == null) return null; | 220 if (_root == null) return null; |
201 _SplayTreeNode<K> node = _root; | 221 _splayMax(); |
202 while (node.right != null) { | 222 return _root; |
203 node = node.right; | |
204 } | |
205 // Maybe implement a splay-method that can splay the minimum without | |
206 // performing comparisons. | |
207 _splay(node.key); | |
208 return node; | |
209 } | 223 } |
210 | 224 |
211 void _clear() { | 225 void _clear() { |
212 _root = null; | 226 _root = null; |
213 _count = 0; | 227 _count = 0; |
214 _modificationCount++; | 228 _modificationCount++; |
215 } | 229 } |
216 } | 230 } |
217 | 231 |
218 /* | 232 /* |
219 * A [Map] of objects that can be ordered relative to each other. | 233 * A [Map] of objects that can be ordered relative to each other. |
220 * | 234 * |
221 * The map is based on a self-balancing binary tree. It allows most operations | 235 * The map is based on a self-balancing binary tree. It allows most operations |
222 * in amortized logarithmic time. | 236 * in amortized logarithmic time. |
223 * | 237 * |
224 * Keys of the map are compared using the `compare` function passed in | 238 * Keys of the map are compared using the `compare` function passed in |
225 * the constructor. If that is omitted, the objects are assumed to be | 239 * the constructor. If that is omitted, the objects are assumed to be |
226 * [Comparable], and are compared using their [Comparable.compareTo] | 240 * [Comparable], and are compared using their [Comparable.compareTo] |
227 * method. | 241 * method. This also means that `null` is *not* allowed as a key. |
228 */ | 242 */ |
229 class SplayTreeMap<K, V> extends _SplayTree<K> implements Map<K, V> { | 243 class SplayTreeMap<K, V> extends _SplayTree<K> implements Map<K, V> { |
230 // TODO(ngeoffray): Restore type when feature is implemented in dart2js | 244 // TODO(ngeoffray): Restore type when feature is implemented in dart2js |
231 // checked mode. http://dartbug.com/7733 | 245 // checked mode. http://dartbug.com/7733 |
232 Function /* Comparator<K> */_comparator; | 246 Function /* Comparator<K> */_comparator; |
233 | 247 |
234 SplayTreeMap([int compare(K key1, K key2)]) | 248 SplayTreeMap([int compare(K key1, K key2)]) |
235 : _comparator = (compare == null) ? Comparable.compare : compare; | 249 : _comparator = (compare == null) ? Comparable.compare : compare; |
236 | 250 |
237 int _compare(K key1, K key2) => _comparator(key1, key2); | 251 int _compare(K key1, K key2) => _comparator(key1, key2); |
238 | 252 |
239 SplayTreeMap._internal(); | 253 SplayTreeMap._internal(); |
240 | 254 |
241 V operator [](K key) { | 255 V operator [](K key) { |
256 if (key == null) throw new ArgumentError(key); | |
242 if (_root != null) { | 257 if (_root != null) { |
243 int comp = _splay(key); | 258 int comp = _splay(key); |
244 if (comp == 0) return _root.value; | 259 if (comp == 0) return _root.value; |
245 } | 260 } |
246 return null; | 261 return null; |
247 } | 262 } |
248 | 263 |
249 V remove(K key) { | 264 V remove(Object key) { |
265 if (key is! K) return null; | |
250 _SplayTreeMapNode root = _remove(key); | 266 _SplayTreeMapNode root = _remove(key); |
251 if (root != null) return root.value; | 267 if (root != null) return root.value; |
252 return null; | 268 return null; |
253 } | 269 } |
254 | 270 |
255 void operator []=(K key, V value) { | 271 void operator []=(K key, V value) { |
272 if (key == null) throw new ArgumentError(key); | |
256 // Splay on the key to move the last node on the search path for | 273 // Splay on the key to move the last node on the search path for |
257 // the key to the root of the tree. | 274 // the key to the root of the tree. |
258 int comp = _splay(key); | 275 int comp = _splay(key); |
259 if (comp == 0) { | 276 if (comp == 0) { |
260 _root.value = value; | 277 _root.value = value; |
261 return; | 278 return; |
262 } | 279 } |
263 _addNewRoot(new _SplayTreeMapNode(key, value), comp); | 280 _addNewRoot(new _SplayTreeMapNode(key, value), comp); |
264 } | 281 } |
265 | 282 |
266 | 283 |
267 V putIfAbsent(K key, V ifAbsent()) { | 284 V putIfAbsent(K key, V ifAbsent()) { |
285 if (key == null) throw new ArgumentError(key); | |
268 int comp = _splay(key); | 286 int comp = _splay(key); |
269 if (comp == 0) return _root.value; | 287 if (comp == 0) return _root.value; |
270 int modificationCount = _modificationCount; | 288 int modificationCount = _modificationCount; |
271 int splayCount = _splayCount; | 289 int splayCount = _splayCount; |
272 V value = ifAbsent(); | 290 V value = ifAbsent(); |
273 if (modificationCount != _modificationCount) { | 291 if (modificationCount != _modificationCount) { |
274 throw new ConcurrentModificationError(this); | 292 throw new ConcurrentModificationError(this); |
275 } | 293 } |
276 if (splayCount != _splayCount) { | 294 if (splayCount != _splayCount) { |
277 comp = _splay(key); | 295 comp = _splay(key); |
(...skipping 26 matching lines...) Expand all Loading... | |
304 void clear() { | 322 void clear() { |
305 _clear(); | 323 _clear(); |
306 } | 324 } |
307 | 325 |
308 bool containsKey(K key) { | 326 bool containsKey(K key) { |
309 return _splay(key) == 0; | 327 return _splay(key) == 0; |
310 } | 328 } |
311 | 329 |
312 bool containsValue(V value) { | 330 bool containsValue(V value) { |
313 bool found = false; | 331 bool found = false; |
332 int initialSplayCount = _splayCount; | |
314 bool visit(_SplayTreeNode node) { | 333 bool visit(_SplayTreeNode node) { |
315 if (node == null) return false; | 334 while (node != null) { |
316 if (node.value == value) return true; | 335 if (node.value == value) return true; |
317 // TODO(lrn): Do we want to handle the case where node.value.operator== | 336 if (initialSplayCount != _splayCount) { |
318 // modifies the map? | 337 throw new ConcurrentModificationError(this); |
319 return visit(node.left) || visit(node.right); | 338 } |
339 if (node.right != null && visit(node.right)) return true; | |
340 node = node.left; | |
341 } | |
342 return false; | |
320 } | 343 } |
321 return visit(_root); | 344 return visit(_root); |
322 } | 345 } |
323 | 346 |
324 Iterable<K> get keys => new _SplayTreeKeyIterable<K>(this); | 347 Iterable<K> get keys => new _SplayTreeKeyIterable<K>(this); |
325 | 348 |
326 Iterable<V> get values => new _SplayTreeValueIterable<K, V>(this); | 349 Iterable<V> get values => new _SplayTreeValueIterable<K, V>(this); |
327 | 350 |
328 String toString() { | 351 String toString() { |
329 return Maps.mapToString(this); | 352 return Maps.mapToString(this); |
330 } | 353 } |
331 | 354 |
332 /** | 355 /** |
333 * Get the first key in the map. Returns [null] if the map is empty. | 356 * Get the first key in the map. Returns [null] if the map is empty. |
334 */ | 357 */ |
335 K firstKey() { | 358 K firstKey() { |
336 _SplayTreeNode node = _first; | 359 if (_root == null) return null; |
337 return (node == null) ? null : node.key; | 360 return _first.key; |
338 } | 361 } |
339 | 362 |
340 /** | 363 /** |
341 * Get the last key in the map. Returns [null] if the map is empty. | 364 * Get the last key in the map. Returns [null] if the map is empty. |
342 */ | 365 */ |
343 K lastKey() { | 366 K lastKey() { |
344 _SplayTreeNode node = _last; | 367 if (_root == null) return null; |
345 return (node == null) ? null : node.key; | 368 return _last.key; |
346 } | 369 } |
347 | 370 |
348 /** | 371 /** |
349 * Get the last key in the map that is strictly smaller than [key]. Returns | 372 * Get the last key in the map that is strictly smaller than [key]. Returns |
350 * [null] if no key was not found. | 373 * [null] if no key was not found. |
351 */ | 374 */ |
352 K lastKeyBefore(K key) { | 375 K lastKeyBefore(K key) { |
376 if (key == null) throw new ArgumentError(key); | |
353 if (_root == null) return null; | 377 if (_root == null) return null; |
354 int comp = _splay(key); | 378 int comp = _splay(key); |
355 if (comp < 0) return _root.key; | 379 if (comp < 0) return _root.key; |
356 _SplayTreeNode<K> node = _root.left; | 380 _SplayTreeNode<K> node = _root.left; |
357 if (node == null) return null; | 381 if (node == null) return null; |
358 while (node.right != null) { | 382 while (node.right != null) { |
359 node = node.right; | 383 node = node.right; |
360 } | 384 } |
361 return node.key; | 385 return node.key; |
362 } | 386 } |
363 | 387 |
364 /** | 388 /** |
365 * Get the first key in the map that is strictly larger than [key]. Returns | 389 * Get the first key in the map that is strictly larger than [key]. Returns |
366 * [null] if no key was not found. | 390 * [null] if no key was not found. |
367 */ | 391 */ |
368 K firstKeyAfter(K key) { | 392 K firstKeyAfter(K key) { |
393 if (key == null) throw new ArgumentError(key); | |
369 if (_root == null) return null; | 394 if (_root == null) return null; |
370 int comp = _splay(key); | 395 int comp = _splay(key); |
371 if (comp > 0) return _root.key; | 396 if (comp > 0) return _root.key; |
372 _SplayTreeNode<K> node = _root.right; | 397 _SplayTreeNode<K> node = _root.right; |
373 if (node == null) return null; | 398 if (node == null) return null; |
374 while (node.left != null) { | 399 while (node.left != null) { |
375 node = node.left; | 400 node = node.left; |
376 } | 401 } |
377 return node.key; | 402 return node.key; |
378 } | 403 } |
(...skipping 118 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
497 class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<V> { | 522 class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<V> { |
498 _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map); | 523 _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map); |
499 V _getValue(_SplayTreeMapNode node) => node.value; | 524 V _getValue(_SplayTreeMapNode node) => node.value; |
500 } | 525 } |
501 | 526 |
502 class _SplayTreeNodeIterator<K> | 527 class _SplayTreeNodeIterator<K> |
503 extends _SplayTreeIterator<_SplayTreeNode<K>> { | 528 extends _SplayTreeIterator<_SplayTreeNode<K>> { |
504 _SplayTreeNodeIterator(_SplayTree<K> map): super(map); | 529 _SplayTreeNodeIterator(_SplayTree<K> map): super(map); |
505 _SplayTreeNode<K> _getValue(_SplayTreeNode node) => node; | 530 _SplayTreeNode<K> _getValue(_SplayTreeNode node) => node; |
506 } | 531 } |
OLD | NEW |