Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(28)

Side by Side Diff: sdk/lib/collection/splay_tree.dart

Issue 14048002: Make the analyzer happy about collections. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Reupload. Created 7 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « sdk/lib/collection/list.dart ('k') | sdk/lib/core/list.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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 }
OLDNEW
« no previous file with comments | « sdk/lib/collection/list.dart ('k') | sdk/lib/core/list.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698