| 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 |