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 |