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