2011年2月28日月曜日

NSArray/NSMutableArrayから重複要素を削除する

NSArrayNSMutableArrayには重複する要素を取り除くメソッドが用意されていない。要素の順序がどうなってもいいなら、NSSetが重複を許さないことを利用して

[[NSSet setWithArray:array] allObjects];

とすることもできるけど、そうでない場合も多々ある。また、セレクタやBlocksで等値判定をしたいこともある。

(追記)iOS 5からはNSOrderedSetが使えるので

[[NSOrderedSet orderedSetWithArray:array] array];

で、順序を保ったまま重複要素の削除ができる。セレクタやBlocksで等値判定を行う場合は下記参照。

NSMutableArray

ということでカテゴリで実装することにした。とりあえずNSMutableArrayから。

- (void)removeDuplicateObjects
{
    NSMutableIndexSet* removedIndexes = [[NSMutableIndexSet alloc] init];
    NSMutableSet* set = [[NSMutableSet alloc] init];
    const NSUInteger count = [self count];
    for (NSUInteger i = 0; i < count; i++) {
        id object = [self objectAtIndex:i];
        if ([set containsObject:object]) {
            [removedIndexes addIndex:i];
        } else {
            [set addObject:object];
        }
    }
    [set release];
    [self removeObjectsAtIndexes:removedIndexes];
    [removedIndexes release];
}

等値判定はもちろん–isEqual:で行われるのだけど、高速化のためNSSetを利用しているので、–hashも適切に定義されている必要がある(最初に挙げたNSSetNSOrderedSetを使った例も–isEqual:–hashが必要)。また、重複要素のうち前にあるほうを残すため、逆向きにループしながら削除する方法は使えずNSMutableIndexSetを使用した。

次に等値判定をセレクタで行う場合。こちらは後ろからループして、各要素について重複要素がないか一つずつ調べていき、見つかればただちに削除している。

- (void)removeDuplicateObjectsUsingSelector:(SEL)selector
{
    for (NSUInteger i = [self count]; i > 0; i--) {
        id object = [self objectAtIndex:i - 1];
        BOOL (*imp)(id, SEL, id) = (BOOL(*)(id, SEL, id))[object methodForSelector:selector];
        for (NSUInteger j = 0; j < i - 1; j++) {
            if (imp(object, selector, [self objectAtIndex:j])) {
                [self removeObjectAtIndex:i - 1];
                break;
            }
        }
    }
}

セレクタの返り値がBOOLなのでIMPを取り出して関数呼び出しを行っているけど、それについてはperformSelectorで返り値がid型以外のメソッドを呼ぶを参照。if文の条件式にperformSelectorの返り値をそのまま使ったら常に真になってしまう場合があって、バグの発見に時間がかかってしまった。

Blocksを使うとこんな感じになる。

- (void)removeDuplicateObjectsUsingBlock:(BOOL (^)(id a, id b))block
{
    for (NSUInteger i = [self count]; i > 0; i--) {
        id object = [self objectAtIndex:i - 1];
        for (NSUInteger j = 0; j < i - 1; j++) {
            if (block(object, [self objectAtIndex:j])) {
                [self removeObjectAtIndex:i - 1];
                break;
            }
        }
    }
}

NSArray

NSArrayの場合はカテゴリで

- (NSArray*)arrayByRemovingDuplicateObjects
{
    NSMutableArray* mutableCopy = [self mutableCopy];
    [mutableCopy removeDuplicateObjects];
    NSArray* uniqueElements = [NSArray arrayWithArray:mutableCopy];
    [mutableCopy release];
    return uniqueElements;
}

のように定義すればいいと思う。自分は必要なかったため実装していないけど、セレクタやBlocksを使う場合も同じようにして簡単に書ける。

テスト

Xcode 3.2.5 and iOS SDK 4.2で確認した。

@interface NSString (Private)
- (BOOL)isCaseInsensitiveEqualToString:(NSString*)other;
@end

@implementation NSString (Private)
- (BOOL)isCaseInsensitiveEqualToString:(NSString*)other
{
    return [self compare:other options:NSCaseInsensitiveSearch] == NSOrderedSame;
}
@end

@interface NSMutableArrayUniqueTest : SenTestCase
@end

@implementation NSMutableArrayUniqueTest

- (void)testRemoveDuplicateObjects
{
    NSMutableArray* array;
    NSMutableArray* expected;
    
    array = [NSMutableArray array];
    [array removeDuplicateObjects];
    expected = [NSMutableArray array];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObject:@"a"];
    [array removeDuplicateObjects];
    expected = [NSMutableArray arrayWithObject:@"a"];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObjects:@"a", @"b", nil];
    [array removeDuplicateObjects];
    expected = [NSMutableArray arrayWithObjects:@"a", @"b", nil];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObjects:@"a", @"a", nil];
    [array removeDuplicateObjects];
    expected = [NSMutableArray arrayWithObject:@"a"];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObjects:@"a", @"b", @"a", @"b", nil];
    [array removeDuplicateObjects];
    expected = [NSMutableArray arrayWithObjects:@"a", @"b", nil];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObjects:@"a", @"b", @"a", @"a", @"b", @"c", nil];
    [array removeDuplicateObjects];
    expected = [NSMutableArray arrayWithObjects:@"a", @"b", @"c", nil];
    STAssertEqualObjects(expected, array, @"");
}

- (void)testRemoveDuplicateObjectsUsingBlock
{
    NSMutableArray* array;
    NSMutableArray* expected;
    BOOL (^block)(id, id) = ^BOOL(id a, id b) {
        return [a compare:b options:NSCaseInsensitiveSearch] == NSOrderedSame;
    };
    
    array = [NSMutableArray array];
    [array removeDuplicateObjectsUsingBlock:block];
    expected = [NSMutableArray array];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObject:@"a"];
    [array removeDuplicateObjectsUsingBlock:block];
    expected = [NSMutableArray arrayWithObject:@"a"];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObjects:@"a", @"b", nil];
    [array removeDuplicateObjectsUsingBlock:block];
    expected = [NSMutableArray arrayWithObjects:@"a", @"b", nil];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObjects:@"a", @"A", nil];
    [array removeDuplicateObjectsUsingBlock:block];
    expected = [NSMutableArray arrayWithObjects:@"a", nil];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObjects:@"a", @"B", @"A", @"b", nil];
    [array removeDuplicateObjectsUsingBlock:block];
    expected = [NSMutableArray arrayWithObjects:@"a", @"B", nil];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObjects:@"a", @"B", @"A", @"a", @"b", @"c", nil];
    [array removeDuplicateObjectsUsingBlock:block];
    expected = [NSMutableArray arrayWithObjects:@"a", @"B", @"c", nil];
    STAssertEqualObjects(expected, array, @"");
}

- (void)testRemoveDuplicateObjectsUsingSelector
{
    NSMutableArray* array;
    NSMutableArray* expected;
    
    array = [NSMutableArray array];
    [array removeDuplicateObjectsUsingSelector:@selector(isCaseInsensitiveEqualToString:)];
    expected = [NSMutableArray array];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObject:@"a"];
    [array removeDuplicateObjectsUsingSelector:@selector(isCaseInsensitiveEqualToString:)];
    expected = [NSMutableArray arrayWithObject:@"a"];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObjects:@"a", @"b", nil];
    [array removeDuplicateObjectsUsingSelector:@selector(isCaseInsensitiveEqualToString:)];
    expected = [NSMutableArray arrayWithObjects:@"a", @"b", nil];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObjects:@"a", @"A", nil];
    [array removeDuplicateObjectsUsingSelector:@selector(isCaseInsensitiveEqualToString:)];
    expected = [NSMutableArray arrayWithObjects:@"a", nil];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObjects:@"a", @"B", @"A", @"b", nil];
    [array removeDuplicateObjectsUsingSelector:@selector(isCaseInsensitiveEqualToString:)];
    expected = [NSMutableArray arrayWithObjects:@"a", @"B", nil];
    STAssertEqualObjects(expected, array, @"");
    
    array = [NSMutableArray arrayWithObjects:@"a", @"B", @"A", @"a", @"b", @"c", nil];
    [array removeDuplicateObjectsUsingSelector:@selector(isCaseInsensitiveEqualToString:)];
    expected = [NSMutableArray arrayWithObjects:@"a", @"B", @"c", nil];
    STAssertEqualObjects(expected, array, @"");
}
@end