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 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
59 * Counter incremented whenever the tree structure changes. | 59 * Counter incremented whenever the tree structure changes. |
60 * | 60 * |
61 * Used to detect that an in-place traversal cannot use | 61 * Used to detect that an in-place traversal cannot use |
62 * cached information that relies on the tree structure. | 62 * cached information that relies on the tree structure. |
63 */ | 63 */ |
64 int _splayCount = 0; | 64 int _splayCount = 0; |
65 | 65 |
66 /** Comparison used to compare keys. */ | 66 /** Comparison used to compare keys. */ |
67 int _compare(K key1, K key2); | 67 int _compare(K key1, K key2); |
68 | 68 |
| 69 Comparator<K> get _comparator; |
| 70 |
| 71 _Predicate<Object> get _validKey; |
| 72 |
69 /** | 73 /** |
70 * Perform the splay operation for the given key. Moves the node with | 74 * Perform the splay operation for the given key. Moves the node with |
71 * the given key to the top of the tree. If no node has the given | 75 * the given key to the top of the tree. If no node has the given |
72 * key, the last node on the search path is moved to the top of the | 76 * key, the last node on the search path is moved to the top of the |
73 * tree. This is the simplified top-down splaying algorithm from: | 77 * tree. This is the simplified top-down splaying algorithm from: |
74 * "Self-adjusting Binary Search Trees" by Sleator and Tarjan. | 78 * "Self-adjusting Binary Search Trees" by Sleator and Tarjan. |
75 * | 79 * |
76 * Returns the result of comparing the new root of the tree to [key]. | 80 * Returns the result of comparing the new root of the tree to [key]. |
77 * Returns -1 if the table is empty. | 81 * Returns -1 if the table is empty. |
78 */ | 82 */ |
(...skipping 748 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
827 return new _SplayTreeNode<E>(node.key)..left = _copyNode(node.left) | 831 return new _SplayTreeNode<E>(node.key)..left = _copyNode(node.left) |
828 ..right = _copyNode(node.right); | 832 ..right = _copyNode(node.right); |
829 } | 833 } |
830 | 834 |
831 void clear() { _clear(); } | 835 void clear() { _clear(); } |
832 | 836 |
833 Set<E> toSet() => _clone(); | 837 Set<E> toSet() => _clone(); |
834 | 838 |
835 String toString() => IterableBase.iterableToFullString(this, '{', '}'); | 839 String toString() => IterableBase.iterableToFullString(this, '{', '}'); |
836 } | 840 } |
OLD | NEW |