std.algorithm.setops.MultiwayMerge/multiwayMerge
- multiple declarations
Function multiwayMerge
Merges multiple sets. The input sets are passed as a
range of ranges and each is assumed to be sorted by less
. Computation is done lazily, one union element at a time. The
complexity of one popFront
operation is Ο(log(ror
). However, the length of ror
decreases as ranges
in it are exhausted, so the complexity of a full pass through MultiwayMerge
is dependent on the distribution of the lengths of ranges
contained within ror
. If all ranges have the same length n
(worst case scenario), the complexity of a full pass through MultiwayMerge
is Ο(n * ror
), i.e., log(ror
times worse than just spanning all ranges in
turn. The output comes sorted (unstably) by less
.
The length of the resulting range is the sum of all lengths of the ranges passed as input. This means that all elements (duplicates included) are transferred to the resulting range.
For backward compatibility, multiwayMerge
is available under
the name nWayUnion
and MultiwayMerge
under the name of NWayUnion
.
Future code should use multiwayMerge
and MultiwayMerge
as nWayUnion
and NWayUnion
will be deprecated.
Parameters
Name | Description |
---|---|
less | Predicate the given ranges are sorted by. |
ror | A range of ranges sorted by less to compute the union for. |
Returns
A range of the union of the ranges in ror
.
Warning
Because MultiwayMerge
does not allocate extra memory, it
will leave ror
modified. Namely, MultiwayMerge
assumes ownership
of ror
and discretionarily swaps and advances elements of it. If
you want ror
to preserve its contents after the call, you may
want to pass a duplicate to MultiwayMerge
(and perhaps cache the
duplicate in between calls).
See Also
merge
for an analogous function that
takes a static number of ranges of possibly disparate types.
Example
import std .algorithm .comparison : equal;
double[][] a =
[
[ 1, 4, 7, 8 ],
[ 1, 7 ],
[ 1, 7, 8],
[ 4 ],
[ 7 ],
];
auto witness = [
1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8
];
assert(equal(multiwayMerge(a), witness));
double[][] b =
[
// range with duplicates
[ 1, 1, 4, 7, 8 ],
[ 7 ],
[ 1, 7, 8],
[ 4 ],
[ 7 ],
];
// duplicates are propagated to the resulting range
assert(equal(multiwayMerge(b), witness));
Struct MultiwayMerge
Merges multiple sets. The input sets are passed as a
range of ranges and each is assumed to be sorted by less
. Computation is done lazily, one union element at a time. The
complexity of one popFront
operation is Ο(log(ror
). However, the length of ror
decreases as ranges
in it are exhausted, so the complexity of a full pass through MultiwayMerge
is dependent on the distribution of the lengths of ranges
contained within ror
. If all ranges have the same length n
(worst case scenario), the complexity of a full pass through MultiwayMerge
is Ο(n * ror
), i.e., log(ror
times worse than just spanning all ranges in
turn. The output comes sorted (unstably) by less
.
struct MultiwayMerge(alias less, RangeOfRanges)
;
The length of the resulting range is the sum of all lengths of the ranges passed as input. This means that all elements (duplicates included) are transferred to the resulting range.
For backward compatibility, multiwayMerge
is available under
the name nWayUnion
and MultiwayMerge
under the name of NWayUnion
.
Future code should use multiwayMerge
and MultiwayMerge
as nWayUnion
and NWayUnion
will be deprecated.
Constructors
Name | Description |
---|---|
this
|
Properties
Name | Type | Description |
---|---|---|
empty [get]
|
bool | |
front [get]
|
auto |
Methods
Name | Description |
---|---|
compFront
|
|
popFront
|
Parameters
Name | Description |
---|---|
less | Predicate the given ranges are sorted by. |
ror | A range of ranges sorted by less to compute the union for. |
Returns
A range of the union of the ranges in ror
.
Warning
Because MultiwayMerge
does not allocate extra memory, it
will leave ror
modified. Namely, MultiwayMerge
assumes ownership
of ror
and discretionarily swaps and advances elements of it. If
you want ror
to preserve its contents after the call, you may
want to pass a duplicate to MultiwayMerge
(and perhaps cache the
duplicate in between calls).
See Also
merge
for an analogous function that
takes a static number of ranges of possibly disparate types.
Example
import std .algorithm .comparison : equal;
double[][] a =
[
[ 1, 4, 7, 8 ],
[ 1, 7 ],
[ 1, 7, 8],
[ 4 ],
[ 7 ],
];
auto witness = [
1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8
];
assert(equal(multiwayMerge(a), witness));
double[][] b =
[
// range with duplicates
[ 1, 1, 4, 7, 8 ],
[ 7 ],
[ 1, 7, 8],
[ 4 ],
[ 7 ],
];
// duplicates are propagated to the resulting range
assert(equal(multiwayMerge(b), witness));