1//
2//  KTMatrixDenseImp
3//  KTMatrix collection class cluster
4//
5//  KTMatrix class cluster 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 "KTMatrixDenseImp.h"
19#import "KTMatrixDenseEnumerator.h"
20
21@implementation KTMatrixDenseImp
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)initWithMatrix:(KTMatrix *)other
36{
37    NSEnumerator<KTMatrixEnumerator> *j = [other objectEnumeratorRetained];
38    if ([j conformsToProtocol:@protocol(KTMatrixEnumerator)])
39        {
40        if ((self = [super init]))
41            {
42            id object;
43
44            // Deal with the hashing object
45            if (NSShouldRetainWithZone([other locationHash], [self zone]))
46                hash = [[other locationHash] retain];
47            else
48                hash = [[other locationHash] copyWithZone:[self zone]];
49            hashIsCoordinateOptimized = [hash conformsToProtocol:
50                @protocol(KTLocationHashCoordinatesOptimization)];
51
52            // Allocate memory for the storage array
53            count    = 0;
54            capacity = [hash hashBound];
55            array    = NSZoneCalloc([self zone],
56                                    capacity,
57                                    sizeof(unsigned));
58
59            // Fill the array
60            while ((object = [j nextObject]))
61                {
62                array[[j hashedLocation]] = [object retain];
63                count++;
64                }
65            }
66        }
67    else
68        {
69        self = [self initWithMatrixData:[other matrixData]
70                           locationHash:[other locationHash]];
71        }
72    [j release];
73    return self;
74}
75- (id)initWithMatrixData:(NSDictionary *)matrixData
76            locationHash:(id<KTLocationHash>)locationHash
77{
78    if ((self = [super init]))
79        {
80        NSNumber *key;
81        NSEnumerator *j = [matrixData keyEnumerator];
82
83        // Deal with the hashing object
84        if (NSShouldRetainWithZone(locationHash, [self zone]))
85            hash = [locationHash retain];
86        else
87            hash = [locationHash copyWithZone:[self zone]];
88        hashIsCoordinateOptimized = [hash conformsToProtocol:
89            @protocol(KTLocationHashCoordinatesOptimization)];
90
91        // Allocate memory for the storage array
92        count    = [matrixData count];
93        capacity = [hash hashBound];
94        array    = NSZoneCalloc([self zone],
95                                capacity,
96                                sizeof(unsigned));
97
98        // Fill the array
99        while ((key = [j nextObject]))
100            array[[key intValue]] = [[matrixData objectForKey:key] retain];
101        }
102    return self;
103}
104- (id)initWithLocationHash:(id<KTLocationHash>)locationHash
105                    object:(id)object
106          atHashedLocation:(unsigned)loc
107{
108    if ((self = [super init]))
109        {
110        // Deal with the hashing object
111        if (NSShouldRetainWithZone(locationHash, [self zone]))
112            hash = [locationHash retain];
113        else
114            hash = [locationHash copyWithZone:[self zone]];
115        hashIsCoordinateOptimized = [hash conformsToProtocol:
116            @protocol(KTLocationHashCoordinatesOptimization)];
117
118        // Allocate memory for the storage array
119        count    = 1;
120        capacity = [hash hashBound];
121        array    = NSZoneCalloc([self zone],
122                                capacity,
123                                sizeof(unsigned));
124
125        // Fill the array
126        array[loc] = [object retain];
127        }
128    return self;
129}
130- (id)initWithLocationHash:(id<KTLocationHash>)locationHash
131                   objects:(NSArray *)objects
132               atLocations:(NSArray *)loc1s
133               byLocations:(NSArray *)loc2s
134{
135    if ((self = [super init]))
136        {
137        id *position;
138        unsigned i;
139
140        // Deal with the hashing object
141        if (NSShouldRetainWithZone(locationHash, [self zone]))
142            hash = [locationHash retain];
143        else
144            hash = [locationHash copyWithZone:[self zone]];
145        hashIsCoordinateOptimized = [hash conformsToProtocol:
146            @protocol(KTLocationHashCoordinatesOptimization)];
147
148        // Check the parameters are sane
149        if ([objects count] != [loc1s count])
150            [NSException raise:NSInvalidArgumentException
151                        format:
152                @"Objects and locations arrays not of equal length"];
153        if ([loc1s count] != [loc2s count])
154            [NSException raise:NSInvalidArgumentException
155                        format:
156                @"Locations arrays not of equal length"];
157
158        // Allocate memory for the storage array
159        count    = 0;
160        capacity = [hash hashBound];
161        array    = NSZoneCalloc([self zone],
162                                capacity,
163                                sizeof(unsigned));
164
165        // Fill the array
166        for (i = 0; i < [objects count]; i++)
167            {
168            position = &array[[hash
169                    hashForLocation:[loc1s objectAtIndex:i]
170                         byLocation:[loc2s objectAtIndex:i]]];
171            if (*position != NULL)
172                [*position release];
173            else
174                count++;
175            *position = [[objects objectAtIndex:i] retain];
176            }
177        }
178    return self;
179}
180
181// Accessor methods
182- (id)objectAtLocation:(NSDictionary *)loc
183            byLocation:(NSDictionary *)loc2;
184{ return array[[hash hashForLocation:loc byLocation:loc2]]; }
185
186    //// Optimized algorithms
187- (id)objectAtCoordinates:(unsigned)x,...
188{
189    va_list args;
190
191    va_start(args, x);
192
193    if (hashIsCoordinateOptimized)
194        {
195        id ret = array[[(id)hash hashForCoordinatesList:x :&args]];
196        va_end(args);
197        return ret;
198        }
199    else
200        {
201        NSMutableArray *_array
202        = [NSMutableArray arrayWithObject:[NSNumber numberWithInt:x]];
203        unsigned axes = [self dimension];
204
205        while ([_array count] < axes)
206            [_array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]];
207
208        va_end(args);
209
210        return [self objectAtCoordinateArray:_array];
211        }
212}
213- (unsigned)dimension
214{
215    if (hashIsCoordinateOptimized) return [(id)hash dimension];
216    else return [[self axes] count];
217}
218- (unsigned)lowerBoundForDimension:(unsigned)dim
219{
220    if (hashIsCoordinateOptimized) return [(id)hash lowerBoundForDimension:dim];
221    else return [self lowerBoundForAxis: [[self axes] objectAtIndex:dim]];
222}
223- (unsigned)upperBoundForDimension:(unsigned)dim
224{
225    if (hashIsCoordinateOptimized) return [(id)hash upperBoundForDimension:dim];
226    else return [self upperBoundForAxis: [[self axes] objectAtIndex:dim]];
227}
228
229
230- (id<KTLocationHash>)locationHash
231{ return hash; }
232- (NSDictionary *)matrixData
233{
234    NSMutableDictionary *data = [NSMutableDictionary
235            dictionaryWithCapacity:count];
236    unsigned i;
237
238    for (i = 0; i < capacity; i++)
239        if (array[i])
240            [data setObject:array[i]
241                     forKey:[NSNumber numberWithInt:i]];
242    return data;
243}
244
245- (NSEnumerator *)objectEnumerator
246{
247    return [[[KTMatrixDenseEnumerator allocWithZone:[self zone]]
248        initWithArray:array
249           ofCapacity:capacity
250           collection:self] autorelease];
251}
252- (NSEnumerator *)objectEnumeratorRetained
253{
254    return [[KTMatrixDenseEnumerator allocWithZone:[self zone]]
255        initWithArray:array
256           ofCapacity:capacity
257           collection:self];
258}
259- (unsigned)count
260{ return count; }
261
262- (id)copyWithZone:(NSZone *)zone
263{
264    if (NSShouldRetainWithZone(self, zone))
265        return [self retain];
266    else
267        return [super copyWithZone:zone];
268}
269
270- (void)dealloc
271{
272    unsigned i;
273
274    for (i = 0; i < capacity; i++)
275        if (array[i])
276            [array[i] release];
277    [hash release];
278    NSZoneFree([self zone], array);
279    [super dealloc];
280}
281@end
282