OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, 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 import 'dart:typed_data'; | 5 import 'dart:typed_data'; |
6 import 'dart:_internal' as internal; | 6 import 'dart:_internal' as internal; |
7 | 7 |
8 @patch | 8 @patch class HashMap<K, V> { |
9 class HashMap<K, V> { | 9 @patch factory HashMap({ bool equals(K key1, K key2), |
10 @patch | 10 int hashCode(K key), |
11 factory HashMap( | 11 bool isValidKey(potentialKey) }) { |
12 {bool equals(K key1, K key2), | |
13 int hashCode(K key), | |
14 bool isValidKey(potentialKey)}) { | |
15 if (isValidKey == null) { | 12 if (isValidKey == null) { |
16 if (hashCode == null) { | 13 if (hashCode == null) { |
17 if (equals == null) { | 14 if (equals == null) { |
18 return new _HashMap<K, V>(); | 15 return new _HashMap<K, V>(); |
19 } | 16 } |
20 hashCode = _defaultHashCode; | 17 hashCode = _defaultHashCode; |
21 } else { | 18 } else { |
22 if (identical(identityHashCode, hashCode) && | 19 if (identical(identityHashCode, hashCode) && |
23 identical(identical, equals)) { | 20 identical(identical, equals)) { |
24 return new _IdentityHashMap<K, V>(); | 21 return new _IdentityHashMap<K, V>(); |
25 } | 22 } |
26 if (equals == null) { | 23 if (equals == null) { |
27 equals = _defaultEquals; | 24 equals = _defaultEquals; |
28 } | 25 } |
29 } | 26 } |
30 } else { | 27 } else { |
31 if (hashCode == null) { | 28 if (hashCode == null) { |
32 hashCode = _defaultHashCode; | 29 hashCode = _defaultHashCode; |
33 } | 30 } |
34 if (equals == null) { | 31 if (equals == null) { |
35 equals = _defaultEquals; | 32 equals = _defaultEquals; |
36 } | 33 } |
37 } | 34 } |
38 return new _CustomHashMap<K, V>(equals, hashCode, isValidKey); | 35 return new _CustomHashMap<K, V>(equals, hashCode, isValidKey); |
39 } | 36 } |
40 | 37 |
41 @patch | 38 @patch factory HashMap.identity() = _IdentityHashMap<K, V>; |
42 factory HashMap.identity() = _IdentityHashMap<K, V>; | |
43 | 39 |
44 Set<K> _newKeySet(); | 40 Set<K> _newKeySet(); |
45 } | 41 } |
46 | 42 |
| 43 |
47 const int _MODIFICATION_COUNT_MASK = 0x3fffffff; | 44 const int _MODIFICATION_COUNT_MASK = 0x3fffffff; |
48 | 45 |
49 class _HashMap<K, V> implements HashMap<K, V> { | 46 class _HashMap<K, V> implements HashMap<K, V> { |
50 static const int _INITIAL_CAPACITY = 8; | 47 static const int _INITIAL_CAPACITY = 8; |
51 | 48 |
| 49 |
52 int _elementCount = 0; | 50 int _elementCount = 0; |
53 List<_HashMapEntry> _buckets = new List(_INITIAL_CAPACITY); | 51 List<_HashMapEntry> _buckets = new List(_INITIAL_CAPACITY); |
54 int _modificationCount = 0; | 52 int _modificationCount = 0; |
55 | 53 |
56 int get length => _elementCount; | 54 int get length => _elementCount; |
57 bool get isEmpty => _elementCount == 0; | 55 bool get isEmpty => _elementCount == 0; |
58 bool get isNotEmpty => _elementCount != 0; | 56 bool get isNotEmpty => _elementCount != 0; |
59 | 57 |
60 Iterable<K> get keys => new _HashMapKeyIterable<K>(this); | 58 Iterable<K> get keys => new _HashMapKeyIterable<K>(this); |
61 Iterable<V> get values => new _HashMapValueIterable<V>(this); | 59 Iterable<V> get values => new _HashMapValueIterable<V>(this); |
(...skipping 16 matching lines...) Expand all Loading... |
78 for (int i = 0; i < length; i++) { | 76 for (int i = 0; i < length; i++) { |
79 _HashMapEntry entry = buckets[i]; | 77 _HashMapEntry entry = buckets[i]; |
80 while (entry != null) { | 78 while (entry != null) { |
81 if (entry.value == value) return true; | 79 if (entry.value == value) return true; |
82 entry = entry.next; | 80 entry = entry.next; |
83 } | 81 } |
84 } | 82 } |
85 return false; | 83 return false; |
86 } | 84 } |
87 | 85 |
88 V operator [](Object key) { | 86 V operator[](Object key) { |
89 int hashCode = key.hashCode; | 87 int hashCode = key.hashCode; |
90 List buckets = _buckets; | 88 List buckets = _buckets; |
91 int index = hashCode & (buckets.length - 1); | 89 int index = hashCode & (buckets.length - 1); |
92 _HashMapEntry entry = buckets[index]; | 90 _HashMapEntry entry = buckets[index]; |
93 while (entry != null) { | 91 while (entry != null) { |
94 if (hashCode == entry.hashCode && entry.key == key) { | 92 if (hashCode == entry.hashCode && entry.key == key) { |
95 return entry.value; | 93 return entry.value; |
96 } | 94 } |
97 entry = entry.next; | 95 entry = entry.next; |
98 } | 96 } |
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
181 } | 179 } |
182 | 180 |
183 void clear() { | 181 void clear() { |
184 _buckets = new List(_INITIAL_CAPACITY); | 182 _buckets = new List(_INITIAL_CAPACITY); |
185 if (_elementCount > 0) { | 183 if (_elementCount > 0) { |
186 _elementCount = 0; | 184 _elementCount = 0; |
187 _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK; | 185 _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK; |
188 } | 186 } |
189 } | 187 } |
190 | 188 |
191 void _removeEntry( | 189 void _removeEntry(_HashMapEntry entry, |
192 _HashMapEntry entry, _HashMapEntry previousInBucket, int bucketIndex) { | 190 _HashMapEntry previousInBucket, |
| 191 int bucketIndex) { |
193 if (previousInBucket == null) { | 192 if (previousInBucket == null) { |
194 _buckets[bucketIndex] = entry.next; | 193 _buckets[bucketIndex] = entry.next; |
195 } else { | 194 } else { |
196 previousInBucket.next = entry.next; | 195 previousInBucket.next = entry.next; |
197 } | 196 } |
198 } | 197 } |
199 | 198 |
200 void _addEntry( | 199 void _addEntry(List buckets, int index, int length, |
201 List buckets, int index, int length, K key, V value, int hashCode) { | 200 K key, V value, int hashCode) { |
202 _HashMapEntry entry = | 201 _HashMapEntry entry = |
203 new _HashMapEntry(key, value, hashCode, buckets[index]); | 202 new _HashMapEntry(key, value, hashCode, buckets[index]); |
204 buckets[index] = entry; | 203 buckets[index] = entry; |
205 int newElements = _elementCount + 1; | 204 int newElements = _elementCount + 1; |
206 _elementCount = newElements; | 205 _elementCount = newElements; |
207 // If we end up with more than 75% non-empty entries, we | 206 // If we end up with more than 75% non-empty entries, we |
208 // resize the backing store. | 207 // resize the backing store. |
209 if ((newElements << 2) > ((length << 1) + length)) _resize(); | 208 if ((newElements << 2) > ((length << 1) + length)) _resize(); |
210 _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK; | 209 _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK; |
211 } | 210 } |
(...skipping 22 matching lines...) Expand all Loading... |
234 Set<K> _newKeySet() => new _HashSet<K>(); | 233 Set<K> _newKeySet() => new _HashSet<K>(); |
235 } | 234 } |
236 | 235 |
237 class _CustomHashMap<K, V> extends _HashMap<K, V> { | 236 class _CustomHashMap<K, V> extends _HashMap<K, V> { |
238 final _Equality<K> _equals; | 237 final _Equality<K> _equals; |
239 final _Hasher<K> _hashCode; | 238 final _Hasher<K> _hashCode; |
240 final _Predicate _validKey; | 239 final _Predicate _validKey; |
241 _CustomHashMap(this._equals, this._hashCode, validKey) | 240 _CustomHashMap(this._equals, this._hashCode, validKey) |
242 : _validKey = (validKey != null) ? validKey : new _TypeTest<K>().test; | 241 : _validKey = (validKey != null) ? validKey : new _TypeTest<K>().test; |
243 | 242 |
| 243 |
244 bool containsKey(Object key) { | 244 bool containsKey(Object key) { |
245 if (!_validKey(key)) return false; | 245 if (!_validKey(key)) return false; |
246 int hashCode = _hashCode(key); | 246 int hashCode = _hashCode(key); |
247 List buckets = _buckets; | 247 List buckets = _buckets; |
248 int index = hashCode & (buckets.length - 1); | 248 int index = hashCode & (buckets.length - 1); |
249 _HashMapEntry entry = buckets[index]; | 249 _HashMapEntry entry = buckets[index]; |
250 while (entry != null) { | 250 while (entry != null) { |
251 if (hashCode == entry.hashCode && _equals(entry.key, key)) return true; | 251 if (hashCode == entry.hashCode && _equals(entry.key, key)) return true; |
252 entry = entry.next; | 252 entry = entry.next; |
253 } | 253 } |
254 return false; | 254 return false; |
255 } | 255 } |
256 | 256 |
257 V operator [](Object key) { | 257 V operator[](Object key) { |
258 if (!_validKey(key)) return null; | 258 if (!_validKey(key)) return null; |
259 int hashCode = _hashCode(key); | 259 int hashCode = _hashCode(key); |
260 List buckets = _buckets; | 260 List buckets = _buckets; |
261 int index = hashCode & (buckets.length - 1); | 261 int index = hashCode & (buckets.length - 1); |
262 _HashMapEntry entry = buckets[index]; | 262 _HashMapEntry entry = buckets[index]; |
263 while (entry != null) { | 263 while (entry != null) { |
264 if (hashCode == entry.hashCode && _equals(entry.key, key)) { | 264 if (hashCode == entry.hashCode && _equals(entry.key, key)) { |
265 return entry.value; | 265 return entry.value; |
266 } | 266 } |
267 entry = entry.next; | 267 entry = entry.next; |
(...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
328 } | 328 } |
329 return null; | 329 return null; |
330 } | 330 } |
331 | 331 |
332 String toString() => Maps.mapToString(this); | 332 String toString() => Maps.mapToString(this); |
333 | 333 |
334 Set<K> _newKeySet() => new _CustomHashSet<K>(_equals, _hashCode, _validKey); | 334 Set<K> _newKeySet() => new _CustomHashSet<K>(_equals, _hashCode, _validKey); |
335 } | 335 } |
336 | 336 |
337 class _IdentityHashMap<K, V> extends _HashMap<K, V> { | 337 class _IdentityHashMap<K, V> extends _HashMap<K, V> { |
| 338 |
338 bool containsKey(Object key) { | 339 bool containsKey(Object key) { |
339 int hashCode = identityHashCode(key); | 340 int hashCode = identityHashCode(key); |
340 List buckets = _buckets; | 341 List buckets = _buckets; |
341 int index = hashCode & (buckets.length - 1); | 342 int index = hashCode & (buckets.length - 1); |
342 _HashMapEntry entry = buckets[index]; | 343 _HashMapEntry entry = buckets[index]; |
343 while (entry != null) { | 344 while (entry != null) { |
344 if (hashCode == entry.hashCode && identical(entry.key, key)) return true; | 345 if (hashCode == entry.hashCode && identical(entry.key, key)) return true; |
345 entry = entry.next; | 346 entry = entry.next; |
346 } | 347 } |
347 return false; | 348 return false; |
348 } | 349 } |
349 | 350 |
350 V operator [](Object key) { | 351 V operator[](Object key) { |
351 int hashCode = identityHashCode(key); | 352 int hashCode = identityHashCode(key); |
352 List buckets = _buckets; | 353 List buckets = _buckets; |
353 int index = hashCode & (buckets.length - 1); | 354 int index = hashCode & (buckets.length - 1); |
354 _HashMapEntry entry = buckets[index]; | 355 _HashMapEntry entry = buckets[index]; |
355 while (entry != null) { | 356 while (entry != null) { |
356 if (hashCode == entry.hashCode && identical(entry.key, key)) { | 357 if (hashCode == entry.hashCode && identical(entry.key, key)) { |
357 return entry.value; | 358 return entry.value; |
358 } | 359 } |
359 entry = entry.next; | 360 entry = entry.next; |
360 } | 361 } |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
418 entry = next; | 419 entry = next; |
419 } | 420 } |
420 return null; | 421 return null; |
421 } | 422 } |
422 | 423 |
423 String toString() => Maps.mapToString(this); | 424 String toString() => Maps.mapToString(this); |
424 | 425 |
425 Set<K> _newKeySet() => new _IdentityHashSet<K>(); | 426 Set<K> _newKeySet() => new _IdentityHashSet<K>(); |
426 } | 427 } |
427 | 428 |
| 429 |
428 class _HashMapEntry { | 430 class _HashMapEntry { |
429 final key; | 431 final key; |
430 var value; | 432 var value; |
431 final int hashCode; | 433 final int hashCode; |
432 _HashMapEntry next; | 434 _HashMapEntry next; |
433 _HashMapEntry(this.key, this.value, this.hashCode, this.next); | 435 _HashMapEntry(this.key, this.value, this.hashCode, this.next); |
434 } | 436 } |
435 | 437 |
436 abstract class _HashMapIterable<E> extends EfficientLengthIterable<E> { | 438 abstract class _HashMapIterable<E> extends EfficientLengthIterable<E> { |
437 final HashMap _map; | 439 final HashMap _map; |
438 _HashMapIterable(this._map); | 440 _HashMapIterable(this._map); |
439 int get length => _map.length; | 441 int get length => _map.length; |
440 bool get isEmpty => _map.isEmpty; | 442 bool get isEmpty => _map.isEmpty; |
441 bool get isNotEmpty => _map.isNotEmpty; | 443 bool get isNotEmpty => _map.isNotEmpty; |
442 } | 444 } |
443 | 445 |
444 class _HashMapKeyIterable<K> extends _HashMapIterable<K> { | 446 class _HashMapKeyIterable<K> extends _HashMapIterable<K> { |
445 _HashMapKeyIterable(HashMap map) : super(map); | 447 _HashMapKeyIterable(HashMap map) : super(map); |
446 Iterator<K> get iterator => new _HashMapKeyIterator<K>(_map); | 448 Iterator<K> get iterator => new _HashMapKeyIterator<K>(_map); |
447 bool contains(Object key) => _map.containsKey(key); | 449 bool contains(Object key) => _map.containsKey(key); |
448 void forEach(void action(K key)) { | 450 void forEach(void action(K key)) { |
449 _map.forEach((K key, _) { | 451 _map.forEach((K key, _) { |
450 action(key); | 452 action(key); |
451 }); | 453 }); |
452 } | 454 } |
453 | |
454 Set<K> toSet() => _map._newKeySet()..addAll(this); | 455 Set<K> toSet() => _map._newKeySet()..addAll(this); |
455 } | 456 } |
456 | 457 |
457 class _HashMapValueIterable<V> extends _HashMapIterable<V> { | 458 class _HashMapValueIterable<V> extends _HashMapIterable<V> { |
458 _HashMapValueIterable(HashMap map) : super(map); | 459 _HashMapValueIterable(HashMap map) : super(map); |
459 Iterator<V> get iterator => new _HashMapValueIterator<V>(_map); | 460 Iterator<V> get iterator => new _HashMapValueIterator<V>(_map); |
460 bool contains(Object value) => _map.containsValue(value); | 461 bool contains(Object value) => _map.containsValue(value); |
461 void forEach(void action(V value)) { | 462 void forEach(void action(V value)) { |
462 _map.forEach((_, V value) { | 463 _map.forEach((_, V value) { |
463 action(value); | 464 action(value); |
464 }); | 465 }); |
465 } | 466 } |
466 } | 467 } |
467 | 468 |
468 abstract class _HashMapIterator<E> implements Iterator<E> { | 469 abstract class _HashMapIterator<E> implements Iterator<E> { |
469 final HashMap _map; | 470 final HashMap _map; |
470 final int _stamp; | 471 final int _stamp; |
471 | 472 |
472 int _index = 0; | 473 int _index = 0; |
473 _HashMapEntry _entry; | 474 _HashMapEntry _entry; |
474 | 475 |
475 _HashMapIterator(HashMap map) | 476 _HashMapIterator(HashMap map) |
476 : _map = map, | 477 : _map = map, _stamp = map._modificationCount; |
477 _stamp = map._modificationCount; | |
478 | 478 |
479 bool moveNext() { | 479 bool moveNext() { |
480 if (_stamp != _map._modificationCount) { | 480 if (_stamp != _map._modificationCount) { |
481 throw new ConcurrentModificationError(_map); | 481 throw new ConcurrentModificationError(_map); |
482 } | 482 } |
483 _HashMapEntry entry = _entry; | 483 _HashMapEntry entry = _entry; |
484 if (entry != null) { | 484 if (entry != null) { |
485 _HashMapEntry next = entry.next; | 485 _HashMapEntry next = entry.next; |
486 if (next != null) { | 486 if (next != null) { |
487 _entry = next; | 487 _entry = next; |
(...skipping 25 matching lines...) Expand all Loading... |
513 } | 513 } |
514 | 514 |
515 class _HashMapValueIterator<V> extends _HashMapIterator<V> { | 515 class _HashMapValueIterator<V> extends _HashMapIterator<V> { |
516 _HashMapValueIterator(HashMap map) : super(map); | 516 _HashMapValueIterator(HashMap map) : super(map); |
517 V get current { | 517 V get current { |
518 _HashMapEntry entry = _entry; | 518 _HashMapEntry entry = _entry; |
519 return (entry == null) ? null : entry.value; | 519 return (entry == null) ? null : entry.value; |
520 } | 520 } |
521 } | 521 } |
522 | 522 |
523 @patch | 523 @patch class HashSet<E> { |
524 class HashSet<E> { | 524 @patch factory HashSet({ bool equals(E e1, E e2), |
525 @patch | 525 int hashCode(E e), |
526 factory HashSet( | 526 bool isValidKey(potentialKey) }) { |
527 {bool equals(E e1, E e2), | |
528 int hashCode(E e), | |
529 bool isValidKey(potentialKey)}) { | |
530 if (isValidKey == null) { | 527 if (isValidKey == null) { |
531 if (hashCode == null) { | 528 if (hashCode == null) { |
532 if (equals == null) { | 529 if (equals == null) { |
533 return new _HashSet<E>(); | 530 return new _HashSet<E>(); |
534 } | 531 } |
535 hashCode = _defaultHashCode; | 532 hashCode = _defaultHashCode; |
536 } else { | 533 } else { |
537 if (identical(identityHashCode, hashCode) && | 534 if (identical(identityHashCode, hashCode) && |
538 identical(identical, equals)) { | 535 identical(identical, equals)) { |
539 return new _IdentityHashSet<E>(); | 536 return new _IdentityHashSet<E>(); |
540 } | 537 } |
541 if (equals == null) { | 538 if (equals == null) { |
542 equals = _defaultEquals; | 539 equals = _defaultEquals; |
543 } | 540 } |
544 } | 541 } |
545 } else { | 542 } else { |
546 if (hashCode == null) { | 543 if (hashCode == null) { |
547 hashCode = _defaultHashCode; | 544 hashCode = _defaultHashCode; |
548 } | 545 } |
549 if (equals == null) { | 546 if (equals == null) { |
550 equals = _defaultEquals; | 547 equals = _defaultEquals; |
551 } | 548 } |
552 } | 549 } |
553 return new _CustomHashSet<E>(equals, hashCode, isValidKey); | 550 return new _CustomHashSet<E>(equals, hashCode, isValidKey); |
554 } | 551 } |
555 | 552 |
556 @patch | 553 @patch factory HashSet.identity() = _IdentityHashSet<E>; |
557 factory HashSet.identity() = _IdentityHashSet<E>; | |
558 } | 554 } |
559 | 555 |
560 class _HashSet<E> extends _HashSetBase<E> implements HashSet<E> { | 556 class _HashSet<E> extends _HashSetBase<E> implements HashSet<E> { |
561 static const int _INITIAL_CAPACITY = 8; | 557 static const int _INITIAL_CAPACITY = 8; |
562 | 558 |
563 List<_HashSetEntry> _buckets = new List(_INITIAL_CAPACITY); | 559 List<_HashSetEntry> _buckets = new List(_INITIAL_CAPACITY); |
564 int _elementCount = 0; | 560 int _elementCount = 0; |
565 int _modificationCount = 0; | 561 int _modificationCount = 0; |
566 | 562 |
567 bool _equals(e1, e2) => e1 == e2; | 563 bool _equals(e1, e2) => e1 == e2; |
(...skipping 78 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
646 bool remove(Object object) => _remove(object, _hashCode(object)); | 642 bool remove(Object object) => _remove(object, _hashCode(object)); |
647 | 643 |
648 void removeAll(Iterable<Object> objectsToRemove) { | 644 void removeAll(Iterable<Object> objectsToRemove) { |
649 for (Object object in objectsToRemove) { | 645 for (Object object in objectsToRemove) { |
650 _remove(object, _hashCode(object)); | 646 _remove(object, _hashCode(object)); |
651 } | 647 } |
652 } | 648 } |
653 | 649 |
654 void _filterWhere(bool test(E element), bool removeMatching) { | 650 void _filterWhere(bool test(E element), bool removeMatching) { |
655 int length = _buckets.length; | 651 int length = _buckets.length; |
656 for (int index = 0; index < length; index++) { | 652 for (int index = 0; index < length; index++) { |
657 _HashSetEntry entry = _buckets[index]; | 653 _HashSetEntry entry = _buckets[index]; |
658 _HashSetEntry previous = null; | 654 _HashSetEntry previous = null; |
659 while (entry != null) { | 655 while (entry != null) { |
660 int modificationCount = _modificationCount; | 656 int modificationCount = _modificationCount; |
661 bool testResult = test(entry.key); | 657 bool testResult = test(entry.key); |
662 if (modificationCount != _modificationCount) { | 658 if (modificationCount != _modificationCount) { |
663 throw new ConcurrentModificationError(this); | 659 throw new ConcurrentModificationError(this); |
664 } | 660 } |
665 if (testResult == removeMatching) { | 661 if (testResult == removeMatching) { |
666 _HashSetEntry next = entry.remove(); | 662 _HashSetEntry next = entry.remove(); |
(...skipping 125 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
792 } | 788 } |
793 | 789 |
794 class _HashSetIterator<E> implements Iterator<E> { | 790 class _HashSetIterator<E> implements Iterator<E> { |
795 final _HashSet _set; | 791 final _HashSet _set; |
796 final int _modificationCount; | 792 final int _modificationCount; |
797 int _index = 0; | 793 int _index = 0; |
798 _HashSetEntry _next; | 794 _HashSetEntry _next; |
799 E _current; | 795 E _current; |
800 | 796 |
801 _HashSetIterator(_HashSet hashSet) | 797 _HashSetIterator(_HashSet hashSet) |
802 : _set = hashSet, | 798 : _set = hashSet, _modificationCount = hashSet._modificationCount; |
803 _modificationCount = hashSet._modificationCount; | |
804 | 799 |
805 bool moveNext() { | 800 bool moveNext() { |
806 if (_modificationCount != _set._modificationCount) { | 801 if (_modificationCount != _set._modificationCount) { |
807 throw new ConcurrentModificationError(_set); | 802 throw new ConcurrentModificationError(_set); |
808 } | 803 } |
809 if (_next != null) { | 804 if (_next != null) { |
810 _current = _next.key; | 805 _current = _next.key; |
811 _next = _next.next; | 806 _next = _next.next; |
812 return true; | 807 return true; |
813 } | 808 } |
(...skipping 14 matching lines...) Expand all Loading... |
828 E get current => _current; | 823 E get current => _current; |
829 } | 824 } |
830 | 825 |
831 class _LinkedHashMapEntry extends _HashMapEntry { | 826 class _LinkedHashMapEntry extends _HashMapEntry { |
832 /// Double-linked list of entries of a linked hash map. | 827 /// Double-linked list of entries of a linked hash map. |
833 /// The _LinkedHashMap itself is the head of the list, so the type is "var". | 828 /// The _LinkedHashMap itself is the head of the list, so the type is "var". |
834 /// Both are initialized to `this` when initialized. | 829 /// Both are initialized to `this` when initialized. |
835 var _nextEntry; | 830 var _nextEntry; |
836 var _previousEntry; | 831 var _previousEntry; |
837 _LinkedHashMapEntry(key, value, int hashCode, _LinkedHashMapEntry next, | 832 _LinkedHashMapEntry(key, value, int hashCode, _LinkedHashMapEntry next, |
838 this._previousEntry, this._nextEntry) | 833 this._previousEntry, this._nextEntry) |
839 : super(key, value, hashCode, next) { | 834 : super(key, value, hashCode, next) { |
840 _previousEntry._nextEntry = this; | 835 _previousEntry._nextEntry = this; |
841 _nextEntry._previousEntry = this; | 836 _nextEntry._previousEntry = this; |
842 } | 837 } |
843 } | 838 } |
844 | 839 |
845 class _LinkedHashMapKeyIterable<K> extends EfficientLengthIterable<K> { | 840 class _LinkedHashMapKeyIterable<K> extends EfficientLengthIterable<K> { |
846 LinkedHashMap<K, dynamic> _map; | 841 LinkedHashMap<K, dynamic> _map; |
847 _LinkedHashMapKeyIterable(this._map); | 842 _LinkedHashMapKeyIterable(this._map); |
848 Iterator<K> get iterator => new _LinkedHashMapKeyIterator<K>(_map); | 843 Iterator<K> get iterator => new _LinkedHashMapKeyIterator<K>(_map); |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
895 class _LinkedHashMapKeyIterator<K> extends _LinkedHashMapIterator<K> { | 890 class _LinkedHashMapKeyIterator<K> extends _LinkedHashMapIterator<K> { |
896 _LinkedHashMapKeyIterator(LinkedHashMap map) : super(map); | 891 _LinkedHashMapKeyIterator(LinkedHashMap map) : super(map); |
897 K _getValue(_LinkedHashMapEntry entry) => entry.key; | 892 K _getValue(_LinkedHashMapEntry entry) => entry.key; |
898 } | 893 } |
899 | 894 |
900 class _LinkedHashMapValueIterator<V> extends _LinkedHashMapIterator<V> { | 895 class _LinkedHashMapValueIterator<V> extends _LinkedHashMapIterator<V> { |
901 _LinkedHashMapValueIterator(LinkedHashMap map) : super(map); | 896 _LinkedHashMapValueIterator(LinkedHashMap map) : super(map); |
902 V _getValue(_LinkedHashMapEntry entry) => entry.value; | 897 V _getValue(_LinkedHashMapEntry entry) => entry.value; |
903 } | 898 } |
904 | 899 |
| 900 |
905 /** | 901 /** |
906 * A hash-based map that iterates keys and values in key insertion order. | 902 * A hash-based map that iterates keys and values in key insertion order. |
907 */ | 903 */ |
908 @patch | 904 @patch class LinkedHashMap<K, V> { |
909 class LinkedHashMap<K, V> { | |
910 /// Holds a double-linked list of entries in insertion order. | 905 /// Holds a double-linked list of entries in insertion order. |
911 /// The fields have the same name as the ones in [_LinkedHashMapEntry], | 906 /// The fields have the same name as the ones in [_LinkedHashMapEntry], |
912 /// and this map is itself used as the head entry of the list. | 907 /// and this map is itself used as the head entry of the list. |
913 /// Set to `this` when initialized, representing the empty list (containing | 908 /// Set to `this` when initialized, representing the empty list (containing |
914 /// only the head entry itself). | 909 /// only the head entry itself). |
915 var _nextEntry; | 910 var _nextEntry; |
916 var _previousEntry; | 911 var _previousEntry; |
917 | 912 |
918 @patch | 913 @patch factory LinkedHashMap({ bool equals(K key1, K key2), |
919 factory LinkedHashMap( | 914 int hashCode(K key), |
920 {bool equals(K key1, K key2), | 915 bool isValidKey(potentialKey) }) { |
921 int hashCode(K key), | |
922 bool isValidKey(potentialKey)}) { | |
923 if (isValidKey == null) { | 916 if (isValidKey == null) { |
924 if (hashCode == null) { | 917 if (hashCode == null) { |
925 if (equals == null) { | 918 if (equals == null) { |
926 return new _InternalLinkedHashMap<K, V>(); | 919 return new _InternalLinkedHashMap<K, V>(); |
927 } | 920 } |
928 hashCode = _defaultHashCode; | 921 hashCode = _defaultHashCode; |
929 } else { | 922 } else { |
930 if (identical(identityHashCode, hashCode) && | 923 if (identical(identityHashCode, hashCode) && |
931 identical(identical, equals)) { | 924 identical(identical, equals)) { |
932 return new _CompactLinkedIdentityHashMap<K, V>(); | 925 return new _CompactLinkedIdentityHashMap<K, V>(); |
933 } | 926 } |
934 if (equals == null) { | 927 if (equals == null) { |
935 equals = _defaultEquals; | 928 equals = _defaultEquals; |
936 } | 929 } |
937 } | 930 } |
938 } else { | 931 } else { |
939 if (hashCode == null) { | 932 if (hashCode == null) { |
940 hashCode = _defaultHashCode; | 933 hashCode = _defaultHashCode; |
941 } | 934 } |
942 if (equals == null) { | 935 if (equals == null) { |
943 equals = _defaultEquals; | 936 equals = _defaultEquals; |
944 } | 937 } |
945 } | 938 } |
946 return new _CompactLinkedCustomHashMap<K, V>(equals, hashCode, isValidKey); | 939 return new _CompactLinkedCustomHashMap<K, V>(equals, hashCode, isValidKey); |
947 } | 940 } |
948 | 941 |
949 @patch | 942 @patch factory LinkedHashMap.identity() = |
950 factory LinkedHashMap.identity() = _CompactLinkedIdentityHashMap<K, V>; | 943 _CompactLinkedIdentityHashMap<K, V>; |
951 } | 944 } |
952 | 945 |
953 @patch | 946 @patch class LinkedHashSet<E> { |
954 class LinkedHashSet<E> { | 947 @patch factory LinkedHashSet({ bool equals(E e1, E e2), |
955 @patch | 948 int hashCode(E e), |
956 factory LinkedHashSet( | 949 bool isValidKey(potentialKey) }) { |
957 {bool equals(E e1, E e2), | |
958 int hashCode(E e), | |
959 bool isValidKey(potentialKey)}) { | |
960 if (isValidKey == null) { | 950 if (isValidKey == null) { |
961 if (hashCode == null) { | 951 if (hashCode == null) { |
962 if (equals == null) { | 952 if (equals == null) { |
963 return new _CompactLinkedHashSet<E>(); | 953 return new _CompactLinkedHashSet<E>(); |
964 } | 954 } |
965 hashCode = _defaultHashCode; | 955 hashCode = _defaultHashCode; |
966 } else { | 956 } else { |
967 if (identical(identityHashCode, hashCode) && | 957 if (identical(identityHashCode, hashCode) && |
968 identical(identical, equals)) { | 958 identical(identical, equals)) { |
969 return new _CompactLinkedIdentityHashSet<E>(); | 959 return new _CompactLinkedIdentityHashSet<E>(); |
970 } | 960 } |
971 if (equals == null) { | 961 if (equals == null) { |
972 equals = _defaultEquals; | 962 equals = _defaultEquals; |
973 } | 963 } |
974 } | 964 } |
975 } else { | 965 } else { |
976 if (hashCode == null) { | 966 if (hashCode == null) { |
977 hashCode = _defaultHashCode; | 967 hashCode = _defaultHashCode; |
978 } | 968 } |
979 if (equals == null) { | 969 if (equals == null) { |
980 equals = _defaultEquals; | 970 equals = _defaultEquals; |
981 } | 971 } |
982 } | 972 } |
983 return new _CompactLinkedCustomHashSet<E>(equals, hashCode, isValidKey); | 973 return new _CompactLinkedCustomHashSet<E>(equals, hashCode, isValidKey); |
984 } | 974 } |
985 | 975 |
986 @patch | 976 @patch factory LinkedHashSet.identity() = |
987 factory LinkedHashSet.identity() = _CompactLinkedIdentityHashSet<E>; | 977 _CompactLinkedIdentityHashSet<E>; |
988 } | 978 } |
OLD | NEW |