Menu
Search

API Documentation

version 2.080.0

overview

View source code
Display the source code in std/algorithm/setops.d from which this page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

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.length)). 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.length * log(ror.length)), i.e., log(ror.length) times worse than just spanning all ranges in turn. The output comes sorted (unstably) by less.

MultiwayMerge!(less,RangeOfRanges) multiwayMerge(alias less, RangeOfRanges) (
  RangeOfRanges ror
);

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

NameDescription
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).

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.length)). 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.length * log(ror.length)), i.e., log(ror.length) 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

NameDescription
this

Properties

NameTypeDescription
empty[get] bool
front[get] auto

Methods

NameDescription
compFront
popFront

Parameters

NameDescription
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).

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));

Authors

Andrei Alexandrescu

License

Boost License 1.0.