std.algorithm.setops

auto cartesianProduct(R1, R2)(R1 range1, R2 range2)
if (!allSatisfy!(isForwardRange, R1, R2) || anySatisfy!(isInfinite, R1, R2));

auto cartesianProduct(RR...)(RR ranges)
if (ranges.length >= 2 && allSatisfy!(isForwardRange, RR) && !anySatisfy!(isInfinite, RR));

auto cartesianProduct(R1, R2, RR...)(R1 range1, R2 range2, RR otherRanges)
if (!allSatisfy!(isForwardRange, R1, R2, RR) || anySatisfy!(isInfinite, R1, R2, RR));

Лениво вычисляет декартово произведение двух или больше диапазонов. Произведение является диапазоном кортежей элементов из каждого соответствующего диапазона.

Условия для двух-рангового случая следующие:

Если оба диапазона конечные, тогда один должен быть (по крайней мере) лидирующим диапазоном и другой входным диапазоном.

Если один диапазон бесконечный, а другой конечный, тогда конечный диапазон должен быть лидирующим диапазоном, а бесконечный диапазон может быть входным дипазоном.

Если оба диапазона бесконечные, тогда оба должны быть лидирующими диапазонами.

Когда присутсвует больше двух диапазонов, вышеуказанные условия относятся к каждой смежной паре диапазонов.

Параметры:

R1 range1	Первый диапазон
R2 range2	Второй диапазон
RR ranges	Два или больше не-бесконечных лидирующих диапазона
RR otherRanges	Ноль или больше не-бесконечных лидирующих диапазона

Возвращает:

Лидирующий диапазон std.typecons.Tuple , представляющий элементы декартового прозведения заданных диапазонов.

Примеры:

import std.algorithm.searching : canFind;
import std.range;
import std.typecons : tuple;

auto N = sequence!"n"(0);         // Диапазон натуральных чисел
auto N2 = cartesianProduct(N, N); // диапазон всех пар натуральных чисел

// Различные произвольные пары чисел можно найти в диапазоне за конечное время.
assert(canFind(N2, tuple(0, 0)));
assert(canFind(N2, tuple(123, 321)));
assert(canFind(N2, tuple(11, 35)));
assert(canFind(N2, tuple(279, 172)));

Примеры:

import std.algorithm.searching : canFind;
import std.typecons : tuple;

auto B = [ 1, 2, 3 ];
auto C = [ 4, 5, 6 ];
auto BC = cartesianProduct(B, C);

foreach (n; [[1, 4], [2, 4], [3, 4], [1, 5], [2, 5], [3, 5], [1, 6],
             [2, 6], [3, 6]])
{
    assert(canFind(BC, tuple(n[0], n[1])));
}

Примеры:

import std.algorithm.comparison : equal;
import std.typecons : tuple;

auto A = [ 1, 2, 3 ];
auto B = [ 'a', 'b', 'c' ];
auto C = [ "x", "y", "z" ];
auto ABC = cartesianProduct(A, B, C);

assert(ABC.equal([
    tuple(1, 'a', "x"), tuple(1, 'a', "y"), tuple(1, 'a', "z"),
    tuple(1, 'b', "x"), tuple(1, 'b', "y"), tuple(1, 'b', "z"),
    tuple(1, 'c', "x"), tuple(1, 'c', "y"), tuple(1, 'c', "z"),
    tuple(2, 'a', "x"), tuple(2, 'a', "y"), tuple(2, 'a', "z"),
    tuple(2, 'b', "x"), tuple(2, 'b', "y"), tuple(2, 'b', "z"),
    tuple(2, 'c', "x"), tuple(2, 'c', "y"), tuple(2, 'c', "z"),
    tuple(3, 'a', "x"), tuple(3, 'a', "y"), tuple(3, 'a', "z"),
    tuple(3, 'b', "x"), tuple(3, 'b', "y"), tuple(3, 'b', "z"),
    tuple(3, 'c', "x"), tuple(3, 'c', "y"), tuple(3, 'c', "z")
]));

void largestPartialIntersection(alias less = "a < b", RangeOfRanges, Range)(RangeOfRanges ror, Range tgt, SortOutput sorted = No.sortOutput);

Дан диапазон отсортированных лидирующих диапазонов ror, копирует в tgt элементы, которые являются общими для большинства диапазонов, вместе с количеством их вхождений. Предполагается, что все диапазоны в ror были отсортированы в соответсвии с предикатом less. Возвращается только tgt.length наиболее частых элементов.

Параметры:

less	Предикат, в соответствии с которым отсортированы диапазоны.
RangeOfRanges ror	Диапазон лидирующих диапазонов, отсортированных в соответсвии с less.
Range tgt	Целевой диапазон, куда копируются общие элементы.
SortOutput sorted	Должны ли скопированные элементы быть отсортированы.

Функция largestPartialIntersection полезна, например, для поиска инвертированного индекса документов, с наибольшей вероятностью содержащих некоторые термины, представляющие интерес. Сложность поиска – Ο(n * log(tgt.length)), где n – сумма длин всех входных диапазонов. Этот метод быстрее, чем хранение ассоциативного массива появлений, и затем выбора его верхних элементов и также требует меньше памяти (largestPartialIntersection строит свой результат непосредственно в tgt и не требует никакой дополнительной памяти).

Warning: Поскольку largestPartialIntersection не распределяет дополнительную память, она оставит ror изменённым. А именно: largestPartialIntersection берет на себя владение ror и по своему усмотрению меняет и продвигает его элементы. Если вы хотите, чтобы ror сохранил свое содержание после вызова, вы можете передать дубликат largestPartialIntersection (и, возможно, кешировать дубликат между вызовами).

Примеры:

import std.typecons : tuple, Tuple;

// Картинка, числа которой можно встретить в большинстве 
// примеров со множествами ниже.
double[][] a =
[
    [ 1, 4, 7, 8 ],
    [ 1, 7 ],
    [ 1, 7, 8],
    [ 4 ],
    [ 7 ],
];
auto b = new Tuple!(double, uint)[1];
// это изменит входной диапазон, следовательно нам нужно создать дубликат
largestPartialIntersection(a.dup, b);
// Первый член является элементом, второй - количеством вхождений
assert(b[0] == tuple(7.0, 4u));
// 7.0 встречается в 4 входах из 5, больше, чем любое другое число

// Если нужно больше самых частых чисел , просто создайте больший
// диапазон tgt
auto c = new Tuple!(double, uint)[2];
largestPartialIntersection(a, c);
assert(c[0] == tuple(1.0, 3u));
// 1.0 встречается в 3 входах

void largestPartialIntersectionWeighted(alias less = "a < b", RangeOfRanges, Range, WeightsAA)(RangeOfRanges ror, Range tgt, WeightsAA weights, SortOutput sorted = No.sortOutput);

Подобно largestPartialIntersection, но ассоциирует вес с каждым отдельным элементом в пересечении.

Параметры:

less	Предикат, в соответствии с которым отсортированы диапазоны.
RangeOfRanges ror	Диапазон лидирующих диапазонов, отсортированных в соответсвии с less.
Range tgt	Целевой диапазон, куда копируются общие элементы.
WeightsAA weights	Ассоциативный массив, отображающий элементы в вес.
SortOutput sorted	Должны ли скопированные элементы быть отсортированы.

Примеры:

import std.typecons : tuple, Tuple;

// Картинка, числа которой можно встретить в большинстве
// примеров со множествами ниже, с удельным весом на элемент
double[][] a =
[
    [ 1, 4, 7, 8 ],
    [ 1, 7 ],
    [ 1, 7, 8],
    [ 4 ],
    [ 7 ],
];
auto b = new Tuple!(double, uint)[1];
double[double] weights = [ 1:1.2, 4:2.3, 7:1.1, 8:1.1 ];
largestPartialIntersectionWeighted(a, b, weights);
// Первый член является элементом, второй - количеством вхождений
assert(b[0] == tuple(4.0, 2u));
// 4.0 встречается 2 раза -> 4.6 (2 * 2.3)
// 7.0 встречается в 3 раза -> 4.4 (3 * 1.1)

Переместиться к: compFront · empty · front · popFront · this

struct NWayUnion(alias less, RangeOfRanges);

NWayUnion!(less, RangeOfRanges) nWayUnion(alias less = "a < b", RangeOfRanges)(RangeOfRanges ror);

Вычисляет объединение нескольких множеств. Входные множества передаются как диапазон диапазонов, и принимается, что каждый отсортирован в соотвествии с предикатом less. Вычисление выполняется лениво, один элемент объединения за один раз. Сложность одной операции popFront – Ο(log(ror.length)). Тем не менее, длина ror уменьшается по мере исчерпания диапазонов, так что сложность полного прохода через NWayUnion зависит от распределения длин диапазонов, содержащихся в ror. Если все диапазоны имеют одинаковую длину n (неблагоприятный сценарий), сложность полного прохода через NWayUnion – Ο(n * ror.length * log(ror.length)), то есть, в log(ror.length) раз хуже, чем просто пройти по всем диапазонам по очереди. Результат на выходе получается отсортированный (unstably) в соотвествии с less.

Параметры:

less	Предикат, в соответствии с которым отсортированы диапазоны.
RangeOfRanges ror	Диапазон диапазонов, отсортированных в соответсвии с less , для вычисления объединения.

Возвращает:

Диапазон с объединением диапазонов в ror.

Warning: Поскольку NWayUnion не распределяет дополнительную память, он оставит ror модифицированным. А именно: NWayUnion берет на себя владение ror и по своему усмотрению меняет и продвигает его элементы. Если вы хотите, чтобы ror сохранил свое содержание после вызова, вы можете передать дубликат на NWayUnion (и, возможно, кешировать дубликат между вызовами).

Примеры:

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(nWayUnion(a), witness));

static bool compFront(.ElementType!RangeOfRanges a, .ElementType!RangeOfRanges b);

this(RangeOfRanges ror);

@property bool empty();

@property ref auto front();

void popFront();

Переместиться к: empty · front · popFront · save · this

struct SetDifference(alias less = "a < b", R1, R2) if (isInputRange!R1 && isInputRange!R2);

SetDifference!(less, R1, R2) setDifference(alias less = "a < b", R1, R2)(R1 r1, R2 r2);

Лениво вычисляет разницу между r1 и r2. Принимается, что два диапазона отсортированы в соотвествии с предикатом less. Типы элементов двух диапазонов должны иметь общий тип.

Параметры:

less	Предикат, в соответствии с которым отсортированы диапазоны.
R1 r1	Первый диапазон.
R2 r2	Диапазон, вычитаемый из r1.

Возвращает:

Диапазон, представляющий разницу между r1 и r2.

Смотрите также:

setSymmetricDifference

Примеры:

import std.algorithm.comparison : equal;
import std.range.primitives : isForwardRange;

int[] a = [ 1, 2, 4, 5, 7, 9 ];
int[] b = [ 0, 1, 2, 4, 7, 8 ];
assert(equal(setDifference(a, b), [5, 9][]));
static assert(isForwardRange!(typeof(setDifference(a, b))));

this(R1 r1, R2 r2);

void popFront();

@property ref auto front();

@property typeof(this) save();

@property bool empty();

Переместиться к: empty · front · popFront · save · this

struct SetIntersection(alias less = "a < b", Rs...) if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void));

SetIntersection!(less, Rs) setIntersection(alias less = "a < b", Rs...)(Rs ranges)
if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void));

Лениво вычисляет пересечение двух или более входных диапазонов ranges. Принимается, что диапазоны отсортированы в соотвествии с предикатом less. Типы элементов диапазонов должны иметь общий тип.

Параметры:

less	Предикат, в соответствии с которым отсортированы диапазоны.
Rs ranges	Диапазоны, у которых будет вычисляться пересечение.

Возвращает:

Диапазон, содержащий пересечение данных диапазонов.

Примеры:

import std.algorithm.comparison : equal;

int[] a = [ 1, 2, 4, 5, 7, 9 ];
int[] b = [ 0, 1, 2, 4, 7, 8 ];
int[] c = [ 0, 1, 4, 5, 7, 8 ];
assert(equal(setIntersection(a, a), a));
assert(equal(setIntersection(a, b), [1, 2, 4, 7]));
assert(equal(setIntersection(a, b, c), [1, 4, 7]));

this(Rs input);

@property bool empty();

void popFront();

@property ElementType front();

@property SetIntersection save();

Переместиться к: empty · front · opSlice · popFront · save · this

struct SetSymmetricDifference(alias less = "a < b", R1, R2) if (isInputRange!R1 && isInputRange!R2);

SetSymmetricDifference!(less, R1, R2) setSymmetricDifference(alias less = "a < b", R1, R2)(R1 r1, R2 r2);

Лениво вычисляет симметричную разницу между r1 и r2, то есть элементы, которые присутствуют в точности только в одном из диапазонов r1 или r2. Принимается, что два диапазона отсортированы в соотвествии с предикатом less, и выход отсортирован также. Типы элементов двух диапазонов должны иметь общий тип.

Если оба аргумента – диапазоны L-values одного и того же типа, тогда SetSymmetricDifference также будет диапазоном L-values этого типа.

Параметры:

less	Предикат, в соответствии с которым отсортированы данные диапазоны.
R1 r1	Первый диапазон.
R2 r2	Второй диапазон.

Возвращает:

Диапазон с симметричной разницей между r1 и r2.

Смотрите также:

setDifference

Примеры:

import std.algorithm.comparison : equal;
import std.range.primitives : isForwardRange;

int[] a = [ 1, 2, 4, 5, 7, 9 ];
int[] b = [ 0, 1, 2, 4, 7, 8 ];
assert(equal(setSymmetricDifference(a, b), [0, 5, 8, 9][]));
static assert(isForwardRange!(typeof(setSymmetricDifference(a, b))));

this(R1 r1, R2 r2);

void popFront();

@property ref auto front();

@property typeof(this) save();

ref auto opSlice();

@property bool empty();