| 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 /** | 7 /** |
| 8 * A node in a splay tree. It holds the sorting key and the left | 8 * A node in a splay tree. It holds the sorting key and the left |
| 9 * and right children in the tree. | 9 * and right children in the tree. |
| 10 */ | 10 */ |
| (...skipping 68 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 79 | 79 |
| 80 // The right child of the dummy node will hold | 80 // The right child of the dummy node will hold |
| 81 // the L tree of the algorithm. The left child of the dummy node | 81 // the L tree of the algorithm. The left child of the dummy node |
| 82 // will hold the R tree of the algorithm. Using a dummy node, left | 82 // will hold the R tree of the algorithm. Using a dummy node, left |
| 83 // and right will always be nodes and we avoid special cases. | 83 // and right will always be nodes and we avoid special cases. |
| 84 _SplayTreeNode<K> left = _dummy; | 84 _SplayTreeNode<K> left = _dummy; |
| 85 _SplayTreeNode<K> right = _dummy; | 85 _SplayTreeNode<K> right = _dummy; |
| 86 _SplayTreeNode<K> current = _root; | 86 _SplayTreeNode<K> current = _root; |
| 87 int comp; | 87 int comp; |
| 88 while (true) { | 88 while (true) { |
| 89 comp = current.key.compareTo(key); | 89 comp = _compare(current.key, key); |
| 90 if (comp > 0) { | 90 if (comp > 0) { |
| 91 if (current.left == null) break; | 91 if (current.left == null) break; |
| 92 comp = current.left.key.compareTo(key); | 92 comp = _compare(current.left.key, key); |
| 93 if (comp > 0) { | 93 if (comp > 0) { |
| 94 // Rotate right. | 94 // Rotate right. |
| 95 _SplayTreeNode<K> tmp = current.left; | 95 _SplayTreeNode<K> tmp = current.left; |
| 96 current.left = tmp.right; | 96 current.left = tmp.right; |
| 97 tmp.right = current; | 97 tmp.right = current; |
| 98 current = tmp; | 98 current = tmp; |
| 99 if (current.left == null) break; | 99 if (current.left == null) break; |
| 100 } | 100 } |
| 101 // Link right. | 101 // Link right. |
| 102 right.left = current; | 102 right.left = current; |
| 103 right = current; | 103 right = current; |
| 104 current = current.left; | 104 current = current.left; |
| 105 } else if (comp < 0) { | 105 } else if (comp < 0) { |
| 106 if (current.right == null) break; | 106 if (current.right == null) break; |
| 107 comp = current.right.key.compareTo(key); | 107 comp = _compare(current.right.key, key); |
| 108 if (comp < 0) { | 108 if (comp < 0) { |
| 109 // Rotate left. | 109 // Rotate left. |
| 110 _SplayTreeNode<K> tmp = current.right; | 110 _SplayTreeNode<K> tmp = current.right; |
| 111 current.right = tmp.left; | 111 current.right = tmp.left; |
| 112 tmp.left = current; | 112 tmp.left = current; |
| 113 current = tmp; | 113 current = tmp; |
| 114 if (current.right == null) break; | 114 if (current.right == null) break; |
| 115 } | 115 } |
| 116 // Link left. | 116 // Link left. |
| 117 left.right = current; | 117 left.right = current; |
| (...skipping 131 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 249 : _comparator = (compare == null) ? Comparable.compare : compare; | 249 : _comparator = (compare == null) ? Comparable.compare : compare; |
| 250 | 250 |
| 251 int _compare(K key1, K key2) => _comparator(key1, key2); | 251 int _compare(K key1, K key2) => _comparator(key1, key2); |
| 252 | 252 |
| 253 SplayTreeMap._internal(); | 253 SplayTreeMap._internal(); |
| 254 | 254 |
| 255 V operator [](K key) { | 255 V operator [](K key) { |
| 256 if (key == null) throw new ArgumentError(key); | 256 if (key == null) throw new ArgumentError(key); |
| 257 if (_root != null) { | 257 if (_root != null) { |
| 258 int comp = _splay(key); | 258 int comp = _splay(key); |
| 259 if (comp == 0) return _root.value; | 259 if (comp == 0) { |
| 260 _SplayTreeMapNode mapRoot = _root; |
| 261 return mapRoot.value; |
| 262 } |
| 260 } | 263 } |
| 261 return null; | 264 return null; |
| 262 } | 265 } |
| 263 | 266 |
| 264 V remove(Object key) { | 267 V remove(Object key) { |
| 265 if (key is! K) return null; | 268 if (key is! K) return null; |
| 266 _SplayTreeMapNode root = _remove(key); | 269 _SplayTreeMapNode mapRoot = _remove(key); |
| 267 if (root != null) return root.value; | 270 if (mapRoot != null) return mapRoot.value; |
| 268 return null; | 271 return null; |
| 269 } | 272 } |
| 270 | 273 |
| 271 void operator []=(K key, V value) { | 274 void operator []=(K key, V value) { |
| 272 if (key == null) throw new ArgumentError(key); | 275 if (key == null) throw new ArgumentError(key); |
| 273 // Splay on the key to move the last node on the search path for | 276 // Splay on the key to move the last node on the search path for |
| 274 // the key to the root of the tree. | 277 // the key to the root of the tree. |
| 275 int comp = _splay(key); | 278 int comp = _splay(key); |
| 276 if (comp == 0) { | 279 if (comp == 0) { |
| 277 _root.value = value; | 280 _SplayTreeMapNode mapRoot = _root; |
| 281 mapRoot.value = value; |
| 278 return; | 282 return; |
| 279 } | 283 } |
| 280 _addNewRoot(new _SplayTreeMapNode(key, value), comp); | 284 _addNewRoot(new _SplayTreeMapNode(key, value), comp); |
| 281 } | 285 } |
| 282 | 286 |
| 283 | 287 |
| 284 V putIfAbsent(K key, V ifAbsent()) { | 288 V putIfAbsent(K key, V ifAbsent()) { |
| 285 if (key == null) throw new ArgumentError(key); | 289 if (key == null) throw new ArgumentError(key); |
| 286 int comp = _splay(key); | 290 int comp = _splay(key); |
| 287 if (comp == 0) return _root.value; | 291 if (comp == 0) { |
| 292 _SplayTreeMapNode mapRoot = _root; |
| 293 return mapRoot.value; |
| 294 } |
| 288 int modificationCount = _modificationCount; | 295 int modificationCount = _modificationCount; |
| 289 int splayCount = _splayCount; | 296 int splayCount = _splayCount; |
| 290 V value = ifAbsent(); | 297 V value = ifAbsent(); |
| 291 if (modificationCount != _modificationCount) { | 298 if (modificationCount != _modificationCount) { |
| 292 throw new ConcurrentModificationError(this); | 299 throw new ConcurrentModificationError(this); |
| 293 } | 300 } |
| 294 if (splayCount != _splayCount) { | 301 if (splayCount != _splayCount) { |
| 295 comp = _splay(key); | 302 comp = _splay(key); |
| 296 // Key is still not there, otherwise _modificationCount would be changed. | 303 // Key is still not there, otherwise _modificationCount would be changed. |
| 297 assert(comp != 0); | 304 assert(comp != 0); |
| (...skipping 25 matching lines...) Expand all Loading... |
| 323 _clear(); | 330 _clear(); |
| 324 } | 331 } |
| 325 | 332 |
| 326 bool containsKey(K key) { | 333 bool containsKey(K key) { |
| 327 return _splay(key) == 0; | 334 return _splay(key) == 0; |
| 328 } | 335 } |
| 329 | 336 |
| 330 bool containsValue(V value) { | 337 bool containsValue(V value) { |
| 331 bool found = false; | 338 bool found = false; |
| 332 int initialSplayCount = _splayCount; | 339 int initialSplayCount = _splayCount; |
| 333 bool visit(_SplayTreeNode node) { | 340 bool visit(_SplayTreeMapNode node) { |
| 334 while (node != null) { | 341 while (node != null) { |
| 335 if (node.value == value) return true; | 342 if (node.value == value) return true; |
| 336 if (initialSplayCount != _splayCount) { | 343 if (initialSplayCount != _splayCount) { |
| 337 throw new ConcurrentModificationError(this); | 344 throw new ConcurrentModificationError(this); |
| 338 } | 345 } |
| 339 if (node.right != null && visit(node.right)) return true; | 346 if (node.right != null && visit(node.right)) return true; |
| 340 node = node.left; | 347 node = node.left; |
| 341 } | 348 } |
| 342 return false; | 349 return false; |
| 343 } | 350 } |
| (...skipping 178 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 522 class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<V> { | 529 class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<V> { |
| 523 _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map); | 530 _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map); |
| 524 V _getValue(_SplayTreeMapNode node) => node.value; | 531 V _getValue(_SplayTreeMapNode node) => node.value; |
| 525 } | 532 } |
| 526 | 533 |
| 527 class _SplayTreeNodeIterator<K> | 534 class _SplayTreeNodeIterator<K> |
| 528 extends _SplayTreeIterator<_SplayTreeNode<K>> { | 535 extends _SplayTreeIterator<_SplayTreeNode<K>> { |
| 529 _SplayTreeNodeIterator(_SplayTree<K> map): super(map); | 536 _SplayTreeNodeIterator(_SplayTree<K> map): super(map); |
| 530 _SplayTreeNode<K> _getValue(_SplayTreeNode node) => node; | 537 _SplayTreeNode<K> _getValue(_SplayTreeNode node) => node; |
| 531 } | 538 } |
| OLD | NEW |