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 242 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
253 * Keys of the map are compared using the `compare` function passed in | 253 * Keys of the map are compared using the `compare` function passed in |
254 * the constructor, both for ordering and for equality. | 254 * the constructor, both for ordering and for equality. |
255 * If the map contains only the key `a`, then `map.containsKey(b)` | 255 * If the map contains only the key `a`, then `map.containsKey(b)` |
256 * will return `true` if and only if `compare(a, b) == 0`, | 256 * will return `true` if and only if `compare(a, b) == 0`, |
257 * and the value of `a == b` is not even checked. | 257 * and the value of `a == b` is not even checked. |
258 * If the compare function is omitted, the objects are assumed to be | 258 * If the compare function is omitted, the objects are assumed to be |
259 * [Comparable], and are compared using their [Comparable.compareTo] method. | 259 * [Comparable], and are compared using their [Comparable.compareTo] method. |
260 * Non-comparable objects (including `null`) will not work as keys | 260 * Non-comparable objects (including `null`) will not work as keys |
261 * in that case. | 261 * in that case. |
262 * | 262 * |
263 * To allow calling [operator[]], [remove] or [containsKey] with objects | 263 * To allow calling [[]], [remove] or [containsKey] with objects |
264 * that are not supported by the `compare` function, an extra `isValidKey` | 264 * that are not supported by the `compare` function, an extra `isValidKey` |
265 * predicate function can be supplied. This function is tested before | 265 * predicate function can be supplied. This function is tested before |
266 * using the `compare` function on an argument value that may not be a [K] | 266 * using the `compare` function on an argument value that may not be a [K] |
267 * value. If omitted, the `isValidKey` function defaults to testing if the | 267 * value. If omitted, the `isValidKey` function defaults to testing if the |
268 * value is a [K]. | 268 * value is a [K]. |
269 */ | 269 */ |
270 class SplayTreeMap<K, V> extends _SplayTree<K, _SplayTreeMapNode<K, V>> | 270 class SplayTreeMap<K, V> extends _SplayTree<K, _SplayTreeMapNode<K, V>> |
271 implements Map<K, V> { | 271 implements Map<K, V> { |
272 _SplayTreeMapNode<K, V> _root; | 272 _SplayTreeMapNode<K, V> _root; |
273 final _SplayTreeMapNode<K, V> _dummy = | 273 final _SplayTreeMapNode<K, V> _dummy = |
(...skipping 573 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 |