Get NSIndexSet from NSArray

Question

NSArray has useful methods to find objects for specified indexes

// To find objects by indexes
- (id)objectAtIndex:(NSUInteger)index
- (NSArray *)objectsAtIndexes:(NSIndexSet *)indexes

// To find index by object
- (NSUInteger)indexOfObject:(id)anObject

However, I want to get NSIndexSet (multiple indexes) for given objects. Something like:

- (NSIndexSet *)indexesOfObjects:(NSArray *)objects

This method does not exist for NSArray. Am I missing something? Does someone know another standard method? Otherwise I have to write this as a category method.

Solution 1

It might be useful to implement it using a set to specify the objects to find, such as:

- (NSIndexSet *) indicesOfObjectsInSet: (NSSet *) set
{
    if ( [set count] == 0 )
        return ( [NSIndexSet indexSet] );

    NSMutableIndexSet * indices = [NSMutableIndexSet indexSet];

    NSUInteger index = 0;
    for ( id obj in self )
    {
        if ( [set containsObject: obj] )
            [indices addIndex: index];

        index++;
    }

    return ( [[indices copy] autorelease] );
}

This requires visiting every object in the array, but at least only does so once and makes use of fast enumeration while doing so. Using an NSSet and testing each object in the array against that set is also much faster than testing for inclusion in an array.

There's a potential optimization here, but it would break in the case where a single object is stored in the receiving array multiple times:

if ( [set containsObject: obj] )
{
    [indices addIndex: index];
    if ( [indices count] == [set count] )
        break;
}

That way if you're scanning a 20'000-item array for two objects and they're both inside the first ten, you'll be able to avoid scanning the other 19'990 objects in the array. As I said though, that doesn't help if the array contains duplicates, because it'll stop as soon as it's found 2 indices (even if they both point to the same object).

Having said that, I agree with Mike's comment above. Chances are you're setting yourself up for some pain come optimization-time. It may be worth thinking about different data types; for instance, while NSArray seems the most logical choice for a simple flat container, if you don't actually need the ordering information it's better to use an NSSet instead; this has the added advantage that it won't store the same object (calculated using -isEqual:) twice. If you do want to keep track of duplicates, but don't need ordering, you can use NSCountedSet, which behaves as NSSet except it keeps track of how many times each objects has been added/removed without actually storing duplicates.

Solution 2

Newer NSArray versions (OSX 10.6 and iOS 4) provides the indexesOfObjectsPassingTest: method.

NSIndexSet *indexesOfObjects = [[array1 indexesOfObjectsPassingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop) {
    return [array2 containsObject:obj];
}];

Solution 3

You have to implement your own category, as far as I can see.

Comments

[Mike Abdullah]

Note though that wanting this method is a strong sign of a design flaw. -indexOfObject: works by searching through every object in the array and thus becomes quite slow for a large array or multiple searches. Rethink your data structures for something more sensible.

[Quinn Taylor]

+1 Just a minor note: both "indexes" and "indices" are correct in English, but Cocoa always uses "indexes", so it's better to keep to that terminology, at least for the method name.