1// 2// KTMatrixDenseImp 3// KTMatrix collection class cluster 4// 5// KTMatrix class cluster 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 "KTMatrixDenseImp.h" 19#import "KTMatrixDenseEnumerator.h" 20 21@implementation KTMatrixDenseImp 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)initWithMatrix:(KTMatrix *)other 36{ 37 NSEnumerator<KTMatrixEnumerator> *j = [other objectEnumeratorRetained]; 38 if ([j conformsToProtocol:@protocol(KTMatrixEnumerator)]) 39 { 40 if ((self = [super init])) 41 { 42 id object; 43 44 // Deal with the hashing object 45 if (NSShouldRetainWithZone([other locationHash], [self zone])) 46 hash = [[other locationHash] retain]; 47 else 48 hash = [[other locationHash] copyWithZone:[self zone]]; 49 hashIsCoordinateOptimized = [hash conformsToProtocol: 50 @protocol(KTLocationHashCoordinatesOptimization)]; 51 52 // Allocate memory for the storage array 53 count = 0; 54 capacity = [hash hashBound]; 55 array = NSZoneCalloc([self zone], 56 capacity, 57 sizeof(unsigned)); 58 59 // Fill the array 60 while ((object = [j nextObject])) 61 { 62 array[[j hashedLocation]] = [object retain]; 63 count++; 64 } 65 } 66 } 67 else 68 { 69 self = [self initWithMatrixData:[other matrixData] 70 locationHash:[other locationHash]]; 71 } 72 [j release]; 73 return self; 74} 75- (id)initWithMatrixData:(NSDictionary *)matrixData 76 locationHash:(id<KTLocationHash>)locationHash 77{ 78 if ((self = [super init])) 79 { 80 NSNumber *key; 81 NSEnumerator *j = [matrixData keyEnumerator]; 82 83 // Deal with the hashing object 84 if (NSShouldRetainWithZone(locationHash, [self zone])) 85 hash = [locationHash retain]; 86 else 87 hash = [locationHash copyWithZone:[self zone]]; 88 hashIsCoordinateOptimized = [hash conformsToProtocol: 89 @protocol(KTLocationHashCoordinatesOptimization)]; 90 91 // Allocate memory for the storage array 92 count = [matrixData count]; 93 capacity = [hash hashBound]; 94 array = NSZoneCalloc([self zone], 95 capacity, 96 sizeof(unsigned)); 97 98 // Fill the array 99 while ((key = [j nextObject])) 100 array[[key intValue]] = [[matrixData objectForKey:key] retain]; 101 } 102 return self; 103} 104- (id)initWithLocationHash:(id<KTLocationHash>)locationHash 105 object:(id)object 106 atHashedLocation:(unsigned)loc 107{ 108 if ((self = [super init])) 109 { 110 // Deal with the hashing object 111 if (NSShouldRetainWithZone(locationHash, [self zone])) 112 hash = [locationHash retain]; 113 else 114 hash = [locationHash copyWithZone:[self zone]]; 115 hashIsCoordinateOptimized = [hash conformsToProtocol: 116 @protocol(KTLocationHashCoordinatesOptimization)]; 117 118 // Allocate memory for the storage array 119 count = 1; 120 capacity = [hash hashBound]; 121 array = NSZoneCalloc([self zone], 122 capacity, 123 sizeof(unsigned)); 124 125 // Fill the array 126 array[loc] = [object retain]; 127 } 128 return self; 129} 130- (id)initWithLocationHash:(id<KTLocationHash>)locationHash 131 objects:(NSArray *)objects 132 atLocations:(NSArray *)loc1s 133 byLocations:(NSArray *)loc2s 134{ 135 if ((self = [super init])) 136 { 137 id *position; 138 unsigned i; 139 140 // Deal with the hashing object 141 if (NSShouldRetainWithZone(locationHash, [self zone])) 142 hash = [locationHash retain]; 143 else 144 hash = [locationHash copyWithZone:[self zone]]; 145 hashIsCoordinateOptimized = [hash conformsToProtocol: 146 @protocol(KTLocationHashCoordinatesOptimization)]; 147 148 // Check the parameters are sane 149 if ([objects count] != [loc1s count]) 150 [NSException raise:NSInvalidArgumentException 151 format: 152 @"Objects and locations arrays not of equal length"]; 153 if ([loc1s count] != [loc2s count]) 154 [NSException raise:NSInvalidArgumentException 155 format: 156 @"Locations arrays not of equal length"]; 157 158 // Allocate memory for the storage array 159 count = 0; 160 capacity = [hash hashBound]; 161 array = NSZoneCalloc([self zone], 162 capacity, 163 sizeof(unsigned)); 164 165 // Fill the array 166 for (i = 0; i < [objects count]; i++) 167 { 168 position = &array[[hash 169 hashForLocation:[loc1s objectAtIndex:i] 170 byLocation:[loc2s objectAtIndex:i]]]; 171 if (*position != NULL) 172 [*position release]; 173 else 174 count++; 175 *position = [[objects objectAtIndex:i] retain]; 176 } 177 } 178 return self; 179} 180 181// Accessor methods 182- (id)objectAtLocation:(NSDictionary *)loc 183 byLocation:(NSDictionary *)loc2; 184{ return array[[hash hashForLocation:loc byLocation:loc2]]; } 185 186 //// Optimized algorithms 187- (id)objectAtCoordinates:(unsigned)x,... 188{ 189 va_list args; 190 191 va_start(args, x); 192 193 if (hashIsCoordinateOptimized) 194 { 195 id ret = array[[(id)hash hashForCoordinatesList:x :&args]]; 196 va_end(args); 197 return ret; 198 } 199 else 200 { 201 NSMutableArray *_array 202 = [NSMutableArray arrayWithObject:[NSNumber numberWithInt:x]]; 203 unsigned axes = [self dimension]; 204 205 while ([_array count] < axes) 206 [_array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]]; 207 208 va_end(args); 209 210 return [self objectAtCoordinateArray:_array]; 211 } 212} 213- (unsigned)dimension 214{ 215 if (hashIsCoordinateOptimized) return [(id)hash dimension]; 216 else return [[self axes] count]; 217} 218- (unsigned)lowerBoundForDimension:(unsigned)dim 219{ 220 if (hashIsCoordinateOptimized) return [(id)hash lowerBoundForDimension:dim]; 221 else return [self lowerBoundForAxis: [[self axes] objectAtIndex:dim]]; 222} 223- (unsigned)upperBoundForDimension:(unsigned)dim 224{ 225 if (hashIsCoordinateOptimized) return [(id)hash upperBoundForDimension:dim]; 226 else return [self upperBoundForAxis: [[self axes] objectAtIndex:dim]]; 227} 228 229 230- (id<KTLocationHash>)locationHash 231{ return hash; } 232- (NSDictionary *)matrixData 233{ 234 NSMutableDictionary *data = [NSMutableDictionary 235 dictionaryWithCapacity:count]; 236 unsigned i; 237 238 for (i = 0; i < capacity; i++) 239 if (array[i]) 240 [data setObject:array[i] 241 forKey:[NSNumber numberWithInt:i]]; 242 return data; 243} 244 245- (NSEnumerator *)objectEnumerator 246{ 247 return [[[KTMatrixDenseEnumerator allocWithZone:[self zone]] 248 initWithArray:array 249 ofCapacity:capacity 250 collection:self] autorelease]; 251} 252- (NSEnumerator *)objectEnumeratorRetained 253{ 254 return [[KTMatrixDenseEnumerator allocWithZone:[self zone]] 255 initWithArray:array 256 ofCapacity:capacity 257 collection:self]; 258} 259- (unsigned)count 260{ return count; } 261 262- (id)copyWithZone:(NSZone *)zone 263{ 264 if (NSShouldRetainWithZone(self, zone)) 265 return [self retain]; 266 else 267 return [super copyWithZone:zone]; 268} 269 270- (void)dealloc 271{ 272 unsigned i; 273 274 for (i = 0; i < capacity; i++) 275 if (array[i]) 276 [array[i] release]; 277 [hash release]; 278 NSZoneFree([self zone], array); 279 [super dealloc]; 280} 281@end 282