比較関数つきsort

最近、STLをD言語へポーティングするみたいな作業をしている。
DTLがあるじゃないかと言われそうだが、DTLは bind2nd など足りないものが多い。

D言語組み込みの動的配列と連想配列だけでコンテナはすませようと思ってるので iterator もポーティングする気はしない。
algorithm は大変なので全部やる気はしないが、functional はやりやすかった。

D言語の組み込み配列だけでは足りない機能として、比較関数つき sort がある。
配列の sort プロパティでは比較関数が opCmp しか使えないので、

class C {
    int id;
    char[] name;
}

といったクラスが要素の配列を、id で sort したり、name で sort したりするには、opCmp から function を呼び出す形にして、function を比較する前に切り替えるなどのしかけが必要になってしまう。

しかもその function をインスタンスメンバにすれば、sort 前に配列内の全要素切り替えなければならないし、static メンバにすれば、id で sort したとき name で sort されている配列は「間違った状態」ということになってしまう。

比較関数をクラスまたはインスタンスの「状態」として恒久的に持つというのはよい考えではなく、sort する時点で指定するものだろう。

そのためのコード。

template swap(T) {
    void swap(inout T v1, inout T v2) {
        T tmp = v1;
        v1 = v2;
        v2 = tmp;
    }
}

template sort(T, O) {
    T[] sort(inout T[] array, O comp)
        in {
            static assert(
            /*
                is (O == int function(T, T)) ||
                is (O == int delegate(T, T)) ||
                is (typeof(O.opCall(T,T)) == int())
            */
                is (typeof(O(T,T)) == int())
            );
        }
        body {  // 20年前に専門ガッコで習ったダサいソート
            for (size_t i = 0; i < array.length - 1; ++i) {
                for (size_t j = i + 1; j < array.length; ++j) {
                    if (comp(array[i], array[j]) > 0) {
                        swap(array[i], array[j]);
                    }
                }
            }
            return array;
        }
}

sort のテンプレート型引数と関数引数が２つあるが、これは無関係なものではないので、契約が必要である。
その契約だが、

                is (typeof(O(T,T)) == int())

の１行で、function, delegate, 関数オブジェクトの３つをまとめて面倒見ることができる。
もっともこれだと、これを見た人が function, delegate には思いが至っても、「関数オブジェクトもオッケーよ」ということが見えにくいので、コメントアウトしている律儀なバージョンの契約を使うのも悪くない。

C++ のテンプレートだと、型に対する要求が実装のあちこちにちらばってしまい、インスタンス化したときにわけの解らないメッセージ読まされることがあるが、D言語のだと要求を一箇所に明記できて便利である。STL の中見ると concept クラスをいっぱい定義してがんばってるみたいだけど。

あと組み込み配列のプロパティと同名の関数を定義して、

    array.sort(compFunc);

と呼ばせることができるかな？と心配だったが、ちゃんとディスパッチしてくれとるようです。
でもこれだと

「array」が「compFunc」を「sort」する

みたいに読めるので、

    array.sortBy(compFunc);

とかすべきだべか。

ともあれ実験。

import std.string;

// ソート対象クラス
class C {
    int id;
    char[] name;
    this(int id, char[] name) { this.id = id; this.name = name.dup; }
    char[] toString() {
        return "{" ~ std.string.toString(id) ~ "," ~ name ~ "}";
    }
    static C opCall(int id, char[] name) { return new C(id, name); }
}

// 比較関数群
template CCompare() {
    int cmpId(C lhs, C rhs)     // idでソート
        { return lhs.id - rhs.id; }
    int cmpName(C lhs, C rhs)   // nameでソート
        { return std.string.cmp(lhs.name, rhs.name); }
    int icmpName(C lhs, C rhs)  // nameで大文字小文字を区別しないでソート
        { return std.string.icmp(lhs.name, rhs.name); }
}

// 比較関数を持つオブジェクト
class CComparator {
    // 比較関数群をメンバ関数としてインスタンス化
    mixin CCompare;
    static CComparator opCall() { return new CComparator(); }
}

// 比較関数オブジェクト
class CCompareFunctor {
    int function(C, C) fpCompare;
    this(int function(C, C) fp) { fpCompare = fp; }
    int opCall(C lhs, C rhs) { return fpCompare(lhs, rhs); }
    static CCompareFunctor opCall(int function(C, C) fp) {
        return new CCompareFunctor(fp);
    }
}

// 比較関数をグローバル領域でインスタンス化
mixin CCompare;

ここまでが sort 材料。
結構長いですね。

以下ドライバ

import house.array;
import house.mbs;
import std.stdio;
import std.cstream;

void main() {

    C[] array = Array!(C)(
        C(3, "bbb"),
        C(2, "ccc"),
        C(1, "aaa"),
        C(6, "BBB"),
        C(5, "CCC"),
        C(4, "AAA")
    );
    writefln(array);

    dout.writeLine(_T("function でソート"));
    writefln(array.sort(&cmpId));
    writefln(array.sort(&icmpName));
    writefln(array.sort(&cmpName));

    dout.writeLine(_T("delegate でソート"));
    writefln(array.sort(&CComparator().cmpId));
    writefln(array.sort(&CComparator().cmpName));
    writefln(array.sort(&CComparator().icmpName));

    dout.writeLine(_T("関数オブジェクト でソート"));
    writefln(array.sort(CCompareFunctor(&cmpId)));
    writefln(array.sort(CCompareFunctor(&cmpName)));
    writefln(array.sort(CCompareFunctor(&icmpName)));
}

実行結果。

C:\d\test>dmd ..\house\mbs -run sort
[{3,bbb},{2,ccc},{1,aaa},{6,BBB},{5,CCC},{4,AAA}]
function でソート
[{1,aaa},{2,ccc},{3,bbb},{4,AAA},{5,CCC},{6,BBB}]
[{1,aaa},{4,AAA},{3,bbb},{6,BBB},{5,CCC},{2,ccc}]
[{4,AAA},{6,BBB},{5,CCC},{1,aaa},{3,bbb},{2,ccc}]
delegate でソート
[{1,aaa},{2,ccc},{3,bbb},{4,AAA},{5,CCC},{6,BBB}]
[{4,AAA},{6,BBB},{5,CCC},{1,aaa},{3,bbb},{2,ccc}]
[{4,AAA},{1,aaa},{6,BBB},{3,bbb},{5,CCC},{2,ccc}]
関数オブジェクト でソート
[{1,aaa},{2,ccc},{3,bbb},{4,AAA},{5,CCC},{6,BBB}]
[{4,AAA},{6,BBB},{5,CCC},{1,aaa},{3,bbb},{2,ccc}]
[{4,AAA},{1,aaa},{6,BBB},{3,bbb},{5,CCC},{2,ccc}]

よかじゃないですか。

ちなみに、icmp による文字の大小無視 sort 結果が２通りあるが、これは「安定ソート」なので、同一カテゴリ内の前後関係が sort 以前のものを保持しているためです。
組み込み配列プロパティの sort は残念ながら安定ソートではないようです。

こうなると比較関数だけでなく、アルゴリズムも sort に渡したいが、比較関数はアルゴリズムが呼び出すものなので、

    array.sort(algorithm(compfunc));

というコール形式になってしまう。

sort に比較関数を渡したい状況は多々あるかもだが、アルゴリズムを渡したい状況はそんなにないのよね。だが上記の形式だと、デフォルト(型)引数を使ってアルゴリズムを省略してコールすることはできない。
とすると、STL にならって、

    array.stable_sort(compfunc);
    array.merge_sort(compfunc);
    array.bubble_sort(compfunc);

とやるべきなのでしょうね。