Paired Arrays in Cocoa and Cocoa Touch

The concept of "paired arrays" is really a powerful one. The basic idea is this - you have multiple NSArrays or NSMutableArrays, and they hold values corresponding to the same things. For example, you might have one array of keys and one of values. That's a simple example, and one where you probably would just use an NSDictionary, but it's a good example to show what they are used for. Now, the first element in one array corresponds to the first element in the other array. This gives you more flexibility than using an NSDictionary because you have ready access to each list and can also have more than two arrays paired, so you're not restricted to just key and value, you could have key and three values for example, without having to mess with dictionaries inside of dictionaries.

I use this technique a lot with SQLitePersistentObjects on the iPhone to avoid loading objects into memory just to display one or two values from an object, for example, to put in a table view. When you have objects that contain UIImages or NSDatas, doing this can really keep your memory footprint way down, which is a very good thing on a resource-constrained device. On the iPhone, I'm a big fan of paired arrays. I don't use them so much on the Mac, but they certainly have their uses.

But, there is one really annoying thing about paired arrays: Sorting them. It's just not fun. NSMutableArray is set up to sort based on the values in its own array, not on the values in another array. So, if you want to sort both the key and value arrays based on the values in the array of keys, how do you do it? There's no easy, built-in way.

Well, if you've followed this blog for any length of time, you know that I really, really like Objective-C categories. Here's a new one - it lets you sort multiple arrays based on the values in one array. It uses exactly the same sorting algorithm as NSMutableArray I believe - a shell sort. I don't work for Apple and don't have access to their code, so I don't know for sure that they still do it this way, but the old NeXTSTEP/OPENSTEP sort was done this way, and the GNUStep sort is still done this way, so I'm guessing that Apple's Foundation Kit version of NSMutableArray still works this way, though I'm certainly open to more optimized sorting algorithms if you want to tweak it.

Here is an example of using this category, using three paired arrays, one with numbers, and two others with those numbers spelled out in different languages, and sorting all three values based on the numbers.

    NSMutableArray *array1 = [NSMutableArray arrayWithObjects:[NSNumber numberWithInt:5], [NSNumber numberWithInt:3], [NSNumber numberWithInt:1], [NSNumber numberWithInt:2], [NSNumber numberWithInt:4], [NSNumber numberWithInt:6], nil];
    NSMutableArray *array2 = [NSMutableArray arrayWithObjects:@"Five", @"Three", @"One", @"Two", @"Four", @"Six", nil];
    NSMutableArray *array3 = [NSMutableArray arrayWithObjects:@"Cinq", @"Trois", @"Un", @"Deux", @"Quatre", @"Six", nil];

    [array1 sortArrayUsingSelector:@selector(compare:) withPairedMutableArrays:array2, array3, nil];

After the call to sortArrayUsingSelector:withPairedArrays:, the three arrays will all be in numeric order, so array2 will look like this:

One, Two, Three, Four, Five, Six

and array3 will look like this:

Un, Deux, Trois, Quatre, Cinq, Six

Pretty cool, huh? Here's the code:

NSMutableArray-MultipleSort.h

//
//  NSMutableArray-MultipleSort.h
//  iContractor
//
//  Created by Jeff LaMarche on 1/16/09.
//  Copyright 2009 Jeff LaMarche. All rights reserved.
//

// This category on NSMutableArray implements a shell sort based on the old NeXT example 
// SortingInAction. It is functionally identical to sortArrayUsingSelector: except that
// it will sort other paired arrays based on the comparison values of the original array
// this is for use in paired array situations, such as when you use one array to store
// keys and another array to store values. This is a variadic method, so you can sort
// as many paired arrays as you have.

// This source may be used, free of charge, for any purposes. commercial or non-
// commercial. There is no attribution requirement, nor any need to distribute
// your source code. If you do redistribute the source code, you must
// leave the original header comments, but you may add additional ones.


// Stride factor defines the size of the shell sort loop's stride. It can be tweaked 
// for performance, though 3 seems to be a good general purpose value
#define STRIDE_FACTOR 3 

#import <Foundation/Foundation.h>

// This compare method was taken from the GNUStep project. GNUStep is
// licensed under the LGPL, which allows such use.
static inline NSComparisonResult compare(id elem1, id elem2, void* context)
{
    NSComparisonResult (*imp)(id, SEL, id);
    
    if (context == 0)
    {
        [NSException raise: NSInvalidArgumentException
                    format: @"compare null selector given"];
    }
    
    imp = (NSComparisonResult (*)(id, SEL, id))
    [elem1 methodForSelector: context];
    
    if (imp == NULL)
    {
        [NSException raise: NSGenericException
                    format: @"invalid selector passed to compare"];
    }
    
    return (*imp)(elem1, context, elem2);
}

@interface NSMutableArray(MultipleSort)
// Takes a comparator and a nil-terminated list of paired arrays
- (void)sortArrayUsingSelector:(SEL)comparator withPairedMutableArrays:(NSMutableArray *)array1, ...;
@end

NSMutableArray-MultipleSort.m

//
//  NSMutableArray-MultipleSort.m
//  iContractor
//
//  Created by Jeff LaMarche on 1/16/09.
//  Copyright 2009 Jeff LaMarche Consulting. All rights reserved.
//
// This source may be used, free of charge, for any purposes. commercial or non-
// commercial. There is no attribution requirement, nor any need to distribute
// your source code. If you do redistribute the source code, you must
// leave the original header comments, but you may add additional ones.

#import "NSMutableArray-MultipleSort.h"

@implementation NSMutableArray(MultipleSort)
- (void)sortArrayUsingSelector:(SEL)comparator withPairedMutableArrays:(NSMutableArray *)array1, ...
{
    unsigned    int     stride = 1;
                BOOL    found = NO;
    unsigned    int     count = [self count];
    unsigned    int     d;
    
    while (stride <= count)
        stride = stride * STRIDE_FACTOR + 1;
    
    while (stride > (STRIDE_FACTOR - 1))
    {
        stride = stride / STRIDE_FACTOR;
        for (unsigned int c = stride; c < count; c++)
        {
            found = NO;
            if (stride > c)
                break;
            
            d = c - stride;
            while (!found)
            {
                id          a = [self objectAtIndex: d + stride];
                id          b = [self objectAtIndex: d];
                
                NSComparisonResult  result = (*compare)(a, b, (void *)comparator);
                
                if (result < 0)
                {
                    [a retain];
                    [self replaceObjectAtIndex: d + stride withObject: b];
                    [self replaceObjectAtIndex: d withObject: a];
                    
                    id eachObject;
                    va_list argumentList;
                    if (array1)                     
                    {   
                        id a1 = [array1 objectAtIndex:d+stride];
                        id b1 = [array1 objectAtIndex:d];
                        [a1 retain];
                        [array1 replaceObjectAtIndex: d + stride withObject:b1];
                        [array1 replaceObjectAtIndex: d withObject: a1];
                        [a1 release];
                        va_start(argumentList, array1);         
                        while (eachObject = va_arg(argumentList, id)) 
                        {
                            id ax = [eachObject objectAtIndex:d+stride];
                            id bx = [eachObject objectAtIndex:d];
                            [ax retain];
                            [eachObject replaceObjectAtIndex: d + stride withObject:bx];
                            [eachObject replaceObjectAtIndex: d withObject: ax];
                            [ax release];
                        }
                        va_end(argumentList);
                    }
                    
                    [a release];
                    
                    if (stride > d)
                        break;
                    
                    d -= stride;    
                }
                else
                    found = YES;
            }
        }
    }
}
@end