1// 2// KTMatrixDenseImp 3// KTMatrix collection class cluster 4// 5// KTMatrix class cluster mutable implementation subclass 6// Constant-time access to a mass-allocated chunk of memory 7// Ideal for mostly-populated matrices 8// Pointer arithmetic accounts for the speed 9// 10// Copyright (c) 2002 Chris Purcell. All rights reserved. 11// 12// You may use this code for whatever purposes you wish. 13// This code comes with no warranties, implied or otherwise. 14// Using it may damage your data. It shouldn't, but save a copy first. 15// That's a good idea anyway, actually. 16// 17 18#import "KTMutableMatrixDenseImp.h" 19#import "KTMatrixDenseEnumerator.h" 20 21@implementation KTMutableMatrixDenseImp 22 23+ (id)matrixWithMatrix:(KTMatrix *)other 24{ return [[[self alloc] initWithMatrix:other] autorelease]; } 25+ (id)matrixWithLocationHash:(id<KTLocationHash>)locationHash 26 objects:(NSArray *)objects 27 atLocations:(NSArray *)loc1s 28 byLocations:(NSArray *)loc2s 29{ 30 return [[[self alloc] initWithLocationHash:locationHash 31 objects:objects 32 atLocations:loc1s 33 byLocations:loc2s] autorelease]; 34} 35+ (id)matrixWithCapacity:(unsigned)numItems 36 locationHash:(id<KTLocationHash>)_hs 37{ 38 return [[[self alloc] initWithCapacity:numItems 39 locationHash:_hs] autorelease]; 40} 41- (id)initWithMatrix:(KTMatrix *)other 42{ 43 if ((self = [super init])) 44 { 45 NSEnumerator<KTMatrixEnumerator> *j = [other objectEnumeratorRetained]; 46 47 // Deal with the hashing object 48 if (NSShouldRetainWithZone([other locationHash], [self zone])) 49 hash = [[other locationHash] retain]; 50 else 51 hash = [[other locationHash] copyWithZone:[self zone]]; 52 hashIsCoordinateOptimized = [hash conformsToProtocol: 53 @protocol(KTLocationHashCoordinatesOptimization)]; 54 55 // Allocate memory for the storage array 56 count = 0; 57 capacity = [hash hashBound]; 58 array = NSZoneCalloc([self zone], 59 capacity, 60 sizeof(unsigned)); 61 62 // Fill the array 63 if ([j conformsToProtocol:@protocol(KTMatrixEnumerator)]) 64 { 65 id object; 66 while ((object = [j nextObject])) 67 { 68 array[[j hashedLocation]] = [object retain]; 69 count++; 70 } 71 } 72 else 73 { 74 NSNumber *key; 75 NSDictionary *matrixData = [other matrixData]; 76 NSEnumerator *k = [matrixData keyEnumerator]; 77 78 while ((key = [k nextObject])) 79 { 80 array[[key intValue]] = [[matrixData objectForKey:key] retain]; 81 count++; 82 } 83 } 84 [j release]; 85 } 86 return self; 87} 88- (id)initWithMatrixData:(NSDictionary *)matrixData 89 locationHash:(id<KTLocationHash>)locationHash 90{ 91 if ((self = [super init])) 92 { 93 NSNumber *key; 94 NSEnumerator *k = [matrixData keyEnumerator]; 95 96 // Deal with the hashing object 97 if (NSShouldRetainWithZone(locationHash, [self zone])) 98 hash = [locationHash retain]; 99 else 100 hash = [locationHash copyWithZone:[self zone]]; 101 hashIsCoordinateOptimized = [hash conformsToProtocol: 102 @protocol(KTLocationHashCoordinatesOptimization)]; 103 104 // Allocate memory for the storage array 105 count = 0; 106 capacity = [hash hashBound]; 107 array = NSZoneCalloc([self zone], 108 capacity, 109 sizeof(unsigned)); 110 111 // Fill the array 112 while ((key = [k nextObject])) 113 { 114 array[[key intValue]] = [[matrixData objectForKey:key] retain]; 115 count++; 116 } 117 } 118 return self; 119} 120- (id)initWithLocationHash:(id<KTLocationHash>)locationHash 121{ 122 if ((self = [super init])) 123 { 124 // Deal with the hashing object 125 if (NSShouldRetainWithZone(locationHash, [self zone])) 126 hash = [locationHash retain]; 127 else 128 hash = [locationHash copyWithZone:[self zone]]; 129 hashIsCoordinateOptimized = [hash conformsToProtocol: 130 @protocol(KTLocationHashCoordinatesOptimization)]; 131 132 // Allocate memory for the storage array 133 count = 0; 134 capacity = [hash hashBound]; 135 array = NSZoneCalloc([self zone], 136 capacity, 137 sizeof(unsigned)); 138 } 139 return self; 140} 141- (id)initWithLocationHash:(id<KTLocationHash>)locationHash 142 objects:(NSArray *)objects 143 atLocations:(NSArray *)loc1s 144 byLocations:(NSArray *)loc2s 145{ 146 if ((self = [super init])) 147 { 148 unsigned i; 149 id *position; 150 151 // Deal with the hashing object 152 if (NSShouldRetainWithZone(locationHash, [self zone])) 153 hash = [locationHash retain]; 154 else 155 hash = [locationHash copyWithZone:[self zone]]; 156 hashIsCoordinateOptimized = [hash conformsToProtocol: 157 @protocol(KTLocationHashCoordinatesOptimization)]; 158 159 // Check the parameters are sane 160 if ([objects count] != [loc1s count]) 161 [NSException raise:NSInvalidArgumentException 162 format: 163 @"Objects and locations arrays not of equal length"]; 164 if ([loc1s count] != [loc2s count]) 165 [NSException raise:NSInvalidArgumentException 166 format: 167 @"Locations arrays not of equal length"]; 168 169 // Allocate memory for the storage array 170 count = 0; 171 capacity = [hash hashBound]; 172 array = NSZoneCalloc([self zone], 173 capacity, 174 sizeof(unsigned)); 175 176 // Fill the storage array 177 for (i = 0; i < [loc1s count]; i++) 178 { 179 position = &array[[hash 180 hashForLocation:[loc1s objectAtIndex:i] 181 byLocation:[loc2s objectAtIndex:i]]]; 182 if (*position != NULL) 183 [*position release]; 184 else 185 count++; 186 *position = [[objects objectAtIndex:i] retain]; 187 } 188 } 189 return self; 190} 191- (id)initWithCapacity:(unsigned)numItems 192 locationHash:(id<KTLocationHash>)locationHash 193{ 194 if ((self = [super init])) 195 { 196 // Deal with the hashing object 197 if (NSShouldRetainWithZone(locationHash, [self zone])) 198 hash = [locationHash retain]; 199 else 200 hash = [locationHash copyWithZone:[self zone]]; 201 hashIsCoordinateOptimized = [hash conformsToProtocol: 202 @protocol(KTLocationHashCoordinatesOptimization)]; 203 204 // Allocate memory for the storage array 205 count = 0; 206 capacity = [hash hashBound]; 207 array = NSZoneCalloc([self zone], 208 capacity, 209 sizeof(unsigned)); 210 } 211 return self; 212} 213 214//// Optimized versions 215- (id)initWithLocationHash:(id<KTLocationHash>)locationHash 216 object:(id)object 217 atHashedLocation:(unsigned)loc 218{ 219 if ((self = [super init])) 220 { // Deal with the hashing object 221 if (NSShouldRetainWithZone(locationHash, [self zone])) 222 hash = [locationHash retain]; 223 else 224 hash = [locationHash copyWithZone:[self zone]]; 225 hashIsCoordinateOptimized = [hash 226 conformsToProtocol:@protocol(KTLocationHashCoordinatesOptimization)]; 227 228 // Allocate memory for the storage array 229 count = 1; 230 capacity = [hash hashBound]; 231 array = NSZoneCalloc([self zone], 232 capacity, 233 sizeof(unsigned)); 234 235 // Fill the storage array 236 array[loc] = [object retain]; 237 } 238 return self; 239} 240 241 242// Accessor methods 243- (id)objectAtLocation:(NSDictionary *)loc 244 byLocation:(NSDictionary *)loc2; 245{ return array[[hash hashForLocation:loc byLocation:loc2]]; } 246 247 //// Optimized algorithms 248- (id)objectAtCoordinates:(unsigned)x,... 249{ 250 va_list args; 251 252 va_start(args, x); 253 254 if (hashIsCoordinateOptimized) 255 { 256 id ret = array[[(id)hash hashForCoordinatesList:x :&args]]; 257 va_end(args); 258 return ret; 259 } 260 else 261 { 262 NSMutableArray *_array 263 = [NSMutableArray arrayWithObject:[NSNumber numberWithInt:x]]; 264 unsigned axes = [self dimension]; 265 266 while ([_array count] < axes) 267 [_array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]]; 268 269 va_end(args); 270 271 return [self objectAtCoordinateArray:_array]; 272 } 273} 274- (unsigned)dimension 275{ 276 if (hashIsCoordinateOptimized) return [(id)hash dimension]; 277 else return [[self axes] count]; 278} 279- (unsigned)lowerBoundForDimension:(unsigned)dim 280{ 281 if (hashIsCoordinateOptimized) return [(id)hash lowerBoundForDimension:dim]; 282 else return [self lowerBoundForAxis: [[self axes] objectAtIndex:dim]]; 283} 284- (unsigned)upperBoundForDimension:(unsigned)dim 285{ 286 if (hashIsCoordinateOptimized) return [(id)hash upperBoundForDimension:dim]; 287 else return [self upperBoundForAxis: [[self axes] objectAtIndex:dim]]; 288} 289 290- (id<KTLocationHash>)locationHash 291{ return hash; } 292- (NSDictionary *)matrixData 293{ 294 NSMutableDictionary *data = [NSMutableDictionary 295 dictionaryWithCapacity:count]; 296 unsigned i; 297 298 for (i = 0; i < capacity; i++) 299 if (array[i]) 300 [data setObject:array[i] 301 forKey:[NSNumber numberWithInt:i]]; 302 return data; 303} 304 305- (NSEnumerator *)objectEnumerator 306{ 307 return [[[KTMatrixDenseEnumerator allocWithZone:[self zone]] 308 initWithArray:array 309 ofCapacity:capacity 310 collection:self] autorelease]; 311} 312- (NSEnumerator *)objectEnumeratorRetained 313{ 314 return [[KTMatrixDenseEnumerator allocWithZone:[self zone]] 315 initWithArray:array 316 ofCapacity:capacity 317 collection:self]; 318} 319- (unsigned)count 320{ return count; } 321 322 323 //// Mutator methods 324- (void)setMatrix:(KTMatrix *)other 325{ 326 NSEnumerator<KTMatrixEnumerator> *j = [other objectEnumerator]; 327 328 [hash release]; 329 NSZoneFree([self zone], array); 330 331 // Deal with the hashing object 332 if (NSShouldRetainWithZone([other locationHash], [self zone])) 333 hash = [[other locationHash] retain]; 334 else 335 hash = [[other locationHash] copyWithZone:[self zone]]; 336 hashIsCoordinateOptimized = [hash conformsToProtocol: 337 @protocol(KTLocationHashCoordinatesOptimization)]; 338 339 // Allocate memory for the storage array 340 count = 0; 341 capacity = [hash hashBound]; 342 array = NSZoneCalloc([self zone], 343 capacity, 344 sizeof(unsigned)); 345 346 // Fill the array 347 if ([j conformsToProtocol:@protocol(KTMatrixEnumerator)]) 348 { 349 id object; 350 while ((object = [j nextObject])) 351 { 352 array[[j hashedLocation]] = [object retain]; 353 count++; 354 } 355 } 356 else 357 { 358 NSNumber *key; 359 NSDictionary *matrixData = [other matrixData]; 360 NSEnumerator *k = [matrixData keyEnumerator]; 361 362 while ((key = [k nextObject])) 363 { 364 array[[key intValue]] = [[matrixData objectForKey:key] retain]; 365 count++; 366 } 367 } 368} 369- (void)setObject:(id)object 370 atLocation:(NSDictionary *)loc1 371 byLocation:(NSDictionary *)loc2 372{ 373 id *position = &array[[hash 374 hashForLocation:loc1 375 byLocation:loc2]]; 376 if (*position != NULL) 377 [*position release]; 378 else 379 count++; 380 *position = [object retain]; 381} 382- (void) setObject:(id)object 383 atHashedLocation:(unsigned)loc 384{ 385 if (array[loc] != NULL) 386 [array[loc] release]; 387 else 388 count++; 389 array[loc] = [object retain]; 390} 391- (void)removeObjectAtLocation:(NSDictionary *)loc1 392 byLocation:(NSDictionary *)loc2; 393{ 394 id *position = &array[[hash 395 hashForLocation:loc1 396 byLocation:loc2]]; 397 if (*position != NULL) 398 { 399 [*position release]; 400 *position = NULL; 401 count--; 402 } 403} 404- (void)removeAllObjects 405{ 406 unsigned i; 407 408 for (i = 0; i < capacity; i++) 409 { 410 if (array[i]) 411 { 412 [array[i] release]; 413 array[i] = NULL; 414 } 415 } 416 count = 0; 417} 418 419//// Optimized versions 420- (void) setObject:(id)object 421 atCoordinates:(unsigned)x,... 422{ 423 va_list args; 424 425 va_start(args, x); 426 427 if (hashIsCoordinateOptimized) 428 { 429 id *position = &array[[(id)hash hashForCoordinatesList:x :&args]]; 430 if (*position != NULL) 431 [*position release]; 432 else 433 count++; 434 *position = [object retain]; 435 } 436 else 437 { 438 NSMutableArray *_array = [NSMutableArray arrayWithObject: 439 [NSNumber numberWithInt:x]]; 440 unsigned axes = [self dimension]; 441 442 while ([_array count] < axes) 443 [_array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]]; 444 445 va_end(args); 446 [self setObject:object 447 atCoordinateArray:_array]; 448 return; 449 } 450} 451- (void)setObjectsAtCoordinates:(id)object1,... 452{ 453 id object = object1; 454 va_list args; 455 456 if (object1 != 0) 457 { 458 va_start(args, object1); 459 460 if (hashIsCoordinateOptimized) 461 { 462 // SELs/IMPs to speed up repeated method calls 463 SEL hashListSEL = @selector(hashForCoordinatesList:); 464 SEL setObjSEL = @selector(setObject:atHashedLocation:); 465 unsigned (*hashListIMP)(id, SEL, ...); 466 void (*setObjIMP)(id, SEL, ...); 467 468 hashListIMP = (unsigned (*)(id, SEL, ...)) 469 [(id)hash methodForSelector:hashListSEL]; 470 setObjIMP = (void (*)(id, SEL, ...)) 471 [self methodForSelector:setObjSEL]; 472 do 473 { 474 setObjIMP(self, setObjSEL, object, 475 hashListIMP(hash,hashListSEL,&args)); 476 } 477 while (object = va_arg(args, id)); 478 } 479 else 480 { 481 NSMutableArray *objects = [NSMutableArray array]; 482 NSMutableArray *coords = [NSMutableArray array]; 483 unsigned dimension = [self dimension]; 484 485 do 486 { 487 NSMutableArray *coord = [NSMutableArray arrayWithCapacity: 488 dimension]; 489 [objects addObject:object]; 490 while ([coord count] < dimension) 491 [coord addObject:[NSNumber numberWithInt: 492 va_arg(args, unsigned)]]; 493 [coords addObject:coord]; 494 } 495 while (object = va_arg(args, id)); 496 497 [self setObjects:objects 498 atCoordinateArrays:coords]; 499 } 500 } 501 502 va_end(args); 503} 504- (void)removeObjectAtCoordinates:(unsigned)x,... 505{ 506 va_list args; 507 508 va_start(args, x); 509 510 if (hashIsCoordinateOptimized) 511 { 512 id *position = &array[[(id)hash hashForCoordinatesList:x :&args]]; 513 if (*position != NULL) 514 { 515 [*position release]; 516 *position = NULL; 517 count--; 518 } 519 } 520 else 521 { 522 NSMutableArray *_array = [NSMutableArray arrayWithObject: 523 [NSNumber numberWithInt:x]]; 524 unsigned axes = [self dimension]; 525 526 while ([_array count] < axes) 527 [_array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]]; 528 [self removeObjectAtCoordinateArray:_array]; 529 } 530 531 va_end(args); 532} 533 534- (void)dealloc 535{ 536 unsigned i; 537 538 for (i = 0; i < capacity; i++) 539 if (array[i]) 540 [array[i] release]; 541 [hash release]; 542 NSZoneFree([self zone], array); 543 [super dealloc]; 544} 545 546@end 547