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