I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Closest-pair problem/Objective-C

Closest-pair problem/Objective-C is part of Closest pair problem. You may find other members of Closest pair problem at Category:Closest pair problem.
Works with: GNUstep
Works with: Cocoa
`#import <Foundation/Foundation.h>#import <math.h> @interface Point : NSObject {  double xCoord, yCoord;}+ (instancetype)x: (double)x y: (double)y;- (instancetype)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 + (instancetype)x: (double)x y: (double)y {  return [[self alloc] initWithX: x andY: y];} - (instancetype)initWithX: (double)x andY: (double)y {  if ((self = [super init])) {    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`
`@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 {  if ( [pts count] < 2 ) return @[ @HUGE_VAL ];  double c = [ pts[0] dist: pts[1] ];  NSArray *r = @[ @(c), pts[0], pts[1] ];  for(int i=0; i < ([pts count] - 1); i++) {    for(int j=i+1; j < [pts count]; j++) {      double t = [ pts[i] dist: pts[j] ];      if ( t < c ) {        c = t;        r = @[ @(t), pts[i], pts[j] ];      }    }  }  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 {  int nP, k;   if ( [xP count] <= 3 ) {    return [self closestPairSimple: xP];  } else {    int midx = ceil([xP count]/2.0);    NSArray *pL = [xP subarrayWithRange: NSMakeRange(0, midx)];    NSArray *pR = [xP subarrayWithRange: NSMakeRange(midx, [xP count] - midx)];    NSMutableArray *yL = [[NSMutableArray alloc] init];    NSMutableArray *yR = [[NSMutableArray alloc] init];    double middleVLine = [pL[midx-1] x];    for(int i=0; i < [yP count]; i++) {      if ( [yP[i] x] <= middleVLine ) {        [yL addObject: yP[i]];      } else {        [yR addObject: yP[i]];      }    }    NSArray *minR = [ClosestPair closestPairPriv: pR and: yR];    NSArray *minL = [ClosestPair closestPairPriv: pL and: yL];    NSMutableArray *minDist = [ClosestPair minBetween: minR and: minL];    NSMutableArray *joiningStrip = [NSMutableArray arrayWithCapacity: [xP count]];    for(int i=0; i < [yP count]; i++) {      if ( fabs([yP[i] x] - middleVLine) <           [minDist[0] doubleValue] ) {        [joiningStrip addObject: yP[i]];      }    }    NSMutableArray *tDist = minDist;    int nP = [joiningStrip count];    for(int i=0; i < (nP - 1); i++) {      int k = i + 1;      while( (k < nP) &&             ( ([joiningStrip[k] y] - [joiningStrip[i] y]) < [minDist[0] doubleValue] ) ) {        double d = [joiningStrip[i] dist: joiningStrip[k]];        if ( d < [tDist[0] doubleValue] ) {          tDist = @[ @(d), joiningStrip[i], joiningStrip[k] ];        }        k++;      }    }    return tDist;  }} + (id)minBetween: (id)minA and: (id)minB {  if ( [minA[0] doubleValue] < [minB[0] doubleValue] ) {    return minA;  } else {    return minB;  }} @end`

Testing

`#define NP 10000 int main(){  @autoreleasepool {     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[0] doubleValue]);    NSLog(@"%lf", [r2[0] doubleValue]);   }  return EXIT_SUCCESS;}`

Timing (with the time command):

```d&c:         0.22user 0.00system 0:00.41elapsed
brute force: 13.53user 0.06system 0:13.87elapsed```