Report a bug

If you spot a problem with this page, click here to create a Github 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
a local clone.

# mir.algorithm.setops

This is a submodule of mir.algorithm. It contains nothrow @nogc BetterC alternative to MultiwayMerge from std.algorithm.

`setops`

.
License:

Authors:

Andrei Alexandrescu (original Phobos code), Ilya Yaroshenko (Mir & BetterC rework, optimization).

- struct
`MultiwayMerge`

(alias less, RangeOfRanges);

MultiwayMerge!(naryFun!less, RangeOfRanges)`multiwayMerge`

(alias less = "a < b", RangeOfRanges)(RangeOfRanges`ror`

); - 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. 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:less Predicate the given ranges are sorted by. RangeOfRanges `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).Examples:import std.algorithm.comparison : equal; static a = [ [ 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 8], [ 4 ], [ 7 ], ]; static witness = [ 1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8 ]; assert(a.multiwayMerge.equal(witness)); static b = [ // range with duplicates [ 1, 1, 4, 7, 8 ], [ 7 ], [ 1, 7, 8], [ 4 ], [ 7 ], ]; // duplicates are propagated to the resulting range assert(b.multiwayMerge.equal(witness));

- this();
- static bool
`compFront`

(ElementType!RangeOfRanges`a`

, ElementType!RangeOfRanges`b`

); - BinaryHeap!(compFront, RangeOfRanges)
`_heap`

; - Heap
- this(RangeOfRanges
`ror`

); - const @property scope bool
`empty`

(); - @property ref auto
`front`

(); - scope @safe void
`popFront`

();

- auto
`multiwayUnion`

(alias less = "a < b", RangeOfRanges)(RangeOfRanges`ror`

); - Computes the union of multiple ranges. The input ranges 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.
`multiwayUnion`

(`ror`

) is functionally equivalent to multiwayMerge(`ror`

).uniq. "The output of`multiwayUnion`

has no duplicates even when its inputs contain duplicates."Parameters:less Predicate the given ranges are sorted by. RangeOfRanges `ror`

A range of ranges sorted by less to compute the intersection for. Returns:A range of the union of the ranges in`ror`

. See also: multiwayMergeExamples:import std.algorithm.comparison : equal; // sets double[][] a = [ [ 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 8], [ 4 ], [ 7 ], ]; auto witness = [1, 4, 7, 8]; assert(a.multiwayUnion.equal(witness)); // multisets double[][] b = [ [ 1, 1, 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 7, 8], [ 4 ], [ 7 ], ]; assert(b.multiwayUnion.equal(witness));

- size_t
`unionLength`

(alias less = "a < b", RangeOfRanges)(RangeOfRanges`ror`

); - Computes the length of union of multiple ranges. The input ranges are passed as a range of ranges and each is assumed to be sorted by less.Parameters:
less Predicate the given ranges are sorted by. RangeOfRanges `ror`

A range of ranges sorted by less to compute the intersection for. Returns:A length of the union of the ranges in`ror`

.

Copyright © 1999-2019 by the D Language Foundation | Page generated by
Ddoc on Wed May 22 12:05:40 2019