2010/11/29

Objective-C上でブロックオブジェクトによる高階関数を用いてソートする方法について

iOS 4.0以降 (Mac OS Xなら10.6以降) で利用可能になったブロックオブジェクトは他の言語でのクロージャに相当するものです。ブロックオブジェクトはC, C++, Objective-Cで利用可能であり、Appleの並列実行アーキテクチャGrand Central Dispatchにおける基盤要素にもなっています。

ブロックオブジェクトはスタック上に生成されるため、copyによってヒープに移動させて破棄されないようにする必要があります (そして、使用後に破棄されるようにするためにautoreleaseさせる必要があります)。しかし、その点に注意さえすれば戻り値をブロックオブジェクトにした高階関数を利用することができます。

この記事ではObjective-Cにおいて、ブロックオブジェクトで高階関数を用いることで比較用のブロックオブジェクトを作成し、それを用いてオブジェクトのソートを行う方法を紹介します。

ブロックオブジェクトの概要

次のインタフェースを持つクラスFileがあり、その配列Arrayがあるとします。

@interface File { /* ... */ }
@property NSString* name;
@property BOOL isDirectory;
@property long size
@end

この配列をnameでソートするときに、比較のためにブロックオブジェクト (以下、単にブロックとする) を利用するならsortedArrayUsingComparator:を使うことになります。ブロックはサーカムフレックス ^ で始まり、引数と本体がその後に続きます。

NSComparator comp = ^(id a, id b) {
    return [[a name] compare:[b name]];
}
NSArray* sortedArray = [array sortedArrayUsingComparator:comp];

ここで、NSComparatorは次のようにtypedefされています。

typedef NSComparisonResult (^NSComparator)(id obj1, id obj2);

高階関数

ここでは、高階関数を関数 (ブロック) を返す関数という意味で用いています。よくある単純な利用例としては次のようになります。

typedef int (^mulBlock)(int);

mulBlock makeMul(int x) {
    return [[ ^(int y) {
        return x * y;
    } copy] autorelease];
}

int main() {
    mulBlock mul5 = makeMul(5);
    printf("%d\n", mul5(4)); // 20
}

ファイルソートの問題

ファイルをソートする際に問題となるのは、そのソート種類の豊富さです。ソート基準としてファイル名、ファイルサイズ、拡張子、更新日などがあり、それ以外にも次のようなものも考慮する必要があります。

  • 拡張子や更新日などが一致するときには別の基準 (ファイル名など) でソートする
  • ファイル名で、アルファベットの大文字と小文字を区別するのか
  • フォルダとファイルを一緒にしてソートするのかどうか
  • ソートの昇順、降順

安定なソートを用いて、これらの基準を用いて順番にソートする方法もありますが、複数回ソートする必要があります。

ファイルソートにおける高階関数の利用

ある基準で比較し、同値になった場合は下位の基準としてNSComparator型のブロックfを用いるようなブロックを作成する関数を用意します。ここでは、ファイル名の比較 (compByName, compByIName) はベースレベルとしており、ブロックを返す関数にはしていません。

NSComparisonResult (^compByName)(id, id) = ^(id a, id b) {
    return [[a name] compare:[b name]];
};

NSComparisonResult (^compByIName)(id, id) = ^(id a, id b) {
    return [[a name] caseInsensitiveCompare:[b name]];
};

NSComparator makeCompByDir(NSComparator f) {
     return [[ ^(id a, id b) {
        BOOL adir = [a isDirectory];
        BOOL bdir = [b isDirectory];
        if (adir == bdir) return f(a, b);
        return (adir && ! bdir)? NSOrderedAscending : NSOrderedDescending;
    } copy] autorelease];    
}

NSComparator makeCompBySize(NSComparator f) {
     return [[ ^(id a, id b) {
        long av = [a size];
        long bv = [b size];
        if (av == bv) return f(a, b);
        return av < bv? NSOrderedAscending : NSOrderedDescending;
    } copy] autorelease];
}

NSComparator makeCompByKind(NSComparator f) {
     return [[ ^(id a, id b) {
        NSComparisonResult res = [[a name].pathExtension 
           caseInsensitiveCompare:[b name].pathExtension];
        return res == NSOrderedSame? f(a, b) : res;
    } copy] autorelease];    
}

これらを用いて、(1) フォルダとファイルを別にして、(2) 拡張子でソートし、(3) 同一拡張子内はファイル名でソート (大文字と小文字を区別) する場合には次のように書くことができます。

sorted = [array sortedArrayUsingComparator:makeCompByDir(makeCompByKind(compByName))];

まとめ

Objective-Cにおいて、ブロックオブジェクトで高階関数を用いてオブジェクトのソートを行う方法を紹介しました。

関連項目


0 件のコメント:

コメントを投稿

注: コメントを投稿できるのは、このブログのメンバーだけです。