1 /* 2 * Hunt - A refined core library for D programming language. 3 * 4 * Copyright (C) 2018-2019 HuntLabs 5 * 6 * Website: https://www.huntlabs.net/ 7 * 8 * Licensed under the Apache-2.0 License. 9 * 10 */ 11 12 module hunt.collection.LinkedHashMap; 13 14 import hunt.collection.AbstractCollection; 15 import hunt.collection.AbstractMap; 16 import hunt.collection.HashMap; 17 import hunt.collection.Map; 18 19 import hunt.Exceptions; 20 21 import std.range; 22 23 /** 24 * <p>Hash table and linked list implementation of the <tt>Map</tt> interface, 25 * with predictable iteration order. This implementation differs from 26 * <tt>HashMap</tt> in that it maintains a doubly-linked list running through 27 * all of its entries. This linked list defines the iteration ordering, 28 * which is normally the order in which keys were inserted into the map 29 * (<i>insertion-order</i>). Note that insertion order is not affected 30 * if a key is <i>re-inserted</i> into the map. (A key <tt>k</tt> is 31 * reinserted into a map <tt>m</tt> if <tt>m.put(k, v)</tt> is invoked when 32 * <tt>m.containsKey(k)</tt> would return <tt>true</tt> immediately prior to 33 * the invocation.) 34 * 35 * <p>This implementation spares its clients from the unspecified, generally 36 * chaotic ordering provided by {@link HashMap} (and {@link Hashtable}), 37 * without incurring the increased cost associated with {@link TreeMap}. It 38 * can be used to produce a copy of a map that has the same order as the 39 * original, regardless of the original map's implementation: 40 * <pre> 41 * void foo(Map m) { 42 * Map copy = new LinkedHashMap(m); 43 * ... 44 * } 45 * </pre> 46 * This technique is particularly useful if a module takes a map on input, 47 * copies it, and later returns results whose order is determined by that of 48 * the copy. (Clients generally appreciate having things returned in the same 49 * order they were presented.) 50 * 51 * <p>A special {@link #LinkedHashMap(int,float,bool) constructor} is 52 * provided to create a linked hash map whose order of iteration is the order 53 * in which its entries were last accessed, from least-recently accessed to 54 * most-recently (<i>access-order</i>). This kind of map is well-suited to 55 * building LRU caches. Invoking the {@code put}, {@code putIfAbsent}, 56 * {@code get}, {@code getOrDefault}, {@code compute}, {@code computeIfAbsent}, 57 * {@code computeIfPresent}, or {@code merge} methods results 58 * in an access to the corresponding entry (assuming it exists after the 59 * invocation completes). The {@code replace} methods only result in an access 60 * of the entry if the value is replaced. The {@code putAll} method generates one 61 * entry access for each mapping in the specified map, in the order that 62 * key-value mappings are provided by the specified map's entry set iterator. 63 * <i>No other methods generate entry accesses.</i> In particular, operations 64 * on collection-views do <i>not</i> affect the order of iteration of the 65 * backing map. 66 * 67 * <p>The {@link #removeEldestEntry(MapEntry)} method may be overridden to 68 * impose a policy for removing stale mappings automatically when new mappings 69 * are added to the map. 70 * 71 * <p>This class provides all of the optional <tt>Map</tt> operations, and 72 * permits null elements. Like <tt>HashMap</tt>, it provides constant-time 73 * performance for the basic operations (<tt>add</tt>, <tt>contains</tt> and 74 * <tt>remove</tt>), assuming the hash function disperses elements 75 * properly among the buckets. Performance is likely to be just slightly 76 * below that of <tt>HashMap</tt>, due to the added expense of maintaining the 77 * linked list, with one exception: Iteration over the collection-views 78 * of a <tt>LinkedHashMap</tt> requires time proportional to the <i>size</i> 79 * of the map, regardless of its capacity. Iteration over a <tt>HashMap</tt> 80 * is likely to be more expensive, requiring time proportional to its 81 * <i>capacity</i>. 82 * 83 * <p>A linked hash map has two parameters that affect its performance: 84 * <i>initial capacity</i> and <i>load factor</i>. They are defined precisely 85 * as for <tt>HashMap</tt>. Note, however, that the penalty for choosing an 86 * excessively high value for initial capacity is less severe for this class 87 * than for <tt>HashMap</tt>, as iteration times for this class are unaffected 88 * by capacity. 89 * 90 * <p><strong>Note that this implementation is not synchronized.</strong> 91 * If multiple threads access a linked hash map concurrently, and at least 92 * one of the threads modifies the map structurally, it <em>must</em> be 93 * synchronized externally. This is typically accomplished by 94 * synchronizing on some object that naturally encapsulates the map. 95 * 96 * If no such object exists, the map should be "wrapped" using the 97 * {@link Collections#synchronizedMap Collections.synchronizedMap} 98 * method. This is best done at creation time, to prevent accidental 99 * unsynchronized access to the map:<pre> 100 * Map m = Collections.synchronizedMap(new LinkedHashMap(...));</pre> 101 * 102 * A structural modification is any operation that adds or deletes one or more 103 * mappings or, in the case of access-ordered linked hash maps, affects 104 * iteration order. In insertion-ordered linked hash maps, merely changing 105 * the value associated with a key that is already contained in the map is not 106 * a structural modification. <strong>In access-ordered linked hash maps, 107 * merely querying the map with <tt>get</tt> is a structural modification. 108 * </strong>) 109 * 110 * <p>The iterators returned by the <tt>iterator</tt> method of the collections 111 * returned by all of this class's collection view methods are 112 * <em>fail-fast</em>: if the map is structurally modified at any time after 113 * the iterator is created, in any way except through the iterator's own 114 * <tt>remove</tt> method, the iterator will throw a {@link 115 * ConcurrentModificationException}. Thus, in the face of concurrent 116 * modification, the iterator fails quickly and cleanly, rather than risking 117 * arbitrary, non-deterministic behavior at an undetermined time in the future. 118 * 119 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 120 * as it is, generally speaking, impossible to make any hard guarantees in the 121 * presence of unsynchronized concurrent modification. Fail-fast iterators 122 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 123 * Therefore, it would be wrong to write a program that depended on this 124 * exception for its correctness: <i>the fail-fast behavior of iterators 125 * should be used only to detect bugs.</i> 126 * 127 * <p>The spliterators returned by the spliterator method of the collections 128 * returned by all of this class's collection view methods are 129 * <em><a href="Spliterator.html#binding">late-binding</a></em>, 130 * <em>fail-fast</em>, and additionally report {@link Spliterator#ORDERED}. 131 * 132 * <p>This class is a member of the 133 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 134 * Java Collections Framework</a>. 135 * 136 * @implNote 137 * The spliterators returned by the spliterator method of the collections 138 * returned by all of this class's collection view methods are created from 139 * the iterators of the corresponding collections. 140 * 141 * @param (K) the type of keys maintained by this map 142 * @param (V) the type of mapped values 143 * 144 * @author Josh Bloch 145 * @see Object#hashCode() 146 * @see Collection 147 * @see Map 148 * @see HashMap 149 * @see TreeMap 150 * @see Hashtable 151 * @since 1.4 152 */ 153 class LinkedHashMap(K, V) : HashMap!(K, V) 154 { 155 /* 156 * Implementation note. A previous version of this class was 157 * internally structured a little differently. Because superclass 158 * HashMap now uses trees for some of its nodes, class 159 * LinkedHashMapEntry is now treated as intermediary node class 160 * that can also be converted to tree form. The name of this 161 * class, LinkedHashMapEntry, is confusing in several ways in its 162 * current context, but cannot be changed. Otherwise, even though 163 * it is not exported outside this package, some existing source 164 * code is known to have relied on a symbol resolution corner case 165 * rule in calls to removeEldestEntry that suppressed compilation 166 * errors due to ambiguous usages. So, we keep the name to 167 * preserve unmodified compilability. 168 * 169 * The changes in node classes also require using two fields 170 * (head, tail) rather than a pointer to a header node to maintain 171 * the doubly-linked before/after list. This class also 172 * previously used a different style of callback methods upon 173 * access, insertion, and removal. 174 */ 175 176 177 // private static final long serialVersionUID = 3801124242820219131L; 178 179 /** 180 * The head (eldest) of the doubly linked list. 181 */ 182 LinkedHashMapEntry!(K, V)head; 183 184 /** 185 * The tail (youngest) of the doubly linked list. 186 */ 187 LinkedHashMapEntry!(K, V)tail; 188 189 /** 190 * The iteration ordering method for this linked hash map: <tt>true</tt> 191 * for access-order, <tt>false</tt> for insertion-order. 192 * 193 * @serial 194 */ 195 bool accessOrder; 196 197 // internal utilities 198 199 // link at the end of list 200 private void linkNodeLast(LinkedHashMapEntry!(K, V)p) { 201 LinkedHashMapEntry!(K, V)last = tail; 202 tail = p; 203 if (last is null) 204 head = p; 205 else { 206 p.before = last; 207 last.after = p; 208 } 209 } 210 211 // apply src's links to dst 212 private void transferLinks(LinkedHashMapEntry!(K, V)src, 213 LinkedHashMapEntry!(K, V)dst) { 214 LinkedHashMapEntry!(K, V)b = dst.before = src.before; 215 LinkedHashMapEntry!(K, V)a = dst.after = src.after; 216 if (b is null) 217 head = dst; 218 else 219 b.after = dst; 220 if (a is null) 221 tail = dst; 222 else 223 a.before = dst; 224 } 225 226 // overrides of HashMap hook methods 227 228 override void reinitialize() { 229 super.reinitialize(); 230 head = tail = null; 231 } 232 233 override HashMapNode!(K, V) newNode(size_t hash, K key, V value, HashMapNode!(K, V) e) { 234 LinkedHashMapEntry!(K, V) p = new LinkedHashMapEntry!(K, V)(hash, key, value, e); 235 linkNodeLast(p); 236 return p; 237 } 238 239 override HashMapNode!(K, V) replacementNode(HashMapNode!(K, V) p, HashMapNode!(K, V) next) { 240 LinkedHashMapEntry!(K, V) q = cast(LinkedHashMapEntry!(K, V))p; 241 LinkedHashMapEntry!(K, V) t = new LinkedHashMapEntry!(K, V)(q.hash, q.key, q.value, next); 242 transferLinks(q, t); 243 return t; 244 } 245 246 override TreeNode!(K, V) newTreeNode(size_t hash, K key, V value, HashMapNode!(K, V) next) { 247 TreeNode!(K, V) p = new TreeNode!(K, V)(hash, key, value, next); 248 linkNodeLast(p); 249 return p; 250 } 251 252 override TreeNode!(K, V) replacementTreeNode(HashMapNode!(K, V) p, HashMapNode!(K, V) next) { 253 LinkedHashMapEntry!(K, V)q = cast(LinkedHashMapEntry!(K, V))p; 254 TreeNode!(K, V) t = new TreeNode!(K, V)(q.hash, q.key, q.value, next); 255 transferLinks(q, t); 256 return t; 257 } 258 259 override void afterNodeRemoval(HashMapNode!(K, V) e) { // unlink 260 LinkedHashMapEntry!(K, V)p = 261 cast(LinkedHashMapEntry!(K, V))e, b = p.before, a = p.after; 262 p.before = p.after = null; 263 if (b is null) 264 head = a; 265 else 266 b.after = a; 267 if (a is null) 268 tail = b; 269 else 270 a.before = b; 271 } 272 273 override void afterNodeInsertion(bool evict) { // possibly remove eldest 274 LinkedHashMapEntry!(K, V) first; 275 if (evict && (first = head) !is null && removeEldestEntry(first)) { 276 K key = first.key; 277 removeNode(hash(key), key, null, false, true); 278 } 279 } 280 281 override void afterNodeAccess(HashMapNode!(K, V) e) { // move node to last 282 LinkedHashMapEntry!(K, V)last; 283 if (accessOrder && (last = tail) != e) { 284 LinkedHashMapEntry!(K, V)p = 285 cast(LinkedHashMapEntry!(K, V))e, b = p.before, a = p.after; 286 p.after = null; 287 if (b is null) 288 head = a; 289 else 290 b.after = a; 291 if (a !is null) 292 a.before = b; 293 else 294 last = b; 295 if (last is null) 296 head = p; 297 else { 298 p.before = last; 299 last.after = p; 300 } 301 tail = p; 302 ++modCount; 303 } 304 } 305 306 // void internalWriteEntries(java.io.ObjectOutputStream s) { 307 // for (LinkedHashMapEntry!(K, V)e = head; e !is null; e = e.after) { 308 // s.writeObject(e.key); 309 // s.writeObject(e.value); 310 // } 311 // } 312 313 /** 314 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance 315 * with the specified initial capacity and load factor. 316 * 317 * @param initialCapacity the initial capacity 318 * @param loadFactor the load factor 319 * @throws IllegalArgumentException if the initial capacity is negative 320 * or the load factor is nonpositive 321 */ 322 this(int initialCapacity, float loadFactor) { 323 super(initialCapacity, loadFactor); 324 accessOrder = false; 325 } 326 327 /** 328 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance 329 * with the specified initial capacity and a default load factor (0.75). 330 * 331 * @param initialCapacity the initial capacity 332 * @throws IllegalArgumentException if the initial capacity is negative 333 */ 334 this(int initialCapacity) { 335 super(initialCapacity); 336 accessOrder = false; 337 } 338 339 /** 340 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance 341 * with the default initial capacity (16) and load factor (0.75). 342 */ 343 this() { 344 super(); 345 accessOrder = false; 346 } 347 348 /** 349 * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with 350 * the same mappings as the specified map. The <tt>LinkedHashMap</tt> 351 * instance is created with a default load factor (0.75) and an initial 352 * capacity sufficient to hold the mappings in the specified map. 353 * 354 * @param m the map whose mappings are to be placed in this map 355 * @throws NullPointerException if the specified map is null 356 */ 357 this(Map!(K, V) m) { 358 super(); 359 accessOrder = false; 360 putMapEntries(m, false); 361 } 362 363 /** 364 * Constructs an empty <tt>LinkedHashMap</tt> instance with the 365 * specified initial capacity, load factor and ordering mode. 366 * 367 * @param initialCapacity the initial capacity 368 * @param loadFactor the load factor 369 * @param accessOrder the ordering mode - <tt>true</tt> for 370 * access-order, <tt>false</tt> for insertion-order 371 * @throws IllegalArgumentException if the initial capacity is negative 372 * or the load factor is nonpositive 373 */ 374 this(int initialCapacity, 375 float loadFactor, 376 bool accessOrder) { 377 super(initialCapacity, loadFactor); 378 this.accessOrder = accessOrder; 379 } 380 381 382 /** 383 * Returns <tt>true</tt> if this map maps one or more keys to the 384 * specified value. 385 * 386 * @param value value whose presence in this map is to be tested 387 * @return <tt>true</tt> if this map maps one or more keys to the 388 * specified value 389 */ 390 override bool containsValue(V value) { 391 for (LinkedHashMapEntry!(K, V)e = head; e !is null; e = e.after) { 392 V v = e.value; 393 if (v == value) // || (value !is null && value.equals(v)) 394 return true; 395 } 396 return false; 397 } 398 399 /** 400 * Returns the value to which the specified key is mapped, 401 * or {@code null} if this map contains no mapping for the key. 402 * 403 * <p>More formally, if this map contains a mapping from a key 404 * {@code k} to a value {@code v} such that {@code (key==null ? k==null : 405 * key.equals(k))}, then this method returns {@code v}; otherwise 406 * it returns {@code null}. (There can be at most one such mapping.) 407 * 408 * <p>A return value of {@code null} does not <i>necessarily</i> 409 * indicate that the map contains no mapping for the key; it's also 410 * possible that the map explicitly maps the key to {@code null}. 411 * The {@link #containsKey containsKey} operation may be used to 412 * distinguish these two cases. 413 */ 414 override V get(K key) { 415 HashMapNode!(K, V) e = getNode(hash(key), key); 416 if (e is null) 417 return null; 418 if (accessOrder) 419 afterNodeAccess(e); 420 return e.value; 421 } 422 423 /** 424 * {@inheritDoc} 425 */ 426 override V getOrDefault(K key, V defaultValue) { 427 HashMapNode!(K, V) e; 428 if ((e = getNode(hash(key), key)) is null) 429 return defaultValue; 430 if (accessOrder) 431 afterNodeAccess(e); 432 return e.value; 433 } 434 435 /** 436 * {@inheritDoc} 437 */ 438 override void clear() { 439 super.clear(); 440 head = tail = null; 441 } 442 443 /** 444 * Returns <tt>true</tt> if this map should remove its eldest entry. 445 * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after 446 * inserting a new entry into the map. It provides the implementor 447 * with the opportunity to remove the eldest entry each time a new one 448 * is added. This is useful if the map represents a cache: it allows 449 * the map to reduce memory consumption by deleting stale entries. 450 * 451 * <p>Sample use: this override will allow the map to grow up to 100 452 * entries and then delete the eldest entry each time a new entry is 453 * added, maintaining a steady state of 100 entries. 454 * <pre> 455 * private static final int MAX_ENTRIES = 100; 456 * 457 * protected bool removeEldestEntry(MapEntry eldest) { 458 * return size() > MAX_ENTRIES; 459 * } 460 * </pre> 461 * 462 * <p>This method typically does not modify the map in any way, 463 * instead allowing the map to modify itself as directed by its 464 * return value. It <i>is</i> permitted for this method to modify 465 * the map directly, but if it does so, it <i>must</i> return 466 * <tt>false</tt> (indicating that the map should not attempt any 467 * further modification). The effects of returning <tt>true</tt> 468 * after modifying the map from within this method are unspecified. 469 * 470 * <p>This implementation merely returns <tt>false</tt> (so that this 471 * map acts like a normal map - the eldest element is never removed). 472 * 473 * @param eldest The least recently inserted entry in the map, or if 474 * this is an access-ordered map, the least recently accessed 475 * entry. This is the entry that will be removed it this 476 * method returns <tt>true</tt>. If the map was empty prior 477 * to the <tt>put</tt> or <tt>putAll</tt> invocation resulting 478 * in this invocation, this will be the entry that was just 479 * inserted; in other words, if the map contains a single 480 * entry, the eldest entry is also the newest. 481 * @return <tt>true</tt> if the eldest entry should be removed 482 * from the map; <tt>false</tt> if it should be retained. 483 */ 484 protected bool removeEldestEntry(MapEntry!(K, V) eldest) { 485 return false; 486 } 487 488 /** 489 * Returns a {@link Set} view of the keys contained in this map. 490 * The set is backed by the map, so changes to the map are 491 * reflected in the set, and vice-versa. If the map is modified 492 * while an iteration over the set is in progress (except through 493 * the iterator's own <tt>remove</tt> operation), the results of 494 * the iteration are undefined. The set supports element removal, 495 * which removes the corresponding mapping from the map, via the 496 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 497 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 498 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> 499 * operations. 500 * Its {@link Spliterator} typically provides faster sequential 501 * performance but much poorer parallel performance than that of 502 * {@code HashMap}. 503 * 504 * @return a set view of the keys contained in this map 505 */ 506 // Set!(K) keySet() { 507 // Set!(K) ks = keySet; 508 // if (ks is null) { 509 // ks = new LinkedKeySet(); 510 // keySet = ks; 511 // } 512 // return ks; 513 // } 514 515 // final class LinkedKeySet : AbstractSet!(K) { 516 // final int size() { return size; } 517 // final void clear() { LinkedHashMap.this.clear(); } 518 // final Iterator!(K) iterator() { 519 // return new LinkedKeyIterator(); 520 // } 521 // final bool contains(Object o) { return containsKey(o); } 522 // final bool remove(Object key) { 523 // return removeNode(hash(key), key, null, false, true) !is null; 524 // } 525 // final Spliterator!(K) spliterator() { 526 // return Spliterators.spliterator(this, Spliterator.SIZED | 527 // Spliterator.ORDERED | 528 // Spliterator.DISTINCT); 529 // } 530 // final void forEach(Consumer<K> action) { 531 // if (action is null) 532 // throw new NullPointerException(); 533 // int mc = modCount; 534 // for (LinkedHashMapEntry!(K, V)e = head; e !is null; e = e.after) 535 // action.accept(e.key); 536 // if (modCount != mc) 537 // throw new ConcurrentModificationException(); 538 // } 539 // } 540 541 /** 542 * Returns a {@link Collection} view of the values contained in this map. 543 * The collection is backed by the map, so changes to the map are 544 * reflected in the collection, and vice-versa. If the map is 545 * modified while an iteration over the collection is in progress 546 * (except through the iterator's own <tt>remove</tt> operation), 547 * the results of the iteration are undefined. The collection 548 * supports element removal, which removes the corresponding 549 * mapping from the map, via the <tt>Iterator.remove</tt>, 550 * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 551 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not 552 * support the <tt>add</tt> or <tt>addAll</tt> operations. 553 * Its {@link Spliterator} typically provides faster sequential 554 * performance but much poorer parallel performance than that of 555 * {@code HashMap}. 556 * 557 * @return a view of the values contained in this map 558 */ 559 // Collection!(V) values() { 560 // Collection!(V) vs = values; 561 // if (vs is null) { 562 // vs = new LinkedValues(); 563 // values = vs; 564 // } 565 // return vs; 566 // } 567 568 // final class LinkedValues : AbstractCollection!(V) { 569 // final override int size() { return _size; } 570 // final override void clear() { this.outer.clear(); } 571 // // final Iterator!(V) iterator() { 572 // // return new LinkedValueIterator(); 573 // // } 574 // final bool contains(Object o) { return containsValue(o); } 575 // // final Spliterator!(V) spliterator() { 576 // // return Spliterators.spliterator(this, Spliterator.SIZED | 577 // // Spliterator.ORDERED); 578 // // } 579 // // final void forEach(Consumer<V> action) { 580 // // if (action is null) 581 // // throw new NullPointerException(); 582 // // int mc = modCount; 583 // // for (LinkedHashMapEntry!(K, V)e = head; e !is null; e = e.after) 584 // // action.accept(e.value); 585 // // if (modCount != mc) 586 // // throw new ConcurrentModificationException(); 587 // // } 588 // } 589 590 /** 591 * Returns a {@link Set} view of the mappings contained in this map. 592 * The set is backed by the map, so changes to the map are 593 * reflected in the set, and vice-versa. If the map is modified 594 * while an iteration over the set is in progress (except through 595 * the iterator's own <tt>remove</tt> operation, or through the 596 * <tt>setValue</tt> operation on a map entry returned by the 597 * iterator) the results of the iteration are undefined. The set 598 * supports element removal, which removes the corresponding 599 * mapping from the map, via the <tt>Iterator.remove</tt>, 600 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and 601 * <tt>clear</tt> operations. It does not support the 602 * <tt>add</tt> or <tt>addAll</tt> operations. 603 * Its {@link Spliterator} typically provides faster sequential 604 * performance but much poorer parallel performance than that of 605 * {@code HashMap}. 606 * 607 * @return a set view of the mappings contained in this map 608 */ 609 // Set!(MapEntry!(K, V)) entrySet() { 610 // Set!(MapEntry!(K, V)) es; 611 // return (es = entrySet) is null ? (entrySet = new LinkedEntrySet()) : es; 612 // } 613 614 // final class LinkedEntrySet : AbstractSet!(MapEntry!(K, V)) { 615 // final int size() { return size; } 616 // final void clear() { this.outer.clear(); } 617 // final Iterator!(MapEntry!(K, V)) iterator() { 618 // return new LinkedEntryIterator(); 619 // } 620 // // final bool contains(Object o) { 621 // // if (!(o instanceof MapEntry)) 622 // // return false; 623 // // MapEntry<?,?> e = (MapEntry<?,?>) o; 624 // // Object key = e.getKey(); 625 // // HashMapNode!(K, V) candidate = getNode(hash(key), key); 626 // // return candidate !is null && candidate.equals(e); 627 // // } 628 // // final bool remove(Object o) { 629 // // if (o instanceof MapEntry) { 630 // // MapEntry<?,?> e = (MapEntry<?,?>) o; 631 // // Object key = e.getKey(); 632 // // Object value = e.getValue(); 633 // // return removeNode(hash(key), key, value, true, true) !is null; 634 // // } 635 // // return false; 636 // // } 637 // // final Spliterator!(MapEntry!(K, V)) spliterator() { 638 // // return Spliterators.spliterator(this, Spliterator.SIZED | 639 // // Spliterator.ORDERED | 640 // // Spliterator.DISTINCT); 641 // // } 642 // // final void forEach(Consumer<MapEntry!(K, V)> action) { 643 // // if (action is null) 644 // // throw new NullPointerException(); 645 // // int mc = modCount; 646 // // for (LinkedHashMapEntry!(K, V)e = head; e !is null; e = e.after) 647 // // action.accept(e); 648 // // if (modCount != mc) 649 // // throw new ConcurrentModificationException(); 650 // // } 651 // } 652 653 // Map overrides 654 655 // void replaceAll(BiFunction<K, V, ? : V> function) { 656 // if (function is null) 657 // throw new NullPointerException(); 658 // int mc = modCount; 659 // for (LinkedHashMapEntry!(K, V)e = head; e !is null; e = e.after) 660 // e.value = function.apply(e.key, e.value); 661 // if (modCount != mc) 662 // throw new ConcurrentModificationException(); 663 // } 664 665 // Iterators 666 667 override int opApply(scope int delegate(ref K, ref V) dg) 668 { 669 if(dg is null) 670 throw new NullPointerException(""); 671 672 int result = 0; 673 int mc = modCount; 674 for (LinkedHashMapEntry!(K, V)e = head; e !is null; e = e.after) 675 { 676 result = dg(e.key, e.value); 677 if(result != 0) return result; 678 } 679 680 if(modCount != mc) 681 throw new ConcurrentModificationException(); 682 683 return result; 684 } 685 686 override int opApply(scope int delegate(MapEntry!(K, V) entry) dg) 687 { 688 if(dg is null) 689 throw new NullPointerException(); 690 691 int result = 0; 692 int mc = modCount; 693 for (LinkedHashMapEntry!(K, V)e = head; e !is null; e = e.after) 694 { 695 result = dg(e); 696 if(result != 0) return result; 697 } 698 699 if(modCount != mc) 700 throw new ConcurrentModificationException(); 701 702 return result; 703 } 704 705 override InputRange!K byKey() 706 { 707 return new KeyInputRange(); 708 } 709 710 override InputRange!V byValue() 711 { 712 return new ValueInputRange(); 713 } 714 715 mixin template LinkedHashMapIterator() { 716 private LinkedHashMapEntry!(K, V) next; 717 private LinkedHashMapEntry!(K, V) current; 718 private int expectedModCount; 719 720 this() { 721 next = head; 722 expectedModCount = modCount; 723 current = null; 724 } 725 726 final bool empty() { 727 return next is null; 728 } 729 730 void popFront() 731 { 732 LinkedHashMapEntry!(K, V) e = next; 733 if (modCount != expectedModCount) 734 throw new ConcurrentModificationException(); 735 if (e is null) 736 throw new NoSuchElementException(); 737 current = e; 738 next = e.after; 739 // return e; 740 } 741 } 742 743 final class KeyInputRange : InputRange!K { 744 mixin LinkedHashMapIterator; 745 746 final K front() @property { return next.key; } 747 748 // https://forum.dlang.org/thread/amzthhonuozlobghqqgk@forum.dlang.org?page=1 749 // https://issues.dlang.org/show_bug.cgi?id=18036 750 final K moveFront() @property { throw new NotSupportedException(); } 751 752 int opApply(scope int delegate(K) dg) { 753 if(dg is null) 754 throw new NullPointerException(); 755 756 int result = 0; 757 int mc = modCount; 758 for (LinkedHashMapEntry!(K, V)e = head; e !is null; e = e.after) 759 { 760 result = dg(e.key); 761 if(result != 0) return result; 762 } 763 764 if(modCount != mc) 765 throw new ConcurrentModificationException(); 766 767 return result; 768 } 769 770 int opApply(scope int delegate(size_t, K) dg) { 771 if(dg is null) 772 throw new NullPointerException(); 773 774 int result = 0; 775 int mc = modCount; 776 size_t index = 0; 777 for (LinkedHashMapEntry!(K, V)e = head; e !is null; e = e.after) 778 { 779 result = dg(index++, e.key); 780 if(result != 0) return result; 781 } 782 783 if(modCount != mc) 784 throw new ConcurrentModificationException(); 785 786 return result; 787 } 788 } 789 790 final class ValueInputRange : InputRange!V { 791 mixin LinkedHashMapIterator; 792 793 final V front() @property { return next.value; } 794 795 final V moveFront() @property { throw new NotSupportedException(); } 796 797 int opApply(scope int delegate(V) dg) { 798 if(dg is null) 799 throw new NullPointerException(); 800 801 int result = 0; 802 int mc = modCount; 803 for (LinkedHashMapEntry!(K, V)e = head; e !is null; e = e.after) 804 { 805 result = dg(e.value); 806 if(result != 0) return result; 807 } 808 809 if(modCount != mc) 810 throw new ConcurrentModificationException(); 811 812 return result; 813 } 814 815 int opApply(scope int delegate(size_t, V) dg) { 816 if(dg is null) 817 throw new NullPointerException(); 818 819 int result = 0; 820 int mc = modCount; 821 size_t index = 0; 822 for (LinkedHashMapEntry!(K, V)e = head; e !is null; e = e.after) { 823 result = dg(index++, e.value); 824 if(result != 0) return result; 825 } 826 827 if(modCount != mc) 828 throw new ConcurrentModificationException(); 829 830 return result; 831 } 832 } 833 834 835 } 836