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.HashMap;
13 
14 import hunt.collection.AbstractMap;
15 import hunt.collection.Map;
16 import hunt.collection.Iterator;
17 
18 import hunt.Exceptions;
19 import hunt.Object;
20 import hunt.text.StringBuilder;
21 
22 import std.algorithm;
23 import std.conv;
24 import std.format: format;
25 import std.math;
26 import std.range;
27 import std.traits;
28 
29 /**
30 */
31 class HashMap(K,V) : AbstractMap!(K,V) {
32 
33     // private enum long serialVersionUID = 362498820763181265L;
34 
35     /*
36      * Implementation notes.
37      *
38      * This map usually acts as a binned (bucketed) hash table, but
39      * when bins get too large, they are transformed into bins of
40      * TreeNodes, each structured similarly to those in
41      * java.util.TreeMap. Most methods try to use normal bins, but
42      * relay to TreeNode methods when applicable (simply by checking
43      * instanceof a node).  Bins of TreeNodes may be traversed and
44      * used like any others, but additionally support faster lookup
45      * when overpopulated. However, since the vast majority of bins in
46      * normal use are not overpopulated, checking for existence of
47      * tree bins may be delayed in the course of table methods.
48      *
49      * Tree bins (i.e., bins whose elements are all TreeNodes) are
50      * ordered primarily by toHash, but in the case of ties, if two
51      * elements are of the same "class C implements Comparable<C>",
52      * type then their compareTo method is used for ordering. (We
53      * conservatively check generic types via reflection to validate
54      * this -- see method comparableClassFor).  The added complexity
55      * of tree bins is worthwhile in providing worst-case O(log n)
56      * operations when keys either have distinct hashes or are
57      * orderable, Thus, performance degrades gracefully under
58      * accidental or malicious usages in which toHash() methods
59      * return values that are poorly distributed, as well as those in
60      * which many keys share a toHash, so long as they are also
61      * Comparable. (If neither of these apply, we may waste about a
62      * factor of two in time and space compared to taking no
63      * precautions. But the only known cases stem from poor user
64      * programming practices that are already so slow that this makes
65      * little difference.)
66      *
67      * Because TreeNodes are about twice the size of regular nodes, we
68      * use them only when bins contain enough nodes to warrant use
69      * (see TREEIFY_THRESHOLD). And when they become too small (due to
70      * removal or resizing) they are converted back to plain bins.  In
71      * usages with well-distributed user hashCodes, tree bins are
72      * rarely used.  Ideally, under random hashCodes, the frequency of
73      * nodes in bins follows a Poisson distribution
74      * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
75      * parameter of about 0.5 on average for the default resizing
76      * threshold of 0.75, although with a large variance because of
77      * resizing granularity. Ignoring variance, the expected
78      * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
79      * factorial(k)). The first values are:
80      *
81      * 0:    0.60653066
82      * 1:    0.30326533
83      * 2:    0.07581633
84      * 3:    0.01263606
85      * 4:    0.00157952
86      * 5:    0.00015795
87      * 6:    0.00001316
88      * 7:    0.00000094
89      * 8:    0.00000006
90      * more: less than 1 in ten million
91      *
92      * The root of a tree bin is normally its first node.  However,
93      * sometimes (currently only upon Iterator.remove), the root might
94      * be elsewhere, but can be recovered following parent links
95      * (method TreeNode.root()).
96      *
97      * All applicable internal methods accept a hash code as an
98      * argument (as normally supplied from a method), allowing
99      * them to call each other without recomputing user hashCodes.
100      * Most internal methods also accept a "tab" argument, that is
101      * normally the current table, but may be a new or old one when
102      * resizing or converting.
103      *
104      * When bin lists are treeified, split, or untreeified, we keep
105      * them in the same relative access/traversal order (i.e., field
106      * Node.next) to better preserve locality, and to slightly
107      * simplify handling of splits and traversals that invoke
108      * iterator.remove. When using comparators on insertion, to keep a
109      * total ordering (or as close as is required here) across
110      * rebalancings, we compare classes and identityHashCodes as
111      * tie-breakers.
112      *
113      * The use and transitions among plain vs tree modes is
114      * complicated by the existence of subclass LinkedHashMap. See
115      * below for hook methods defined to be invoked upon insertion,
116      * removal and access that allow LinkedHashMap internals to
117      * otherwise remain independent of these mechanics. (This also
118      * requires that a map instance be passed to some utility methods
119      * that may create new nodes.)
120      *
121      * The concurrent-programming-like SSA-based coding style helps
122      * avoid aliasing errors amid all of the twisty pointer operations.
123      */
124 
125     /**
126      * The default initial capacity - MUST be a power of two.
127      */
128     enum int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
129 
130     /**
131      * The maximum capacity, used if a higher value is implicitly specified
132      * by either of the constructors with arguments.
133      * MUST be a power of two <= 1<<30.
134      */
135     enum int MAXIMUM_CAPACITY = 1 << 30;
136 
137     /**
138      * The load factor used when none specified in constructor.
139      */
140     enum float DEFAULT_LOAD_FACTOR = 0.75f;
141 
142     /**
143      * The bin count threshold for using a tree rather than list for a
144      * bin.  Bins are converted to trees when adding an element to a
145      * bin with at least this many nodes. The value must be greater
146      * than 2 and should be at least 8 to mesh with assumptions in
147      * tree removal about conversion back to plain bins upon
148      * shrinkage.
149      */
150     enum int TREEIFY_THRESHOLD = 8;
151 
152     /**
153      * The smallest table capacity for which bins may be treeified.
154      * (Otherwise the table is resized if too many nodes in a bin.)
155      * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
156      * between resizing and treeification thresholds.
157      */
158     enum int MIN_TREEIFY_CAPACITY = 64;
159 
160     /* ---------------- Static utilities -------------- */
161 
162     /**
163      * Computes key.toHash() and spreads (XORs) higher bits of hash
164      * to lower.  Because the table uses power-of-two masking, sets of
165      * hashes that vary only in bits above the current mask will
166      * always collide. (Among known examples are sets of Float keys
167      * holding consecutive whole numbers in small tables.)  So we
168      * apply a transform that spreads the impact of higher bits
169      * downward. There is a tradeoff between speed, utility, and
170      * quality of bit-spreading. Because many common sets of hashes
171      * are already reasonably distributed (so don't benefit from
172      * spreading), and because we use trees to handle large sets of
173      * collisions in bins, we just XOR some shifted bits in the
174      * cheapest possible way to reduce systematic lossage, as well as
175      * to incorporate impact of the highest bits that would otherwise
176      * never be used in index calculations because of table bounds.
177      */
178     static size_t hash(K key) {
179         size_t h;
180         static if(is(K == class)) {
181             return (key is null) ? 0 : (h = key.toHash()) ^ (h >>> 16);
182         }
183         else {
184             h = hashOf(key);
185             return  h ^ (h >>> 16);
186         }
187     }
188 
189     /**
190      * Returns x's Class if it is of the form "class C implements
191      * Comparable<C>", else null.
192      */
193     // static Class<?> comparableClassFor(Object x) {
194     //     if (x instanceof Comparable) {
195     //         Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
196     //         if ((c = x.getClass()) == string.class) // bypass checks
197     //             return c;
198     //         if ((ts = c.getGenericInterfaces()) !is null) {
199     //             for (int i = 0; i < ts.length; ++i) {
200     //                 if (((t = ts[i]) instanceof ParameterizedType) &&
201     //                     ((p = (ParameterizedType)t).getRawType() ==
202     //                      Comparable.class) &&
203     //                     (as = p.getActualTypeArguments()) !is null &&
204     //                     as.length == 1 && as[0] == c) // type arg is c
205     //                     return c;
206     //             }
207     //         }
208     //     }
209     //     return null;
210     // }
211 
212     /**
213      * Returns k.compareTo(x) if x matches kc (k's screened comparable
214      * class), else 0.
215      */
216     //  // for cast to Comparable
217     // static int compareComparables(Class<?> kc, Object k, Object x) {
218     //     return (x is null || x.getClass() != kc ? 0 :
219     //             ((Comparable)k).compareTo(x));
220     // }
221 
222     /**
223      * Returns a power of two size for the given target capacity.
224      */
225     static final int tableSizeFor(int cap) {
226         int n = cap - 1;
227         n |= n >>> 1;
228         n |= n >>> 2;
229         n |= n >>> 4;
230         n |= n >>> 8;
231         n |= n >>> 16;
232         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
233     }
234 
235     /* ---------------- Fields -------------- */
236 
237     /**
238      * The table, initialized on first use, and resized as
239      * necessary. When allocated, length is always a power of two.
240      * (We also tolerate length zero in some operations to allow
241      * bootstrapping mechanics that are currently not needed.)
242      */
243     HashMapNode!(K,V)[] table;
244 
245     /**
246      * Holds cached entrySet(). Note that AbstractMap fields are used
247      * for keySet() and values().
248      */
249     // Set<MapEntry!(K,V)> entrySet;
250 
251     /**
252      * The number of key-value mappings contained in this map.
253      */
254     // int _size;
255 
256     /**
257      * The number of times this HashMap has been structurally modified
258      * Structural modifications are those that change the number of mappings in
259      * the HashMap or otherwise modify its internal structure (e.g.,
260      * rehash).  This field is used to make iterators on Collection-views of
261      * the HashMap fail-fast.  (See ConcurrentModificationException).
262      */
263     int modCount;
264 
265     /**
266      * The next size value at which to resize (capacity * load factor).
267      *
268      * @serial
269      */
270     // (The javadoc description is true upon serialization.
271     // Additionally, if the table array has not been allocated, this
272     // field holds the initial array capacity, or zero signifying
273     // DEFAULT_INITIAL_CAPACITY.)
274     int threshold;
275 
276     /**
277      * The load factor for the hash table.
278      *
279      * @serial
280      */
281     float loadFactor;
282 
283     /* ---------------- Public operations -------------- */
284 
285     /**
286      * Constructs an empty <tt>HashMap</tt> with the specified initial
287      * capacity and load factor.
288      *
289      * @param  initialCapacity the initial capacity
290      * @param  loadFactor      the load factor
291      * @throws IllegalArgumentException if the initial capacity is negative
292      *         or the load factor is nonpositive
293      */
294     this(int initialCapacity, float loadFactor) {
295         if (initialCapacity < 0)
296             throw new IllegalArgumentException("Illegal initial capacity: " ~
297                                                initialCapacity.to!string());
298         if (initialCapacity > MAXIMUM_CAPACITY)
299             initialCapacity = MAXIMUM_CAPACITY;
300         if (loadFactor <= 0 || isNaN(loadFactor))
301             throw new IllegalArgumentException("Illegal load factor: " ~
302                                                loadFactor.to!string());
303         this.loadFactor = loadFactor;
304         this.threshold = tableSizeFor(initialCapacity);
305     }
306 
307     /**
308      * Constructs an empty <tt>HashMap</tt> with the specified initial
309      * capacity and the default load factor (0.75).
310      *
311      * @param  initialCapacity the initial capacity.
312      * @throws IllegalArgumentException if the initial capacity is negative.
313      */
314     this(int initialCapacity) {
315         this(initialCapacity, DEFAULT_LOAD_FACTOR);
316     }
317 
318     /**
319      * Constructs an empty <tt>HashMap</tt> with the default initial capacity
320      * (16) and the default load factor (0.75).
321      */
322     this() {
323         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
324     }
325 
326     /**
327      * Constructs a new <tt>HashMap</tt> with the same mappings as the
328      * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
329      * default load factor (0.75) and an initial capacity sufficient to
330      * hold the mappings in the specified <tt>Map</tt>.
331      *
332      * @param   m the map whose mappings are to be placed in this map
333      * @throws  NullPointerException if the specified map is null
334      */
335     this(Map!(K, V) m) {
336         this.loadFactor = DEFAULT_LOAD_FACTOR;
337         putMapEntries(m, false);
338     }
339 
340     /**
341      * Implements Map.putAll and Map constructor
342      *
343      * @param m the map
344      * @param evict false when initially constructing this map, else
345      * true (relayed to method afterNodeInsertion).
346      */
347     final void putMapEntries(Map!(K, V) m, bool evict) {
348         // throw new NotImplementedException("");
349         int s = m.size();
350         if (s > 0) {
351             if (table is null) { // pre-size
352                 float ft = (cast(float)s / loadFactor) + 1.0F;
353                 int t = ((ft < cast(float)MAXIMUM_CAPACITY) ?
354                          cast(int)ft : MAXIMUM_CAPACITY);
355                 if (t > threshold)
356                     threshold = tableSizeFor(t);
357             }
358             else if (s > threshold)
359                 resize();
360             // for (MapEntry!(K, V) e : m.entrySet()) {
361             foreach(K key, V value; m) {
362                 // K key = e.getKey();
363                 // V value = e.getValue();
364                 putVal(hash(key), key, value, false, evict);
365             }
366         }
367     }
368 
369   
370     /**
371      * Returns the value to which the specified key is mapped,
372      * or {@code null} if this map contains no mapping for the key.
373      *
374      * <p>More formally, if this map contains a mapping from a key
375      * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
376      * key.equals(k))}, then this method returns {@code v}; otherwise
377      * it returns {@code null}.  (There can be at most one such mapping.)
378      *
379      * <p>A return value of {@code null} does not <i>necessarily</i>
380      * indicate that the map contains no mapping for the key; it's also
381      * possible that the map explicitly maps the key to {@code null}.
382      * The {@link #containsKey containsKey} operation may be used to
383      * distinguish these two cases.
384      *
385      * @see #put(Object, Object)
386      */
387     override V get(K key) {
388         HashMapNode!(K, V) e = getNode(hash(key), key);
389         return e is null ? V.init : e.value;
390     }
391 
392     /**
393      * Implements Map.get and related methods
394      *
395      * @param hash hash for key
396      * @param key the key
397      * @return the node, or null if none
398      */
399     final HashMapNode!(K, V) getNode(size_t hash, K key) {
400         HashMapNode!(K, V)[] tab; HashMapNode!(K, V) first, e; size_t n; K k;
401         if ((tab = table) !is null && (n = tab.length) > 0 &&
402             (first = tab[(n - 1) & hash]) !is null) {
403             k = first.key;
404             if (first.hash == hash && // always check first node
405                 k == key )
406                 return first;
407             if ((e = first.next) !is null) {
408                 auto tempNode = cast(TreeNode!(K, V))first;
409                 if (tempNode !is null)
410                     return tempNode.getTreeNode(hash, key);
411                 do {
412                     k = e.key;
413                     if (e.hash == hash && k == key)
414                         return e;
415                 } while ((e = e.next) !is null);
416             }
417         }
418         return null;
419     }
420 
421     /**
422      * Returns <tt>true</tt> if this map contains a mapping for the
423      * specified key.
424      *
425      * @param   key   The key whose presence in this map is to be tested
426      * @return <tt>true</tt> if this map contains a mapping for the specified
427      * key.
428      */
429     override bool containsKey(K key) {
430         return getNode(hash(key), key) !is null;
431     }
432 
433     /**
434      * Associates the specified value with the specified key in this map.
435      * If the map previously contained a mapping for the key, the old
436      * value is replaced.
437      *
438      * @param key key with which the specified value is to be associated
439      * @param value value to be associated with the specified key
440      * @return the previous value associated with <tt>key</tt>, or
441      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
442      *         (A <tt>null</tt> return can also indicate that the map
443      *         previously associated <tt>null</tt> with <tt>key</tt>.)
444      */
445     override V put(K key, V value) {
446         return putVal(hash(key), key, value, false, true);
447     }
448 
449     /**
450      * Implements Map.put and related methods
451      *
452      * @param hash hash for key
453      * @param key the key
454      * @param value the value to put
455      * @param onlyIfAbsent if true, don't change existing value
456      * @param evict if false, the table is in creation mode.
457      * @return previous value, or null if none
458      */
459     final V putVal(size_t hash, K key, V value, bool onlyIfAbsent, bool evict) {
460         HashMapNode!(K, V)[] tab; HashMapNode!(K, V) p; 
461         size_t n;
462         if ((tab = table) is null || (n = tab.length) == 0)
463             n = (tab = resize()).length;
464 
465         size_t i = (n - 1) & hash;
466         if ((p = tab[i]) is null) {
467             tab[i] = newNode(hash, key, value, null);
468         }
469         else {
470             HashMapNode!(K, V) e; K k;
471             k = p.key;
472             if (p.hash == hash && k == key)
473                 e = p;
474             else{
475                 TreeNode!(K, V) pp = cast(TreeNode!(K, V))p;
476                 if (pp !is null)
477                     e = pp.putTreeVal(this, tab, hash, key, value);
478                 else {
479                     for (int binCount = 0; ; ++binCount) {
480                         if ((e = p.next) is null) {
481                             p.next = newNode(hash, key, value, null);
482                             if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
483                                 treeifyBin(tab, hash);
484                             break;
485                         }
486                         k = e.key;
487                         if (e.hash == hash && k == key )
488                             break;
489                         p = e;
490                     }
491                 }
492             }
493 
494             if (e !is null) { // existing mapping for key
495                 V oldValue = e.value;
496                 static if( is(V == class)) {
497                     if (!onlyIfAbsent || oldValue is null)
498                         e.value = value;
499                 }
500                 else {
501                     if (!onlyIfAbsent)
502                         e.value = value;
503                 }
504                 afterNodeAccess(e);
505                 return oldValue;
506             }
507         }
508         ++modCount;
509         if (++_size > threshold)
510             resize();
511         afterNodeInsertion(evict);
512         return V.init;                       
513     }
514 
515   
516     /**
517      * Initializes or doubles table size.  If null, allocates in
518      * accord with initial capacity target held in field threshold.
519      * Otherwise, because we are using power-of-two expansion, the
520      * elements from each bin must either stay at same index, or move
521      * with a power of two offset in the new table.
522      *
523      * @return the table
524      */
525     final HashMapNode!(K,V)[] resize() {
526         HashMapNode!(K,V)[] oldTab = table;
527         int oldCap = (oldTab is null) ? 0 : cast(int)oldTab.length;
528         int oldThr = threshold;
529         int newCap, newThr = 0;
530         if (oldCap > 0) {
531             if (oldCap >= MAXIMUM_CAPACITY) {
532                 threshold = int.max;
533                 return oldTab;
534             }
535             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
536                      oldCap >= DEFAULT_INITIAL_CAPACITY)
537                 newThr = oldThr << 1; // double threshold
538         }
539         else if (oldThr > 0) // initial capacity was placed in threshold
540             newCap = oldThr;
541         else {               // zero initial threshold signifies using defaults
542             newCap = DEFAULT_INITIAL_CAPACITY;
543             newThr = cast(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
544         }
545         if (newThr == 0) {
546             float ft = cast(float)newCap * loadFactor;
547             newThr = (newCap < MAXIMUM_CAPACITY && ft < cast(float)MAXIMUM_CAPACITY ?
548                       cast(int)ft : int.max);
549         }
550         threshold = newThr;
551 
552         HashMapNode!(K,V)[] newTab = new HashMapNode!(K,V)[newCap];
553         TreeNode!(K,V) ee;
554         table = newTab;
555         if (oldTab !is null) {
556             for (int j = 0; j < oldCap; ++j) {
557                 HashMapNode!(K,V) e;
558                 if ((e = oldTab[j]) !is null) {
559                     oldTab[j] = null;
560                     if (e.next is null)
561                         newTab[e.hash & (newCap - 1)] = e;
562                     else if ((ee = cast(TreeNode!(K,V))e) !is null)
563                         ee.split(this, newTab, j, oldCap);
564                     else { // preserve order
565                         HashMapNode!(K,V) loHead = null, loTail = null;
566                         HashMapNode!(K,V) hiHead = null, hiTail = null;
567                         HashMapNode!(K,V) next;
568                         do {
569                             next = e.next;
570                             if ((e.hash & oldCap) == 0) {
571                                 if (loTail is null)
572                                     loHead = e;
573                                 else
574                                     loTail.next = e;
575                                 loTail = e;
576                             }
577                             else {
578                                 if (hiTail is null)
579                                     hiHead = e;
580                                 else
581                                     hiTail.next = e;
582                                 hiTail = e;
583                             }
584                         } while ((e = next) !is null);
585                         if (loTail !is null) {
586                             loTail.next = null;
587                             newTab[j] = loHead;
588                         }
589                         if (hiTail !is null) {
590                             hiTail.next = null;
591                             newTab[j + oldCap] = hiHead;
592                         }
593                     }
594                 }
595             }
596         }
597         return newTab;
598     }
599 
600     /**
601      * Replaces all linked nodes in bin at index for given hash unless
602      * table is too small, in which case resizes instead.
603      */
604     final void treeifyBin(HashMapNode!(K,V)[] tab, size_t hash) {
605         size_t n, index; HashMapNode!(K,V) e;
606         if (tab is null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
607             resize();
608         else if ((e = tab[index = (n - 1) & hash]) !is null) {
609             TreeNode!(K,V) hd = null, tl = null;
610             do {
611                 TreeNode!(K,V) p = replacementTreeNode(e, null);
612                 if (tl is null)
613                     hd = p;
614                 else {
615                     p.prev = tl;
616                     tl.next = p;
617                 }
618                 tl = p;
619             } while ((e = e.next) !is null);
620             if ((tab[index] = hd) !is null)
621                 hd.treeify(tab);
622         }
623     }
624 
625     /**
626      * Copies all of the mappings from the specified map to this map.
627      * These mappings will replace any mappings that this map had for
628      * any of the keys currently in the specified map.
629      *
630      * @param m mappings to be stored in this map
631      * @throws NullPointerException if the specified map is null
632      */
633     // override void putAll(Map!(K, V) m) {
634     //     putMapEntries(m, true);
635     // }
636 
637     /**
638      * Removes the mapping for the specified key from this map if present.
639      *
640      * @param  key key whose mapping is to be removed from the map
641      * @return the previous value associated with <tt>key</tt>, or
642      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
643      *         (A <tt>null</tt> return can also indicate that the map
644      *         previously associated <tt>null</tt> with <tt>key</tt>.)
645      */
646     override V remove(K key) {
647         HashMapNode!(K,V) e = removeNode(hash(key), key, V.init, false, true);
648         return e is null ? V.init : e.value;
649     }
650 
651     alias remove = AbstractMap!(K, V).remove;
652 
653     /**
654      * Implements Map.remove and related methods
655      *
656      * @param hash hash for key
657      * @param key the key
658      * @param value the value to match if matchValue, else ignored
659      * @param matchValue if true only remove if value is equal
660      * @param movable if false do not move other nodes while removing
661      * @return the node, or null if none
662      */
663     final HashMapNode!(K,V) removeNode(size_t hash, K key, V value,
664                                bool matchValue, bool movable) {
665         HashMapNode!(K,V)[] tab; HashMapNode!(K,V) p; 
666         size_t n, index;
667         if ((tab = table) !is null && (n = tab.length) > 0 &&
668             (p = tab[index = (n - 1) & hash]) !is null) {
669             HashMapNode!(K,V) node = null, e; K k; V v;
670             k = p.key;
671             if (p.hash == hash && k == key )
672                 node = p;
673             else if ((e = p.next) !is null) {
674                 TreeNode!(K,V) pp = cast(TreeNode!(K,V))p;
675                 if (pp !is null)
676                     node = pp.getTreeNode(hash, key);
677                 else {
678                     do {
679                         k = e.key;
680                         if (e.hash == hash && k == key ) {
681                             node = e;
682                             break;
683                         }
684                         p = e;
685                     } while ((e = e.next) !is null);
686                 }
687             }
688             if (node !is null && (!matchValue || (v = node.value) == value)) {
689                 auto _node = cast(TreeNode!(K,V))node;
690                 if (_node !is null)
691                     _node.removeTreeNode(this, tab, movable);
692                 else if (node == p)
693                     tab[index] = node.next;
694                 else
695                     p.next = node.next;
696                 ++modCount;
697                 --_size;
698                 afterNodeRemoval(node);
699                 return node;
700             }
701         }
702         return null;
703     }
704 
705     /**
706      * Removes all of the mappings from this map.
707      * The map will be empty after this call returns.
708      */
709     override void clear() {
710         HashMapNode!(K,V)[] tab;
711         modCount++;
712         if ((tab = table) !is null && size > 0) {
713             _size = 0;
714             for (size_t i = 0; i < tab.length; ++i)
715                 tab[i] = null;
716         }
717     }
718 
719     /**
720      * Returns <tt>true</tt> if this map maps one or more keys to the
721      * specified value.
722      *
723      * @param value value whose presence in this map is to be tested
724      * @return <tt>true</tt> if this map maps one or more keys to the
725      *         specified value
726      */
727     override bool containsValue(V value) {
728         HashMapNode!(K, V)[] tab; V v;
729         if ((tab = table) !is null && size > 0) {
730             for (size_t i = 0; i < tab.length; ++i) {
731                 for (HashMapNode!(K, V) e = tab[i]; e !is null; e = e.next) {
732                     v = e.value;
733                     // if ((v = e.value) == value ||
734                     //     (value !is null && value == v))
735                     if(v == value)
736                         return true;
737                 }
738             }
739         }
740         return false;
741     }
742 
743     /**
744      * Returns a {@link Set} view of the keys contained in this map.
745      * The set is backed by the map, so changes to the map are
746      * reflected in the set, and vice-versa.  If the map is modified
747      * while an iteration over the set is in progress (except through
748      * the iterator's own <tt>remove</tt> operation), the results of
749      * the iteration are undefined.  The set supports element removal,
750      * which removes the corresponding mapping from the map, via the
751      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
752      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
753      * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
754      * operations.
755      *
756      * @return a set view of the keys contained in this map
757      */
758     // Set!K keySet() {
759     //     Set!K ks = keySet;
760     //     if (ks is null) {
761     //         ks = new KeySet();
762     //         keySet = ks;
763     //     }
764     //     return ks;
765     // }
766 
767     /* ------------------------------------------------------------ */
768     // iterators
769 
770     override int opApply(scope int delegate(ref K, ref V) dg) {
771         if(dg is null)
772             throw new NullPointerException();
773         HashMapNode!(K, V)[] tab = table;
774 
775         int result = 0;
776         if(_size > 0 && tab !is null) {
777             int mc = modCount;
778             for(size_t i=0; i<tab.length; i++) {
779                 for(HashMapNode!(K, V) e = tab[i]; e !is null; e = e.next) {
780                     result = dg(e.key, e.value);
781                     if(result != 0) return result;
782                 }
783             }
784 
785             if(modCount != mc)
786                 throw new ConcurrentModificationException();
787         }
788 
789         return result;
790     }
791 
792     override int opApply(scope int delegate(MapEntry!(K, V) entry) dg) {
793         if(dg is null)
794             throw new NullPointerException("");
795         HashMapNode!(K, V)[] tab = table;
796 
797         if(_size <= 0 || tab is null) 
798             return 0;
799         
800         int result = 0;
801         int mc = modCount;
802         for(size_t i=0; i<tab.length; i++) {
803             for(HashMapNode!(K, V) e = tab[i]; e !is null; e = e.next) {
804                 result = dg(e);
805                 if(result != 0) return result;
806             }
807         }
808 
809         if(modCount != mc)
810             throw new ConcurrentModificationException("");
811 
812         return result;
813     }
814 
815     override InputRange!K byKey() {
816         return new KeyInputRange();
817     }
818 
819     override InputRange!V byValue() {
820         return new ValueInputRange();
821     }
822     
823     
824     mixin template HashIterator() {
825         protected HashMapNode!(K, V) next;        // next entry to return
826         protected HashMapNode!(K, V) current;     // current entry
827         protected int expectedModCount;  // for fast-fail
828         protected int index;             // current slot
829 
830         this() {
831             expectedModCount = modCount;
832             HashMapNode!(K, V)[] t = table;
833             next = null;
834             index = 0;
835             if (t !is null && size > 0) { // advance to first entry
836                 do {} while (index < t.length && (next = t[index++]) is null);
837             }
838             current = next;
839         }
840 
841         final bool empty() {
842             return next is null;
843         }
844 
845         void popFront() {
846             HashMapNode!(K, V)[] t;
847             HashMapNode!(K, V) e = next;
848             if (modCount != expectedModCount)
849                 throw new ConcurrentModificationException();
850             if (e is null)
851                 throw new NoSuchElementException();
852             if ((next = (current = e).next) is null && (t = table) !is null) {
853                 do {} while (index < t.length && (next = t[index++]) is null);
854             }
855         }
856     }
857 
858     final class KeyInputRange :  InputRange!K {
859         mixin HashIterator;
860 
861         final K front() @property { return next.key; }
862 
863         // https://forum.dlang.org/thread/amzthhonuozlobghqqgk@forum.dlang.org?page=1
864         // https://issues.dlang.org/show_bug.cgi?id=18036
865         final K moveFront() @property { throw new NotSupportedException(); }
866         
867         int opApply(scope int delegate(K) dg) {
868             if(dg is null)
869                 throw new NullPointerException("");
870 
871             if(_size <= 0 || table is null) 
872                 return 0;
873             
874             HashMapNode!(K, V)[] tab = table;
875             int result = 0;
876             int mc = modCount;
877             for(size_t i=0; i<tab.length; i++) {
878                 for(HashMapNode!(K, V) e = tab[i]; e !is null; e = e.next) {
879                     result = dg(e.key);
880                     if(result != 0) return result;
881                 }
882             }
883 
884             if(modCount != mc)
885                 throw new ConcurrentModificationException("");
886 
887             return result;
888         }
889 
890         int opApply(scope int delegate(size_t, K) dg) {
891             if(dg is null)
892                 throw new NullPointerException("");
893                 
894             if(_size <= 0 || table is null) 
895                 return 0;
896             
897             HashMapNode!(K, V)[] tab = table;
898             int result = 0;
899             int mc = modCount;            
900             size_t index = 0;
901 
902             for(size_t i=0; i<tab.length; i++) {
903                 for(HashMapNode!(K, V) e = tab[i]; e !is null; e = e.next) {
904                     result = dg(index++, e.key);
905                     if(result != 0) return result;
906                 }
907             }
908 
909             if(modCount != mc)
910                 throw new ConcurrentModificationException("");
911 
912             return result;
913         }
914     }
915     
916     final class ValueInputRange :  InputRange!V {
917         mixin HashIterator;
918 
919         final V front() @property { return next.value; }
920 
921         final V moveFront() @property { throw new NotSupportedException(); }
922         
923         int opApply(scope int delegate(V) dg)
924         {
925             if(dg is null)
926                 throw new NullPointerException("");
927 
928             if(_size <= 0 || table is null) 
929                 return 0;
930             
931             HashMapNode!(K, V)[] tab = table;
932             int result = 0;
933             int mc = modCount;
934             for(size_t i=0; i<tab.length; i++)
935             {
936                 for(HashMapNode!(K, V) e = tab[i]; e !is null; e = e.next)
937                 {
938                     result = dg(e.value);
939                     if(result != 0) return result;
940                 }
941             }
942 
943             if(modCount != mc)
944                 throw new ConcurrentModificationException("");
945 
946             return result;
947         }
948 
949         int opApply(scope int delegate(size_t, V) dg) {
950             if(dg is null)
951                 throw new NullPointerException("");
952                 
953             if(_size <= 0 || table is null) 
954                 return 0;
955             
956             HashMapNode!(K, V)[] tab = table;
957             int result = 0;
958             int mc = modCount;
959             size_t index = 0;
960             for(size_t i=0; i<tab.length; i++) {
961                 for(HashMapNode!(K, V) e = tab[i]; e !is null; e = e.next)
962                 {
963                     result = dg(index++, e.value);
964                     if(result != 0) return result;
965                 }
966             }
967 
968             if(modCount != mc)
969                 throw new ConcurrentModificationException("");
970 
971             return result;
972         }
973     }
974 
975 
976 
977     // for Test
978     // Iterator!K keyIterator()
979     // {
980     //     return new KeyIterator();
981     // }
982     
983     // mixin template HashIterator() {
984     //     HashMapNode!(K, V) _next;        // next entry to return
985     //     HashMapNode!(K, V) current;     // current entry
986     //     int expectedModCount;  // for fast-fail
987     //     int index;             // current slot
988 
989     //     this() {
990     //         expectedModCount = modCount;
991     //         HashMapNode!(K, V)[] t = table;
992     //         current = _next = null;
993     //         index = 0;
994     //         if (t !is null && size > 0) { // advance to first entry
995     //             do {} while (index < t.length && (_next = t[index++]) is null);
996     //         }
997     //     }
998 
999     //     void next(HashMapNode!(K, V) v) { _next = v; }
1000 
1001     //     final bool hasNext() {
1002     //         return _next !is null;
1003     //     }
1004 
1005     //     final HashMapNode!(K, V) nextNode() {
1006     //         HashMapNode!(K, V)[] t;
1007     //         HashMapNode!(K, V) e = _next;
1008     //         if (modCount != expectedModCount)
1009     //             throw new ConcurrentModificationException();
1010     //         if (e is null)
1011     //             throw new NoSuchElementException();
1012     //         if ((_next = (current = e).next) is null && (t = table) !is null) {
1013     //             do {} while (index < t.length && (_next = t[index++]) is null);
1014     //         }
1015     //         return e;
1016     //     }
1017 
1018     //     final void remove() {
1019     //         HashMapNode!(K, V) p = current;
1020     //         if (p is null)
1021     //             throw new IllegalStateException();
1022     //         if (modCount != expectedModCount)
1023     //             throw new ConcurrentModificationException();
1024     //         current = null;
1025     //         K key = p.key;
1026     //         removeNode(hash(key), key, null, false, false);
1027     //         expectedModCount = modCount;
1028     //     }
1029     // }
1030 
1031     // final class KeyIterator :  Iterator!K {
1032     //     mixin HashIterator;
1033     //     final K next() { return nextNode().key; }
1034     // }
1035 
1036     // final class ValueIterator : HashIterator
1037     //     implements Iterator!V {
1038     //     final V next() { return nextNode().value; }
1039     // }
1040 
1041     // final class EntryIterator : HashIterator
1042     //     implements Iterator<MapEntry!(K,V)> {
1043     //     final MapEntry!(K,V) next() { return nextNode(); }
1044     // }
1045 
1046     // Overrides of JDK8 Map extension methods
1047 
1048     // override
1049     // V getOrDefault(Object key, V defaultValue) {
1050     //     HashMapNode!(K,V) e;
1051     //     return (e = getNode(hash(key), key)) is null ? defaultValue : e.value;
1052     // }
1053 
1054     // override
1055     // V putIfAbsent(K key, V value) {
1056     //     return putVal(hash(key), key, value, true, true);
1057     // }
1058 
1059     // override
1060     // bool remove(Object key, Object value) {
1061     //     return removeNode(hash(key), key, value, true, true) !is null;
1062     // }
1063 
1064     // override
1065     // bool replace(K key, V oldValue, V newValue) {
1066     //     HashMapNode!(K,V) e; V v;
1067     //     if ((e = getNode(hash(key), key)) !is null &&
1068     //         ((v = e.value) == oldValue || (v !is null && v.equals(oldValue)))) {
1069     //         e.value = newValue;
1070     //         afterNodeAccess(e);
1071     //         return true;
1072     //     }
1073     //     return false;
1074     // }
1075 
1076     // override
1077     // V replace(K key, V value) {
1078     //     HashMapNode!(K,V) e;
1079     //     if ((e = getNode(hash(key), key)) !is null) {
1080     //         V oldValue = e.value;
1081     //         e.value = value;
1082     //         afterNodeAccess(e);
1083     //         return oldValue;
1084     //     }
1085     //     return null;
1086     // }
1087 
1088     // override
1089     // V computeIfAbsent(K key,
1090     //                          Function<K, V> mappingFunction) {
1091     //     if (mappingFunction is null)
1092     //         throw new NullPointerException();
1093     //     int hash = hash(key);
1094     //     HashMapNode!(K,V)[] tab; HashMapNode!(K,V) first; int n, i;
1095     //     int binCount = 0;
1096     //     TreeNode!(K,V) t = null;
1097     //     HashMapNode!(K,V) old = null;
1098     //     if (size > threshold || (tab = table) is null ||
1099     //         (n = tab.length) == 0)
1100     //         n = (tab = resize()).length;
1101     //     if ((first = tab[i = (n - 1) & hash]) !is null) {
1102     //         if (first instanceof TreeNode)
1103     //             old = (t = (TreeNode!(K,V))first).getTreeNode(hash, key);
1104     //         else {
1105     //             HashMapNode!(K,V) e = first; K k;
1106     //             do {
1107     //                 if (e.hash == hash &&
1108     //                     ((k = e.key) == key || (key !is null && key.equals(k)))) {
1109     //                     old = e;
1110     //                     break;
1111     //                 }
1112     //                 ++binCount;
1113     //             } while ((e = e.next) !is null);
1114     //         }
1115     //         V oldValue;
1116     //         if (old !is null && (oldValue = old.value) !is null) {
1117     //             afterNodeAccess(old);
1118     //             return oldValue;
1119     //         }
1120     //     }
1121     //     V v = mappingFunction.apply(key);
1122     //     if (v is null) {
1123     //         return null;
1124     //     } else if (old !is null) {
1125     //         old.value = v;
1126     //         afterNodeAccess(old);
1127     //         return v;
1128     //     }
1129     //     else if (t !is null)
1130     //         t.putTreeVal(this, tab, hash, key, v);
1131     //     else {
1132     //         tab[i] = newNode(hash, key, v, first);
1133     //         if (binCount >= TREEIFY_THRESHOLD - 1)
1134     //             treeifyBin(tab, hash);
1135     //     }
1136     //     ++modCount;
1137     //     ++size;
1138     //     afterNodeInsertion(true);
1139     //     return v;
1140     // }
1141 
1142     // V computeIfPresent(K key,
1143     //                           BiFunction<K, V, V> remappingFunction) {
1144     //     if (remappingFunction is null)
1145     //         throw new NullPointerException();
1146     //     HashMapNode!(K,V) e; V oldValue;
1147     //     int hash = hash(key);
1148     //     if ((e = getNode(hash, key)) !is null &&
1149     //         (oldValue = e.value) !is null) {
1150     //         V v = remappingFunction.apply(key, oldValue);
1151     //         if (v !is null) {
1152     //             e.value = v;
1153     //             afterNodeAccess(e);
1154     //             return v;
1155     //         }
1156     //         else
1157     //             removeNode(hash, key, null, false, true);
1158     //     }
1159     //     return null;
1160     // }
1161 
1162     // override
1163     // V compute(K key,
1164     //                  BiFunction<K, V, V> remappingFunction) {
1165     //     if (remappingFunction is null)
1166     //         throw new NullPointerException();
1167     //     int hash = hash(key);
1168     //     HashMapNode!(K,V)[] tab; HashMapNode!(K,V) first; int n, i;
1169     //     int binCount = 0;
1170     //     TreeNode!(K,V) t = null;
1171     //     HashMapNode!(K,V) old = null;
1172     //     if (size > threshold || (tab = table) is null ||
1173     //         (n = tab.length) == 0)
1174     //         n = (tab = resize()).length;
1175     //     if ((first = tab[i = (n - 1) & hash]) !is null) {
1176     //         if (first instanceof TreeNode)
1177     //             old = (t = (TreeNode!(K,V))first).getTreeNode(hash, key);
1178     //         else {
1179     //             HashMapNode!(K,V) e = first; K k;
1180     //             do {
1181     //                 if (e.hash == hash &&
1182     //                     ((k = e.key) == key || (key !is null && key.equals(k)))) {
1183     //                     old = e;
1184     //                     break;
1185     //                 }
1186     //                 ++binCount;
1187     //             } while ((e = e.next) !is null);
1188     //         }
1189     //     }
1190     //     V oldValue = (old is null) ? null : old.value;
1191     //     V v = remappingFunction.apply(key, oldValue);
1192     //     if (old !is null) {
1193     //         if (v !is null) {
1194     //             old.value = v;
1195     //             afterNodeAccess(old);
1196     //         }
1197     //         else
1198     //             removeNode(hash, key, null, false, true);
1199     //     }
1200     //     else if (v !is null) {
1201     //         if (t !is null)
1202     //             t.putTreeVal(this, tab, hash, key, v);
1203     //         else {
1204     //             tab[i] = newNode(hash, key, v, first);
1205     //             if (binCount >= TREEIFY_THRESHOLD - 1)
1206     //                 treeifyBin(tab, hash);
1207     //         }
1208     //         ++modCount;
1209     //         ++size;
1210     //         afterNodeInsertion(true);
1211     //     }
1212     //     return v;
1213     // }
1214 
1215     // override
1216     // V merge(K key, V value,
1217     //                BiFunction<V, V, V> remappingFunction) {
1218     //     if (value is null)
1219     //         throw new NullPointerException();
1220     //     if (remappingFunction is null)
1221     //         throw new NullPointerException();
1222     //     int hash = hash(key);
1223     //     HashMapNode!(K,V)[] tab; HashMapNode!(K,V) first; int n, i;
1224     //     int binCount = 0;
1225     //     TreeNode!(K,V) t = null;
1226     //     HashMapNode!(K,V) old = null;
1227     //     if (size > threshold || (tab = table) is null ||
1228     //         (n = tab.length) == 0)
1229     //         n = (tab = resize()).length;
1230     //     if ((first = tab[i = (n - 1) & hash]) !is null) {
1231     //         if (first instanceof TreeNode)
1232     //             old = (t = (TreeNode!(K,V))first).getTreeNode(hash, key);
1233     //         else {
1234     //             HashMapNode!(K,V) e = first; K k;
1235     //             do {
1236     //                 if (e.hash == hash &&
1237     //                     ((k = e.key) == key || (key !is null && key.equals(k)))) {
1238     //                     old = e;
1239     //                     break;
1240     //                 }
1241     //                 ++binCount;
1242     //             } while ((e = e.next) !is null);
1243     //         }
1244     //     }
1245     //     if (old !is null) {
1246     //         V v;
1247     //         if (old.value !is null)
1248     //             v = remappingFunction.apply(old.value, value);
1249     //         else
1250     //             v = value;
1251     //         if (v !is null) {
1252     //             old.value = v;
1253     //             afterNodeAccess(old);
1254     //         }
1255     //         else
1256     //             removeNode(hash, key, null, false, true);
1257     //         return v;
1258     //     }
1259     //     if (value !is null) {
1260     //         if (t !is null)
1261     //             t.putTreeVal(this, tab, hash, key, value);
1262     //         else {
1263     //             tab[i] = newNode(hash, key, value, first);
1264     //             if (binCount >= TREEIFY_THRESHOLD - 1)
1265     //                 treeifyBin(tab, hash);
1266     //         }
1267     //         ++modCount;
1268     //         ++size;
1269     //         afterNodeInsertion(true);
1270     //     }
1271     //     return value;
1272     // }
1273 
1274 
1275     /* ------------------------------------------------------------ */
1276     // LinkedHashMap support
1277 
1278     /*
1279      * The following package-protected methods are designed to be
1280      * overridden by LinkedHashMap, but not by any other subclass.
1281      * Nearly all other internal methods are also package-protected
1282      * but are declared final, so can be used by LinkedHashMap, view
1283      * classes, and HashSet.
1284      */
1285 
1286     // Create a regular (non-tree) node
1287     HashMapNode!(K,V) newNode(size_t hash, K key, V value, HashMapNode!(K,V) next) {
1288         return new HashMapNode!(K,V)(hash, key, value, next);
1289     }
1290 
1291     // For conversion from TreeNodes to plain nodes
1292     HashMapNode!(K,V) replacementNode(HashMapNode!(K,V) p, HashMapNode!(K,V) next) {
1293         return new HashMapNode!(K,V)(p.hash, p.key, p.value, next);
1294     }
1295 
1296     // Create a tree bin node
1297     TreeNode!(K,V) newTreeNode(size_t hash, K key, V value, HashMapNode!(K,V) next) {
1298         return new TreeNode!(K,V)(hash, key, value, next);
1299     }
1300 
1301     // For treeifyBin
1302     TreeNode!(K,V) replacementTreeNode(HashMapNode!(K,V) p, HashMapNode!(K,V) next) {
1303         return new TreeNode!(K,V)(p.hash, p.key, p.value, next);
1304     }
1305 
1306     /**
1307      * Reset to initial default state.  Called by clone and readObject.
1308      */
1309     void reinitialize() {
1310         table = null;
1311         // entrySet = null;
1312         // _keySet = null;
1313         // _values = null;
1314         modCount = 0;
1315         threshold = 0;
1316         _size = 0;
1317     }
1318 
1319     // Callbacks to allow LinkedHashMap post-actions
1320     void afterNodeAccess(HashMapNode!(K,V) p) { }
1321     void afterNodeInsertion(bool evict) { }
1322     void afterNodeRemoval(HashMapNode!(K,V) p) { }
1323 
1324     // Called only from writeObject, to ensure compatible ordering.
1325     // void internalWriteEntries(java.io.ObjectOutputStream s) {
1326     //     HashMapNode!(K,V)[] tab;
1327     //     if (size > 0 && (tab = table) !is null) {
1328     //         for (int i = 0; i < tab.length; ++i) {
1329     //             for (HashMapNode!(K,V) e = tab[i]; e !is null; e = e.next) {
1330     //                 s.writeObject(e.key);
1331     //                 s.writeObject(e.value);
1332     //             }
1333     //         }
1334     //     }
1335     // }
1336   
1337 }
1338 
1339 /* ------------------------------------------------------------ */
1340 // Tree bins
1341 
1342 /**
1343  * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
1344  * extends Node) so can be used as extension of either regular or
1345  * linked node.
1346  */
1347 final class TreeNode(K, V) : LinkedHashMapEntry!(K, V) {
1348 
1349     /**
1350      * The bin count threshold for untreeifying a (split) bin during a
1351      * resize operation. Should be less than TREEIFY_THRESHOLD, and at
1352      * most 6 to mesh with shrinkage detection under removal.
1353      */
1354     enum int UNTREEIFY_THRESHOLD = 6;
1355 
1356     TreeNode!(K, V) parent;  // red-black tree links
1357     TreeNode!(K, V) left;
1358     TreeNode!(K, V) right;
1359     TreeNode!(K, V) prev;    // needed to unlink next upon deletion
1360     bool red;
1361 
1362     this(size_t hash, K key, V val, HashMapNode!(K, V) next) {
1363         super(hash, key, val, next);
1364     }
1365 
1366     /**
1367      * Returns root of tree containing this node.
1368      */
1369     final TreeNode!(K, V) root() {
1370         for (TreeNode!(K, V) r = this, p;;) {
1371             if ((p = r.parent) is null)
1372                 return r;
1373             r = p;
1374         }
1375     }
1376 
1377     /**
1378      * Ensures that the given root is the first node of its bin.
1379      */
1380     static void moveRootToFront(K, V)(HashMapNode!(K, V)[] tab, TreeNode!(K, V) root) {
1381         size_t n;
1382         if (root !is null && tab !is null && (n = tab.length) > 0) {
1383             size_t index = (n - 1) & root.hash;
1384             TreeNode!(K, V) first = cast(TreeNode!(K, V))tab[index];
1385             if (root != first) {
1386                 HashMapNode!(K, V) rn;
1387                 tab[index] = root;
1388                 TreeNode!(K, V) rp = root.prev;
1389                 if ((rn = root.next) !is null)
1390                     (cast(TreeNode!(K, V))rn).prev = rp;
1391                 if (rp !is null)
1392                     rp.next = rn;
1393                 if (first !is null)
1394                     first.prev = root;
1395                 root.next = first;
1396                 root.prev = null;
1397             }
1398             assert(checkInvariants(root));
1399         }
1400     }
1401 
1402     /**
1403      * Finds the node starting at root p with the given hash and key.
1404      * The kc argument caches comparableClassFor(key) upon first use
1405      * comparing keys.
1406      */
1407     final TreeNode!(K, V) find(size_t h, K k) {
1408         TreeNode!(K, V) p = this;
1409         do {
1410             size_t ph; int dir; K pk;
1411             TreeNode!(K, V) pl = p.left, pr = p.right, q;
1412             if ((ph = p.hash) > h)
1413                 p = pl;
1414             else if (ph < h)
1415                 p = pr;
1416             else {
1417                 pk = p.key;
1418                 if (pk == k)
1419                     return p;
1420                 else if (pl is null)
1421                     p = pr;
1422                 else if (pr is null)
1423                     p = pl;
1424                 else {
1425                     // static if(isNumeric!(K)) { dir = std.math.cmp(cast(float)k, cast(float)pk); }
1426                     // else { dir = std.algorithm.cmp(k, pk); }    
1427 
1428                     // if (dir != 0)
1429                     //     p = (dir < 0) ? pl : pr;
1430                     // else if ((q = pr.find(h, k)) !is null)
1431                     //     return q;
1432                     // else
1433                     //     p = pl;
1434                     if(k < pk) 
1435                         p = pl;
1436                     else if( k>pk) 
1437                         p = pr;
1438                     else if ((q = pr.find(h, k)) !is null)
1439                         return q;
1440                     else
1441                         p = pl; 
1442                 }
1443             } 
1444         } while (p !is null);
1445         return null;
1446     }
1447 
1448     /**
1449      * Calls find for root node.
1450      */
1451     final TreeNode!(K, V) getTreeNode(size_t h, K k) {
1452         return ((parent !is null) ? root() : this).find(h, k);
1453     }
1454 
1455     /**
1456      * Tie-breaking utility for ordering insertions when equal
1457      * hashCodes and non-comparable. We don't require a total
1458      * order, just a consistent insertion rule to maintain
1459      * equivalence across rebalancings. Tie-breaking further than
1460      * necessary simplifies testing a bit.
1461      */
1462     static int tieBreakOrder(T)(T a, T b) if(isBasicType!(T) || isSomeString!T) {
1463         return (hashOf(a) <= hashOf(b) ? -1 : 1);
1464     }
1465 
1466     static int tieBreakOrder(T)(T a, T b) if(is(T == class) || is(T == interface)) {
1467         int d = 0;
1468         if (a is null || b is null  ||
1469             (d = std.algorithm.cmp(typeid(a).name, 
1470                 typeid(b).name)) == 0)
1471             d = ((cast(Object)a).toHash() <= (cast(Object)b).toHash() ? -1 : 1);
1472         return d;
1473     }
1474 
1475     static int tieBreakOrder(T)(T a, T b) if(is(T == struct)) {
1476         int d = std.algorithm.cmp(typeid(a).name,
1477                 typeid(b).name);
1478         if (d == 0)
1479             d = (a.toHash() <= b.toHash() ? -1 : 1);
1480         return d;
1481     }
1482 
1483     /**
1484      * Forms tree of the nodes linked from this node.
1485      * @return root of tree
1486      */
1487     final void treeify(HashMapNode!(K, V)[] tab) {
1488         TreeNode!(K, V) root = null;
1489         for (TreeNode!(K, V) x = this, next; x !is null; x = next) {
1490             next = cast(TreeNode!(K, V))x.next;
1491             x.left = x.right = null;
1492             if (root is null) {
1493                 x.parent = null;
1494                 x.red = false;
1495                 root = x;
1496             }
1497             else {
1498                 K k = x.key;
1499                 size_t h = x.hash;
1500                 for (TreeNode!(K, V) p = root;;) {
1501                     size_t ph;
1502                     int dir;
1503                     K pk = p.key;
1504                     if ((ph = p.hash) > h)
1505                         dir = -1;
1506                     else if (ph < h)
1507                         dir = 1;
1508                     else {
1509                         // static if(isNumeric!(K)) { dir = std.math.cmp(cast(float)k, cast(float)pk); }
1510                         // else { dir = std.algorithm.cmp(k, pk); }
1511                         if (k == pk)
1512                             dir = tieBreakOrder!(K)(k, pk);
1513                         else if(k > pk)
1514                             dir = 1;
1515                         else 
1516                             dir = -1;
1517                     }
1518 
1519                     TreeNode!(K, V) xp = p;
1520                     if ((p = (dir <= 0) ? p.left : p.right) is null) {
1521                         x.parent = xp;
1522                         if (dir <= 0)
1523                             xp.left = x;
1524                         else
1525                             xp.right = x;
1526                         root = balanceInsertion(root, x);
1527                         break;
1528                     }
1529                 }
1530             }
1531         }
1532         moveRootToFront(tab, root);
1533     }
1534 
1535     /**
1536      * Returns a list of non-TreeNodes replacing those linked from
1537      * this node.
1538      */
1539     final HashMapNode!(K, V) untreeify(HashMap!(K, V) map) {
1540         HashMapNode!(K, V) hd = null, tl = null;
1541         for (HashMapNode!(K, V) q = this; q !is null; q = q.next) {
1542             HashMapNode!(K, V) p = map.replacementNode(q, null);
1543             if (tl is null)
1544                 hd = p;
1545             else
1546                 tl.next = p;
1547             tl = p;
1548         }
1549         return hd;
1550     }
1551 
1552     /**
1553      * Tree version of putVal.
1554      */
1555     final TreeNode!(K, V) putTreeVal(HashMap!(K, V) map, HashMapNode!(K, V)[] tab,
1556                                    size_t h, K k, V v) {
1557         // Class<?> kc = null;
1558         bool searched = false;
1559         TreeNode!(K, V) root = (parent !is null) ? root() : this;
1560         for (TreeNode!(K, V) p = root;;) {
1561             size_t ph; K pk; int dir;
1562 
1563             if ((ph = p.hash) > h)
1564                 dir = -1;
1565             else if (ph < h)
1566                 dir = 1;
1567             else {
1568                 pk = p.key;
1569                 if (pk == k)
1570                     return p;
1571                 else {
1572                     // static if(isNumeric!(K)) { dir = std.math.cmp(cast(float)k, cast(float)pk); }
1573                     // else { dir = std.algorithm.cmp(k, pk); }
1574 
1575                     if(k == pk) {
1576                         if (!searched) {
1577                             TreeNode!(K, V) q, ch;
1578                             searched = true;
1579                             if (((ch = p.left) !is null &&
1580                                 (q = ch.find(h, k)) !is null) ||
1581                                 ((ch = p.right) !is null &&
1582                                 (q = ch.find(h, k)) !is null))
1583                                 return q;
1584                         }
1585                         dir = tieBreakOrder!(K)(k, pk);
1586                     } else if(k > pk)
1587                         dir = 1;
1588                     else
1589                         dir = -1;
1590                 }
1591             }
1592 
1593             TreeNode!(K, V) xp = p;
1594             if ((p = (dir <= 0) ? p.left : p.right) is null) {
1595                 HashMapNode!(K, V) xpn = xp.next;
1596                 TreeNode!(K, V) x = map.newTreeNode(h, k, v, xpn);
1597                 if (dir <= 0)
1598                     xp.left = x;
1599                 else
1600                     xp.right = x;
1601                 xp.next = x;
1602                 x.parent = x.prev = xp;
1603                 if (xpn !is null)
1604                     (cast(TreeNode!(K, V))xpn).prev = x;
1605                 moveRootToFront(tab, balanceInsertion(root, x));
1606                 return null;
1607             }
1608         }
1609     }
1610 
1611     /**
1612      * Removes the given node, that must be present before this call.
1613      * This is messier than typical red-black deletion code because we
1614      * cannot swap the contents of an interior node with a leaf
1615      * successor that is pinned by "next" pointers that are accessible
1616      * independently during traversal. So instead we swap the tree
1617      * linkages. If the current tree appears to have too few nodes,
1618      * the bin is converted back to a plain bin. (The test triggers
1619      * somewhere between 2 and 6 nodes, depending on tree structure).
1620      */
1621     final void removeTreeNode(HashMap!(K, V) map, HashMapNode!(K, V)[] tab,
1622                               bool movable) {
1623         size_t n;
1624         if (tab is null || (n = tab.length) == 0)
1625             return;
1626         size_t index = (n - 1) & hash;
1627         TreeNode!(K, V) first = cast(TreeNode!(K, V))tab[index], root = first, rl;
1628         TreeNode!(K, V) succ = cast(TreeNode!(K, V))next, pred = prev;
1629         if (pred is null)
1630             tab[index] = first = succ;
1631         else
1632             pred.next = succ;
1633         if (succ !is null)
1634             succ.prev = pred;
1635         if (first is null)
1636             return;
1637         if (root.parent !is null)
1638             root = root.root();
1639         if (root is null || root.right is null ||
1640             (rl = root.left) is null || rl.left is null) {
1641             tab[index] = first.untreeify(map);  // too small
1642             return;
1643         }
1644         TreeNode!(K, V) p = this, pl = left, pr = right, replacement;
1645         if (pl !is null && pr !is null) {
1646             TreeNode!(K, V) s = pr, sl;
1647             while ((sl = s.left) !is null) // find successor
1648                 s = sl;
1649             bool c = s.red; s.red = p.red; p.red = c; // swap colors
1650             TreeNode!(K, V) sr = s.right;
1651             TreeNode!(K, V) pp = p.parent;
1652             if (s == pr) { // p was s's direct parent
1653                 p.parent = s;
1654                 s.right = p;
1655             }
1656             else {
1657                 TreeNode!(K, V) sp = s.parent;
1658                 if ((p.parent = sp) !is null) {
1659                     if (s == sp.left)
1660                         sp.left = p;
1661                     else
1662                         sp.right = p;
1663                 }
1664                 if ((s.right = pr) !is null)
1665                     pr.parent = s;
1666             }
1667             p.left = null;
1668             if ((p.right = sr) !is null)
1669                 sr.parent = p;
1670             if ((s.left = pl) !is null)
1671                 pl.parent = s;
1672             if ((s.parent = pp) is null)
1673                 root = s;
1674             else if (p == pp.left)
1675                 pp.left = s;
1676             else
1677                 pp.right = s;
1678             if (sr !is null)
1679                 replacement = sr;
1680             else
1681                 replacement = p;
1682         }
1683         else if (pl !is null)
1684             replacement = pl;
1685         else if (pr !is null)
1686             replacement = pr;
1687         else
1688             replacement = p;
1689         if (replacement != p) {
1690             TreeNode!(K, V) pp = replacement.parent = p.parent;
1691             if (pp is null)
1692                 root = replacement;
1693             else if (p == pp.left)
1694                 pp.left = replacement;
1695             else
1696                 pp.right = replacement;
1697             p.left = p.right = p.parent = null;
1698         }
1699 
1700         TreeNode!(K, V) r = p.red ? root : balanceDeletion(root, replacement);
1701 
1702         if (replacement == p) {  // detach
1703             TreeNode!(K, V) pp = p.parent;
1704             p.parent = null;
1705             if (pp !is null) {
1706                 if (p == pp.left)
1707                     pp.left = null;
1708                 else if (p == pp.right)
1709                     pp.right = null;
1710             }
1711         }
1712         if (movable)
1713             moveRootToFront(tab, r);
1714     }
1715 
1716     /**
1717      * Splits nodes in a tree bin into lower and upper tree bins,
1718      * or untreeifies if now too small. Called only from resize;
1719      * see above discussion about split bits and indices.
1720      *
1721      * @param map the map
1722      * @param tab the table for recording bin heads
1723      * @param index the index of the table being split
1724      * @param bit the bit of hash to split on
1725      */
1726     final void split(HashMap!(K, V) map, HashMapNode!(K, V)[] tab, int index, int bit) {
1727         TreeNode!(K, V) b = this;
1728         // Relink into lo and hi lists, preserving order
1729         TreeNode!(K, V) loHead = null, loTail = null;
1730         TreeNode!(K, V) hiHead = null, hiTail = null;
1731         int lc = 0, hc = 0;
1732         for (TreeNode!(K, V) e = b, next; e !is null; e = next) {
1733             next = cast(TreeNode!(K, V))e.next;
1734             e.next = null;
1735             if ((e.hash & bit) == 0) {
1736                 if ((e.prev = loTail) is null)
1737                     loHead = e;
1738                 else
1739                     loTail.next = e;
1740                 loTail = e;
1741                 ++lc;
1742             }
1743             else {
1744                 if ((e.prev = hiTail) is null)
1745                     hiHead = e;
1746                 else
1747                     hiTail.next = e;
1748                 hiTail = e;
1749                 ++hc;
1750             }
1751         }
1752 
1753         if (loHead !is null) {
1754             if (lc <= UNTREEIFY_THRESHOLD)
1755                 tab[index] = loHead.untreeify(map);
1756             else {
1757                 tab[index] = loHead;
1758                 if (hiHead !is null) // (else is already treeified)
1759                     loHead.treeify(tab);
1760             }
1761         }
1762         if (hiHead !is null) {
1763             if (hc <= UNTREEIFY_THRESHOLD)
1764                 tab[index + bit] = hiHead.untreeify(map);
1765             else {
1766                 tab[index + bit] = hiHead;
1767                 if (loHead !is null)
1768                     hiHead.treeify(tab);
1769             }
1770         }
1771     }
1772 
1773     /* ------------------------------------------------------------ */
1774     // Red-black tree methods, all adapted from CLR
1775 
1776     static TreeNode!(K, V) rotateLeft(K, V)(TreeNode!(K, V) root,
1777                                           TreeNode!(K, V) p) {
1778         TreeNode!(K, V) r, pp, rl;
1779         if (p !is null && (r = p.right) !is null) {
1780             if ((rl = p.right = r.left) !is null)
1781                 rl.parent = p;
1782             if ((pp = r.parent = p.parent) is null)
1783                 (root = r).red = false;
1784             else if (pp.left == p)
1785                 pp.left = r;
1786             else
1787                 pp.right = r;
1788             r.left = p;
1789             p.parent = r;
1790         }
1791         return root;
1792     }
1793 
1794     static TreeNode!(K, V) rotateRight(K, V)(TreeNode!(K, V) root,
1795                                            TreeNode!(K, V) p) {
1796         TreeNode!(K, V) l, pp, lr;
1797         if (p !is null && (l = p.left) !is null) {
1798             if ((lr = p.left = l.right) !is null)
1799                 lr.parent = p;
1800             if ((pp = l.parent = p.parent) is null)
1801                 (root = l).red = false;
1802             else if (pp.right == p)
1803                 pp.right = l;
1804             else
1805                 pp.left = l;
1806             l.right = p;
1807             p.parent = l;
1808         }
1809         return root;
1810     }
1811 
1812     static TreeNode!(K, V) balanceInsertion(K, V)(TreeNode!(K, V) root,
1813                                                 TreeNode!(K, V) x) {
1814         x.red = true;
1815         for (TreeNode!(K, V) xp, xpp, xppl, xppr;;) {
1816             if ((xp = x.parent) is null) {
1817                 x.red = false;
1818                 return x;
1819             }
1820             else if (!xp.red || (xpp = xp.parent) is null)
1821                 return root;
1822             if (xp == (xppl = xpp.left)) {
1823                 if ((xppr = xpp.right) !is null && xppr.red) {
1824                     xppr.red = false;
1825                     xp.red = false;
1826                     xpp.red = true;
1827                     x = xpp;
1828                 }
1829                 else {
1830                     if (x == xp.right) {
1831                         root = rotateLeft(root, x = xp);
1832                         xpp = (xp = x.parent) is null ? null : xp.parent;
1833                     }
1834                     if (xp !is null) {
1835                         xp.red = false;
1836                         if (xpp !is null) {
1837                             xpp.red = true;
1838                             root = rotateRight(root, xpp);
1839                         }
1840                     }
1841                 }
1842             }
1843             else {
1844                 if (xppl !is null && xppl.red) {
1845                     xppl.red = false;
1846                     xp.red = false;
1847                     xpp.red = true;
1848                     x = xpp;
1849                 }
1850                 else {
1851                     if (x == xp.left) {
1852                         root = rotateRight(root, x = xp);
1853                         xpp = (xp = x.parent) is null ? null : xp.parent;
1854                     }
1855                     if (xp !is null) {
1856                         xp.red = false;
1857                         if (xpp !is null) {
1858                             xpp.red = true;
1859                             root = rotateLeft(root, xpp);
1860                         }
1861                     }
1862                 }
1863             }
1864         }
1865     }
1866 
1867     static TreeNode!(K, V) balanceDeletion(K, V)(TreeNode!(K, V) root,
1868                                                TreeNode!(K, V) x) {
1869         for (TreeNode!(K, V) xp, xpl, xpr;;)  {
1870             if (x is null || x == root)
1871                 return root;
1872             else if ((xp = x.parent) is null) {
1873                 x.red = false;
1874                 return x;
1875             }
1876             else if (x.red) {
1877                 x.red = false;
1878                 return root;
1879             }
1880             else if ((xpl = xp.left) == x) {
1881                 if ((xpr = xp.right) !is null && xpr.red) {
1882                     xpr.red = false;
1883                     xp.red = true;
1884                     root = rotateLeft(root, xp);
1885                     xpr = (xp = x.parent) is null ? null : xp.right;
1886                 }
1887                 if (xpr is null)
1888                     x = xp;
1889                 else {
1890                     TreeNode!(K, V) sl = xpr.left, sr = xpr.right;
1891                     if ((sr is null || !sr.red) &&
1892                         (sl is null || !sl.red)) {
1893                         xpr.red = true;
1894                         x = xp;
1895                     }
1896                     else {
1897                         if (sr is null || !sr.red) {
1898                             if (sl !is null)
1899                                 sl.red = false;
1900                             xpr.red = true;
1901                             root = rotateRight(root, xpr);
1902                             xpr = (xp = x.parent) is null ?
1903                                 null : xp.right;
1904                         }
1905                         if (xpr !is null) {
1906                             xpr.red = (xp is null) ? false : xp.red;
1907                             if ((sr = xpr.right) !is null)
1908                                 sr.red = false;
1909                         }
1910                         if (xp !is null) {
1911                             xp.red = false;
1912                             root = rotateLeft(root, xp);
1913                         }
1914                         x = root;
1915                     }
1916                 }
1917             }
1918             else { // symmetric
1919                 if (xpl !is null && xpl.red) {
1920                     xpl.red = false;
1921                     xp.red = true;
1922                     root = rotateRight(root, xp);
1923                     xpl = (xp = x.parent) is null ? null : xp.left;
1924                 }
1925                 if (xpl is null)
1926                     x = xp;
1927                 else {
1928                     TreeNode!(K, V) sl = xpl.left, sr = xpl.right;
1929                     if ((sl is null || !sl.red) &&
1930                         (sr is null || !sr.red)) {
1931                         xpl.red = true;
1932                         x = xp;
1933                     }
1934                     else {
1935                         if (sl is null || !sl.red) {
1936                             if (sr !is null)
1937                                 sr.red = false;
1938                             xpl.red = true;
1939                             root = rotateLeft(root, xpl);
1940                             xpl = (xp = x.parent) is null ?
1941                                 null : xp.left;
1942                         }
1943                         if (xpl !is null) {
1944                             xpl.red = (xp is null) ? false : xp.red;
1945                             if ((sl = xpl.left) !is null)
1946                                 sl.red = false;
1947                         }
1948                         if (xp !is null) {
1949                             xp.red = false;
1950                             root = rotateRight(root, xp);
1951                         }
1952                         x = root;
1953                     }
1954                 }
1955             }
1956         }
1957     }
1958 
1959     /**
1960      * Recursive invariant check
1961      */
1962     static bool checkInvariants(K, V)(TreeNode!(K, V) t) {
1963         TreeNode!(K, V) tp = t.parent, tl = t.left, tr = t.right,
1964             tb = t.prev, tn = cast(TreeNode!(K, V))t.next;
1965         if (tb !is null && tb.next != t)
1966             return false;
1967         if (tn !is null && tn.prev != t)
1968             return false;
1969         if (tp !is null && t != tp.left && t != tp.right)
1970             return false;
1971         if (tl !is null && (tl.parent != t || tl.hash > t.hash))
1972             return false;
1973         if (tr !is null && (tr.parent != t || tr.hash < t.hash))
1974             return false;
1975         if (t.red && tl !is null && tl.red && tr !is null && tr.red)
1976             return false;
1977         if (tl !is null && !checkInvariants(tl))
1978             return false;
1979         if (tr !is null && !checkInvariants(tr))
1980             return false;
1981         return true;
1982     }
1983 }
1984 
1985     
1986 /**
1987 * Basic hash bin node, used for most entries.  (See below for
1988 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
1989 */
1990 class HashMapNode(K, V) : MapEntry!(K, V) {
1991     package size_t hash;
1992     package K key;
1993     package V value;
1994     package HashMapNode!(K, V) next;
1995 
1996     this(size_t hash, K key, V value, HashMapNode!(K, V) next) {
1997         this.hash = hash;
1998         this.key = key;
1999         this.value = value;
2000         this.next = next;
2001     }
2002 
2003     final K getKey()        { return key; }
2004     final V getValue()      { return value; }
2005     final override string toString() { return format("%s=%s", key, value); }
2006 
2007     final override size_t toHash() @trusted nothrow {
2008         return hashOf(key) ^ hashOf(value);
2009     }
2010 
2011     final V setValue(V newValue) {
2012         V oldValue = value;
2013         value = newValue;
2014         return oldValue;
2015     }
2016 
2017     bool opEquals(IObject o) {
2018         return opEquals(cast(Object) o);
2019     }
2020 
2021     final override bool opEquals(Object o) {
2022         if (o is this)
2023             return true;
2024             
2025         MapEntry!(K, V) e = cast(MapEntry!(K, V))o;
2026         if (e !is null) {
2027             if (key == e.getKey() && value == e.getValue())
2028                 return true;
2029         }
2030         return false;
2031     }
2032 }
2033 
2034 
2035 /**
2036 * HashMap.Node subclass for normal LinkedHashMap entries.
2037 */
2038 static class LinkedHashMapEntry(K, V) : HashMapNode!(K, V) {
2039     LinkedHashMapEntry!(K, V) before, after;
2040     this(size_t hash, K key, V value, HashMapNode!(K, V) next) {
2041         super(hash, key, value, next);
2042     }
2043 }