1//
2//  KTMatrix
3//  KTMatrix collection class cluster
4//
5//  Stores a matrix of objects
6//
7//  It works like this:
8//    - A set of keys is used to denote the matrix axes
9//    - A dictionary is used to access individual elements
10//    - (A hash is used to transform this dictionary into a key)
11//    - The axis values must be NSNumbers
12//  This differs from a dictionary with dictionary keys only in that
13//    the hash does not depend on the key type
14//  Also, if two locations hash the same, they are treated as identical
15//
16//  Copyright (c) 2002 Chris Purcell. All rights reserved.
17//
18//  You may use this code for whatever purposes you wish.
19//  This code comes with no warranties, implied or otherwise.
20//  Using it may damage your data. It shouldn't, but save a copy first.
21//  That's a good idea anyway, actually.
22//
23
24#import "KTMatrix.h"
25#import "KTPlaceholderMatrix.h"
26#import "KTMatrixSparseImp.h"
27#import "KTMatrixDenseImp.h"
28#import "KTMutableMatrix.h"
29#import "KTMutableMatrixSparseImp.h"
30#import "KTMutableMatrixDenseImp.h"
31#import "KTCuboidHash.h"
32
33@implementation KTMatrix
34
35//// Allocators
36+ (id)alloc
37{
38    if ([self isEqual:[KTMatrix class]])
39        return [KTPlaceholderMatrix alloc];
40    else
41        return [super alloc];
42}
43+ (id)allocWithZone:(NSZone *)zone
44{
45    if ([self isEqual:[KTMatrix class]])
46        return [KTPlaceholderMatrix allocWithZone:zone];
47    else
48        return [super allocWithZone:zone];
49}
50
51//// Constructors
52+ (id)matrix
53{
54    id<KTLocationHash> hash = [[KTCuboidHash allocWithZone:NULL] init];
55    id ret = [self matrixWithLocationHash:hash];
56    [hash release];
57    return ret;
58}
59+ (id)matrixWithMatrix:(KTMatrix *)matrix
60{
61    if (([[matrix locationHash] hashBound] == 0) ||
62        ([matrix count] < [[matrix locationHash] hashBound]/3))
63        return [KTMatrixSparseImp matrixWithMatrix:matrix];
64    else
65        return [KTMatrixDenseImp matrixWithMatrix:matrix];
66}
67
68+ (id)matrixWithLocationHash:(id<KTLocationHash>)hash
69{
70    if ([self isEqual:[KTMatrix class]])
71        return [KTMatrixSparseImp matrixWithLocationHash:hash];
72    else
73        {
74        [NSException raise:NSGenericException
75                    format:
76            @"Must implement a complete subclass of KTMatrix!"];
77        return NULL;
78        }
79}
80+ (id)matrixWithLocationHash:(id<KTLocationHash>)hash
81                      object:(id)object
82                  atLocation:(NSDictionary *)loc
83{
84    return [self matrixWithLocationHash:(id<KTLocationHash>)hash
85                                objects:[NSArray arrayWithObject:object]
86                            atLocations:[NSArray arrayWithObject:loc]
87                            byLocations:[NSArray arrayWithObject:
88                              [NSDictionary dictionary]]];
89}
90+ (id)matrixWithLocationHash:(id<KTLocationHash>)hash
91                      object:(id)object
92                  atLocation:(NSDictionary *)loc1
93                  byLocation:(NSDictionary *)loc2
94{
95    return [self matrixWithLocationHash:(id<KTLocationHash>)hash
96                                objects:[NSArray arrayWithObject:object]
97                            atLocations:[NSArray arrayWithObject:loc1]
98                            byLocations:[NSArray arrayWithObject:loc2]];
99}
100+ (id)matrixWithLocationHash:(id<KTLocationHash>)hash
101                     objects:(NSArray *)objects
102                 atLocations:(NSArray *)locs
103{
104    NSDictionary *empty = [[NSDictionary alloc] init];
105    NSMutableArray *temp = [[NSMutableArray alloc] initWithCapacity:
106        [locs count]];
107    id ret;
108    unsigned i;
109    for (i = 0; i < [locs count]; i++)
110        [temp addObject:empty];
111    [empty release];
112    ret = [self matrixWithLocationHash:(id<KTLocationHash>)hash
113                               objects:objects
114                           atLocations:locs
115                           byLocations:temp];
116    [temp release];
117    return ret;
118}
119+ (id)matrixWithLocationHash:(id<KTLocationHash>)hash
120                     objects:(NSArray *)objects
121                 atLocations:(NSArray *)loc1s
122                  byLocation:(NSDictionary *)loc2
123{
124    NSMutableArray *temp = [[NSMutableArray alloc] initWithCapacity:
125        [loc1s count]];
126    unsigned i;
127    id ret;
128    for (i = 0; i < [loc1s count]; i++)
129        [temp addObject:loc2];
130    ret = [self matrixWithLocationHash:(id<KTLocationHash>)hash
131                                objects:objects
132                            atLocations:loc1s
133                            byLocations:temp];
134    [temp release];
135    return ret;
136}
137+ (id)matrixWithLocationHash:(id<KTLocationHash>)hash
138                     objects:(NSArray *)objects
139                 atLocations:(NSArray *)loc1s
140                 byLocations:(NSArray *)loc2s
141{
142    if (([hash hashBound] == 0) || ([objects count] < [hash hashBound]/3))
143        return [KTMatrixSparseImp matrixWithLocationHash:hash
144                                                 objects:objects
145                                             atLocations:loc1s
146                                             byLocations:loc2s];
147    else
148        return [KTMatrixDenseImp matrixWithLocationHash:hash
149                                                objects:objects
150                                            atLocations:loc1s
151                                            byLocations:loc2s];
152}
153+ (id)matrixWithLocationHash:(id<KTLocationHash>)hash
154          objectsAtLocations:(id)object1,...
155{
156    NSDictionary *empty     = [NSDictionary dictionary];
157    NSMutableArray *objects = [NSMutableArray array];
158    NSMutableArray *loc1s   = [NSMutableArray array];
159    NSMutableArray *loc2s   = [NSMutableArray array];
160    id object = object1;
161    va_list args;
162
163    if (object1 != 0)
164        {
165        va_start(args, object1);
166
167        do
168            {
169                [objects addObject:object];
170                [loc1s addObject:va_arg(args, id)];
171                [loc2s addObject:empty];
172            }
173        while (object = va_arg(args, id));
174
175        va_end(args);
176        }
177    return [self matrixWithLocationHash:(id<KTLocationHash>)hash
178                                objects:objects
179                            atLocations:loc1s
180                            byLocations:loc2s];
181}
182+ (id)     matrixWithLocationHash:(id<KTLocationHash>)hash
183    objectsAtLocationsByLocations:(id)object1,...
184{
185    NSMutableArray *objects = [NSMutableArray array];
186    NSMutableArray *loc1s   = [NSMutableArray array];
187    NSMutableArray *loc2s   = [NSMutableArray array];
188    id object = object1;
189    va_list args;
190
191    if (object1 != 0)
192        {
193        va_start(args, object1);
194
195        do
196            {
197                [objects addObject:object];
198                [loc1s addObject:va_arg(args, id)];
199                [loc2s addObject:va_arg(args, id)];
200            }
201        while (object = va_arg(args, id));
202
203        va_end(args);
204        }
205    return [self matrixWithLocationHash:(id<KTLocationHash>)hash
206                                objects:objects
207                            atLocations:loc1s
208                            byLocations:loc2s];
209}
210
211+ (id)matrixWithLocationHash:(id<KTLocationHash>)hash
212                      object:(id)object
213           atCoordinateArray:(NSArray *)coord
214{
215    NSMutableDictionary *loc1 = [[NSMutableDictionary alloc] init];
216    NSDictionary *loc2 = [[NSDictionary alloc] init];
217    NSEnumerator *axes = [[hash axes] objectEnumerator];
218    NSEnumerator *coords = [coord objectEnumerator];
219    id axis;
220    id ret;
221
222    if ([[hash axes] count] != [coord count])
223        [NSException raise:NSInvalidArgumentException
224                    format:
225            @"Dimensions of hash do not agree with number of coordinates"];
226    while ((axis = [axes nextObject]))
227        [loc1 setObject:[coords nextObject]
228                 forKey:axis];
229    ret = [self matrixWithLocationHash:hash
230                                object:object
231                            atLocation:loc1
232                            byLocation:loc2];
233    [loc1 release];
234    [loc2 release];
235    return ret;
236}
237+ (id)matrixWithLocationHash:(id<KTLocationHash>)hash
238                      object:(id)object
239               atCoordinates:(unsigned)x,...
240{
241    NSMutableArray *array = [NSMutableArray arrayWithObject:
242        [NSNumber numberWithInt:x]];
243    unsigned axes = [[hash axes] count];
244    va_list args;
245
246    va_start(args, x);
247
248    while ([array count] < axes)
249        [array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]];
250
251    va_end(args);
252
253    return [self matrixWithLocationHash:hash
254                                 object:object
255                      atCoordinateArray:array];
256}
257+ (id)matrixWithLocationHash:(id<KTLocationHash>)hash
258                     objects:(NSArray *)objects
259          atCoordinateArrays:(NSArray *)coords
260{
261    NSArray *dims = [hash axes];
262    NSMutableArray *loc1s = [[NSMutableArray alloc] initWithCapacity:
263        [coords count]];
264    NSMutableArray *loc2s = [[NSMutableArray alloc] initWithCapacity:
265        [coords count]];
266    NSMutableDictionary *loc;
267    NSDictionary *empty = [[NSDictionary alloc] init];
268
269    NSEnumerator *axes;
270    NSEnumerator *coordArrays = [coords objectEnumerator];
271    NSEnumerator *vals;
272    id axis;
273    NSArray *coord;
274    id ret;
275
276    while ((coord = [coordArrays nextObject]))
277        {
278        if ([dims count] != [coord count])
279            [NSException raise:NSInvalidArgumentException
280                        format:
281                @"Dimensions of hash and number of coordinates not equal"];
282        axes = [dims objectEnumerator];
283        vals = [coord objectEnumerator];
284        loc  = [[NSMutableDictionary alloc] init];
285        while ((axis = [axes nextObject]))
286            [loc setObject:[vals nextObject]
287                    forKey:axis];
288        [loc1s addObject:loc];
289        [loc2s addObject:empty];
290        [loc release];
291        }
292    ret = [self matrixWithLocationHash:hash
293                               objects:objects
294                           atLocations:loc1s
295                           byLocations:loc2s];
296    [loc1s release];
297    [loc2s release];
298    [empty release];
299    return ret;
300}
301+ (id)matrixWithLocationHash:(id<KTLocationHash>)hash
302        objectsAtCoordinates:(id)object1,...
303{
304    NSMutableArray *objects = [NSMutableArray array];
305    NSMutableArray *coords  = [NSMutableArray array];
306    unsigned dimension = [[hash axes] count];
307    id object = object1;
308    va_list args;
309
310    if (object1 != 0)
311        {
312        va_start(args, object1);
313
314        do
315            {
316                NSMutableArray *coord = [NSMutableArray arrayWithCapacity:
317                    dimension];
318                [objects addObject:object];
319                while ([coord count] < dimension)
320                    [coord addObject:[NSNumber numberWithInt:
321                        va_arg(args, unsigned)]];
322                [coords addObject:coord];
323            }
324        while (object = va_arg(args, id));
325
326        va_end(args);
327        }
328    return [self matrixWithLocationHash:hash
329                                objects:objects
330                     atCoordinateArrays:coords];
331}
332
333+ (id)matrixWithCuboidBoundArray:(NSArray *)bounds
334{
335    id<KTLocationHash> hash = [[KTCuboidHash allocWithZone:NULL]
336                                    initWithBounds:bounds];
337    id ret = [self matrixWithLocationHash:hash];
338    [hash release];
339    return ret;
340}
341+ (id)matrixWithCuboidBoundArray:(NSArray *)bounds
342                          object:(id)object
343               atCoordinateArray:(NSArray *)coord
344{
345    NSMutableDictionary *loc1 = [NSMutableDictionary dictionaryWithCapacity:
346        [bounds count]];
347    NSMutableDictionary *loc2 = [NSMutableDictionary dictionary];
348    id<KTLocationHash> hash = [[KTCuboidHash allocWithZone:NULL]
349        initWithBounds:bounds];
350    unsigned i;
351    id ret;
352
353    if ([bounds count] != [coord count])
354        [NSException raise:NSInvalidArgumentException
355                    format:
356            @"Dimension of cuboid and dimension of coordinates not equal"];
357    for (i = 0; i < [bounds count]; i++)
358        [loc1 setObject:[coord objectAtIndex:i]
359                 forKey:[NSNumber numberWithInt:i]];
360    ret = [self matrixWithLocationHash:hash
361                                object:object
362                            atLocation:loc1
363                            byLocation:loc2];
364    [hash release];
365    return ret;
366}
367+ (id)matrixWithCuboidBoundArray:(NSArray *)bounds
368                          object:(id)object
369                   atCoordinates:(unsigned)x,...
370{
371    NSMutableArray *array = [NSMutableArray arrayWithObject:
372        [NSNumber numberWithInt:x]];
373    unsigned axes = [bounds count];
374    id<KTLocationHash> hash = [[KTCuboidHash allocWithZone:NULL]
375        initWithBounds:bounds];
376    id ret;
377    va_list args;
378
379    va_start(args, x);
380
381    while ([array count] < axes)
382        [array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]];
383
384    va_end(args);
385
386    ret = [self matrixWithLocationHash:hash
387                                object:object
388                     atCoordinateArray:array];
389    [hash release];
390    return ret;
391}
392+ (id)matrixWithCuboidBoundArray:(NSArray *)bounds
393                         objects:(NSArray *)objects
394              atCoordinateArrays:(NSArray *)coords
395{
396    NSMutableArray *loc1s = [[NSMutableArray alloc] initWithCapacity:
397        [coords count]];
398    NSMutableArray *loc2s = [[NSMutableArray alloc] initWithCapacity:
399        [coords count]];
400    NSMutableDictionary *loc;
401    NSDictionary *empty = [[NSDictionary alloc] init];
402    id<KTLocationHash> hash = [[KTCuboidHash allocWithZone:NULL]
403        initWithBounds:bounds];
404    unsigned i;
405
406    NSEnumerator *coordArrays = [coords objectEnumerator];
407    NSArray *coord;
408    id ret;
409
410    while ((coord = [coordArrays nextObject]))
411        {
412        if ([bounds count] != [coord count])
413            [NSException raise:NSInvalidArgumentException
414                        format:
415                @"Dimensions of cuboid and number of coordinates not equal"];
416        loc  = [[NSMutableDictionary alloc] init];
417        for (i = 0; i < [bounds count]; i++)
418            [loc setObject:[coord objectAtIndex:i]
419                    forKey:[NSNumber numberWithInt:i]];
420        [loc1s addObject:loc];
421        [loc2s addObject:empty];
422        [loc release];
423        }
424
425    ret = [self matrixWithLocationHash:hash
426                               objects:objects
427                           atLocations:loc1s
428                           byLocations:loc2s];
429    [hash release];
430    [loc1s release];
431    [loc2s release];
432    [empty release];
433    return ret;
434}
435+ (id)matrixWithCuboidBoundArray:(NSArray *)bounds
436            objectsAtCoordinates:(id)object1,...
437{
438    NSMutableArray *objects = [NSMutableArray array];
439    NSMutableArray *coords  = [NSMutableArray array];
440    id object = object1;
441    va_list args;
442
443    if (object1 != 0)
444        {
445        va_start(args, object1);
446
447        do
448            {
449                NSMutableArray *coord = [NSMutableArray arrayWithCapacity:
450                    [bounds count]];
451                [objects addObject:object];
452                while ([coord count] < [bounds count])
453                    [coord addObject:[NSNumber numberWithInt:
454                        va_arg(args, unsigned)]];
455                [coords addObject:coord];
456            }
457        while (object = va_arg(args, id));
458
459        va_end(args);
460        }
461    return [self matrixWithCuboidBoundArray:bounds
462                                    objects:objects
463                         atCoordinateArrays:coords];
464}
465+ (id)matrixWithCuboidBounds:(unsigned)bound1,...
466{
467    va_list args;
468    id<KTLocationHash> hash;
469    id ret;
470
471    va_start(args, bound1);
472    hash = [[KTCuboidHash allocWithZone:NULL] initWithBoundsList:bound1 :&args];
473    ret = [self matrixWithLocationHash:hash];
474    [hash release];
475    va_end(args);
476    return ret;
477}
478+ (id)matrixWithCuboidBoundsObjectAtCoordinates:(unsigned)bound1,...
479{
480    KTCuboidHash *hash; // The hashing object to use
481    va_list args;       // To trawl through the arguments
482    id ret;             // The object being returned
483    id object;          // Used to store the object in the arguments
484
485    va_start(args, bound1);
486    hash = [[KTCuboidHash alloc] initWithBoundsList:bound1 :&args];
487    object = va_arg(args, id);
488
489    if ([self isEqual:[KTMatrix class]])
490        {   // Can optimize away some inefficiencies
491        unsigned loc = [hash hashForCoordinatesList:&args];
492
493        if (([hash hashBound] != 0) && ([hash hashBound] <= 3))
494            ret = [KTMatrixDenseImp alloc];
495        else
496            ret = [KTMatrixSparseImp alloc];
497        ret = [[ret initWithLocationHash:hash
498                                  object:object
499                        atHashedLocation:loc] autorelease];
500        }
501    else
502        {
503        unsigned i, dimension = [hash dimension];
504        NSMutableArray *coord = [[NSMutableArray alloc] init];
505        NSNumber *number;
506
507        for (i = 0; i < dimension; i++)
508            {
509            number = [[NSNumber alloc] initWithInt:va_arg(args, unsigned)];
510            [coord addObject:number];
511            [number release];
512            }
513
514        ret = [self matrixWithLocationHash:hash
515                                    object:object
516                         atCoordinateArray:coord];
517        [coord release];
518        }
519
520    [hash release];
521    va_end(args);
522    return ret;
523}
524+ (id)matrixWithCuboidBoundsObjectsAtCoordinateArrays:(unsigned)bound1,...
525{
526    NSMutableArray *bounds = [NSMutableArray array];
527    unsigned bound = bound1;
528    NSMutableArray *objects = [NSMutableArray array];
529    NSMutableArray *coords  = [NSMutableArray array];
530    id object = NULL;
531    va_list args;
532
533    if (bound1 != 0)
534        {
535        va_start(args, bound1);
536
537        do
538            [bounds addObject:[NSNumber numberWithInt:bound]];
539        while (bound = va_arg(args, unsigned));
540
541        while (object = va_arg(args, id))
542            {
543            [objects addObject:object];
544            [coords addObject:va_arg(args, id)];
545            }
546
547        va_end(args);
548        }
549    return [self matrixWithCuboidBoundArray:bounds
550                                    objects:objects
551                         atCoordinateArrays:coords];
552}
553+ (id)matrixWithCuboidBoundsObjectsAtCoordinates:(unsigned)bound1,...
554{
555    KTCuboidHash *hash; // The hashing object to use
556    va_list args;       // To trawl through the arguments
557    id object;          // Used to store the objects in the arguments
558    id ret;             // The object being returned
559
560    // Read in data for the cuboid hash
561    va_start(args, bound1);
562    hash = [[KTCuboidHash alloc] initWithBoundsList:bound1 :&args];
563
564    if ([self isEqual:[KTMatrix class]])
565        {   // Can optimize away some inefficiencies
566        // Need a mutable temporary to store all the objects
567        KTMutableMatrixSparseImp *temp;
568        // SELs/IMPs to speed up repeated method calls
569        SEL hashListSEL = @selector(hashForCoordinatesList:);
570        SEL setObjSEL = @selector(setObject:atHashedLocation:);
571        unsigned (*hashListIMP)(id, SEL, ...);
572        void (*setObjIMP)(id, SEL, ...);
573
574        // Allocate the temporary mutable matrix
575        temp = [[KTMutableMatrixSparseImp alloc] initWithCapacity:0
576                                                     locationHash:hash];
577
578        // Read in objects and coordinates
579        hashListIMP = (unsigned (*)(id, SEL, ...))
580            [hash methodForSelector:hashListSEL];
581        setObjIMP = (void (*)(id, SEL, ...))
582            [temp methodForSelector:setObjSEL];
583        while (object = va_arg(args, id))
584            setObjIMP(temp, setObjSEL, object,
585                      hashListIMP(hash,hashListSEL,&args));
586
587        // Make an immutable copy of the object
588        ret = [[temp copyWithZone:NULL] autorelease];
589        [temp release];
590        }
591    else
592        {   // Version for derived classes
593        unsigned dimension = [hash dimension];
594        NSMutableArray *objects = [[NSMutableArray alloc] init];
595        NSMutableArray *coords  = [[NSMutableArray alloc] init];
596        NSNumber *number;
597        unsigned i;
598        NSMutableArray *coord;
599
600        // Fill a couple of arrays with the objects and coordinates
601        while (object = va_arg(args, id))
602            {
603            [objects addObject:object];
604            coord = [NSMutableArray array];
605            for (i = 0; i < dimension; i++)
606                {
607                number = [[NSNumber alloc] initWithInt:va_arg(args, unsigned)];
608                [coord addObject:number];
609                [number release];
610                }
611            [coords addObject:coord];
612            }
613
614        ret = [self matrixWithLocationHash:hash
615                                   objects:objects
616                        atCoordinateArrays:coords];
617        [objects release];
618        [coords release];
619        }
620
621    [hash release];
622    va_end(args);
623    return ret;
624}
625
626- (id)init
627{
628    return (self = [super init]);
629}
630- (id)initWithMatrix:(KTMatrix *)matrix
631{
632    [NSException raise:NSGenericException
633                format:
634        @"Must implement a complete subclass of KTMatrix!"];
635    [self release];
636    return NULL;
637}
638- (id)initWithLocationHash:(id<KTLocationHash>)hash
639{
640    return (self = [self initWithMatrix:
641        [KTMatrix matrixWithLocationHash:hash]]);
642}
643- (id)initWithLocationHash:(id<KTLocationHash>)hash
644                    object:(id)object
645                atLocation:(NSDictionary *)loc
646{   // Not sure of an efficient way to implement this generally
647    NSArray *objects = [NSArray arrayWithObject:object];
648    NSArray *loc1s = [NSArray arrayWithObject:loc];
649    NSDictionary *empty = [[NSDictionary allocWithZone:NULL] init];
650    NSArray *loc2s = [NSArray arrayWithObject:empty];
651    self = [self initWithLocationHash:hash
652                              objects:objects
653                          atLocations:loc1s
654                          byLocations:loc2s];
655    [empty release];
656    return self;
657}
658- (id)initWithLocationHash:(id<KTLocationHash>)hash
659                    object:(id)object
660                atLocation:(NSDictionary *)loc1
661                byLocation:(NSDictionary *)loc2
662{   // Not sure of a way to implement this generally without autorelease use
663    // I suspect NSArray's initWithObjects: may use autorelease
664    return [self initWithLocationHash:(id<KTLocationHash>)hash
665                              objects:[NSArray arrayWithObject:object]
666                          atLocations:[NSArray arrayWithObject:loc1]
667                          byLocations:[NSArray arrayWithObject:loc2]];
668}
669- (id)initWithLocationHash:(id<KTLocationHash>)hash
670                   objects:(NSArray *)objects
671               atLocations:(NSArray *)locs
672{
673    NSDictionary *empty = [[NSDictionary alloc] init];
674    NSMutableArray *temp = [[NSMutableArray alloc] initWithCapacity:
675        [locs count]];
676    unsigned i;
677    for (i = 0; i < [locs count]; i++)
678        [temp addObject:empty];
679    [empty release];
680    self = [self initWithLocationHash:(id<KTLocationHash>)hash
681                              objects:objects
682                          atLocations:locs
683                          byLocations:temp];
684    [temp release];
685    return self;
686}
687- (id)initWithLocationHash:(id<KTLocationHash>)hash
688                   objects:(NSArray *)objects
689               atLocations:(NSArray *)loc1s
690                byLocation:(NSDictionary *)loc2
691{
692    NSMutableArray *temp = [[NSMutableArray alloc] initWithCapacity:
693        [loc1s count]];
694    unsigned i;
695    for (i = 0; i < [loc1s count]; i++)
696        [temp addObject:loc2];
697    self = [self initWithLocationHash:(id<KTLocationHash>)hash
698                              objects:objects
699                          atLocations:loc1s
700                          byLocations:temp];
701    [temp release];
702    return self;
703}
704- (id)initWithLocationHash:(id<KTLocationHash>)hash
705                   objects:(NSArray *)objects
706               atLocations:(NSArray *)loc1s
707               byLocations:(NSArray *)loc2
708{
709    return [self initWithMatrix:
710        [KTMatrixSparseImp matrixWithLocationHash:hash
711                                          objects:objects
712                                      atLocations:loc1s
713                                      byLocations:loc2]];
714}
715- (id)initWithLocationHash:(id<KTLocationHash>)hash
716        objectsAtLocations:(id)object1,...
717{
718    NSDictionary *empty     = [NSDictionary dictionary];
719    NSMutableArray *objects = [NSMutableArray array];
720    NSMutableArray *loc1s   = [NSMutableArray array];
721    NSMutableArray *loc2s   = [NSMutableArray array];
722    id object = object1;
723    va_list args;
724
725    if (object1 != 0)
726        {
727        va_start(args, object1);
728
729        do
730            {
731                [objects addObject:object];
732                [loc1s addObject:va_arg(args, id)];
733                [loc2s addObject:empty];
734            }
735        while (object = va_arg(args, id));
736
737        va_end(args);
738        }
739    return [self initWithLocationHash:(id<KTLocationHash>)hash
740                              objects:objects
741                          atLocations:loc1s
742                          byLocations:loc2s];
743}
744- (id)       initWithLocationHash:(id<KTLocationHash>)hash
745    objectsAtLocationsByLocations:(id)object1,...
746{
747    NSMutableArray *objects = [NSMutableArray array];
748    NSMutableArray *loc1s   = [NSMutableArray array];
749    NSMutableArray *loc2s   = [NSMutableArray array];
750    id object = object1;
751    va_list args;
752
753    if (object1 != 0)
754        {
755        va_start(args, object1);
756
757        do
758            {
759                [objects addObject:object];
760                [loc1s addObject:va_arg(args, id)];
761                [loc2s addObject:va_arg(args, id)];
762            }
763        while (object = va_arg(args, id));
764
765        va_end(args);
766        }
767    return [self initWithLocationHash:(id<KTLocationHash>)hash
768                              objects:objects
769                          atLocations:loc1s
770                          byLocations:loc2s];
771}
772
773- (id)initWithLocationHash:(id<KTLocationHash>)hash
774                    object:(id)object
775         atCoordinateArray:(NSArray *)coord
776{
777    NSMutableDictionary *loc1 = [[NSMutableDictionary alloc] init];
778    NSDictionary *loc2 = [[NSDictionary alloc] init];
779    NSEnumerator *axes = [[hash axes] objectEnumerator];
780    NSEnumerator *coords = [coord objectEnumerator];
781    id axis;
782
783    if ([[hash axes] count] != [coord count])
784        [NSException raise:NSInvalidArgumentException
785                    format:
786            @"Dimensions of hash do not agree with number of coordinates"];
787    while ((axis = [axes nextObject]))
788        [loc1 setObject:[coords nextObject]
789                 forKey:axis];
790    self = [self initWithLocationHash:hash
791                               object:object
792                           atLocation:loc1
793                           byLocation:loc2];
794    [loc1 release];
795    [loc2 release];
796    return self;
797}
798- (id)initWithLocationHash:(id<KTLocationHash>)hash
799                    object:(id)object
800             atCoordinates:(unsigned)x,...
801{
802    NSMutableArray *array = [NSMutableArray arrayWithObject:
803        [NSNumber numberWithInt:x]];
804    unsigned axes = [[hash axes] count];
805    va_list args;
806
807    va_start(args, x);
808
809    while ([array count] < axes)
810        [array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]];
811
812    va_end(args);
813
814    return [self initWithLocationHash:hash
815                               object:object
816                    atCoordinateArray:array];
817}
818- (id)initWithLocationHash:(id<KTLocationHash>)hash
819                   objects:(NSArray *)objects
820        atCoordinateArrays:(NSArray *)coords
821{
822    NSArray *dims = [hash axes];
823    NSMutableArray *loc1s = [[NSMutableArray alloc] initWithCapacity:
824        [coords count]];
825    NSMutableArray *loc2s = [[NSMutableArray alloc] initWithCapacity:
826        [coords count]];
827    NSMutableDictionary *loc;
828    NSDictionary *empty = [[NSDictionary alloc] init];
829
830    NSEnumerator *axes;
831    NSEnumerator *coordArrays = [coords objectEnumerator];
832    NSEnumerator *vals;
833    id axis;
834    NSArray *coord;
835
836    while ((coord = [coordArrays nextObject]))
837        {
838        if ([dims count] != [coord count])
839            [NSException raise:NSInvalidArgumentException
840                        format:
841                @"Dimensions of hash and number of coordinates not equal"];
842        axes = [dims objectEnumerator];
843        vals = [coord objectEnumerator];
844        loc  = [[NSMutableDictionary alloc] init];
845        while ((axis = [axes nextObject]))
846            [loc setObject:[vals nextObject]
847                    forKey:axis];
848        [loc1s addObject:loc];
849        [loc2s addObject:empty];
850        [loc release];
851        }
852    self = [self initWithLocationHash:hash
853                              objects:objects
854                          atLocations:loc1s
855                          byLocations:loc2s];
856    [loc1s release];
857    [loc2s release];
858    [empty release];
859    return self;
860}
861- (id)initWithLocationHash:(id<KTLocationHash>)hash
862      objectsAtCoordinates:(id)object1,...
863{
864    NSMutableArray *objects = [NSMutableArray array];
865    NSMutableArray *coords  = [NSMutableArray array];
866    id object = object1;
867    va_list args;
868
869    if (object1 != 0)
870        {
871        va_start(args, object1);
872
873        do
874            {
875                [objects addObject:object];
876                [coords addObject:va_arg(args, id)];
877            }
878        while (object = va_arg(args, id));
879
880        va_end(args);
881        }
882    return [self initWithLocationHash:hash
883                              objects:objects
884                   atCoordinateArrays:coords];
885}
886
887- (id)initWithCuboidBoundArray:(NSArray *)bounds
888{
889    id<KTLocationHash> hash = [[KTCuboidHash allocWithZone:[self zone]]
890        initWithBounds:bounds];
891    self = [self initWithLocationHash:hash];
892    [hash release];
893    return self;
894}
895- (id)initWithCuboidBoundArray:(NSArray *)bounds
896                        object:(id)object
897             atCoordinateArray:(NSArray *)coord
898{
899    NSMutableDictionary *loc1 = [NSMutableDictionary dictionaryWithCapacity:
900        [bounds count]];
901    NSMutableDictionary *loc2 = [NSMutableDictionary dictionary];
902    id<KTLocationHash> hash = [[KTCuboidHash allocWithZone:[self zone]]
903        initWithBounds:bounds];
904    unsigned i;
905
906    if ([bounds count] != [coord count])
907        [NSException raise:NSInvalidArgumentException
908                    format:
909            @"Dimension of cuboid and dimension of coordinates not equal"];
910    for (i = 0; i < [bounds count]; i++)
911        [loc1 setObject:[coord objectAtIndex:i]
912                 forKey:[NSNumber numberWithInt:i]];
913    self = [self initWithLocationHash:hash
914                               object:object
915                           atLocation:loc1
916                           byLocation:loc2];
917    [hash release];
918    return self;
919}
920- (id)initWithCuboidBoundArray:(NSArray *)bounds
921                        object:(id)object
922                 atCoordinates:(unsigned)x,...
923{
924    NSMutableArray *array = [NSMutableArray arrayWithObject:
925        [NSNumber numberWithInt:x]];
926    unsigned axes = [bounds count];
927    id<KTLocationHash> hash = [[KTCuboidHash allocWithZone:[self zone]]
928        initWithBounds:bounds];
929    va_list args;
930
931    va_start(args, x);
932
933    while ([array count] < axes)
934        [array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]];
935
936    va_end(args);
937
938    self = [self initWithLocationHash:hash
939                               object:object
940                    atCoordinateArray:array];
941    [hash release];
942    return self;
943}
944- (id)initWithCuboidBoundArray:(NSArray *)bounds
945                       objects:(NSArray *)objects
946            atCoordinateArrays:(NSArray *)coords
947{
948    NSMutableArray *loc1s = [[NSMutableArray alloc] initWithCapacity:
949        [coords count]];
950    NSMutableArray *loc2s = [[NSMutableArray alloc] initWithCapacity:
951        [coords count]];
952    NSMutableDictionary *loc;
953    NSDictionary *empty = [[NSDictionary alloc] init];
954    id<KTLocationHash> hash = [[KTCuboidHash allocWithZone:[self zone]]
955        initWithBounds:bounds];
956    unsigned i;
957
958    NSEnumerator *coordArrays = [coords objectEnumerator];
959    NSArray *coord;
960
961    while ((coord = [coordArrays nextObject]))
962        {
963        if ([bounds count] != [coord count])
964            [NSException raise:NSInvalidArgumentException
965                        format:
966                @"Dimensions of cuboid and number of coordinates not equal"];
967        loc  = [[NSMutableDictionary alloc] init];
968        for (i = 0; i < [bounds count]; i++)
969            [loc setObject:[coord objectAtIndex:i]
970                    forKey:[NSNumber numberWithInt:i]];
971        [loc1s addObject:loc];
972        [loc2s addObject:empty];
973        [loc release];
974        }
975    self = [self initWithLocationHash:hash
976                              objects:objects
977                          atLocations:loc1s
978                          byLocations:loc2s];
979    [hash release];
980    [loc1s release];
981    [loc2s release];
982    [empty release];
983    return self;
984}
985- (id)initWithCuboidBoundArray:(NSArray *)bounds
986          objectsAtCoordinates:(id)object1,...
987{
988    NSMutableArray *objects = [NSMutableArray array];
989    NSMutableArray *coords  = [NSMutableArray array];
990    id object = object1;
991    va_list args;
992
993    if (object1 != 0)
994        {
995        va_start(args, object1);
996
997        do
998            {
999                [objects addObject:object];
1000                [coords addObject:va_arg(args, id)];
1001            }
1002        while (object = va_arg(args, id));
1003
1004        va_end(args);
1005        }
1006    return [self initWithCuboidBoundArray:bounds
1007                                  objects:objects
1008                       atCoordinateArrays:coords];
1009}
1010- (id)initWithCuboidBounds:(unsigned)bound1,...
1011{
1012    va_list args;
1013    KTCuboidHash *hash;
1014
1015    va_start(args, bound1);
1016    hash = [[KTCuboidHash allocWithZone:[self zone]]
1017                initWithBoundsList:bound1 :&args];
1018    self = [self initWithLocationHash:hash];
1019    [hash release];
1020    return self;
1021}
1022- (id)initWithCuboidBoundsObjectAtCoordinates:(unsigned)bound1,...
1023{
1024    KTCuboidHash *hash;
1025    unsigned dimension;
1026    id object = NULL;
1027    NSMutableArray *coord = [NSMutableArray allocWithZone:NULL];
1028    NSNumber *number;
1029    va_list args;
1030
1031    va_start(args, bound1);
1032    hash = [[KTCuboidHash allocWithZone:[self zone]]
1033                initWithBoundsList:bound1 :&args];
1034    dimension = [hash dimension];
1035
1036    object = va_arg(args, id);
1037
1038    coord = [coord initWithCapacity:dimension];
1039    while ([coord count] < dimension)
1040        {
1041        number = [[NSNumber alloc] initWithInt:va_arg(args, unsigned)];
1042        [coord addObject:number];
1043        [number release];
1044        }
1045
1046    self = [self initWithLocationHash:hash
1047                               object:object
1048                    atCoordinateArray:coord];
1049
1050    va_end(args);
1051    [hash release];
1052    [coord release];
1053    return self;
1054}
1055- (id)initWithCuboidBoundsObjectsAtCoordinateArrays:(unsigned)bound1,...
1056{
1057    NSMutableArray *bounds = [NSMutableArray array];
1058    unsigned bound = bound1;
1059    NSMutableArray *objects = [NSMutableArray array];
1060    NSMutableArray *coords  = [NSMutableArray array];
1061    id object = NULL;
1062    va_list args;
1063
1064    if (bound1 != 0)
1065        {
1066        va_start(args, bound1);
1067
1068        do
1069            [bounds addObject:[NSNumber numberWithInt:bound]];
1070        while (bound = va_arg(args, unsigned));
1071
1072        while (object = va_arg(args, id))
1073            {
1074            [objects addObject:object];
1075            [coords addObject:va_arg(args, id)];
1076            }
1077
1078        va_end(args);
1079        }
1080    return [self initWithCuboidBoundArray:bounds
1081                                  objects:objects
1082                       atCoordinateArrays:coords];
1083}
1084- (id)initWithCuboidBoundsObjectsAtCoordinates:(unsigned)bound1,...
1085{
1086    KTCuboidHash *hash;
1087    unsigned dimension;
1088    NSMutableArray *objects = [[NSMutableArray allocWithZone:NULL] init];
1089    NSMutableArray *coords  = [[NSMutableArray allocWithZone:NULL] init];
1090    id object = NULL;
1091    unsigned i;
1092    NSMutableArray *coord;
1093    NSNumber *number;
1094    va_list args;
1095
1096    va_start(args, bound1);
1097
1098    hash = [[KTCuboidHash allocWithZone:[self zone]]
1099                initWithBoundsList:bound1 :&args];
1100    dimension = [hash dimension];
1101
1102    while (object = va_arg(args, id))
1103        {
1104        [objects addObject:object];
1105        coord = [[NSMutableArray allocWithZone:NULL] initWithCapacity:
1106            dimension];
1107        for (i = 0; i < dimension; i++)
1108            {
1109            number = [[NSNumber alloc] initWithInt:va_arg(args, unsigned)];
1110            [coord addObject:number];
1111            [number release];
1112            }
1113        [coords addObject:coord];
1114        [coord release];
1115        }
1116
1117    self = [self initWithLocationHash:hash
1118                              objects:objects
1119                   atCoordinateArrays:coords];
1120
1121    va_end(args);
1122    [hash release];
1123    [objects release];
1124    [coords release];
1125    return self;
1126}
1127
1128//// Accessor methods
1129- (id)objectAtLocation:(NSDictionary *)loc
1130{
1131    return [self objectAtLocation:loc
1132                       byLocation:[NSDictionary dictionary]];
1133}
1134- (id)objectAtLocation:(NSDictionary *)loc1
1135            byLocation:(NSDictionary *)loc2;
1136{
1137    [NSException raise:NSGenericException
1138                format:
1139        @"Must implement a complete subclass of KTMatrix!"];
1140    return NULL;
1141}
1142- (NSArray *)objectsAtLocations:(NSArray *)locs
1143                 notFoundMarker:(id)anObject
1144{
1145    NSEnumerator *i = [locs objectEnumerator];
1146    NSMutableArray *ret = [NSMutableArray arrayWithCapacity:[locs count]];
1147    NSDictionary *empty = [NSDictionary dictionary];
1148    id loc;
1149    id object;
1150    while ((loc = [i nextObject]))
1151        {
1152        if ((object = [self objectAtLocation:loc
1153                                  byLocation:empty]))
1154            [ret addObject:object];
1155        else
1156            [ret addObject:anObject];
1157        }
1158    return ret;
1159}
1160- (NSArray *)objectsAtLocations:(NSArray *)loc1s
1161                     byLocation:(NSDictionary *)loc2
1162                 notFoundMarker:(id)anObject
1163{
1164    NSEnumerator *i = [loc1s objectEnumerator];
1165    NSMutableArray *ret = [NSMutableArray arrayWithCapacity:[loc1s count]];
1166    id loc1;
1167    id object;
1168    while ((loc1 = [i nextObject]))
1169        {
1170        if ((object = [self objectAtLocation:loc1
1171                                  byLocation:loc2]))
1172            [ret addObject:object];
1173        else
1174            [ret addObject:anObject];
1175        }
1176    return ret;
1177}
1178- (NSArray *)objectsAtLocations:(NSArray *)loc1s
1179                    byLocations:(NSArray *)loc2s
1180                 notFoundMarker:(id)anObject
1181{
1182    NSEnumerator *i = [loc1s objectEnumerator];
1183    NSEnumerator *j = [loc2s objectEnumerator];
1184    NSMutableArray *ret = [NSMutableArray arrayWithCapacity:[loc1s count]];
1185    id loc1, loc2;
1186    id object;
1187    if ([loc1s count] != [loc2s count])
1188        [NSException raise:NSInvalidArgumentException
1189                    format:
1190            @"Locations arrays not of equal length"];
1191    while ((loc1 = [i nextObject]) && (loc2 = [j nextObject]))
1192        {
1193        if ((object = [self objectAtLocation:loc1
1194                                  byLocation:loc2]))
1195            [ret addObject:object];
1196        else
1197            [ret addObject:anObject];
1198        }
1199    return ret;
1200}
1201- (id)objectAtCoordinateArray:(NSArray *)coords
1202{
1203    NSMutableDictionary *loc = [NSMutableDictionary dictionaryWithCapacity:
1204        [coords count]];
1205    NSArray *dims = [self axes];
1206    unsigned axis;
1207
1208    if ([dims count] != [coords count])
1209        [NSException raise:NSInvalidArgumentException
1210                    format:
1211            @"Dimension of cuboid and dimension of coordinates not equal"];
1212    for (axis = 0; axis < [coords count]; axis++)
1213        [loc setObject:[coords objectAtIndex:axis]
1214                forKey:[dims objectAtIndex:axis]];
1215    return [self objectAtLocation:loc
1216                       byLocation:[NSDictionary dictionary]];
1217}
1218- (NSArray *)objectsAtCoordinateArrays:(NSArray *)coords
1219                        notFoundMarker:(id)anObject
1220{
1221    NSEnumerator *i = [coords objectEnumerator];
1222    NSMutableArray *ret = [NSMutableArray arrayWithCapacity:[coords count]];
1223    id coord;
1224    id object;
1225    NSMutableDictionary *loc = [NSMutableDictionary dictionaryWithCapacity:
1226        [coords count]];
1227    NSDictionary *empty = [NSDictionary dictionary];
1228    NSArray *dims = [self axes];
1229    unsigned axis;
1230
1231    while ((coord = [i nextObject]))
1232        {
1233        if ([dims count] != [coord count])
1234            [NSException raise:NSInvalidArgumentException
1235                        format:
1236                @"Dimension of cuboid and of coordinates not equal"];
1237        for (axis = 0; axis < [coord count]; axis++)
1238            [loc setObject:[coord objectAtIndex:axis]
1239                    forKey:[dims objectAtIndex:axis]];
1240        if ((object = [self objectAtLocation:loc
1241                                  byLocation:empty]))
1242            [ret addObject:object];
1243        else
1244            [ret addObject:anObject];
1245        }
1246    return ret;
1247}
1248- (id)objectAtCoordinates:(unsigned)x,...
1249{
1250    NSMutableArray *array
1251    = [NSMutableArray arrayWithObject:[NSNumber numberWithInt:x]];
1252    unsigned axes = [self dimension];
1253    va_list args;
1254
1255    va_start(args, x);
1256
1257    while ([array count] < axes)
1258        [array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]];
1259
1260    va_end(args);
1261
1262    return [self objectAtCoordinateArray:array];
1263}
1264- (id<KTLocationHash>)locationHash
1265{
1266    [NSException raise:NSGenericException
1267                format:
1268        @"Must implement a complete subclass of KTMatrix!"];
1269    return NULL;
1270}
1271
1272//// Internal use accessors
1273- (NSDictionary *)matrixData
1274{
1275    [NSException raise:NSGenericException
1276                format:
1277        @"Must implement a complete subclass of KTMatrix!"];
1278    return NULL;
1279}
1280
1281//// Convenience methods fall straight through to hash equivalents
1282- (NSArray *)axes
1283{ return [[self locationHash] axes]; }
1284- (unsigned)dimension
1285{ return [[self axes] count]; }
1286- (unsigned)lowerBoundForAxis:(id)axis
1287{ return [[self locationHash] lowerBoundForAxis:axis]; }
1288- (unsigned)lowerBoundForDimension:(unsigned)dim
1289{
1290    return [self lowerBoundForAxis:
1291        [[self axes] objectAtIndex:dim]];
1292}
1293- (unsigned)upperBoundForAxis:(id)axis
1294{ return [[self locationHash] upperBoundForAxis:axis]; }
1295- (unsigned)upperBoundForDimension:(unsigned)dim
1296{
1297    return [self upperBoundForAxis:
1298        [[self axes] objectAtIndex:dim]];
1299}
1300
1301//// Object methods
1302- (NSArray *)allObjects
1303{ return [[self objectEnumerator] allObjects]; }
1304- (unsigned)count
1305{
1306    [NSException raise:NSGenericException
1307                format:
1308        @"Must implement a complete subclass of KTMatrix!"];
1309    return 0;
1310}
1311- (NSEnumerator *)objectEnumerator
1312{
1313    [NSException raise:NSGenericException
1314                format:
1315        @"Must implement a complete subclass of KTMatrix!"];
1316    return NULL;
1317}
1318- (NSEnumerator *)objectEnumeratorRetained
1319{ return [[self objectEnumerator] retain]; }
1320- (NSEnumerator *)reverseObjectEnumerator
1321{ return [[self allObjects] reverseObjectEnumerator]; }
1322
1323//// Inherited NSObject methods
1324- (BOOL)isEqual:(id)other
1325{
1326    if ([other isKindOfClass:[KTMatrix class]])
1327        return ([[self matrixData] isEqual:[other matrixData]] &&
1328                [[self locationHash] isEqual:[other locationHash]]);
1329    return NO;
1330}
1331
1332
1333//// Protocols
1334- (void)encodeWithCoder:(NSCoder *)coder
1335{
1336    [coder encodeObject:[self matrixData]/* forKey:@"matrixData"*/];
1337    [coder encodeObject:[self locationHash]/* forKey:@"locationHash"*/];
1338}
1339- (id)initWithCoder:(NSCoder *)coder
1340{
1341    NSDictionary *matrixData = [coder decodeObject/*ForKey:@"matrixData"*/];
1342    id<KTLocationHash> hash = [coder decodeObject/*ForKey:@"locationHash"*/];
1343    NSZone *zone = [self zone];
1344    [self release];
1345    if (([hash hashBound] == 0) || ([matrixData count] < [hash hashBound]/3))
1346        self = [[KTMatrixSparseImp allocWithZone:zone]
1347                   initWithMatrixData:matrixData
1348                         locationHash:hash];
1349    else
1350        self = [[KTMatrixDenseImp allocWithZone:zone]
1351                   initWithMatrixData:matrixData
1352                         locationHash:hash];
1353    return self;
1354}
1355
1356- (id)copyWithZone:(NSZone *)zone
1357{
1358    if (([[self locationHash] hashBound] == 0) ||
1359        ([self count] < [[self locationHash] hashBound]/3))
1360        return [[KTMatrixSparseImp allocWithZone:zone] initWithMatrix:self];
1361    else
1362        return [[KTMatrixDenseImp allocWithZone:zone] initWithMatrix:self];
1363}
1364
1365- (id)mutableCopyWithZone:(NSZone *)zone;
1366{
1367    if (([[self locationHash] hashBound] == 0) ||
1368        ([self count] < [[self locationHash] hashBound]/3))
1369        return [[KTMutableMatrixSparseImp allocWithZone:
1370            zone] initWithMatrix:self];
1371    else
1372        return [[KTMutableMatrixDenseImp allocWithZone:
1373            zone] initWithMatrix:self];
1374}
1375
1376@end
1377