| OLD | NEW |
| 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, 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 /** | 5 /** |
| 6 * A [Map] is an associative container, mapping a key to a value. | 6 * A [Map] is an associative container, mapping a key to a value. |
| 7 * Null values are supported, but null keys are not. | 7 * Null values are supported, but null keys are not. |
| 8 */ | 8 */ |
| 9 abstract class Map<K, V> { | 9 abstract class Map<K, V> { |
| 10 /** | 10 /** |
| (...skipping 180 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 191 int _probeForAdding(K key) { | 191 int _probeForAdding(K key) { |
| 192 if (key == null) throw const NullPointerException(); | 192 if (key == null) throw const NullPointerException(); |
| 193 int hash = _firstProbe(key.hashCode, _keys.length); | 193 int hash = _firstProbe(key.hashCode, _keys.length); |
| 194 int numberOfProbes = 1; | 194 int numberOfProbes = 1; |
| 195 int initialHash = hash; | 195 int initialHash = hash; |
| 196 // insertionIndex points to a slot where a key was deleted. | 196 // insertionIndex points to a slot where a key was deleted. |
| 197 int insertionIndex = -1; | 197 int insertionIndex = -1; |
| 198 while (true) { | 198 while (true) { |
| 199 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. | 199 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. |
| 200 Object existingKey = _keys[hash]; | 200 Object existingKey = _keys[hash]; |
| 201 if (existingKey === null) { | 201 if (existingKey == null) { |
| 202 // We are sure the key is not already in the set. | 202 // We are sure the key is not already in the set. |
| 203 // If the current slot is empty and we didn't find any | 203 // If the current slot is empty and we didn't find any |
| 204 // insertion slot before, return this slot. | 204 // insertion slot before, return this slot. |
| 205 if (insertionIndex < 0) return hash; | 205 if (insertionIndex < 0) return hash; |
| 206 // If we did find an insertion slot before, return it. | 206 // If we did find an insertion slot before, return it. |
| 207 return insertionIndex; | 207 return insertionIndex; |
| 208 } else if (existingKey == key) { | 208 } else if (existingKey == key) { |
| 209 // The key is already in the map. Return its slot. | 209 // The key is already in the map. Return its slot. |
| 210 return hash; | 210 return hash; |
| 211 } else if ((insertionIndex < 0) && (_DELETED_KEY === existingKey)) { | 211 } else if ((insertionIndex < 0) && |
| 212 (identical(existingKey, _DELETED_KEY))) { |
| 212 // The slot contains a deleted element. Because previous calls to this | 213 // The slot contains a deleted element. Because previous calls to this |
| 213 // method may not have had this slot deleted, we must continue iterate | 214 // method may not have had this slot deleted, we must continue iterate |
| 214 // to find if there is a slot with the given key. | 215 // to find if there is a slot with the given key. |
| 215 insertionIndex = hash; | 216 insertionIndex = hash; |
| 216 } | 217 } |
| 217 | 218 |
| 218 // We did not find an insertion slot. Look at the next one. | 219 // We did not find an insertion slot. Look at the next one. |
| 219 hash = _nextProbe(hash, numberOfProbes++, _keys.length); | 220 hash = _nextProbe(hash, numberOfProbes++, _keys.length); |
| 220 // _ensureCapacity has guaranteed the following cannot happen. | 221 // _ensureCapacity has guaranteed the following cannot happen. |
| 221 // assert(hash != initialHash); | 222 // assert(hash != initialHash); |
| 222 } | 223 } |
| 223 } | 224 } |
| 224 | 225 |
| 225 int _probeForLookup(K key) { | 226 int _probeForLookup(K key) { |
| 226 if (key == null) throw const NullPointerException(); | 227 if (key == null) throw const NullPointerException(); |
| 227 int hash = _firstProbe(key.hashCode, _keys.length); | 228 int hash = _firstProbe(key.hashCode, _keys.length); |
| 228 int numberOfProbes = 1; | 229 int numberOfProbes = 1; |
| 229 int initialHash = hash; | 230 int initialHash = hash; |
| 230 while (true) { | 231 while (true) { |
| 231 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. | 232 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. |
| 232 Object existingKey = _keys[hash]; | 233 Object existingKey = _keys[hash]; |
| 233 // If the slot does not contain anything (in particular, it does not | 234 // If the slot does not contain anything (in particular, it does not |
| 234 // contain a deleted key), we know the key is not in the map. | 235 // contain a deleted key), we know the key is not in the map. |
| 235 if (existingKey === null) return -1; | 236 if (existingKey == null) return -1; |
| 236 // The key is in the map, return its index. | 237 // The key is in the map, return its index. |
| 237 if (existingKey == key) return hash; | 238 if (existingKey == key) return hash; |
| 238 // Go to the next probe. | 239 // Go to the next probe. |
| 239 hash = _nextProbe(hash, numberOfProbes++, _keys.length); | 240 hash = _nextProbe(hash, numberOfProbes++, _keys.length); |
| 240 // _ensureCapacity has guaranteed the following cannot happen. | 241 // _ensureCapacity has guaranteed the following cannot happen. |
| 241 // assert(hash != initialHash); | 242 // assert(hash != initialHash); |
| 242 } | 243 } |
| 243 } | 244 } |
| 244 | 245 |
| 245 void _ensureCapacity() { | 246 void _ensureCapacity() { |
| (...skipping 25 matching lines...) Expand all Loading... |
| 271 int capacity = _keys.length; | 272 int capacity = _keys.length; |
| 272 _loadLimit = _computeLoadLimit(newCapacity); | 273 _loadLimit = _computeLoadLimit(newCapacity); |
| 273 List oldKeys = _keys; | 274 List oldKeys = _keys; |
| 274 List<V> oldValues = _values; | 275 List<V> oldValues = _values; |
| 275 _keys = new List(newCapacity); | 276 _keys = new List(newCapacity); |
| 276 _values = new List<V>(newCapacity); | 277 _values = new List<V>(newCapacity); |
| 277 for (int i = 0; i < capacity; i++) { | 278 for (int i = 0; i < capacity; i++) { |
| 278 // [key] can be either of type [K] or [_DeletedKeySentinel]. | 279 // [key] can be either of type [K] or [_DeletedKeySentinel]. |
| 279 Object key = oldKeys[i]; | 280 Object key = oldKeys[i]; |
| 280 // If there is no key, we don't need to deal with the current slot. | 281 // If there is no key, we don't need to deal with the current slot. |
| 281 if (key === null || key === _DELETED_KEY) { | 282 if (key == null || identical(key, _DELETED_KEY)) { |
| 282 continue; | 283 continue; |
| 283 } | 284 } |
| 284 V value = oldValues[i]; | 285 V value = oldValues[i]; |
| 285 // Insert the {key, value} pair in their new slot. | 286 // Insert the {key, value} pair in their new slot. |
| 286 int newIndex = _probeForAdding(key); | 287 int newIndex = _probeForAdding(key); |
| 287 _keys[newIndex] = key; | 288 _keys[newIndex] = key; |
| 288 _values[newIndex] = value; | 289 _values[newIndex] = value; |
| 289 } | 290 } |
| 290 _numberOfDeleted = 0; | 291 _numberOfDeleted = 0; |
| 291 } | 292 } |
| 292 | 293 |
| 293 void clear() { | 294 void clear() { |
| 294 _numberOfEntries = 0; | 295 _numberOfEntries = 0; |
| 295 _numberOfDeleted = 0; | 296 _numberOfDeleted = 0; |
| 296 int length = _keys.length; | 297 int length = _keys.length; |
| 297 for (int i = 0; i < length; i++) { | 298 for (int i = 0; i < length; i++) { |
| 298 _keys[i] = null; | 299 _keys[i] = null; |
| 299 _values[i] = null; | 300 _values[i] = null; |
| 300 } | 301 } |
| 301 } | 302 } |
| 302 | 303 |
| 303 void operator []=(K key, V value) { | 304 void operator []=(K key, V value) { |
| 304 _ensureCapacity(); | 305 _ensureCapacity(); |
| 305 int index = _probeForAdding(key); | 306 int index = _probeForAdding(key); |
| 306 if ((_keys[index] === null) || (_keys[index] === _DELETED_KEY)) { | 307 if ((_keys[index] == null) || (identical(_keys[index], _DELETED_KEY))) { |
| 307 _numberOfEntries++; | 308 _numberOfEntries++; |
| 308 } | 309 } |
| 309 _keys[index] = key; | 310 _keys[index] = key; |
| 310 _values[index] = value; | 311 _values[index] = value; |
| 311 } | 312 } |
| 312 | 313 |
| 313 V operator [](K key) { | 314 V operator [](K key) { |
| 314 int index = _probeForLookup(key); | 315 int index = _probeForLookup(key); |
| 315 if (index < 0) return null; | 316 if (index < 0) return null; |
| 316 return _values[index]; | 317 return _values[index]; |
| (...skipping 27 matching lines...) Expand all Loading... |
| 344 } | 345 } |
| 345 | 346 |
| 346 int get length { | 347 int get length { |
| 347 return _numberOfEntries; | 348 return _numberOfEntries; |
| 348 } | 349 } |
| 349 | 350 |
| 350 void forEach(void f(K key, V value)) { | 351 void forEach(void f(K key, V value)) { |
| 351 int length = _keys.length; | 352 int length = _keys.length; |
| 352 for (int i = 0; i < length; i++) { | 353 for (int i = 0; i < length; i++) { |
| 353 var key = _keys[i]; | 354 var key = _keys[i]; |
| 354 if ((key !== null) && (key !== _DELETED_KEY)) { | 355 if ((key != null) && (!identical(key, _DELETED_KEY))) { |
| 355 f(key, _values[i]); | 356 f(key, _values[i]); |
| 356 } | 357 } |
| 357 } | 358 } |
| 358 } | 359 } |
| 359 | 360 |
| 360 | 361 |
| 361 Collection<K> get keys { | 362 Collection<K> get keys { |
| 362 List<K> list = new List<K>(length); | 363 List<K> list = new List<K>(length); |
| 363 int i = 0; | 364 int i = 0; |
| 364 forEach(void _(K key, V value) { | 365 forEach(void _(K key, V value) { |
| (...skipping 12 matching lines...) Expand all Loading... |
| 377 } | 378 } |
| 378 | 379 |
| 379 bool containsKey(K key) { | 380 bool containsKey(K key) { |
| 380 return (_probeForLookup(key) != -1); | 381 return (_probeForLookup(key) != -1); |
| 381 } | 382 } |
| 382 | 383 |
| 383 bool containsValue(V value) { | 384 bool containsValue(V value) { |
| 384 int length = _values.length; | 385 int length = _values.length; |
| 385 for (int i = 0; i < length; i++) { | 386 for (int i = 0; i < length; i++) { |
| 386 var key = _keys[i]; | 387 var key = _keys[i]; |
| 387 if ((key !== null) && (key !== _DELETED_KEY)) { | 388 if ((key != null) && (!identical(key, _DELETED_KEY))) { |
| 388 if (_values[i] == value) return true; | 389 if (_values[i] == value) return true; |
| 389 } | 390 } |
| 390 } | 391 } |
| 391 return false; | 392 return false; |
| 392 } | 393 } |
| 393 | 394 |
| 394 String toString() { | 395 String toString() { |
| 395 return Maps.mapToString(this); | 396 return Maps.mapToString(this); |
| 396 } | 397 } |
| 397 } | 398 } |
| (...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 443 if (_map.containsKey(key)) { | 444 if (_map.containsKey(key)) { |
| 444 _map[key].element.value = value; | 445 _map[key].element.value = value; |
| 445 } else { | 446 } else { |
| 446 _list.addLast(new _KeyValuePair<K, V>(key, value)); | 447 _list.addLast(new _KeyValuePair<K, V>(key, value)); |
| 447 _map[key] = _list.lastEntry(); | 448 _map[key] = _list.lastEntry(); |
| 448 } | 449 } |
| 449 } | 450 } |
| 450 | 451 |
| 451 V operator [](K key) { | 452 V operator [](K key) { |
| 452 DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map[key]; | 453 DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map[key]; |
| 453 if (entry === null) return null; | 454 if (entry == null) return null; |
| 454 return entry.element.value; | 455 return entry.element.value; |
| 455 } | 456 } |
| 456 | 457 |
| 457 V remove(K key) { | 458 V remove(K key) { |
| 458 DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map.remove(key); | 459 DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map.remove(key); |
| 459 if (entry === null) return null; | 460 if (entry == null) return null; |
| 460 entry.remove(); | 461 entry.remove(); |
| 461 return entry.element.value; | 462 return entry.element.value; |
| 462 } | 463 } |
| 463 | 464 |
| 464 V putIfAbsent(K key, V ifAbsent()) { | 465 V putIfAbsent(K key, V ifAbsent()) { |
| 465 V value = this[key]; | 466 V value = this[key]; |
| 466 if ((this[key] === null) && !(containsKey(key))) { | 467 if ((this[key] == null) && !(containsKey(key))) { |
| 467 value = ifAbsent(); | 468 value = ifAbsent(); |
| 468 this[key] = value; | 469 this[key] = value; |
| 469 } | 470 } |
| 470 return value; | 471 return value; |
| 471 } | 472 } |
| 472 | 473 |
| 473 Collection<K> get keys { | 474 Collection<K> get keys { |
| 474 List<K> list = new List<K>(length); | 475 List<K> list = new List<K>(length); |
| 475 int index = 0; | 476 int index = 0; |
| 476 _list.forEach(void _(_KeyValuePair<K, V> entry) { | 477 _list.forEach(void _(_KeyValuePair<K, V> entry) { |
| (...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 517 | 518 |
| 518 void clear() { | 519 void clear() { |
| 519 _map.clear(); | 520 _map.clear(); |
| 520 _list.clear(); | 521 _list.clear(); |
| 521 } | 522 } |
| 522 | 523 |
| 523 String toString() { | 524 String toString() { |
| 524 return Maps.mapToString(this); | 525 return Maps.mapToString(this); |
| 525 } | 526 } |
| 526 } | 527 } |
| OLD | NEW |