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 |