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