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 171 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
182 | 182 |
183 static int _firstProbe(int hashCode, int length) { | 183 static int _firstProbe(int hashCode, int length) { |
184 return hashCode & (length - 1); | 184 return hashCode & (length - 1); |
185 } | 185 } |
186 | 186 |
187 static int _nextProbe(int currentProbe, int numberOfProbes, int length) { | 187 static int _nextProbe(int currentProbe, int numberOfProbes, int length) { |
188 return (currentProbe + numberOfProbes) & (length - 1); | 188 return (currentProbe + numberOfProbes) & (length - 1); |
189 } | 189 } |
190 | 190 |
191 int _probeForAdding(K key) { | 191 int _probeForAdding(K key) { |
192 if (key == null) throw new ArgumentError(null); | 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. |
(...skipping 14 matching lines...) Expand all Loading... |
217 } | 217 } |
218 | 218 |
219 // 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. |
220 hash = _nextProbe(hash, numberOfProbes++, _keys.length); | 220 hash = _nextProbe(hash, numberOfProbes++, _keys.length); |
221 // _ensureCapacity has guaranteed the following cannot happen. | 221 // _ensureCapacity has guaranteed the following cannot happen. |
222 // assert(hash != initialHash); | 222 // assert(hash != initialHash); |
223 } | 223 } |
224 } | 224 } |
225 | 225 |
226 int _probeForLookup(K key) { | 226 int _probeForLookup(K key) { |
227 if (key == null) throw new ArgumentError(null); | 227 if (key == null) throw const NullPointerException(); |
228 int hash = _firstProbe(key.hashCode, _keys.length); | 228 int hash = _firstProbe(key.hashCode, _keys.length); |
229 int numberOfProbes = 1; | 229 int numberOfProbes = 1; |
230 int initialHash = hash; | 230 int initialHash = hash; |
231 while (true) { | 231 while (true) { |
232 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. | 232 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. |
233 Object existingKey = _keys[hash]; | 233 Object existingKey = _keys[hash]; |
234 // 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 |
235 // 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. |
236 if (existingKey == null) return -1; | 236 if (existingKey == null) return -1; |
237 // The key is in the map, return its index. | 237 // The key is in the map, return its index. |
(...skipping 280 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
518 | 518 |
519 void clear() { | 519 void clear() { |
520 _map.clear(); | 520 _map.clear(); |
521 _list.clear(); | 521 _list.clear(); |
522 } | 522 } |
523 | 523 |
524 String toString() { | 524 String toString() { |
525 return Maps.mapToString(this); | 525 return Maps.mapToString(this); |
526 } | 526 } |
527 } | 527 } |
OLD | NEW |