Xtalの配列を、std::sortでソートする

xtal::Array::iteratorはSTLのイテレータの要件を満たしていませんし、ラップするイテレータを実装するのも面倒くさいのですが、ポインタはSTLのイテレータの用件を満たすため、Xtalの配列が

• 連続領域を使用している
• 最初と最後（正確には最後の次）を指すポインタを取得できる

の2つの条件を満たしていれば、STLのalgorithmを利用できることになります。

前者は（コード読むと）満たしていることがわかります。後者は、次のようにすることによって取得できます。

AnyPtr* begin = &*array->begin();
AnyPtr* end = &*array->end();

xtal::Array::begin, xtal::Array::endはそれぞれ最初と最後の要素を指すイテレータを返すので、それのアドレスを取得することによって最初と最後の要素を指すポインタを得ることができました。

これでSTLのalgorithmを利用する準備ができました。実際にstd::sortでソートしてみます。

#include <xtal.h>
#include <xtal_macro.h>
 
#include <xtal_lib/xtal_cstdiostream.h> 
#include <xtal_lib/xtal_winthread.h>
#include <xtal_lib/xtal_winfilesystem.h>
#include <xtal_lib/xtal_chcode.h>
#include <xtal_lib/xtal_errormessage.h>
 
#include <algorithm>
#include <functional>
 
#pragma comment(lib, "xtallib.lib")
 
struct IntArraySortPred : public std::binary_function<bool, xtal::AnyPtr, xtal::AnyPtr>{
    bool operator ()(const xtal::AnyPtr& plh, const xtal::AnyPtr& prh) const{
        const int lh = xtal::unchecked_cast<int>(plh);
        const int rh = xtal::unchecked_cast<int>(prh);
        return lh < rh;
    }
};
 
void SortArray(const xtal::ArrayPtr& array){
    std::sort(&*array->begin(), &*array->end(), IntArraySortPred());
}
 
void bind_xtal(){
    using namespace xtal;
}
void exec_xtal(){
    using namespace xtal;
 
    const CodePtr code(compile_file("test.xtal"));
    if (code){
        code->def_fun(Xid(sort), &SortArray);
        code->call();
    }
}
 
int main(int argc, char* argv[]){
    using namespace xtal;
 
    CStdioStdStreamLib std_stream_lib;     // std*はCの標準ライブラリを使う
    WinThreadLib thread_lib;               // Windowsのスレッドを使う
    WinFilesystemLib filesystem_lib;       // Windowsのファイルシステムを使う
    SJISChCodeLib ch_code_lib;             // SJISを使う
 
    Setting setting; 
    setting.std_stream_lib = &std_stream_lib;
    setting.thread_lib = &thread_lib;
    setting.filesystem_lib = &filesystem_lib;
    setting.ch_code_lib = &ch_code_lib;
 
    // Xtalを初期化
    initialize(setting);
    bind_error_message();
 
    bind_xtal();
    exec_xtal();
    XTAL_CATCH_EXCEPT(e){
        stderr_stream()->println(e->to_s());
    }
 
    // Xtalを破棄
    uninitialize();
 
    return 0;
}

// test.xtal
fun make_random_values(n){
    a : Array(n);
    for (i : 0; i < n; ++i){
        a[i] = (math::random()*1000000000).to_i;
    }
 
    return a;
}
array : make_random_values(100);
array.p;
sort(array);
array.p;

以下ちょっとした解説と注意点。

struct IntArraySortPred : public std::binary_function<bool, xtal::AnyPtr, xtal::AnyPtr>{
    bool operator ()(const xtal::AnyPtr& plh, const xtal::AnyPtr& prh) const{
        const int lh = xtal::unchecked_cast<int>(plh);
        const int rh = xtal::unchecked_cast<int>(prh);
        return lh < rh;
    }
};

このようなPredicateを作成することにより、高速に比較することができ、sortをより高速に処理することができます。ただし、intでなくfloatのソートしたいときなどは、xtal::unchecked_cast<float>などのようにその型に合わせた型にキャストする必要があります。
operator < を定義してあるクラスであればPredicateをtemplateクラスにすることでより一般化することもできるでしょう。

template<class T>
struct ArraySortPred : public std::binary_function<bool, xtal::AnyPtr, xtal::AnyPtr>{
    bool operator ()(const xtal::AnyPtr& plh, const xtal::AnyPtr& prh) const{
        const T& lh = xtal::unchecked_cast<T>(plh);
        const T& rh = xtal::unchecked_cast<T>(prh);
        return lh < rh;
    }
};
 
...
 
std::sort(begin, end, ArraySortPred<int>());

なお、Xtalオブジェクトに作用させる際にもっとも一般的（たぶん？）なPredicateを用意するとしたら、

struct ArraySortPred : public std::binary_function<bool, xtal::AnyPtr, xtal::AnyPtr>{
    bool operator ()(const xtal::AnyPtr& lh, const xtal::AnyPtr& rh) const{
        return lh->send(Xid(op_lt), rh);
    }
};

のようになりますが、これはXtalの処理系を通して比較を処理することになるためにかなり遅くなってしまいます。型がわかっているときにはなるべくC++での比較をできるようなPredicateを用意するのが良いでしょう。

逆に言えば、op_ltを実装していればXtalで定義したクラスでもこのような関数オブジェクトを定義することでSTLの関数を利用することができる、ということでもあります。