D 2.0
About Japanese Translation

Last update Sun Dec 19 23:27:22 2010

std.algorithm

主としてデータ列のさまざまな処理を目的としたアルゴリズムを実装しています。 いくつかの関数は、C++ の Alexander Stepanov による Standard Template Library の algorithm ヘッダ の同名の関数に由来しており、同等もしくはより汎用的な機能を持っています。

Source:
std/algorithm.d

License:
Boost License 1.0

Authors:
Andrei Alexandrescu

Note:
このモジュールの多くの関数が、関数や 述語 でパラメタ化されています。 述語としては、関数名かデリゲート名、 ファンクタ名、 コンパイル時文字列のいずれかを指定することができます。文字列で指定する場合、 第一引数を a、第二引数を b とした任意のD言語の式で 関数の内容を記述することが可能です。これらの引数は別のコンテキストで評価されるため、 ユーザーコード内の同名のシンボルと混同されることはありません。 バイナリ比較述語のデフォルトとしては、 等価比較の場合は "a == b"、順序比較の場合は "a < b" が使用されます。

Example:
int[] a = ...;
static bool greater(int a, int b)
{
    return a > b;
}
sort!(greater)(a);  // alias で述語を指定
sort!("a > b")(a);  // 文字列で述語を指定
                    // (配列名と混同されることはない)
sort(a);            // 述語無し。デフォルトの "a < b"

Map!(adjoin!(staticMap!(unaryFun, fun)), Range) map(fun..., Range)(Range r)
多くの関数型言語に存在する同名の関数 (transform としても知られる) の実装です。map!(fun)(range) を呼び出すと、左から右に range 内の x に関数を適用した結果 fun(x) を並べたレンジが結果として得られます。引数として与えられたレンジは変更されません。 評価は遅延評価的に行われます。map の返すレンジは最後に評価した値をキャッシュし、複数回 front を呼んでも fun は一度しか呼び出されません。

Example:
int[] arr1 = [ 1, 2, 3, 4 ];
int[] arr2 = [ 5, 6 ];
auto squares = map!("a * a")(chain(arr1, arr2));
assert(equal(squares, [ 1, 4, 9, 16, 25, 36 ]));
複数の関数を map に渡すことも可能です。 この場合、map 結果のレンジの要素は、 各々の関数の適用結果を並べたタプルになります。

Example:
auto arr1 = [ 1, 2, 3, 4 ];
foreach (e; map!("a + a", "a * a")(arr1))
{
    writeln(e[0], " ", e[1]);
}
map のインスタンスを、個別にaliasして使うのも良いでしょう: 
alias map!(to!string) stringize;
assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ]));

E reduce(fun...,E,R)(E result, R r)
多くの関数型言語に存在する同名の関数 (accumulate, compress, inject, foldl, などとしても知られる) の実装です。reduce!(fun)(seed, range) を呼び出すと、まず「アキュムレータ」と呼ばれる内部変数 result に seed を設定し、range の各要素 x について、result = fun(result, x) が実行されます。最終的には、result が返されます。一引数バージョン reduce!(fun)(range) も同様の動作をしますが、 seed として range の第一要素を使います（rangeは非空である必要があります)。

レンジに対する多くの操作が、 比較的簡単に reduce によって実現できます。以下の例は、 reduce の表現力と柔軟性をよく表しています。

Example:
int[] arr = [ 1, 2, 3, 4, 5 ];
// 総和の計算
auto sum = reduce!("a + b")(0, arr);
assert(sum == 15);

// 全ての要素の最大値を計算
auto largest = reduce!(max)(arr);
assert(largest == 5);

// 奇数の個数をカウント
auto odds = reduce!("a + (b & 1)")(0, arr);
assert(odds == 3);

// 二乗の総和の計算
auto ssquares = reduce!("a + b * b")(0, arr);
assert(ssquares == 55);

// 複数のレンジをひとつのseedから始めて繋いで処理
int[] a = [ 3, 4 ];
int[] b = [ 100 ];
auto r = reduce!("a + b")(chain(a, b));
assert(r == 107);

// 変換可能な型のレンジならば混ぜて使うことも可能
double[] c = [ 2.5, 3.0 ];
auto r1 = reduce!("a + b")(chain(a, b, c));
assert(r1 == 112.5);
複数の関数:
しばしば、複数の集計を１パスで実行できると便利なことがあります。特に、ループのオーバーヘッドを共有することで 計算が高速化することが期待できます。このため、 reduce では複数の関数を受け取ることができます。２個以上の関数が渡された場合、 reduce はそれぞれの関数による結果を順に並べた std.typecons.Tuple オブジェクトを返します。指定する seed の個数を増やす必要があることに注意してください。

Example:
double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ];
// 最小値と最大値を１パスで計算
auto r = reduce!(min, max)(a);
// The type of r is Tuple!(double, double)
assert(r[0] == 2);  // 最小値
assert(r[1] == 11); // 最大値

// 総和と二乗の総和を１パスで計算
r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a);
assert(r[0] == 35);  // 総和
assert(r[1] == 233); // 二乗の総和
// これを使って平均値と分散を計算
auto avg = r[0] / a.length;
auto stdev = sqrt(r[1] / a.length - avg * avg);

void fill(Range, Value)(Range range, Value filler);
レンジを値valueで埋めます。

Example:
int[] a = [ 1, 2, 3, 4 ];
fill(a, 5);
assert(a == [ 5, 5, 5, 5 ]);

void fill(Range1, Range2)(Range1 range, Range2 filler);
レンジ range を、別のレンジfiller からコピーした値で埋めます。 range の長さは filler の倍数でなくても構いません。filler が空の場合は例外が飛びます。

Example:
int[] a = [ 1, 2, 3, 4, 5 ];
int[] b = [ 8, 9 ];
fill(a, b);
assert(a == [ 8, 9, 8, 9, 8 ]);

void uninitializedFill(Range, Value)(Range range, Value filler);
レンジを値で埋めます。 レンジにはまだ意味のある内容が入っていないことを仮定します。 これはコピーコンストラクタを定義した構造体に関してのみ意味があります。(他の全ての型では、 fill と uninitializedFill は同じです)

Example:
struct S { ... }
S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5];
uninitializedFill(s, 42);
assert(s == [ 42, 42, 42, 42, 42 ]);

void initializeAll(Range)(Range range);
レンジの全ての要素をその型の .init の値で埋めます。 レンジにはまだ意味のある内容が入っていないことを仮定します。

Example:
struct S { ... }
S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5];
initialize(s);
assert(s == [ 0, 0, 0, 0, 0 ]);

Filter!(unaryFun!(pred),Range) filter(alias pred, Range)(Range rs);
多くの関数型言語に存在する同名の関数（別名: select等）の実装です。 filter!(fun)(range) を呼び出すと、range 内の x のうち pred(x) が true となるものだけを含んだ新しいレンジを返します。

Example:
int[] arr = [ 1, 2, 3, 4, 5 ];
// 3より小さいもの
auto small = filter!("a < 3")(arr);
assert(small == [ 1, 2 ]);
// chain() と組み合わせて複数のレンジを繋ぐ
int[] a = [ 3, -2, 400 ];
int[] b = [ 100, -101, 102 ];
auto r = filter!("a > 0")(chain(a, b));
assert(equal(r, [ 3, 400, 100, 102 ]));
// 変換可能なレンジを混ぜて使うことも可能
double[] c = [ 2.5, 3.0 ];
auto r1 = filter!("cast(int) a != a")(chain(c, a, b));
assert(r1 == [ 2.5 ]);

void move(T)(ref T source, ref T target);
T move(T)(ref T src);
破壊的コピーによってsource を target に移動します。 特に:
  • hasAliasing!(T) が true(see std.traits.hasAliasing) の時、 source はビット毎に target にコピーされ、source = T.init が実行されます。
  • それ以外の場合では、target = source が実行されます。
参照: std.exception.pointsTo

Preconditions:
&source == &target || !pointsTo(source, source)

Range2 moveAll(Range1, Range2)(Range1 src, Range2 tgt);
レンジ src の要素 a と tgt の要素 b について、先頭から順に move(a, b) を呼び出します。 返値は tgt に残った部分のレンジです。 tgt の方が src より短いと例外が飛びます。

Preconditions:
walkLength(src) >= walkLength(tgt)

Tuple!(Range1,Range2) moveSome(Range1, Range2)(Range1 src, Range2 tgt);
レンジ src の要素 a と tgt の要素 b について、先頭から順に move(a, b) を呼び出します。 src と tgt のどちらかが終端に達すると終了し、双方の残った部分のレンジを返します。

void swap(T)(ref T lhs, ref T rhs);
lhs と rhs をswapします。std.contracts.pointsTo 参照。

Preconditions:
!pointsTo(lhs, lhs) && !pointsTo(lhs, rhs) && !pointsTo(rhs, lhs) && !pointsTo(rhs, rhs)

struct Splitter(Range,Separator) if (is(typeof(Range.init.front == Separator.init.front)));
Splitter!(Range,Separator) splitter(Range, Separator)(Range r, Separator s);
レンジを、要素を指定して分割します。 任意のレンジに対して使用できますが、特に文字列に対して使われることが多い機能です。

セパレータが２つ並んでいる場合は空列を１つ囲っているものと解釈されます。

空のレンジが渡された場合、結果は一つの空要素を持つレンジになります。 セパレータ１だけでできたレンジが渡された場合は、 空要素を二つ持つレンジが答えです。 Example:
assert(equal(splitter("hello  world", ' '), [ "hello", "", "world" ]));
int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
int[][] w = [ [1, 2], [], [3], [4, 5] ];
assert(equal(splitter(a, 0), w));
a = null;
assert(equal(splitter(a, 0), [ (int[]).init ]));
a = [ 0 ];
assert(equal(splitter(a, 0), [ (int[]).init, (int[]).init ]));
a = [ 0, 1 ];
assert(equal(splitter(a, 0), [ [], [1] ]));

struct Uniq(alias pred,R);
Uniq!(pred,Range) uniq(alias pred = "a == b", Range)(Range r);
与えられたレンジの、連続する同値な部分をひとまとめにして列挙します。（機能としては uniq コマンドに似ています）。 同値性は、述語 pred によって指定します。デフォルトは "a == b" です。 元のレンジが双方向レンジならば、uniq 結果も双方向レンジになります。

Example:
int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));

struct Group(alias pred,R) if (isInputRange!(R));
Group!(pred,Range) group(alias pred = "a == b", Range)(Range r);
uniq 同様、group も連続する同値な要素をひとまとめにして列挙します。 ただし、返す要素型は Tuple!(ElementType!R, uint) で、 まとめた要素の個数を持つようになっています。 同値性は述語 pred で指定し、デフォルトは "a == b" です。

R が入力レンジならば Group も入力レンジで、それ以外では前進レンジになります。

Example:
int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u),
    tuple(4, 3u), tuple(5, 1u) ][]));

R find(alias pred = "a == b", R, E)(R haystack, E needle);
入力レンジから個別の要素を探します。haystack の各要素が needle と、述語 pred で比較されます。Ο(walkLength(haystack)) 回 pred を評価します。STL の find 参照。

needle の haystack での最後の出現を探すには、 find(retro(haystack), needle) を使います。std.range.retro 参照のこと。

Parameters:
haystack 検索対象のレンジ
needle 検索する要素

Constraints:
isInputRange!R && is(typeof(binaryFun!pred(haystack.front, needle) : bool))

Returns:
haystack が binaryFun!pred(haystack.front, needle) が true を返すまで進みます。 (そのような位置がなければ、haystack は最後まで進みます)

Example:
assert(find("hello, world", ',') == ", world");
assert(find([1, 2, 3, 5], 4) == []);
assert(find(SList!int(1, 2, 3, 4, 5)[], 4) == SList!int(4, 5)[]);
assert(find!"a > b"([1, 2, 3, 5], 2) == [3, 5]);

auto a = [ 1, 2, 3 ];
assert(find(a, 5).empty);       // not found
assert(!find(a, 2).empty);      // 発見

// 大文字小文字の違いを無視する文字列サーチ
string[] s = [ "Hello", "world", "!" ];
assert(!find!("tolower(a) == b")(s, "hello").empty);

R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle);
あるレンジの中から、別の前進レンジを探します。要素ごとの等値性で比較が行われます。 Ο(walkLength(haystack) * walkLength(needle)) 回の比較を最悪の場合実行します。 双方向、あるいはランダムアクセスレンジの利点を活かした特殊化によって、 二つのレンジの内容の分布によっては高速化が行われる可能性があります。

Parameters:
haystack このレンジの中から検索
needle このレンジの出現を探す

Constraints:
isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front) : bool))

Returns:
haystack が、needle がその接頭辞になるまで進んだものを返します、。(そのような位置がなければ、 haystack が空になるまで進みます) 

assert(find("hello, world", "World").empty);
assert(find("hello, world", "wo") == "world");
assert(find([1, 2, 3, 4], SList!(2, 3)[]) == [2, 3, 4]);

Tuple!(Range,size_t) find(alias pred = "a == b", Range, Ranges...)(Range haystack, Ranges needles);
struct BoyerMooreFinder(alias pred,Range);
BoyerMooreFinder!(binaryFun!(pred),Range) boyerMooreFinder(alias pred = "a == b", Range)(Range needle);
２個かそれ以上の needles を haystack の中から探します。述語 pred を使って要素を比較します。デフォルトでは、 == で同値性を比較します。

Parameters:
haystack 検索対象のレンジ。 入力レンジ をしてします。needles の内ひとつでも haystackの要素と比較可能な要素を持つレンジであれば、haystack は、バックトラックを可能とするために 前進レンジ でなければなりません。
needles 一つ以上の、検索したい要素。needles の要素それぞれとしては、haystack の要素と比較可能な値か、 またはそれ自身が比較可能な要素を持つ 前進レンジ を渡すことができます。

Returns:
haystack がどれかのneedleとマッチした位置まで進んだレンジと、 マッチした要素の needles での1-baseのインデックスの組を返します (0 は needles のどの要素もマッチしなかったことを、1 は needles[0] がマッチしたこと、2 は needles[1] ... を意味します)

haystack と needles の関係は、 int の配列に対して、個々の int を探すことも、int の配列を探すこともできる、ということです。 さらに、比較可能でさえあれば、違う型の needles でも検索をかけられます。 例えば、double[] に対して int や short[] で検索したり、long[] に対して float や double[] の検索を実行できます。これによって、 わざわざ片方の型をキャストで他方に揃えるなどの必要なく、効率的な検索が行えます。

Example:
int[] a = [ 1, 4, 2, 3 ];
assert(find(a, 4) == [ 4, 2, 3 ]);
assert(find(a, [ 1, 4 ]) == [ 1, 4, 2, 3 ]);
assert(find(a, [ 1, 3 ], 4) == tuple([ 4, 2, 3 ], 2));
// 多種の型を混ぜて良い
assert(find(a, 5, [ 1.2, 3.5 ], 2.0, [ 1 ]) == tuple([ 2, 3 ], 3));
検索の計算量は Ο(haystack.length * max(needles.length)) です。(単一要素を指定した needle については、 length は 1 とします)。複数のneedleを検索する際には、 haystack 上の移動を最小化するために、キャッシュを最大限活用する方針で検索が実装されています。
Range find(alias pred, Range)(Range haystack);
入力レンジ haystack に対し haystack.popFront を繰り返し呼び出し、pred(haystack.front) または haystack.empty となったところで停止します。Ο(haystack.length) 回 pred を呼び出します。STL の find_if 参照。

双方向レンジ haystack の pred を満たす最後の要素を取得するには、find!(pred)(retro(haystack)) を使います。std.range.retro 参照。

Example:
auto arr = [ 1, 2, 3, 4, 1 ];
assert(find!("a > 2")(arr) == [ 3, 4, 1 ]);

// 述語aliasで
bool pred(int x) { return x + 1 > 1.5; }
assert(find!(pred)(arr) == arr);

sizediff_t indexOf(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle);
haystack がスライシング可能な場合、n haystack[n .. $].startsWith!pred(needle) が成り立つ最小の n を返します。 それ以外の場合は、n 回 haystack.popFront を呼ぶと haystack.startsWith!pred(needle) になる最小の n を返します。 そのような数がないときは、-1 を返します。

enum OpenRight;
until (下参照) 他で使う、区間のオプション指定です。

no
右端は閉じた区間とする（最後の要素を含む）

yes
右端は開いた区間とする（最後の要素を含まない）

struct Until(alias pred,Range,Sentinel) if (isInputRange!(Range));
Until!(pred,Range,Sentinel) until(alias pred = "a == b", Range, Sentinel)(Range range, Sentinel sentinel, OpenRight openRight = OpenRight.yes);
Until!(pred,Range,void) until(alias pred, Range)(Range range, OpenRight openRight = OpenRight.yes);
range 上をループし、sentinel が見つかったところで停止します。

Example:
int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5];
assert(equal(a.until(7), [1, 2, 4][]));
assert(equal(a.until(7, OpenRight.no), [1, 2, 4, 7][]));

uint startsWith(alias pred = "a == b", Range, Ranges...)(Range doesThisStart, Ranges withOneOfThese);
bool startsWith(alias pred = "a == b", R1, R2)(R1 doesThisStart, R2 withThis);
bool startsWith(alias pred = "a == b", R, E)(R doesThisStart, E withThis);
レンジ doesThisStart が withOneOfThese に含まれるレンジのいずれかで始まっているかをチェックします。withOneOfThese[0] で始まっていれば1、withOneOfThese[1] ならば2、等々を返します。 どれともマッチしなければ 0 を返します。

Example:
assert(startsWith("abc", ""));
assert(startsWith("abc", "a"));
assert(!startsWith("abc", "b"));
assert(startsWith("abc", 'a', "b") == 1);
assert(startsWith("abc", "b", "a") == 2);
assert(startsWith("abc", "a", "a") == 1);
assert(startsWith("abc", "x", "a", "b") == 2);
assert(startsWith("abc", "x", "aa", "ab") == 3);
assert(startsWith("abc", "x", "aaa", "sab") == 0);
assert(startsWith("abc", "x", "aaa", "a", "sab") == 3);

bool skipOver(alias pred = "a == b", R1, R2)(ref R1 r1, R2 r2);
startsWith(r1, r2) ならば、r1 を対応する部分を飛ばすだけ進めて、true を返します。そうでなければ、r1 は変えずに false を返します。

bool skipOver(alias pred = "a == b", R, E)(ref R r, E e);
レンジが指定の要素で始まるかどうかを調べ、そうであれば、 その要素を消費して r を進め、true を返します。そうでなければ、r は変えずにfalse を返します。

uint endsWith(alias pred = "a == b", Range, Ranges...)(Range doesThisEnd, Ranges withOneOfThese);
startsWith の逆バージョンです。

Example:
assert(endsWith("abc", ""));
assert(!endsWith("abc", "b"));
assert(endsWith("abc", "a", 'c') == 2);
assert(endsWith("abc", "c", "a") == 1);
assert(endsWith("abc", "c", "c") == 1);
assert(endsWith("abc", "x", "c", "b") == 2);
assert(endsWith("abc", "x", "aa", "bc") == 3);
assert(endsWith("abc", "x", "aaa", "sab") == 0);
assert(endsWith("abc", "x", "aaa", 'c', "sab") == 3);

uint endsWith(alias pred = "a == b", Range, Elements...)(Range doesThisEnd, Elements withOneOfThese);
doesThisEnd が withOneOfThese に含まれる要素のどれかで終わるかどうかを調べます（比較は predを使います）

Example:
assert(endsWith("abc", 'x', 'c', 'a') == 2);

Range findAdjacent(alias pred = "a == b", Range)(Range r);
r を、隣り合った要素 a と b で pred(a, b) を満たすものが見つかるまで進めます。Ο(r.length) 回 pred を呼び出します。参照: STL の adjacent_find

Example:
int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
auto r = findAdjacent(a);
assert(r == [ 10, 10, 9, 8, 8, 7, 8, 9 ]);
p = findAdjacent!("a < b")(a);
assert(p == [ 7, 8, 9 ]);

Range1 findAmong(alias pred = "a == b", Range1, Range2)(Range1 seq, Range2 choices);
seq に対し seq.popFront を繰り返し呼び出し、find!(pred)(choices, seq.front) が true になるか seq が空になったところで止まります。Ο(seq.length * choices.length) 回 pred を呼び出します。参照： STL の find_first_of

Example:
int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
int[] b = [ 3, 1, 2 ];
assert(findAmong(a, b) == a[2 .. $]);

size_t count(alias pred = "true", Range, E)(Range r, E value);
r 内の要素 x で、pred(x, value) が true になるものの個数を数えます。pred は == による比較がデフォルトです。Ο(r.length) 回 pred を呼び出します。

Example:
int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
assert(count(a, 2) == 3);
assert(count!("a > b")(a, 2) == 5);

size_t count(alias pred, Range)(Range r);
r 内の要素 x で、pred(x) が true になるものの個数を数えます。Ο(r.length) 回 pred を呼び出します。

Example:
int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
assert(count!("a > 1")(a) == 8);

bool balancedParens(Range, E)(Range r, E lPar, E rPar, size_t maxNestingLevel = size_t.max);
r の中の"括弧がバランスしているか"、つまり、 lPar の全ての要素の出現が対応する rPar の要素で閉じられているかをチェックします。 パラメタ maxNestingLevel は許容するネストの深さを制御します。 典型的な使用ケースは、デフォルトか、0 を指定します。 後者の場合ネストは一切許されません。

Example:
auto s = "1 + (2 * (3 + 1 / 2)";
assert(!balancedParens(s, '(', ')'));
s = "1 + (2 * (3 + 1) / 2)";
assert(balancedParens(s, '(', ')'));
s = "1 + (2 * (3 + 1) / 2)";
assert(!balancedParens(s, '(', ')', 1));
s = "1 + (2 * 3 + 1) / (2 - 5)";
assert(balancedParens(s, '(', ')', 1));

bool equal(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2);
二つのレンジの全ての要素が、二項述語 pred によって等しいと判定されたとき、 そのときに限り true を返します。 二つのレンジが違う型の要素を持っていても、pred(a, b) が r1 の a と r2 の b に対して bool を返すならば、このアルゴリズム関数は使用できます。 Ο(min(r1.length, r2.length)) 回 pred を呼び出します。参照: STL の equal.

Example:
int[] a = [ 1, 2, 4, 3 ];
assert(!equal(a, a[1..$]));
assert(equal(a, a));

// 違う型
double[] b = [ 1., 2, 4, 3];
assert(!equal(a, b[1..$]));
assert(equal(a, b));

// 述語版: 二つのベクトルがおおよそ等しい
double[] c = [ 1.005, 2, 4, 3];
assert(equal!(approxEqual)(b, c));

MinType!(T1,T2,T) min(T1, T2, T...)(T1 a, T2 b, T xs);
指定された値達のうち最小の物を返します。 結果の型は std.traits.CommonType で計算されます。

MaxType!(T1,T2,T) max(T1, T2, T...)(T1 a, T2 b, T xs);
指定された値達のうち最大の物を返します。 結果の型は std.traits.CommonType で計算されます。

Example:
int a = 5;
short b = 6;
double c = 2;
auto d = max(a, b);
assert(is(typeof(d) == int));
assert(d == 6);
auto e = min(a, b, c);
assert(is(typeof(e) == double));
assert(e == 2);

Tuple!(ElementType!(Range),size_t) minCount(alias pred = "a < b", Range)(Range range);
レンジ中の最小要素を、 出現回数と共に返します。 実際のところ、最大要素やその他の順序関係についても使用できます。(このため、maxCount アルゴリズムは特に提供されていません)。

Example:
int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
// 最小値は 1 で 3 回出現
assert(minCount(a) == tuple(1, 3));
// 最大値は 4 で 2 回出現
assert(minCount!("a > b")(a) == tuple(4, 2));

Range minPos(alias pred = "a < b", Range)(Range range);
前進レンジ range の最小値の位置を返します。つまり、 range の部分レンジであって、先頭がその最小値で、末尾が range と同じになっているものを返します。 この関数は実際には最大値やその他の順序関係にも使用できます。 (このため、maxPos は特に提供されていません)。

Example:
int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
// 最小値は 1 で最初の出現は第 3 要素
assert(minPos(a) == [ 1, 2, 4, 1, 1, 2 ]);
// 最大値は 1 で最初の出現は第 2 要素
assert(minPos!("a > b")(a) == [ 4, 1, 2, 4, 1, 1, 2 ]);

Tuple!(Range1,Range2) mismatch(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2);
r1 と r2 の要素を先頭から順に比較し、 最初に（pred による比較:デフォルトは==で） 等しくならなかった位置を返します。返値は、ミスマッチした値で始まるレンジのペアです。 Ο(min(r1.length, r2.length)) 回 pred を呼び出します。参照: STL の mismatch

Example:
int[]    x = [ 1,  5, 2, 7,   4, 3 ];
double[] y = [ 1., 5, 2, 7.3, 4, 8 ];
auto m = mismatch(x, y);
assert(m[0] == begin(x) + 3);
assert(m[1] == begin(y) + 3);

enum EditOp;
一つのシーケンスを別のシーケンスに変更するのに必要な 編集操作 を表します。 任意の入力 s (source) と t (target) に対し、 s を t に変える編集操作 EditOp の列が存在します。 例えば、s = "cat" と "cars" に対して、s から t への最短の編集操作列は: 2文字スキップ、't' を 'r' に置換、's' を挿入、となります。 編集操作に関する処理には、スペルチェッカ （ミススペルされた単語に一番近い単語を探す）や、 近似検索、ファイル間の差違を調べるdiff風のプログラム、 パッチの効率的な表現、DNA解析、盗用の検出などの応用があります。

none
カレントの項目は等しい; 編集の必要なし

substitute
sourceのカレント項目をtargetのカレント項目に置換

insert
targetのカレント項目をsourceに挿入

remove
sourceのカレント項目を削除

size_t levenshteinDistance(alias equals = "a == b", Range1, Range2)(Range1 s, Range2 t);
s と t の Levenshtein 距離 を返します。Levenshtein 距離とは、 s を t に変更するのに必要な最短の編集操作の回数です。 Ο(s.length * t.length) 回 equals を呼び出し、Ο(s.length * t.length) のメモリを使用します。

Example:
assert(levenshteinDistance("cat", "rat") == 1);
assert(levenshteinDistance("parks", "spark") == 2);
assert(levenshteinDistance("kitten", "sitting") == 3);
// 大文字小文字を区別しない
assert(levenshteinDistance!("toupper(a) == toupper(b)")
    ("parks", "SPARK") == 2);

Tuple!(size_t,EditOp[]) levenshteinDistanceAndPath(alias equals = "a == b", Range1, Range2)(Range1 s, Range2 t);
s と t の間の Levenshtein距離と、編集操作列を計算します。

Example:
string a = "Saturday", b = "Sunday";
auto p = levenshteinDistanceAndPath(a, b);
assert(p[0], 3);
assert(equals(p[1], "nrrnsnnn"));

Range2 copy(Range1, Range2)(Range1 source, Range2 target);
source の中身を target にコピーし、 target の残りの (埋められていない) 部分を返します。参照: STL の copy。もし STL の copy_backward に似た挙動が必要ならば、 copy(retro(source), retro(target)) とします。参照: std.range.retro.

Example:
int[] a = [ 1, 5 ];
int[] b = [ 9, 8 ];
int[] c = new int[a.length + b.length + 10];
auto d = copy(b, copy(a, c));
assert(c[0 .. a.length + b.length] == a ~ b);
assert(d.length == 10);
target の要素が source からの代入が可能な型であれば、 違う型のレンジ間のコピーも可能です。

Example:
float[] a = [ 1.0f, 5 ];
double[] b = new double[a.length];
auto d = copy(a, b);
最大 n 個までと限定を付けてレンジ a からレンジ b へのコピーを行うには、 copy(take(a, n), b) とすると良いでしょう。 レンジ a 中の条件 pred を満たす要素だけを b にコピーするには、 copy(filter!(pred)(a), b) とします。

Example:
int[] a = [ 1, 5, 8, 9, 10, 1, 2, 0 ];
auto b = new int[a.length];
auto c = copy(filter!("(a & 1) == 1")(a), b);
assert(b[0 .. $ - c.length] == [ 1, 5, 9, 1 ]);

Tuple!(Range1,Range2) swapRanges(Range1, Range2)(Range1 r1, Range2 r2);
レンジ r1 の各要素と、対応する位置にある r2 の要素をswapします。 r1 と r2 のswapされていない残りの部分（どちらか一方は空）を返します。 レンジ自体の型は異なっていても構いませんが、swapできるためには、 要素型は同じである必要があります。

Example:
int[] a = [ 100, 101, 102, 103 ];
int[] b = [ 0, 1, 2, 3 ];
auto c = swapRanges(a[1 .. 3], b[2 .. 4]);
assert(c[0].empty && c[1].empty);
assert(a == [ 100, 2, 3, 103 ]);
assert(b == [ 0, 1, 101, 102 ]);

void reverse(Range)(Range r);
r を in-place で逆転します。r.length 回 swap を呼び出します。参照: STL の reverse

Example:
int[] arr = [ 1, 2, 3 ];
reverse(arr);
assert(arr == [ 3, 2, 1 ]);

size_t bringToFront(Range1, Range2)(Range1 front, Range2 back);
bringToFront 関数は高い柔軟性と有用性を備えています。 ひとつのバッファの中で左右に要素を回転することもできますし、 同じ長さのバッファの要素を交換することもでき、さらには、 違う型違う長さのレンジの間で要素を動かすことも可能です。

bringToFront は二つのレンジ front と back を引数に取ります。 異なる型でも構いません。front と back を連結したレンジを仮想的に考え、 その連結レンジの内で back にあった要素が連結レンジの先頭に来るように動かします。front と back の中での相対的な順番は変化しません。

一番シンプルな bringToFront の使い方は、バッファの要素を回転される使い方です。例: 

auto arr = [4, 5, 6, 7, 1, 2, 3];
bringToFront(arr[0 .. 4], arr[4 .. $]);
assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ]);
front レンジは、実際には back レンジを"覆って"いても構いません。これは、 簡単に右を落とした部分レンジを arr[0 .. 4] のように簡単には計算できない、 前進レンジ等で役立ちます。以下の例では、r2 は r1 に含まれています。 

auto list = SList!(int)(4, 5, 6, 7, 1, 2, 3);
auto r1 = list[];
auto r2 = list[]; popFrontN(r2, 4);
assert(equal(r2, [ 1, 2, 3 ]));
bringToFront(r1, r2);
assert(equal(list[], [ 1, 2, 3, 4, 5, 6, 7 ]));
異なるレンジ型の間でも要素を交換できます: 

auto list = SList!(int)(4, 5, 6, 7);
auto vec = [ 1, 2, 3 ];
bringToFront(list[], vec);
assert(equal(list[], [ 1, 2, 3, 4 ]));
assert(equal(vec, [ 5, 6, 7 ]));
Ο(max(front.length, back.length)) 回の swap の評価を伴います。参照: STL の rotate。

Preconditions:
front と back が共通部分を持たないか、back が front から到達可能で front がback かた到達不可能であること

Returns:
frontへ移動された要素数、つまり、back の長さ

enum SwapStrategy;
レンジ内の要素をスワップする必要があるアルゴリズム（partion や sort） でのスワップ方針の定義です。 スワップ方針は、アルゴリズムのコアとなる基準では順序が重要でない要素の並べかたの 方針を表します。例えば、[ "abc", "b", "aBc" ] を順序 toupper(a) < toupper(b) に従ってソートするアルゴリズムを考えます。 このアルゴリズムでは、二つの同等な要素 "abc" と "aBc" の順序を入れ替えるかも知れないし、入れ替えないかもしれません。[ "abc", "aBc", "b" ] と [ "aBc", "abc", "b" ] のどちらもソートの出力としては妥当です。

状況によっては、そのような要素の順序は変更しないことが重要な場合もあります。 (先程の例で言うと、 [ "abc", "aBc", "b" ] だけを正しい出力としたい場合です)。 このようなアルゴリズムは stable (安定) であると言われます。 アルゴリズムが同等の要素をどう扱うか決まっていない場合、unstable (不安定) であると言われます。

両者の中間としてもう一つ、レンジの一部部分については stable を保証する、 という方針もあります。 この方針には一般的な名前はついていませんが、このライブラリでは semistable (準安定) と呼んでいます。

一般に、stable な方法は、他の二者と比較して 時間や空間計算量の面でコストがかかることがあります。 同様に、semistable は unstable よりもコストが高いかもしれません。(準)安定性が必要となる機会は必ずしも多くないので、 このモジュールでは SwapStrategy をパラメタ化し、 デフォルトでは全てのアルゴリズムで SwapStrategy.unstable を選択するようになっています。

unstable
アルゴリズムの基準を満たす限りでは、 要素を任意にスワップしてよい。

semistable
レンジを二つに分けるアルゴリズムで、 左半分についてのみ、元の順序を保存するようにする。

stable
アルゴリズムの基準を満たす範囲で最大限に、 要素の元の順序を保存するようにする。

Range remove(SwapStrategy s = SwapStrategy.stable, Range, Offset...)(Range range, Offset offset);
指定されたオフセットの要素を range から取り除き、 短くなったレンジを返します。一番簡単なケースでは、要素を一つ取り除きます。 

int[] a = [ 3, 5, 7, 8 ];
assert(remove(a, 1) == [ 3, 7, 8 ]);
assert(a == [ 3, 7, 8, 8 ]);
上の例では、オフセット 1 の要素が除かれ、remove は一つ短いレンジを返しています。元々の配列は、 長さは変換しません。std.algorithm の関数は全て 内容 は書き換えても トポロジ は書き換えないためです。 値 8 が繰り返されているのは、std.algorithm.move によって要素が移動されているためで、move は int に関しては単なるコピーを行うからです。 a に削除結果を反映させるには、 a = remove(a, 1) と代入します。 スライスは短い配列に合わせられ、最高の効率で処理が完了します。

複数のインデックスを remove に渡すこともできます。 この場合、対応するインデックスの要素が全て削除されます。 インデックスは昇順に渡して下さい。昇順になっていなければ例外が発生します。 

int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
assert(remove(a, 1, 3, 5) ==
    [ 0, 2, 4, 6, 7, 8, 9, 10 ]);
(全てのインデックスが 元々の 配列でのインデックスを指しているのにお気づきでしょうか。 縮めている作業の途中のインデックスではありません。） 最後に、整数オフセットと、 二つの整数のタプルで指定するオフセットを混ぜて渡すことができます。 

int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
assert(remove(a, 1, tuple(3, 5), 9) == [ 0, 2, 6, 7, 8, 10 ]);
この場合、インデックス 1, 3, 4, 9 にある要素が配列から取り除かれます。 タプルは、左を含み右を含まない区間 （配列スライスと同じです）を表します。tuple(3, 5) は 3 と 4 を含みますが 5 は含みません。

レンジ中の要素を取り除きたいが除いた後の順序は特に気にしない、 というケースでは、 SwapStrategy.unstable を remove に渡します。 

int[] a = [ 0, 1, 2, 3 ];
assert(remove!(SwapStrategy.unstable)(a, 1) == [ 0, 3, 2 ]);
この例では 1 が除かれ、 レンジの最後の要素で代わりに埋められています。 順序不変性を捨てるかわりに、この場合は remove は 配列の後ろから要素をとってきて削除された部分を埋めようとします。 このようにすることで、要素の移動回数が減り、実行時間の削減をもたらします。

関数 remove は前進レンジに適用できます。 スワップ方針は (速い順に):
  • s == SwapStrategy.unstable && isRandomAccessRange!Range && hasLength!Range のとき、削除部分を埋める要素はレンジの末端から取ってこられます。 この場合、理論的に最小の移動回数が実現されます。
  • それ以外では、s == SwapStrategy.unstable && isBidirectionalRange!Range && hasLength!Range の場合も、要素はレンジの末端から取ってこられますが、 range.popFront の繰り返しでレンジを進める分の時間がかかります。
  • それ以外では、 レンジの要素は順々に銭湯に向かって移動されます。 一つの要素が複数回動くことはありませんが、上2つのケースよりも移動される要素の数自体が多くなります。

Range remove(alias pred, SwapStrategy s = SwapStrategy.stable, Range)(Range range);
レンジ range から、pred を満たす要素を取り除きます。 s = SwapStrategy.stable (デフォルト) が指定されていれば。 残った要素の順序は保存されるように動作します。 残った要素を含む、 元々のレンジのスライスが返値となります。

Example:
int[] a = [ 1, 2, 3, 2, 3, 4, 5, 2, 5, 6 ];
assert(a[0 .. remove!("a == 2")(a).length] == [ 1, 3, 3, 4, 5, 5, 6 ]);

Range partition(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)(Range r);
述語 pred を使用して、レンジを分割します。 具体的には、レンジ r を swap によって r = [left, right) の形に並べ直し、 pred(i) が true な要素 i が全て pred(j) が false な要素 j の前に来るようにします。

Ο(r.length) 回 (unstable か semistable の時) または Ο(r.length * log(r.length)) 回 (stable の時)、less と swap を呼び出します。unstable 版は swap の評価回数を最小化します (おおよそ、semistable 版の半分になります)

参照: STL の partition と stable_partition.

Returns:
r を分割したあとの右側レンジ

ss == SwapStrategy.stable ならば、 partition は pred(a) == pred(b) が成り立つ要素 a, b 間の順序をそのまま維持します。 ss == SwapStrategy.semistable ならば、pred(a) == pred(b) == false な要素間の順序だけはそのまま維持します。

Example: 
auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
auto arr = Arr.dup;
static bool even(int a) { return (a & 1) == 0; }
// 偶数が先にくるように分離
auto r = partition!(even)(arr);
// この時点で、arr は偶数と奇数に分離されています
// stableではないため、数字の順番はごちゃごちゃに混ざっているかもしれません
assert(r == arr[5 .. $]);
assert(count!(even)(arr[0 .. 5]) == 5);
assert(find!(even)(r).empty);

// 文字列で述語を指定することも可能です
// 引数名としては 'a' を使います
arr[] = Arr[];
r = partition!(q{(a & 1) == 0})(arr);
assert(r == arr[5 .. $]);

// stableな分離:
arr[] = Arr[];
r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr);
// arr は [2 4 6 8 10 1 3 5 7 9] で、r は 1 を指すようになる
assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]);

// 述語が状態を持つ必要があるときは、delegate を使います
arr[] = Arr[];
int x = 3;
// 3 より大きい要素を左に
bool fun(int a) { return a > x; }
r = partition!(fun, SwapStrategy.semistable)(arr);
// arr は [4 5 6 7 8 9 10 2 3 1] で r は 2 を指す
assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && r == arr[7 .. $]);

bool isPartitioned(alias pred, Range)(Range r);
r が述語 pred に従って分割されていれば true を返します。

Example:
int[] r = [ 1, 3, 5, 7, 8, 2, 4, ];
assert(isPartitioned!("a & 1")(r));

void topN(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r, size_t nth);
レンジ r を swap によって並び替えて、r[nth] に、ソートしたら nth 番目に来るはずの要素が来るようにします。 加えて、r 中の要素で r[0] から r[nth] の範囲にあるものは !less(r[nth], e1) を満たし、 r[nth] から r[r.length] にあるものは !less(e2, r[nth]) を満たすようにします。結果として、 (less に関して) 小さい方から nth 個の要素を見つけ出す処理になっています。Ο(r.length) 回 (unstableのとき) または Ο(r.length * log(r.length)) 回 (stable の時) less と swap を呼び出します。参照: STL の nth_element

Example:
int[] v = [ 25, 7, 9, 2, 0, 5, 21 ];
auto n = 4;
topN!(less)(v, n);
assert(v[n] == 9);
// Equivalent form:
topN!("a < b")(v, n);
assert(v[n] == 9);

BUGS:
Stable topN は未実装です

void topN(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(Range1 r1, Range2 r2);
一つ目のレンジに、小さい要素を集めます。

SortedRange!(Range,less) sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r);
ランダムアクセスレンジを述語 less に従ってソートします。 Ο(r.length * log(r.length)) 回 (unstableのとき) または Ο(r.length * log(r.length) * log(r.length)) 回 (stableのとき)、less と swap を呼び出します。参照: STL の sort と stable_sort

Example:
int[] array = [ 1, 2, 3, 4 ];
// sort in descending order
sort!("a > b")(array);
assert(array == [ 4, 3, 2, 1 ]);
// sort in ascending order
sort(array);
assert(array == [ 1, 2, 3, 4 ]);
// sort with a delegate
bool myComp(int x, int y) { return x > y; }
sort!(myComp)(array);
assert(array == [ 4, 3, 2, 1 ]);
// Showcase stable sorting
string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
sort!("toupper(a) < toupper(b)", SwapStrategy.stable)(words);
assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);

void schwartzSort(alias transform, alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r);
レンジを Schwartzian transform 風のアルゴリズムでソートします。 Python や Lisp では decorate-sort-undecorate パターンとして知られています。 (他の Schwartz と混同しないように)。この関数は、比較キーの計算にコストがかかる場合の ソートに便利です。計算量は 対応する sort と同じですが、schwartzSort は transform を高々 r.length 回しか呼び出しません。(普通のソートの半分以下です)。 使い方は次の例をご覧下さい。

Example:
uint hashFun(string) { ... 重い計算 ... }
string[] array = ...;
// ハッシュ値で文字列をソート。遅い。
sort!("hashFun(a) < hashFun(b)")(array);
// ハッシュ値で文字列をソート。速い (arr.length 回しかハッシュを計算しない):
schwartzSort!(hashFun, "a < b")(array);
schwartzSort 関数は、Perl のイディオムや Python, Lisp の decorate-sort-undecorate イディオムよりもテンポラリ領域の消費が少なく、 高速に動作する可能性があります。これは、ソートが in-place で行われ、 追加のデータ領域が最小 (変換後の要素を含む配列１つ) にとどまるためです。

あらかじめSchwartzソート済みかどうかをチェックして高速化に役立てるための関数 schwartzIsSorted は提供されません。 これは、同じ効果が isSorted!(less)(map!(transform)(r)) で実現できるからです。

void partialSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r, size_t n);
ランダムアクセスレンジ r を並べ替えて、r[0 .. mid] が r をソートしたときと同じ状態になるようにし、 r[mid .. r.length] は不特定の順番のままにします。 Ο(r.length * log(mid)) 回 pred を呼び出します。 実装は単に topN!(less, ss)(r, n) の後に sort!(less, ss)(r[0 .. n]) を呼び出します。

Example:
int[] a = [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ];
partialSort(a, 5);
assert(a[0 .. 5] == [ 0, 1, 2, 3, 4 ]);

void completeSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(SortedRange!(Range1,less) lhs, Range2 rhs);
ランダムアクセスレンジ chain(lhs, rhs) を 述語 less に従ってソートします。左レンジ lhs はソート済みであると仮定されます。rhs には特に前提条件はありません。 どのような戦略でソートを行うかは lhs と rhs のサイズに依存します。Ο(lhs.length + rhs.length * log(rhs.length)) 回 (最良ケース) から Ο((lhs.length + rhs.length) * log(lhs.length + rhs.length)) 回 (最悪ケース) swap を呼び出します。

Example:
int[] a = [ 1, 2, 3 ];
int[] b = [ 4, 0, 6, 5 ];
completeSort(assumeSorted(a), b);
assert(a == [ 0, 1, 2 ]);
assert(b == [ 3, 4, 5, 6 ]);

bool isSorted(alias less = "a < b", Range)(Range r);
random-access レンジが比較演算lessに関してソート済みかどうかチェックします。Ο(r.length) 回 less を呼び出します。

Example:
int[] arr = [4, 3, 2, 1];
assert(!isSorted(arr));
sort(arr);
assert(isSorted(arr));
sort!("a > b")(arr);
assert(isSorted!("a > b")(arr));

void makeIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index) if (isForwardRange!(Range) && isRandomAccessRange!(RangeIndex) && is(ElementType!(RangeIndex) : ElementType!(Range)*))
void makeIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index) if (isRandomAccessRange!(Range) && isRandomAccessRange!(RangeIndex) && isIntegral!(ElementType!(RangeIndex)))
レンジ r に関する、比較演算 less についてのインデックスを作成します。ここでのインデックスとは、ソート済みのポインタ配列で、 各ポインタは元のレンジの要素を指します。このテクニックはソートに似ていますが、 より柔軟です。理由としては (1) immutable なコレクションの "ソート" が可能で (2) オリジナルのコレクションがランダムアクセス不可能であっても二分探索を可能とし、 (3) 異なる述語による複数のインデックスを作成可能で (4) 巨大なオブジェクトを扱う際にはより高速になりうる、などがあります。 一方で、インデックスを使うことで余計なポインタ参照が入るため低速になる場面もありますし、 元のコレクションに加えて別にインデックスを持つため、 確実に多くのメモリを消費します。 計算量は sort と同じです。

makeIndex は第二引数を結果で上書きしますが、 メモリの再割り当ては行いません。第二引数のレンジが必要量より短いときには、 例外が発生します。

makeIndex の１つ目のオーバーロード版ではポインタを格納するレンジに書き込み、 ２つ目ではオフセットを格納するレンジに書き込みます。 １つ目では Range が前進レンジである必要があり、 ２つめではランダムアクセスレンジが要求されます。

Example:
immutable(int[]) arr = [ 2, 3, 1, 5, 0 ];
// ポインタによるインデックス
auto index1 = new immutable(int)*[arr.length];
makeIndex!("a < b")(arr, index1);
assert(isSorted!("*a < *b")(index1));
// オフセットによるインデックス
auto index2 = new size_t[arr.length];
makeIndex!("a < b")(arr, index2);
assert(isSorted!
    ((size_t a, size_t b){ return arr[a] < arr[b];})
    (index2));

enum SortOutput;
アルゴリズムの出力がソート済みであって欲しいか否かの指定です。

no
出力をソートしない

yes
出力をソートする

bool canFind(alias pred = "a == b", Range, V)(Range range, V value);
value が range に見つる時に true を返しますΟ(r.length) 回 pred を呼び出します。

bool canFind(alias pred, Range)(Range range);
述語 pred を満たす要素 v が前進レンジ range の中に見つかるときに true を返します。Ο(r.length) 回 pred を呼び出します。

TRange topNCopy(alias less = "a < b", SRange, TRange)(SRange source, TRange target, SortOutput sorted = SortOutput.no);
入力レンジ source をソートしたときの上位 target.length 要素をランダムアクセスレンジ target にコピーします。 source の内容は変わりません。sorted が true ならば、target もソート済みになります。それ以外の場合、 target は heap property を持った列になります。

Example:
int[] a = [ 10, 16, 2, 3, 1, 5, 0 ];
int[] b = new int[3];
topNCopy(a, b, true);
assert(b == [ 0, 1, 2 ]);

struct SetUnion(alias less = "a < b",Rs...) if (allSatisfy!(isInputRange,Rs));
SetUnion!(less,Rs) setUnion(alias less = "a < b", Rs...)(Rs rs);
複数のレンジの併合を遅延評価的に計算します。 各レンジは less でソートされているものと仮定されます。 出力レンジの要素は unique 化されていません; 出力の長さは入力の長さの総和です。 (length メンバは、与えられたレンジ全てが length を持っていれば提供されます。) 各レンジの要素型は共通の型を持たなければなりません。

Example:
int[] a = [ 1, 2, 4, 5, 7, 9 ];
int[] b = [ 0, 1, 2, 4, 7, 8 ];
int[] c = [ 10 ];
assert(setUnion(a, b).length == a.length + b.length);
assert(equal(setUnion(a, b), [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9][]));
assert(equal(setUnion(a, c, b),
    [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9, 10][]));

struct SetIntersection(alias less = "a < b",Rs...) if (allSatisfy!(isInputRange,Rs));
SetIntersection!(less,Rs) setIntersection(alias less = "a < b", Rs...)(Rs ranges);
複数のレンジの共通部分を遅延評価的に計算します。 各レンジは less でソートされているものと仮定されます。 各レンジの要素型は共通の型を持たなければなりません。

Example:
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][]));

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 でソートされているものと仮定されます。 二つのレンジの要素型は共通の型を持たなければなりません。

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

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 でソートされているものと仮定されます。 二つのレンジの要素型は共通の型を持たなければなりません。

Example:
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][]));

struct NWayUnion(alias less,RangeOfRanges);
NWayUnion!(less,RangeOfRanges) nWayUnion(alias less = "a < b", RangeOfRanges)(RangeOfRanges ror);
複数の集合を全て合併した集合を計算します。入力は、 less でソート済みのレンジのレンジで与えます。計算は遅延評価的に実行され、 合併集合の要素が一つずつ計算されます。1回の popFront の計算量は Ο(log(ror.length)) です。ただし、 ror の長さは空になったレンジが除かれて行くたびに短くなるので、NWayUnion で最後まで列挙し終わるまでの計算量は、 ror 内の要素の分布に依存します。全てのレンジが同じ長さ n (最悪ケース) であれば、NWayUnion 全体の計算量は Ο(n * ror.length * log(ror.length)) となり、全てのレンジを単にたどるのより log(ror.length) 倍悪くなります。 出力は (unstable に) less によってソートされて返されます。

Warning:
NWayUnion は余計なメモリを割り当てないために、 ror を書き換えます。つまり、NWayUnion は ror の所有権を暗に仮定しており、その要素を swap 等で書き換えます。 ror の中身を変えずに残しておきたい場合は、 NWayUnion には ror のコピーを渡すようにするとよいでしょう。

Example:
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[]));

void largestPartialIntersection(alias less = "a < b", RangeOfRanges, Range)(RangeOfRanges ror, Range tgt, SortOutput sorted = SortOutput.no);
ソート済み前進レンジのレンジ ror を受け取り、tgt に、rorに出現した回数の多い共通要素を出現回数と共に記録します。 ror のレンジは全て less でソート済みと仮定されます。出現回数上位 tgt.length 個の要素が記録されます。

Example:
// もっとも多くの配列に登場した
// 要素を答える例
double[][] a =
[
    [ 1, 4, 7, 8 ],
    [ 1, 7 ],
    [ 1, 7, 8],
    [ 4 ],
    [ 7 ],
];
auto b = new Tuple!(double, uint)[1];
largestPartialIntersection(a, b);
// 第一要素がレンジ中の要素で、第二要素が出現回数です
assert(b[0] == tuple(7.0, 4u));
7.0 が、5 入力中 4 回と他のどの値よりも多く登場したので、答えとなっています。 返値タプルの第二要素は 4 (7.0 の出現回数) です。最大頻度の値だけでなく 2 番目、3 番目も欲しいときは、 tgt レンジのサイズを大きくします。上の例では、b の長さを 2 にしていれば tuple(1.0, 3u) が2つ目に入ります。

largestPartialIntersection は、例としては、 ドキュメント群の 転置インデックス から、指定の単語にもっとも関連の高いドキュメントを探す場合などに有用です。 検索の計算量は Ο(n * log(tgt.length)) となります（n は全てのレンジの長さの総和です）。 このアプローチは、 出現を連想配列で保持しておきトップの要素を取り出すのと比べて高速で、 必要とするメモリも少量で済みます (largestPartialIntersection は結果を直接 tgt に格納し余計なメモリを使いません)

Warning:
largestPartialIntersection は余計なメモリを割り当てないために、 ror を書き換えます。つまり、NWayUnion は ror の所有権を暗に仮定しており、その要素を swap 等で書き換えます。 ror の中身を変えずに残しておきたい場合は、largestPartialIntersection には ror のコピーを渡すようにするとよいでしょう。

void largestPartialIntersectionWeighted(alias less = "a < b", RangeOfRanges, Range, WeightsAA)(RangeOfRanges ror, Range tgt, WeightsAA weights, SortOutput sorted = SortOutput.no);
largestPartialIntersection と似ていますが、 要素毎に重みを設定できます。

Example:
// もっとも多くの配列に登場した
// 要素を答える例（重み付き）
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.3 の 2 倍) あり、値 7 の重み 4.4 (1.1 の 4 倍) より大きくなっています。