1// Written in the D programming language. 2/** 3This is a submodule of $(MREF std, algorithm). 4It contains generic algorithms that implement set operations. 5 6The functions $(LREF multiwayMerge), $(LREF multiwayUnion), $(LREF setDifference), 7$(LREF setIntersection), $(LREF setSymmetricDifference) expect a range of sorted 8ranges as input. 9 10All algorithms are generalized to accept as input not only sets but also 11$(HTTP https://en.wikipedia.org/wiki/Multiset, multisets). Each algorithm 12documents 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 37Copyright: Andrei Alexandrescu 2008-. 38 39License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). 40 41Authors: $(HTTP erdani.com, Andrei Alexandrescu) 42 43Source: $(PHOBOSSRC std/algorithm/_setops.d) 44 45Macros: 46T2=$(TR $(TDNW $(LREF $1)) $(TD $+)) 47 */ 48module std.algorithm.setops; 49 50import std.range.primitives; 51 52// FIXME 53import std.functional; // : unaryFun, binaryFun; 54import std.traits; 55// FIXME 56import std.meta; // : AliasSeq, staticMap, allSatisfy, anySatisfy; 57 58import std.algorithm.sorting; // : Merge; 59import std.typecons : No; 60 61// cartesianProduct 62/** 63Lazily computes the Cartesian product of two or more ranges. The product is a 64_range of tuples of elements from each respective range. 65 66The conditions for the two-range case are as follows: 67 68If both ranges are finite, then one must be (at least) a 69$(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) and the 70other an $(REF_ALTTEXT input range, isInputRange, std,range,primitives). 71 72If one _range is infinite and the other finite, then the finite _range must 73be a forward _range, and the infinite range can be an input _range. 74 75If both ranges are infinite, then both must be forward ranges. 76 77When there are more than two ranges, the above conditions apply to each 78adjacent pair of ranges. 79 80Params: 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 86Returns: 87 A forward range of $(REF Tuple, std,typecons) representing elements of the 88 cartesian product of the given ranges. 89*/ 90auto cartesianProduct(R1, R2)(R1 range1, R2 range2) 91if (!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 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 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 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); 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 243 foreach (pair; Expected) 244 { 245 assert(canFind(XY, tuple(pair[0], pair[1]))); 246 } 247 248 // Verify XY ��� Expected 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. 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 } 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 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 } 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 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 352pure nothrow @safe @nogc unittest 353{ 354 int[1] a = [1]; 355 foreach (t; cartesianProduct(a[], a[])) {} 356} 357 358/// ditto 359auto cartesianProduct(RR...)(RR ranges) 360if (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 378 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 } 389 @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 } 396 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 } 409 @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); 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@safe unittest 450{ 451 // Issue 13393 452 assert(!cartesianProduct([0],[0],[0]).save.empty); 453} 454 455/// ditto 456auto cartesianProduct(R1, R2, RR...)(R1 range1, R2 range2, RR otherRanges) 457if (!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 535pure @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); 554 foreach (pair; cartesianProduct(seq, seq)) {} 555} 556 557// largestPartialIntersection 558/** 559Given 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 561of occurrences. All ranges in $(D ror) are assumed to be sorted by $(D 562less). Only the most frequent $(D tgt.length) elements are returned. 563 564Params: 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 570The function $(D largestPartialIntersection) is useful for 571e.g. searching an $(LINK2 https://en.wikipedia.org/wiki/Inverted_index, 572inverted index) for the documents most 573likely to contain some terms of interest. The complexity of the search 574is $(BIGOH n * log(tgt.length)), where $(D n) is the sum of lengths of 575all input ranges. This approach is faster than keeping an associative 576array of the occurrences and then selecting its top items, and also 577requires less memory ($(D largestPartialIntersection) builds its 578result directly in $(D tgt) and requires no extra memory). 579 580If at least one of the ranges is a multiset, then all occurences 581of a duplicate element are taken into account. The result is 582equivalent to merging all ranges and picking the most frequent 583$(D tgt.length) elements. 584 585Warning: Because $(D largestPartialIntersection) does not allocate 586extra memory, it will leave $(D ror) modified. Namely, $(D 587largestPartialIntersection) assumes ownership of $(D ror) and 588discretionarily swaps and advances elements of it. If you want $(D 589ror) to preserve its contents after the call, you may want to pass a 590duplicate to $(D largestPartialIntersection) (and perhaps cache the 591duplicate in between calls). 592 */ 593void 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 651import std.algorithm.sorting : SortOutput; // FIXME 652 653// largestPartialIntersectionWeighted 654/** 655Similar to $(D largestPartialIntersection), but associates a weight 656with each distinct element in the intersection. 657 658If at least one of the ranges is a multiset, then all occurences 659of a duplicate element are taken into account. The result 660is equivalent to merging all input ranges and picking the highest 661$(D tgt.length), weight-based ranking elements. 662 663Params: 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*/ 672void 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; 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/** 798Merges multiple sets. The input sets are passed as a 799range of ranges and each is assumed to be sorted by $(D 800less). Computation is done lazily, one union element at a time. The 801complexity of one $(D popFront) operation is $(BIGOH 802log(ror.length)). However, the length of $(D ror) decreases as ranges 803in it are exhausted, so the complexity of a full pass through $(D 804MultiwayMerge) is dependent on the distribution of the lengths of ranges 805contained within $(D ror). If all ranges have the same length $(D n) 806(worst case scenario), the complexity of a full pass through $(D 807MultiwayMerge) is $(BIGOH n * ror.length * log(ror.length)), i.e., $(D 808log(ror.length)) times worse than just spanning all ranges in 809turn. The output comes sorted (unstably) by $(D less). 810 811The length of the resulting range is the sum of all lengths of 812the ranges passed as input. This means that all elements (duplicates 813included) are transferred to the resulting range. 814 815For backward compatibility, `multiwayMerge` is available under 816the name `nWayUnion` and `MultiwayMerge` under the name of `NWayUnion` . 817Future code should use `multiwayMerge` and `MultiwayMerge` as `nWayUnion` 818and `NWayUnion` will be deprecated. 819 820Params: 821 less = Predicate the given ranges are sorted by. 822 ror = A range of ranges sorted by `less` to compute the union for. 823 824Returns: 825 A range of the union of the ranges in `ror`. 826 827Warning: Because $(D MultiwayMerge) does not allocate extra memory, it 828will leave $(D ror) modified. Namely, $(D MultiwayMerge) assumes ownership 829of $(D ror) and discretionarily swaps and advances elements of it. If 830you want $(D ror) to preserve its contents after the call, you may 831want to pass a duplicate to $(D MultiwayMerge) (and perhaps cache the 832duplicate in between calls). 833 */ 834struct 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 891MultiwayMerge!(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 929alias nWayUnion = multiwayMerge; 930alias NWayUnion = MultiwayMerge; 931 932/** 933Computes the union of multiple ranges. The input ranges are passed 934as a range of ranges and each is assumed to be sorted by $(D 935less). 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 940Params: 941 less = Predicate the given ranges are sorted by. 942 ror = A range of ranges sorted by `less` to compute the intersection for. 943 944Returns: 945 A range of the union of the ranges in `ror`. 946 947See also: $(LREF multiwayMerge) 948 */ 949auto 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/** 986Lazily computes the difference of $(D r1) and $(D r2). The two ranges 987are assumed to be sorted by $(D less). The element types of the two 988ranges must have a common type. 989 990 991In the case of multisets, considering that element `a` appears `x` 992times in $(D r1) and `y` times and $(D r2), the number of occurences 993of `a` in the resulting range is going to be `x-y` if x > y or 0 othwerise. 994 995Params: 996 less = Predicate the given ranges are sorted by. 997 r1 = The first range. 998 r2 = The range to subtract from `r1`. 999 1000Returns: 1001 A range of the difference of `r1` and `r2`. 1002 1003See_also: $(LREF setSymmetricDifference) 1004 */ 1005struct SetDifference(alias less = "a < b", R1, R2) 1006if (isInputRange!(R1) && isInputRange!(R2)) 1007{ 1008private: 1009 R1 r1; 1010 R2 r2; 1011 alias comp = binaryFun!(less); 1012 1013 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 1031public: 1032 /// 1033 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 /// 1042 void popFront() 1043 { 1044 r1.popFront(); 1045 adjustPosition(); 1046 } 1047 1048 /// 1049 @property auto ref front() 1050 { 1051 assert(!empty); 1052 return r1.front; 1053 } 1054 1055 static if (isForwardRange!R1 && isForwardRange!R2) 1056 { 1057 /// 1058 @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 /// 1068 @property bool empty() { return r1.empty; } 1069} 1070 1071/// Ditto 1072SetDifference!(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/** 1110Lazily computes the intersection of two or more input ranges $(D 1111ranges). The ranges are assumed to be sorted by $(D less). The element 1112types of the ranges must have a common type. 1113 1114In the case of multisets, the range with the minimum number of 1115occurences of a given element, propagates the number of 1116occurences of this element to the resulting range. 1117 1118Params: 1119 less = Predicate the given ranges are sorted by. 1120 ranges = The ranges to compute the intersection for. 1121 1122Returns: 1123 A range containing the intersection of the given ranges. 1124 */ 1125struct SetIntersection(alias less = "a < b", Rs...) 1126if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && 1127 !is(CommonType!(staticMap!(ElementType, Rs)) == void)) 1128{ 1129private: 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 1135 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 1160public: 1161 /// 1162 this(Rs input) 1163 { 1164 this._input = input; 1165 // position to the first element 1166 adjustPosition(); 1167 } 1168 1169 /// 1170 @property bool empty() 1171 { 1172 foreach (ref r; _input) 1173 { 1174 if (r.empty) return true; 1175 } 1176 return false; 1177 } 1178 1179 /// 1180 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 /// 1197 @property ElementType front() 1198 { 1199 assert(!empty); 1200 return _input[0].front; 1201 } 1202 1203 static if (allSatisfy!(isForwardRange, Rs)) 1204 { 1205 /// 1206 @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 1219SetIntersection!(less, Rs) setIntersection(alias less = "a < b", Rs...)(Rs ranges) 1220if (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/** 1277Lazily computes the symmetric difference of $(D r1) and $(D r2), 1278i.e. the elements that are present in exactly one of $(D r1) and $(D 1279r2). The two ranges are assumed to be sorted by $(D less), and the 1280output is also sorted by $(D less). The element types of the two 1281ranges must have a common type. 1282 1283If both ranges are sets (without duplicated elements), the resulting 1284range is going to be a set. If at least one of the ranges is a multiset, 1285the number of occurences of an element `x` in the resulting range is `abs(a-b)` 1286where `a` is the number of occurences of `x` in $(D r1), `b` is the number of 1287occurences of `x` in $(D r2), and `abs` is the absolute value. 1288 1289If both arguments are ranges of L-values of the same type then 1290$(D SetSymmetricDifference) will also be a range of L-values of 1291that type. 1292 1293Params: 1294 less = Predicate the given ranges are sorted by. 1295 r1 = The first range. 1296 r2 = The second range. 1297 1298Returns: 1299 A range of the symmetric difference between `r1` and `r2`. 1300 1301See_also: $(LREF setDifference) 1302 */ 1303struct SetSymmetricDifference(alias less = "a < b", R1, R2) 1304if (isInputRange!(R1) && isInputRange!(R2)) 1305{ 1306private: 1307 R1 r1; 1308 R2 r2; 1309 //bool usingR2; 1310 alias comp = binaryFun!(less); 1311 1312 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 1326public: 1327 /// 1328 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 /// 1337 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 /// 1359 @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 /// 1370 @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 /// 1380 ref auto opSlice() { return this; } 1381 1382 /// 1383 @property bool empty() { return r1.empty && r2.empty; } 1384} 1385 1386/// Ditto 1387SetSymmetricDifference!(less, R1, R2) 1388setSymmetricDifference(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/++ 1434TODO: once SetUnion got deprecated we can provide the usual definition 1435(= merge + filter after uniqs) 1436See: https://github.com/dlang/phobos/pull/4249 1437/** 1438Lazily computes the union of two or more ranges $(D rs). The ranges 1439are assumed to be sorted by $(D less). Elements in the output are 1440unique. The element types of all ranges must have a common type. 1441 1442Params: 1443 less = Predicate the given ranges are sorted by. 1444 rs = The ranges to compute the union for. 1445 1446Returns: 1447 A range containing the unique union of the given ranges. 1448 1449See_Also: 1450 $(REF merge, std,algorithm,sorting) 1451 */ 1452auto 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