2010-04-14

iPhoneアプリ開発: objective-cでのqueueやstack

iPhoneアプリ内で、データ構造としてqueueを利用したい場合、それそのものなクラス(例えばJavaにおけるjava.util.Queueの実装クラス)は存在しないようです。ただ、Cocoa FoundationフレームワークのNSMutableArrayを利用すると、容易に実装できます。
※ちなみにリスト1のQueueクラスはマルチスレッド対応をしてあります。

リスト1. queueの実装
//Queue.h

@interface Queue : NSObject {
    NSMutableArray *queue;
    int maxSize;
}
- (id)initWithSize:(int)maxSize;
- (id)dequeue;
- (void)enqueue:(id)anObject ;
- (int)count;
@end


//Queue.m

@implementation Queue

- (id)initWithSize:(int)aMaxSize;
    self = [super init];
    if (self != nil) {
        queue = [[NSMutableArray alloc] init];
        maxSize = aMaxSize;
    }
    return self;
}

- (id)dequeue { 
    id headObject;
    @synchronized(q){
        if ([queue count] == 0) return nil;
        id headObject = [queue objectAtIndex:0];
        if (headObject != nil) {
            [[headObject retain] autorelease];
            [queue removeObjectAtIndex:0];
        }
    }
    return headObject;
}

- (void)enqueue:(id)anObject {
    @synchronized(q){
        if (anObject == nil) {
            return;
        }
        if ([q count] >= maxSize) {
            [q removeObjectAtIndex:0];
        }
        [q addObject:anObject];
    }
}

- (int)count {
    int c = 0;
    @synchronized(q) {
        c = [q count];
    }
    return c;
}

このコードではQueueクラスを作成していますが、objective-cのカテゴリ機構を利用して、NSMutableArrayにQueueのために必要なメソッドを追加することで、Queue実装を実現することもできます。

リスト2. カテゴリ機構を利用したqueueの実装
//NSMutableArray+QueueAdditions.h

@interface NSMutableArray (QueueAdditions)
- (id) dequeue;
- (void) enqueue:(id)obj;
@end


//NSMutableArray+QueueAdditions.m

@implementation NSMutableArray (QueueAdditions)
// Queues are first-in-first-out, so we remove objects from the head
- (id) dequeue {
    // if ([self count] == 0) return nil; // to avoid raising exception (Quinn)
    id headObject = [self objectAtIndex:0];
    if (headObject != nil) {
        [[headObject retain] autorelease]; // so it isn't dealloc'ed on remove
        [self removeObjectAtIndex:0];
    }
    return headObject;
}

// Add to the tail of the queue (no one likes it when people cut in line!)
- (void) enqueue:(id)anObject {
    [self addObject:anObject];
    //this method automatically adds to the end of the array
}
@end
How do I make and use a Queue in Objective-C? - Stack Overflowより引用)

queueを使いたいときは、NSMutableArrayのメソッド利用方法と同様にqueue用のメソッドを利用できます。
import "NSMutableArray+QueueAdditions.h"

NSMutableArray queue;
NSData data = [[NSData alloc] init];

queue = [[NSMutableArray alloc] init];
[queue enqueue:data];
data = [queue dequeue];

リスト2の引用元サイトに、同様にstackの実装コードもあったので、ついでに記載しておきます。

リスト3. カテゴリ機構を利用したstackの実装
//NSMutableArray+StackAdditions.h

@interface NSMutableArray (StackAdditions)

- (id)pop;
- (void)push:(id)obj;

@end


//NSMutableArray+StackAdditions.m

@implementation NSMutableArray (StackAdditions)

- (id)pop
{
    // nil if [self count] == 0
    id lastObject = [[[self lastObject] retain] autorelease];
    if (lastObject)
        [self removeLastObject];
    return lastObject;
}

- (void)push:(id)obj
{
     [self addObject: obj];
}
@end
How do I make and use a Queue in Objective-C? - Stack Overflowより引用)

ちなみにカテゴリとは…
カテゴリはメソッドのコレクションを定義して、クラス定義後に追加オーバーライドを行なう機構。

特徴的なのは、メソッドのオーバーライドが、カテゴリがロードされたタイミングで実行時に行われるという点で、これにより外部モジュールで基盤モジュールを置き換える事ができる。従ってカテゴリを用いればオリジナルコードの再コンパイルなしにルートクラスの挙動を変更する事さえ可能となる。また機能追加のためだけのサブクラス化を行なう必要がなくなる点は特筆に値する。

カテゴリが上述のInformalプロトコルに利用できるのは、ロードが実行時に行われるという構造上、コードのリンク時に実装が存在する保証がなく、インターフェースのみが先行する形になることから。

応用範囲は非常に広く、単純にクラス定義を複数の機能クラスターから構成するために用いる事もあれば、先に挙げたフレームワークのパッチや Informalプロトコルに用いるケースなど多岐にわたる。プログラムの可読性や設計のしやすさ全般に貢献しており、Objective-Cプログラマの間では「Javaの最大の弱点はカテゴリがないこと」などとささやかれるほどである。
Wapedia - Wiki: Objective-Cより引用)

1 件のコメント:

tokentoken さんのコメント...

Objective-C Queue で検索してここにきました。
リスト1で、
@synchronized(q){
などいきなり q が現れていますが queue のことですね。
一応お知らせです。