Closest-pair problem/Objective-C
<lang objc>#import <Foundation/Foundation.h>
- import <math.h>
@interface Point : NSObject {
double xCoord, yCoord;
} + (id)x: (double)x y: (double)y; - (id)initWithX: (double)x andY: (double)y; - (double)x; - (double)y; - (double)dist: (Point *)pt; - (NSComparisonResult)compareX: (Point *)pt; - (NSComparisonResult)compareY: (Point *)pt; @end
@implementation Point
+ (id)x: (double)x y: (double)y {
return [[[self alloc] initWithX: x andY: y] autorelease];
}
- (id)initWithX: (double)x andY: (double)y {
if (!(self = [super init])) return nil;
xCoord = x; yCoord = y;
return self;
}
- (double)x { return xCoord; } - (double)y { return yCoord; }
- (double)dist: (Point *)pt {
return hypot([self x] - [pt x], [self y] - [pt y]);
}
- (NSComparisonResult)compareX: (Point *)pt {
if ( [self x] < [pt x] ) return NSOrderedAscending; else if ( [self x] > [pt x] ) return NSOrderedDescending; else return NSOrderedSame;
}
- (NSComparisonResult)compareY: (Point *)pt {
if ( [self y] < [pt y] ) return NSOrderedAscending; else if ( [self y] > [pt y] ) return NSOrderedDescending; else return NSOrderedSame;
} @end</lang>
<lang objc>@interface ClosestPair : NSObject + (NSArray *)closestPairSimple: (NSArray *)pts; + (NSArray *)closestPair: (NSArray *)pts; + (NSArray *)closestPairPriv: (NSArray *)xP and: (NSArray *)yP; + (id)minBetween: (id)minA and: (id)minB; @end
@implementation ClosestPair
+ (NSArray *)closestPairSimple: (NSArray *)pts {
int i, j; if ( [pts count] < 2 ) return [NSArray arrayWithObject: [NSNumber numberWithDouble: HUGE_VAL]]; NSArray *r; double c = [[pts objectAtIndex: 0] dist: [pts objectAtIndex: 1]]; r = [NSArray arrayWithObjects: [NSNumber numberWithDouble: c], [pts objectAtIndex: 0], [pts objectAtIndex: 1], nil]; for(i=0; i < ([pts count] - 1); i++) { for(j=i+1; j < [pts count]; j++) { double t; t = [[pts objectAtIndex: i] dist: [pts objectAtIndex: j]]; if ( t < c ) { c = t; r = [NSArray arrayWithObjects: [NSNumber numberWithDouble: t], [pts objectAtIndex: i], [pts objectAtIndex: j], nil]; } } } return r;
}
+ (NSArray *)closestPair: (NSArray *)pts {
return [self closestPairPriv: [pts sortedArrayUsingSelector: @selector(compareX:)] and: [pts sortedArrayUsingSelector: @selector(compareY:)] ];
}
+ (NSArray *)closestPairPriv: (NSArray *)xP and: (NSArray *)yP {
NSArray *pR, *pL, *minR, *minL; NSMutableArray *yR, *yL, *joiningStrip, *tDist, *minDist; double middleVLine; int i, nP, k;
if ( [xP count] <= 3 ) { return [self closestPairSimple: xP]; } else { int midx = ceil([xP count]/2.0); pL = [xP subarrayWithRange: NSMakeRange(0, midx)]; pR = [xP subarrayWithRange: NSMakeRange(midx, [xP count] - midx)]; yL = [[NSMutableArray alloc] init]; yR = [[NSMutableArray alloc] init]; middleVLine = [[pL objectAtIndex: (midx-1)] x]; for(i=0; i < [yP count]; i++) { if ( [[yP objectAtIndex: i] x] <= middleVLine ) { [yL addObject: [yP objectAtIndex: i]]; } else { [yR addObject: [yP objectAtIndex: i]]; } } minR = [ClosestPair closestPairPriv: pR and: yR]; minL = [ClosestPair closestPairPriv: pL and: yL]; minDist = [ClosestPair minBetween: minR and: minL]; joiningStrip = [NSMutableArray arrayWithCapacity: [xP count]]; for(i=0; i < [yP count]; i++) { if ( fabs([[yP objectAtIndex: i] x] - middleVLine) < [[minDist objectAtIndex: 0] doubleValue] ) { [joiningStrip addObject: [yP objectAtIndex: i]]; } } tDist = minDist; nP = [joiningStrip count]; for(i=0; i < (nP - 1); i++) { k = i + 1; while( (k < nP) && ( ([[joiningStrip objectAtIndex: k] y] - [[joiningStrip objectAtIndex: i] y]) < [[minDist objectAtIndex: 0] doubleValue] ) ) { double d = [[joiningStrip objectAtIndex: i] dist: [joiningStrip objectAtIndex: k]]; if ( d < [[tDist objectAtIndex: 0] doubleValue] ) { tDist = [NSArray arrayWithObjects: [NSNumber numberWithDouble: d], [joiningStrip objectAtIndex: i], [joiningStrip objectAtIndex: k], nil]; } k++; } } [yL release]; [yR release]; return tDist; }
}
+ (id)minBetween: (id)minA and: (id)minB {
if ( [[minA objectAtIndex: 0] doubleValue] < [[minB objectAtIndex: 0] doubleValue] ) { return minA; } else { return minB; }
}
@end</lang>
Testing
<lang objc>#define NP 10000
int main() {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
NSMutableArray *p = [[NSMutableArray alloc] init]; srand(0); for(int i = 0; i < NP; i++) { [p addObject: [Point x: 20.0*((double)rand()/(RAND_MAX+1.0)) - 10.0 y: 20.0*((double)rand()/(RAND_MAX+1.0)) - 10.0] ]; }
//NSArray *r1 = [ClosestPair closestPairSimple: p]; NSArray *r2 = [ClosestPair closestPair: p];
//NSLog(@"%lf", [[r1 objectAtIndex: 0] doubleValue]); NSLog(@"%lf", [[r2 objectAtIndex: 0] doubleValue]);
[p release]; [pool drain]; return EXIT_SUCCESS;
}</lang>
Timing (with the time command):
d&c: 0.22user 0.00system 0:00.41elapsed brute force: 13.53user 0.06system 0:13.87elapsed