Friday, January 16, 2009

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





4 comments:

bing said...

I just want to say thank you for this beautiful piece of code. I started learning cocoa and objc for the iPhone from one of your books, and I hit a wall with a project I'm working on. Basically I needed to return some values (averages that were calculated on a database field) and their related objects. I tried using NSDictionary but realized that since the average scores might not be unique, I wouldn't get all the elements I needed in the dictionary. Needless to say I thought multiple arrays-- but then how to sort them??? Well this fixed it. Thanks!

Edwin said...

scrub m65 kamagra attorney lawyer body scrub field jacket lovegra marijuana attorney injury lawyer

h4ns said...

I was very encouraged to find this site. I wanted to thank you for this special read. I definitely savored every little bit of it and I have you bookmarked to check out new stuff you post.

AC Milan vs Lazio Live Streaming
West Bromwich Albion vs Wigan Athletic Live Streaming
Manchester United vs Aston Villa Live Streaming
Sunderland vs Chelsea Live Streaming
Arsenal vs Everton Live Streaming
Augsburg vs Bochum Live Streaming
Racing Santander vs Valencia Live Streaming
Frosinone vs Atalanta Live Streaming
AC Milan vs Lazio Live Streaming
West Bromwich Albion vs Wigan Athletic Live Streaming
Manchester United vs Aston Villa Live Streaming
Sunderland vs Chelsea Live Streaming
Arsenal vs Everton Live Streaming
Augsburg vs Bochum Live Streaming
Racing Santander vs Valencia Live Streaming
Frosinone vs Atalanta Live Streaming
Technology News | Hot News Today | Live Stream

launch-mailinator-com said...

You don't need to make a special case for array1. Instead of en entire section

id eachObject;
va_list argumentList;
if (array1)
{ ... }

You can just do

id eachObject;
va_list argumentList;
va_start(argumentList, array1);
for (eachObject = array1; eachObject; 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);