A problem came up whilst I was hard at work at my current job (iOS developer at zeebox) where I needed a list of things that were going to be displayed in a table. These things were going to be ordered based on time but the API I wanted my table view to have was such that it would be given a chunk of new items to display but it didn’t necessarily know where to display them. I would want to animate the changes to the table so when adding a new object I’d need to know where they had been added. So I thought to myself:

Wouldn’t it be nice to have an array which kept itself sorted when you added objects to it and also told you where it had added them?

And this is where MJGMutableSortedArray was born…

Why would you want this sort of array?

Consider a situation where you’re showing a objects in a list which have a logical sort order. For example, think of a list of people ordered by their name. You may get an opportunity to add a new object to the array and in the process you want your table view to animate in the change. The usual way of doing this would be the following:

1. Add the new person to your internal storage array of people.
2. Sort your array of people.
3. Figure out where the new person ended up.
4. Perform the animation now that you know the index of the row which has been added.

This is quite a time consuming process and we can surely do better, right?

My solution

I came up with the idea of an array which you give it a means of ordering itself. Since I wanted compatibility with NSMutableArray I chose to allow the following methods for keeping the array sorted:

1. Using an array of sort descriptors.
2. Using a comparator block.
3. Using a callback function.
4. Using a specific selector.

These map nicely to NSMutableArray’s sortUsing... method family, which is nice.

So I came up with this initial header file:

1
2
3
4
5
6
7
8

@interface MJGSortedMutableArray : NSObject

- (id)initWithDescriptors:(NSArray*)descriptors;
- (id)initWithComparator:(NSComparator)comparator;
- (id)initWithFunction:(NSInteger (*)(id, id, void *))compare context:(void *)context;
- (id)initWithSelector:(SEL)selector;

@end

Great! That’s how we’d create one of these. But what about the other methods we’d want in such an array. The first really important method is the whole reason for creating this class, which is to add an object and find out where in the array the new object was added. It would also be great to be able to remove objects, so I came up with these two methods:

1
2

- (NSUInteger)addObject:(id)obj;
- (void)removeObjectAtIndex:(NSUInteger)index;

And that just leaves implementing it…

Implementing it

Implementing this is actually really straight forward. The only tricky bit is ensuring that the array stays sorted when you add to it. The beauty of only allowing addition of single objects at a time, added to the fact that the method for comparison is decided at initialisation means that you can make the optimisation that you know your array is sorted at all times. So addition of an element is O(n).

I decided to stick with blocks being the basis of everything and boil all the comparison methods down into NSComparator blocks. So then it makes the addObject: method really simple. I made the class have a comparator and a mutable array internally, which the insertion and deletion methods will act upon. This is what the class continuation category looks like:

1
2
3
4

@interface MJGSortedMutableArray ()
@property (nonatomic, strong) NSMutableArray *backingArray;
@property (nonatomic, strong) NSComparator comparator;
@end

So then the addObject: method is simply this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

- (NSUInteger)addObject:(id)obj {
    __block NSUInteger addedIndex = NSNotFound;
    [_backingArray enumerateObjectsUsingBlock:^(id obj2, NSUInteger idx, BOOL *stop) {
        NSComparisonResult result = _comparator(obj, obj2);
        if (result != NSOrderedDescending) {
            addedIndex = idx;
            [_backingArray insertObject:obj atIndex:addedIndex];
            *stop = YES;
        }
    }];

    if (addedIndex == NSNotFound) {
        [_backingArray addObject:obj];
        addedIndex = (_backingArray.count - 1);
    }
    return addedIndex;
}

It should be fairly easy to convince yourself how this works. It loops over all the objects currently in the array until it hits one where the result of comparing the object to insert with the iterated object is not NSOrderedDescending. The following example should make you understand that:

Current array:     1  4  6  9
Object to insert:  7
Comparison method: NSNumber's compare: method

Iteration 0:       obj2 = 1
                   result = [7 compare:1] = NSOrderedDescending

Iteration 1:       obj2 = 4
                   result = [7 compare:4] = NSOrderedDescending

Iteration 2:       obj2 = 6
                   result = [7 compare:6] = NSOrderedDescending

Iteration 3:       obj2 = 9
                   result = [7 compare:9] = NSOrderedAscending

In this case we hit the right place to insert when the iteration index was 3, since at that point the result of the comparison was NSOrderedAscending. The object would be added at index 3, so the array would then be:

1  4  6  7  9

This has clearly worked. Woo! Removal is simple:

1
2
3

- (void)removeObjectAtIndex:(NSUInteger)index {
    [_backingArray removeObjectAtIndex:index];
}

Initialising the array with the various options

That just leaves initialising the array and creating the comparator block. The simple case is the initWithComparator: since the comparator has already been created by the caller for us:

1
2
3
4
5
6

- (id)initWithComparator:(NSComparator)comparator {
    if ((self = [self init])) {
        self.comparator = comparator;
    }
    return self;
}

The next easiest is initWithFunction: since that comparator is simple to create:

1
2
3
4
5
6
7
8

- (id)initWithFunction:(NSInteger (*)(id, id, void *))compare context:(void *)context {
    if ((self = [self init])) {
        self.comparator = ^NSComparisonResult(id obj1, id obj2) {
            return compare(obj1, obj2, context);
        };
    }
    return self;
}

Then comes initWithDescriptors:, which is a bit more complicated. This involves looping through an array of descriptors until one finds the two objects to be different, i.e. don’t compare as NSOrderedSame. It should be simple enough to convince yourself that the following implementation gives that:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

- (id)initWithDescriptors:(NSArray*)descriptors {
    if ((self = [self init])) {
        self.comparator = ^NSComparisonResult(id obj1, id obj2) {
            for (NSSortDescriptor *descriptor in descriptors) {
                NSComparisonResult result = [descriptor compareObject:obj1 toObject:obj2];
                if (result != NSOrderedSame) {
                    return result;
                }
            }
            return NSOrderedSame;
        };
    }
    return self;
}

Finally, that leaves initWithSelector: which is a bit harder. It could be achieved by just using performSelector: but that gives compiler warnings since the compiler cannot know what the return type of the selector is and therefore ARC can’t do it’s thing (imagine if the selector actually returned an object with a +1 reference count – it would be leaked as ARC cannot know at compile time that the selector is going to do this). So I decided to use NSInvocation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

- (id)initWithSelector:(SEL)selector {
    if ((self = [self init])) {
        // 1
        NSMethodSignature *methodSignature = [NSNumber instanceMethodSignatureForSelector:@selector(compare:)];

        // 2
        NSInvocation *invocation = [NSInvocation invocationWithMethodSignature:methodSignature];
        [invocation setSelector:selector];

        // 3
        self.comparator = ^NSComparisonResult(id obj1, id obj2) {
            // 4
            [invocation setTarget:obj1];
            [invocation setArgument:&obj2 atIndex:2];
            [invocation invoke];

            // 5
            NSComparisonResult returnValue;
            [invocation getReturnValue:&returnValue];

            // 6
            return returnValue;
        };
    }
    return self;
}

That’s a bit crazy, but here’s what’s happening:

1. First we need the method signature that the selector is going to conform to. We don’t actually know it, but we have defined in the API of this class that we expect a selector that takes 1 object argument and returns an NSComparisonResult, just like NSMutableArray’s sortUsingSelector: method does. It just so happens that NSNumber has a method that has the same signature, so we use the instanceMethodSignatureForSelector: method to get one. You could have created the signature manually using the ASCII representation of the signature encoding, but this is just easier I think.

2. Next we create an invocation object with the signature and set the selector.

3. Then comes creating the comparator…

4. When the comparator is invoked, the first thing to do is set the target, argument (which is at index 2 because NSInvocation is wrapping objc_msgSend where the first argument to a method is the 3rd argument to objc_msgSend) and then invoke it.

5. To get the return type, we need to create some memory of the right size and the call getReturnValue: to ask the invocation to fill it in with the return value.

6. And finally, return the comparison result from the comparator.

There, that wasn’t too bad was it?! That is everything to get the array working!

Enumerating, quickly

Anyone using an array will at some point want to enumerate it. That’s usually done using NSFastEnumeration which looks something like this:

for (id object in array) {
    // Do something
}

Now how can we go about adding that to our class then you are asking? Well, NSFastEnumeration all lies with one method:

- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(__unsafe_unretained id [])buffer count:(NSUInteger)len;

Mike Ash has a very good post about it, but we don’t actually have to do much work. Since there is an NSArray backing this class which already supports fast enumeration, all we have to do is the following:

1
2
3

- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(__unsafe_unretained id [])buffer count:(NSUInteger)len {
    return [_backingArray countByEnumeratingWithState:state objects:buffer count:len];
}

And that’s it!

More more more!

I implemented a few more methods which you can read the source for on GitHub. Other than that, I will no doubt be adding more to this when I see fit. I also have plans for a dictionary where the keys stay sorted.