1//
2//  KTMatrixDenseImp
3//  KTMatrix collection class cluster
4//
5//  KTMatrix class cluster mutable implementation subclass
6//  Constant-time access to a mass-allocated chunk of memory
7//  Ideal for mostly-populated matrices
8//  Pointer arithmetic accounts for the speed
9//
10//  Copyright (c) 2002 Chris Purcell. All rights reserved.
11//
12//  You may use this code for whatever purposes you wish.
13//  This code comes with no warranties, implied or otherwise.
14//  Using it may damage your data. It shouldn't, but save a copy first.
15//  That's a good idea anyway, actually.
16//
17
18#import "KTMutableMatrixDenseImp.h"
19#import "KTMatrixDenseEnumerator.h"
20
21@implementation KTMutableMatrixDenseImp
22
23+ (id)matrixWithMatrix:(KTMatrix *)other
24{ return [[[self alloc] initWithMatrix:other] autorelease]; }
25+ (id)matrixWithLocationHash:(id<KTLocationHash>)locationHash
26                     objects:(NSArray *)objects
27                 atLocations:(NSArray *)loc1s
28                 byLocations:(NSArray *)loc2s
29{
30    return [[[self alloc] initWithLocationHash:locationHash
31                                       objects:objects
32                                   atLocations:loc1s
33                                   byLocations:loc2s] autorelease];
34}
35+ (id)matrixWithCapacity:(unsigned)numItems
36            locationHash:(id<KTLocationHash>)_hs
37{
38    return [[[self alloc] initWithCapacity:numItems
39                              locationHash:_hs] autorelease];
40}
41- (id)initWithMatrix:(KTMatrix *)other
42{
43    if ((self = [super init]))
44        {
45        NSEnumerator<KTMatrixEnumerator> *j = [other objectEnumeratorRetained];
46
47        // Deal with the hashing object
48        if (NSShouldRetainWithZone([other locationHash], [self zone]))
49            hash = [[other locationHash] retain];
50        else
51            hash = [[other locationHash] copyWithZone:[self zone]];
52        hashIsCoordinateOptimized = [hash conformsToProtocol:
53            @protocol(KTLocationHashCoordinatesOptimization)];
54
55        // Allocate memory for the storage array
56        count    = 0;
57        capacity = [hash hashBound];
58        array    = NSZoneCalloc([self zone],
59                                capacity,
60                                sizeof(unsigned));
61
62        // Fill the array
63        if ([j conformsToProtocol:@protocol(KTMatrixEnumerator)])
64            {
65            id object;
66            while ((object = [j nextObject]))
67                {
68                array[[j hashedLocation]] = [object retain];
69                count++;
70                }
71            }
72        else
73            {
74            NSNumber *key;
75            NSDictionary *matrixData = [other matrixData];
76            NSEnumerator *k = [matrixData keyEnumerator];
77
78            while ((key = [k nextObject]))
79                {
80                array[[key intValue]] = [[matrixData objectForKey:key] retain];
81                count++;
82                }
83            }
84        [j release];
85        }
86    return self;
87}
88- (id)initWithMatrixData:(NSDictionary *)matrixData
89            locationHash:(id<KTLocationHash>)locationHash
90{
91    if ((self = [super init]))
92        {
93        NSNumber *key;
94        NSEnumerator *k = [matrixData keyEnumerator];
95
96        // Deal with the hashing object
97        if (NSShouldRetainWithZone(locationHash, [self zone]))
98            hash = [locationHash retain];
99        else
100            hash = [locationHash copyWithZone:[self zone]];
101        hashIsCoordinateOptimized = [hash conformsToProtocol:
102            @protocol(KTLocationHashCoordinatesOptimization)];
103
104        // Allocate memory for the storage array
105        count    = 0;
106        capacity = [hash hashBound];
107        array    = NSZoneCalloc([self zone],
108                                capacity,
109                                sizeof(unsigned));
110
111        // Fill the array
112        while ((key = [k nextObject]))
113            {
114            array[[key intValue]] = [[matrixData objectForKey:key] retain];
115            count++;
116            }
117        }
118    return self;
119}
120- (id)initWithLocationHash:(id<KTLocationHash>)locationHash
121{
122    if ((self = [super init]))
123        {
124        // Deal with the hashing object
125        if (NSShouldRetainWithZone(locationHash, [self zone]))
126            hash = [locationHash retain];
127        else
128            hash = [locationHash copyWithZone:[self zone]];
129        hashIsCoordinateOptimized = [hash conformsToProtocol:
130            @protocol(KTLocationHashCoordinatesOptimization)];
131
132        // Allocate memory for the storage array
133        count    = 0;
134        capacity = [hash hashBound];
135        array    = NSZoneCalloc([self zone],
136                                capacity,
137                                sizeof(unsigned));
138        }
139    return self;
140}
141- (id)initWithLocationHash:(id<KTLocationHash>)locationHash
142                   objects:(NSArray *)objects
143               atLocations:(NSArray *)loc1s
144               byLocations:(NSArray *)loc2s
145{
146    if ((self = [super init]))
147        {
148        unsigned i;
149        id *position;
150
151        // Deal with the hashing object
152        if (NSShouldRetainWithZone(locationHash, [self zone]))
153            hash = [locationHash retain];
154        else
155            hash = [locationHash copyWithZone:[self zone]];
156        hashIsCoordinateOptimized = [hash conformsToProtocol:
157            @protocol(KTLocationHashCoordinatesOptimization)];
158
159        // Check the parameters are sane
160        if ([objects count] != [loc1s count])
161            [NSException raise:NSInvalidArgumentException
162                        format:
163                @"Objects and locations arrays not of equal length"];
164        if ([loc1s count] != [loc2s count])
165            [NSException raise:NSInvalidArgumentException
166                        format:
167                @"Locations arrays not of equal length"];
168
169        // Allocate memory for the storage array
170        count    = 0;
171        capacity = [hash hashBound];
172        array    = NSZoneCalloc([self zone],
173                                capacity,
174                                sizeof(unsigned));
175
176        // Fill the storage array
177        for (i = 0; i < [loc1s count]; i++)
178            {
179            position = &array[[hash
180                    hashForLocation:[loc1s objectAtIndex:i]
181                         byLocation:[loc2s objectAtIndex:i]]];
182            if (*position != NULL)
183                [*position release];
184            else
185                count++;
186            *position = [[objects objectAtIndex:i] retain];
187            }
188        }
189    return self;
190}
191- (id)initWithCapacity:(unsigned)numItems
192          locationHash:(id<KTLocationHash>)locationHash
193{
194    if ((self = [super init]))
195        {
196        // Deal with the hashing object
197        if (NSShouldRetainWithZone(locationHash, [self zone]))
198            hash = [locationHash retain];
199        else
200            hash = [locationHash copyWithZone:[self zone]];
201        hashIsCoordinateOptimized = [hash conformsToProtocol:
202            @protocol(KTLocationHashCoordinatesOptimization)];
203
204        // Allocate memory for the storage array
205        count    = 0;
206        capacity = [hash hashBound];
207        array    = NSZoneCalloc([self zone],
208                                capacity,
209                                sizeof(unsigned));
210        }
211    return self;
212}
213
214//// Optimized versions
215- (id)initWithLocationHash:(id<KTLocationHash>)locationHash
216                    object:(id)object
217          atHashedLocation:(unsigned)loc
218{
219    if ((self = [super init]))
220        {   // Deal with the hashing object
221        if (NSShouldRetainWithZone(locationHash, [self zone]))
222            hash = [locationHash retain];
223        else
224            hash = [locationHash copyWithZone:[self zone]];
225        hashIsCoordinateOptimized = [hash
226            conformsToProtocol:@protocol(KTLocationHashCoordinatesOptimization)];
227
228        // Allocate memory for the storage array
229        count    = 1;
230        capacity = [hash hashBound];
231        array    = NSZoneCalloc([self zone],
232                                capacity,
233                                sizeof(unsigned));
234
235        // Fill the storage array
236        array[loc] = [object retain];
237        }
238    return self;
239}
240
241
242// Accessor methods
243- (id)objectAtLocation:(NSDictionary *)loc
244            byLocation:(NSDictionary *)loc2;
245{ return array[[hash hashForLocation:loc byLocation:loc2]]; }
246
247    //// Optimized algorithms
248- (id)objectAtCoordinates:(unsigned)x,...
249{
250    va_list args;
251
252    va_start(args, x);
253
254    if (hashIsCoordinateOptimized)
255        {
256        id ret = array[[(id)hash hashForCoordinatesList:x :&args]];
257        va_end(args);
258        return ret;
259        }
260    else
261        {
262        NSMutableArray *_array
263        = [NSMutableArray arrayWithObject:[NSNumber numberWithInt:x]];
264        unsigned axes = [self dimension];
265
266        while ([_array count] < axes)
267            [_array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]];
268
269        va_end(args);
270
271        return [self objectAtCoordinateArray:_array];
272        }
273}
274- (unsigned)dimension
275{
276    if (hashIsCoordinateOptimized) return [(id)hash dimension];
277    else return [[self axes] count];
278}
279- (unsigned)lowerBoundForDimension:(unsigned)dim
280{
281    if (hashIsCoordinateOptimized) return [(id)hash lowerBoundForDimension:dim];
282    else return [self lowerBoundForAxis: [[self axes] objectAtIndex:dim]];
283}
284- (unsigned)upperBoundForDimension:(unsigned)dim
285{
286    if (hashIsCoordinateOptimized) return [(id)hash upperBoundForDimension:dim];
287    else return [self upperBoundForAxis: [[self axes] objectAtIndex:dim]];
288}
289
290- (id<KTLocationHash>)locationHash
291{ return hash; }
292- (NSDictionary *)matrixData
293{
294    NSMutableDictionary *data = [NSMutableDictionary
295            dictionaryWithCapacity:count];
296    unsigned i;
297
298    for (i = 0; i < capacity; i++)
299        if (array[i])
300            [data setObject:array[i]
301                     forKey:[NSNumber numberWithInt:i]];
302    return data;
303}
304
305- (NSEnumerator *)objectEnumerator
306{
307    return [[[KTMatrixDenseEnumerator allocWithZone:[self zone]]
308        initWithArray:array
309           ofCapacity:capacity
310           collection:self] autorelease];
311}
312- (NSEnumerator *)objectEnumeratorRetained
313{
314    return [[KTMatrixDenseEnumerator allocWithZone:[self zone]]
315        initWithArray:array
316           ofCapacity:capacity
317           collection:self];
318}
319- (unsigned)count
320{ return count; }
321
322
323    //// Mutator methods
324- (void)setMatrix:(KTMatrix *)other
325{
326    NSEnumerator<KTMatrixEnumerator> *j = [other objectEnumerator];
327
328    [hash release];
329    NSZoneFree([self zone], array);
330
331    // Deal with the hashing object
332    if (NSShouldRetainWithZone([other locationHash], [self zone]))
333        hash = [[other locationHash] retain];
334    else
335        hash = [[other locationHash] copyWithZone:[self zone]];
336    hashIsCoordinateOptimized = [hash conformsToProtocol:
337        @protocol(KTLocationHashCoordinatesOptimization)];
338
339    // Allocate memory for the storage array
340    count    = 0;
341    capacity = [hash hashBound];
342    array    = NSZoneCalloc([self zone],
343                            capacity,
344                            sizeof(unsigned));
345
346    // Fill the array
347    if ([j conformsToProtocol:@protocol(KTMatrixEnumerator)])
348        {
349        id object;
350        while ((object = [j nextObject]))
351            {
352            array[[j hashedLocation]] = [object retain];
353            count++;
354            }
355        }
356    else
357        {
358        NSNumber *key;
359        NSDictionary *matrixData = [other matrixData];
360        NSEnumerator *k = [matrixData keyEnumerator];
361
362        while ((key = [k nextObject]))
363            {
364            array[[key intValue]] = [[matrixData objectForKey:key] retain];
365            count++;
366            }
367        }
368}
369- (void)setObject:(id)object
370       atLocation:(NSDictionary *)loc1
371       byLocation:(NSDictionary *)loc2
372{
373    id *position = &array[[hash
374                    hashForLocation:loc1
375                         byLocation:loc2]];
376    if (*position != NULL)
377        [*position release];
378    else
379        count++;
380    *position = [object retain];
381}
382- (void)   setObject:(id)object
383    atHashedLocation:(unsigned)loc
384{
385    if (array[loc] != NULL)
386        [array[loc] release];
387    else
388        count++;
389    array[loc] = [object retain];
390}
391- (void)removeObjectAtLocation:(NSDictionary *)loc1
392                    byLocation:(NSDictionary *)loc2;
393{
394    id *position = &array[[hash
395                    hashForLocation:loc1
396                         byLocation:loc2]];
397    if (*position != NULL)
398        {
399        [*position release];
400        *position = NULL;
401        count--;
402        }
403}
404- (void)removeAllObjects
405{
406    unsigned i;
407
408    for (i = 0; i < capacity; i++)
409        {
410        if (array[i])
411            {
412            [array[i] release];
413            array[i] = NULL;
414            }
415        }
416    count = 0;
417}
418
419//// Optimized versions
420- (void)    setObject:(id)object
421        atCoordinates:(unsigned)x,...
422{
423    va_list args;
424
425    va_start(args, x);
426
427    if (hashIsCoordinateOptimized)
428        {
429        id *position = &array[[(id)hash hashForCoordinatesList:x :&args]];
430        if (*position != NULL)
431            [*position release];
432        else
433            count++;
434        *position = [object retain];
435        }
436    else
437        {
438        NSMutableArray *_array = [NSMutableArray arrayWithObject:
439            [NSNumber numberWithInt:x]];
440        unsigned axes = [self dimension];
441
442        while ([_array count] < axes)
443            [_array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]];
444
445        va_end(args);
446        [self setObject:object
447      atCoordinateArray:_array];
448        return;
449        }
450}
451- (void)setObjectsAtCoordinates:(id)object1,...
452{
453    id object = object1;
454    va_list args;
455
456    if (object1 != 0)
457        {
458        va_start(args, object1);
459
460        if (hashIsCoordinateOptimized)
461            {
462            // SELs/IMPs to speed up repeated method calls
463            SEL hashListSEL = @selector(hashForCoordinatesList:);
464            SEL setObjSEL = @selector(setObject:atHashedLocation:);
465            unsigned (*hashListIMP)(id, SEL, ...);
466            void (*setObjIMP)(id, SEL, ...);
467
468            hashListIMP = (unsigned (*)(id, SEL, ...))
469                [(id)hash methodForSelector:hashListSEL];
470            setObjIMP = (void (*)(id, SEL, ...))
471                [self methodForSelector:setObjSEL];
472            do
473                {
474                    setObjIMP(self, setObjSEL, object,
475                              hashListIMP(hash,hashListSEL,&args));
476                }
477            while (object = va_arg(args, id));
478            }
479        else
480            {
481            NSMutableArray *objects = [NSMutableArray array];
482            NSMutableArray *coords  = [NSMutableArray array];
483            unsigned dimension = [self dimension];
484
485            do
486                {
487                    NSMutableArray *coord = [NSMutableArray arrayWithCapacity:
488                        dimension];
489                    [objects addObject:object];
490                    while ([coord count] < dimension)
491                        [coord addObject:[NSNumber numberWithInt:
492                            va_arg(args, unsigned)]];
493                    [coords addObject:coord];
494                }
495            while (object = va_arg(args, id));
496
497            [self       setObjects:objects
498                atCoordinateArrays:coords];
499            }
500        }
501
502    va_end(args);
503}
504- (void)removeObjectAtCoordinates:(unsigned)x,...
505{
506    va_list args;
507
508    va_start(args, x);
509
510    if (hashIsCoordinateOptimized)
511        {
512        id *position = &array[[(id)hash hashForCoordinatesList:x :&args]];
513        if (*position != NULL)
514            {
515            [*position release];
516            *position = NULL;
517            count--;
518            }
519        }
520    else
521        {
522        NSMutableArray *_array = [NSMutableArray arrayWithObject:
523            [NSNumber numberWithInt:x]];
524        unsigned axes = [self dimension];
525
526        while ([_array count] < axes)
527            [_array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]];
528        [self removeObjectAtCoordinateArray:_array];
529        }
530
531    va_end(args);
532}
533
534- (void)dealloc
535{
536    unsigned i;
537
538    for (i = 0; i < capacity; i++)
539        if (array[i])
540            [array[i] release];
541    [hash release];
542    NSZoneFree([self zone], array);
543    [super dealloc];
544}
545
546@end
547