More NSArray Sorting

Welcome to another Objective-C Tuesdays. Last week, we looked at sorting C arrays and NSArrays. Today, we will continue looking at sorting NSArrays using NSSortDescriptors.

As we saw last week, the sorting methods of NSArray require you to specify a comparator in one form or another. When sorting an NSArray of simple objects like NSStrings or NSDates, the comparators are usually pretty simple to write and common objects often have useful comparator methods like -caseInsensitiveCompare: and -localizedCompare:.

When sorting NSArrays of more complex objects, writing comparators is often more tedious and error-prone. Here's the interface for simple Person class:

// Person.h
@interface Person : NSObject

@property (strong) Address *address;
@property (strong) NSDate *birthdate;
@property (copy) NSString *firstName;
@property (copy) NSString *lastName;

@end

And here's the Address class used by Person:

// Address.h
@interface Address : NSObject

@property (copy, nonatomic) NSString *street;
@property (copy, nonatomic) NSString *city;
@property (copy, nonatomic) NSString *state;
@property (copy, nonatomic) NSString *country;
@property (copy, nonatomic) NSString *postalCode;

@end

If we have an NSArray of Person objects, we may want to sort them in country, lastName, firstName order. Here's one way to do that, using a comparator block:

// sort Person objects by lastName, firstName
Person *frodo = [Person new];
[frodo setFirstName:@"Frodo"];
[frodo setLastName:@"Baggins"];
// ...
[[frodo address] setCountry:@"Shire"];

Person *bilbo = [Person new];
[bilbo setFirstName:@"Bilbo"];
[bilbo setLastName:@"Baggins"];
// ...
[[bilbo address] setCountry:@"Shire"];

Person *legolas = [Person new];
[legolas setFirstName:@"Legolas"];
[legolas setLastName:@"Greenleaf"];
// ...
[[legolas address] setCountry:@"Mirkwood"];

NSArray *people = [NSArray arrayWithObjects:frodo, bilbo, legolas, nil];
NSArray *sortedPeople = [people sortedArrayUsingComparator:^(id item1, id item2) {
  Person *person1 = item1;
  Person *person2 = item2;
  
  // NSComparisonResult is a typedef for int
  NSComparisonResult result = [[[person1 address] country] compare:[[person2 address] lastName]];
  if (result) {
    return result;
  }
  
  result = [[person1 lastName] compare:[person2 lastName]];
  if (result) {
    return result;
  }
  
  result = [[person1 firstName] compare:[person2 firstName]];
  if (result) {
    return result;
  }
  
  return NSOrderedSame; // NSOrderedSame == 0
}];
// sortedPeople contains:
// Legolas Greenleaf (Mirkwood)
// Bilbo Baggins (Shire)
// Frodo Baggins (Shire)

The general pattern of a multi-field comparator is simple: check each field in turn, stop and return the comparison result if non-zero; if all fields are equal, return zero (or NSOrderedSame to be more descriptive). This quickly becomes tedious when you have many fields to sort by or you need to dig down into child or grandchild objects for fields.

Fortunately, there's an easier way to do this. NSArray has a method called -sortedArrayUsingDescriptors: that takes an array of NSSortDescriptor objects. Each NSSortDescriptor specifies a key path and sort direction (ascending or descending). The order of NSSortDescriptors in the array determines the precedence of each field. If you're not familiar with Key Value Coding (KVC), you may not have encountered key paths before. KVC is similar reflection in Java and other dynamic languages. KVC allows you to get and set fields on an object using the field names as strings, called keys. To access fields on child objects, you use keys separated by dots to form a key path; KVC knows how to drill down your object graph and access fields on child objects. There are a lot of interesting things you can do with KVC, but today we will stick to building an array of NSSortDescriptors:

NSSortDescriptor *byCountry = [NSSortDescriptor sortDescriptorWithKey:@"address.country" 
                                                            ascending:YES];
NSSortDescriptor *byLastName = [NSSortDescriptor sortDescriptorWithKey:@"lastName" 
                                                             ascending:YES];
NSSortDescriptor *byFirstName = [NSSortDescriptor sortDescriptorWithKey:@"firstName" 
                                                              ascending:YES];
NSArray *sortDescriptors = [NSArray arrayWithObjects:byCountry, byLastName, byFirstName, nil];

Notice that the byCountry sort descriptor uses the key path @"address.country": it will first get the value of the address property of the Person object, then get the country property of the address. Key paths can be as deep as your object graph.

Using the array of sort descriptors is easy:

NSArray *sortedPeople = [people sortedArrayUsingDescriptors:sortDescriptors];
// sortedPeople contains:
// Legolas Greenleaf (Mirkwood)
// Bilbo Baggins (Shire)
// Frodo Baggins (Shire)

This certainly makes creating complex sort criteria much easier, and you're not limited to the default comparator for a field. You can specify a selector for a comparator method on the field this way:

// specify a method to call on the lastName object
NSSortDescriptor *byLastName = [NSSortDescriptor sortDescriptorWithKey:@"lastName" 
                                                             ascending:YES
                                                              selector:@selector(caseInsensitiveCompare:)];

Or for more specialized comparisons, you can pass in a NSComparator block this way:

// sort descriptor using length of last name
NSSortDescriptor *byLastNameLength = [NSSortDescriptor sortDescriptorWithKey:@"lastName" 
                                                                   ascending:YES 
                                                                  comparator:^(id item1, id item2) {
  NSString *lastName1 = item1;
  NSString *lastName2 = item2;
  // cast result to NSComparisonResult so that the 
  // compiler infers the correct return type
  return (NSComparisonResult) ([lastName1 length] - [lastName2 length]);
}];

Specifying complex sort orders with NSSortDescriptors is the type of higher level, declarative code that is easy to write, easy to read and easy to maintain, and in most cases you should consider using NSSortDescriptor rather than writing your own comparator methods, functions or blocks.

Next time, we will look at sorting NSMutableArrays in place, rather than producing a sorted copy like the various -sortedArray methods.