Zen言語の標準ライブラリ紹介〜sort②〜

はじめに

けっこう標準ライブラリが充実しているわけですが、ドキュメントがないのがもったいないですね。 まとまった時間が取れないので、ちょこちょこ書いていくシリーズです。

リクエストあれば、優先する、かも?

ソート関係ですが、ソート本体以外にstd.sortにあるものを紹介します。

std.sort.asc

<演算子が定義されている型Tに対して、fn (a: T, b: T) bool { return a < b } を計算する関数ポインタを返します。 コメントにあるように、sort()関数呼び出し時に引数渡しする比較関数を生成するために使います。

// Use these to generate a comparator function for a given type. e.g. `sort(u8, slice, asc(u8))`.
pub fn asc(comptime T: type) fn (T, T) bool
const std = @import("std");
const sort = std.sort;
const testing = std.testing;

test "std.sort.asc" {
    const asc_u8 = sort.asc(u8);
    // true if `a` is less than `b`
    testing.ok(asc_u8(1, 2));
    testing.ok(!asc_u8(2, 2));
    testing.ok(!asc_u8(2, 1));
}

実装は次の通りなのですが、a < bを返さずに、generic.lessThanを使えば、構造体にも使えるようになる気が…?

pub fn asc(comptime T: type) fn (T, T) bool {
    const impl = struct {
        fn inner(a: T, b: T) bool {
            return a < b;
        }
    };

    return impl.inner;
}

現状では、構造体の型を渡すとコンパイルエラーになります。 次はコンパイルエラーです。

test "std.sort.asc for struct" {
    const S = struct {
        a: usize,
        b: f64,
    };
    const asc_s = sort.asc(S);
}
error[E09063]: operator not allowed for type 'S'
            return a < b;
                     ~

後で修正リクエスト投げてみましょう。

std.sort.desc

ascの逆版です。 fn (a: T, b: T) bool { return a > b } を計算する関数ポインタを返します。

pub fn desc(comptime T: type) fn (T, T) bool
test "std.sort.desc" {
    const asc_u8 = sort.desc(u8);
    // true if `a` is bigger than `b`
    testing.ok(asc_u8(2, 1));
    testing.ok(!asc_u8(2, 2));
    testing.ok(!asc_u8(1, 2));
}

std.sort.min / std.sort.argMin

任意型のスライスの中で最も小さい値を返します。 スライスの要素数0の場合のみ、nullを返します。

pub fn min(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) ?T

最も小さい値が格納されているインデックスを返します。

pub fn argMin(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) ?usize

使い方は、次のような感じです。

test "std.sort.min" {
    const inputs = [_]i32{ 10, -5, 3, 20, -4 };
    testing.equal(@to(?i32, -5), sort.min(i32, &inputs, sort.asc(i32)));

    const position = sort.argMin(i32, &inputs, sort.asc(i32));
    testing.equal(@to(?usize, 1), position);
    testing.equal(@to(i32, -5), inputs[position.?]);
}

std.sort.max / std.sort.argMax

minのmax版です。

std.sort.isSorted

与えたスライスがソート済みかどうかをブール値で返します。

pub fn isSorted(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) bool
test "std.sort.isSorted" {
    const sorted = [_]i32{ -1, 0, 1, 2, 3, 4, 5 };
    const unsorted = [_]i32{ 2, 0, 1, -1, 3, 4, 5 };

    testing.ok(sort.isSorted(i32, &sorted, sort.asc(i32)));
    testing.ok(!sort.isSorted(i32, &unsorted, sort.asc(i32)));
}