1// 2// KTCuboidHash.m 3// KTMatrix collection class cluster 4// 5// Implements a cuboid location hashing algorithm 6// 7// Copyright (c) 2002 Chris Purcell. All rights reserved. 8// 9// You may use this code for whatever purposes you wish. 10// This code comes with no warranties, implied or otherwise. 11// Using it may damage your data. It shouldn't, but save a copy first. 12// That's a good idea anyway, actually. 13// 14 15#import "KTCuboidHash.h" 16 17@implementation KTCuboidHash 18 19+ (id)cuboidHash 20{ return [[[self alloc] init] autorelease]; } 21+ (id)cuboidHashWithBounds:(NSArray *)bounds 22{ return [[[self alloc] initWithBounds:bounds] autorelease]; } 23+ (id)cuboidHashWithBoundsList:(unsigned)bound1 :(va_list *)bounds 24{ return [[[self alloc] initWithBoundsList:bound1 :bounds] autorelease]; } 25- (id)init 26{ 27 if ((self = [super init])) 28 { 29 dimension = 0; 30 upperBounds = nil; 31 labels = nil; 32 } 33 return self; 34} 35- (id)initWithDimension:(unsigned)_dm 36 data:(const unsigned *)_da 37{ 38 if ((self = [super init])) 39 { 40 dimension = _dm; 41 upperBounds = NSZoneCalloc([self zone], 42 dimension, 43 sizeof(unsigned)); 44 memcpy((unsigned *)upperBounds, _da, sizeof(unsigned)*dimension); 45 labels = nil; 46 } 47 return self; 48} 49- (id)initWithBounds:(NSArray *)bounds 50{ 51 if ((self = [super init])) 52 { 53 unsigned bound, upperlimit = (unsigned)-1, product = 1; 54 dimension = [bounds count]; 55 upperBounds = nil; 56 labels = nil; 57 if (dimension > 0) 58 { 59 unsigned *tempBounds = NSZoneCalloc([self zone], 60 dimension, 61 sizeof(unsigned)); 62 unsigned i; 63 for (i = 0; i < dimension; i++) 64 { 65 bound = [[bounds objectAtIndex:i] intValue]; 66 if (product > 1) 67 if (((upperlimit / product) + 68 (((upperlimit % product)+1 == product)?1:0)) 69 < bound) 70 [NSException raise:NSInvalidArgumentException 71 format: 72 @"Bounds overflow the capacity of unsigned"]; 73 if ((product == 0) && (bound != 1)) 74 [NSException raise:NSInvalidArgumentException 75 format: 76 @"Bounds overflow the capacity of unsigned"]; 77 product *= bound; 78 tempBounds[i] = bound; 79 } 80 upperBounds = tempBounds; 81 } 82 } 83 return self; 84} 85- (id)initWithBoundsList:(unsigned)bound1 :(va_list *)bounds 86{ 87 if ((self = [super init])) 88 { 89 unsigned bound = bound1; 90 unsigned upperlimit = (unsigned)-1, product = 1; 91 92 dimension = 0; 93 upperBounds = nil; 94 labels = nil; 95 if (bound != 0) 96 { 97 NSZone *zone = [self zone]; 98 unsigned *tempBounds = nil; 99 do 100 { 101 dimension++; 102 if ((dimension & 7) == 1) 103 tempBounds = 104 NSZoneRealloc(zone, 105 tempBounds, 106 (dimension+7)*sizeof(unsigned)); 107 108 if (product > 1) 109 if (((upperlimit / product) + 110 (((upperlimit % product)+1 == product)?1:0)) 111 < bound) 112 [NSException raise:NSInvalidArgumentException 113 format: 114 @"Bounds overflow the capacity of unsigned"]; 115 if ((product == 0) && (bound != 1)) 116 [NSException raise:NSInvalidArgumentException 117 format: 118 @"Bounds overflow the capacity of unsigned"]; 119 product *= bound; 120 tempBounds[dimension-1] = bound; 121 } 122 while ((bound = va_arg(*bounds, unsigned)) != 0); 123 124 upperBounds = NSZoneRealloc(zone, 125 tempBounds, 126 dimension * sizeof(unsigned)); 127 } 128 } 129 return self; 130} 131 132 133- (unsigned)hashForLocation:(NSDictionary *)loc1 134 byLocation:(NSDictionary *)loc2 135{ 136 unsigned i, intval, hash = 0; 137 NSNumber *val; 138 139 for (i = 0; i < dimension; i++) 140 { // Go through each coordinate in turn 141 val = [loc1 objectForKey:[NSNumber numberWithInt:i]]; 142 if (val == nil) 143 val = [loc2 objectForKey:[NSNumber numberWithInt:i]]; 144 145 // Assertions 146 if (val != nil) 147 [NSException raise:NSInvalidArgumentException 148 format: 149 @"Not enough axes given to cuboid matrix"]; 150 intval = [val intValue]; 151 if (intval < 0) 152 [NSException raise:NSInvalidArgumentException 153 format: 154 @"Coord %d (%d) less than lower bound (0)", 155 i, intval]; 156 if (intval >= upperBounds[i]) 157 [NSException raise:NSInvalidArgumentException 158 format: 159 @"Coord %d (%d) overflows upper bound (%d) in matrix", 160 i, intval, upperBounds[i]]; 161 162 // Hash calculation 163 hash *= upperBounds[i]; 164 hash += intval; 165 } 166 return hash; 167} 168- (unsigned)hashForCoordinatesList:(va_list *)coords 169{ // Optional optimization 170 unsigned i, val, hash = 0; 171 172 for (i = 0; i < dimension; i++) 173 { // Go through each coordinate in turn 174 val = va_arg(*coords, unsigned); 175 176 // Assertions 177 if (val >= upperBounds[i]) 178 [NSException raise:NSInvalidArgumentException 179 format: 180 @"Coord %d (%d) overflows upper bound (%d) in matrix", 181 i, val, upperBounds[i]]; 182 183 // Hash calculation 184 hash *= upperBounds[i]; 185 hash += val; 186 } 187 return hash; 188} 189- (unsigned)hashForCoordinatesList:(unsigned)x :(va_list *)coords 190{ // Optional optimization 191 unsigned i, val, hash = x; 192 193 for (i = 1; i < dimension; i++) 194 { // Go through each coordinate in turn 195 val = va_arg(*coords, unsigned); 196 197 // Assertions 198 if (val >= upperBounds[i]) 199 return nil; 200 201 // Hash calculation 202 hash *= upperBounds[i]; 203 hash += val; 204 } 205 return hash; 206} 207 208- (NSArray *)axes 209{ 210 if (labels == nil) 211 { 212 unsigned i; 213 NSMutableArray *dims = 214 [NSMutableArray arrayWithCapacity:dimension]; 215 for (i = 0; i < dimension; i++) 216 [dims addObject:[[[NSNumber allocWithZone:[self zone]] 217 initWithInt:i] autorelease]]; 218 labels = [dims copyWithZone:[self zone]]; 219 } 220 return labels; 221} 222- (unsigned)dimension 223{ return dimension; } 224- (unsigned)lowerBoundForAxis:(id)axis 225{ return 0; } 226- (unsigned)lowerBoundForDimension:(unsigned)dim 227{ return 0; } 228- (unsigned)upperBoundForAxis:(id)axis 229{ 230 if (([axis isKindOfClass:[NSNumber class]]) && 231 ([axis intValue] < dimension) && ([axis intValue] >= 0)) 232 return upperBounds[[axis intValue]]; 233 return 0; 234} 235- (unsigned)upperBoundForDimension:(unsigned)dim 236{ if (dim < dimension) return upperBounds[dim]; else return 0; } 237 238- (unsigned)hashBound 239{ 240 unsigned i; 241 unsigned ret = 1; 242 for (i = 0; i < dimension; i++) 243 ret *= upperBounds[i]; 244 return ret; 245} 246 247- (id)copyWithZone:(NSZone *)zone 248{ 249 return [[KTCuboidHash allocWithZone:zone] 250 initWithDimension:dimension 251 data:upperBounds]; 252} 253 254- (void)dealloc 255{ 256 [labels release]; 257 NSZoneFree([self zone], (void *)upperBounds); 258}/* 259 260- (void)encodeWithCoder:coder 261{ 262 [coder encodeInt:dimension forKey:@"dimension"]; 263 [coder encodeBytes:(void *)(upperBounds) length:dimension*sizeof(unsigned) forKey:@"upperBounds"]; 264 [coder encodeObject:labels forKey:@"labels"]; 265} 266 267- initWithCoder:coder 268{ 269 [super init]; 270 dimension = (unsigned)[coder decodeIntForKey:@"dimension"]; 271 unsigned * bounds = (unsigned *)[coder decodeBytesForKey:@"upperBounds" returnedLength:NULL]; 272 upperBounds = malloc(sizeof(unsigned)*dimension); 273 memcpy((unsigned *)upperBounds, bounds, sizeof(unsigned)*dimension); 274 labels = [[coder decodeObjectForKey:@"labels"] retain]; 275 return self; 276}*/ 277 278@end 279