Suppose you want to sort an array of strings according to some prescribed order. In other words, you are given an array of strings as input, plus another array of strings describing the required ordering. The result is another array of strings equal to the first but sorted by the second.
Take an example. It’s usually best.
Say you want to iterate dictionary keys in a specific order, regardless of internal ordering or whether individual keys are present or not. Say your required key ordering is C, B, A, for arguments sake; then, given A, B, C for the set of dictionary keys or any alternative combination, you always get C, B, A. If any keys fail to match the required sequence, they appear at the end unsorted.
This requirement assumes the order matters. Sometimes it doesn’t, of course. But sometimes it does! It also assumes that normal lexical ordering does not fit the bill. Otherwise you could just sort the array as normal.
Test case
Start with an array that needs sorting. The test case contains three strings (C, B, A) in that order.
NSArray *needsSorting = [NSArray arrayWithObjects:@"C", @"B", @"A", nil];Next, we need an array defining the required sort order. Instead of A, B, C let’s choose a non-lexical ordering like B, C, A. This acts as the ‘lexicon’ for sorting. According to this lexicon, the sorted result should be B, C, A.
NSArray *sortUsing = [NSArray arrayWithObjects:@"B", @"C", @"A", nil];Truly, this is a unrealistic example. It does not pretend to be purposeful beyond a test exercise. But it does provide a basic test. Once the outcome is available, the test case can assert its success as follows.
NSLog(@"%@", sorted);The Console should reply:
(
B,
C,
A
)It might be tempting to use the Foundation framework’s NSAssert macro. But that’s only possible from within Objective-C classes. Reason is simple. When NSAssert throws an exception, it accesses _cmd and self. So unless asserting from with an instance or class method, no go! Not if you execute the test from say a standard C function like main. See below.
#import <Foundation/Foundation.h>
int main(int argc, char *argv[])
{
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
NSArray *needsSorting = [NSArray arrayWithObjects:@"C", @"B", @"A", nil];
NSArray *sortUsing = [NSArray arrayWithObjects:@"B", @"C", @"A", nil];
NSArray *sorted;
//
// needsSorting, sortUsing --> sorted!!!
//
NSLog(@"%@", sorted);
[pool drain];
return 0;
}Running this initially gives:
(null)So that’s a successful first test. It confirms failure which is what we expect, of course.
Design
The requirement is for a sorting process, just like any other sort. It’s identical apart from the one small difference: comparison. Rather than comparing each element, the sort compares the element’s position in the lexical array. Only if they have identical positions (indices) do their values need comparing.
How to implement? As a function? As a sorting object? Or perhaps, as an extension to the NSArray class? It makes sense to follow the sortedArrayUsingSomething pattern of methods that already exists for NSArray instances. The new method can be called sortedArrayUsingArray since it sorts an array using another array. In the form of an Objective-C extension on the NSArray class, the interface appears as follows, where RRFoundation is the category name:
#import <Foundation/Foundation.h>
@interface NSArray(RRFoundation)
- (NSArray *)sortedArrayUsingArray:(NSArray *)otherArray;
@endImplementation
It turns out that the implementation—making good use of existing Foundation framework methods—proves quite simple.
#import "NSArray+RRFoundation.h"
@implementation NSArray(RRFoundation)
static NSInteger comparatorForSortingUsingArray(id object1, id object2, void *context)
{
// Use NSArray's -indexOfObject:anObject rather than its "identical" form,
// -indexOfObjectIdenticalTo:anObject. Note that converting object to index
// answers an unsigned integer. A value of NSNotFound indicates, well, not
// found! And, since this value equals -1 and therefore the maximum possible
// unsigned integer, objects not found come last in the sorting order. Also
// note, if the two objects have the same index, their values are compared
// as normal.
NSUInteger index1 = [(NSArray *)context indexOfObject:object1];
NSUInteger index2 = [(NSArray *)context indexOfObject:object2];
if (index1 < index2)
return NSOrderedAscending;
// else
if (index1 > index2)
return NSOrderedDescending;
// else
return [object1 compare:object2];
}
- (NSArray *)sortedArrayUsingArray:(NSArray *)otherArray
{
return [self sortedArrayUsingFunction:comparatorForSortingUsingArray context:otherArray];
}
@endBut is it really that simple? Simpler than I thought. Let’s try some testing.
Testing
Sure enough, importing the requisite header and adding the line below, gives the output expected.
sorted = [needsSorting sortedArrayUsingArray:sortUsing];Console shows:
(
B,
C,
A
)Done. Well, almost.
Finally, let’s go wild! Let’s feed it a tonne of stuff and see what breaks. Naughty but nice.
Let’s use keys from the IOKit framework, specifically Power Source keys. We’ll insert an static array of keys, adding the code below before main.
#import <IOKit/ps/IOPSKeys.h>
static const char *const kIOPSKeys[] =
{
kIOPSPowerSourceStateKey,
kIOPSCurrentCapacityKey,
kIOPSMaxCapacityKey,
};Then convert the array of const char *consts (constant pointers to constant characters) to an NSArray of NSStrings.
NSUInteger i;
NSMutableArray *IOPSKeys = [NSMutableArray array];
for (i = 0; i < sizeof(IOPSKeys)/sizeof(IOPSKeys[0]); i++)
{
[IOPSKeys addObject:[NSString stringWithUTF8String:kIOPSKeys[i]]];
}Now there’s an array of keys expressing the required order: power source state, then current capacity, then maximum capacity. What will happen if we throw every possible combination at the sort-using-array method? Every combination. Iterating over combinations. That’s not exactly straightforward!
I feel a digression coming on.