| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 part of dart.collection; | |
| 6 | |
| 7 typedef bool _Predicate<T>(T value); | |
| 8 | |
| 9 /** | |
| 10 * A node in a splay tree. It holds the sorting key and the left | |
| 11 * and right children in the tree. | |
| 12 */ | |
| 13 class _SplayTreeNode<K> { | |
| 14 final K key; | |
| 15 _SplayTreeNode<K> left; | |
| 16 _SplayTreeNode<K> right; | |
| 17 | |
| 18 _SplayTreeNode(K this.key); | |
| 19 } | |
| 20 | |
| 21 /** | |
| 22 * A node in a splay tree based map. | |
| 23 * | |
| 24 * A [_SplayTreeNode] that also contains a value | |
| 25 */ | |
| 26 class _SplayTreeMapNode<K, V> extends _SplayTreeNode<K> { | |
| 27 V value; | |
| 28 _SplayTreeMapNode(K key, V this.value) : super(key); | |
| 29 } | |
| 30 | |
| 31 /** | |
| 32 * A splay tree is a self-balancing binary search tree. | |
| 33 * | |
| 34 * It has the additional property that recently accessed elements | |
| 35 * are quick to access again. | |
| 36 * It performs basic operations such as insertion, look-up and | |
| 37 * removal, in O(log(n)) amortized time. | |
| 38 */ | |
| 39 abstract class _SplayTree<K, Node extends _SplayTreeNode<K>> { | |
| 40 // The root node of the splay tree. It will contain either the last | |
| 41 // element inserted or the last element looked up. | |
| 42 Node get _root; | |
| 43 set _root(Node newValue); | |
| 44 | |
| 45 // The dummy node used when performing a splay on the tree. Reusing it | |
| 46 // avoids allocating a node each time a splay is performed. | |
| 47 Node get _dummy; | |
| 48 | |
| 49 // Number of elements in the splay tree. | |
| 50 int _count = 0; | |
| 51 | |
| 52 /** | |
| 53 * Counter incremented whenever the keys in the map changes. | |
| 54 * | |
| 55 * Used to detect concurrent modifications. | |
| 56 */ | |
| 57 int _modificationCount = 0; | |
| 58 | |
| 59 /** | |
| 60 * Counter incremented whenever the tree structure changes. | |
| 61 * | |
| 62 * Used to detect that an in-place traversal cannot use | |
| 63 * cached information that relies on the tree structure. | |
| 64 */ | |
| 65 int _splayCount = 0; | |
| 66 | |
| 67 /** The comparator that is used for this splay tree. */ | |
| 68 Comparator<K> get _comparator; | |
| 69 | |
| 70 /** The predicate to determine that a given object is a valid key. */ | |
| 71 _Predicate get _validKey; | |
| 72 | |
| 73 /** Comparison used to compare keys. */ | |
| 74 int _compare(K key1, K key2); | |
| 75 | |
| 76 /** | |
| 77 * Perform the splay operation for the given key. Moves the node with | |
| 78 * the given key to the top of the tree. If no node has the given | |
| 79 * key, the last node on the search path is moved to the top of the | |
| 80 * tree. This is the simplified top-down splaying algorithm from: | |
| 81 * "Self-adjusting Binary Search Trees" by Sleator and Tarjan. | |
| 82 * | |
| 83 * Returns the result of comparing the new root of the tree to [key]. | |
| 84 * Returns -1 if the table is empty. | |
| 85 */ | |
| 86 int _splay(K key) { | |
| 87 if (_root == null) return -1; | |
| 88 | |
| 89 // The right child of the dummy node will hold | |
| 90 // the L tree of the algorithm. The left child of the dummy node | |
| 91 // will hold the R tree of the algorithm. Using a dummy node, left | |
| 92 // and right will always be nodes and we avoid special cases. | |
| 93 Node left = _dummy; | |
| 94 Node right = _dummy; | |
| 95 Node current = _root; | |
| 96 int comp; | |
| 97 while (true) { | |
| 98 comp = _compare(current.key, key); | |
| 99 if (comp > 0) { | |
| 100 if (current.left == null) break; | |
| 101 comp = _compare(current.left.key, key); | |
| 102 if (comp > 0) { | |
| 103 // Rotate right. | |
| 104 _SplayTreeNode<K> tmp = current.left; | |
| 105 current.left = tmp.right; | |
| 106 tmp.right = current; | |
| 107 current = tmp; | |
| 108 if (current.left == null) break; | |
| 109 } | |
| 110 // Link right. | |
| 111 right.left = current; | |
| 112 right = current; | |
| 113 current = current.left; | |
| 114 } else if (comp < 0) { | |
| 115 if (current.right == null) break; | |
| 116 comp = _compare(current.right.key, key); | |
| 117 if (comp < 0) { | |
| 118 // Rotate left. | |
| 119 Node tmp = current.right; | |
| 120 current.right = tmp.left; | |
| 121 tmp.left = current; | |
| 122 current = tmp; | |
| 123 if (current.right == null) break; | |
| 124 } | |
| 125 // Link left. | |
| 126 left.right = current; | |
| 127 left = current; | |
| 128 current = current.right; | |
| 129 } else { | |
| 130 break; | |
| 131 } | |
| 132 } | |
| 133 // Assemble. | |
| 134 left.right = current.left; | |
| 135 right.left = current.right; | |
| 136 current.left = _dummy.right; | |
| 137 current.right = _dummy.left; | |
| 138 _root = current; | |
| 139 | |
| 140 _dummy.right = null; | |
| 141 _dummy.left = null; | |
| 142 _splayCount++; | |
| 143 return comp; | |
| 144 } | |
| 145 | |
| 146 // Emulates splaying with a key that is smaller than any in the subtree | |
| 147 // anchored at [node]. | |
| 148 // and that node is returned. It should replace the reference to [node] | |
| 149 // in any parent tree or root pointer. | |
| 150 Node _splayMin(Node node) { | |
| 151 Node current = node; | |
| 152 while (current.left != null) { | |
| 153 Node left = current.left; | |
| 154 current.left = left.right; | |
| 155 left.right = current; | |
| 156 current = left; | |
| 157 } | |
| 158 return current; | |
| 159 } | |
| 160 | |
| 161 // Emulates splaying with a key that is greater than any in the subtree | |
| 162 // anchored at [node]. | |
| 163 // After this, the largest element in the tree is the root of the subtree, | |
| 164 // and that node is returned. It should replace the reference to [node] | |
| 165 // in any parent tree or root pointer. | |
| 166 Node _splayMax(Node node) { | |
| 167 Node current = node; | |
| 168 while (current.right != null) { | |
| 169 Node right = current.right; | |
| 170 current.right = right.left; | |
| 171 right.left = current; | |
| 172 current = right; | |
| 173 } | |
| 174 return current; | |
| 175 } | |
| 176 | |
| 177 Node _remove(K key) { | |
| 178 if (_root == null) return null; | |
| 179 int comp = _splay(key); | |
| 180 if (comp != 0) return null; | |
| 181 Node result = _root; | |
| 182 _count--; | |
| 183 // assert(_count >= 0); | |
| 184 if (_root.left == null) { | |
| 185 _root = _root.right; | |
| 186 } else { | |
| 187 Node right = _root.right; | |
| 188 // Splay to make sure that the new root has an empty right child. | |
| 189 _root = _splayMax(_root.left); | |
| 190 // Insert the original right child as the right child of the new | |
| 191 // root. | |
| 192 _root.right = right; | |
| 193 } | |
| 194 _modificationCount++; | |
| 195 return result; | |
| 196 } | |
| 197 | |
| 198 /** | |
| 199 * Adds a new root node with the given [key] or [value]. | |
| 200 * | |
| 201 * The [comp] value is the result of comparing the existing root's key | |
| 202 * with key. | |
| 203 */ | |
| 204 void _addNewRoot(Node node, int comp) { | |
| 205 _count++; | |
| 206 _modificationCount++; | |
| 207 if (_root == null) { | |
| 208 _root = node; | |
| 209 return; | |
| 210 } | |
| 211 // assert(_count >= 0); | |
| 212 if (comp < 0) { | |
| 213 node.left = _root; | |
| 214 node.right = _root.right; | |
| 215 _root.right = null; | |
| 216 } else { | |
| 217 node.right = _root; | |
| 218 node.left = _root.left; | |
| 219 _root.left = null; | |
| 220 } | |
| 221 _root = node; | |
| 222 } | |
| 223 | |
| 224 Node get _first { | |
| 225 if (_root == null) return null; | |
| 226 _root = _splayMin(_root); | |
| 227 return _root; | |
| 228 } | |
| 229 | |
| 230 Node get _last { | |
| 231 if (_root == null) return null; | |
| 232 _root = _splayMax(_root); | |
| 233 return _root; | |
| 234 } | |
| 235 | |
| 236 void _clear() { | |
| 237 _root = null; | |
| 238 _count = 0; | |
| 239 _modificationCount++; | |
| 240 } | |
| 241 } | |
| 242 | |
| 243 class _TypeTest<T> { | |
| 244 bool test(v) => v is T; | |
| 245 } | |
| 246 | |
| 247 /** | |
| 248 * A [Map] of objects that can be ordered relative to each other. | |
| 249 * | |
| 250 * The map is based on a self-balancing binary tree. It allows most operations | |
| 251 * in amortized logarithmic time. | |
| 252 * | |
| 253 * Keys of the map are compared using the `compare` function passed in | |
| 254 * the constructor, both for ordering and for equality. | |
| 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`, | |
| 257 * and the value of `a == b` is not even checked. | |
| 258 * If the compare function is omitted, the objects are assumed to be | |
| 259 * [Comparable], and are compared using their [Comparable.compareTo] method. | |
| 260 * Non-comparable objects (including `null`) will not work as keys | |
| 261 * in that case. | |
| 262 * | |
| 263 * To allow calling [operator[]], [remove] or [containsKey] with objects | |
| 264 * that are not supported by the `compare` function, an extra `isValidKey` | |
| 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] | |
| 267 * value. If omitted, the `isValidKey` function defaults to testing if the | |
| 268 * value is a [K]. | |
| 269 */ | |
| 270 class SplayTreeMap<K, V> extends _SplayTree<K, _SplayTreeMapNode<K, V>> | |
| 271 implements Map<K, V> { | |
| 272 _SplayTreeMapNode<K, V> _root; | |
| 273 final _SplayTreeMapNode<K, V> _dummy = | |
| 274 new _SplayTreeMapNode<K, V>(null, null); | |
| 275 | |
| 276 Comparator<K> _comparator; | |
| 277 _Predicate _validKey; | |
| 278 | |
| 279 SplayTreeMap([int compare(K key1, K key2), bool isValidKey(potentialKey)]) | |
| 280 : _comparator = compare ?? Comparable.compare as Comparator<K>, | |
| 281 _validKey = isValidKey ?? ((v) => v is K); | |
| 282 | |
| 283 /** | |
| 284 * Creates a [SplayTreeMap] that contains all key/value pairs of [other]. | |
| 285 */ | |
| 286 factory SplayTreeMap.from(Map other, | |
| 287 [int compare(K key1, K key2), | |
| 288 bool isValidKey(potentialKey)]) { | |
| 289 SplayTreeMap<K, V> result = new SplayTreeMap<K, V>(compare, isValidKey); | |
| 290 other.forEach((k, v) { result[k as Object/*=K*/] = v as Object/*=V*/; }); | |
| 291 return result; | |
| 292 } | |
| 293 | |
| 294 /** | |
| 295 * Creates a [SplayTreeMap] where the keys and values are computed from the | |
| 296 * [iterable]. | |
| 297 * | |
| 298 * For each element of the [iterable] this constructor computes a key/value | |
| 299 * pair, by applying [key] and [value] respectively. | |
| 300 * | |
| 301 * The keys of the key/value pairs do not need to be unique. The last | |
| 302 * occurrence of a key will simply overwrite any previous value. | |
| 303 * | |
| 304 * If no functions are specified for [key] and [value] the default is to | |
| 305 * use the iterable value itself. | |
| 306 */ | |
| 307 factory SplayTreeMap.fromIterable(Iterable iterable, | |
| 308 {K key(element), | |
| 309 V value(element), | |
| 310 int compare(K key1, K key2), | |
| 311 bool isValidKey(potentialKey) }) { | |
| 312 SplayTreeMap<K, V> map = new SplayTreeMap<K, V>(compare, isValidKey); | |
| 313 Maps._fillMapWithMappedIterable(map, iterable, key, value); | |
| 314 return map; | |
| 315 } | |
| 316 | |
| 317 /** | |
| 318 * Creates a [SplayTreeMap] associating the given [keys] to [values]. | |
| 319 * | |
| 320 * This constructor iterates over [keys] and [values] and maps each element of | |
| 321 * [keys] to the corresponding element of [values]. | |
| 322 * | |
| 323 * If [keys] contains the same object multiple times, the last occurrence | |
| 324 * overwrites the previous value. | |
| 325 * | |
| 326 * It is an error if the two [Iterable]s don't have the same length. | |
| 327 */ | |
| 328 factory SplayTreeMap.fromIterables(Iterable<K> keys, Iterable<V> values, | |
| 329 [int compare(K key1, K key2), bool isValidKey(potentialKey)]) { | |
| 330 SplayTreeMap<K, V> map = new SplayTreeMap<K, V>(compare, isValidKey); | |
| 331 Maps._fillMapWithIterables(map, keys, values); | |
| 332 return map; | |
| 333 } | |
| 334 | |
| 335 int _compare(K key1, K key2) => _comparator(key1, key2); | |
| 336 | |
| 337 SplayTreeMap._internal(); | |
| 338 | |
| 339 V operator [](Object key) { | |
| 340 if (!_validKey(key)) return null; | |
| 341 if (_root != null) { | |
| 342 int comp = _splay(key as dynamic/*=K*/); | |
| 343 if (comp == 0) { | |
| 344 return _root.value; | |
| 345 } | |
| 346 } | |
| 347 return null; | |
| 348 } | |
| 349 | |
| 350 V remove(Object key) { | |
| 351 if (!_validKey(key)) return null; | |
| 352 _SplayTreeMapNode<K, V> mapRoot = _remove(key as dynamic/*=K*/); | |
| 353 if (mapRoot != null) return mapRoot.value; | |
| 354 return null; | |
| 355 } | |
| 356 | |
| 357 void operator []=(K key, V value) { | |
| 358 if (key == null) throw new ArgumentError(key); | |
| 359 // Splay on the key to move the last node on the search path for | |
| 360 // the key to the root of the tree. | |
| 361 int comp = _splay(key); | |
| 362 if (comp == 0) { | |
| 363 _root.value = value; | |
| 364 return; | |
| 365 } | |
| 366 _addNewRoot(new _SplayTreeMapNode(key, value), comp); | |
| 367 } | |
| 368 | |
| 369 | |
| 370 V putIfAbsent(K key, V ifAbsent()) { | |
| 371 if (key == null) throw new ArgumentError(key); | |
| 372 int comp = _splay(key); | |
| 373 if (comp == 0) { | |
| 374 return _root.value; | |
| 375 } | |
| 376 int modificationCount = _modificationCount; | |
| 377 int splayCount = _splayCount; | |
| 378 V value = ifAbsent(); | |
| 379 if (modificationCount != _modificationCount) { | |
| 380 throw new ConcurrentModificationError(this); | |
| 381 } | |
| 382 if (splayCount != _splayCount) { | |
| 383 comp = _splay(key); | |
| 384 // Key is still not there, otherwise _modificationCount would be changed. | |
| 385 assert(comp != 0); | |
| 386 } | |
| 387 _addNewRoot(new _SplayTreeMapNode(key, value), comp); | |
| 388 return value; | |
| 389 } | |
| 390 | |
| 391 void addAll(Map<K, V> other) { | |
| 392 other.forEach((K key, V value) { this[key] = value; }); | |
| 393 } | |
| 394 | |
| 395 bool get isEmpty { | |
| 396 return (_root == null); | |
| 397 } | |
| 398 | |
| 399 bool get isNotEmpty => !isEmpty; | |
| 400 | |
| 401 void forEach(void f(K key, V value)) { | |
| 402 Iterator<_SplayTreeNode<K>> nodes = | |
| 403 new _SplayTreeNodeIterator<K>(this); | |
| 404 while (nodes.moveNext()) { | |
| 405 _SplayTreeMapNode<K, V> node = nodes.current; | |
| 406 f(node.key, node.value); | |
| 407 } | |
| 408 } | |
| 409 | |
| 410 int get length { | |
| 411 return _count; | |
| 412 } | |
| 413 | |
| 414 void clear() { | |
| 415 _clear(); | |
| 416 } | |
| 417 | |
| 418 bool containsKey(Object key) { | |
| 419 return _validKey(key) && _splay(key as dynamic/*=K*/) == 0; | |
| 420 } | |
| 421 | |
| 422 bool containsValue(Object value) { | |
| 423 bool found = false; | |
| 424 int initialSplayCount = _splayCount; | |
| 425 bool visit(_SplayTreeMapNode node) { | |
| 426 while (node != null) { | |
| 427 if (node.value == value) return true; | |
| 428 if (initialSplayCount != _splayCount) { | |
| 429 throw new ConcurrentModificationError(this); | |
| 430 } | |
| 431 if (node.right != null && visit(node.right)) return true; | |
| 432 node = node.left; | |
| 433 } | |
| 434 return false; | |
| 435 } | |
| 436 return visit(_root); | |
| 437 } | |
| 438 | |
| 439 Iterable<K> get keys => new _SplayTreeKeyIterable<K>(this); | |
| 440 | |
| 441 Iterable<V> get values => new _SplayTreeValueIterable<K, V>(this); | |
| 442 | |
| 443 String toString() { | |
| 444 return Maps.mapToString(this); | |
| 445 } | |
| 446 | |
| 447 /** | |
| 448 * Get the first key in the map. Returns [:null:] if the map is empty. | |
| 449 */ | |
| 450 K firstKey() { | |
| 451 if (_root == null) return null; | |
| 452 return _first.key; | |
| 453 } | |
| 454 | |
| 455 /** | |
| 456 * Get the last key in the map. Returns [:null:] if the map is empty. | |
| 457 */ | |
| 458 K lastKey() { | |
| 459 if (_root == null) return null; | |
| 460 return _last.key; | |
| 461 } | |
| 462 | |
| 463 /** | |
| 464 * Get the last key in the map that is strictly smaller than [key]. Returns | |
| 465 * [:null:] if no key was not found. | |
| 466 */ | |
| 467 K lastKeyBefore(K key) { | |
| 468 if (key == null) throw new ArgumentError(key); | |
| 469 if (_root == null) return null; | |
| 470 int comp = _splay(key); | |
| 471 if (comp < 0) return _root.key; | |
| 472 _SplayTreeNode<K> node = _root.left; | |
| 473 if (node == null) return null; | |
| 474 while (node.right != null) { | |
| 475 node = node.right; | |
| 476 } | |
| 477 return node.key; | |
| 478 } | |
| 479 | |
| 480 /** | |
| 481 * Get the first key in the map that is strictly larger than [key]. Returns | |
| 482 * [:null:] if no key was not found. | |
| 483 */ | |
| 484 K firstKeyAfter(K key) { | |
| 485 if (key == null) throw new ArgumentError(key); | |
| 486 if (_root == null) return null; | |
| 487 int comp = _splay(key); | |
| 488 if (comp > 0) return _root.key; | |
| 489 _SplayTreeNode<K> node = _root.right; | |
| 490 if (node == null) return null; | |
| 491 while (node.left != null) { | |
| 492 node = node.left; | |
| 493 } | |
| 494 return node.key; | |
| 495 } | |
| 496 } | |
| 497 | |
| 498 abstract class _SplayTreeIterator<K, T> implements Iterator<T> { | |
| 499 final _SplayTree<K, _SplayTreeNode<K>> _tree; | |
| 500 /** | |
| 501 * Worklist of nodes to visit. | |
| 502 * | |
| 503 * These nodes have been passed over on the way down in a | |
| 504 * depth-first left-to-right traversal. Visiting each node, | |
| 505 * and their right subtrees will visit the remainder of | |
| 506 * the nodes of a full traversal. | |
| 507 * | |
| 508 * Only valid as long as the original tree isn't reordered. | |
| 509 */ | |
| 510 final List<_SplayTreeNode<K>> _workList = <_SplayTreeNode<K>>[]; | |
| 511 | |
| 512 /** | |
| 513 * Original modification counter of [_tree]. | |
| 514 * | |
| 515 * Incremented on [_tree] when a key is added or removed. | |
| 516 * If it changes, iteration is aborted. | |
| 517 * | |
| 518 * Not final because some iterators may modify the tree knowingly, | |
| 519 * and they update the modification count in that case. | |
| 520 */ | |
| 521 int _modificationCount; | |
| 522 | |
| 523 /** | |
| 524 * Count of splay operations on [_tree] when [_workList] was built. | |
| 525 * | |
| 526 * If the splay count on [_tree] increases, [_workList] becomes invalid. | |
| 527 */ | |
| 528 int _splayCount; | |
| 529 | |
| 530 /** Current node. */ | |
| 531 _SplayTreeNode<K> _currentNode; | |
| 532 | |
| 533 _SplayTreeIterator(_SplayTree<K, _SplayTreeNode<K>> tree) | |
| 534 : _tree = tree, | |
| 535 _modificationCount = tree._modificationCount, | |
| 536 _splayCount = tree._splayCount { | |
| 537 _findLeftMostDescendent(tree._root); | |
| 538 } | |
| 539 | |
| 540 _SplayTreeIterator.startAt(_SplayTree<K, _SplayTreeNode<K>> tree, K startKey) | |
| 541 : _tree = tree, | |
| 542 _modificationCount = tree._modificationCount { | |
| 543 if (tree._root == null) return; | |
| 544 int compare = tree._splay(startKey); | |
| 545 _splayCount = tree._splayCount; | |
| 546 if (compare < 0) { | |
| 547 // Don't include the root, start at the next element after the root. | |
| 548 _findLeftMostDescendent(tree._root.right); | |
| 549 } else { | |
| 550 _workList.add(tree._root); | |
| 551 } | |
| 552 } | |
| 553 | |
| 554 T get current { | |
| 555 if (_currentNode == null) return null; | |
| 556 return _getValue(_currentNode); | |
| 557 } | |
| 558 | |
| 559 void _findLeftMostDescendent(_SplayTreeNode<K> node) { | |
| 560 while (node != null) { | |
| 561 _workList.add(node); | |
| 562 node = node.left; | |
| 563 } | |
| 564 } | |
| 565 | |
| 566 /** | |
| 567 * Called when the tree structure of the tree has changed. | |
| 568 * | |
| 569 * This can be caused by a splay operation. | |
| 570 * If the key-set changes, iteration is aborted before getting | |
| 571 * here, so we know that the keys are the same as before, it's | |
| 572 * only the tree that has been reordered. | |
| 573 */ | |
| 574 void _rebuildWorkList(_SplayTreeNode<K> currentNode) { | |
| 575 assert(!_workList.isEmpty); | |
| 576 _workList.clear(); | |
| 577 if (currentNode == null) { | |
| 578 _findLeftMostDescendent(_tree._root); | |
| 579 } else { | |
| 580 _tree._splay(currentNode.key); | |
| 581 _findLeftMostDescendent(_tree._root.right); | |
| 582 assert(!_workList.isEmpty); | |
| 583 } | |
| 584 } | |
| 585 | |
| 586 bool moveNext() { | |
| 587 if (_modificationCount != _tree._modificationCount) { | |
| 588 throw new ConcurrentModificationError(_tree); | |
| 589 } | |
| 590 // Picks the next element in the worklist as current. | |
| 591 // Updates the worklist with the left-most path of the current node's | |
| 592 // right-hand child. | |
| 593 // If the worklist is no longer valid (after a splay), it is rebuild | |
| 594 // from scratch. | |
| 595 if (_workList.isEmpty) { | |
| 596 _currentNode = null; | |
| 597 return false; | |
| 598 } | |
| 599 if (_tree._splayCount != _splayCount && _currentNode != null) { | |
| 600 _rebuildWorkList(_currentNode); | |
| 601 } | |
| 602 _currentNode = _workList.removeLast(); | |
| 603 _findLeftMostDescendent(_currentNode.right); | |
| 604 return true; | |
| 605 } | |
| 606 | |
| 607 T _getValue(_SplayTreeNode<K> node); | |
| 608 } | |
| 609 | |
| 610 class _SplayTreeKeyIterable<K> extends Iterable<K> | |
| 611 implements EfficientLength { | |
| 612 _SplayTree<K, _SplayTreeNode<K>> _tree; | |
| 613 _SplayTreeKeyIterable(this._tree); | |
| 614 int get length => _tree._count; | |
| 615 bool get isEmpty => _tree._count == 0; | |
| 616 Iterator<K> get iterator => new _SplayTreeKeyIterator<K>(_tree); | |
| 617 | |
| 618 Set<K> toSet() { | |
| 619 SplayTreeSet<K> set = | |
| 620 new SplayTreeSet<K>(_tree._comparator, _tree._validKey); | |
| 621 set._count = _tree._count; | |
| 622 set._root = set._copyNode(_tree._root); | |
| 623 return set; | |
| 624 } | |
| 625 } | |
| 626 | |
| 627 class _SplayTreeValueIterable<K, V> extends Iterable<V> | |
| 628 implements EfficientLength { | |
| 629 SplayTreeMap<K, V> _map; | |
| 630 _SplayTreeValueIterable(this._map); | |
| 631 int get length => _map._count; | |
| 632 bool get isEmpty => _map._count == 0; | |
| 633 Iterator<V> get iterator => new _SplayTreeValueIterator<K, V>(_map); | |
| 634 } | |
| 635 | |
| 636 class _SplayTreeKeyIterator<K> extends _SplayTreeIterator<K, K> { | |
| 637 _SplayTreeKeyIterator(_SplayTree<K, _SplayTreeNode<K>> map): super(map); | |
| 638 K _getValue(_SplayTreeNode<K> node) => node.key; | |
| 639 } | |
| 640 | |
| 641 class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<K, V> { | |
| 642 _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map); | |
| 643 V _getValue(_SplayTreeNode<K> node) { | |
| 644 _SplayTreeMapNode<K, V> mapNode = | |
| 645 node as dynamic/*=_SplayTreeMapNode<K, V>*/; | |
| 646 return mapNode.value; | |
| 647 } | |
| 648 } | |
| 649 | |
| 650 class _SplayTreeNodeIterator<K> | |
| 651 extends _SplayTreeIterator<K, _SplayTreeNode<K>> { | |
| 652 _SplayTreeNodeIterator(_SplayTree<K, _SplayTreeNode<K>> tree): super(tree); | |
| 653 _SplayTreeNodeIterator.startAt( | |
| 654 _SplayTree<K, _SplayTreeNode<K>> tree, K startKey) | |
| 655 : super.startAt(tree, startKey); | |
| 656 _SplayTreeNode<K> _getValue(_SplayTreeNode<K> node) => node; | |
| 657 } | |
| 658 | |
| 659 | |
| 660 /** | |
| 661 * A [Set] of objects that can be ordered relative to each other. | |
| 662 * | |
| 663 * The set is based on a self-balancing binary tree. It allows most operations | |
| 664 * in amortized logarithmic time. | |
| 665 * | |
| 666 * Elements of the set are compared using the `compare` function passed in | |
| 667 * the constructor, both for ordering and for equality. | |
| 668 * If the set contains only an object `a`, then `set.contains(b)` | |
| 669 * will return `true` if and only if `compare(a, b) == 0`, | |
| 670 * and the value of `a == b` is not even checked. | |
| 671 * If the compare function is omitted, the objects are assumed to be | |
| 672 * [Comparable], and are compared using their [Comparable.compareTo] method. | |
| 673 * Non-comparable objects (including `null`) will not work as an element | |
| 674 * in that case. | |
| 675 */ | |
| 676 class SplayTreeSet<E> extends _SplayTree<E, _SplayTreeNode<E>> | |
| 677 with IterableMixin<E>, SetMixin<E> { | |
| 678 _SplayTreeNode<E> _root; | |
| 679 final _SplayTreeNode<E> _dummy = new _SplayTreeNode<E>(null); | |
| 680 | |
| 681 Comparator<E> _comparator; | |
| 682 _Predicate _validKey; | |
| 683 | |
| 684 /** | |
| 685 * Create a new [SplayTreeSet] with the given compare function. | |
| 686 * | |
| 687 * If the [compare] function is omitted, it defaults to [Comparable.compare], | |
| 688 * and the elements must be comparable. | |
| 689 * | |
| 690 * A provided `compare` function may not work on all objects. It may not even | |
| 691 * work on all `E` instances. | |
| 692 * | |
| 693 * For operations that add elements to the set, the user is supposed to not | |
| 694 * pass in objects that doesn't work with the compare function. | |
| 695 * | |
| 696 * The methods [contains], [remove], [lookup], [removeAll] or [retainAll] | |
| 697 * are typed to accept any object(s), and the [isValidKey] test can used to | |
| 698 * filter those objects before handing them to the `compare` function. | |
| 699 * | |
| 700 * If [isValidKey] is provided, only values satisfying `isValidKey(other)` | |
| 701 * are compared using the `compare` method in the methods mentioned above. | |
| 702 * If the `isValidKey` function returns false for an object, it is assumed to | |
| 703 * not be in the set. | |
| 704 * | |
| 705 * If omitted, the `isValidKey` function defaults to checking against the | |
| 706 * type parameter: `other is E`. | |
| 707 */ | |
| 708 SplayTreeSet([int compare(E key1, E key2), bool isValidKey(potentialKey)]) | |
| 709 : _comparator = | |
| 710 compare ?? Comparable.compare as dynamic/*=Comparator<E>*/, | |
| 711 _validKey = isValidKey ?? ((v) => v is E); | |
| 712 | |
| 713 /** | |
| 714 * Creates a [SplayTreeSet] that contains all [elements]. | |
| 715 * | |
| 716 * The set works as if created by `new SplayTreeSet<E>(compare, isValidKey)`. | |
| 717 * | |
| 718 * All the [elements] should be valid as arguments to the [compare] function. | |
| 719 */ | |
| 720 factory SplayTreeSet.from(Iterable elements, | |
| 721 [int compare(E key1, E key2), | |
| 722 bool isValidKey(potentialKey)]) { | |
| 723 SplayTreeSet<E> result = new SplayTreeSet<E>(compare, isValidKey); | |
| 724 for (final element in elements) { | |
| 725 E e = element as Object/*=E*/; | |
| 726 result.add(e); | |
| 727 } | |
| 728 return result; | |
| 729 } | |
| 730 | |
| 731 int _compare(E e1, E e2) => _comparator(e1, e2); | |
| 732 | |
| 733 // From Iterable. | |
| 734 | |
| 735 Iterator<E> get iterator => new _SplayTreeKeyIterator<E>(this); | |
| 736 | |
| 737 int get length => _count; | |
| 738 bool get isEmpty => _root == null; | |
| 739 bool get isNotEmpty => _root != null; | |
| 740 | |
| 741 E get first { | |
| 742 if (_count == 0) throw IterableElementError.noElement(); | |
| 743 return _first.key; | |
| 744 } | |
| 745 | |
| 746 E get last { | |
| 747 if (_count == 0) throw IterableElementError.noElement(); | |
| 748 return _last.key; | |
| 749 } | |
| 750 | |
| 751 E get single { | |
| 752 if (_count == 0) throw IterableElementError.noElement(); | |
| 753 if (_count > 1) throw IterableElementError.tooMany(); | |
| 754 return _root.key; | |
| 755 } | |
| 756 | |
| 757 // From Set. | |
| 758 bool contains(Object object) { | |
| 759 return _validKey(object) && _splay(object as dynamic/*=E*/) == 0; | |
| 760 } | |
| 761 | |
| 762 bool add(E element) { | |
| 763 int compare = _splay(element); | |
| 764 if (compare == 0) return false; | |
| 765 _addNewRoot(new _SplayTreeNode(element), compare); | |
| 766 return true; | |
| 767 } | |
| 768 | |
| 769 bool remove(Object object) { | |
| 770 if (!_validKey(object)) return false; | |
| 771 return _remove(object as dynamic/*=E*/) != null; | |
| 772 } | |
| 773 | |
| 774 void addAll(Iterable<E> elements) { | |
| 775 for (E element in elements) { | |
| 776 int compare = _splay(element); | |
| 777 if (compare != 0) { | |
| 778 _addNewRoot(new _SplayTreeNode(element), compare); | |
| 779 } | |
| 780 } | |
| 781 } | |
| 782 | |
| 783 void removeAll(Iterable<Object> elements) { | |
| 784 for (Object element in elements) { | |
| 785 if (_validKey(element)) _remove(element as dynamic/*=E*/); | |
| 786 } | |
| 787 } | |
| 788 | |
| 789 void retainAll(Iterable<Object> elements) { | |
| 790 // Build a set with the same sense of equality as this set. | |
| 791 SplayTreeSet<E> retainSet = new SplayTreeSet<E>(_comparator, _validKey); | |
| 792 int modificationCount = _modificationCount; | |
| 793 for (Object object in elements) { | |
| 794 if (modificationCount != _modificationCount) { | |
| 795 // The iterator should not have side effects. | |
| 796 throw new ConcurrentModificationError(this); | |
| 797 } | |
| 798 // Equivalent to this.contains(object). | |
| 799 if (_validKey(object) && _splay(object as dynamic/*=E*/) == 0) { | |
| 800 retainSet.add(_root.key); | |
| 801 } | |
| 802 } | |
| 803 // Take over the elements from the retained set, if it differs. | |
| 804 if (retainSet._count != _count) { | |
| 805 _root = retainSet._root; | |
| 806 _count = retainSet._count; | |
| 807 _modificationCount++; | |
| 808 } | |
| 809 } | |
| 810 | |
| 811 E lookup(Object object) { | |
| 812 if (!_validKey(object)) return null; | |
| 813 int comp = _splay(object as dynamic/*=E*/); | |
| 814 if (comp != 0) return null; | |
| 815 return _root.key; | |
| 816 } | |
| 817 | |
| 818 Set<E> intersection(Set<Object> other) { | |
| 819 Set<E> result = new SplayTreeSet<E>(_comparator, _validKey); | |
| 820 for (E element in this) { | |
| 821 if (other.contains(element)) result.add(element); | |
| 822 } | |
| 823 return result; | |
| 824 } | |
| 825 | |
| 826 Set<E> difference(Set<Object> other) { | |
| 827 Set<E> result = new SplayTreeSet<E>(_comparator, _validKey); | |
| 828 for (E element in this) { | |
| 829 if (!other.contains(element)) result.add(element); | |
| 830 } | |
| 831 return result; | |
| 832 } | |
| 833 | |
| 834 Set<E> union(Set<E> other) { | |
| 835 return _clone()..addAll(other); | |
| 836 } | |
| 837 | |
| 838 SplayTreeSet<E> _clone() { | |
| 839 var set = new SplayTreeSet<E>(_comparator, _validKey); | |
| 840 set._count = _count; | |
| 841 set._root = _copyNode(_root); | |
| 842 return set; | |
| 843 } | |
| 844 | |
| 845 // Copies the structure of a SplayTree into a new similar structure. | |
| 846 // Works on _SplayTreeMapNode as well, but only copies the keys, | |
| 847 _SplayTreeNode<E> _copyNode(_SplayTreeNode<E> node) { | |
| 848 if (node == null) return null; | |
| 849 return new _SplayTreeNode<E>(node.key)..left = _copyNode(node.left) | |
| 850 ..right = _copyNode(node.right); | |
| 851 } | |
| 852 | |
| 853 void clear() { _clear(); } | |
| 854 | |
| 855 Set<E> toSet() => _clone(); | |
| 856 | |
| 857 String toString() => IterableBase.iterableToFullString(this, '{', '}'); | |
| 858 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2698353003:
unfork DDC's copy of most SDK libraries (Closed)
