The OpenD Programming Language

1 // Written in the D programming language.
2 /**
3 This is a submodule of $(MREF std, algorithm).
4 It contains generic algorithms that implement set operations.
5 
6 The functions $(LREF multiwayMerge), $(LREF multiwayUnion), $(LREF setDifference),
7 $(LREF setIntersection), $(LREF setSymmetricDifference) expect a range of sorted
8 ranges as input.
9 
10 All algorithms are generalized to accept as input not only sets but also
11 $(HTTP https://en.wikipedia.org/wiki/Multiset, multisets). Each algorithm
12 documents behaviour in the presence of duplicated inputs.
13 
14 $(SCRIPT inhibitQuickIndex = 1;)
15 $(BOOKTABLE Cheat Sheet,
16 $(TR $(TH Function Name) $(TH Description))
17 $(T2 cartesianProduct,
18         Computes Cartesian product of two ranges.)
19 $(T2 largestPartialIntersection,
20         Copies out the values that occur most frequently in a range of ranges.)
21 $(T2 largestPartialIntersectionWeighted,
22         Copies out the values that occur most frequently (multiplied by
23         per-value weights) in a range of ranges.)
24 $(T2 multiwayMerge,
25         Merges a range of sorted ranges.)
26 $(T2 multiwayUnion,
27         Computes the union of a range of sorted ranges.)
28 $(T2 setDifference,
29         Lazily computes the set difference of two or more sorted ranges.)
30 $(T2 setIntersection,
31         Lazily computes the intersection of two or more sorted ranges.)
32 $(T2 setSymmetricDifference,
33         Lazily computes the symmetric set difference of two or more sorted
34         ranges.)
35 )
36 
37 Copyright: Andrei Alexandrescu 2008-.
38 
39 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
40 
41 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
42 
43 Source: $(PHOBOSSRC std/algorithm/setops.d)
44 
45 Macros:
46 T2=$(TR $(TDNW $(LREF $1)) $(TD $+))
47  */
48 module std.algorithm.setops;
49 
50 import std.range.primitives;
51 
52 import std.functional : unaryFun, binaryFun;
53 import std.traits;
54 import std.meta : AliasSeq, staticMap, allSatisfy, anySatisfy;
55 
56 import std.algorithm.sorting : Merge;
57 import std.typecons : No;
58 
59 // cartesianProduct
60 /**
61 Lazily computes the Cartesian product of two or more ranges. The product is a
62 range of tuples of elements from each respective range.
63 
64 The conditions for the two-range case are as follows:
65 
66 If both ranges are finite, then one must be (at least) a
67 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) and the
68 other an $(REF_ALTTEXT input range, isInputRange, std,range,primitives).
69 
70 If one range is infinite and the other finite, then the finite range must
71 be a forward range, and the infinite range can be an input range.
72 
73 If both ranges are infinite, then both must be forward ranges.
74 
75 When there are more than two ranges, the above conditions apply to each
76 adjacent pair of ranges.
77 
78 Params:
79     range1 = The first range
80     range2 = The second range
81     ranges = Two or more non-infinite forward ranges
82     otherRanges = Zero or more non-infinite forward ranges
83 
84 Returns:
85     A forward range of $(REF Tuple, std,typecons) representing elements of the
86     cartesian product of the given ranges.
87 */
88 auto cartesianProduct(R1, R2)(R1 range1, R2 range2)
89 if (!allSatisfy!(isForwardRange, R1, R2) ||
90     anySatisfy!(isInfinite, R1, R2))
91 {
92     import std.algorithm.iteration : map, joiner;
93 
94     static if (isInfinite!R1 && isInfinite!R2)
95     {
96         static if (isForwardRange!R1 && isForwardRange!R2)
97         {
98             import std.range : zip, repeat, take, chain, sequence;
99 
100             // This algorithm traverses the cartesian product by alternately
101             // covering the right and bottom edges of an increasing square area
102             // over the infinite table of combinations. This schedule allows us
103             // to require only forward ranges.
104             return zip(sequence!"n"(cast(size_t) 0), range1.save, range2.save,
105                        repeat(range1), repeat(range2))
106                 .map!(function(a) => chain(
107                     zip(repeat(a[1]), take(a[4].save, a[0])),
108                     zip(take(a[3].save, a[0]+1), repeat(a[2]))
109                 ))()
110                 .joiner();
111         }
112         else static assert(0, "cartesianProduct of infinite ranges requires "~
113                               "forward ranges");
114     }
115     else static if (isInputRange!R1 && isForwardRange!R2 && !isInfinite!R2)
116     {
117         import std.range : zip, repeat;
118         return joiner(map!((ElementType!R1 a) => zip(repeat(a), range2.save))
119                           (range1));
120     }
121     else static if (isInputRange!R2 && isForwardRange!R1 && !isInfinite!R1)
122     {
123         import std.range : zip, repeat;
124         return joiner(map!((ElementType!R2 a) => zip(range1.save, repeat(a)))
125                           (range2));
126     }
127     else static assert(0, "cartesianProduct involving finite ranges must "~
128                           "have at least one finite forward range");
129 }
130 
131 ///
132 @safe unittest
133 {
134     import std.algorithm.searching : canFind;
135     import std.range;
136     import std.typecons : tuple;
137 
138     auto N = sequence!"n"(0);         // the range of natural numbers
139     auto N2 = cartesianProduct(N, N); // the range of all pairs of natural numbers
140 
141     // Various arbitrary number pairs can be found in the range in finite time.
142     assert(canFind(N2, tuple(0, 0)));
143     assert(canFind(N2, tuple(123, 321)));
144     assert(canFind(N2, tuple(11, 35)));
145     assert(canFind(N2, tuple(279, 172)));
146 }
147 
148 ///
149 @safe unittest
150 {
151     import std.algorithm.searching : canFind;
152     import std.typecons : tuple;
153 
154     auto B = [ 1, 2, 3 ];
155     auto C = [ 4, 5, 6 ];
156     auto BC = cartesianProduct(B, C);
157 
158     foreach (n; [[1, 4], [2, 4], [3, 4], [1, 5], [2, 5], [3, 5], [1, 6],
159                  [2, 6], [3, 6]])
160     {
161         assert(canFind(BC, tuple(n[0], n[1])));
162     }
163 }
164 
165 @safe unittest
166 {
167     // Test cartesian product of two infinite ranges
168     import std.algorithm.searching : canFind;
169     import std.range;
170     import std.typecons : tuple;
171 
172     auto Even = sequence!"2*n"(0);
173     auto Odd = sequence!"2*n+1"(0);
174     auto EvenOdd = cartesianProduct(Even, Odd);
175 
176     foreach (pair; [[0, 1], [2, 1], [0, 3], [2, 3], [4, 1], [4, 3], [0, 5],
177                     [2, 5], [4, 5], [6, 1], [6, 3], [6, 5]])
178     {
179         assert(canFind(EvenOdd, tuple(pair[0], pair[1])));
180     }
181 
182     // This should terminate in finite time
183     assert(canFind(EvenOdd, tuple(124, 73)));
184     assert(canFind(EvenOdd, tuple(0, 97)));
185     assert(canFind(EvenOdd, tuple(42, 1)));
186 }
187 
188 @safe unittest
189 {
190     // Test cartesian product of an infinite input range and a finite forward
191     // range.
192     import std.algorithm.searching : canFind;
193     import std.range;
194     import std.typecons : tuple;
195 
196     auto N = sequence!"n"(0);
197     auto M = [100, 200, 300];
198     auto NM = cartesianProduct(N,M);
199 
200     foreach (pair; [[0, 100], [0, 200], [0, 300], [1, 100], [1, 200], [1, 300],
201                     [2, 100], [2, 200], [2, 300], [3, 100], [3, 200],
202                     [3, 300]])
203     {
204         assert(canFind(NM, tuple(pair[0], pair[1])));
205     }
206 
207     // We can't solve the halting problem, so we can only check a finite
208     // initial segment here.
209     assert(!canFind(NM.take(100), tuple(100, 0)));
210     assert(!canFind(NM.take(100), tuple(1, 1)));
211     assert(!canFind(NM.take(100), tuple(100, 200)));
212 
213     auto MN = cartesianProduct(M,N);
214     foreach (pair; [[100, 0], [200, 0], [300, 0], [100, 1], [200, 1], [300, 1],
215                     [100, 2], [200, 2], [300, 2], [100, 3], [200, 3],
216                     [300, 3]])
217     {
218         assert(canFind(MN, tuple(pair[0], pair[1])));
219     }
220 
221     // We can't solve the halting problem, so we can only check a finite
222     // initial segment here.
223     assert(!canFind(MN.take(100), tuple(0, 100)));
224     assert(!canFind(MN.take(100), tuple(0, 1)));
225     assert(!canFind(MN.take(100), tuple(100, 200)));
226 }
227 
228 @safe unittest
229 {
230     import std.algorithm.searching : canFind;
231     import std.typecons : tuple;
232 
233     // Test cartesian product of two finite ranges.
234     auto X = [1, 2, 3];
235     auto Y = [4, 5, 6];
236     auto XY = cartesianProduct(X, Y);
237     auto Expected = [[1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4],
238                      [3, 5], [3, 6]];
239 
240     // Verify Expected ⊆ XY
241     foreach (pair; Expected)
242     {
243         assert(canFind(XY, tuple(pair[0], pair[1])));
244     }
245 
246     // Verify XY ⊆ Expected
247     foreach (pair; XY)
248     {
249         assert(canFind(Expected, [pair[0], pair[1]]));
250     }
251 
252     // And therefore, by set comprehension, XY == Expected
253 }
254 
255 @safe unittest
256 {
257     import std.algorithm.comparison : equal;
258     import std.algorithm.iteration : map;
259     import std.algorithm.searching : canFind;
260     import std.typecons : tuple;
261 
262     import std.range;
263     auto N = sequence!"n"(0);
264 
265     // To force the template to fall to the second case, we wrap N in a struct
266     // that doesn't allow bidirectional access.
267     struct FwdRangeWrapper(R)
268     {
269         R impl;
270 
271         // Input range API
272         @property auto front() { return impl.front; }
273         void popFront() { impl.popFront(); }
274         static if (isInfinite!R)
275             enum empty = false;
276         else
277             @property bool empty() { return impl.empty; }
278 
279         // Forward range API
280         @property auto save() { return typeof(this)(impl.save); }
281     }
282     auto fwdWrap(R)(R range) { return FwdRangeWrapper!R(range); }
283 
284     // General test: two infinite bidirectional ranges
285     auto N2 = cartesianProduct(N, N);
286 
287     assert(canFind(N2, tuple(0, 0)));
288     assert(canFind(N2, tuple(123, 321)));
289     assert(canFind(N2, tuple(11, 35)));
290     assert(canFind(N2, tuple(279, 172)));
291 
292     // Test first case: forward range with bidirectional range
293     auto fwdN = fwdWrap(N);
294     auto N2_a = cartesianProduct(fwdN, N);
295 
296     assert(canFind(N2_a, tuple(0, 0)));
297     assert(canFind(N2_a, tuple(123, 321)));
298     assert(canFind(N2_a, tuple(11, 35)));
299     assert(canFind(N2_a, tuple(279, 172)));
300 
301     // Test second case: bidirectional range with forward range
302     auto N2_b = cartesianProduct(N, fwdN);
303 
304     assert(canFind(N2_b, tuple(0, 0)));
305     assert(canFind(N2_b, tuple(123, 321)));
306     assert(canFind(N2_b, tuple(11, 35)));
307     assert(canFind(N2_b, tuple(279, 172)));
308 
309     // Test third case: finite forward range with (infinite) input range
310     static struct InpRangeWrapper(R)
311     {
312         R impl;
313 
314         // Input range API
315         @property auto front() { return impl.front; }
316         void popFront() { impl.popFront(); }
317         static if (isInfinite!R)
318             enum empty = false;
319         else
320             @property bool empty() { return impl.empty; }
321     }
322     auto inpWrap(R)(R r) { return InpRangeWrapper!R(r); }
323 
324     auto inpN = inpWrap(N);
325     auto B = [ 1, 2, 3 ];
326     auto fwdB = fwdWrap(B);
327     auto BN = cartesianProduct(fwdB, inpN);
328 
329     assert(equal(map!"[a[0],a[1]]"(BN.take(10)), [[1, 0], [2, 0], [3, 0],
330                  [1, 1], [2, 1], [3, 1], [1, 2], [2, 2], [3, 2], [1, 3]]));
331 
332     // Test fourth case: (infinite) input range with finite forward range
333     auto NB = cartesianProduct(inpN, fwdB);
334 
335     assert(equal(map!"[a[0],a[1]]"(NB.take(10)), [[0, 1], [0, 2], [0, 3],
336                  [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1]]));
337 
338     // General finite range case
339     auto C = [ 4, 5, 6 ];
340     auto BC = cartesianProduct(B, C);
341 
342     foreach (n; [[1, 4], [2, 4], [3, 4], [1, 5], [2, 5], [3, 5], [1, 6],
343                  [2, 6], [3, 6]])
344     {
345         assert(canFind(BC, tuple(n[0], n[1])));
346     }
347 }
348 
349 // https://issues.dlang.org/show_bug.cgi?id=13091
350 pure nothrow @safe @nogc unittest
351 {
352     int[1] a = [1];
353     foreach (t; cartesianProduct(a[], a[])) {}
354 }
355 
356 /// ditto
357 auto cartesianProduct(RR...)(RR ranges)
358 if (ranges.length >= 2 &&
359     allSatisfy!(isForwardRange, RR) &&
360     !anySatisfy!(isInfinite, RR))
361 {
362     // This overload uses a much less template-heavy implementation when
363     // all ranges are finite forward ranges, which is the most common use
364     // case, so that we don't run out of resources too quickly.
365     //
366     // For infinite ranges or non-forward ranges, we fall back to the old
367     // implementation which expands an exponential number of templates.
368     import std.typecons : tuple;
369 
370     static struct Result
371     {
372         RR ranges;
373         RR current;
374         bool empty = true;
375 
376         this(RR _ranges)
377         {
378             ranges = _ranges;
379             empty = false;
380             foreach (i, r; ranges)
381             {
382                 current[i] = r.save;
383                 if (current[i].empty)
384                     empty = true;
385             }
386         }
387         @property auto front()
388         {
389             import std.algorithm.internal : algoFormat;
390             import std.range : iota;
391             return mixin(algoFormat("tuple(%(current[%d].front%|,%))",
392                                     iota(0, current.length)));
393         }
394         void popFront() scope
395         {
396             foreach_reverse (i, ref r; current)
397             {
398                 r.popFront();
399                 if (!r.empty) break;
400 
401                 static if (i == 0)
402                     empty = true;
403                 else
404                     r = ranges[i].save; // rollover
405             }
406         }
407         @property Result save() return scope
408         {
409             Result copy = this;
410             foreach (i, r; ranges)
411             {
412                 copy.ranges[i] = ranges[i].save;
413                 copy.current[i] = current[i].save;
414             }
415             return copy;
416         }
417     }
418     static assert(isForwardRange!Result, Result.stringof ~ " must be a forward"
419             ~ " range");
420 
421     return Result(ranges);
422 }
423 
424 // cartesian product of empty ranges should be empty
425 // https://issues.dlang.org/show_bug.cgi?id=10693
426 @safe unittest
427 {
428     int[] a, b, c, d, e;
429     auto cprod = cartesianProduct(a,b,c,d,e);
430     assert(cprod.empty);
431     foreach (_; cprod) {} // should not crash
432 
433     // Test case where only one of the ranges is empty: the result should still
434     // be empty.
435     int[] p=[1], q=[];
436     auto cprod2 = cartesianProduct(p,p,p,q,p);
437     assert(cprod2.empty);
438     foreach (_; cprod2) {} // should not crash
439 }
440 
441 @safe unittest
442 {
443     // .init value of cartesianProduct should be empty
444     auto cprod = cartesianProduct([0,0], [1,1], [2,2]);
445     assert(!cprod.empty);
446     assert(cprod.init.empty);
447 }
448 
449 // https://issues.dlang.org/show_bug.cgi?id=13393
450 @safe unittest
451 {
452     assert(!cartesianProduct([0],[0],[0]).save.empty);
453 }
454 
455 /// ditto
456 auto cartesianProduct(R1, R2, RR...)(R1 range1, R2 range2, RR otherRanges)
457 if (!allSatisfy!(isForwardRange, R1, R2, RR) ||
458     anySatisfy!(isInfinite, R1, R2, RR))
459 {
460     /* We implement the n-ary cartesian product by recursively invoking the
461      * binary cartesian product. To make the resulting range nicer, we denest
462      * one level of tuples so that a ternary cartesian product, for example,
463      * returns 3-element tuples instead of nested 2-element tuples.
464      */
465     import std.algorithm.internal : algoFormat;
466     import std.algorithm.iteration : map;
467     import std.range : iota;
468 
469     enum string denest = algoFormat("tuple(a[0], %(a[1][%d]%|,%))",
470                                 iota(0, otherRanges.length+1));
471     return map!denest(
472         cartesianProduct(range1, cartesianProduct(range2, otherRanges))
473     );
474 }
475 
476 @safe unittest
477 {
478     import std.algorithm.searching : canFind;
479     import std.range;
480     import std.typecons : tuple, Tuple;
481 
482     auto N = sequence!"n"(0);
483     auto N3 = cartesianProduct(N, N, N);
484 
485     // Check that tuples are properly denested
486     assert(is(ElementType!(typeof(N3)) == Tuple!(size_t,size_t,size_t)));
487 
488     assert(canFind(N3, tuple(0, 27, 7)));
489     assert(canFind(N3, tuple(50, 23, 11)));
490     assert(canFind(N3, tuple(9, 3, 0)));
491 }
492 
493 @safe unittest
494 {
495     import std.algorithm.searching : canFind;
496     import std.range;
497     import std.typecons : tuple, Tuple;
498 
499     auto N = sequence!"n"(0);
500     auto N4 = cartesianProduct(N, N, N, N);
501 
502     // Check that tuples are properly denested
503     assert(is(ElementType!(typeof(N4)) == Tuple!(size_t,size_t,size_t,size_t)));
504 
505     assert(canFind(N4, tuple(1, 2, 3, 4)));
506     assert(canFind(N4, tuple(4, 3, 2, 1)));
507     assert(canFind(N4, tuple(10, 3, 1, 2)));
508 }
509 
510 // https://issues.dlang.org/show_bug.cgi?id=9878
511 ///
512 @safe unittest
513 {
514     import std.algorithm.comparison : equal;
515     import std.typecons : tuple;
516 
517     auto A = [ 1, 2, 3 ];
518     auto B = [ 'a', 'b', 'c' ];
519     auto C = [ "x", "y", "z" ];
520     auto ABC = cartesianProduct(A, B, C);
521 
522     assert(ABC.equal([
523         tuple(1, 'a', "x"), tuple(1, 'a', "y"), tuple(1, 'a', "z"),
524         tuple(1, 'b', "x"), tuple(1, 'b', "y"), tuple(1, 'b', "z"),
525         tuple(1, 'c', "x"), tuple(1, 'c', "y"), tuple(1, 'c', "z"),
526         tuple(2, 'a', "x"), tuple(2, 'a', "y"), tuple(2, 'a', "z"),
527         tuple(2, 'b', "x"), tuple(2, 'b', "y"), tuple(2, 'b', "z"),
528         tuple(2, 'c', "x"), tuple(2, 'c', "y"), tuple(2, 'c', "z"),
529         tuple(3, 'a', "x"), tuple(3, 'a', "y"), tuple(3, 'a', "z"),
530         tuple(3, 'b', "x"), tuple(3, 'b', "y"), tuple(3, 'b', "z"),
531         tuple(3, 'c', "x"), tuple(3, 'c', "y"), tuple(3, 'c', "z")
532     ]));
533 }
534 
535 pure @safe nothrow @nogc unittest
536 {
537     import std.range.primitives : isForwardRange;
538     int[2] A = [1,2];
539     auto C = cartesianProduct(A[], A[], A[]);
540     assert(isForwardRange!(typeof(C)));
541 
542     C.popFront();
543     auto front1 = C.front;
544     auto D = C.save;
545     C.popFront();
546     assert(D.front == front1);
547 }
548 
549 // https://issues.dlang.org/show_bug.cgi?id=13935
550 @safe unittest
551 {
552     import std.algorithm.iteration : map;
553     auto seq = [1, 2].map!(x => x);
554     foreach (pair; cartesianProduct(seq, seq)) {}
555 }
556 
557 @system unittest
558 {
559     import std.algorithm.comparison : equal;
560     import std.typecons : tuple;
561 
562     static struct SystemRange
563     {
564         int[] data;
565 
566         int front() @system @property inout
567         {
568             return data[0];
569         }
570 
571         bool empty() @system @property inout
572         {
573             return data.length == 0;
574         }
575 
576         void popFront() @system
577         {
578             data = data[1 .. $];
579         }
580 
581         SystemRange save() @system
582         {
583             return this;
584         }
585     }
586 
587     assert(SystemRange([1, 2]).cartesianProduct(SystemRange([3, 4]))
588         .equal([tuple(1, 3), tuple(1, 4), tuple(2, 3), tuple(2, 4)]));
589 }
590 
591 // largestPartialIntersection
592 /**
593 Given a range of sorted $(REF_ALTTEXT forward ranges, isForwardRange, std,range,primitives)
594 `ror`, copies to `tgt` the elements that are common to most ranges, along with their number
595 of occurrences. All ranges in `ror` are assumed to be sorted by $(D
596 less). Only the most frequent `tgt.length` elements are returned.
597 
598 Params:
599     less = The predicate the ranges are sorted by.
600     ror = A range of forward ranges sorted by `less`.
601     tgt = The target range to copy common elements to.
602     sorted = Whether the elements copied should be in sorted order.
603 
604 The function `largestPartialIntersection` is useful for
605 e.g. searching an $(LINK2 https://en.wikipedia.org/wiki/Inverted_index,
606 inverted index) for the documents most
607 likely to contain some terms of interest. The complexity of the search
608 is $(BIGOH n * log(tgt.length)), where `n` is the sum of lengths of
609 all input ranges. This approach is faster than keeping an associative
610 array of the occurrences and then selecting its top items, and also
611 requires less memory (`largestPartialIntersection` builds its
612 result directly in `tgt` and requires no extra memory).
613 
614 If at least one of the ranges is a multiset, then all occurences
615 of a duplicate element are taken into account. The result is
616 equivalent to merging all ranges and picking the most frequent
617 `tgt.length` elements.
618 
619 Warning: Because `largestPartialIntersection` does not allocate
620 extra memory, it will leave `ror` modified. Namely, $(D
621 largestPartialIntersection) assumes ownership of `ror` and
622 discretionarily swaps and advances elements of it. If you want $(D
623 ror) to preserve its contents after the call, you may want to pass a
624 duplicate to `largestPartialIntersection` (and perhaps cache the
625 duplicate in between calls).
626  */
627 void largestPartialIntersection
628 (alias less = "a < b", RangeOfRanges, Range)
629 (RangeOfRanges ror, Range tgt, SortOutput sorted = No.sortOutput)
630 {
631     struct UnitWeights
632     {
633         static int opIndex(ElementType!(ElementType!RangeOfRanges)) { return 1; }
634     }
635     return largestPartialIntersectionWeighted!less(ror, tgt, UnitWeights(),
636             sorted);
637 }
638 
639 ///
640 @system unittest
641 {
642     import std.typecons : tuple, Tuple;
643 
644     // Figure which number can be found in most arrays of the set of
645     // arrays below.
646     double[][] a =
647     [
648         [ 1, 4, 7, 8 ],
649         [ 1, 7 ],
650         [ 1, 7, 8],
651         [ 4 ],
652         [ 7 ],
653     ];
654     auto b = new Tuple!(double, uint)[1];
655     // it will modify the input range, hence we need to create a duplicate
656     largestPartialIntersection(a.dup, b);
657     // First member is the item, second is the occurrence count
658     assert(b[0] == tuple(7.0, 4u));
659     // 7.0 occurs in 4 out of 5 inputs, more than any other number
660 
661     // If more of the top-frequent numbers are needed, just create a larger
662     // tgt range
663     auto c = new Tuple!(double, uint)[2];
664     largestPartialIntersection(a, c);
665     assert(c[0] == tuple(1.0, 3u));
666     // 1.0 occurs in 3 inputs
667 
668     // multiset
669     double[][] x =
670     [
671         [1, 1, 1, 1, 4, 7, 8],
672         [1, 7],
673         [1, 7, 8],
674         [4, 7],
675         [7]
676     ];
677     auto y = new Tuple!(double, uint)[2];
678     largestPartialIntersection(x.dup, y);
679     // 7.0 occurs 5 times
680     assert(y[0] == tuple(7.0, 5u));
681     // 1.0 occurs 6 times
682     assert(y[1] == tuple(1.0, 6u));
683 }
684 
685 import std.algorithm.sorting : SortOutput; // FIXME
686 
687 // largestPartialIntersectionWeighted
688 /**
689 Similar to `largestPartialIntersection`, but associates a weight
690 with each distinct element in the intersection.
691 
692 If at least one of the ranges is a multiset, then all occurences
693 of a duplicate element are taken into account. The result
694 is equivalent to merging all input ranges and picking the highest
695 `tgt.length`, weight-based ranking elements.
696 
697 Params:
698     less = The predicate the ranges are sorted by.
699     ror = A range of $(REF_ALTTEXT forward ranges, isForwardRange, std,range,primitives)
700     sorted by `less`.
701     tgt = The target range to copy common elements to.
702     weights = An associative array mapping elements to weights.
703     sorted = Whether the elements copied should be in sorted order.
704 
705 */
706 void largestPartialIntersectionWeighted
707 (alias less = "a < b", RangeOfRanges, Range, WeightsAA)
708 (RangeOfRanges ror, Range tgt, WeightsAA weights, SortOutput sorted = No.sortOutput)
709 {
710     import std.algorithm.iteration : group;
711     import std.algorithm.sorting : topNCopy;
712 
713     if (tgt.empty) return;
714     alias InfoType = ElementType!Range;
715     bool heapComp(InfoType a, InfoType b)
716     {
717         return weights[a[0]] * a[1] > weights[b[0]] * b[1];
718     }
719     topNCopy!heapComp(group(multiwayMerge!less(ror)), tgt, sorted);
720 }
721 
722 ///
723 @system unittest
724 {
725     import std.typecons : tuple, Tuple;
726 
727     // Figure which number can be found in most arrays of the set of
728     // arrays below, with specific per-element weights
729     double[][] a =
730     [
731         [ 1, 4, 7, 8 ],
732         [ 1, 7 ],
733         [ 1, 7, 8],
734         [ 4 ],
735         [ 7 ],
736     ];
737     auto b = new Tuple!(double, uint)[1];
738     double[double] weights = [ 1:1.2, 4:2.3, 7:1.1, 8:1.1 ];
739     largestPartialIntersectionWeighted(a, b, weights);
740     // First member is the item, second is the occurrence count
741     assert(b[0] == tuple(4.0, 2u));
742     // 4.0 occurs 2 times -> 4.6 (2 * 2.3)
743     // 7.0 occurs 3 times -> 4.4 (3 * 1.1)
744 
745    // multiset
746     double[][] x =
747     [
748         [ 1, 1, 1, 4, 7, 8 ],
749         [ 1, 7 ],
750         [ 1, 7, 8],
751         [ 4 ],
752         [ 7 ],
753     ];
754     auto y = new Tuple!(double, uint)[1];
755     largestPartialIntersectionWeighted(x, y, weights);
756     assert(y[0] == tuple(1.0, 5u));
757     // 1.0 occurs 5 times -> 1.2 * 5 = 6
758 }
759 
760 @system unittest
761 {
762     import std.conv : text;
763     import std.typecons : tuple, Tuple, Yes;
764 
765     double[][] a =
766         [
767             [ 1, 4, 7, 8 ],
768             [ 1, 7 ],
769             [ 1, 7, 8],
770             [ 4 ],
771             [ 7 ],
772         ];
773     auto b = new Tuple!(double, uint)[2];
774     largestPartialIntersection(a, b, Yes.sortOutput);
775     assert(b == [ tuple(7.0, 4u), tuple(1.0, 3u) ][], text(b));
776     assert(a[0].empty);
777 }
778 
779 @system unittest
780 {
781     import std.conv : text;
782     import std.typecons : tuple, Tuple, Yes;
783 
784     string[][] a =
785         [
786             [ "1", "4", "7", "8" ],
787             [ "1", "7" ],
788             [ "1", "7", "8"],
789             [ "4" ],
790             [ "7" ],
791         ];
792     auto b = new Tuple!(string, uint)[2];
793     largestPartialIntersection(a, b, Yes.sortOutput);
794     assert(b == [ tuple("7", 4u), tuple("1", 3u) ][], text(b));
795 }
796 
797 @system unittest
798 {
799     import std.typecons : tuple, Tuple;
800 
801     // Figure which number can be found in most arrays of the set of
802     // arrays below, with specific per-element weights
803     double[][] a =
804         [
805             [ 1, 4, 7, 8 ],
806             [ 1, 7 ],
807             [ 1, 7, 8],
808             [ 4 ],
809             [ 7 ],
810             ];
811     auto b = new Tuple!(double, uint)[1];
812     double[double] weights = [ 1:1.2, 4:2.3, 7:1.1, 8:1.1 ];
813     largestPartialIntersectionWeighted(a, b, weights);
814     // First member is the item, second is the occurrence count
815     assert(b[0] == tuple(4.0, 2u));
816 }
817 
818 @system unittest
819 {
820     import std.container : Array;
821     import std.typecons : Tuple;
822 
823     alias T = Tuple!(uint, uint);
824     const Array!T arrayOne = Array!T( [ T(1,2), T(3,4) ] );
825     const Array!T arrayTwo = Array!T([ T(1,2), T(3,4) ] );
826 
827     assert(arrayOne == arrayTwo);
828 }
829 
830 // MultiwayMerge
831 /**
832 Merges multiple sets. The input sets are passed as a
833 range of ranges and each is assumed to be sorted by $(D
834 less). Computation is done lazily, one union element at a time. The
835 complexity of one `popFront` operation is $(BIGOH
836 log(ror.length)). However, the length of `ror` decreases as ranges
837 in it are exhausted, so the complexity of a full pass through $(D
838 MultiwayMerge) is dependent on the distribution of the lengths of ranges
839 contained within `ror`. If all ranges have the same length `n`
840 (worst case scenario), the complexity of a full pass through $(D
841 MultiwayMerge) is $(BIGOH n * ror.length * log(ror.length)), i.e., $(D
842 log(ror.length)) times worse than just spanning all ranges in
843 turn. The output comes sorted (unstably) by `less`.
844 
845 The length of the resulting range is the sum of all lengths of
846 the ranges passed as input. This means that all elements (duplicates
847 included) are transferred to the resulting range.
848 
849 For backward compatibility, `multiwayMerge` is available under
850 the name `nWayUnion` and `MultiwayMerge` under the name of `NWayUnion` .
851 Future code should use `multiwayMerge` and `MultiwayMerge` as `nWayUnion`
852 and `NWayUnion` will be deprecated.
853 
854 Params:
855     less = Predicate the given ranges are sorted by.
856     ror = A range of ranges sorted by `less` to compute the union for.
857 
858 Returns:
859     A range of the union of the ranges in `ror`.
860 
861 Warning: Because `MultiwayMerge` does not allocate extra memory, it
862 will leave `ror` modified. Namely, `MultiwayMerge` assumes ownership
863 of `ror` and discretionarily swaps and advances elements of it. If
864 you want `ror` to preserve its contents after the call, you may
865 want to pass a duplicate to `MultiwayMerge` (and perhaps cache the
866 duplicate in between calls).
867 
868 See_Also: $(REF merge, std,algorithm,sorting) for an analogous function that
869     takes a static number of ranges of possibly disparate types.
870  */
871 struct MultiwayMerge(alias less, RangeOfRanges)
872 {
873     import std.container : BinaryHeap;
874 
875     private alias ElementType = .ElementType!(.ElementType!RangeOfRanges);
876     private alias comp = binaryFun!less;
877     private RangeOfRanges _ror;
878 
879     ///
880     static bool compFront(.ElementType!RangeOfRanges a,
881             .ElementType!RangeOfRanges b)
882     {
883         // revert comparison order so we get the smallest elements first
884         return comp(b.front, a.front);
885     }
886     private BinaryHeap!(RangeOfRanges, compFront) _heap;
887 
888     ///
889     this(RangeOfRanges ror)
890     {
891         import std.algorithm.mutation : remove, SwapStrategy;
892 
893         // Preemptively get rid of all empty ranges in the input
894         // No need for stability either
895         _ror = remove!("a.empty", SwapStrategy.unstable)(ror);
896         //Build the heap across the range
897         _heap.acquire(_ror);
898     }
899 
900     ///
901     @property bool empty() { return _ror.empty; }
902 
903     ///
904     @property auto ref front()
905     {
906         return _heap.front.front;
907     }
908 
909     ///
910     void popFront()
911     {
912         _heap.removeFront();
913         // let's look at the guy just popped
914         _ror.back.popFront();
915         if (_ror.back.empty)
916         {
917             _ror.popBack();
918             // nothing else to do: the empty range is not in the
919             // heap and not in _ror
920             return;
921         }
922         // Put the popped range back in the heap
923         const bool worked = _heap.conditionalInsert(_ror.back);
924         assert(worked, "Failed to insert item into heap");
925     }
926 }
927 
928 /// Ditto
929 MultiwayMerge!(less, RangeOfRanges) multiwayMerge
930 (alias less = "a < b", RangeOfRanges)
931 (RangeOfRanges ror)
932 {
933     return typeof(return)(ror);
934 }
935 
936 ///
937 @system unittest
938 {
939     import std.algorithm.comparison : equal;
940 
941     double[][] a =
942     [
943         [ 1, 4, 7, 8 ],
944         [ 1, 7 ],
945         [ 1, 7, 8],
946         [ 4 ],
947         [ 7 ],
948     ];
949     auto witness = [
950         1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8
951     ];
952     assert(equal(multiwayMerge(a), witness));
953 
954     double[][] b =
955     [
956         // range with duplicates
957         [ 1, 1, 4, 7, 8 ],
958         [ 7 ],
959         [ 1, 7, 8],
960         [ 4 ],
961         [ 7 ],
962     ];
963     // duplicates are propagated to the resulting range
964     assert(equal(multiwayMerge(b), witness));
965 }
966 
967 alias nWayUnion = multiwayMerge;
968 alias NWayUnion = MultiwayMerge;
969 
970 /**
971 Computes the union of multiple ranges. The
972 $(REF_ALTTEXT input ranges, isInputRange, std,range,primitives) are passed
973 as a range of ranges and each is assumed to be sorted by $(D
974 less). Computation is done lazily, one union element at a time.
975 `multiwayUnion(ror)` is functionally equivalent to `multiwayMerge(ror).uniq`.
976 
977 "The output of multiwayUnion has no duplicates even when its inputs contain duplicates."
978 
979 Params:
980     less = Predicate the given ranges are sorted by.
981     ror = A range of ranges sorted by `less` to compute the intersection for.
982 
983 Returns:
984     A range of the union of the ranges in `ror`.
985 
986 See also: $(LREF multiwayMerge)
987  */
988 auto multiwayUnion(alias less = "a < b", RangeOfRanges)(RangeOfRanges ror)
989 {
990     import std.algorithm.iteration : uniq;
991     import std.functional : not;
992     return ror.multiwayMerge!(less).uniq!(not!less);
993 }
994 
995 ///
996 @system unittest
997 {
998     import std.algorithm.comparison : equal;
999 
1000     // sets
1001     double[][] a =
1002     [
1003         [ 1, 4, 7, 8 ],
1004         [ 1, 7 ],
1005         [ 1, 7, 8],
1006         [ 4 ],
1007         [ 7 ],
1008     ];
1009 
1010     auto witness = [1, 4, 7, 8];
1011     assert(equal(multiwayUnion(a), witness));
1012 
1013     // multisets
1014     double[][] b =
1015     [
1016         [ 1, 1, 1, 4, 7, 8 ],
1017         [ 1, 7 ],
1018         [ 1, 7, 7, 8],
1019         [ 4 ],
1020         [ 7 ],
1021     ];
1022     assert(equal(multiwayUnion(b), witness));
1023 
1024     double[][] c =
1025     [
1026         [9, 8, 8, 8, 7, 6],
1027         [9, 8, 6],
1028         [9, 8, 5]
1029     ];
1030     auto witness2 = [9, 8, 7, 6, 5];
1031     assert(equal(multiwayUnion!"a > b"(c), witness2));
1032 }
1033 
1034 /**
1035 Lazily computes the difference of `r1` and `r2`. The two ranges
1036 are assumed to be sorted by `less`. The element types of the two
1037 ranges must have a common type.
1038 
1039 
1040 In the case of multisets, considering that element `a` appears `x`
1041 times in `r1` and `y` times and `r2`, the number of occurences
1042 of `a` in the resulting range is going to be `x-y` if x > y or 0 otherwise.
1043 
1044 Params:
1045     less = Predicate the given ranges are sorted by.
1046     r1 = The first range.
1047     r2 = The range to subtract from `r1`.
1048 
1049 Returns:
1050     A range of the difference of `r1` and `r2`.
1051 
1052 See_also: $(LREF setSymmetricDifference)
1053  */
1054 struct SetDifference(alias less = "a < b", R1, R2)
1055 if (isInputRange!(R1) && isInputRange!(R2))
1056 {
1057 private:
1058     R1 r1;
1059     R2 r2;
1060     alias comp = binaryFun!(less);
1061 
1062     void adjustPosition()
1063     {
1064         while (!r1.empty)
1065         {
1066             if (r2.empty || comp(r1.front, r2.front)) break;
1067             if (comp(r2.front, r1.front))
1068             {
1069                 r2.popFront();
1070             }
1071             else
1072             {
1073                 // both are equal
1074                 r1.popFront();
1075                 r2.popFront();
1076             }
1077         }
1078     }
1079 
1080 public:
1081     ///
1082     this(R1 r1, R2 r2)
1083     {
1084         this.r1 = r1;
1085         this.r2 = r2;
1086         // position to the first element
1087         adjustPosition();
1088     }
1089 
1090     ///
1091     void popFront()
1092     {
1093         r1.popFront();
1094         adjustPosition();
1095     }
1096 
1097     ///
1098     @property auto ref front()
1099     {
1100         assert(!empty, "Can not get front of empty SetDifference");
1101         return r1.front;
1102     }
1103 
1104     static if (isForwardRange!R1 && isForwardRange!R2)
1105     {
1106         ///
1107         @property typeof(this) save()
1108         {
1109             auto ret = this;
1110             ret.r1 = r1.save;
1111             ret.r2 = r2.save;
1112             return ret;
1113         }
1114     }
1115 
1116     ///
1117     @property bool empty() { return r1.empty; }
1118 }
1119 
1120 /// Ditto
1121 SetDifference!(less, R1, R2) setDifference(alias less = "a < b", R1, R2)
1122 (R1 r1, R2 r2)
1123 {
1124     return typeof(return)(r1, r2);
1125 }
1126 
1127 ///
1128 @safe unittest
1129 {
1130     import std.algorithm.comparison : equal;
1131     import std.range.primitives : isForwardRange;
1132 
1133     //sets
1134     int[] a = [ 1, 2, 4, 5, 7, 9 ];
1135     int[] b = [ 0, 1, 2, 4, 7, 8 ];
1136     assert(equal(setDifference(a, b), [5, 9]));
1137     static assert(isForwardRange!(typeof(setDifference(a, b))));
1138 
1139     // multisets
1140     int[] x = [1, 1, 1, 2, 3];
1141     int[] y = [1, 1, 2, 4, 5];
1142     auto r = setDifference(x, y);
1143     assert(equal(r, [1, 3]));
1144     assert(setDifference(r, x).empty);
1145 }
1146 
1147 // https://issues.dlang.org/show_bug.cgi?id=10460
1148 @safe unittest
1149 {
1150     import std.algorithm.comparison : equal;
1151 
1152     int[] a = [1, 2, 3, 4, 5];
1153     int[] b = [2, 4];
1154     foreach (ref e; setDifference(a, b))
1155         e = 0;
1156     assert(equal(a, [0, 2, 0, 4, 0]));
1157 }
1158 
1159 /**
1160 Lazily computes the intersection of two or more
1161 $(REF_ALTTEXT input ranges, isInputRange, std,range,primitives)
1162 `ranges`. The ranges are assumed to be sorted by `less`. The element
1163 types of the ranges must have a common type.
1164 
1165 In the case of multisets, the range with the minimum number of
1166 occurences of a given element, propagates the number of
1167 occurences of this element to the resulting range.
1168 
1169 Params:
1170     less = Predicate the given ranges are sorted by.
1171     ranges = The ranges to compute the intersection for.
1172 
1173 Returns:
1174     A range containing the intersection of the given ranges.
1175  */
1176 struct SetIntersection(alias less = "a < b", Rs...)
1177 if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) &&
1178     !is(CommonType!(staticMap!(ElementType, Rs)) == void))
1179 {
1180 private:
1181     Rs _input;
1182     alias comp = binaryFun!less;
1183     alias ElementType = CommonType!(staticMap!(.ElementType, Rs));
1184 
1185     // Positions to the first elements that are all equal
1186     void adjustPosition()
1187     {
1188         if (empty) return;
1189 
1190         size_t done = Rs.length;
1191         static if (Rs.length > 1) while (true)
1192         {
1193             foreach (i, ref r; _input)
1194             {
1195                 alias next = _input[(i + 1) % Rs.length];
1196 
1197                 if (comp(next.front, r.front))
1198                 {
1199                     do
1200                     {
1201                         next.popFront();
1202                         if (next.empty) return;
1203                     } while (comp(next.front, r.front));
1204                     done = Rs.length;
1205                 }
1206                 if (--done == 0) return;
1207             }
1208         }
1209     }
1210 
1211 public:
1212     ///
1213     this(Rs input)
1214     {
1215         this._input = input;
1216         // position to the first element
1217         adjustPosition();
1218     }
1219 
1220     ///
1221     @property bool empty()
1222     {
1223         foreach (ref r; _input)
1224         {
1225             if (r.empty) return true;
1226         }
1227         return false;
1228     }
1229 
1230     ///
1231     void popFront()
1232     {
1233         assert(!empty, "Can not popFront of empty SetIntersection");
1234         static if (Rs.length > 1) foreach (i, ref r; _input)
1235         {
1236             alias next = _input[(i + 1) % Rs.length];
1237             assert(!comp(r.front, next.front), "Set elements must not"
1238                     ~ " contradict the less predicate");
1239         }
1240 
1241         foreach (ref r; _input)
1242         {
1243             r.popFront();
1244         }
1245         adjustPosition();
1246     }
1247 
1248     ///
1249     @property ElementType front()
1250     {
1251         assert(!empty, "Can not get front of empty SetIntersection");
1252         return _input[0].front;
1253     }
1254 
1255     static if (allSatisfy!(isForwardRange, Rs))
1256     {
1257         ///
1258         @property SetIntersection save()
1259         {
1260             auto ret = this;
1261             foreach (i, ref r; _input)
1262             {
1263                 ret._input[i] = r.save;
1264             }
1265             return ret;
1266         }
1267     }
1268 }
1269 
1270 /// Ditto
1271 SetIntersection!(less, Rs) setIntersection(alias less = "a < b", Rs...)(Rs ranges)
1272 if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) &&
1273     !is(CommonType!(staticMap!(ElementType, Rs)) == void))
1274 {
1275     return typeof(return)(ranges);
1276 }
1277 
1278 ///
1279 @safe unittest
1280 {
1281     import std.algorithm.comparison : equal;
1282 
1283     // sets
1284     int[] a = [ 1, 2, 4, 5, 7, 9 ];
1285     int[] b = [ 0, 1, 2, 4, 7, 8 ];
1286     int[] c = [ 0, 1, 4, 5, 7, 8 ];
1287     assert(equal(setIntersection(a, a), a));
1288     assert(equal(setIntersection(a, b), [1, 2, 4, 7]));
1289     assert(equal(setIntersection(a, b, c), [1, 4, 7]));
1290 
1291     // multisets
1292     int[] d = [ 1, 1, 2, 2, 7, 7 ];
1293     int[] e = [ 1, 1, 1, 7];
1294     assert(equal(setIntersection(a, d), [1, 2, 7]));
1295     assert(equal(setIntersection(d, e), [1, 1, 7]));
1296 }
1297 
1298 @safe unittest
1299 {
1300     import std.algorithm.comparison : equal;
1301     import std.algorithm.iteration : filter;
1302 
1303     int[] a = [ 1, 2, 4, 5, 7, 9 ];
1304     int[] b = [ 0, 1, 2, 4, 7, 8 ];
1305     int[] c = [ 0, 1, 4, 5, 7, 8 ];
1306     int[] d = [ 1, 3, 4 ];
1307     int[] e = [ 4, 5 ];
1308 
1309     assert(equal(setIntersection(a, a), a));
1310     assert(equal(setIntersection(a, a, a), a));
1311     assert(equal(setIntersection(a, b), [1, 2, 4, 7]));
1312     assert(equal(setIntersection(a, b, c), [1, 4, 7]));
1313     assert(equal(setIntersection(a, b, c, d), [1, 4]));
1314     assert(equal(setIntersection(a, b, c, d, e), [4]));
1315 
1316     auto inpA = a.filter!(_ => true), inpB = b.filter!(_ => true);
1317     auto inpC = c.filter!(_ => true), inpD = d.filter!(_ => true);
1318     assert(equal(setIntersection(inpA, inpB, inpC, inpD), [1, 4]));
1319 
1320     assert(equal(setIntersection(a, b, b, a), [1, 2, 4, 7]));
1321     assert(equal(setIntersection(a, c, b), [1, 4, 7]));
1322     assert(equal(setIntersection(b, a, c), [1, 4, 7]));
1323     assert(equal(setIntersection(b, c, a), [1, 4, 7]));
1324     assert(equal(setIntersection(c, a, b), [1, 4, 7]));
1325     assert(equal(setIntersection(c, b, a), [1, 4, 7]));
1326 }
1327 
1328 /**
1329 Lazily computes the symmetric difference of `r1` and `r2`,
1330 i.e. the elements that are present in exactly one of `r1` and $(D
1331 r2). The two ranges are assumed to be sorted by `less`, and the
1332 output is also sorted by `less`. The element types of the two
1333 ranges must have a common type.
1334 
1335 If both ranges are sets (without duplicated elements), the resulting
1336 range is going to be a set. If at least one of the ranges is a multiset,
1337 the number of occurences of an element `x` in the resulting range is `abs(a-b)`
1338 where `a` is the number of occurences of `x` in `r1`, `b` is the number of
1339 occurences of `x` in `r2`, and `abs` is the absolute value.
1340 
1341 If both arguments are ranges of L-values of the same type then
1342 `SetSymmetricDifference` will also be a range of L-values of
1343 that type.
1344 
1345 Params:
1346     less = Predicate the given ranges are sorted by.
1347     r1 = The first range.
1348     r2 = The second range.
1349 
1350 Returns:
1351     A range of the symmetric difference between `r1` and `r2`.
1352 
1353 See_also: $(LREF setDifference)
1354  */
1355 struct SetSymmetricDifference(alias less = "a < b", R1, R2)
1356 if (isInputRange!(R1) && isInputRange!(R2))
1357 {
1358 private:
1359     R1 r1;
1360     R2 r2;
1361     //bool usingR2;
1362     alias comp = binaryFun!(less);
1363 
1364     void adjustPosition()
1365     {
1366         while (!r1.empty && !r2.empty)
1367         {
1368             if (comp(r1.front, r2.front) || comp(r2.front, r1.front))
1369             {
1370                 break;
1371             }
1372             // equal, pop both
1373             r1.popFront();
1374             r2.popFront();
1375         }
1376     }
1377 
1378 public:
1379     ///
1380     this(R1 r1, R2 r2)
1381     {
1382         this.r1 = r1;
1383         this.r2 = r2;
1384         // position to the first element
1385         adjustPosition();
1386     }
1387 
1388     ///
1389     void popFront()
1390     {
1391         assert(!empty, "Can not popFront of empty SetSymmetricDifference");
1392         if (r1.empty) r2.popFront();
1393         else if (r2.empty) r1.popFront();
1394         else
1395         {
1396             // neither is empty
1397             if (comp(r1.front, r2.front))
1398             {
1399                 r1.popFront();
1400             }
1401             else
1402             {
1403                 assert(comp(r2.front, r1.front), "Elements of R1 and R2"
1404                         ~ " must be different");
1405                 r2.popFront();
1406             }
1407         }
1408         adjustPosition();
1409     }
1410 
1411     ///
1412     @property auto ref front()
1413     {
1414         assert(!empty, "Can not get the front of an empty"
1415                 ~ " SetSymmetricDifference");
1416         immutable chooseR1 = r2.empty || !r1.empty && comp(r1.front, r2.front);
1417         assert(chooseR1 || r1.empty || comp(r2.front, r1.front), "Failed to"
1418                 ~ " get appropriate front");
1419         return chooseR1 ? r1.front : r2.front;
1420     }
1421 
1422     static if (isForwardRange!R1 && isForwardRange!R2)
1423     {
1424         ///
1425         @property typeof(this) save()
1426         {
1427             auto ret = this;
1428             ret.r1 = r1.save;
1429             ret.r2 = r2.save;
1430             return ret;
1431         }
1432     }
1433 
1434     ///
1435     ref auto opSlice() { return this; }
1436 
1437     ///
1438     @property bool empty() { return r1.empty && r2.empty; }
1439 }
1440 
1441 /// Ditto
1442 SetSymmetricDifference!(less, R1, R2)
1443 setSymmetricDifference(alias less = "a < b", R1, R2)
1444 (R1 r1, R2 r2)
1445 {
1446     return typeof(return)(r1, r2);
1447 }
1448 
1449 ///
1450 @safe unittest
1451 {
1452     import std.algorithm.comparison : equal;
1453     import std.range.primitives : isForwardRange;
1454 
1455     // sets
1456     int[] a = [ 1, 2, 4, 5, 7, 9 ];
1457     int[] b = [ 0, 1, 2, 4, 7, 8 ];
1458     assert(equal(setSymmetricDifference(a, b), [0, 5, 8, 9][]));
1459     static assert(isForwardRange!(typeof(setSymmetricDifference(a, b))));
1460 
1461     //mutisets
1462     int[] c = [1, 1, 1, 1, 2, 2, 2, 4, 5, 6];
1463     int[] d = [1, 1, 2, 2, 2, 2, 4, 7, 9];
1464     assert(equal(setSymmetricDifference(c, d), setSymmetricDifference(d, c)));
1465     assert(equal(setSymmetricDifference(c, d), [1, 1, 2, 5, 6, 7, 9]));
1466 }
1467 
1468 // https://issues.dlang.org/show_bug.cgi?id=10460
1469 @safe unittest
1470 {
1471     import std.algorithm.comparison : equal;
1472 
1473     int[] a = [1, 2];
1474     double[] b = [2.0, 3.0];
1475     int[] c = [2, 3];
1476 
1477     alias R1 = typeof(setSymmetricDifference(a, b));
1478     static assert(is(ElementType!R1 == double));
1479     static assert(!hasLvalueElements!R1);
1480 
1481     alias R2 = typeof(setSymmetricDifference(a, c));
1482     static assert(is(ElementType!R2 == int));
1483     static assert(hasLvalueElements!R2);
1484 
1485     assert(equal(setSymmetricDifference(a, b), [1.0, 3.0]));
1486     assert(equal(setSymmetricDifference(a, c), [1, 3]));
1487 }
1488 
1489 /++
1490 TODO: once SetUnion got deprecated we can provide the usual definition
1491 (= merge + filter after uniqs)
1492 See: https://github.com/dlang/phobos/pull/4249
1493 /**
1494 Lazily computes the union of two or more ranges `rs`. The ranges
1495 are assumed to be sorted by `less`. Elements in the output are
1496 unique. The element types of all ranges must have a common type.
1497 
1498 Params:
1499     less = Predicate the given ranges are sorted by.
1500     rs = The ranges to compute the union for.
1501 
1502 Returns:
1503     A range containing the unique union of the given ranges.
1504 
1505 See_Also:
1506    $(REF merge, std,algorithm,sorting)
1507  */
1508 auto setUnion(alias less = "a < b", Rs...)
1509 (Rs rs)
1510 {
1511     import std.algorithm.iteration : uniq;
1512     import std.algorithm.sorting : merge;
1513     return merge!(less, Rs)(rs).uniq;
1514 }
1515 
1516 ///
1517 @safe pure nothrow unittest
1518     ///
1519 {
1520     import std.algorithm.comparison : equal;
1521 
1522     int[] a = [1, 3, 5];
1523     int[] b = [2, 3, 4];
1524     assert(a.setUnion(b).equal([1, 2, 3, 4, 5]));
1525 }
1526 
1527 @safe pure nothrow unittest
1528 {
1529     import std.algorithm.comparison : equal;
1530 
1531     int[] a = [ 1, 2, 4, 5, 7, 9 ];
1532     int[] b = [ 0, 1, 2, 4, 7, 8 ];
1533     double[] c = [ 10.5 ];
1534 
1535     assert(equal(setUnion(a, b), [0, 1, 2, 4, 5, 7, 8, 9][]));
1536     assert(equal(setUnion(a, c, b),
1537                     [0, 1, 2, 4, 5, 7, 8, 9, 10.5][]));
1538 }
1539 
1540 @safe unittest
1541 {
1542     // save
1543     import std.range : dropOne;
1544     int[] a = [0, 1, 2];
1545     int[] b = [0, 3];
1546     auto arr = a.setUnion(b);
1547     assert(arr.front == 0);
1548     assert(arr.save.dropOne.front == 1);
1549     assert(arr.front == 0);
1550 }
1551 
1552 @nogc @safe pure nothrow unittest
1553 {
1554     import std.algorithm.comparison : equal;
1555 
1556     static immutable a = [1, 3, 5];
1557     static immutable b = [2, 4];
1558     static immutable r = [1, 2, 3, 4, 5];
1559     assert(a.setUnion(b).equal(r));
1560 }
1561 
1562 @safe pure nothrow unittest
1563 {
1564     import std.algorithm.comparison : equal;
1565     import std.internal.test.dummyrange;
1566     import std.range : iota;
1567 
1568     auto dummyResult1 = [1, 1.5, 2, 3, 4, 5, 5.5, 6, 7, 8, 9, 10];
1569     auto dummyResult2 = iota(1, 11);
1570     foreach (DummyType; AllDummyRanges)
1571     {
1572         DummyType d;
1573         assert(d.setUnion([1, 1.5, 5.5]).equal(dummyResult1));
1574         assert(d.setUnion(d).equal(dummyResult2));
1575     }
1576 }
1577 ++/