A Better Table View Data Structure

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!

Some Love for Data Structures

NSArray.  NSDictionary.  NSSet.  So common.  So ordinary.  Or are they really?

You probably use tons of these every day.  You probably write them without even thinking about them.  They are the foundation of any (interesting) iOS application.  Rarely do we ever think about what they are.  Who are these creatures?  What do they do? In short they’re data structures.  The foundation of an application and the bane of every computer science undergrad.

It’s often difficult to find good topics to blog about, especially when you’re in the middle of bug-fix mode with my day job and haven’t necessarily been doing anything interesting or innovative.  For my second iDevBlogADay post, I’m going to give some love to our built-in data structures and also discuss some alternatives to them.

But first a side-bar:

Big-O

Big-O is used to describe the complexity of an operation (algorithm).  It defines the worst case performance of an operation.  It’s usually useless describe the best or even the average case of an operation, but always useful to be able to say that an operation will perform no worse than particular value.  For data structures we define the performance in terms of ‘n’ which the number of items in the data structure.

For instance:

O(n) – “big O of n” means that for an operation we have to touch every object in the data structure at worst case.

O(2n) – “big O of 2n” means that for an operation, we have to touch every object in the data structure twice at worst case.

O(n²) – “big O of n-squared” means that for an operation, we have to touch every object in the data structure once for every object, at worst case.

There are a myriad of other ways to express complexity including using the logarithm of n, or factorials of n.  I’m not really going to cover these here.

Confused?  That’s ok.  Here’s some more concrete examples:

Let’s start with a basic array, defined as a basic indexed series of objects.  Let’s say our array holds 1000 numbers (how many doesn’t matter) and we want to search for the number 99.  We can imagine that the number 99 may exist at the first index (index 0) or the last index (999) or anywhere in the middle.  Regardless, we know that it will never take more comparisons than 1000 to find 99 if it exists.  It will also take no more than 1000 comparisons to determine whether it exists at all.  Because n = 1000, we say that the complexity is O(n) since it will always take n comparisons to find a particular value in an array.

Another example.  Let’s say we have our array of 1000 numbers, and we want to sort it.  Let’s consider a basic sort that compares each value to every other value.  To iterate over the array will take 1000 steps, and comparing one element to every other will take another 999 steps.  So we’re talking about 1000 x 999 steps, or about 1000 squared.  Therefore we say that the sort operation runs in n-squared time or O(n²).

Big-O is not necessarily something you always think about, but when you’re trying to optimize your code, the complexity of the algorithms you use on your data structure can become a big deal.

NS Data Structures

When we delve into the documentation for data structures like NSArray, we begin to discover that an array is not quite what we expect.  RidiculousFish points out that some operations on CFArray, and consequently, NSArray are in O(N*lgN) (n times the base 2 log of n, which is bigger than n), not in straight O(n) as we might think.  Operations such as searching.  This is kind of a big deal.  What gives?

The prevailing Apple wisdom seems to be that our data structures only need to look like the real thing, rather than act like it.  For instance, in a real honest-to-god array, an operation like [NSArray objectAtIndex:] should return run in what we call constant time, or O(1), meaning that it’s instantaneous.  No need to count or search; we’re able to jump right to where we need to go.  The CFArray comments RidiculousFish mentions say that it could run in O(lg n).  For the mathematically impaired, this is way slower.

The computer scientist in you should feel cheated an betrayed.  Your inner programmer should be thinking of sending Steve Jobs a strongly worded email about this telling him that arrays indexing should be constant time and nothing else.  Don’t click send just yet.  99 times out of 100 the NSArray implementation will work fine for what you need.  The same holds for all the other data structures that comes standard in Foundation.  But what about those rare times where you actually need not only the interface of a data structure (the methods on it) but also the implementation that goes along with it?

Let’s think about an example.  Imagine a queue, just like a line at the bank, where the first person in line is the first person served.  First in, first out.  Let’s assume you needed that implementation exactly.  You need an enqueue method to add an item to the end of the line and a dequeue method to remove an item to the front.  You might easily wrap an NSMutabableArray in the following manner:

1. To enqueue an item, simply use the addObject: method on NSMutableArray
2. To dequeue an item, simply use the removeObjectAtIndex method with index 0, effectively removing the first item at the front of the array.

Oh and did I mention you want it to be fast?  Knowing what you know about NSArray, you can see how this would wind up being a poor performance implementation.  Enqueue would be fast, since you only need to find the end of the array, probably O(1) since we’d know how big the array is.  Dequeue on the other hand would be slow and expensive since adding removing the zeroth object would involve shifting all the other objects down by 1.  This would run in O(n) time.  A better implementation would be to use some kind of chained list where lopping off the front of the list wouldn’t require everything to be re-indexed.

Stacks and Trees and Graphs . . . Oh My

There’s a plethora of data structures defined in the abstract sense, from trees to lists, to fully connected webs.  Questions of data structure choice can arise all the time in applications and choosing the right one can greatly enhance the speed and efficiency of your code.  You can of course opt to write your own, either by adapting one of the built in data structures like NSArray or by working from scratch.  In fact, if you’ve never written data structures, its always a worthwhile exercise to write some implementations to get a feel for how they work.  CHDataStructures is also a great library for getting implementation-exact structures for list, circular buffers, and others.

The foundation structures often pamper us into using them.  They’re nice, comfortable, familiar – like your favorite pair of jeans.  It’s important to remember that there are other things out there.  Things that may be tailored exactly to your needs.  Things worth checking out.

Using an NSDictionary for storing a matrix of values

For a recent project I needed to store a matrix of data. My only requirement was that access would be fast given a row and column designation. Unfortunately, the usual approach of using arrays of arrays wouldn’t work because of how NSArray works. From the Apple documentation for NSMutableArray:

Note that NSArray objects are not like C arrays. That is, even though you specify a size when you create an array, the specified size is regarded as a “hint”; the actual size of the array is still 0. This means that you cannot insert an object at an index greater than the current count of an array.

I could have used C arrays, but I wanted something more flexible when it comes to size and I didn’t necessarily need the contiguous memory. Constant time access was good enough.

NSDictionaries provide constant time access, and the only requirements for keys are that the object used conform to NSCoding and implement a hash function, both of which are implemented by NSIndexPath.

For my example I’ll use the adapter pattern and wrap a dictionary and expose only the methods I want:

// PZMatrix.h
#import <Foundation/Foundation.h>

@interface PZMatrix : NSObject 
{
    @private
    NSMutableDictionary *_source;
}

- (id)initWithRows:(NSInteger)rows columns:(NSInteger)cols;
- (id)objectForRow:(NSInteger)row column:(NSInteger)col;
- (void)setObject:(id)object forRow:(NSInteger)row column:(NSInteger)col;
- (void)removeAllObjects;

@end

You can see that I’m using the NSDictionary as the only iVar in the class, and I’ve created a few accessors and mutators for the data structure.

// PZMatrix.m
#import "PZMatrix.h"

@implementation PZMatrix

- (id)initWithRows:(NSInteger)rows columns:(NSInteger)cols
{
    self = [super init];
    if (self)
    {
        _source = [[NSMutableDictionary alloc] initWithCapacity:rows *cols];
    }    
    return self;
}

- (id)objectForRow:(NSInteger)row column:(NSInteger)col
{
    NSUInteger idxs[] = {row, col};
    NSIndexPath *path = [NSIndexPath indexPathWithIndexes:idxs length:2];
    return [_source objectForKey:path];
}

- (void)setObject:(id)object forRow:(NSInteger)row column:(NSInteger)col
{
    NSUInteger idxs[] = {row, col};
    NSIndexPath *path = [NSIndexPath indexPathWithIndexes:idxs length:2];
    [_source setObject:object forKey:path];
}

- (void)removeAllObjects
{
    [_source removeAllObjects];
}

@end

Pretty simple. There’s obviously some code duplication here, some of which I can simplify with a category on NSIndexPath:

//  NSIndexPath+Matrix.h
#import <Foundation/Foundation.h>

@interface NSIndexPath (Matrix)

+ (NSIndexPath *)indexPathWithRow:(NSUInteger)row column:(NSUInteger)col;

@end

//  NSIndexPath+Matrix.m
#import "NSIndexPath+Matrix.h"

@implementation NSIndexPath (Matrix)

+ (NSIndexPath *)indexPathWithRow:(NSUInteger)row column:(NSUInteger)col
{
    NSUInteger indexes[] = {row, col};
    return [NSIndexPath indexPathWithIndexes:indexes length:2];
}

@end

I can now pull that category into the matrix storage class:

// PZMatrix.m
#import "PZMatrix.h"
#import "NSIndexPath+Matrix.h"

@implementation PZMatrix

- (id)initWithRows:(NSInteger)rows columns:(NSInteger)cols
{
    self = [super init];
    if (self)
    {
        _source = [[NSMutableDictionary alloc] initWithCapacity:rows *cols];
    }    
    return self;
}

- (id)objectForRow:(NSInteger)row column:(NSInteger)col
{
    NSIndexPath *path = [NSIndexPath indexPathWithRow:row column:col];
    return [_source objectForKey:path];
}

- (void)setObject:(id)object forRow:(NSInteger)row column:(NSInteger)col
{
    NSIndexPath *path = [NSIndexPath indexPathWithRow:row column:col];
    [_source setObject:object forKey:path];
}

- (void)removeAllObjects
{
    [_source removeAllObjects];
}

@end

Testing the implementation:

PZMatrix *matrix = [[PZMatrix alloc] initWithRows:10 columns:10];
[matrix setObject:@"foo" forRow:2 column:8];
[matrix setObject:@"bar" forRow:0 column:9];
[matrix setObject:@"baz" forRow:9 column:9];
    
NSLog(@"%@", [matrix objectForRow:2 column:8]);
NSLog(@"%@", [matrix objectForRow:9 column:9]);
NSLog(@"%@", [matrix objectForRow:9 column:8]);