D 2.0
About Japanese Translation

www.digitalmars.com
Last update Thu Aug 7 22:02:19 2008

std.algorithm

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

Author:
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"
いくつかの関数は、move (デフォルトは std.algorithm.move) や iterSwap (デフォルトは std.algorithm.iterSwap) のようなプリミティブを追加のパラメタとして受け付けます。 これらのパラメタでは、データの操作方法を指定でき、アルゴリズムは これらを通してのみ値を操作することが保証されます。デフォルトの挙動を上書きする必要が生じる場合としては、 例えば、オブザーバへの通知や、処理回数のカウント、複数個の処理を１個のロックにまとめる場合などがあります。

template map(fun...)
多くの関数型言語に存在する同名の関数 (transform としても知られる) の実装です。 map!(fun)(range1,range2, ..., rangeN) を呼び出すと、左から右に range1 内の x、range2 内の x、…、rangeN 内の x に関数を適用した結果 fun(x) を並べたレンジが結果として得られます。引数として与えられたレンジは変更されません。

Example:
int[] arr1 = [ 1, 2, 3, 4 ];
int[] arr2 = [ 5, 6 ];
auto squares = map!("a * a")(arr1, arr2);
assert(squares == [ 1, 4, 9, 16, 25, 36 ]);
いずれの場合も、結果の型は第一引数のレンジと同じ型となります。 別のレンジが必要な場合は、 先頭に空のレンジを渡してください。

Example:
short[] arr = [ 1, 2 ];
auto squares = map!("a * a")(cast(int[]) null, arr);
assert(is(typeof(squares) == int[]));


template reduce(F...)
多くの関数型言語に存在する同名の関数 (accumulate, compress, inject, foldl, などとしても知られる) の実装です。reduce!(fun)(seed, range) を呼び出すと、まず「アキュムレータ」と呼ばれる内部変数 result に seed を設定し、range の各要素 x について、result = fun(result, x) が実行されます。最終的には、result が返されます。 レンジに対する多くの操作が、 比較的簡単に 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[0], arr[1 .. $]);
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);
複数のレンジ:
reduce には、 reduce!(fun)(seed, range1, range2, range3) のように複数のレンジを渡すことができます。この場合 reduce は各々のレンジに対して左から右に順々に実行されます。

Example:
int[] a = [ 3, 4 ];
int[] b = [ 100 ];
auto r = reduce!("a + b")(0, a, b);
assert(r == 107);

// 変換可能な型を混ぜることも可能
double[] c = [ 2.5, 3.0 ];
auto r1 = reduce!("a + b")(0.0, 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)(double.max, -double.max, a);
// r の型は Tuple!(double, double)
assert(r._0 == 2);  // 最小値
assert(r._1 == 11); // 最大値

// 総和と二乗の総和を１パスで計算
r = reduce!("a + b", "a + b * b")(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);
複数のレンジと関数:
従って、reduce の一般形としては、複数の関数と複数のレンジを 同時に受け取ることになります。reduce!(fun1, ..., funN)(seed1, ..., seedN, range1, ..., rangeM) を呼び出すと、全ての関数と全てのレンジに対して アルゴリズムが実行されます。

Example:
int[] a = [ 3, 4, 7, 11, 3, 2, 5 ];
double[] b = [ 2.5, 4, -4.5, 2, 10.9 ];
// a と b にわたる最小値と最大値を計算
auto r = reduce!(min, max)(double.max, -double.max, a, b);
assert(r._0 == -4.5);  // 最小値
assert(r._1 == 11);    // 最大値


Range overlap(Range)(Range r1, Range r2);
二つのレンジに重なりがあればその部分を返します。equal と違い、overlap はレンジ内の値を見ずに、イテレータだけを比較します。 r1 と r2 に重なりがあった場合は、その重なりに対応するレンジを返します。そうでなければ、 空レンジを返します。レンジが forward range の場合は Ο(min(r1.length, r2.length)) 回のイテレータの増加と比較を行い、レンジが random access の場合は Ο(1) 回の比較が行われます。

Example:
int[] a = [ 10, 11, 12, 13, 14 ];
int[] b = a[1 .. 3];
assert(overlap(a, b) == [ 11, 12 ]);
b = b.dup;
// 内容が同じでも今度は重なりは無い
assert(isEmpty(overlap(a, b)));


Ranges[0] filter(alias pred, Ranges...)(Ranges 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 ]);
複数のレンジ:
filter に filter!(fun)(range1, range2, range3) のように複数のレンジを渡すことが可能です。この場合、filter は各々のレンジに対して左から右に順々に実行されます。 返値は先頭のレンジと同じ型になります。

Example:
int[] a = [ 3, -2, 400 ];
int[] b = [ 100, -101, 102 ];
auto r = filter!("a > 0")(a, b);
assert(r == [ 3, 400, 100, 102 ]);

// 変換可能な型を混ぜることも可能
double[] c = [ 2.5, 3.0 ];
auto r1 = filter!("cast(int) a != a")(c, a, b);
assert(r1 == [ 2.5 ]);


void inPlace(alias fun, Range, Ranges...)(Range r, Ranges rs);
map と似ていますが、こちらは渡されたレンジを変更し、 void を返します。inPlace!(fun)(range1, range2, ..., rangeN) を呼び出すと、fun(x) が左から右に range1 内の ref x、 range2 内の ref x、…、rangeN 内の ref x に対して実行されます。

Example:
int[] arr1 = [ 1, 2, 3 ];
inPlace!(writeln)(arr1); // print the array
double[] arr2 = [ 4.0, 8.5, 13 ];
inPlace!("++a")(arr1, arr2);
assert(arr1 == [ 2, 3, 4 ]);
assert(arr2 == [ 5.0, 9.5, 14 ]);


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

Preconditions:
!pointsTo(source, source)

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

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

Range overwriteAdjacent(alias pred, alias move, Range)(Range r);
Range overwriteAdjacent(string fun = "a == b", alias move = .move, Range)(Range r);
pred(a, b) を満たす隣接要素 a, b が r から無くなるまで、 r をシフトして要素を減らすことを繰り返します。シフト操作は move(source, target) を評価することで実行されます。 このアルゴリズムは安定（stable）で、Ο(r.length) 時間で実行されます。 返値は要素を減らし終えたあとのレンジです。

デフォルトの std.algorithm.move は、破壊的となりうる source から target への代入を実行します。 従って、返されたレンジよりも先のオブジェクトは "空" と見なされるべきです。 デフォルトの pred は等値性を比較するもので、この場合、overwriteAdjacent は隣り合う重複要素を一つにまとめます。（uniq のような働きとなります。）

Example:
int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
auto r = overwriteAdjacent(arr);
assert(r == [ 1, 2, 3, 4, 5 ]);


Iterator!(Range) find(alias pred = "a == b", Range, E)(Range haystack, E needle);
haystack 内の最初の needle の出現を線形探索で探し、 その出現を指すイテレータを返します。二項述語 pred を指定することで、 find での比較方法をカスタマイズできます （レンジの要素を第一引数に、needleを第二引数にして呼び出します）。デフォルトでは、等値性を比較します。 pred は Ο(haystack.length) 回呼び出されます。参照： STL の find

haystack 内の最後の needle の出現を得るには、find(retro(haystack), needle) を呼び出し、結果を rEnd(haystack) と比較してください。参照： std.iterator.retro

Example:
auto a = [ 1, 2, 3 ];
assert(find(a, 5) == end(a));       // not found
assert(find(a, 2) == begin(a) + 1); // found

// 文字列の大文字小文字を区別しない検索
string[] s = [ "Hello", "world", "!" ];
assert(find!("toupper(a) == toupper(b)")(s, "hello") == begin(s));


Iterator!(Range) find(alias pred, Range)(Range haystack);
単項述語 pred を満たす最初の要素を探します。Ο(haystack.length) 回 pred を呼び出します。 参照： STL の find_if

haystack の中の pred を満たす最後の要素を探した場合は、find!(pred)(retro(haystack)) を呼んで結果を rEnd(haystack) と比較してください。参照： std.iterator.retro

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

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


Iterator!(Range1) findRange(alias pred = "a == b", Range1, Range2)(Range1 seq, Range2 subseq);
seq 内の最初の subseq の出現を、線形探索の繰り返しで探します。 Ο(seq.length * subseq.length) 回 pred を呼び出すため、長大なレンジに対してこの関数を使用するのはお薦めできません。そのような場合は std.algorithm.findBoyerMoore の方がより適切です。 参照： STL の search

Example:
int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
int[] b = [ 1, 2, 3 ];
assert(findRange(a, b) == begin(a) + 2);
assert(findRange(b, a) == end(b));


Iterator!(Range) findBoyerMoore(alias pred = "a == b", Range)(Range seq, Range subseq);
seq 内の最初の subseq の出現を、 Boyer-Moore algorithm で探索します。このアルゴリズムは初期コストは大きいですが、劣線形のスケーラビリティがあり、 長大なレンジに対する検索に適しています。最悪ケースで Ο(seq.length) 回、最良ケースで Ο(seq.length / subseq.length) 回 pred を呼び出します。

Example:
int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
int[] b = [ 1, 2, 3 ];
assert(findBoyerMoore(a, b) == begin(a) + 2);
assert(findBoyerMoore(b, a) == end(b));


BUGS:
最後の subseq に基づく計算をキャッシュして スレッドセーフな領域に保存し、何度も計算を繰り返す必要がないよう実装されるべき

Iterator!(Range) findAdjacent(alias pred = "a == b", Range)(Range r);
レンジ r 内の、最初に pred(a, b) を満たす隣接要素 a, b を探します。Ο(r.length) 回 pred を呼び出します。参照： STL の adjacent_find

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


Iterator!(Range1) findAmong(alias pred = "a == b", Range1, Range2)(Range1 seq, Range2 choices);
（pred によって）choices の要素のいずれかと等しいと判定されるような、 seq の最初の要素を探します。choices レンジに対しては線形探索が行われます。 Ο(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) == begin(a) + 2);
assert(findAmong(b, a) == begin(b));


Iterator!(Range1) findAmongSorted(alias less = "a < b", Range1, Range2)(Range1 seq, in Range2 choices);
seq の要素 x で、 choices 内のいずれかの要素 y と等しいと判定されるもの （つまり !less(x, y) && !less(y, x)）のうち最初の要素を探します。choices レンジに対しては二分探索が行われます。 従って、choices は pred （デフォルトは "a < b"） によってソート済みと仮定されます。Ο(seq.length * log(choices.length)) 回 less を呼び出します。

seq 内の条件を満たす最後の要素を得るには、 findAmongSorted(retro(seq), choices) を呼び出し、結果をrEnd(seq) と比較してください。参照： std.iterator.retro

Example:
int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
int[] b = [ 1, 2, 3 ];
assert(findAmongSorted(a, b) == begin(a) + 2);
assert(findAmongSorted(b, a) == end(b));


bool canFind(alias pred = "a == b", Range, E)(Range haystack, E needle);
bool canFind(alias pred, Range)(Range haystack);
bool canFindAmong(alias pred, Range1, Range2)(Range1 seq, Range2 choices);
bool canFindAmongSorted(alias pred, Range1, Range2)(Range1 seq, Range2 choices);
それぞれ対応する find* 系関数が end(r) と違う値を返すときに true を返すような便利関数です。 find* 系関数で検索を行うが、 実際に見つかった要素の位置の情報は特に必要ない、 という数々の状況で役に立ちます。

Example:
int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
assert(canFind(a, 4));
assert(!canFind(a, 10));
assert(canFind!("a - 1 < b")(a, 4));
assert(!canFind!("a > 5")(a));


size_t count(alias pred = "a == b", 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 equal(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2);
二つのレンジを要素毎に pred で比較し、すべて等しければ true を返します。 r1 の要素 a と r2 の要素 b に対して pred(a, 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!(Iterator!(Range1),Iterator!(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, Range1, Range2)(Range1 s, Range2 t);
size_t levenshteinDistance(string 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, Range1, Range2)(Range1 s, Range2 t);
Tuple!(size_t,EditOp[]) levenshteinDistanceAndPath(string 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.iterator.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);


Range2 copyIf(alias pred,Range1,Range2)(Range1 source, Range2 target);
source の要素 x のうち pred(x) を満たすものを、先頭から順に target にコピーし、残った （コピーで埋まらなかった）部分を返します。参照： STL の copy_if

Example:
int[] a = [ 1, 5, 8, 9, 10, 1, 2, 0 ];
auto b = new int[a.length];
auto c = copyIf!("(a & 1) == 1")(a, b);
assert(b[0 .. $ - c.length] == [ 1, 5, 9, 1 ]);
target レンジの要素型が source レンジの要素型からの代入を受け付けるならば、違う型のレンジでも構いません。

Example:
float[] a = [ 1.0f, 5, -3, -5, 0, 4, -3 ];
double[] b = new double[a.length];
auto d = copyIf!("a > 0")(a, b);
assert(a == [ 1.0f, 5, 0, 4 ]);


void iterSwap(It)(It lhs, It rhs);
*lhs と *rhs をスワップ

Preconditions:
swap(*lhs, *rhs) の事前条件と同じ

Range2 swapRanges(alias iterSwap = .iterSwap,Range1,Range2)(T r1, T r2);
r1 の全ての要素を r2 の対応する要素と iterSwap でスワップします。r1 は、 r2 と同じかより少ない数の要素を持っている必要があります。そうでない場合は例外が発生します。 スワップされなかった r2 の後半部分を返します。

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


void reverse(alias iterSwap = .iterSwap,Range)(Range r);
r をその場で逆順にします。r.length 回 iterSwap を呼び出します。参照： STL の reverse

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


It rotate(alias iterSwap = .iterSwap,Range,It)(Range r, It middle);
レンジ r = [first, last) を回転して、スライス [middle, last) が先頭に、スライス [first, middle) が後半となるようにします。Ο(r.length) 回 iterSwap を呼び出します。参照： STL の rotate

Preconditions:
first <= middle && middle <= last;

Returns:
first が移動した先を指すイテレータ

Example:
auto arr = [4, 5, 6, 7, 1, 2, 3];
auto p = rotate(arr, begin(arr) + 4);
assert(p - begin(arr) == 3);
assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ]);


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 eliminate(alias pred,SwapStrategy ss = SwapStrategy.unstable,alias move = .move,Range)(Range r);
pred(x) を満たす r の要素 x を全て上書きし、レンジを縮小します。返値は縮小後のレンジです。

Example:
int[] arr = [ 1, 2, 3, 4, 5 ];
// 偶数を除去
auto r = eliminate!("(a & 1) == 0")(arr);
assert(r == [ 1, 3, 5 ]);
assert(arr == [ 1, 3, 5, 4, 5 ]);


Range eliminate(alias pred = "a == b",SwapStrategy ss = SwapStrategy.semistable,Range,Value)(Range r, Value v);
pred(x, v) を満たす r の要素 x を全て上書きし、レンジを縮小します。返値は縮小後のレンジです。

Example:
int[] arr = [ 1, 2, 3, 2, 4, 5, 2 ];
// 2以外の要素を残す
auto r = eliminate(arr, 2);
assert(r == [ 1, 3, 4, 5 ]);
assert(arr == [ 1, 3, 4, 5, 4, 5, 2  ]);


Iterator!(Range) partition(alias predOrStr,SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,Range)(Range r);
レンジを、二つの区間に分離します。pred を比較述語、iterSwap を二つの要素のスワップに使用します。具体的には、 レンジ r = [left, right) を iterSwap で並び替えて、 pred(i) が true になる要素 i が先頭側に、 pred(j) が false を返す要素 j が後ろ側に集まるようにします。

Ο(r.length) 回 (unstable 版 と semistable 版) あるいは Ο(r.length * log(r.length)) 回 (stable 版) の less と iterSwap の呼び出しを行います。unstable 版は、 iterSwap の呼び出し回数を最小限にします (おおよそ、semistable 版の 半分の回数になります)。

partition が iterSwap(i, j) を呼び出すのは、常に i < j && !pred(*i) && pred(*j) を満たすイテレータに対してです。iterSwap(i, j) の呼び出し後は、partition は *i と *j の値に対してなんの仮定もおきません。従って partition は実際には、 分離されたデータを別のコンテナや配列に格納するといった処理も実現可能です。 (実は、eliminate は partition に特別な iterSwap を与える形で実装されています。)

参照： STL の partition と stable_partition

Returns:
以下の条件を同時に満たすイテレータ p を返します：
  1. [left, p) 内の 全ての p1 ついて、pred(*p1)
  2. [p, right) 内の全ての p2 について、!pred(*p2)
ss == SwapStrategy.stable ならば、 partition は pred(a) == pred(b) であるような a, b について、元のレンジ r での相対的な順番を保ちます。ss == SwapStrategy.semistable ならば、partition は、pred(a) == pred(b) であるような begin(r) .. p 内の要素について、 a, b の相対的な順序を元通りに保ちます。

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 p = partition!(even)(arr);
// この時点で、arr は偶数と奇数に分離されています
// stableではないため、数字の順番はごちゃごちゃに混ざっているかもしれません
assert(p == arr.ptr + 5);
assert(count!(even)(range(begin(arr), p)) == p - begin(arr));
assert(find!(even)(range(p, end(arr))) == end(arr));

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

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

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


void topN(alias less = "a < b",SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,Range,It)(Range r, It nth);
r = [first, last) を iterSwap 使って並び替えて、nth の指す先に、レンジを完全にソートしたら 来るはずの要素が来るようにします。結果として、r 内で (順序 less に関して) n番目に小さい要素を見つけることができます。 さらに追加効果として、r が、 [first, nth) 内の p1 は less(*p1, *nth) を満たし、 [nth, last) 内の p2 が !less(*p2, nth) を満たすように分離されます。Ο(r.length) 回 (unstable版) あるいは Ο(r.length * log(r.length)) 回 (stable版) の less と iterSwap の呼び出しを伴います。参照： STL の nth_element

Example:
int[] v = [ 25, 7, 9, 2, 0, 5, 21 ];
auto n = 4;
topN!(less)(v, begin(v) + n);
assert(v[n] == 9);
// 以下に同じ:
topN!("a < b")(v, begin(v) + n);
assert(v[n] == 9);


BUGS:
stable な topN は未実装です。

void sort(alias less = "a < b",SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,Range)(Range r);
random-access レンジを述語 less でソートします。 Ο(r.length * log(r.length)) 回 (unstable版) あるいは Ο(r.length * log(r.length) * log(r.length)) 回 (stable版) の less と iterSwap の呼び出しを行います。参照： STL の sort and stable_sort

Example:
int[] array = [ 1, 2, 3, 4 ];
// 降順ソート
sort!("a > b")(array);
assert(array == [ 4, 3, 2, 1 ]);
// 昇順ソート
sort(array);
assert(array == [ 1, 2, 3, 4 ]);
// delegateでソート
bool myComp(int x, int y) { return x > y; }
sort!(myComp)(array);
assert(array == [ 4, 3, 2, 1 ]);
// 安定ソートの例
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 パターンとして知られています。 (他の the other 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 で行われ、 追加のデータ領域が最小 (変換後の要素を含む配列１つ) にとどまるためです。

void partialSort(alias less = "a < b",SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,Range,It)(Range r, It mid);
r を並び替えて、begin(r) .. mid が r をソートしたときと等しくなるようにします。残りの要素は mid .. end(r) に順序不定で残ります。Ο(r.length * log(mid - begin(r))) 回 pred を呼び出します。

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


bool isSorted(alias less,Range)(Range r);
bool isSorted(string 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 topNIndex(alias less,SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,SRange,TRange)(SRange source, TRange target);
void topNIndex(string less,SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,SRange,TRange)(SRange source, TRange target);
topNIndex

void partialIndex(alias less,SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,SRange,TRange)(SRange source, TRange target);
比較演算 less に基づいて source の順序インデックスを計算し、 結果を target に格納します。target.length < source.length とすることも可能で、この場合、source の小さい方から target.length 個の要素のみにインデックスが計算されます。target は、 いわば source のソートされた "view" となります。このテクニックは ソートと部分ソートに似ていますが、(1) invariantなコレクションのソートができる (2) オリジナルのコレクションがランダムアクセス不可能でも二分探索が可能 (3) 異なる比較基準によって複数のインデックスを作成可能 (4) 巨大なオブジェクトを扱うときには高速、といった利点があります。一方で、 よけいな間接参照を挟むことで、場合によってはインデックスを作成することは非効率なこともあります。 特に、オリジナルのコレクションに加えてインデックス用のメモリ領域が必要なため、 ソートによる方法よりもメモリ消費は必ず大きくなります。 計算量は Ο(source.length * log(target.length)) です。

二種類のインデックスがサポートされています。この二種類は target 引数の型に応じて選択されます:
  1. Iterator!(Source) 型のインデックス。この場合インデックスは 述語 less(*a, *b) でソートされます
  2. 整数型 （size_t など）のインデックス。この場合インデックスは 述語 less(source[a], source[b]) でソートされます


Example:
invariant arr = [ 2, 3, 1 ];
int* index[3];
partialIndex(arr, index);
assert(*index[0] == 1 && *index[1] == 2 && *index[2] == 3);
assert(isSorted!("*a < *b")(index));


bool schwartzIsSorted(alias transform,alias less,Range)(Range r);
bool schwartzIsSorted(alias transform,string less = "a < b",Range)(Range r);
比較演算 less(transform(a), transform(b)) に基づいて、 random-access レンジがソート済みかどうかを判定します。 Ο(r.length) 回 less と transform を呼び出します。 isSorted と比較した利点は、transform の呼び出し回数が半分になることです。

Example:
int[] arr = [ "ab", "Ab", "aB", "bc", "Bc" ];
assert(!schwartzIsSorted!(toupper, "a < b")(arr));


Iterator!(Range) lowerBound(alias less = "a < b",Range,V)(Range r, V value);
r のなかで、 それより左の要素 x は全て less(x, value) を満たすような最も左の位置を指すイテレータを返します。 Ο(log(r.length)) 回 less を呼び出します。参照： STL の lower_bound

Precondition:
isSorted!(less)(r)

Returns:
[begin(r), i) 内の p が全て less(*p, i) を満たすような i

Example:
int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ];
auto p = lowerBound!(less)(a, 4);
assert(*p == 4);
p = lowerBound(a, 4); // デフォルトはlessを使用
assert(*p == 4);
p = lowerBound!("a < b")(a, 4); // 文字列で述語指定
assert(*p == 4);


Iterator!(Range) upperBound(alias less = "a < b",Range,V)(Range r, V value);
r のなかで、 それより左の要素 x は全て !less(value, x) を満たすような最も右の位置を指すイテレータを返します。 Ο(log(r.length)) 回 less を評価します。参照： STL の upper_bound.

Precondition:
isSorted!(less)(r)

Returns:
[begin(r), i) 内の p が全て !less(value, *p) を満たすような i

Example:
auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ];
auto p = upperBound(a, 3);
assert(p == begin(a) + 5);


Range equalRange(alias less = "a < b",Range,V)(Range r, V value);
equalRange!(less)(r, v) を呼び出すと、range(lowerBound!(less)(r, v), upperBound!(less)(r, v)) を返します。 ただし二つの関数を呼び出すよりは効率的な実装となっています。Ο(log(r.length)) 回 less を呼び出します。参照： STL の equal_range

Precondition:
isSorted!(less)(range)

Returns:
全ての要素 p が !less(*p, value) && !less(value, *p) を満たすような r の最大の部分レンジ

Example:
auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ];
auto r = equalRange(a, 3);
assert(r == [ 3, 3, 3 ]);


bool canFindSorted(alias less = "a < b",T,V)(T range, V value);
ソート済みレンジ range の中に value が存在すると true を返します。Ο(log(r.length)) 回 less を呼び出します。参照： STL の binary_search。

void makeHeap(alias less = "a < b",alias iterSwap = .iterSwap,Range)(Range r);
レンジ r をヒープに変換します。Ο(r.length) 回 less を呼び出します。

void popHeap(alias less,alias iterSwap = .iterSwap,Range)(Range r);
popHeap

void sortHeap(alias less,alias iterSwap = .iterSwap,Range)(Range r);
sortHeap

void topNCopy(alias less,alias iterSwap = .iterSwap,SRange,TRange)(SRange source, TRange target);
topNCopy

void partialSortCopy(alias less,alias iterSwap = .iterSwap,SRange,TRange)(SRange source, TRange target);
partialSortCopy