| 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 215 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 226 return _root; | 226 return _root; |
| 227 } | 227 } |
| 228 | 228 |
| 229 void _clear() { | 229 void _clear() { |
| 230 _root = null; | 230 _root = null; |
| 231 _count = 0; | 231 _count = 0; |
| 232 _modificationCount++; | 232 _modificationCount++; |
| 233 } | 233 } |
| 234 } | 234 } |
| 235 | 235 |
| 236 class _TypeTest<T> { | |
| 237 bool test(v) => v is T; | |
| 238 } | |
| 239 | |
| 240 /** | 236 /** |
| 241 * A [Map] of objects that can be ordered relative to each other. | 237 * A [Map] of objects that can be ordered relative to each other. |
| 242 * | 238 * |
| 243 * The map is based on a self-balancing binary tree. It allows most operations | 239 * The map is based on a self-balancing binary tree. It allows most operations |
| 244 * in amortized logarithmic time. | 240 * in amortized logarithmic time. |
| 245 * | 241 * |
| 246 * Keys of the map are compared using the `compare` function passed in | 242 * Keys of the map are compared using the `compare` function passed in |
| 247 * the constructor, both for ordering and for equality. | 243 * the constructor, both for ordering and for equality. |
| 248 * If the map contains only the key `a`, then `map.containsKey(b)` | 244 * If the map contains only the key `a`, then `map.containsKey(b)` |
| 249 * will return `true` if and only if `compare(a, b) == 0`, | 245 * will return `true` if and only if `compare(a, b) == 0`, |
| (...skipping 339 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 589 return false; | 585 return false; |
| 590 } | 586 } |
| 591 if (_tree._splayCount != _splayCount && _currentNode != null) { | 587 if (_tree._splayCount != _splayCount && _currentNode != null) { |
| 592 _rebuildWorkList(_currentNode); | 588 _rebuildWorkList(_currentNode); |
| 593 } | 589 } |
| 594 _currentNode = _workList.removeLast(); | 590 _currentNode = _workList.removeLast(); |
| 595 _findLeftMostDescendent(_currentNode.right); | 591 _findLeftMostDescendent(_currentNode.right); |
| 596 return true; | 592 return true; |
| 597 } | 593 } |
| 598 | 594 |
| 599 T _getValue(_SplayTreeNode node); | 595 T _getValue(_SplayTreeMapNode node); |
| 600 } | 596 } |
| 601 | 597 |
| 602 class _SplayTreeKeyIterable<K> extends IterableBase<K> | 598 class _SplayTreeKeyIterable<K> extends IterableBase<K> |
| 603 implements EfficientLength { | 599 implements EfficientLength { |
| 604 _SplayTree<K> _tree; | 600 _SplayTree<K> _tree; |
| 605 _SplayTreeKeyIterable(this._tree); | 601 _SplayTreeKeyIterable(this._tree); |
| 606 int get length => _tree._count; | 602 int get length => _tree._count; |
| 607 bool get isEmpty => _tree._count == 0; | 603 bool get isEmpty => _tree._count == 0; |
| 608 Iterator<K> get iterator => new _SplayTreeKeyIterator<K>(_tree); | 604 Iterator<K> get iterator => new _SplayTreeKeyIterator<K>(_tree); |
| 609 | 605 |
| (...skipping 178 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 788 } | 784 } |
| 789 } | 785 } |
| 790 | 786 |
| 791 E lookup(Object object) { | 787 E lookup(Object object) { |
| 792 if (!_validKey(object)) return null; | 788 if (!_validKey(object)) return null; |
| 793 int comp = _splay(object); | 789 int comp = _splay(object); |
| 794 if (comp != 0) return null; | 790 if (comp != 0) return null; |
| 795 return _root.key; | 791 return _root.key; |
| 796 } | 792 } |
| 797 | 793 |
| 798 Set<E> intersection(Set<E> other) { | 794 Set<E> intersection(Set<Object> other) { |
| 799 Set<E> result = new SplayTreeSet<E>(_comparator, _validKey); | 795 Set<E> result = new SplayTreeSet<E>(_comparator, _validKey); |
| 800 for (E element in this) { | 796 for (E element in this) { |
| 801 if (other.contains(element)) result.add(element); | 797 if (other.contains(element)) result.add(element); |
| 802 } | 798 } |
| 803 return result; | 799 return result; |
| 804 } | 800 } |
| 805 | 801 |
| 806 Set<E> difference(Set<E> other) { | 802 Set<E> difference(Set<Object> other) { |
| 807 Set<E> result = new SplayTreeSet<E>(_comparator, _validKey); | 803 Set<E> result = new SplayTreeSet<E>(_comparator, _validKey); |
| 808 for (E element in this) { | 804 for (E element in this) { |
| 809 if (!other.contains(element)) result.add(element); | 805 if (!other.contains(element)) result.add(element); |
| 810 } | 806 } |
| 811 return result; | 807 return result; |
| 812 } | 808 } |
| 813 | 809 |
| 814 Set<E> union(Set<E> other) { | 810 Set<E> union(Set<E> other) { |
| 815 return _clone()..addAll(other); | 811 return _clone()..addAll(other); |
| 816 } | 812 } |
| (...skipping 12 matching lines...) Expand all Loading... |
| 829 return new _SplayTreeNode<E>(node.key)..left = _copyNode(node.left) | 825 return new _SplayTreeNode<E>(node.key)..left = _copyNode(node.left) |
| 830 ..right = _copyNode(node.right); | 826 ..right = _copyNode(node.right); |
| 831 } | 827 } |
| 832 | 828 |
| 833 void clear() { _clear(); } | 829 void clear() { _clear(); } |
| 834 | 830 |
| 835 Set<E> toSet() => _clone(); | 831 Set<E> toSet() => _clone(); |
| 836 | 832 |
| 837 String toString() => IterableBase.iterableToFullString(this, '{', '}'); | 833 String toString() => IterableBase.iterableToFullString(this, '{', '}'); |
| 838 } | 834 } |
| OLD | NEW |