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

<lang objc>#import <Foundation/Foundation.h>

1. 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