Closest-pair problem/Objective-C

From Rosetta Code

Works with: GNUstep

Works with: Cocoa

#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

@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

Testing

#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;
}

Timing (with the time command):

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