| 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 |
| 11 * and right children in the tree. | 11 * and right children in the tree. |
| 12 */ | 12 */ |
| 13 class _SplayTreeNode<K> { | 13 class _SplayTreeNode<K> { |
| 14 final K key; | 14 final K key; |
| 15 _SplayTreeNode<K> left; | 15 _SplayTreeNode<K> left; |
| 16 _SplayTreeNode<K> right; | 16 _SplayTreeNode<K> right; |
| 17 | 17 |
| 18 _SplayTreeNode(K this.key); | 18 _SplayTreeNode(this.key); |
| 19 } | 19 } |
| 20 | 20 |
| 21 /** | 21 /** |
| 22 * A node in a splay tree based map. | 22 * A node in a splay tree based map. |
| 23 * | 23 * |
| 24 * A [_SplayTreeNode] that also contains a value | 24 * A [_SplayTreeNode] that also contains a value |
| 25 */ | 25 */ |
| 26 class _SplayTreeMapNode<K, V> extends _SplayTreeNode<K> { | 26 class _SplayTreeMapNode<K, V> extends _SplayTreeNode<K> { |
| 27 V value; | 27 V value; |
| 28 _SplayTreeMapNode(K key, V this.value) : super(key); | 28 _SplayTreeMapNode(K key, this.value) : super(key); |
| 29 } | 29 } |
| 30 | 30 |
| 31 /** | 31 /** |
| 32 * A splay tree is a self-balancing binary search tree. | 32 * A splay tree is a self-balancing binary search tree. |
| 33 * | 33 * |
| 34 * It has the additional property that recently accessed elements | 34 * It has the additional property that recently accessed elements |
| 35 * are quick to access again. | 35 * are quick to access again. |
| 36 * It performs basic operations such as insertion, look-up and | 36 * It performs basic operations such as insertion, look-up and |
| 37 * removal, in O(log(n)) amortized time. | 37 * removal, in O(log(n)) amortized time. |
| 38 */ | 38 */ |
| (...skipping 808 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 847 return new _SplayTreeNode<E>(node.key)..left = _copyNode(node.left) | 847 return new _SplayTreeNode<E>(node.key)..left = _copyNode(node.left) |
| 848 ..right = _copyNode(node.right); | 848 ..right = _copyNode(node.right); |
| 849 } | 849 } |
| 850 | 850 |
| 851 void clear() { _clear(); } | 851 void clear() { _clear(); } |
| 852 | 852 |
| 853 Set<E> toSet() => _clone(); | 853 Set<E> toSet() => _clone(); |
| 854 | 854 |
| 855 String toString() => IterableBase.iterableToFullString(this, '{', '}'); | 855 String toString() => IterableBase.iterableToFullString(this, '{', '}'); |
| 856 } | 856 } |
| OLD | NEW |