1// 2// KTMatrixSparseImp 3// KTMatrix collection class cluster 4// 5// KTMatrix class cluster implementation subclass 6// Uses hash tables to reference a mass-allocated chunk of memory 7// Ideal for sparsely-populated matrices 8// Sacrifices some speed for a considerable potential memory saving 9// Uses a O(log(n)) binary search algorithm to find object 10// 11// Copyright (c) 2002 Chris Purcell. All rights reserved. 12// 13// You may use this code for whatever purposes you wish. 14// This code comes with no warranties, implied or otherwise. 15// Using it may damage your data. It shouldn't, but save a copy first. 16// That's a good idea anyway, actually. 17// 18 19#import "KTMatrixSparseImp.h" 20#import "KTMatrixSparseEnumerator.h" 21 22static int compare(const void * elem1, const void * elem2 ) 23{ 24 if (((const struct KTMatrixSparseElement *)elem1)->hashedLocation > 25 ((const struct KTMatrixSparseElement *)elem2)->hashedLocation) 26 return 1; 27 if (((const struct KTMatrixSparseElement *)elem1)->hashedLocation < 28 ((const struct KTMatrixSparseElement *)elem2)->hashedLocation) 29 return -1; 30 return 0; 31} 32 33#define SearchAndLocate(_aim, ret) \ 34{ \ 35 unsigned low = 0, high = count, middle; \ 36 unsigned aim = _aim; \ 37 struct KTMatrixSparseElement *elements = memory; \ 38 while (high > low + 1) \ 39 { \ 40 middle = (high - low)/2+low; \ 41 if (elements[middle].hashedLocation == aim) \ 42 high = low = middle; \ 43 else if (elements[middle].hashedLocation < aim) \ 44 low = middle + 1; \ 45 else \ 46 high = middle; \ 47 } \ 48 middle = (high - low)/2+low; \ 49 if (elements[middle].hashedLocation == aim) \ 50 ret = elements[middle].object; \ 51 else \ 52 ret = NULL; \ 53} 54 55 56@implementation KTMatrixSparseImp 57 58+ (id)matrixWithMatrix:(KTMatrix *)other 59{ return [[[self alloc] initWithMatrix:other] autorelease]; } 60+ (id)matrixWithLocationHash:(id<KTLocationHash>)locationHash 61{ return [[[self alloc] initWithLocationHash:locationHash] autorelease]; } 62+ (id)matrixWithLocationHash:(id<KTLocationHash>)locationHash 63 objects:(NSArray *)objects 64 atLocations:(NSArray *)loc1s 65 byLocations:(NSArray *)loc2s 66{ 67 return [[[self alloc] initWithLocationHash:locationHash 68 objects:objects 69 atLocations:loc1s 70 byLocations:loc2s] autorelease]; 71} 72- (id)initWithMatrix:(KTMatrix *)other 73{ 74 NSEnumerator<KTMatrixEnumerator> *j = [other objectEnumeratorRetained]; 75 if ([j conformsToProtocol:@protocol(KTMatrixEnumerator)]) 76 { 77 if ((self = [super init])) 78 { 79 struct KTMatrixSparseElement *elements; 80 id object; 81 82 // Deal with the hashing object 83 if (NSShouldRetainWithZone([other locationHash], [self zone])) 84 hash = [[other locationHash] retain]; 85 else 86 hash = [[other locationHash] copyWithZone:[self zone]]; 87 hashIsCoordinateOptimized = [hash conformsToProtocol: 88 @protocol(KTLocationHashCoordinatesOptimization)]; 89 90 // Allocate memory 91 count = 0; 92 memory = NSZoneCalloc([self zone], 93 [other count], 94 sizeof(struct KTMatrixSparseElement)); 95 elements = memory; 96 97 // Fill the memory 98 while ((object = [j nextObject])) 99 { 100 elements[count].hashedLocation = [j hashedLocation]; 101 elements[count].object = [object retain]; 102 count++; 103 } 104 qsort(elements, count, sizeof(struct KTMatrixSparseElement), 105 compare); 106 } 107 } 108 else 109 { 110 self = [self initWithMatrixData:[other matrixData] 111 locationHash:[other locationHash]]; 112 } 113 [j release]; 114 return self; 115} 116- (id)initWithLocationHash:(id<KTLocationHash>)locationHash 117{ 118 if ((self = [super init])) 119 { 120 // Deal with the hashing object 121 if (NSShouldRetainWithZone(locationHash, [self zone])) 122 hash = [locationHash retain]; 123 else 124 hash = [locationHash copyWithZone:[self zone]]; 125 hashIsCoordinateOptimized = [hash conformsToProtocol: 126 @protocol(KTLocationHashCoordinatesOptimization)]; 127 128 count = 0; 129 memory = nil; 130 } 131 return self; 132} 133- (id)initWithMatrixData:(NSDictionary *)matrixData 134 locationHash:(id<KTLocationHash>)locationHash 135{ 136 if ((self = [super init])) 137 { 138 struct KTMatrixSparseElement *elements; 139 NSNumber *key; 140 NSEnumerator *j = [matrixData keyEnumerator]; 141 142 // Deal with the hashing object 143 if (NSShouldRetainWithZone(locationHash, [self zone])) 144 hash = [locationHash retain]; 145 else 146 hash = [locationHash copyWithZone:[self zone]]; 147 hashIsCoordinateOptimized = [hash conformsToProtocol: 148 @protocol(KTLocationHashCoordinatesOptimization)]; 149 150 // Allocate memory 151 count = 0; 152 memory = NSZoneCalloc([self zone], 153 count, 154 sizeof(struct KTMatrixSparseElement)); 155 elements = memory; 156 157 // Fill the memory 158 while ((key = [j nextObject])) 159 { 160 elements[count].hashedLocation = [key intValue]; 161 elements[count].object = [[matrixData objectForKey:key] retain]; 162 count++; 163 } 164 qsort(elements + 1, count, sizeof(struct KTMatrixSparseElement), 165 compare); 166 } 167 return self; 168} 169- (id)initWithLocationHash:(id<KTLocationHash>)locationHash 170 object:(id)object 171 atHashedLocation:(unsigned)loc 172{ 173 if ((self = [super init])) 174 { 175 struct KTMatrixSparseElement *element; 176 unsigned i; 177 178 // Deal with the hashing object 179 if (NSShouldRetainWithZone(locationHash, [self zone])) 180 hash = [locationHash retain]; 181 else 182 hash = [locationHash copyWithZone:[self zone]]; 183 hashIsCoordinateOptimized = [hash conformsToProtocol: 184 @protocol(KTLocationHashCoordinatesOptimization)]; 185 186 // Allocate memory 187 count = 1; 188 memory = NSZoneMalloc([self zone], 189 sizeof(struct KTMatrixSparseElement)); 190 element = memory; 191 192 // Fill the memory 193 for (i = 0; i < count; i++) 194 { 195 element->hashedLocation = loc; 196 element->object = [object retain]; 197 } 198 } 199 return self; 200} 201- (id)initWithLocationHash:(id<KTLocationHash>)locationHash 202 objects:(NSArray *)objects 203 atLocations:(NSArray *)loc1s 204 byLocations:(NSArray *)loc2s 205{ 206 if ((self = [super init])) 207 { 208 struct KTMatrixSparseElement *elements; 209 unsigned i; 210 211 // Deal with the hashing object 212 if (NSShouldRetainWithZone(locationHash, [self zone])) 213 hash = [locationHash retain]; 214 else 215 hash = [locationHash copyWithZone:[self zone]]; 216 hashIsCoordinateOptimized = [hash conformsToProtocol: 217 @protocol(KTLocationHashCoordinatesOptimization)]; 218 219 // Check the parameters are sane 220 if ([objects count] != [loc1s count]) 221 [NSException raise:NSInvalidArgumentException 222 format: 223 @"Objects and locations arrays not of equal length"]; 224 if ([loc1s count] != [loc2s count]) 225 [NSException raise:NSInvalidArgumentException 226 format: 227 @"Locations arrays not of equal length"]; 228 229 // Allocate memory 230 count = [objects count]; 231 memory = NSZoneCalloc([self zone], 232 count, 233 sizeof(struct KTMatrixSparseElement)); 234 elements = memory; 235 236 // Fill the memory 237 for (i = 0; i < count; i++) 238 { 239 elements[i].hashedLocation = [hash 240 hashForLocation:[loc1s objectAtIndex:i] 241 byLocation:[loc2s objectAtIndex:i]]; 242 elements[i].object = [[objects objectAtIndex:i] retain]; 243 } 244 qsort(elements, count, sizeof(struct KTMatrixSparseElement), 245 compare); 246 } 247 return self; 248} 249 250// Accessor methods 251- (id)objectAtLocation:(NSDictionary *)loc 252 byLocation:(NSDictionary *)loc2; 253{ 254 unsigned low = 0, high = count, middle; 255 unsigned aim = [hash hashForLocation:loc byLocation:loc2]; 256 struct KTMatrixSparseElement *elements = memory; 257 while (high > low + 1) 258 { 259 middle = (high - low)/2+low; 260 if (elements[middle].hashedLocation == aim) 261 high = low = middle; 262 else if (elements[middle].hashedLocation < aim) 263 low = middle + 1; 264 else 265 high = middle; 266 } 267 middle = (high - low)/2+low; 268 if (elements[middle].hashedLocation == aim) 269 return elements[middle].object; 270 else 271 return NULL; 272} 273 274//// Optimized algorithms 275- (id)objectAtCoordinates:(unsigned)x,... 276{ 277 va_list args; 278 279 va_start(args, x); 280 281 if (hashIsCoordinateOptimized) 282 { 283 id ret; 284 SearchAndLocate([(id)hash hashForCoordinatesList:x :&args], ret); 285 va_end(args); 286 return ret; 287 } 288 else 289 { 290 NSMutableArray *array 291 = [NSMutableArray arrayWithObject:[NSNumber numberWithInt:x]]; 292 unsigned axes = [self dimension]; 293 294 while ([array count] < axes) 295 [array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]]; 296 297 va_end(args); 298 299 return [self objectAtCoordinateArray:array]; 300 } 301} 302- (unsigned)dimension 303{ 304 if (hashIsCoordinateOptimized) return [(id)hash dimension]; 305 else return [[self axes] count]; 306} 307- (unsigned)lowerBoundForDimension:(unsigned)dim 308{ 309 if (hashIsCoordinateOptimized) return [(id)hash lowerBoundForDimension:dim]; 310 else return [self lowerBoundForAxis: [[self axes] objectAtIndex:dim]]; 311} 312- (unsigned)upperBoundForDimension:(unsigned)dim 313{ 314 if (hashIsCoordinateOptimized) return [(id)hash upperBoundForDimension:dim]; 315 else return [self upperBoundForAxis: [[self axes] objectAtIndex:dim]]; 316} 317 318- (id<KTLocationHash>)locationHash 319{ return hash; } 320- (NSDictionary *)matrixData 321{ 322 NSMutableDictionary *data = [NSMutableDictionary 323 dictionaryWithCapacity:count]; 324 struct KTMatrixSparseElement *i = 325 ((struct KTMatrixSparseElement *)memory); 326 struct KTMatrixSparseElement *iend = i + count; 327 for (; i < iend; i++) 328 [data setObject:i->object 329 forKey:[NSNumber numberWithInt:i->hashedLocation]]; 330 return data; 331} 332 333- (NSEnumerator *)objectEnumerator 334{ 335 return [[[KTMatrixSparseEnumerator allocWithZone:[self zone]] 336 initWithArray:memory 337 count:count 338 collection:self] autorelease]; 339} 340- (NSEnumerator *)objectEnumeratorRetained 341{ 342 return [[KTMatrixSparseEnumerator allocWithZone:[self zone]] 343 initWithArray:memory 344 count:count 345 collection:self]; 346} 347- (unsigned)count 348{ return count; } 349 350- (id)copyWithZone:(NSZone *)zone 351{ 352 if (NSShouldRetainWithZone(self, zone)) 353 return [self retain]; 354 else 355 return [super copyWithZone:zone]; 356} 357 358- (void)dealloc 359{ 360 struct KTMatrixSparseElement *i = 361 ((struct KTMatrixSparseElement *)memory); 362 struct KTMatrixSparseElement *iend = i + count; 363 for (; i < iend; i++) 364 [i->object release]; 365 [hash release]; 366 NSZoneFree([self zone], memory); 367 [super dealloc]; 368} 369@end 370