Lately, I’ve found myself creating a lot of table views that look like this:

Grouped Table View

A plain-jane table view filled with homogenous items grouped by some common element.  I couldn’t help but notice how ill-suited the standard NS data structures are for handling this.  It always involves some sorted array containing the keys of a dictionary which is filled with sorted arrays.  The setup for these is pretty standard and easily repeatable, so I submit to the community my IndexArray class which takes care of much of the boiler plate for you.  This is definitely rough around the edges as I only started putting this all together yesterday.

First some high level requirements:

• Everything should be sortable: keys and items.
• I want to be able to add and remove items without having to always resort.
• I want to be able to specify how the sort should occur.  I want this to be as convenient as sorting an array.
• I don’t want have to worry about the logic of whether a key has an array associated with it when I push items into it.
• Items should be easily accessible by index so it works rather seamlessly with UITableViews.
• Keys should have the same freedom as they do in NSDictionary.

Here’s my public interface as it stands now:

@property (nonatomic, assign) SEL keySortSelector;
@property (nonatomic, assign) SEL objectSortSelector;
@property (nonatomic, copy) NSComparator keySortComparator;
@property (nonatomic, copy) NSComparator objectSortComparator;

// accessing keys
- (id)keyAtIndex:(NSUInteger)index;
- (NSOrderedSet *)allKeys;
- (NSUInteger)keyCount;

// accessing objects
- (id)objectForKeyAtIndex:(NSUInteger)keyIndex objectIndex:(NSUInteger)objIndex;
- (id)objectForKey:(id)key index:(NSUInteger)index;
- (NSArray *)allObjectsForKey:(id)key;
- (NSUInteger)count;

// adding objects
- (void)addObject:(id)object forKey:(id<NSCopying>)key;

// removing objects
- (void)removeObject:(id)object forKey:(id)key;

You can see that I’ve specified 2 ways to sort keys and items.  Since keys are usually strings, it’s uber convenient to simply hand the compare: selector to the data structure.  For what I’ve been working on the items are NSManagedObject subclasses, so I need something a little more powerful to maintain their order, so I can also send in a comparator block in the form:

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

Adding and removing objects is as simple as possible with:

// adding objects
- (void)addObject:(id)object forKey:(id<NSCopying>)key;

// removing objects
- (void)removeObject:(id)object forKey:(id)key;

Under the hood:

Here’s the rest of the interface:

@interface PZIndexedArray : NSObject
{
    @private
    NSMutableDictionary *dictionary_;
    NSMutableOrderedSet *orderedKeys_;
    
    SEL keySortSelector_;
    SEL objectSortSelector_;
    NSComparator keySortComparator_;
    NSComparator objectSortComparator_;
    
    BOOL sortsKeys_;
    BOOL sortsObjects_;
    BOOL usesComparatorForKeys_;
    BOOL usesComparatorForObjects_;
}

I’m using two data structures inside the class. First an NSDictionary that will contain mutable arrays for each key. Secondly an NSOrderedSet that will also contain every key. The ordered set will guarantee uniqueness of the keys and provide the ordering I need.

You can also see the selectors and comparators being stored. There’s also some flags to know whether the class should try to sort at all (we won’t if there’s neither a comparator nor a selector). In the implementation as I have it, the selector will take precedence over the comparator if both are provided for either keys or items.

The implementation is pretty straightforward. Setting a comparator or a selector automatically triggers the flags for sorting. There’s a setter for each one, but they all look basically like this:

- (void)setKeySortComparator:(NSComparator)keySortComparator
{
    if (keySortComparator != keySortComparator_)
    {
        [keySortComparator_ release];
        keySortComparator_ = Block_copy(keySortComparator);
    }
    
    sortsKeys_ = keySortComparator != nil;
}

Adding an object for a key is pretty simple. The mutable array is automatically created if no entry exists for a key.

// adding objects
- (void)addObject:(id)object forKey:(id<NSCopying>)key
{
    NSMutableArray *array = [dictionary_ objectForKey:key];
    if (!array)
    {
        array = [NSMutableArray array];
        [dictionary_ setObject:array forKey:key];
        
        if (sortsKeys_)
        {
            [self insertKeySorted:key];
        }
        else
        {
            [orderedKeys_ addObject:key];
        }
    }
    
    if (sortsObjects_)
    {
        [self insertObject:object array:array];
    }
    else
    {
        [array addObject:object];
    }
}

If there’s no sorting the on the keys, the key simply added to the set, otherwise it gets inserted in sorted order. Same goes for items. The sorted insert methods are pretty much the same both. The basic method is to iterate through the array until the object in the enumerator is greater than the object being inserted.

- (void)insertKeySorted:(id)key
{
    if ([orderedKeys_ count] == 0)
    {
        [orderedKeys_ addObject:key];
        return;
    }
    
    __block NSUInteger insertIndex = -1;
    __block NSInvocation *selectorInvocation = nil;
    if (!usesComparatorForKeys_)
    {
        selectorInvocation = [NSInvocation invocationWithMethodSignature:[key methodSignatureForSelector:keySortSelector_]];
        [selectorInvocation setTarget:key];
        [selectorInvocation setSelector:keySortSelector_];
    }
    
    [orderedKeys_ enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        if (idx  < [orderedKeys_ count])
        {     
            NSComparisonResult result = NSOrderedAscending;
            if (usesComparatorForKeys_)
            {
                result = self.keySortComparator(key, obj);
            }
            else
            {
                [selectorInvocation setArgument:&obj atIndex:2];
                [selectorInvocation invoke];
                [selectorInvocation getReturnValue:&result];
            }
            
            if (result == NSOrderedAscending)
            {
                insertIndex = idx;
                *stop = YES;
            }
                                
        }
    }];
    
    if (insertIndex == -1)
    {
        [orderedKeys_ addObject:key];
    }
    else
    {
        [orderedKeys_ insertObject:key atIndex:insertIndex];
    }
}

The result is adding items from an array into this data structure is much more compact and cleaner than maintaining the data structures yourself:

IndexedArray *byName = [[IndexedArray alloc] init];
byName.keySortSelector = @selector(compare:);
byName.objectSortComparator = ^NSComparisonResult(Document *doc1, Document *doc2) {
    return [[doc1.filename firstCharacterAsString] compare:[doc2.filename firstCharacterAsString]];
};
// firstCharacterAsString is a category I created.  

And it integrates nicely with the table view datasource methods:

- (NSInteger)numberOfSectionsInTableView:(UITableView *)tableView
{
    return [categoryIndex keyCount];
}

- (NSInteger)tableView:(UITableView *)tableView numberOfRowsInSection:(NSInteger)section
{
    return [categoryIndex allObjectsForKey:[categoryIndex keyAtIndex:section]];
}

- (NSString *)tableView:(UITableView *)tableView titleForHeaderInSection:(NSInteger)section
{
    return [categoryIndex keyAtIndex:section];
}

- (UITableViewCell *)tableView:(UITableView *)tableView cellForRowAtIndexPath:(NSIndexPath *)indexPath
{
    static NSString *identifier = @"cell";
    UITableViewCell *cell = [tableView dequeueReusableCellWithIdentifier:identifier];
    if (cell == nil)
    {
        cell = [[UITableViewCell alloc] initWithStyle:UITableViewCellStyleValue1 reuseIdentifier:identifier];
    }
    
    id item = [categoryIndex objectForKeyAtIndex:indexPath.section objectIndex:indexPath.row];
    cell.textLabel.text = [item filename];
    return cell;
}

The code for this is posted up GitHub. Please have a look and feel free to contribute back!