1//
2//  KTMutableMatrixSparseImp
3//  KTMatrix collection class cluster
4//
5//  KTMatrix class cluster mutable implementation subclass
6//  Uses hash tables to reference on-the-fly allocated memory
7//  Ideal for sparsely-populated matrices
8//  Sacrifices some speed for a considerable potential memory saving
9//  Sacrifices some of those memory savings for mutability
10//  Same object retrieval time as any hash table-based storage
11//
12//  Copyright (c) 2002 Chris Purcell. All rights reserved.
13//
14//  You may use this code for whatever purposes you wish.
15//  This code comes with no warranties, implied or otherwise.
16//  Using it may damage your data. It shouldn't, but save a copy first.
17//  That's a good idea anyway, actually.
18//
19
20#import "KTMutableMatrixSparseImp.h"
21#import "KTMatrixSparseEnumerator.h"
22
23static unsigned KTCallback_hash(NSHashTable *table,
24                         const void *elem)
25{ return ((const struct KTMatrixSparseElement *)elem)->hashedLocation; }
26static BOOL KTCallback_isEqual(NSHashTable *table, const void *_1,
27                               const void *_2)
28{
29    return (((const struct KTMatrixSparseElement *)_1)->hashedLocation ==
30            ((const struct KTMatrixSparseElement *)_2)->hashedLocation);
31}
32static void KTCallback_retain(NSHashTable *table, const void *elem)
33{ [(((const struct KTMatrixSparseElement *)elem)->object) retain]; }
34static void KTCallback_release(NSHashTable *table, void *elem)
35{
36    [(((const struct KTMatrixSparseElement *)elem)->object) release];
37    free(elem);
38}
39static NSString *KTCallback_describe(NSHashTable *table, const void *elem)
40{ return [(((const struct KTMatrixSparseElement *)elem)->object) description];}
41
42
43
44@implementation KTMutableMatrixSparseImp
45
46+ (id)matrixWithMatrix:(KTMatrix *)other
47{
48    return [[[self alloc] initWithMatrix:other] autorelease];
49}
50+ (id)matrixWithLocationHash:(id<KTLocationHash>)locationHash
51                     objects:(NSArray *)objects
52                 atLocations:(NSArray *)loc1s
53                 byLocations:(NSArray *)loc2s
54{
55    return [[[self alloc] initWithLocationHash:locationHash
56                                       objects:objects
57                                   atLocations:loc1s
58                                   byLocations:loc2s] autorelease];
59}
60+ (id)matrixWithCapacity:(unsigned)numItems
61            locationHash:(id<KTLocationHash>)_hs
62{
63    return [[[self alloc] initWithCapacity:numItems
64                              locationHash:_hs] autorelease];
65}
66- (id)initWithMatrix:(KTMatrix *)other
67{
68    NSEnumerator<KTMatrixEnumerator> *j = [other objectEnumeratorRetained];
69    if ([j conformsToProtocol:@protocol(KTMatrixEnumerator)])
70        {
71        if ((self = [super init]))
72            {
73            struct KTMatrixSparseElement *element;
74            NSHashTableCallBacks callback;
75            id object;
76
77            callback.hash = KTCallback_hash;
78            callback.isEqual = KTCallback_isEqual;
79            callback.retain = KTCallback_retain;
80            callback.release = KTCallback_release;
81            callback.describe = KTCallback_describe;
82
83            // Deal with the hashing object
84            if (NSShouldRetainWithZone([other locationHash], [self zone]))
85                hash = [[other locationHash] retain];
86            else
87                hash = [[other locationHash] copyWithZone:[self zone]];
88            hashIsCoordinateOptimized = [hash conformsToProtocol:
89                @protocol(KTLocationHashCoordinatesOptimization)];
90
91            // Allocate memory for the hashing table and cache
92            matrix = NSCreateHashTableWithZone(callback,
93                                               [other count],
94                                               [self zone]);
95            cache = NSZoneMalloc([self zone],
96                                 sizeof(struct KTMatrixSparseElement));
97
98            // Fill the hashing table
99            while ((object = [j nextObject]))
100                {
101                element = NSZoneMalloc([self zone],
102                                       sizeof(struct KTMatrixSparseElement));
103                element->hashedLocation = [j hashedLocation];
104                element->object = object;
105                NSHashInsert(matrix, element);
106                }
107            }
108        }
109    else
110        {
111        self = [self initWithMatrixData:[other matrixData]
112                           locationHash:[other locationHash]];
113        }
114    [j release];
115    return self;
116}
117- (id)initWithMatrixData:(NSDictionary *)matrixData
118            locationHash:(id<KTLocationHash>)locationHash
119{ // Same method: setMatrix
120    if ((self = [super init]))
121        {
122        struct KTMatrixSparseElement *element;
123        NSHashTableCallBacks callback;
124        NSNumber *key;
125        NSEnumerator *j = [matrixData keyEnumerator];
126
127        callback.hash = KTCallback_hash;
128        callback.isEqual = KTCallback_isEqual;
129        callback.retain = KTCallback_retain;
130        callback.release = KTCallback_release;
131        callback.describe = KTCallback_describe;
132
133        // Deal with the hashing object
134        if (NSShouldRetainWithZone(locationHash, [self zone]))
135            hash = [locationHash retain];
136        else
137            hash = [locationHash copyWithZone:[self zone]];
138        hashIsCoordinateOptimized = [hash conformsToProtocol:
139            @protocol(KTLocationHashCoordinatesOptimization)];
140
141        // Allocate memory for the hashing table and cache
142        matrix = NSCreateHashTableWithZone(callback,
143                                           [matrixData count],
144                                           [self zone]);
145        cache = NSZoneMalloc([self zone],
146                             sizeof(struct KTMatrixSparseElement));
147
148        // Fill the hashing table
149        while ((key = [j nextObject]))
150            {
151            element = NSZoneMalloc([self zone],
152                                   sizeof(struct KTMatrixSparseElement));
153            element->hashedLocation = [key intValue];
154            element->object = [matrixData objectForKey:key];
155            NSHashInsert(matrix, element);
156            }
157        }
158    return self;
159}
160- (id)initWithLocationHash:(id<KTLocationHash>)locationHash
161{
162    if ((self = [super init]))
163        {
164        NSHashTableCallBacks callback;
165
166        callback.hash = KTCallback_hash;
167        callback.isEqual = KTCallback_isEqual;
168        callback.retain = KTCallback_retain;
169        callback.release = KTCallback_release;
170        callback.describe = KTCallback_describe;
171
172        // Deal with the hashing object
173        if (NSShouldRetainWithZone(locationHash, [self zone]))
174            hash = [locationHash retain];
175        else
176            hash = [locationHash copyWithZone:[self zone]];
177        hashIsCoordinateOptimized = [hash conformsToProtocol:
178            @protocol(KTLocationHashCoordinatesOptimization)];
179
180        // Allocate memory for the hashing table and cache
181        matrix = NSCreateHashTableWithZone(callback,
182                                           0,
183                                           [self zone]);
184        cache = NSZoneMalloc([self zone],
185                             sizeof(struct KTMatrixSparseElement));
186        }
187    return self;
188}
189- (id)initWithLocationHash:(id<KTLocationHash>)locationHash
190                   objects:(NSArray *)objects
191               atLocations:(NSArray *)loc1s
192               byLocations:(NSArray *)loc2s
193{
194    if ((self = [super init]))
195        {
196        struct KTMatrixSparseElement *element;
197        NSHashTableCallBacks callback;
198        unsigned i;
199
200        callback.hash = KTCallback_hash;
201        callback.isEqual = KTCallback_isEqual;
202        callback.retain = KTCallback_retain;
203        callback.release = KTCallback_release;
204        callback.describe = KTCallback_describe;
205
206        // Deal with the hashing object
207        if (NSShouldRetainWithZone(locationHash, [self zone]))
208            hash = [locationHash retain];
209        else
210            hash = [locationHash copyWithZone:[self zone]];
211        hashIsCoordinateOptimized = [hash conformsToProtocol:
212            @protocol(KTLocationHashCoordinatesOptimization)];
213
214        // Check the parameters are sane
215        if ([objects count] != [loc1s count])
216            [NSException raise:NSInvalidArgumentException
217                        format:
218                @"Objects and locations arrays not of equal length"];
219        if ([loc1s count] != [loc2s count])
220            [NSException raise:NSInvalidArgumentException
221                        format:
222                @"Locations arrays not of equal length"];
223
224        // Allocate memory for the hashing table and cache
225        matrix = NSCreateHashTableWithZone(callback,
226                                           [objects count],
227                                           [self zone]);
228        cache = NSZoneMalloc([self zone],
229                             sizeof(struct KTMatrixSparseElement));
230
231        // Fill the cache and the hashing table
232        for (i = 0; i < [loc1s count]; i++)
233            {
234            element = NSZoneMalloc([self zone],
235                                   sizeof(struct KTMatrixSparseElement));
236            element->hashedLocation = [hash
237                    hashForLocation:[loc1s objectAtIndex:i]
238                         byLocation:[loc2s objectAtIndex:i]];
239            element->object = [objects objectAtIndex:i];
240            NSHashInsert(matrix, element);
241            }
242        }
243    return self;
244}
245- (id)initWithCapacity:(unsigned)numItems
246          locationHash:(id<KTLocationHash>)locationHash
247{
248    if ((self = [super init]))
249        {
250        NSHashTableCallBacks callback;
251
252        callback.hash = KTCallback_hash;
253        callback.isEqual = KTCallback_isEqual;
254        callback.retain = KTCallback_retain;
255        callback.release = KTCallback_release;
256        callback.describe = KTCallback_describe;
257
258        // Deal with the hashing object
259        if (NSShouldRetainWithZone(locationHash, [self zone]))
260            hash = [locationHash retain];
261        else
262            hash = [locationHash copyWithZone:[self zone]];
263        hashIsCoordinateOptimized = [hash conformsToProtocol:
264            @protocol(KTLocationHashCoordinatesOptimization)];
265
266        // Allocate memory for the hashing table and cache
267        matrix = NSCreateHashTableWithZone(callback,
268                                           numItems,
269                                           [self zone]);
270        cache = NSZoneMalloc([self zone],
271                             sizeof(struct KTMatrixSparseElement));
272        }
273    return self;
274}
275
276//// Optimized versions
277- (id)initWithLocationHash:(id<KTLocationHash>)locationHash
278                    object:(id)object
279          atHashedLocation:(unsigned)loc
280{
281    if ((self = [super init]))
282        {
283        struct KTMatrixSparseElement *element;
284        NSHashTableCallBacks callback;
285
286        callback.hash = KTCallback_hash;
287        callback.isEqual = KTCallback_isEqual;
288        callback.retain = KTCallback_retain;
289        callback.release = KTCallback_release;
290        callback.describe = KTCallback_describe;
291
292        // Deal with the hashing object
293        if (NSShouldRetainWithZone(locationHash, [self zone]))
294            hash = [locationHash retain];
295        else
296            hash = [locationHash copyWithZone:[self zone]];
297        hashIsCoordinateOptimized = [hash
298            conformsToProtocol:@protocol(KTLocationHashCoordinatesOptimization)];
299
300        // Allocate memory for the hashing table and cache
301        matrix = NSCreateHashTableWithZone(callback,
302                                           1,
303                                           [self zone]);
304        cache = NSZoneMalloc([self zone],
305                             sizeof(struct KTMatrixSparseElement));
306
307        // Fill the cache and the hashing table
308        element = NSZoneMalloc([self zone],
309                               sizeof(struct KTMatrixSparseElement));
310        element->hashedLocation = loc;
311        element->object = object;
312        NSHashInsert(matrix, element);
313        }
314    return self;
315}
316
317
318// Accessor methods
319- (id)objectAtLocation:(NSDictionary *)loc
320            byLocation:(NSDictionary *)loc2;
321{
322    struct KTMatrixSparseElement *elem;
323    ((struct KTMatrixSparseElement *)cache)->hashedLocation = [hash
324            hashForLocation:loc byLocation:loc2];
325    elem = (struct KTMatrixSparseElement *)NSHashGet(matrix, cache);
326    if (elem != NULL)
327        return (elem)->object;
328    else
329        return NULL;
330}
331
332//// Optimized algoritms
333- (id)objectAtCoordinates:(unsigned)x,...
334{
335    va_list args;
336
337    va_start(args, x);
338
339    if (hashIsCoordinateOptimized)
340        {
341        struct KTMatrixSparseElement *elem;
342        ((struct KTMatrixSparseElement *)cache)->hashedLocation =
343            [(id)hash hashForCoordinatesList:x :&args];
344        va_end(args);
345
346        elem = (struct KTMatrixSparseElement *)NSHashGet(matrix, cache);
347        if (elem != NULL)
348            return (elem)->object;
349        else
350            return NULL;
351        }
352    else
353        {
354        NSMutableArray *array
355        = [NSMutableArray arrayWithObject:[NSNumber numberWithInt:x]];
356        unsigned axes = [self dimension];
357
358        while ([array count] < axes)
359            [array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]];
360
361        va_end(args);
362
363        return [self objectAtCoordinateArray:array];
364        }
365}
366- (unsigned)dimension
367{
368    if (hashIsCoordinateOptimized) return [(id)hash dimension];
369    else return [[self axes] count];
370}
371- (unsigned)lowerBoundForDimension:(unsigned)dim
372{
373    if (hashIsCoordinateOptimized) return [(id)hash lowerBoundForDimension:dim];
374    else return [self lowerBoundForAxis: [[self axes] objectAtIndex:dim]];
375}
376- (unsigned)upperBoundForDimension:(unsigned)dim
377{
378    if (hashIsCoordinateOptimized) return [(id)hash upperBoundForDimension:dim];
379    else return [self upperBoundForAxis: [[self axes] objectAtIndex:dim]];
380}
381
382- (id<KTLocationHash>)locationHash
383{ return hash; }
384- (NSDictionary *)matrixData
385{
386    NSMutableDictionary *data = [NSMutableDictionary
387            dictionaryWithCapacity:[self count]];
388    NSHashEnumerator i = NSEnumerateHashTable(matrix);
389    struct KTMatrixSparseElement *elem;
390    while ((elem =
391            (struct KTMatrixSparseElement *)NSNextHashEnumeratorItem(&i)))
392        [data setObject:elem->object
393                 forKey:[NSNumber numberWithInt:elem->hashedLocation]];
394    NSEndHashTableEnumeration(&i);
395
396    return data;
397}
398
399- (NSEnumerator *)objectEnumerator
400{
401    return [[[KTMutableMatrixSparseEnumerator allocWithZone:[self zone]]
402            initWithHashEnumerator:NSEnumerateHashTable(matrix)
403                        collection:self] autorelease];
404}
405- (NSEnumerator *)objectEnumeratorRetained
406{
407    return [[KTMutableMatrixSparseEnumerator allocWithZone:[self zone]]
408            initWithHashEnumerator:NSEnumerateHashTable(matrix)
409                        collection:self];
410}
411- (unsigned)count
412{ return NSCountHashTable(matrix); }
413
414
415    //// Mutator methods
416- (void)setMatrix:(KTMatrix *)other
417{
418    struct KTMatrixSparseElement *element;
419    NSEnumerator<KTMatrixEnumerator> *j = [other objectEnumerator];
420    NSHashTableCallBacks callback;
421
422    [hash release];
423    NSFreeHashTable(matrix);
424
425    callback.hash = KTCallback_hash;
426    callback.isEqual = KTCallback_isEqual;
427    callback.retain = KTCallback_retain;
428    callback.release = KTCallback_release;
429    callback.describe = KTCallback_describe;
430
431    // Deal with the hashing object
432    if (NSShouldRetainWithZone([other locationHash], [self zone]))
433        hash = [[other locationHash] retain];
434    else
435        hash = [[other locationHash] copyWithZone:[self zone]];
436    hashIsCoordinateOptimized =
437        [hash conformsToProtocol:@protocol(KTLocationHashCoordinatesOptimization)];
438
439    // Allocate memory for the hashing table
440    matrix = NSCreateHashTableWithZone(callback,
441                                       [other count],
442                                       [self zone]);
443
444    // Fill the hashing table
445    if ([j conformsToProtocol:@protocol(KTMatrixEnumerator)])
446        {
447        id object;
448        while ((object = [j nextObject]))
449            {
450            element = NSZoneMalloc([self zone],
451                                   sizeof(struct KTMatrixSparseElement));
452            element->hashedLocation = [j hashedLocation];
453            element->object = object;
454            NSHashInsert(matrix, element);
455            }
456        }
457    else
458        {
459        NSDictionary *matrixData = [other matrixData];
460        NSNumber *key;
461        NSEnumerator *k = [matrixData keyEnumerator];
462
463        while ((key = [k nextObject]))
464            {
465            element = NSZoneMalloc([self zone],
466                                   sizeof(struct KTMatrixSparseElement));
467            element->hashedLocation = [key intValue];
468            element->object = [matrixData objectForKey:key];
469            NSHashInsert(matrix, element);
470            }
471        }
472}
473- (void)setObject:(id)object
474       atLocation:(NSDictionary *)loc1
475       byLocation:(NSDictionary *)loc2
476{
477    struct KTMatrixSparseElement *elem;
478    ((struct KTMatrixSparseElement *)cache)->hashedLocation = [hash
479        hashForLocation:loc1 byLocation:loc2];
480    elem = (struct KTMatrixSparseElement *)NSHashGet(matrix, cache);
481    if (elem)
482        {   // Just change object if the location is occupied
483        [elem->object release];
484        elem->object = object;
485        }
486    else
487        {   // Else allocate more memory
488        elem = NSZoneMalloc([self zone],
489                            sizeof(struct KTMatrixSparseElement));
490        elem->hashedLocation =
491            ((struct KTMatrixSparseElement *)cache)->hashedLocation;
492        elem->object = object;
493        NSHashInsertKnownAbsent(matrix, elem);
494        }
495}
496- (void)   setObject:(id)object
497    atHashedLocation:(unsigned)loc
498{
499    struct KTMatrixSparseElement *elem;
500    ((struct KTMatrixSparseElement *)cache)->hashedLocation = loc;
501
502    elem = (struct KTMatrixSparseElement *)NSHashGet(matrix, cache);
503    if (elem)
504        {   // Just change object if the location is occupied
505        [elem->object release];
506        elem->object = object;
507        }
508    else
509        {   // Else allocate more memory
510        elem = NSZoneMalloc([self zone],
511                            sizeof(struct KTMatrixSparseElement));
512        elem->hashedLocation =
513            ((struct KTMatrixSparseElement *)cache)->hashedLocation;
514        elem->object = object;
515        NSHashInsertKnownAbsent(matrix, elem);
516        }
517}
518- (void)removeObjectAtLocation:(NSDictionary *)loc1
519                    byLocation:(NSDictionary *)loc2;
520{
521    ((struct KTMatrixSparseElement *)cache)->hashedLocation = [hash
522            hashForLocation:loc1 byLocation:loc2];
523    NSHashRemove(matrix, cache);
524}
525- (void)removeAllObjects
526{ NSResetHashTable(matrix); }
527
528//// Optimized versions
529- (void)    setObject:(id)object
530        atCoordinates:(unsigned)x,...
531{
532    va_list args;
533
534    va_start(args, x);
535
536    if (hashIsCoordinateOptimized)
537        {
538        struct KTMatrixSparseElement *elem;
539        ((struct KTMatrixSparseElement *)cache)->hashedLocation =
540            [(id)hash hashForCoordinatesList:x :&args];
541
542        elem = (struct KTMatrixSparseElement *)NSHashGet(matrix, cache);
543        if (elem)
544            {   // Just change object if the location is occupied
545            [elem->object release];
546            elem->object = object;
547            }
548        else
549            {   // Else allocate more memory
550            elem = NSZoneMalloc([self zone],
551                                sizeof(struct KTMatrixSparseElement));
552            elem->hashedLocation =
553                ((struct KTMatrixSparseElement *)cache)->hashedLocation;
554            elem->object = object;
555            NSHashInsertKnownAbsent(matrix, elem);
556            }
557        }
558    else
559        {
560        NSMutableArray *array = [NSMutableArray arrayWithObject:
561            [NSNumber numberWithInt:x]];
562        unsigned axes = [self dimension];
563
564        while ([array count] < axes)
565            [array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]];
566
567        va_end(args);
568        [self setObject:object
569      atCoordinateArray:array];
570        return;
571        }
572}
573- (void)setObjectsAtCoordinates:(id)object1,...
574{
575    id object = object1;
576    va_list args;
577
578    if (object1 != 0)
579        {
580        va_start(args, object1);
581
582        if (hashIsCoordinateOptimized)
583            {
584            // SELs/IMPs to speed up repeated method calls
585            SEL hashListSEL = @selector(hashForCoordinatesList:);
586            SEL setObjSEL = @selector(setObject:atHashedLocation:);
587            unsigned (*hashListIMP)(id, SEL, ...);
588            void (*setObjIMP)(id, SEL, ...);
589
590            hashListIMP = (unsigned (*)(id, SEL, ...))
591                [(id)hash methodForSelector:hashListSEL];
592            setObjIMP = (void (*)(id, SEL, ...))
593                [self methodForSelector:setObjSEL];
594            do
595                {
596                    setObjIMP(self, setObjSEL, object,
597                              hashListIMP(hash,hashListSEL,&args));
598                }
599            while (object = va_arg(args, id));
600            }
601        else
602            {
603            NSMutableArray *objects = [NSMutableArray array];
604            NSMutableArray *coords  = [NSMutableArray array];
605            unsigned dimension = [self dimension];
606
607            do
608                {
609                    NSMutableArray *coord = [NSMutableArray arrayWithCapacity:
610                        dimension];
611                    [objects addObject:object];
612                    while ([coord count] < dimension)
613                        [coord addObject:[NSNumber numberWithInt:
614                            va_arg(args, unsigned)]];
615                    [coords addObject:coord];
616                }
617            while (object = va_arg(args, id));
618
619            [self       setObjects:objects
620                atCoordinateArrays:coords];
621            }
622        }
623
624    va_end(args);
625}
626- (void)removeObjectAtCoordinates:(unsigned)x,...
627{
628    va_list args;
629
630    va_start(args, x);
631
632    if (hashIsCoordinateOptimized)
633        {
634        ((struct KTMatrixSparseElement *)cache)->hashedLocation = [(id)hash
635            hashForCoordinatesList:x :&args];
636        NSHashRemove(matrix, cache);
637        }
638    else
639        {
640        NSMutableArray *array = [NSMutableArray arrayWithObject:
641            [NSNumber numberWithInt:x]];
642        unsigned axes = [self dimension];
643
644        while ([array count] < axes)
645            [array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]];
646        [self removeObjectAtCoordinateArray:array];
647        }
648
649    va_end(args);
650}
651
652- (void)dealloc
653{
654    [hash release];
655    NSFreeHashTable(matrix);
656    NSZoneFree([self zone], cache);
657    [super dealloc];
658}
659
660@end
661