| 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 410 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 421 | 421 |
| 422 Iterable<K> get keys => new _SplayTreeKeyIterable<K>(this); | 422 Iterable<K> get keys => new _SplayTreeKeyIterable<K>(this); |
| 423 | 423 |
| 424 Iterable<V> get values => new _SplayTreeValueIterable<K, V>(this); | 424 Iterable<V> get values => new _SplayTreeValueIterable<K, V>(this); |
| 425 | 425 |
| 426 String toString() { | 426 String toString() { |
| 427 return Maps.mapToString(this); | 427 return Maps.mapToString(this); |
| 428 } | 428 } |
| 429 | 429 |
| 430 /** | 430 /** |
| 431 * Get the first key in the map. Returns [null] if the map is empty. | 431 * Get the first key in the map. Returns [:null:] if the map is empty. |
| 432 */ | 432 */ |
| 433 K firstKey() { | 433 K firstKey() { |
| 434 if (_root == null) return null; | 434 if (_root == null) return null; |
| 435 return _first.key; | 435 return _first.key; |
| 436 } | 436 } |
| 437 | 437 |
| 438 /** | 438 /** |
| 439 * Get the last key in the map. Returns [null] if the map is empty. | 439 * Get the last key in the map. Returns [:null:] if the map is empty. |
| 440 */ | 440 */ |
| 441 K lastKey() { | 441 K lastKey() { |
| 442 if (_root == null) return null; | 442 if (_root == null) return null; |
| 443 return _last.key; | 443 return _last.key; |
| 444 } | 444 } |
| 445 | 445 |
| 446 /** | 446 /** |
| 447 * Get the last key in the map that is strictly smaller than [key]. Returns | 447 * Get the last key in the map that is strictly smaller than [key]. Returns |
| 448 * [null] if no key was not found. | 448 * [:null:] if no key was not found. |
| 449 */ | 449 */ |
| 450 K lastKeyBefore(K key) { | 450 K lastKeyBefore(K key) { |
| 451 if (key == null) throw new ArgumentError(key); | 451 if (key == null) throw new ArgumentError(key); |
| 452 if (_root == null) return null; | 452 if (_root == null) return null; |
| 453 int comp = _splay(key); | 453 int comp = _splay(key); |
| 454 if (comp < 0) return _root.key; | 454 if (comp < 0) return _root.key; |
| 455 _SplayTreeNode<K> node = _root.left; | 455 _SplayTreeNode<K> node = _root.left; |
| 456 if (node == null) return null; | 456 if (node == null) return null; |
| 457 while (node.right != null) { | 457 while (node.right != null) { |
| 458 node = node.right; | 458 node = node.right; |
| 459 } | 459 } |
| 460 return node.key; | 460 return node.key; |
| 461 } | 461 } |
| 462 | 462 |
| 463 /** | 463 /** |
| 464 * Get the first key in the map that is strictly larger than [key]. Returns | 464 * Get the first key in the map that is strictly larger than [key]. Returns |
| 465 * [null] if no key was not found. | 465 * [:null:] if no key was not found. |
| 466 */ | 466 */ |
| 467 K firstKeyAfter(K key) { | 467 K firstKeyAfter(K key) { |
| 468 if (key == null) throw new ArgumentError(key); | 468 if (key == null) throw new ArgumentError(key); |
| 469 if (_root == null) return null; | 469 if (_root == null) return null; |
| 470 int comp = _splay(key); | 470 int comp = _splay(key); |
| 471 if (comp > 0) return _root.key; | 471 if (comp > 0) return _root.key; |
| 472 _SplayTreeNode<K> node = _root.right; | 472 _SplayTreeNode<K> node = _root.right; |
| 473 if (node == null) return null; | 473 if (node == null) return null; |
| 474 while (node.left != null) { | 474 while (node.left != null) { |
| 475 node = node.left; | 475 node = node.left; |
| (...skipping 341 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 817 | 817 |
| 818 bool containsAll(Iterable<Object> other) { | 818 bool containsAll(Iterable<Object> other) { |
| 819 for (var element in other) { | 819 for (var element in other) { |
| 820 if (!this.contains(element)) return false; | 820 if (!this.contains(element)) return false; |
| 821 } | 821 } |
| 822 return true; | 822 return true; |
| 823 } | 823 } |
| 824 | 824 |
| 825 void clear() { _clear(); } | 825 void clear() { _clear(); } |
| 826 } | 826 } |
| OLD | NEW |