Rosetta Code

Closest-pair problem/Objective-C: Difference between revisions

Page Discussion

Closest-pair problem/Objective-C (view source)

Revision as of 13:57, 1 September 2022

821 bytes removed ,  1 year ago
m
Fixed syntax highlighting.
m (Fixed syntax highlighting.)
 
(One intermediate revision by one other user not shown)
Line 4:
 
{{works with|Cocoa}}
<langsyntaxhighlight lang="objc">#import <Foundation/Foundation.h>
#import <math.h>
 
Line 10:
double xCoord, yCoord;
}
+ (idinstancetype)x: (double)x y: (double)y;
- (idinstancetype)initWithX: (double)x andY: (double)y;
- (double)x;
- (double)y;
Line 21:
@implementation Point
 
+ (idinstancetype)x: (double)x y: (double)y {
return [[[self alloc] initWithX: x andY: y] autorelease];
}
 
- (idinstancetype)initWithX: (double)x andY: (double)y {
if (!(self = [super init])) return nil;{
xCoord = x;
 
xCoord yCoord = xy;
}
yCoord = y;
 
return self;
}
Line 52 ⟶ 51:
else return NSOrderedSame;
}
@end</langsyntaxhighlight>
 
<langsyntaxhighlight lang="objc">@interface ClosestPair : NSObject
+ (NSArray *)closestPairSimple: (NSArray *)pts;
+ (NSArray *)closestPair: (NSArray *)pts;
Line 64 ⟶ 63:
 
+ (NSArray *)closestPairSimple: (NSArray *)pts {
if ( [pts count] < 2 ) return @[ @HUGE_VAL ];
int i, j;▼
double c = [ pts[0] dist: pts[1] ];
if ( [pts count] < 2 ) return [NSArray arrayWithObject: [NSNumber numberWithDouble: HUGE_VAL]];
NSArray *r = @[ @(c), pts[0], pts[1] ];
double cfor(int i=0; [i < ([pts objectAtIndex: 0count] dist:- [pts1); objectAtIndex:i++) 1]];{
for(int j=i+1; j < [pts count]; j++) {▼
r = [NSArray
double t = [ pts[i] dist: pts[j] ];
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 @(t), pts[i], pts[j] ];
arrayWithObjects: [NSNumber numberWithDouble: t],
[pts objectAtIndex: i],
[pts objectAtIndex: j], nil];
}
}
Line 95 ⟶ 85:
 
+ (NSArray *)closestPairPriv: (NSArray *)xP and: (NSArray *)yP {
▲ int inP, jk;
NSArray *pR, *pL, *minR, *minL;
NSMutableArray *yR, *yL, *joiningStrip, *tDist, *minDist;
double middleVLine;
int i, nP, k;
 
if ( [xP count] <= 3 ) {
Line 104 ⟶ 91:
} 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[pL objectAtIndex: (midx-1)] x];
for(int i=0; i < [yP count]; i++) {
if ( [[yP objectAtIndex: [i] x] <= middleVLine ) {
[yL addObject: [yP objectAtIndex: [i]];
} else {
[yR addObject: [yP objectAtIndex: [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 objectAtIndex: [i] x] - middleVLine) <
[[minDist objectAtIndex: [0] doubleValue] ) {
[joiningStrip addObject: [yP objectAtIndex: [i]];
}
}
NSMutableArray *tDist = minDist;
int nP = [joiningStrip count];
for(int i=0; i < (nP - 1); i++) {
int k = i + 1;
while( (k < nP) &&
( ([[joiningStrip objectAtIndex: [k] y] - [joiningStrip[i] y]) < [minDist[0] doubleValue] ) ) {
double d = [joiningStrip[i] dist: joiningStrip[k]];
[[joiningStrip objectAtIndex: i] y]) < [[minDist objectAtIndex: 0] doubleValue] ) ) {
[[minB objectAtIndex:if ( d < [tDist[0] doubleValue] ) {▼
double d = [[joiningStrip objectAtIndex: i] dist: [joiningStrip objectAtIndex: k]];
if ( dtDist <= @[[tDist objectAtIndex:@(d), 0joiningStrip[i], doubleValuejoiningStrip[k] ) {];
tDist = [NSArray arrayWithObjects: [NSNumber numberWithDouble: d],
[joiningStrip objectAtIndex: i],
[joiningStrip objectAtIndex: k], nil];
}
k++;
}
}
[yL release]; [yR release];
return tDist;
}
Line 148 ⟶ 131:
 
+ (id)minBetween: (id)minA and: (id)minB {
if ( [[minA[0] objectAtIndex:doubleValue] < [minB[0] doubleValue] <) {
▲ [[minB objectAtIndex: 0] doubleValue] ) {
return minA;
} else {
Line 156 ⟶ 138:
}
 
@end</langsyntaxhighlight>
 
'''Testing'''
 
<langsyntaxhighlight lang="objc">#define NP 10000
 
int main()
{
@autoreleasepool {
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;
}</langsyntaxhighlight>
 
Timing (with the <tt>time</tt> command):
PureFox
9,477

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/136199...329468"