I've got a method that takes in the annotations (custom PostLocationAnnotation class) to be displayed on a map view and clusters close ones together, outputting an array of MKAnnotation of PostLocationAnnotations and LocationGroupAnnotations (the clusters, which each contain some PostLocationAnnotations). Here's how I call the function (from within an 'updateAnnotations' method, called when the viewport of the map changes):
[annotationsToAdd addObjectsFromArray:[ffMapView annotations]];
[ffMapView addAnnotations:[self clusterAnnotations:annotationsToAdd WithEpsilon:20.0f andMinPts:4]];
annotationsToAdd is initially populated by the annotations that have been retrieved from the server that have not already been added to the map. Therefore I am passing the full list of the annotations that should be put on the map into the clusterAnnotations method. Here is the body of the method:
- (NSArray *)clusterAnnotations:(NSArray *)annotations WithEpsilon:(float)eps andMinPts:(int)minPts
{
NSMutableSet *D = [[NSMutableSet alloc] initWithCapacity:[annotations count]];
NSMutableArray *C = [[NSMutableArray alloc] init];
for (id <MKAnnotation> annotation in annotations)
{
if ([annotation isKindOfClass:[PostLocationAnnotation class]])
{
NSMutableDictionary *dictEntry = [NSMutableDictionary dictionaryWithObjectsAndKeys:
annotation, @"point",
[NSNumber numberWithBool:NO], @"visited",
[NSNumber numberWithBool:NO], @"noise",
[NSNumber numberWithBool:NO], @"clustered", nil];
[D addObject:dictEntry];
[dictEntry release];
} else if ([annotation isKindOfClass:[LocationGroupAnnotation class]])
{
for (PostLocationAnnotation *location in [(LocationGroupAnnotation *)annotation locations])
{
NSMutableDictionary *dictEntry = [NSMutableDictionary dictionaryWithObjectsAndKeys:
location, @"point",
[NSNumber numberWithBool:NO], @"visited",
[NSNumber numberWithBool:NO], @"noise",
[NSNumber numberWithBool:NO], @"clustered", nil];
[D addObject:dictEntry];
[dictEntry release];
}
}
}
for (NSMutableDictionary *P in D)
{
if ([P objectForKey:@"visited"] == [NSNumber numberWithBool:NO])
{
[P setValue:[NSNumber numberWithBool:YES] forKey:@"visited"];
NSMutableSet *N = [[NSMutableSet alloc] initWithSet:[self regionQueryForPoint:P andEpsilon:eps fromList:D]];
if ([N count] < minPts)
{
[P setValue:[NSNumber numberWithBool:YES] forKey:@"noise"];
} else {
LocationGroupAnnotation *newCluster = [[LocationGroupAnnotation alloc] initWithLocations:nil];
[C addObject:newCluster];
[self expandDbscanClusterWithPoint:P andRegion:N andCluster:newCluster andEpsilon:eps andMinPts:minPts fromList:D];
[newCluster release];
}
[N release];
}
}
NSMutableArray *annotationsToAdd = [[[NSMutableArray alloc] initWithCapacity:[annotations count]] autorelease];
for (NSMutableDictionary *P in D)
{
if ([P objectForKey:@"clustered"] == [NSNumber numberWithBool:NO])
{
[annotationsToAdd addObject:[P objectForKey:@"point"]];
}
}
for (LocationGroupAnnotation *cluster in C)
{
[cluster updateCenterCoordinate];
}
[annotationsToAdd addObjectsFromArray:(NSArray *)C];
[D release];
[C release];
return (NSArray *)annotationsToAdd;
}
When I run this I get a zombie message, and I have found that removing [D release] fixes the zombie but causes a leak. Looking at Instruments I can see that the memory address is first Malloc'd in clusterAnnotations, then retained and released a couple of times, then retained a large number of times by regionQueryForPoint (reaching a peak of 47 references), then released twice by clusterAnnotations, then released by [NSAutoreleasePool drain] until the refcount reaches -1 and I get the zombie message error. Here is the code for regionQueryForPoint:
- (NSSet *)regionQueryForPoint:(NSMutableDictionary *)P andEpsilon:(float)eps fromList:(NSMutableSet *)D
{
NSMutableSet *N = [[[NSMutableSet alloc] init] autorelease];
for (NSMutableDictionary *dictEntry in D)
{
if ((dictEntry != P) &&
([[dictEntry objectForKey:@"point"] isKindOfClass:[PostLocationAnnotation class]]))
{
CGPoint p1 = [ffMapView convertCoordinate:[[P objectForKey:@"point"] coordinate] toPointToView:self.view];
CGPoint p2 = [ffMapView convertCoordinate:[[dictEntry objectForKey:@"point"] coordinate] toPointToView:self.view];
float dX = p1.x - p2.x;
float dY = p1.y - p2.y;
if (sqrt(pow(dX,2)+pow(dY,2)) < eps)
{
[N addObject:dictEntry];
}
}
}
return (NSSet *)N;
}
The large number of retains appear to happen when regionQueryForPoint is called from the expandDbScanClusterWithPoint method, so I've included that here for completeness:
- (void)expandDbscanClusterWithPoint:(NSMutableDictionary *)P andRegion:(NSMutableSet *)N
andCluster:(LocationGroupAnnotation *)cluster
andEpsilon:(float)eps
andMinPts:(int)minPts
fromList:(NSMutableSet *)D
{
[cluster addAnnotation:(PostLocationAnnotation *)[P objectForKey:@"point"]];
[P setValue:[NSNumber numberWithBool:YES] forKey:@"clustered"];
BOOL finished = NO;
while (!finished)
{
finished = YES;
for (NSMutableDictionary *nextP in N)
{
if ([nextP objectForKey:@"visited"] == [NSNumber numberWithBool:NO])
{
[nextP setValue:[NSNumber numberWithBool:YES] forKey:@"visited"];
NSSet *nextN = [self regionQueryForPoint:nextP andEpsilon:eps fromList:D];
if ([nextN count] >= minPts)
{
[N unionSet:nextN];
finished = NO;
break;
}
}
if ([nextP objectForKey:@"clustered"] == [NSNumber numberWithBool:NO])
{
[cluster addAnnotation:[nextP objectForKey:@"point"]];
[nextP setValue:[NSNumber numberWithBool:YES] forKey:@"clustered"];
}
}
}
}
I've been dissecting this for ages, counting references, watching pointers and everything but I just can't work out how to safely release this D set. Can anyone see anything I'm not seeing?
You seem to be over-releasing dictEntry with [dictEntry release];. When using dictionaryWithObjectsAndKeys, you're getting an autoreleased object back. So releasing it again will decrease the retain count.
EDIT: If you're unsure how it works and when you're actually retaining objects, you might want to have a look at the memory management docs:
You create an object using a method whose name begins with “alloc”, “new”, “copy”, or “mutableCopy” (for example, alloc, newObject, or mutableCopy).