| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 // TODO(ahe): Remove this file and use the shared one. | |
| 6 | |
| 7 // Hash map implementation with open addressing and quadratic probing. | |
| 8 class HashMapImplementation<K extends Hashable, V> implements HashMap<K, V> { | |
| 9 | |
| 10 // The [_keys] list contains the keys inserted in the map. | |
| 11 // The [_keys] list must be a raw list because it | |
| 12 // will contain both elements of type K, and the [_DELETED_KEY] of type | |
| 13 // [_DeletedKeySentinel]. | |
| 14 // The alternative of declaring the [_keys] list as of type Object | |
| 15 // does not work, because the HashSetIterator constructor would fail: | |
| 16 // HashSetIterator(HashSet<E> set) | |
| 17 // : _nextValidIndex = -1, | |
| 18 // _entries = set_._backingMap._keys { | |
| 19 // _advance(); | |
| 20 // } | |
| 21 // With K being type int, for example, it would fail because | |
| 22 // List<Object> is not assignable to type List<int> of entries. | |
| 23 List _keys; | |
| 24 | |
| 25 // The values inserted in the map. For a filled entry index in this | |
| 26 // list, there is always the corresponding key in the [keys_] list | |
| 27 // at the same entry index. | |
| 28 List<V> _values; | |
| 29 | |
| 30 // The load limit is the number of entries we allow until we double | |
| 31 // the size of the lists. | |
| 32 int _loadLimit; | |
| 33 | |
| 34 // The current number of entries in the map. Will never be greater | |
| 35 // than [_loadLimit]. | |
| 36 int _numberOfEntries; | |
| 37 | |
| 38 // The current number of deleted entries in the map. | |
| 39 int _numberOfDeleted; | |
| 40 | |
| 41 // The sentinel when a key is deleted from the map. | |
| 42 static final _DeletedKeySentinel _DELETED_KEY = const _DeletedKeySentinel(); | |
| 43 | |
| 44 // The initial capacity of a hash map. | |
| 45 static final int _INITIAL_CAPACITY = 8; // must be power of 2 | |
| 46 | |
| 47 HashMapImplementation() { | |
| 48 _numberOfEntries = 0; | |
| 49 _numberOfDeleted = 0; | |
| 50 _loadLimit = _computeLoadLimit(_INITIAL_CAPACITY); | |
| 51 _keys = new List(_INITIAL_CAPACITY); | |
| 52 _values = new List<V>(_INITIAL_CAPACITY); | |
| 53 } | |
| 54 | |
| 55 factory HashMapImplementation.from(Map<K, V> other) { | |
| 56 Map<K, V> result = new HashMapImplementation<K, V>(); | |
| 57 other.forEach((K key, V value) { result[key] = value; }); | |
| 58 return result; | |
| 59 } | |
| 60 | |
| 61 static int _computeLoadLimit(int capacity) { | |
| 62 return (capacity * 3) ~/ 4; | |
| 63 } | |
| 64 | |
| 65 static int _firstProbe(int hashCode, int length) { | |
| 66 return hashCode & (length - 1); | |
| 67 } | |
| 68 | |
| 69 static int _nextProbe(int currentProbe, int numberOfProbes, int length) { | |
| 70 return (currentProbe + numberOfProbes) & (length - 1); | |
| 71 } | |
| 72 | |
| 73 int _probeForAdding(K key) { | |
| 74 int hash = _firstProbe(key.hashCode(), _keys.length); | |
| 75 int numberOfProbes = 1; | |
| 76 int initialHash = hash; | |
| 77 // insertionIndex points to a slot where a key was deleted. | |
| 78 int insertionIndex = -1; | |
| 79 while (true) { | |
| 80 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. | |
| 81 Object existingKey = _keys[hash]; | |
| 82 if (existingKey === null) { | |
| 83 // We are sure the key is not already in the set. | |
| 84 // If the current slot is empty and we didn't find any | |
| 85 // insertion slot before, return this slot. | |
| 86 if (insertionIndex < 0) return hash; | |
| 87 // If we did find an insertion slot before, return it. | |
| 88 return insertionIndex; | |
| 89 } else if (existingKey == key) { | |
| 90 // The key is already in the map. Return its slot. | |
| 91 return hash; | |
| 92 } else if ((insertionIndex < 0) && (_DELETED_KEY === existingKey)) { | |
| 93 // The slot contains a deleted element. Because previous calls to this | |
| 94 // method may not have had this slot deleted, we must continue iterate | |
| 95 // to find if there is a slot with the given key. | |
| 96 insertionIndex = hash; | |
| 97 } | |
| 98 | |
| 99 // We did not find an insertion slot. Look at the next one. | |
| 100 hash = _nextProbe(hash, numberOfProbes++, _keys.length); | |
| 101 // _ensureCapacity has guaranteed the following cannot happen. | |
| 102 // assert(hash != initialHash); | |
| 103 } | |
| 104 } | |
| 105 | |
| 106 int _probeForLookup(K key) { | |
| 107 int hash = _firstProbe(key.hashCode(), _keys.length); | |
| 108 int numberOfProbes = 1; | |
| 109 int initialHash = hash; | |
| 110 while (true) { | |
| 111 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. | |
| 112 Object existingKey = _keys[hash]; | |
| 113 // If the slot does not contain anything (in particular, it does not | |
| 114 // contain a deleted key), we know the key is not in the map. | |
| 115 if (existingKey === null) return -1; | |
| 116 // The key is in the map, return its index. | |
| 117 if (existingKey == key) return hash; | |
| 118 // Go to the next probe. | |
| 119 hash = _nextProbe(hash, numberOfProbes++, _keys.length); | |
| 120 // _ensureCapacity has guaranteed the following cannot happen. | |
| 121 // assert(hash != initialHash); | |
| 122 } | |
| 123 } | |
| 124 | |
| 125 void _ensureCapacity() { | |
| 126 int newNumberOfEntries = _numberOfEntries + 1; | |
| 127 // Test if adding an element will reach the load limit. | |
| 128 if (newNumberOfEntries >= _loadLimit) { | |
| 129 _grow(_keys.length * 2); | |
| 130 return; | |
| 131 } | |
| 132 | |
| 133 // Make sure that we don't have poor performance when a map | |
| 134 // contains lots of deleted entries: we _grow if | |
| 135 // there are more deleted entried than free entries. | |
| 136 int capacity = _keys.length; | |
| 137 int numberOfFreeOrDeleted = capacity - newNumberOfEntries; | |
| 138 int numberOfFree = numberOfFreeOrDeleted - _numberOfDeleted; | |
| 139 // assert(numberOfFree > 0); | |
| 140 if (_numberOfDeleted > numberOfFree) { | |
| 141 _grow(_keys.length); | |
| 142 } | |
| 143 } | |
| 144 | |
| 145 static bool _isPowerOfTwo(int x) { | |
| 146 return ((x & (x - 1)) == 0); | |
| 147 } | |
| 148 | |
| 149 void _grow(int newCapacity) { | |
| 150 assert(_isPowerOfTwo(newCapacity)); | |
| 151 int capacity = _keys.length; | |
| 152 _loadLimit = _computeLoadLimit(newCapacity); | |
| 153 List oldKeys = _keys; | |
| 154 List<V> oldValues = _values; | |
| 155 _keys = new List(newCapacity); | |
| 156 _values = new List<V>(newCapacity); | |
| 157 for (int i = 0; i < capacity; i++) { | |
| 158 // [key] can be either of type [K] or [_DeletedKeySentinel]. | |
| 159 Object key = oldKeys[i]; | |
| 160 // If there is no key, we don't need to deal with the current slot. | |
| 161 if (key !== null && key !== _DELETED_KEY) { | |
| 162 V value = oldValues[i]; | |
| 163 // Insert the {key, value} pair in their new slot. | |
| 164 int newIndex = _probeForAdding(key); | |
| 165 _keys[newIndex] = key; | |
| 166 _values[newIndex] = value; | |
| 167 } | |
| 168 } | |
| 169 _numberOfDeleted = 0; | |
| 170 } | |
| 171 | |
| 172 void clear() { | |
| 173 _numberOfEntries = 0; | |
| 174 _numberOfDeleted = 0; | |
| 175 int length = _keys.length; | |
| 176 for (int i = 0; i < length; i++) { | |
| 177 _keys[i] = null; | |
| 178 _values[i] = null; | |
| 179 } | |
| 180 } | |
| 181 | |
| 182 void operator []=(K key, V value) { | |
| 183 _ensureCapacity(); | |
| 184 int index = _probeForAdding(key); | |
| 185 if ((_keys[index] === null) || (_keys[index] === _DELETED_KEY)) { | |
| 186 _numberOfEntries++; | |
| 187 } | |
| 188 _keys[index] = key; | |
| 189 _values[index] = value; | |
| 190 } | |
| 191 | |
| 192 V operator [](K key) { | |
| 193 int index = _probeForLookup(key); | |
| 194 if (index < 0) return null; | |
| 195 return _values[index]; | |
| 196 } | |
| 197 | |
| 198 V putIfAbsent(K key, V ifAbsent()) { | |
| 199 int index = _probeForLookup(key); | |
| 200 if (index >=0) return _values[index]; | |
| 201 | |
| 202 V value = ifAbsent(); | |
| 203 this[key] = value; | |
| 204 return value; | |
| 205 } | |
| 206 | |
| 207 V remove(K key) { | |
| 208 int index = _probeForLookup(key); | |
| 209 if (index >= 0) { | |
| 210 _numberOfEntries--; | |
| 211 V value = _values[index]; | |
| 212 _values[index] = null; | |
| 213 // Set the key to the sentinel to not break the probing chain. | |
| 214 _keys[index] = _DELETED_KEY; | |
| 215 _numberOfDeleted++; | |
| 216 return value; | |
| 217 } | |
| 218 return null; | |
| 219 } | |
| 220 | |
| 221 bool isEmpty() { | |
| 222 return _numberOfEntries == 0; | |
| 223 } | |
| 224 | |
| 225 int get length() { | |
| 226 return _numberOfEntries; | |
| 227 } | |
| 228 | |
| 229 void forEach(void f(K key, V value)) { | |
| 230 int length = _keys.length; | |
| 231 for (int i = 0; i < length; i++) { | |
| 232 var key = _keys[i]; | |
| 233 if ((key !== null) && (key !== _DELETED_KEY)) { | |
| 234 f(key, _values[i]); | |
| 235 } | |
| 236 } | |
| 237 } | |
| 238 | |
| 239 | |
| 240 Collection<K> getKeys() { | |
| 241 List<K> list = new List<K>(length); | |
| 242 int i = 0; | |
| 243 forEach(void _(K key, V value) { | |
| 244 list[i++] = key; | |
| 245 }); | |
| 246 return list; | |
| 247 } | |
| 248 | |
| 249 Collection<V> getValues() { | |
| 250 List<V> list = new List<V>(length); | |
| 251 int i = 0; | |
| 252 forEach(void _(K key, V value) { | |
| 253 list[i++] = value; | |
| 254 }); | |
| 255 return list; | |
| 256 } | |
| 257 | |
| 258 bool containsKey(K key) { | |
| 259 return (_probeForLookup(key) != -1); | |
| 260 } | |
| 261 | |
| 262 bool containsValue(V value) { | |
| 263 int length = _values.length; | |
| 264 for (int i = 0; i < length; i++) { | |
| 265 var key = _keys[i]; | |
| 266 if ((key !== null) && (key !== _DELETED_KEY)) { | |
| 267 if (_values[i] == value) return true; | |
| 268 } | |
| 269 } | |
| 270 return false; | |
| 271 } | |
| 272 | |
| 273 String toString() { | |
| 274 return Maps.mapToString(this); | |
| 275 } | |
| 276 } | |
| 277 | |
| 278 class HashSetImplementation<E extends Hashable> implements HashSet<E> { | |
| 279 | |
| 280 HashSetImplementation() { | |
| 281 _backingMap = new HashMapImplementation<E, E>(); | |
| 282 } | |
| 283 | |
| 284 factory HashSetImplementation.from(Iterable<E> other) { | |
| 285 Set<E> set = new HashSetImplementation<E>(); | |
| 286 for (final e in other) { | |
| 287 set.add(e); | |
| 288 } | |
| 289 return set; | |
| 290 } | |
| 291 | |
| 292 void clear() { | |
| 293 _backingMap.clear(); | |
| 294 } | |
| 295 | |
| 296 void add(E value) { | |
| 297 _backingMap[value] = value; | |
| 298 } | |
| 299 | |
| 300 bool contains(E value) { | |
| 301 return _backingMap.containsKey(value); | |
| 302 } | |
| 303 | |
| 304 bool remove(E value) { | |
| 305 if (!_backingMap.containsKey(value)) return false; | |
| 306 _backingMap.remove(value); | |
| 307 return true; | |
| 308 } | |
| 309 | |
| 310 void addAll(Collection<E> collection) { | |
| 311 collection.forEach(void _(E value) { | |
| 312 add(value); | |
| 313 }); | |
| 314 } | |
| 315 | |
| 316 Set<E> intersection(Collection<E> collection) { | |
| 317 Set<E> result = new Set<E>(); | |
| 318 collection.forEach(void _(E value) { | |
| 319 if (contains(value)) result.add(value); | |
| 320 }); | |
| 321 return result; | |
| 322 } | |
| 323 | |
| 324 bool isSubsetOf(Collection<E> other) { | |
| 325 return new Set.from(other).containsAll(this); | |
| 326 } | |
| 327 | |
| 328 void removeAll(Collection<E> collection) { | |
| 329 collection.forEach(void _(E value) { | |
| 330 remove(value); | |
| 331 }); | |
| 332 } | |
| 333 | |
| 334 bool containsAll(Collection<E> collection) { | |
| 335 return collection.every(bool _(E value) { | |
| 336 return contains(value); | |
| 337 }); | |
| 338 } | |
| 339 | |
| 340 void forEach(void f(E element)) { | |
| 341 _backingMap.forEach(void _(E key, E value) { | |
| 342 f(key); | |
| 343 }); | |
| 344 } | |
| 345 | |
| 346 Set map(f(E element)) { | |
| 347 Set result = new Set(); | |
| 348 _backingMap.forEach(void _(E key, E value) { | |
| 349 result.add(f(key)); | |
| 350 }); | |
| 351 return result; | |
| 352 } | |
| 353 | |
| 354 Set<E> filter(bool f(E element)) { | |
| 355 Set<E> result = new Set<E>(); | |
| 356 _backingMap.forEach(void _(E key, E value) { | |
| 357 if (f(key)) result.add(key); | |
| 358 }); | |
| 359 return result; | |
| 360 } | |
| 361 | |
| 362 bool every(bool f(E element)) { | |
| 363 Collection<E> keys = _backingMap.getKeys(); | |
| 364 return keys.every(f); | |
| 365 } | |
| 366 | |
| 367 bool some(bool f(E element)) { | |
| 368 Collection<E> keys = _backingMap.getKeys(); | |
| 369 return keys.some(f); | |
| 370 } | |
| 371 | |
| 372 bool isEmpty() { | |
| 373 return _backingMap.isEmpty(); | |
| 374 } | |
| 375 | |
| 376 int get length() { | |
| 377 return _backingMap.length; | |
| 378 } | |
| 379 | |
| 380 Iterator<E> iterator() { | |
| 381 return new HashSetIterator<E>(this); | |
| 382 } | |
| 383 | |
| 384 String toString() { | |
| 385 return Collections.collectionToString(this); | |
| 386 } | |
| 387 | |
| 388 // The map backing this set. The associations in this map are all | |
| 389 // of the form element -> element. If a value is not in the map, | |
| 390 // then it is not in the set. | |
| 391 HashMapImplementation<E, E> _backingMap; | |
| 392 } | |
| 393 | |
| 394 class HashSetIterator<E> implements Iterator<E> { | |
| 395 | |
| 396 // TODO(4504458): Replace set_ with set. | |
| 397 HashSetIterator(HashSetImplementation<E> set_) | |
| 398 : _nextValidIndex = -1, | |
| 399 _entries = set_._backingMap._keys { | |
| 400 _advance(); | |
| 401 } | |
| 402 | |
| 403 bool hasNext() { | |
| 404 if (_nextValidIndex >= _entries.length) return false; | |
| 405 if (_entries[_nextValidIndex] === HashMapImplementation._DELETED_KEY) { | |
| 406 // This happens in case the set was modified in the meantime. | |
| 407 // A modification on the set may make this iterator misbehave, | |
| 408 // but we should never return the sentinel. | |
| 409 _advance(); | |
| 410 } | |
| 411 return _nextValidIndex < _entries.length; | |
| 412 } | |
| 413 | |
| 414 E next() { | |
| 415 if (!hasNext()) { | |
| 416 throw const NoMoreElementsException(); | |
| 417 } | |
| 418 E res = _entries[_nextValidIndex]; | |
| 419 _advance(); | |
| 420 return res; | |
| 421 } | |
| 422 | |
| 423 void _advance() { | |
| 424 int length = _entries.length; | |
| 425 var entry; | |
| 426 final deletedKey = HashMapImplementation._DELETED_KEY; | |
| 427 do { | |
| 428 if (++_nextValidIndex >= length) break; | |
| 429 entry = _entries[_nextValidIndex]; | |
| 430 } while ((entry === null) || (entry === deletedKey)); | |
| 431 } | |
| 432 | |
| 433 // The entries in the set. May contain null or the sentinel value. | |
| 434 List<E> _entries; | |
| 435 | |
| 436 // The next valid index in [_entries] or the length of [entries_]. | |
| 437 // If it is the length of [_entries], calling [hasNext] on the | |
| 438 // iterator will return false. | |
| 439 int _nextValidIndex; | |
| 440 } | |
| 441 | |
| 442 /** | |
| 443 * A singleton sentinel used to represent when a key is deleted from the map. | |
| 444 * We can't use [: const Object() :] as a sentinel because it would end up | |
| 445 * canonicalized and then we cannot distinguish the deleted key from the | |
| 446 * canonicalized [: Object() :]. | |
| 447 */ | |
| 448 class _DeletedKeySentinel { | |
| 449 const _DeletedKeySentinel(); | |
| 450 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 9808109:
Implement unlabeled continue. (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge