The D Programming Language's Unofficial Docs
beta
The D Programming Language's Unofficial Docs
beta
A range containing the union of the given ranges.
All of its inputs are assumed to be sorted. This can mean that inputs are instances of std.range.SortedRange. Use the result of std.algorithm.sorting.sort, or std.range.assumeSorted to merge ranges known to be sorted (show in the example below). Note that there is currently no way of ensuring that two or more instances of std.range.SortedRange are sorted using a specific comparison function pred. Therefore no checking is done here to assure that all inputs rs are instances of std.range.SortedRange.
This algorithm is lazy, doing work progressively as elements are pulled off the result.
Time complexity is proportional to the sum of element counts over all inputs.
If all inputs have the same element type and offer it by ref, output becomes a range with mutable front (and back where appropriate) that reflects in the original inputs.
If any of the inputs rs is infinite so is the result (empty being always false).
import std.algorithm.comparison : equal; import std.range : retro; int[] a = [1, 3, 5]; int[] b = [2, 3, 4]; assert(a.merge(b).equal([1, 2, 3, 3, 4, 5])); assert(a.merge(b).retro.equal([5, 4, 3, 3, 2, 1]));
test bi-directional access and common type
1 import std.algorithm.comparison : equal; 2 import std.range : retro; 3 import std.traits : CommonType; 4 5 alias S = short; 6 alias I = int; 7 alias D = double; 8 9 S[] a = [1, 2, 3]; 10 I[] b = [50, 60]; 11 D[] c = [10, 20, 30, 40]; 12 13 auto m = merge(a, b, c); 14 15 static assert(is(typeof(m.front) == CommonType!(S, I, D))); 16 17 assert(equal(m, [1, 2, 3, 10, 20, 30, 40, 50, 60])); 18 assert(equal(m.retro, [60, 50, 40, 30, 20, 10, 3, 2, 1])); 19 20 m.popFront(); 21 assert(equal(m, [2, 3, 10, 20, 30, 40, 50, 60])); 22 m.popBack(); 23 assert(equal(m, [2, 3, 10, 20, 30, 40, 50])); 24 m.popFront(); 25 assert(equal(m, [3, 10, 20, 30, 40, 50])); 26 m.popBack(); 27 assert(equal(m, [3, 10, 20, 30, 40])); 28 m.popFront(); 29 assert(equal(m, [10, 20, 30, 40])); 30 m.popBack(); 31 assert(equal(m, [10, 20, 30])); 32 m.popFront(); 33 assert(equal(m, [20, 30])); 34 m.popBack(); 35 assert(equal(m, [20])); 36 m.popFront(); 37 assert(m.empty);
std.algorithm.setops.multiwayMerge for an analogous function that merges a dynamic number of ranges.
Merge multiple sorted ranges rs with less-than predicate function pred into one single sorted output range containing the sorted union of the elements of inputs. Duplicates are not eliminated, meaning that the total number of elements in the output is the sum of all elements in the ranges passed to it; the length member is offered if all inputs also have length. The element types of all the inputs must have a common type CommonType.