1 /**
2  * Associative Array utility functions
3  *
4  * License:
5  *   This Source Code Form is subject to the terms of
6  *   the Mozilla Public License, v. 2.0. If a copy of
7  *   the MPL was not distributed with this file, You
8  *   can obtain one at http://mozilla.org/MPL/2.0/.
9  *
10  * Authors:
11  *   Vladimir Panteleev <ae@cy.md>
12  */
13 
14 module ae.utils.aa;
15 
16 import std.algorithm;
17 import std.range;
18 import std.traits;
19 import std.typecons;
20 
21 import ae.utils.meta : progn, BoxVoid, BoxedVoid;
22 
23 // ***************************************************************************
24 
25 /// Polyfill for object.require
26 static if (!__traits(hasMember, object, "require"))
27 ref V require(K, V)(ref V[K] aa, K key, lazy V value = V.init)
28 {
29 	auto p = key in aa;
30 	if (p)
31 		return *p;
32 	return aa[key] = value;
33 }
34 
35 debug(ae_unittest) unittest
36 {
37 	int[int] aa;
38 	aa.require(1, 2);
39 	assert(aa[1] == 2);
40 	aa.require(2, 3) = 4;
41 	assert(aa[2] == 4);
42 	aa.require(1, 5);
43 	assert(aa[1] == 2);
44 	aa.require(1, 6) = 7;
45 	assert(aa[1] == 7);
46 }
47 
48 static if (!__traits(hasMember, object, "update"))
49 {
50 	/// Polyfill for object.update
51 	void updatePolyfill(K, V, C, U)(ref V[K] aa, K key, scope C create, scope U update)
52 	if (is(typeof(create()) : V) && is(typeof(update(aa[K.init])) : V))
53 	{
54 		auto p = key in aa;
55 		if (p)
56 			*p = update(*p);
57 		else
58 			aa[key] = create();
59 	}
60 
61 	/// Work around https://issues.dlang.org/show_bug.cgi?id=15795
62 	alias update = updatePolyfill;
63 }
64 
65 // https://github.com/dlang/druntime/pull/3012
66 private enum haveObjectUpdateWithVoidUpdate = is(typeof({
67 	int[int] aa;
68 	.object.update(aa, 0, { return 0; }, (ref int v) { });
69 }));
70 
71 static if (!haveObjectUpdateWithVoidUpdate)
72 {
73 	/// Polyfill for object.update with void update function
74 	void updateVoid(K, V, C, U)(ref V[K] aa, K key, scope C create, scope U update)
75 	if (is(typeof(create()) : V) && is(typeof(update(aa[K.init])) == void))
76 	{
77 		// We can polyfill this in two ways.
78 		// What's more expensive, copying the value, or a second key lookup?
79 		enum haveObjectUpdate = __traits(hasMember, object, "update");
80 		enum valueIsExpensiveToCopy = V.sizeof > string.sizeof
81 			|| hasElaborateCopyConstructor!V
82 			|| hasElaborateDestructor!V;
83 		static if (haveObjectUpdate && !valueIsExpensiveToCopy)
84 		{
85 			.object.update(aa, key,
86 				delegate V() { return create(); },
87 				(ref V v) { update(v); return v; });
88 		}
89 		else
90 		{
91 			auto p = key in aa;
92 			if (p)
93 				update(*p);
94 			else
95 				aa[key] = create();
96 		}
97 	}
98 
99 	/// Work around https://issues.dlang.org/show_bug.cgi?id=15795
100 	alias update = updateVoid;
101 }
102 else
103 	alias updateVoid = object.update; /// Use `object.update` for void update function
104 
105 // Inject overload
106 static if (__traits(hasMember, object, "update"))
107 	private alias update = object.update;
108 
109 // ***************************************************************************
110 
111 /// Get a value from an AA, and throw an exception (not an error) if not found
112 ref auto aaGet(AA, K)(auto ref AA aa, auto ref K key)
113 	if (is(typeof(key in aa)))
114 {
115 	import std.conv;
116 
117 	auto p = key in aa;
118 	if (p)
119 		return *p;
120 	else
121 		static if (is(typeof(text(key))))
122 			throw new Exception("Absent value: " ~ text(key));
123 		else
124 			throw new Exception("Absent value");
125 }
126 
127 /// If key is not in aa, add it with defaultValue.
128 /// Returns a reference to the value corresponding to key.
129 ref V getOrAdd(K, V)(ref V[K] aa, auto ref K key, auto ref V defaultValue)
130 {
131 	return aa.require(key, defaultValue);
132 }
133 
134 /// ditto
135 ref V getOrAdd(K, V)(ref V[K] aa, auto ref K key)
136 {
137 	return getOrAdd(aa, key, V.init);
138 }
139 
140 debug(ae_unittest) unittest
141 {
142 	int[int] aa;
143 	aa.getOrAdd(1, 2) = 3;
144 	assert(aa[1] == 3);
145 	assert(aa.getOrAdd(1, 4) == 3);
146 }
147 
148 /// If key is not in aa, add it with the given value, and return true.
149 /// Otherwise, return false.
150 bool addNew(K, V)(ref V[K] aa, auto ref K key, auto ref V value)
151 {
152 	bool added = void;
153 	updateVoid(aa, key,
154 		delegate V   (       ) { added = true ; return value; },
155 		delegate void(ref V v) { added = false;               },
156 	);
157 	return added;
158 }
159 
160 debug(ae_unittest) unittest
161 {
162 	int[int] aa;
163 	assert( aa.addNew(1, 2));
164 	assert(!aa.addNew(1, 3));
165 	assert(aa[1] == 2);
166 }
167 
168 debug(ae_unittest) unittest
169 {
170 	OrderedMap!(int, int) aa;
171 	assert( aa.addNew(1, 2));
172 	assert(!aa.addNew(1, 3));
173 	assert(aa[1] == 2);
174 }
175 
176 // ***************************************************************************
177 
178 /// Key/value pair
179 struct KeyValuePair(K, V) { K key; /***/ V value; /***/ }
180 
181 /// Get key/value pairs from AA
182 deprecated KeyValuePair!(K, V)[] pairs(K, V)(V[K] aa)
183 {
184 	KeyValuePair!(K, V)[] result;
185 	foreach (key, value; aa)
186 		result ~= KeyValuePair!(K, V)(key, value);
187 	return result;
188 }
189 
190 /// Get key/value pairs from AA, sorted by keys
191 KeyValuePair!(K, V)[] sortedPairs(K, V)(V[K] aa)
192 {
193 	KeyValuePair!(K, V)[] result;
194 	foreach (key; aa.keys.sort)
195 		result ~= KeyValuePair!(K, V)(key, aa[key]);
196 	return result;
197 }
198 
199 /// Get values from AA, sorted by keys
200 V[] sortedValues(K, V)(in V[K] aa)
201 {
202 	V[] result;
203 	foreach (key; aa.keys.sort())
204 		result ~= aa[key];
205 	return result;
206 }
207 
208 /// Merge source into target. Return target.
209 V[K] merge(K, V)(auto ref V[K] target, V[K] source)
210 {
211 	foreach (k, v; source)
212 		target[k] = v;
213 	return target;
214 }
215 
216 debug(ae_unittest) unittest
217 {
218 	int[int] target;
219 	int[int] source = [2:4];
220 	merge(target, source);
221 	assert(source == target);
222 
223 	target = [1:1, 2:2, 3:3];
224 	merge(target, source);
225 	assert(target == [1:1, 2:4, 3:3]);
226 
227 	assert(merge([1:1], [2:2]) == [1:1, 2:2]);
228 }
229 
230 debug(ae_unittest) unittest
231 {
232 	ubyte[][string] a, b;
233 	merge(a, b);
234 }
235 
236 /// Slurp a range of two elements (or two-element struct/class) into an AA.
237 auto toAA(R)(R r)
238 	if (is(typeof(r.front[1])))
239 {
240 	alias K = typeof(r.front[0]);
241 	alias V = typeof(r.front[1]);
242 	V[K] result;
243 	foreach (pair; r)
244 	{
245 		assert(pair.length == 2);
246 		result[pair[0]] = pair[1];
247 	}
248 	return result;
249 }
250 
251 /// ditto
252 auto toAA(R)(R r)
253 	if (is(typeof(r.front.tupleof)) && r.front.tupleof.length == 2 && !is(typeof(r.front[1])))
254 {
255 	return r.map!(el => tuple(el.tupleof)).toAA();
256 }
257 
258 debug(ae_unittest) deprecated unittest
259 {
260 	assert([[2, 4]].toAA() == [2:4]);
261 	assert([2:4].pairs.toAA() == [2:4]);
262 }
263 
264 /// Ensure that arr is non-null if empty.
265 V[K] nonNull(K, V)(V[K] aa)
266 {
267 	if (aa !is null)
268 		return aa;
269 	aa[K.init] = V.init;
270 	aa.remove(K.init);
271 	assert(aa !is null);
272 	return aa;
273 }
274 
275 debug(ae_unittest) unittest
276 {
277 	int[int] aa;
278 	assert(aa is null);
279 	aa = aa.nonNull;
280 	assert(aa !is null);
281 	assert(aa.length == 0);
282 }
283 
284 // ***************************************************************************
285 
286 // Helpers for HashCollection
287 private
288 {
289 	alias Void = BoxedVoid;
290 	static assert(Void.sizeof == 0);
291 
292 	// Abstraction layer for single/multi-value type holding one or many T.
293 	// Optimizer representation for Void.
294 	struct SingleOrMultiValue(bool multi, T)
295 	{
296 		alias ValueType = Select!(multi,
297 			// multi==true
298 			Select!(is(T == Void),
299 				size_t, // "store" the items by keeping track of their count only.
300 				T[],
301 			),
302 
303 			// multi==false
304 			Select!(is(T == Void),
305 				Void,
306 				T[1],
307 			),
308 		);
309 
310 		// Using free functions instead of struct methods,
311 		// as structs always have non-zero size.
312 	static:
313 
314 		size_t length(ref const ValueType v) nothrow
315 		{
316 			static if (is(T == Void))
317 				static if (multi)
318 					return v; // count
319 				else
320 					return 1;
321 			else
322 				return v.length; // static or dynamic array
323 		}
324 	}
325 }
326 
327 /// Base type for ordered/unordered single-value/multi-value map/set
328 /*private*/ struct HashCollection(K, V, bool ordered, bool multi)
329 {
330 private:
331 	enum bool haveValues = !is(V == void); // Not a set
332 
333 	// The type for values used when a value variable is needed
334 	alias ValueVarType = Select!(haveValues, V, Void);
335 
336 	// The type of a single element of the values of `this.lookup`.
337 	// When ordered==true, we use size_t (index into `this.items`).
338 	alias LookupItem = Select!(ordered, size_t, ValueVarType);
339 
340 	// The type of the values of `this.lookup`.
341 	alias SM = SingleOrMultiValue!(multi, LookupItem);
342 	alias LookupValue = SM.ValueType;
343 
344 	// Return type of assign operations, "in" operator, etc.
345 	static if (haveValues)
346 		alias ReturnType = V;
347 	else
348 		alias ReturnType = void;
349 	enum haveReturnType = !is(ReturnType == void);
350 
351 	static if (ordered)
352 		alias OrderIndex = size_t;
353 	else
354 		alias OrderIndex = void;
355 
356 	// DWIM: a[k] should mean key lookup for maps,
357 	// otherwise index lookup for ordered sets.
358 	static if (haveValues)
359 	{
360 		alias OpIndexKeyType = K;
361 		alias OpIndexValueType = V; // also the return type of opIndex
362 	}
363 	else
364 	{
365 		static if (ordered)
366 		{
367 			alias OpIndexKeyType = size_t;
368 			alias OpIndexValueType = K;
369 		}
370 		else
371 		{
372 			alias OpIndexKeyType = void;
373 			alias OpIndexValueType = void;
374 		}
375 	}
376 	enum haveIndexing = !is(OpIndexKeyType == void);
377 	static assert(haveIndexing == haveValues || ordered);
378 	alias IK = OpIndexKeyType;
379 	alias IV = OpIndexValueType;
380 
381 	// The contract we try to follow is that adding/removing items in
382 	// one copy of the object will not affect other copies.
383 	// Therefore, when we have array fields, make sure they are dup'd
384 	// on copy, so that we don't trample older copies' data.
385 	enum bool needDupOnCopy = ordered;
386 
387 	static if (ordered)
388 		/*  */ ref inout(ReturnType) lookupToReturnValue(in        LookupItem  lookupItem) inout { return items[lookupItem].returnValue; }
389 	else
390 	static if (haveValues)
391 		static ref inout(ReturnType) lookupToReturnValue(ref inout(LookupItem) lookupItem)       { return       lookupItem             ; }
392 	else
393 		static ref inout(ReturnType) lookupToReturnValue(ref inout(LookupItem) lookupItem)       {                                       }
394 
395 	static if (ordered)
396 		/*  */ ref inout(IV) lookupToIndexValue(in        LookupItem  lookupItem) inout { return items[lookupItem].indexValue; }
397 	else
398 	static if (haveValues)
399 		static ref inout(IV) lookupToIndexValue(ref inout(LookupItem) lookupItem)       { return       lookupItem            ; }
400 	else
401 		static ref inout(IV) lookupToIndexValue(ref inout(LookupItem) lookupItem)       {                                      }
402 
403 	// *** Data ***
404 
405 	// This is used for all key hash lookups.
406 	LookupValue[K] lookup;
407 
408 	static if (ordered)
409 	{
410 		struct Item
411 		{
412 			K key;
413 			ValueVarType value;
414 
415 			static if (haveValues)
416 				alias /*ReturnType*/ returnValue = value;
417 			else
418 				@property ReturnType returnValue() const {}
419 
420 			static if (haveValues)
421 				alias /*OpIndexValueType*/ indexValue = value;
422 			else
423 			static if (ordered)
424 				alias /*OpIndexValueType*/ indexValue = key;
425 		}
426 		Item[] items;
427 
428 		enum bool canDup = is(typeof(lookup.dup)) && is(typeof(items.dup));
429 	}
430 	else
431 	{
432 		enum bool canDup = is(typeof(lookup.dup));
433 	}
434 
435 public:
436 
437 	// *** Lifetime ***
438 
439 	/// Postblit
440 	static if (needDupOnCopy)
441 	{
442 		static if (canDup)
443 			this(this)
444 			{
445 				lookup = lookup.dup;
446 				items = items.dup;
447 			}
448 		else
449 			@disable this(this);
450 	}
451 
452 	/// Create shallow copy
453 	static if (canDup)
454 	typeof(this) dup()
455 	{
456 		static if (needDupOnCopy)
457 			return this;
458 		else
459 		{
460 			typeof(this) copy;
461 			copy.lookup = lookup.dup;
462 			static if (ordered)
463 				copy.items = items.dup;
464 			return copy;
465 		}
466 	}
467 	
468 	// *** Conversions (from) ***
469 
470 	/// Construct from something else
471 	this(Input)(Input input)
472 	if (is(typeof(opAssign(input))))
473 	{
474 		opAssign(input);
475 	}
476 
477 	/// Null assignment
478 	ref typeof(this) opAssign(typeof(null) _)
479 	{
480 		clear();
481 		return this;
482 	}
483 
484 	/// Convert from an associative type
485 	ref typeof(this) opAssign(AA)(AA aa)
486 	if (haveValues
487 		&& !is(AA : typeof(this))
488 		&& is(typeof({ foreach (ref k, ref v; aa) add(k, v); })))
489 	{
490 		clear();
491 		foreach (ref k, ref v; aa)
492 			add(k, v);
493 		return this;
494 	}
495 
496 	/// Convert from an associative type of multiple items
497 	ref typeof(this) opAssign(AA)(AA aa)
498 	if (haveValues
499 		&& multi
500 		&& !is(AA : typeof(this))
501 		&& is(typeof({ foreach (ref k, ref vs; aa) foreach (ref v; vs) add(k, v); })))
502 	{
503 		clear();
504 		foreach (ref k, ref vs; aa)
505 			foreach (ref v; vs)
506 				add(k, v);
507 		return this;
508 	}
509 
510 	/// Convert from a range of tuples
511 	ref typeof(this) opAssign(R)(R input)
512 	if (haveValues
513 		&& is(typeof({ foreach (ref pair; input) add(pair[0], pair[1]); }))
514 		&& !is(typeof({ foreach (ref k, ref v; input) add(k, v); }))
515 		&& is(typeof(input.front.length))
516 		&& input.front.length == 2)
517 	{
518 		clear();
519 		foreach (ref pair; input)
520 			add(pair[0], pair[1]);
521 		return this;
522 	}
523 
524 	/// Convert from a range of key/value pairs
525 	ref typeof(this) opAssign(R)(R input)
526 	if (haveValues
527 		&& is(typeof({ foreach (ref pair; input) add(pair.key, pair.value); }))
528 		&& !is(typeof({ foreach (ref k, ref v; input) add(k, v); })))
529 	{
530 		clear();
531 		foreach (ref pair; input)
532 			add(pair.key, pair.value);
533 		return this;
534 	}
535 
536 	/// Convert from a range of values
537 	ref typeof(this) opAssign(R)(R input)
538 	if (!haveValues
539 		&& !is(R : typeof(this))
540 		&& is(typeof({ foreach (ref v; input) add(v); })))
541 	{
542 		clear();
543 		foreach (ref v; input)
544 			add(v);
545 		return this;
546 	}
547 
548 	// *** Conversions (to) ***
549 
550 	/// Convert to bool (true if non-null)
551 	bool opCast(T)() const
552 	if (is(T == bool))
553 	{
554 		return lookup !is null;
555 	}
556 
557 	/// Convert to D associative array
558 	static if (!ordered)
559 	{
560 		const(LookupValue[K]) toAA() const
561 		{
562 			return lookup;
563 		}
564 
565 		static if (is(typeof(lookup.dup)))
566 		LookupValue[K] toAA()
567 		{
568 			return lookup.dup;
569 		}
570 
571 		deprecated alias items = toAA;
572 	}
573 
574 	// *** Query (basic) ***
575 
576 	/// True when there are no items.
577 	bool empty() pure const nothrow @nogc @trusted
578 	{
579 		static if (ordered)
580 			return items.length == 0; // optimization
581 		else
582 			return lookup.byKey.empty; // generic version
583 	}
584 
585 	/// Total number of items, including with duplicate keys.
586 	size_t length() pure const nothrow @nogc @trusted
587 	{
588 		static if (ordered)
589 			return items.length; // optimization
590 		else
591 		static if (!multi)
592 			return lookup.length; // optimization
593 		else // generic version
594 		{
595 			size_t result;
596 			foreach (ref v; lookup.byValue)
597 				result += SM.length(v);
598 			return result;
599 		}
600 	}
601 
602 	// *** Query (by key) ***
603 
604 	/// Check if item with this key has been added.
605 	/// When applicable, return a pointer to the last value added with this key.
606 	Select!(haveReturnType, inout(ReturnType)*, bool) opBinaryRight(string op : "in", _K)(auto ref _K key) inout
607 	if (is(typeof(key in lookup)))
608 	{
609 		enum missValue = select!haveReturnType(null, false);
610 
611 		auto p = key in lookup;
612 		if (!p)
613 			return missValue;
614 
615 		static if (haveReturnType)
616 			return &lookupToIndexValue((*p)[$-1]);
617 		else
618 			return true;
619 	}
620 
621 	// *** Query (by index) ***
622 
623 	/// Index access (for ordered collections).
624 	/// For maps, returns the key.
625 	static if (ordered)
626 	ref inout(K) at()(size_t i) inout
627 	{
628 		return items[i].key;
629 	}
630 
631 	/// ditto
632 	static if (ordered)
633 	auto ref inout(K) getAt()(size_t i, auto ref K defaultValue) inout
634 	{
635 		return i < items.length ? items[i].key : defaultValue;
636 	}
637 
638 	// *** Query (by key/index - DWIM) ***
639 
640 	/// Index operator.
641 	/// The key must exist. Indexing with a key which does not exist
642 	/// is an error.
643 	static if (haveIndexing)
644 	ref inout(IV) opIndex()(auto ref const IK k) inout
645 	{
646 		static if (haveValues)
647 			return lookupToIndexValue(lookup[k][$-1]);
648 		else
649 			return items[k].indexValue;
650 	}
651 
652 	/// Retrieve last value associated with key, or `defaultValue` if none.
653 	static if (haveIndexing)
654 	{
655 		static if (haveValues)
656 			auto ref IV get(this This, KK)(auto ref KK k, auto ref IV defaultValue)
657 			if (is(typeof(k in lookup)))
658 			{
659 				auto p = k in lookup;
660 				return p ? lookupToIndexValue((*p)[$-1]) : defaultValue;
661 			}
662 		else
663 			auto ref IV get(this This, KK)(auto ref KK k, auto ref IV defaultValue)
664 			if (is(typeof(items[k])))
665 			{
666 				return k < items.length ? items[k].returnValue : defaultValue;
667 			}
668 	}
669 
670 	// *** Query (ranges) ***
671 
672 	/// Return a range which iterates over key/value pairs.
673 	static if (haveValues)
674 	auto byKeyValue(this This)()
675 	{
676 		static if (ordered)
677 			return items;
678 		else
679 		{
680 			return lookup
681 				.byKeyValue
682 				.map!(pair =>
683 					pair
684 					.value
685 					.map!(value => KeyValuePair!(K, V)(pair.key, value))
686 				)
687 				.joiner;
688 		}
689 	}
690 
691 	/// ditto
692 	static if (haveValues)
693 	auto byPair(this This)()
694 	{
695 		return byKeyValue
696 			.map!(pair => tuple!("key", "value")(pair.key, pair.value));
697 	}
698 
699 	/// Return a range which iterates over all keys.
700 	/// Duplicate keys will occur several times in the range.
701 	auto byKey(this This)()
702 	{
703 		static if (ordered)
704 		{
705 			static ref getKey(MItem)(ref MItem item) { return item.key; }
706 			return items.map!getKey;
707 		}
708 		else
709 		{
710 			return lookup
711 				.byKeyValue
712 				.map!(pair =>
713 					pair.key.repeat(SM.length(pair.value))
714 				)
715 				.joiner;
716 		}
717 	}
718 
719 	/// Return a range which iterates over all values.
720 	static if (haveValues)
721 	auto byValue(this This)()
722 	{
723 		static if (ordered)
724 		{
725 			static ref getValue(MItem)(ref MItem item) { return item.value; }
726 			return items.map!getValue;
727 		}
728 		else
729 		{
730 			return lookup
731 				.byKeyValue
732 				.map!(pair =>
733 					pair
734 					.value
735 				)
736 				.joiner;
737 		}
738 	}
739 
740 	/// Returns all keys as an array.
741 	@property auto keys(this This)() { return byKey.array; }
742 
743 	/// Returns all values as an array.
744 	@property auto values(this This)() { return byValue.array; }
745 
746 	// *** Query (search by key) ***
747 
748 	static if (ordered)
749 	{
750 		/// Returns index of key `k`.
751 		sizediff_t indexOf()(auto ref const K k) const
752 		{
753 			auto p = k in lookup;
754 			return p ? (*p)[0] : -1;
755 		}
756 
757 		/// Returns all indices of key `k`.
758 		inout(size_t)[] indicesOf()(auto ref const K k) inout
759 		{
760 			auto p = k in lookup;
761 			return p ? (*p)[] : null;
762 		}
763 	}
764 
765 	/// Return the number of items with the given key.
766 	/// When multi==false, always returns 0 or 1.
767 	size_t count()(auto ref K k)
768 	{
769 		static if (ordered)
770 			return indicesOf(k).length;
771 		else
772 		{
773 			auto p = k in lookup;
774 			return p ? SM.length(*p) : 0;
775 		}
776 	}
777 
778 	/// Return a range with all values with the given key.
779 	/// If the key is not present, returns an empty range.
780 	static if (haveValues)
781 	auto byValueOf(this This)(auto ref K k)
782 	{
783 		static if (ordered)
784 			return indicesOf(k).map!(index => items[index].value);
785 		else
786 			return valuesOf(k);
787 	}
788 
789 	/// Return an array with all values with the given key.
790 	/// If the key is not present, returns an empty array.
791 	static if (haveValues)
792 	V[] valuesOf()(auto ref K k)
793 	{
794 		static if (ordered)
795 			return byValueOf(k).array;
796 		else
797 		{
798 			static if (multi)
799 				return lookup.get(k, null);
800 			else
801 			{
802 				auto p = k in lookup;
803 				return p ? (*p)[] : null;
804 			}
805 		}
806 	}
807 
808 	static if (haveValues)
809 	deprecated alias getAll = valuesOf;
810 
811 	// *** Iteration ***
812 
813 	// Note: When iterating over keys in an AA, you must choose
814 	// mutable OR ref, but not both. This is an important reason for
815 	// the complexity below.
816 
817 	private enum isParameterRef(size_t index, fun...) = (){
818 		foreach (keyStorageClass; __traits(getParameterStorageClasses, fun[0], index))
819 			if (keyStorageClass == "ref")
820 				return true;
821 		return false;
822 	}();
823 
824 	private int opApplyImpl(this This, Dg)(scope Dg dg)
825 	{
826 		enum single = arity!dg == 1;
827 
828 		int result = 0;
829 
830 		static if (ordered)
831 		{
832 			foreach (ref item; items)
833 			{
834 				static if (single)
835 					result = dg(item.indexValue);
836 				else
837 					result = dg(item.key, item.value);
838 				if (result)
839 					break;
840 			}
841 		}
842 		else
843 		{
844 			static if (single && haveValues)
845 			{
846 				// Dg accepts value only, so use whatever we want for the key iteration.
847 				alias LK = const(K);
848 				enum useRef = true;
849 			}
850 			else
851 			{
852 				// Dg accepts a key (and maybe a value), so use the Dg signature for iteration.
853 				alias LK = Parameters!Dg[0];
854 				enum useRef = isParameterRef!(0, Dg);
855 			}
856 			// LookupValue or const(LookupValue), depending on the constness of This
857 			alias LV = typeof(lookup.values[0]);
858 
859 			bool handle()(ref LK key, ref LV values)
860 			{
861 				static if (haveValues)
862 				{
863 					foreach (ref value; values)
864 					{
865 						static if (single)
866 							result = dg(value);
867 						else
868 							result = dg(key, value);
869 						if (result)
870 							return false;
871 					}
872 				}
873 				else
874 				{
875 					foreach (iteration; 0 .. SM.length(values))
876 					{
877 						static assert(single);
878 						result = dg(key);
879 						if (result)
880 							return false;
881 					}
882 				}
883 				return true;
884 			}
885 
886 			static if (useRef)
887 			{
888 				foreach (ref LK key, ref LV values; lookup)
889 					if (!handle(key, values))
890 						break;
891 			}
892 			else
893 			{
894 				foreach (LK key, ref LV values; lookup)
895 					if (!handle(key, values))
896 						break;
897 			}
898 		}
899 		return result;
900 	}
901 
902 	private alias KeyIterationType(bool isConst, bool byRef) = typeof(*(){
903 
904 		static if (isConst)
905 			const bool[K] aa;
906 		else
907 			bool[K] aa;
908 
909 		static if (byRef)
910 			foreach (ref k, v; aa)
911 				return &k;
912 		else
913 			foreach (k, v; aa)
914 				return &k;
915 
916 		assert(false);
917 	}());
918 
919 	private enum needRefOverload(bool isConst) =
920 		// Unfortunately this doesn't work: https://issues.dlang.org/show_bug.cgi?id=21683
921 		// !is(KeyIterationType!(isConst, false) == KeyIterationType!(isConst, true));
922 		!isCopyable!K;
923 
924 	private template needIter(bool isConst, bool byRef)
925 	{
926 		static if (!isCopyable!K)
927 			enum needIter = byRef;
928 		else
929 		static if (!byRef)
930 			enum needIter = true;
931 		else
932 			enum needIter = needRefOverload!isConst;
933 	}
934 
935 	static if (haveValues)
936 	{
937 		/// Iterate over values (maps).
938 		int opApply(scope int delegate(      ref V) dg)       { return opApplyImpl(dg); }
939 		int opApply(scope int delegate(const ref V) dg) const { return opApplyImpl(dg); } /// ditto
940 	}
941 	else
942 	{
943 		/// Iterate over keys (sets).
944 		static if (needIter!(false, false)) int opApply(scope int delegate(    KeyIterationType!(false, false)) dg)       { return opApplyImpl(dg); }
945 		static if (needIter!(true , false)) int opApply(scope int delegate(    KeyIterationType!(true , false)) dg) const { return opApplyImpl(dg); } /// ditto
946 		static if (needIter!(false, true )) int opApply(scope int delegate(ref KeyIterationType!(false, true )) dg)       { return opApplyImpl(dg); } /// ditto
947 		static if (needIter!(true , true )) int opApply(scope int delegate(ref KeyIterationType!(true , true )) dg) const { return opApplyImpl(dg); } /// ditto
948 	}
949 
950 	static if (haveValues)
951 	{
952 		/// Iterate over keys and values.
953 		static if (needIter!(false, false)) int opApply(scope int delegate(    KeyIterationType!(false, false),       ref V) dg)       { return opApplyImpl(dg); }
954 		static if (needIter!(true , false)) int opApply(scope int delegate(    KeyIterationType!(true , false), const ref V) dg) const { return opApplyImpl(dg); } /// ditto
955 		static if (needIter!(false, true )) int opApply(scope int delegate(ref KeyIterationType!(false, true ),       ref V) dg)       { return opApplyImpl(dg); } /// ditto
956 		static if (needIter!(true , true )) int opApply(scope int delegate(ref KeyIterationType!(true , true ), const ref V) dg) const { return opApplyImpl(dg); } /// ditto
957 	}
958 
959 	private struct ByRef(bool isConst)
960 	{
961 		static if (isConst)
962 			const(HashCollection)* c;
963 		else
964 			HashCollection* c;
965 
966 		static if (haveValues)
967 		{
968 			static if (isConst)
969 				int opApply(scope int delegate(ref KeyIterationType!(true , true ), const ref V) dg) const { return c.opApplyImpl(dg); }
970 			else
971 				int opApply(scope int delegate(ref KeyIterationType!(false, true ),       ref V) dg)       { return c.opApplyImpl(dg); }
972 		}
973 		else
974 		{
975 			static if (isConst)
976 				int opApply(scope int delegate(ref KeyIterationType!(true , true )) dg) const { return c.opApplyImpl(dg); }
977 			else
978 				int opApply(scope int delegate(ref KeyIterationType!(false, true )) dg)       { return c.opApplyImpl(dg); }
979 		}
980 	}
981 
982 	/// Returns an object that allows iterating over this collection with ref keys.
983 	/// Workaround for https://issues.dlang.org/show_bug.cgi?id=21683
984 	auto byRef()       return { return ByRef!false(&this); }
985 	auto byRef() const return { return ByRef!true (&this); } /// ditto
986 
987 	// *** Mutation (addition) ***
988 
989 	private enum AddMode
990 	{
991 		add,     /// Always add value
992 		replace, /// Replace all previous values
993 		require, /// Only add value if it did not exist before
994 		addNew,  /// Only add value if it did not exist before; call getValue in that case
995 	}
996 
997 	private auto addImpl(AddMode mode, AK, GV)(ref AK key, scope GV getValue)
998 	if (is(AK : K))
999 	{
1000 		static if (ordered)
1001 		{
1002 			size_t addedIndex;
1003 
1004 			static if (multi && mode == AddMode.add)
1005 			{
1006 				addedIndex = items.length;
1007 				lookup[key] ~= addedIndex;
1008 				items ~= Item(key, getValue());
1009 			}
1010 			else
1011 			{
1012 				lookup.updateVoid(key,
1013 					delegate LookupValue()
1014 					{
1015 						addedIndex = items.length;
1016 						auto item = Item(key, getValue());
1017 						items.length++;
1018 						move(item, items[$-1]);
1019 						return [addedIndex];
1020 					},
1021 					delegate void(ref LookupValue existingIndex)
1022 					{
1023 						addedIndex = existingIndex[0];
1024 						static if (mode != AddMode.require && mode != AddMode.addNew)
1025 						{
1026 							static if (multi)
1027 							{
1028 								static assert(mode == AddMode.replace);
1029 								existingIndex = existingIndex[0 .. 1];
1030 							}
1031 							items[addedIndex].value = getValue();
1032 						}
1033 					});
1034 			}
1035 
1036 			auto self = &this;
1037 			static struct Result
1038 			{
1039 				size_t orderIndex;
1040 				typeof(self) context;
1041 				@property ref auto returnValue() { return context.items[orderIndex].returnValue; }
1042 			}
1043 			return Result(addedIndex, self);
1044 		}
1045 		else // ordered
1046 		{
1047 			static if (haveValues)
1048 			{
1049 				static struct Result
1050 				{
1051 					ReturnType* ptr;
1052 					@property ref ReturnType returnValue() { return *ptr; }
1053 				}
1054 
1055 				static if (mode == AddMode.require || mode == AddMode.addNew)
1056 					return Result(&(lookup.require(key, [getValue()]))[0]);
1057 				else
1058 				static if (multi && mode == AddMode.add)
1059 					return Result(&(lookup[key] ~= getValue())[$-1]);
1060 				else
1061 					return Result(&(lookup[key] = [getValue()])[0]);
1062 			}
1063 			else
1064 			{
1065 				static if (multi)
1066 				{
1067 					static if (mode == AddMode.require)
1068 						lookup.require(key, 1);
1069 					else
1070 					static if (mode == AddMode.addNew)
1071 						lookup.require(key, progn(getValue(), 1));
1072 					else
1073 					static if (mode == AddMode.add)
1074 						lookup[key]++;
1075 					else
1076 						lookup[key] = 1;
1077 				}
1078 				else
1079 				{
1080 					static if (mode == AddMode.addNew)
1081 						lookup.require(key, progn(getValue(), LookupValue.init));
1082 					else
1083 						lookup[key] = LookupValue.init;
1084 				}
1085 				// This branch returns void, as there is no reasonable
1086 				// ref to an AA key that we can return here.
1087 				static struct Result { @property void returnValue(){} }
1088 				return Result();
1089 			}
1090 		}
1091 	}
1092 
1093 	/*private*/ template _addSetFunc(AddMode mode)
1094 	{
1095 		static if (haveValues)
1096 		{
1097 			ref ReturnType _addSetFunc(AK, AV)(auto ref AK key, ref AV value)
1098 			if (is(AK : K) && is(AV : V))
1099 			{
1100 				return addImpl!mode(key, () => value).returnValue;
1101 			}
1102 
1103 			ref ReturnType _addSetFunc(AK, AV)(auto ref AK key, AV value)
1104 			if (is(AK : K) && is(AV : V))
1105 			{
1106 				return addImpl!mode(key, () => move(value)).returnValue;
1107 			}
1108 		}
1109 		else
1110 		{
1111 			ref ReturnType _addSetFunc(AK)(auto ref AK key)
1112 			if (is(AK : K))
1113 			{
1114 				ValueVarType value; // void[0]
1115 				return addImpl!mode(key, () => value).returnValue;
1116 			}
1117 		}
1118 	}
1119 
1120 	/// Add an item.
1121 	alias add = _addSetFunc!(AddMode.add);
1122 
1123 	/// Ensure a key exists (with the given value).
1124 	/// When `multi==true`, replaces all previous entries with this key.
1125 	/// Otherwise, behaves identically to `add`.
1126 	alias set = _addSetFunc!(AddMode.replace);
1127 
1128 	/// Add `value` only if `key` is not present.
1129 	static if (haveValues)
1130 	ref V require()(auto ref K key, lazy V value = V.init)
1131 	{
1132 		return addImpl!(AddMode.require)(key, () => value).returnValue;
1133 	}
1134 
1135 	static if (ordered)
1136 	size_t requireIndex()(auto ref K key, lazy ValueVarType value = ValueVarType.init)
1137 	{
1138 		return addImpl!(AddMode.require)(key, () => value).orderIndex;
1139 	}
1140 
1141 	deprecated alias getOrAdd = require;
1142 
1143 	private alias UpdateFuncRT(U) = typeof({ U u = void; V v = void; return u(v); }());
1144 
1145 	/// If `key` is present, call `update` for every value;
1146 	/// otherwise, add new value with `create`.
1147 	static if (haveValues)
1148 	void update(C, U)(auto ref K key, scope C create, scope U update)
1149 	if (is(typeof(create()) : V) && (is(UpdateFuncRT!U : V) || is(UpdateFuncRT!U == void)))
1150 	{
1151 		static if (ordered)
1152 		{
1153 			lookup.updateVoid(key,
1154 				delegate LookupValue()
1155 				{
1156 					auto addedIndex = items.length;
1157 					items ~= Item(key, create());
1158 					return [addedIndex];
1159 				},
1160 				delegate void(ref LookupValue existingIndex)
1161 				{
1162 					foreach (i; existingIndex)
1163 						static if (is(UpdateFuncRT!U == void))
1164 							update(items[i].value);
1165 						else
1166 							items[i].value = update(items[i].value);
1167 				});
1168 		}
1169 		else // ordered
1170 		{
1171 			lookup.updateVoid(key,
1172 				delegate LookupValue ()
1173 				{
1174 					return [create()];
1175 				},
1176 				delegate void (ref LookupValue values)
1177 				{
1178 					foreach (ref value; values)
1179 						static if (is(UpdateFuncRT!U == void))
1180 							update(value);
1181 						else
1182 							value = update(value);
1183 				});
1184 		}
1185 	}
1186 
1187 	static if (haveValues)
1188 	{
1189 		bool addNew()(auto ref K key, lazy V value = V.init)
1190 		{
1191 			bool added = false;
1192 			// update(key,
1193 			// 	delegate V   (       ) { added = true ; return value; },
1194 			// 	delegate void(ref V v) { added = false;               },
1195 			// );
1196 			addImpl!(AddMode.addNew)(key, { added = true; return value; });
1197 			return added;
1198 		}
1199 	}
1200 	else
1201 	{
1202 		bool addNew()(auto ref K key)
1203 		{
1204 			bool added = false;
1205 			ValueVarType value; // void[0]
1206 			addImpl!(AddMode.addNew)(key, { added = true; return value; });
1207 			return added;
1208 		}
1209 	}
1210 
1211 	// *** Mutation (editing) ***
1212 
1213 	static if (haveIndexing)
1214 	{
1215 		static if (haveValues)
1216 		{
1217 			/// Same as `set(k, v)`.
1218 			ref IV opIndexAssign(AK, AV)(ref AV v, auto ref AK k)
1219 			if (is(AK : K) && is(AV : V))
1220 			{
1221 				return set(k, v);
1222 			}
1223 
1224 			ref IV opIndexAssign(AK, AV)(AV v, auto ref AK k)
1225 			if (is(AK : K) && is(AV : V))
1226 			{
1227 				return set(k, move(v));
1228 			} /// ditto
1229 
1230 			/// Perform cumulative operation with value
1231 			/// (initialized with `.init` if the key does not exist).
1232 			ref IV opIndexOpAssign(string op, AK, AV)(auto ref AV v, auto ref AK k)
1233 			if (is(AK : K) && is(AV : V))
1234 			{
1235 				auto pv = &require(k);
1236 				return mixin("(*pv) " ~ op ~ "= v");
1237 			}
1238 
1239 			/// Perform unary operation with value
1240 			/// (initialized with `.init` if the key does not exist).
1241 			ref IV opIndexUnary(string op, AK)(auto ref AK k)
1242 			if (is(AK : K))
1243 			{
1244 				auto pv = &require(k);
1245 				mixin("(*pv) " ~ op ~ ";");
1246 				return *pv;
1247 			}
1248 		}
1249 		else
1250 		{
1251 			private ref K editIndex(size_t index, scope void delegate(ref K) edit)
1252 			{
1253 				auto item = &items[index];
1254 				K oldKey = item.key;
1255 				auto pOldIndices = oldKey in lookup;
1256 				assert(pOldIndices);
1257 
1258 				edit(item.key);
1259 
1260 				// Add new value
1261 
1262 				lookup.updateVoid(item.key,
1263 					delegate LookupValue()
1264 					{
1265 						// New value did not exist.
1266 						if ((*pOldIndices).length == 1)
1267 						{
1268 							// Optimization - migrate the Indexes value
1269 							assert((*pOldIndices)[0] == index);
1270 							return *pOldIndices;
1271 						}
1272 						else
1273 							return [index];
1274 					},
1275 					delegate void(ref LookupValue existingIndex)
1276 					{
1277 						// Value(s) with the new key already existed
1278 						static if (multi)
1279 							existingIndex ~= index;
1280 						else
1281 							assert(false, "Collision after in-place edit of a non-multi ordered set element");
1282 					});
1283 
1284 				// Remove old value
1285 
1286 				if ((*pOldIndices).length == 1)
1287 					lookup.remove(oldKey);
1288 				else
1289 				static if (multi)
1290 					*pOldIndices = (*pOldIndices).remove!(i => i == index);
1291 				else
1292 					assert(false); // Should be unreachable (`if` above will always be true)
1293 
1294 				return item.key;
1295 			}
1296 
1297 			/// Allows writing to ordered sets by index.
1298 			/// The total number of elements never changes as a result
1299 			/// of such an operation - a consequence of which is that
1300 			/// if multi==false, changing the value to one that's
1301 			/// already in the set is an error.
1302 			ref IV opIndexAssign()(auto ref IV v, auto ref IK k)
1303 			{
1304 				static if (haveValues)
1305 					return set(k, v);
1306 				else
1307 					return editIndex(k, (ref IV e) { e = v; });
1308 			}
1309 
1310 			/// Perform cumulative operation with value at index.
1311 			ref IV opIndexOpAssign(string op)(auto ref VV v, auto ref IK k)
1312 			{
1313 				return editIndex(k, (ref IV e) { mixin("e " ~ op ~ "= v;"); });
1314 			}
1315 
1316 			/// Perform unary operation with value at index.
1317 			ref IV opIndexUnary(string op)(auto ref IK k)
1318 			{
1319 				return editIndex(k, (ref IV e) { mixin("e " ~ op ~ ";"); });
1320 			}
1321 		}
1322 	}
1323 
1324 	// *** Mutation (removal) ***
1325 
1326 	/// Removes all elements with the given key.
1327 	bool remove(AK)(auto ref AK key)
1328 	if (is(typeof(lookup.remove(key))))
1329 	{
1330 		static if (ordered)
1331 		{
1332 			auto p = key in lookup;
1333 			if (!p)
1334 				return false;
1335 
1336 			auto targets = *p;
1337 			foreach (target; targets)
1338 			{
1339 				items = items.remove!(SwapStrategy.stable)(target);
1340 				foreach (ref k, ref vs; lookup)
1341 					foreach (ref v; vs)
1342 						if (v > target)
1343 							v--;
1344 			}
1345 			auto success = lookup.remove(key);
1346 			assert(success);
1347 			return true;
1348 		}
1349 		else
1350 			return lookup.remove(key);
1351 	}
1352 
1353 	/// Removes all elements.
1354 	void clear()
1355 	{
1356 		lookup.clear();
1357 		static if (ordered)
1358 			items = null;
1359 	}
1360 }
1361 
1362 /// An associative array which retains the order in which elements were added.
1363 alias OrderedMap(K, V) = HashCollection!(K, V, true, false);
1364 
1365 debug(ae_unittest) unittest
1366 {
1367 	alias M = OrderedMap!(string, int);
1368 	M m;
1369 	m["a"] = 1;
1370 	m["b"] = 2;
1371 	m["c"] = 3;
1372 	assert(m.length == 3);
1373 	assert("a" in m);
1374 	assert("d" !in m);
1375 
1376 	assert( m.addNew("x", 1));
1377 	assert(!m.addNew("x", 2));
1378 	assert(m["x"] == 1);
1379 	assert( m.remove("x"));
1380 	assert(!m.remove("x"));
1381 
1382 	{
1383 		auto r = m.byKeyValue;
1384 		assert(!r.empty);
1385 		assert(r.front.key == "a");
1386 		r.popFront();
1387 		assert(!r.empty);
1388 		assert(r.front.key == "b");
1389 		r.popFront();
1390 		assert(!r.empty);
1391 		assert(r.front.key == "c");
1392 		r.popFront();
1393 		assert(r.empty);
1394 	}
1395 
1396 	assert(m.byKey.equal(["a", "b", "c"]));
1397 	assert(m.byValue.equal([1, 2, 3]));
1398 	assert(m.byKeyValue.map!(p => p.key).equal(m.byKey));
1399 	assert(m.byKeyValue.map!(p => p.value).equal(m.byValue));
1400 	assert(m.keys == ["a", "b", "c"]);
1401 	assert(m.values == [1, 2, 3]);
1402 
1403 	{
1404 		const(M)* c = &m;
1405 		assert(c.byKey.equal(["a", "b", "c"]));
1406 		assert(c.byValue.equal([1, 2, 3]));
1407 		assert(c.keys == ["a", "b", "c"]);
1408 		assert(c.values == [1, 2, 3]);
1409 	}
1410 
1411 	m.byValue.front = 5;
1412 	assert(m.byValue.equal([5, 2, 3]));
1413 
1414 	m.remove("a");
1415 	assert(m.length == 2);
1416 	m["x"] -= 1;
1417 	assert(m["x"] == -1);
1418 	++m["y"];
1419 	assert(m["y"] == 1);
1420 	auto cm = cast(const)m.dup;
1421 	foreach (k, v; cm)
1422 		if (k == "x")
1423 			assert(v == -1);
1424 }
1425 
1426 debug(ae_unittest) unittest
1427 {
1428 	OrderedMap!(string, int) m;
1429 	m["a"] = 1;
1430 	m["b"] = 2;
1431 	m.remove("a");
1432 	assert(m["b"] == 2);
1433 }
1434 
1435 debug(ae_unittest) unittest
1436 {
1437 	OrderedMap!(string, int) m;
1438 	m["a"] = 1;
1439 	auto m2 = m;
1440 	m2.remove("a");
1441 	m2["b"] = 2;
1442 	assert(m["a"] == 1);
1443 }
1444 
1445 debug(ae_unittest) unittest
1446 {
1447 	OrderedMap!(string, int) m;
1448 	m["a"] = 1;
1449 	m["b"] = 2;
1450 	auto m2 = m;
1451 	m.remove("a");
1452 	assert(m2["a"] == 1);
1453 }
1454 
1455 debug(ae_unittest) unittest
1456 {
1457 	class C {}
1458 	const OrderedMap!(string, C) m;
1459 	cast(void)m.byKeyValue;
1460 }
1461 
1462 debug(ae_unittest) unittest
1463 {
1464 	OrderedMap!(int, int) m;
1465 	m.update(10,
1466 		{ return 20; },
1467 		(ref int k) { k++; return 30; },
1468 	);
1469 	assert(m.length == 1 && m[10] == 20);
1470 	m.update(10,
1471 		{ return 40; },
1472 		(ref int k) { k++; return 50; },
1473 	);
1474 	assert(m.length == 1 && m[10] == 50);
1475 }
1476 
1477 // https://issues.dlang.org/show_bug.cgi?id=18606
1478 debug(ae_unittest) unittest
1479 {
1480 	struct S
1481 	{
1482 		struct T
1483 		{
1484 			int foo;
1485 			int[] bar;
1486 		}
1487 
1488 		OrderedMap!(int, T) m;
1489 	}
1490 }
1491 
1492 debug(ae_unittest) unittest
1493 {
1494 	OrderedMap!(string, int) m;
1495 	static assert(is(typeof(m.keys)));
1496 	static assert(is(typeof(m.values)));
1497 }
1498 
1499 debug(ae_unittest) unittest
1500 {
1501 	OrderedMap!(string, int) m;
1502 	foreach (k, v; m)
1503 		k = k ~ k;
1504 }
1505 
1506 debug(ae_unittest) unittest
1507 {
1508 	struct S { @disable this(); }
1509 	const OrderedMap!(string, S) m;
1510 }
1511 
1512 debug(ae_unittest) unittest
1513 {
1514 	class C {}
1515 	OrderedMap!(string, C) m;
1516 	m.get(null, new C);
1517 }
1518 
1519 /// Like assocArray
1520 auto orderedMap(R)(R input)
1521 if (is(typeof(input.front.length) : size_t) && input.front.length == 2)
1522 {
1523 	alias K = typeof(input.front[0]);
1524 	alias V = typeof(input.front[1]);
1525 	return OrderedMap!(K, V)(input);
1526 }
1527 
1528 auto orderedMap(R)(R input)
1529 if (is(typeof(input.front.key)) && is(typeof(input.front.value)) && !is(typeof(input.front.length)))
1530 {
1531 	alias K = typeof(input.front.key);
1532 	alias V = typeof(input.front.value);
1533 	return OrderedMap!(K, V)(input);
1534 } /// ditto
1535 
1536 debug(ae_unittest) unittest
1537 {
1538 	auto map = 3.iota.map!(n => tuple(n, n + 1)).orderedMap;
1539 	assert(map.length == 3 && map[1] == 2);
1540 }
1541 
1542 debug(ae_unittest) unittest
1543 {
1544 	OrderedMap!(string, int) m;
1545 	m = m.byKeyValue.orderedMap;
1546 	m = m.byPair.orderedMap;
1547 }
1548 
1549 debug(ae_unittest) unittest
1550 {
1551 	OrderedMap!(string, int) m;
1552 	const(char)[] s;
1553 	m.get(s, 0);
1554 }
1555 
1556 debug(ae_unittest) unittest
1557 {
1558 	OrderedMap!(string, OrderedMap!(string, string[][])) m;
1559 
1560 	m.require("");
1561 }
1562 
1563 debug(ae_unittest) unittest
1564 {
1565 	struct Q { void* p; }
1566 	struct S { OrderedMap!(string, Q) m; }
1567 	OrderedMap!(string, S) objects;
1568 
1569 	objects[""] = S();
1570 }
1571 
1572 // ***************************************************************************
1573 
1574 /// Helper/wrapper for void[0][T]
1575 alias HashSet(T) = HashCollection!(T, void, false, false);
1576 
1577 debug(ae_unittest) unittest
1578 {
1579 	HashSet!int s;
1580 	assert(!s);
1581 	assert(s.length == 0);
1582 	assert(!(1 in s));
1583 	assert(1 !in s);
1584 	s.add(1);
1585 	assert(1 in s);
1586 	assert(s.length == 1);
1587 	foreach (k; s)
1588 		assert(k == 1);
1589 	foreach (ref k; s.byRef)
1590 		assert(k == 1);
1591 	s.remove(1);
1592 	assert(s.length == 0);
1593 
1594 	s.add(1);
1595 	auto t = s.dup;
1596 	s.add(2);
1597 	assert(t.length==1);
1598 	t.remove(1);
1599 	assert(t.length==0);
1600 
1601 	assert( t.addNew(5));
1602 	assert(!t.addNew(5));
1603 	assert(5 in t);
1604 	assert( t.remove(5));
1605 	assert(!t.remove(5));
1606 }
1607 
1608 debug(ae_unittest) unittest
1609 {
1610 	struct S { int[int] aa; }
1611 	HashSet!S set;
1612 	S s;
1613 	set.add(s);
1614 	assert(s in set);
1615 }
1616 
1617 /// Construct a set from the range `r`.
1618 auto toSet(R)(R r)
1619 {
1620 	alias E = ElementType!R;
1621 	return HashSet!E(r);
1622 }
1623 
1624 debug(ae_unittest) unittest
1625 {
1626 	auto set = [1, 2, 3].toSet();
1627 	assert(2 in set);
1628 	assert(4 !in set);
1629 }
1630 
1631 debug(ae_unittest) unittest
1632 {
1633 	HashSet!int m;
1634 	const int i;
1635 	m.remove(i);
1636 }
1637 
1638 debug(ae_unittest) unittest
1639 {
1640 	HashSet!Object m;
1641 	Object o;
1642 	m.remove(o);
1643 }
1644 
1645 debug(ae_unittest) unittest
1646 {
1647 	struct S
1648 	{
1649 		@disable this(this);
1650 	}
1651 
1652 	HashSet!S set;
1653 }
1654 
1655 // ***************************************************************************
1656 
1657 /// An ordered set of `T`, which retains
1658 /// the order in which elements are added.
1659 alias OrderedSet(T) = HashCollection!(T, void, true, false);
1660 
1661 debug(ae_unittest) unittest
1662 {
1663 	OrderedSet!int set;
1664 
1665 	assert(1 !in set);
1666 	set.add(1);
1667 	assert(1 in set);
1668 	set.remove(1);
1669 	assert(1 !in set);
1670 
1671 	set.add(1);
1672 	set.clear();
1673 	assert(1 !in set);
1674 
1675 	set = set.init;
1676 	assert(!set);
1677 	set.add(1);
1678 	assert(!!set);
1679 
1680 	assert(set[0] == 1);
1681 	set[0] = 2;
1682 	assert(set[0] == 2);
1683 	assert(1 !in set);
1684 	assert(2 in set);
1685 
1686 	assert(set.length == 1);
1687 	set.remove(2);
1688 	assert(set.length == 0);
1689 
1690 	set.add(1);
1691 	auto set2 = set;
1692 	set.remove(1);
1693 	set.add(2);
1694 	assert(1 !in set && 2 in set);
1695 	assert(1 in set2 && 2 !in set2);
1696 
1697 	foreach (v; set)
1698 		assert(v == 2);
1699 
1700 	assert(set.length == 1);
1701 	auto index1 = set.requireIndex(1);
1702 	assert(set[index1] == 1);
1703 	assert(set.length == 2);
1704 	auto index2 = set.requireIndex(2);
1705 	assert(set[index2] == 2);
1706 	assert(set.length == 2);
1707 
1708 	assert(set[set.indexOf(2)] == 2);
1709 
1710 	void f(ref const OrderedSet!int set)
1711 	{
1712 		const size_t i = 0;
1713 		assert(set[i] == 2);
1714 	}
1715 
1716 	assert(set.at(set.indexOf(2)) == 2);
1717 	assert(set.getAt(set.indexOf(2), 99) == 2);
1718 	assert(set.getAt(99, 99) == 99);
1719 }
1720 
1721 /// Construct an ordered set from the range `r`.
1722 auto orderedSet(R)(R r)
1723 {
1724 	alias E = ElementType!R;
1725 	return OrderedSet!E(r);
1726 }
1727 
1728 // ***************************************************************************
1729 
1730 /// An object which acts mostly as an associative array,
1731 /// with the added property of being able to hold keys with
1732 /// multiple values. These are only exposed explicitly and
1733 /// through iteration
1734 alias MultiAA(K, V) = HashCollection!(K, V, false, true);
1735 
1736 debug(ae_unittest) unittest
1737 {
1738 	alias MASS = MultiAA!(string, int);
1739 	MASS aa;
1740 	aa.add("foo", 42);
1741 	assert(aa["foo"] == 42);
1742 	assert(aa.valuesOf("foo") == [42]);
1743 	assert(aa.byPair.front.key == "foo");
1744 
1745 	auto aa2 = MASS([tuple("foo", 42)]);
1746 	aa2 = ["a":1,"b":2];
1747 
1748 	const int i;
1749 	aa["a"] = i;
1750 }
1751 
1752 debug(ae_unittest) unittest
1753 {
1754 	MultiAA!(int, int) m;
1755 	int[][int] a;
1756 	m = a;
1757 }
1758 
1759 // ***************************************************************************
1760 
1761 /// Given an AA literal, construct an AA-like object which can be built
1762 /// at compile-time and queried at run-time.
1763 /// The AA literal is unrolled into code.
1764 auto staticAA(alias aa)()
1765 {
1766 	alias K = typeof(aa.keys[0]);
1767 	alias V = typeof(aa.values[0]);
1768 	ref auto value(alias v)() // Work around "... is already defined in another scope in ..."
1769 	{
1770 		static immutable iv = v;
1771 		return iv;
1772 	}
1773 	struct StaticMap
1774 	{
1775 		static immutable K[] keys = aa.keys;
1776 		static immutable V[] values = aa.values;
1777 
1778 		ref immutable(V) opIndex(K key) const
1779 		{
1780 			final switch (key)
1781 			{
1782 				static foreach (i, aaKey; aa.keys)
1783 				{
1784 					case aaKey:
1785 						return value!(aa.values[i]);
1786 				}
1787 			}
1788 		}
1789 
1790 		bool opBinaryRight(string op : "in")(K key) inout
1791 		{
1792 			switch (key)
1793 			{
1794 				static foreach (aaKey; aa.keys)
1795 				{
1796 					case aaKey:
1797 						return true;
1798 				}
1799 				default:
1800 					return false;
1801 			}
1802 		}
1803 
1804 		int opApply(scope int delegate(ref immutable K, ref immutable V) dg) const
1805 		{
1806 			static foreach (i, aaKey; aa.keys)
1807 			{{
1808 				int ret = dg(value!aaKey, value!(aa.values[i]));
1809 				if (ret)
1810 					return ret;
1811 			}}
1812 			return 0;
1813 		}
1814 	}
1815 	return StaticMap();
1816 }
1817 
1818 debug(ae_unittest) unittest
1819 {
1820 	static immutable aa = staticAA!([
1821 		"foo" : 1,
1822 		"bar" : 2,
1823 	]);
1824 
1825 	assert(aa["foo"] == 1);
1826 
1827 	assert("foo" in aa);
1828 	assert("baz" !in aa);
1829 
1830 	assert(aa.keys == ["foo", "bar"]);
1831 	assert(aa.values == [1, 2]);
1832 
1833 	foreach (key, value; aa)
1834 		assert((key == "foo" && value == 1) || (key == "bar" && value == 2));
1835 }