1 module dstruct.map;
2 
3 import core.memory;
4 import core.exception;
5 
6 import std.range;
7 
8 import dstruct.support;
9 
10 private struct Entry(K, V) {
11     Entry* next;
12     size_t hash;
13     K key;
14     V value;
15 
16     @nogc @safe pure nothrow
17     this(size_t _hash, ref K _key, ref V _value) {
18         hash = _hash;
19         key = _key;
20         value = _value;
21     }
22 
23     @nogc @safe pure nothrow
24     this(size_t _hash, ref K _key, V _value) {
25         hash = _hash;
26         key = _key;
27         value = _value;
28     }
29 
30     @nogc @safe pure nothrow
31     this(size_t _hash, K _key, ref V _value) {
32         hash = _hash;
33         key = _key;
34         value = _value;
35     }
36 
37     @nogc @safe pure nothrow
38     this(size_t _hash, K _key, V _value) {
39         hash = _hash;
40         key = _key;
41         value = _value;
42     }
43 }
44 
45 @nogc @safe pure nothrow
46 private size_t hashIndex(size_t hash, size_t length) in {
47     assert(length > 0);
48 } body {
49     return hash & (length - 1);
50 }
51 
52 static if(__VERSION__ < 2066) {
53     private alias SafeGetHashType = size_t delegate(const(void*)) pure nothrow;
54 } else {
55     // Use mixin to hide UDA errors from old D compilers, it will never
56     // execute the mixin, so it won't report an error in syntax.
57     mixin("private alias SafeGetHashType = size_t delegate(const(void*)) @nogc pure nothrow;");
58 }
59 
60 @nogc @trusted pure nothrow
61 private size_t computeHash(K)(ref K key) {
62     // Cast so we can keep our function qualifiers.
63     return (cast(SafeGetHashType) &(typeid(K).getHash))(&key);
64 }
65 
66 // Check that computeHash is doing the right thing.
67 unittest {
68     int x = 1;
69     int y = 2;
70     int z = 3;
71 
72     assert(computeHash(x) == 1);
73     assert(computeHash(y) == 2);
74     assert(computeHash(z) == 3);
75 }
76 
77 /**
78  * This struct implements a hashmap type, much like the standard associative
79  * array type.
80  *
81  * This map should be almost totally usable in @safe pure nothrow functions.
82  *
83  * An empty map will be a valid object, and will not result in any allocations.
84  */
85 struct HashMap(K, V) {
86     alias ThisType = typeof(this);
87 
88     private Entry!(K, V)*[] bucket;
89     private size_t _length;
90 
91     @nogc @trusted pure nothrow
92     private Entry!(K, V)* topEntry(ref K key) const {
93         return cast(typeof(return))
94             bucket[hashIndex(computeHash(key), bucket.length)];
95     }
96 
97     @safe pure nothrow
98     private void resize(size_t newBucketLength) in {
99         assert(newBucketLength > bucket.length);
100     } body {
101         auto newBucket = new Entry!(K, V)*[newBucketLength];
102 
103         foreach(entry; bucket) {
104             while (entry !is null) {
105                 auto oldNext = entry.next;
106                 entry.next = null;
107 
108                 size_t index = hashIndex(entry.hash, newBucket.length);
109 
110                 if (newBucket[index] is null) {
111                     newBucket[index] = entry;
112                 } else {
113                     auto newPrev = newBucket[index];
114 
115                     while (newPrev.next !is null) {
116                         newPrev = newPrev.next;
117                     }
118 
119                     newPrev.next = entry;
120                 }
121 
122                 entry = oldNext;
123             }
124         }
125 
126         bucket = newBucket;
127     }
128 
129     @safe pure nothrow
130     private auto addNewEntry(size_t bucketIndex, Entry!(K, V)* newEntry) {
131         if (++_length > bucket.length) {
132             // The new length exceeds a threshold, so resize the bucket.
133             resize(bucket.length * 2);
134 
135             // Compute the index again, as it has changed.
136             bucketIndex = hashIndex(newEntry.hash, bucket.length);
137         }
138 
139         if (bucket[bucketIndex] is null) {
140             return bucket[bucketIndex] = newEntry;
141         } else {
142             auto entry = bucket[bucketIndex];
143 
144             while (entry.next !is null) {
145                 entry = entry.next;
146             }
147 
148             return entry.next = newEntry;
149         }
150     }
151 
152     /**
153      * Set a value in the map.
154      *
155      * Params:
156      *     key = The key in the map.
157      *     value = A value to set in the map.
158      */
159     @safe pure nothrow
160     void opIndexAssign(V value, K key) {
161         size_t hash = computeHash(key);
162 
163         if (bucket.length == 0) {
164             // 0 length is a special case.
165             _length = 1;
166             resize(4);
167 
168             // Add in the first value.
169             bucket[hashIndex(hash, bucket.length)] =
170                 new Entry!(K, V)(hash, key, value);
171             return;
172         }
173 
174         size_t bucketIndex = hashIndex(hash, bucket.length);
175 
176         if (auto entry = bucket[bucketIndex]) {
177             do {
178                 if (entry.key == key) {
179                     // We found a key match, so update the value and return.
180                     entry.value = value;
181                     return;
182                 }
183             } while (entry.next !is null);
184 
185             if (++_length <= bucket.length) {
186                 // We can add on another without needing a resize.
187                 entry.next = new Entry!(K, V)(hash, key, value);
188                 return;
189             }
190         } else if (++_length <= bucket.length) {
191             // We can slot this in right here without needing a resize.
192             bucket[bucketIndex] = new Entry!(K, V)(hash, key, value);
193             return;
194         }
195 
196         // The new length exceeds a threshold, so resize the bucket.
197         resize(bucket.length * 2);
198 
199         // Compute the index again, as it has changed.
200         bucketIndex = hashIndex(hash, bucket.length);
201 
202         if (auto entry = bucket[bucketIndex]) {
203             while (entry.next !is null) {
204                 entry = entry.next;
205             }
206 
207             entry.next = new Entry!(K, V)(hash, key, value);
208         } else {
209             bucket[bucketIndex] = new Entry!(K, V)(hash, key, value);
210         }
211     }
212 
213     /**
214      * Implement the 'in' operator for a map.
215      *
216      * The in operator on a map will return a pointer to a value, which will
217      * be null when no corresponding value is set for a given key.
218      *
219      * Params:
220      *     key = The key in the map.
221      *
222      * Returns:
223      *     A pointer to a value, a null pointer if a value is not set.
224      */
225     @nogc @safe pure nothrow
226     V* opBinaryRight(string op)(K key) const if (op == "in") {
227         for (auto entry = topEntry(key); entry; entry = entry.next) {
228             if (entry.key == key) {
229                 // We found it, so return a pointer to it.
230                 return &(entry.value);
231             }
232         }
233 
234         return null;
235     }
236 
237     /**
238      * Retrieve a value from the map.
239      *
240      * If a value is not set for the given key, a RangeError will be thrown.
241      *
242      * Params:
243      *     key = The key in the map.
244      *
245      * Returns:
246      *     A value from the map.
247      */
248     @nogc @safe pure nothrow
249     ref V opIndex(K key) const {
250         for (auto entry = topEntry(key); entry; entry = entry.next) {
251             if (entry.key == key) {
252                 return entry.value;
253             }
254         }
255 
256         assert(false, "Key not found in HashMap!");
257     }
258 
259     /**
260      * Get a value from the map, or return the given default value, which
261      * is lazy-evaluated.
262      *
263      * Params:
264      *     key = The key in the map.
265      *     def = A lazy default value.
266      *
267      * Returns:
268      *     A value from the map, or the default value.
269      */
270     @safe pure
271     V get(V2)(K key, lazy V2 def) const if(is(V2 : V)) {
272         for (auto entry = topEntry(key); entry; entry = entry.next) {
273             if (entry.key == key) {
274                 return entry.value;
275             }
276         }
277 
278         return def;
279     }
280 
281     /**
282      * Get a value from the map, or return V.init if a value is not set for
283      * a given key.
284      *
285      * Params:
286      *     key = The key in the map.
287      *
288      * Returns:
289      *     A value from the map, or the default value.
290      */
291     @nogc @safe pure nothrow
292     V get(K key) const {
293         for (auto entry = topEntry(key); entry; entry = entry.next) {
294             if (entry.key == key) {
295                 return entry.value;
296             }
297         }
298 
299         return V.init;
300     }
301 
302     /**
303      * Get or create a value from/in the map.
304      *
305      * Given a key, and a lazy evaluated default value,
306      * attempt to retrieve a value from the map. If a value for the given
307      * key is not set, set the provided default value in the map and
308      * return that.
309      *
310      * The value will be returned by reference.
311      *
312      * Params:
313      *     key = The key in the map.
314      *     def = A lazy default value.
315      *
316      * Returns:
317      *     A reference to the value in the map.
318      */
319     @trusted pure
320     ref V setDefault(V2)(K key, lazy V2 value) if (is(V2 : V)) {
321         size_t hash = computeHash(key);
322 
323         if (bucket.length == 0) {
324             // 0 length is a special case.
325             _length = 1;
326             resize(4);
327 
328             // Add in the first value.
329             return (bucket[hashIndex(hash, bucket.length)] =
330                 new Entry!(K, V)(hash, key, value)).value;
331         }
332 
333         size_t bucketIndex = hashIndex(hash, bucket.length);
334 
335         for (auto entry = bucket[bucketIndex]; entry; entry = entry.next) {
336             if (entry.key == key) {
337                 return entry.value;
338             }
339         }
340 
341         return addNewEntry(
342             bucketIndex,
343             new Entry!(K, V)(hash, key, value)
344         ).value;
345     }
346 
347     /**
348      * Get or create a value from/in a hashmap.
349      *
350      * Given a key attempt to retrieve a value from the hashmap.
351      * If a value for the given key is not set, set the value in
352      * the associative array to the default value for the value's type.
353      *
354      * The value will be returned by reference.
355      *
356      * Params:
357      *     key = The key in the map.
358      *
359      * Returns:
360      *     A reference to the value in the map.
361      */
362     @trusted pure nothrow
363     ref V setDefault(K key) {
364         size_t hash = computeHash(key);
365 
366         if (bucket.length == 0) {
367             // 0 length is a special case.
368             _length = 1;
369             resize(4);
370 
371             // Add in the first value.
372             return (bucket[hashIndex(hash, bucket.length)] =
373                 new Entry!(K, V)(hash, key, V.init)).value;
374         }
375 
376         size_t bucketIndex = hashIndex(hash, bucket.length);
377 
378         for (auto entry = bucket[bucketIndex]; entry; entry = entry.next) {
379             if (entry.key == key) {
380                 return entry.value;
381             }
382         }
383 
384         return addNewEntry(
385             bucketIndex,
386             new Entry!(K, V)(hash, key, V.init)
387         ).value;
388     }
389 
390     /**
391      * Remove a entry from the map if it is set, given a key.
392      *
393      * Params:
394      *     key = The key in the map.
395      *
396      * Returns:
397      *     true if a value was removed, otherwise false.
398      */
399     @nogc @safe pure nothrow
400     bool remove(K key) {
401         size_t bucketIndex = hashIndex(computeHash(key), bucket.length);
402         auto arr = bucket[bucketIndex];
403 
404         Entry!(K, V)* lastEntry = null;
405         Entry!(K, V)* entry = bucket[bucketIndex];
406 
407         while (entry !is null) {
408             if (entry.key == key) {
409                 // We found a match, so remove the entry.
410                 if (lastEntry is null) {
411                     bucket[bucketIndex] = entry.next;
412                 } else {
413                     lastEntry.next = entry.next;
414                 }
415 
416                 --_length;
417                 return true;
418             }
419 
420             lastEntry = entry;
421             entry = entry.next;
422         }
423 
424         return false;
425     }
426 
427     /**
428      * The length of the map.
429      *
430      * Returns: The number of entries in the map, in constant time.
431      */
432     @nogc @safe pure nothrow
433     @property
434     size_t length() const {
435         return _length;
436     }
437 
438     /**
439      * Test if two maps are equal.
440      *
441      * Params:
442      *     otherMap = Another map.
443      *
444      * Returns:
445      *     true only if the maps are equal in length, keys, and values.
446      */
447     @nogc @safe pure nothrow
448     bool opEquals(ref const(HashMap!(K, V)) otherMap) const {
449         if (_length != otherMap._length) {
450             return false;
451         }
452 
453         foreach(const(Entry!(K, V))* entry; bucket) {
454             leftLoop: for(; entry; entry = entry.next) {
455                 const(Entry!(K, V))* otherEntry = otherMap.bucket[
456                     hashIndex(entry.hash, otherMap.bucket.length)
457                 ];
458 
459                 for(; otherEntry; otherEntry = otherEntry.next) {
460                     if (entry.hash == otherEntry.hash
461                     && entry.key == otherEntry.key
462                     && entry.value == otherEntry.value) {
463                         // We found this entry in the other map,
464                         // So search with the next entry.
465                         continue leftLoop;
466                     }
467                 }
468 
469                 // No match found for this entry.
470                 return false;
471             }
472         }
473 
474         return true;
475     }
476 
477     /// ditto
478     @nogc @safe pure nothrow
479     bool opEquals(const(HashMap!(K, V)) otherMap) const {
480         return opEquals(otherMap);
481     }
482 }
483 
484 template HashMapKeyType(T) {
485     alias HashMapKeyType = typeof(ElementType!(typeof(T.bucket)).key);
486 }
487 
488 template HashMapValueType(T) {
489     alias HashMapValueType = typeof(ElementType!(typeof(T.bucket)).value);
490 }
491 
492 // Check setting values, retrieval, removal, and lengths.
493 unittest {
494     HashMap!(int, string) map;
495 
496     map[1] = "a";
497     map[2] = "b";
498     map[3] = "c";
499 
500     map[1] = "x";
501     map[2] = "y";
502     map[3] = "z";
503 
504     assert(map.length == 3);
505 
506     assert(map[1] == "x");
507     assert(map[2] == "y");
508     assert(map[3] == "z");
509 
510     assert(map.remove(3));
511     assert(map.remove(2));
512     assert(map.remove(1));
513 
514     assert(!map.remove(1));
515 
516     assert(map.length == 0);
517 }
518 
519 // Test the 'in' operator.
520 unittest {
521     HashMap!(int, string) map;
522 
523     map[1] = "a";
524     map[2] = "b";
525     map[3] = "c";
526 
527     assert((4 in map) is null);
528 
529     assert(*(1 in map) == "a");
530     assert(*(2 in map) == "b");
531     assert(*(3 in map) == "c");
532 }
533 
534 // Test get with default init
535 unittest {
536     HashMap!(int, string) map;
537 
538     map[1] = "a";
539 
540     assert(map.get(1) == "a");
541     assert(map.get(2) is null);
542 }
543 
544 // Test get with a given default.
545 unittest {
546     HashMap!(int, string) map;
547 
548     map[1] = "a";
549 
550     assert(map.get(1, "b") == "a");
551     assert(map.get(2, "b") == "b");
552 }
553 
554 // Test opEquals
555 unittest {
556     HashMap!(string, string) leftMap;
557     HashMap!(string, string) rightMap;
558 
559     // Give the left one a bit more, and take away from it.
560     leftMap["a"] = "1";
561     leftMap["b"] = "2";
562     leftMap["c"] = "3";
563     leftMap["d"] = "4";
564     leftMap["e"] = "5";
565     leftMap["f"] = "6";
566     leftMap["g"] = "7";
567 
568     // Remove the extra keys
569     leftMap.remove("d");
570     leftMap.remove("e");
571     leftMap.remove("f");
572     leftMap.remove("g");
573 
574     rightMap["a"] = "1";
575     rightMap["b"] = "2";
576     rightMap["c"] = "3";
577 
578     // Now the two maps should have different buckets, but they
579     // should still be considered equal.
580     assert(leftMap == rightMap);
581 }
582 
583 // Test setDefault with default init
584 unittest {
585     HashMap!(int, string) map;
586 
587     map[1] = "a";
588 
589     assert(map.setDefault(1) == "a");
590     assert(map.setDefault(2) is null);
591 
592     assert(map.length == 2);
593 
594     assert(map[2] is null);
595 }
596 
597 // Test setDefault with a given value.
598 unittest {
599     HashMap!(int, string) map;
600 
601     map[1] = "a";
602 
603     assert(map.setDefault(1, "b") == "a");
604     assert(map.setDefault(2, "b") == "b");
605 
606     assert(map.length == 2);
607 
608     assert(map[2] == "b");
609 }
610 
611 // Test setDefault with a given value which can be implicitly converted.
612 unittest {
613     HashMap!(int, long) map;
614 
615     map[1] = 2;
616 
617     assert(map.setDefault(1, 3) == 2);
618 
619     int x = 4;
620 
621     assert(map.setDefault(2, x) == 4);
622 
623     assert(map.length == 2);
624 
625     assert(map[2] == 4);
626 }
627 
628 unittest {
629     int[string] map = ["foo": 3];
630 
631     auto val1 = map["foo"];
632     auto val2 = map.setDefault("bar", 4);
633 
634     assert(val1 == 3);
635     assert(val2 == 4);
636 }
637 
638 private struct EntryRange(K, V) {
639 private:
640     Entry!(K, V)*[] _bucket;
641     Entry!(K, V)* _entry;
642 public:
643     @nogc @safe pure nothrow
644     this(Entry!(K, V)*[] bucket) {
645         _bucket = bucket;
646 
647         while(_bucket.length > 0) {
648             _entry = _bucket[0];
649 
650             if (_entry !is null) {
651                 return;
652             }
653 
654             _bucket = _bucket[1 .. $];
655         }
656     }
657 
658     @nogc @trusted pure nothrow
659     this(const(Entry!(K, V)*[]) bucket) {
660         this(cast(Entry!(K, V)*[]) bucket);
661     }
662 
663     @nogc @safe pure nothrow
664     inout(typeof(this)) save() inout {
665         return this;
666     }
667 
668     @nogc @safe pure nothrow
669     @property
670     bool empty() const {
671         return _entry is null;
672     }
673 
674     @nogc @safe pure nothrow
675     @property
676     inout(Entry!(K, V)*) front() inout in {
677         assert(!empty());
678     } body {
679         return _entry;
680     }
681 
682     @nogc @safe pure nothrow
683     void popFront() in {
684         assert(!empty());
685     } body {
686         if (_entry.next !is null) {
687             // We have a another entry in the linked list, so skip to that.
688             _entry = _entry.next;
689             return;
690         }
691 
692         _bucket = _bucket[1 .. $];
693 
694         // Keep advancing until we find the start of another linked list,
695         // or we run off the end.
696         while (_bucket.length > 0) {
697             _entry = _bucket[0];
698 
699             if (_entry !is null) {
700                 return;
701             }
702 
703             _bucket = _bucket[1 .. $];
704         }
705 
706         // Clear the entry if we hit the end.
707         _entry = null;
708     }
709 }
710 
711 /**
712  * This is a range which runs through a series of keys in map.
713  */
714 struct KeyRange(K, V) {
715 private:
716     EntryRange!(K, V) _entryRange;
717 public:
718     @nogc @safe pure nothrow
719     private this()(auto ref Entry!(K, V)*[] bucket) {
720         _entryRange = EntryRange!(K, V)(bucket);
721     }
722 
723     ///
724     @nogc @safe pure nothrow
725     inout(typeof(this)) save() inout {
726         return this;
727     }
728 
729     ///
730     @nogc @safe pure nothrow
731     @property
732     bool empty() const {
733         return _entryRange.empty;
734     }
735 
736     ///
737     @nogc @trusted pure nothrow
738     @property
739     ref inout(K) front() inout {
740         return _entryRange.front.key;
741     }
742 
743     ///
744     @nogc @safe pure nothrow
745     void popFront() {
746         _entryRange.popFront();
747     }
748 }
749 
750 /**
751  * Produce a range through the keys of a map.
752  *
753  * Params:
754  *     map = A map.
755  * Returns:
756  *     A range running through the keys in the map.
757  */
758 @nogc @safe pure nothrow
759 auto keys(K, V)(auto ref HashMap!(K, V) map) {
760     return KeyRange!(K, V)(map.bucket);
761 }
762 
763 /// ditto
764 @nogc @trusted pure nothrow
765 auto keys(K, V)(auto ref const(HashMap!(K, V)) map) {
766     alias RealK = HashMapKeyType!(typeof(map));
767     alias RealV = HashMapValueType!(typeof(map));
768 
769     return KeyRange!(RealK, RealV)(
770         cast(Entry!(RealK, RealV)*[])
771         map.bucket
772     );
773 }
774 
775 /// ditto
776 @nogc @trusted pure nothrow
777 auto keys(K, V)(auto ref immutable(HashMap!(K, V)) map) {
778     alias RealK = HashMapKeyType!(typeof(map));
779     alias RealV = HashMapValueType!(typeof(map));
780 
781     return KeyRange!(RealK, RealV)(
782         cast(Entry!(RealK, RealV)*[])
783         map.bucket
784     );
785 }
786 
787 unittest {
788     HashMap!(int, string) map;
789 
790     map[1] = "a";
791     map[2] = "b";
792     map[3] = "c";
793 
794     int[] keyList;
795 
796     foreach(ref key; map.keys()) {
797         keyList ~= key;
798     }
799 
800     // From the way the buckets are distributed, we know we'll get this back.
801     assert(keyList == [1, 2, 3]);
802 }
803 
804 unittest {
805     HashMap!(string, string) mmap;
806     const(HashMap!(string, string)) cmap;
807     immutable(HashMap!(string, string)) imap;
808 
809     auto mKeys = mmap.keys();
810     auto cKeys = cmap.keys();
811     auto iKeys = imap.keys();
812 
813     assert(is(typeof(mKeys.front) == string));
814     assert(is(typeof(cKeys.front) == const(string)));
815     assert(is(typeof(iKeys.front) == immutable(string)));
816 }
817 
818 /**
819  * This is a range which runs through a series of values in a map.
820  */
821 struct ValueRange(K, V) {
822 private:
823     EntryRange!(K, V) _entryRange;
824 public:
825     @nogc @safe pure nothrow
826     private this()(auto ref Entry!(K, V)*[] bucket) {
827         _entryRange = EntryRange!(K, V)(bucket);
828     }
829 
830     ///
831     @nogc @safe pure nothrow
832     inout(typeof(this)) save() inout {
833         return this;
834     }
835 
836     ///
837     @nogc @safe pure nothrow
838     @property
839     bool empty() const {
840         return _entryRange.empty;
841     }
842 
843     ///
844     @nogc @trusted pure nothrow
845     @property
846     ref inout(V) front() inout {
847         return _entryRange.front.value;
848     }
849 
850     ///
851 
852     @nogc @safe pure nothrow
853     void popFront() {
854         _entryRange.popFront();
855     }
856 }
857 
858 /**
859  * Produce a range through the values of a map.
860  *
861  * Params:
862  *     map = A map.
863  * Returns:
864  *     A range running through the values in the map.
865  */
866 @nogc @safe pure nothrow
867 auto values(K, V)(auto ref HashMap!(K, V) map) {
868     return ValueRange!(K, V)(map.bucket);
869 }
870 
871 /// ditto
872 @nogc @trusted pure nothrow
873 auto values(K, V)(auto ref const(HashMap!(K, V)) map) {
874     alias RealK = HashMapKeyType!(typeof(map));
875     alias RealV = HashMapValueType!(typeof(map));
876 
877     return ValueRange!(RealK, RealV)(
878         cast(Entry!(RealK, RealV)*[])
879         map.bucket
880     );
881 }
882 
883 /// ditto
884 @nogc @trusted pure nothrow
885 auto values(K, V)(auto ref immutable(HashMap!(K, V)) map) {
886     alias RealK = HashMapKeyType!(typeof(map));
887     alias RealV = HashMapValueType!(typeof(map));
888 
889     return ValueRange!(RealK, RealV)(
890         cast(Entry!(RealK, RealV)*[])
891         map.bucket
892     );
893 }
894 
895 unittest {
896     HashMap!(int, string) map;
897 
898     map[1] = "a";
899     map[2] = "b";
900     map[3] = "c";
901 
902     string[] valueList = [];
903 
904     foreach(ref value; map.values()) {
905         valueList ~= value;
906     }
907 
908     // From the way the buckets are distributed, we know we'll get this back.
909     assert(valueList == ["a", "b", "c"]);
910 }
911 
912 unittest {
913     HashMap!(string, string) mmap;
914     const(HashMap!(string, string)) cmap;
915     immutable(HashMap!(string, string)) imap;
916 
917     auto mValues = mmap.values();
918     auto cValues = cmap.values();
919     auto iValues = imap.values();
920 
921     assert(is(typeof(mValues.front) == string));
922     assert(is(typeof(cValues.front) == const(string)));
923     assert(is(typeof(iValues.front) == immutable(string)));
924 }
925 
926 /**
927  * An item from a map.
928  *
929  * The keys and the values in the map are references into the map itself.
930  */
931 struct Item(K, V) {
932 private:
933     Entry!(K, V)* _entry;
934 
935     @nogc @safe pure nothrow
936     this(inout(Entry!(K, V)*) entry) inout in {
937         assert(entry !is null);
938     } body {
939         _entry = entry;
940     }
941 public:
942     ///
943     @disable this();
944 
945     /**
946      * A key from the map.
947      */
948     @nogc @safe pure nothrow
949     @property ref inout(K) key() inout {
950         return _entry.key;
951     }
952 
953     /**
954      * A value from the map.
955      */
956     @nogc @safe pure nothrow
957     @property ref inout(V) value() inout {
958         return _entry.value;
959     }
960 }
961 
962 /**
963  * A range through a series of items in the map.
964  */
965 struct ItemRange(K, V) {
966 private:
967     EntryRange!(K, V) _entryRange;
968 public:
969     @nogc @safe pure nothrow
970     private this()(auto ref Entry!(K, V)*[] bucket) {
971         _entryRange = EntryRange!(K, V)(bucket);
972     }
973 
974     ///
975     @nogc @safe pure nothrow
976     inout(typeof(this)) save() inout {
977         return this;
978     }
979 
980     ///
981     @nogc @safe pure nothrow
982     @property
983     bool empty() const {
984         return _entryRange.empty;
985     }
986 
987     ///
988     @nogc @safe pure nothrow
989     @property
990     inout(Item!(K, V)) front() inout {
991         return typeof(return)(_entryRange.front);
992     }
993 
994     ///
995     @nogc @safe pure nothrow
996     void popFront() {
997         _entryRange.popFront();
998     }
999 }
1000 
1001 /**
1002  * Produce a range through the items of a map. (A key-value pair)
1003  *
1004  * Params:
1005  *     map = A map.
1006  * Returns:
1007  *     A range running through the items in the map.
1008  */
1009 @nogc @safe pure nothrow
1010 auto items(K, V)(auto ref HashMap!(K, V) map) {
1011     return ItemRange!(K, V)(map.bucket);
1012 }
1013 
1014 /// ditto
1015 @nogc @trusted pure nothrow
1016 auto items(K, V)(auto ref const(HashMap!(K, V)) map) {
1017     alias RealK = HashMapKeyType!(typeof(map));
1018     alias RealV = HashMapValueType!(typeof(map));
1019 
1020     return ItemRange!(RealK, RealV)(
1021         cast(Entry!(RealK, RealV)*[])
1022         map.bucket
1023     );
1024 }
1025 
1026 /// ditto
1027 @nogc @trusted pure nothrow
1028 auto items(K, V)(auto ref immutable(HashMap!(K, V)) map) {
1029     alias RealK = HashMapKeyType!(typeof(map));
1030     alias RealV = HashMapValueType!(typeof(map));
1031 
1032     return ItemRange!(RealK, RealV)(
1033         cast(Entry!(RealK, RealV)*[])
1034         map.bucket
1035     );
1036 }
1037 
1038 unittest {
1039     HashMap!(int, string) map;
1040 
1041     map[1] = "a";
1042     map[2] = "b";
1043     map[3] = "c";
1044 
1045     int[] keyList;
1046     string[] valueList;
1047 
1048     foreach(item; map.items()) {
1049         keyList ~= item.key;
1050         valueList ~= item.value;
1051     }
1052 
1053     // From the way the buckets are distributed, we know we'll get this back.
1054     assert(keyList == [1, 2, 3]);
1055     assert(valueList == ["a", "b", "c"]);
1056 }
1057 
1058 unittest {
1059     HashMap!(string, string) mmap;
1060     const(HashMap!(string, string)) cmap;
1061     immutable(HashMap!(string, string)) imap;
1062 
1063     auto mItems = mmap.items();
1064     auto cItems = cmap.items();
1065     auto iItems = imap.items();
1066 
1067     assert(is(typeof(mItems.front.key) == string));
1068     assert(is(typeof(cItems.front.key) == const(string)));
1069     assert(is(typeof(iItems.front.key) == immutable(string)));
1070     assert(is(typeof(mItems.front.value) == string));
1071     assert(is(typeof(cItems.front.value) == const(string)));
1072     assert(is(typeof(iItems.front.value) == immutable(string)));
1073 }
1074 
1075 // Test that the ranges can be created from r-values.
1076 unittest {
1077     auto func() {
1078         HashMap!(int, string) map;
1079 
1080         map[1] = "a";
1081         map[2] = "b";
1082         map[3] = "c";
1083 
1084         return map;
1085     }
1086 
1087     auto keyRange = func().keys();
1088     auto valueRange = func().values();
1089     auto itemRange = func().items();
1090 }
1091 
1092 /**
1093  * Get or create a value from/in an associative array.
1094  *
1095  * Given an associative array to modify, a key, and a
1096  * lazy evaluated default value, attempt to retrieve a value from
1097  * an associative array. If a value for the given key is not set,
1098  * set the provided default value in the associative array and
1099  * return that.
1100  *
1101  * The value will be returned by reference.
1102  *
1103  * Params:
1104  *     map = The associative array to modify.
1105  *     key = The key in the associative array.
1106  *     def = A lazy default value.
1107  *
1108  * Returns:
1109  *     A reference to the value in the associative array.
1110  */
1111 @safe pure
1112 ref V1 setDefault(K, V1, V2)(ref V1[K] map, K key, lazy V2 def)
1113 if (is(V2 : V1)) {
1114     V1* valPtr = key in map;
1115 
1116     if (valPtr != null) {
1117         return *valPtr;
1118     }
1119 
1120     map[key] = def();
1121 
1122     return map[key];
1123 }
1124 
1125 /**
1126  * Get or create a value from/in an associative array.
1127  *
1128  * Given an associative array to modify and a key,
1129  * attempt to retrieve a value from the associative array.
1130  * If a value for the given key is not set, set the value in
1131  * the associative array to the default value for the value's type.
1132  *
1133  * The value will be returned by reference.
1134  *
1135  * Params:
1136  *     map = The associative array to modify.
1137  *     key = The key in the associative array.
1138  *
1139  * Returns:
1140  *     A reference to the value in the associative array.
1141  */
1142 @safe pure nothrow
1143 ref V setDefault(K, V)(ref V[K] map, K key) {
1144     V* valPtr = key in map;
1145 
1146     if (valPtr != null) {
1147         return *valPtr;
1148     }
1149 
1150     map[key] = V.init;
1151 
1152     return map[key];
1153 }
1154 
1155 unittest {
1156     int[string] map = ["foo": 3];
1157 
1158     auto val1 = map["foo"];
1159     auto val2 = map.setDefault("bar");
1160 
1161     assert(val1 == 3);
1162     assert(val2 == 0);
1163 }
1164 
1165 /**
1166  * Copy an existing map into a new mutable map.
1167  *
1168  * Params:
1169  *     originalMap = The map to copy from.
1170  *
1171  * Returns:
1172  *     The fresh copy of the map.
1173  */
1174 @safe pure nothrow
1175 HashMap!(K, V) dup(K, V)(ref const(HashMap!(K, V)) originalMap)
1176 if(isDupable!K && isDupable!V) {
1177     import std.math;
1178 
1179     HashMap!(K, V) newMap;
1180 
1181     if (originalMap._length == 0) {
1182         // 0 is a special case.
1183         return newMap;
1184     } else if (originalMap._length <= 4) {
1185         newMap.bucket = new Entry!(K, V)*[4];
1186     } else {
1187         // Allocate a power of two bucket size large enough to fit this.
1188         newMap.bucket = new Entry!(K, V)*[
1189             cast(size_t) 2 ^^ ceil(log2(originalMap._length))
1190         ];
1191     }
1192 
1193     newMap._length = originalMap._length;
1194 
1195     foreach(const(Entry!(K, V))* entry; originalMap.bucket) {
1196         leftLoop: for(; entry; entry = entry.next) {
1197             size_t newIndex = hashIndex(entry.hash, newMap.bucket.length);
1198             auto otherEntry = newMap.bucket[newIndex];
1199 
1200             if (otherEntry is null) {
1201                 newMap.bucket[newIndex] = new Entry!(K, V)(
1202                     entry.hash, entry.key, entry.value
1203                 );
1204             } else {
1205                 // Skip ahead till we hit the last entry.
1206                 while (otherEntry.next !is null) {
1207                     otherEntry = otherEntry.next;
1208                 }
1209 
1210                 otherEntry.next = new Entry!(K, V)(
1211                     entry.hash, entry.key, entry.value
1212                 );
1213             }
1214         }
1215     }
1216 
1217     return newMap;
1218 }
1219 
1220 /// ditto
1221 @safe pure nothrow
1222 HashMap!(K, V) dup(K, V)(const(HashMap!(K, V)) originalMap)
1223 if(isDupable!K && isDupable!V) {
1224     return originalMap.dup();
1225 }
1226 
1227 unittest {
1228     const(HashMap!(int, int)) createMap() {
1229         HashMap!(int, int) map;
1230 
1231         map[3] = 4;
1232         map[4] = 7;
1233 
1234         return map;
1235     }
1236 
1237     auto map = createMap();
1238     auto newMap = map.dup;
1239     // Test r-values.
1240     auto thirdMap = createMap().dup();
1241 
1242     assert(map == newMap);
1243 }
1244 
1245 unittest {
1246     HashMap!(int, void[0]) map;
1247 
1248     auto x = map.dup;
1249 }