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