2 Copyright (C) 2000-2005 SKYRIX Software AG
4 This file is part of SOPE.
6 SOPE is free software; you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 SOPE is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
14 License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with SOPE; see the file COPYING. If not, write to the
18 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 #include "WETableCalcMatrix.h"
26 NSMutableArray *items;
38 typedef enum { WERow, WEColumn } WEOrientation;
40 static NSNull *null = nil;
42 @implementation WETableCalcMatrixSpan
44 + (id)spanWithObject:(id)_obj range:(NSRange *)_range {
46 span = [[WETableCalcMatrixSpan alloc] initWithObject:_obj range:_range];
47 return [span autorelease];
49 - (id)initWithObject:(id)_obj range:(NSRange *)_range {
50 self->object = [_obj retain];
51 self->range = *_range;
55 [self->object release];
70 - (BOOL)startsAtIndex:(unsigned)_idx {
71 return (_idx == self->range.location) ? YES : NO;
73 - (BOOL)occupiesIndex:(unsigned)_idx {
74 if (_idx < self->range.location)
76 if (_idx >= (self->range.location + self->range.length))
81 return self->range.length;
86 - (NSString *)description {
87 return [NSString stringWithFormat:
88 @"<0x%08X[%@]: object=0x%08X start=%d len=%d>",
89 self, NSStringFromClass([self class]),
95 @end /* WETableCalcMatrixSpan */
97 @interface WETableCalcMatrixStripe : NSObject
101 MatrixThread *threads;
103 WETableCalcMatrix *matrix; /* non-retained */
104 id delegate; /* non-retained */
107 - (unsigned)threadCount;
108 - (NSArray *)threads;
109 - (NSArray *)threadSpans;
113 - (void)addObject:(id)_obj atPositions:(unsigned *)_pos count:(unsigned)_c;
117 @implementation WETableCalcMatrixStripe
120 if (null == nil) null = [[NSNull null] retain];
123 - (id)initWithSize:(unsigned)_h
124 matrix:(WETableCalcMatrix *)_matrix
125 delegate:(id)_delegate
128 self->matrix = _matrix;
130 if ([_delegate respondsToSelector:
131 @selector(tableCalcMatrix:spanForObject:range:)])
132 self->delegate = _delegate;
140 for (i = 0; i < (unsigned)self->threadCount; i++) {
141 if (self->threads[i].objects) {
144 for (j = 0; j < self->size; j++)
145 [self->threads[i].objects[j] release];
146 free(self->threads[i].objects);
156 - (unsigned)threadCount {
157 return self->threadCount;
160 - (NSArray *)threadAtIndex:(unsigned)_idx {
165 objs = calloc(self->size, sizeof(id));
166 NSAssert(objs, @"could not allocate memory ..");
167 NSAssert(self->size > 0, @"invalid size ..");
169 for (i = 0; i < self->size; i++) {
170 objs[i] = self->threads[_idx].objects[i];
175 result = [NSArray arrayWithObjects:objs count:self->size];
179 - (NSArray *)spansAtIndex:(unsigned)_idx {
181 unsigned i, spanCount;
184 spans = calloc(self->size, sizeof(id));
186 for (i = 0, spanCount = 0; i < self->size; ) {
187 WETableCalcMatrixSpan *span;
192 obj = self->threads[_idx].objects[i];
194 if ((i + 1) == self->size) {
201 /* look ahead for similiar entries */
207 for (j = i + 1; j < self->size; j++) {
210 nextObj = self->threads[_idx].objects[j];
216 /* continue at end of this object */
221 if (self->delegate) {
222 span = [self->delegate tableCalcMatrix:self->matrix
227 span = [[WETableCalcMatrixSpan alloc] initWithObject:obj range:&r];
231 spans[spanCount] = span;
234 result = [NSArray arrayWithObjects:spans count:spanCount];
239 - (NSArray *)threads {
240 if (self->threadCount == 0)
242 if (self->threadCount == 1)
243 return [NSArray arrayWithObject:[self threadAtIndex:0]];
246 id threadArrays[self->threadCount];
249 for (i = 0; i < (unsigned)self->threadCount; i++)
250 threadArrays[i] = [self threadAtIndex:i];
252 return [NSArray arrayWithObjects:threadArrays count:self->threadCount];
255 - (NSArray *)threadSpans {
256 if (self->threadCount == 0)
258 else if (self->threadCount == 1)
259 return [NSArray arrayWithObject:[self spansAtIndex:0]];
261 NSArray *threadArrays[self->threadCount];
264 for (i = 0; i < (unsigned)self->threadCount; i++) {
265 threadArrays[i] = [self spansAtIndex:i];
268 return [NSArray arrayWithObjects:threadArrays count:self->threadCount];
274 - (unsigned)threadForPositions:(unsigned *)_pos count:(unsigned)_c {
278 if (self->threadCount == 0) {
279 self->threads = calloc(1, sizeof(MatrixThread));
280 self->threads[0].objects = calloc(self->size, sizeof(id));
281 self->threadCount = 1;
285 /* check each column */
286 for (i = 0; i < (unsigned)self->threadCount; i++) {
288 MatrixThread *column;
291 column = &(self->threads[i]);
293 /* check each required position in column */
294 for (j = 0, ok = YES; j < _c; j++) {
295 unsigned requiredPos;
297 requiredPos = _pos[j];
298 NSAssert(requiredPos < self->size, @"index to high ..");
300 if (column->objects[requiredPos] != nil) {
301 /* position already assigned */
307 /* all required position available, return column */
310 /* check next column */
313 /* all available threads are full, make new one .. */
315 self->threads = calloc(self->threadCount + 1, sizeof(MatrixThread));
316 memcpy(self->threads, tmp, self->threadCount * sizeof(MatrixThread));
317 self->threads[self->threadCount].objects = calloc(self->size, sizeof(id));
319 return (self->threadCount - 1);
322 - (void)addObject:(id)_obj atPositions:(unsigned *)_pos count:(unsigned)_c {
329 thread = [self threadForPositions:_pos count:_c];
330 NSAssert(thread < (unsigned)self->threadCount, @"invalid idx");
333 for (i = 0; i < _c; i++) {
334 unsigned requiredIdx;
336 requiredIdx = _pos[i];
339 NSAssert(requiredIdx < self->size, @"index to high ..");
340 NSAssert3(self->threads[thread].objects[requiredIdx] == nil,
341 @"index %i is already marked (by=0x%08X, my=0x%08X) !",
342 requiredIdx, self->threads[thread].objects[requiredIdx], _obj);
345 self->threads[thread].objects[requiredIdx] = RETAIN(_obj);
351 @interface WETableCalcMatrixPositionArray : NSObject
352 { /* mutable array of matrix coordinates */
355 MatrixCoord *positions;
358 - (void)addPosition:(unsigned)_x:(unsigned)_y;
359 - (void)checkForDuplicates;
361 /* narrow set to row or column */
362 - (unsigned *)indicesInColumn:(unsigned)_x count:(unsigned *)_count;
363 - (unsigned *)indicesInRow:(unsigned)_y count:(unsigned *)_count;
367 @implementation WETableCalcMatrixPositionArray
370 if (self->positions) free(self->positions);
374 - (void)checkForDuplicates {
377 for (j = 0; j < self->count; j++) {
380 for (i = 0; i < j; i++) {
381 NSAssert4(!((self->positions[j].x) == self->positions[i].x &&
382 (self->positions[j].y) == self->positions[i].y),
383 @"duplicate coordinate at %d and %d: %d/%d !",
384 j, i, self->positions[j].x, self->positions[j].y);
389 - (void)addPosition:(unsigned)_x:(unsigned)_y {
390 if (self->positions == NULL) {
391 self->positions = calloc(1, sizeof(MatrixCoord));
392 self->positions[0].x = _x;
393 self->positions[0].y = _y;
397 unsigned oldCount = self->count;
400 tmp = self->positions;
401 self->positions = calloc(oldCount + 1, sizeof(MatrixCoord));
402 memcpy(self->positions, tmp, (oldCount * sizeof(MatrixCoord)));
404 self->positions[oldCount].x = _x;
405 self->positions[oldCount].y = _y;
410 - (unsigned *)indicesIn:(WEOrientation)o index:(unsigned)_idx
411 count:(unsigned *)_count
413 unsigned i, rowCount;
417 for (i = 0, rowCount = 0; i < self->count; i++) {
420 j = (o == WEColumn) ? self->positions[i].x : self->positions[i].y;
428 pos = calloc(rowCount, sizeof(unsigned));
431 for (i = 0, p = pos; i < self->count; i++) {
434 j = (o == WEColumn) ? self->positions[i].x : self->positions[i].y;
438 ? self->positions[i].y
439 : self->positions[i].x;
446 - (unsigned *)indicesInRow:(unsigned)_y count:(unsigned *)_count {
447 return [self indicesIn:WERow index:_y count:_count];
449 - (unsigned *)indicesInColumn:(unsigned)_x count:(unsigned *)_count {
450 return [self indicesIn:WEColumn index:_x count:_count];
453 - (NSString *)description {
454 return [NSString stringWithFormat:@"<%08X[%@]: count=%d>",
455 self, NSStringFromClass([self class]),
459 @end /* WETableCalcMatrixPositionArray */
461 @implementation WETableCalcMatrix
467 static inline MatrixEntry *entryAt(WETableCalcMatrix *self, unsigned x,
469 return self->matrix +
470 (x * self->height * sizeof(MatrixEntry)) +
471 (y * sizeof(MatrixEntry));
474 - (id)initWithSize:(unsigned)_width:(unsigned)_height {
475 if (_width == 0 || _height == 0) {
476 [self logWithFormat:@"ERROR: specified invalid matrix dimensions: %ix%i",
482 NSAssert(_width > 0 && _height > 0, @"invalid args ..");
483 self->width = _width;
484 self->height = _height;
485 self->matrix = (void *)calloc(_width * _height, sizeof(MatrixEntry));
486 memset(self->matrix, 0, _width * _height * sizeof(MatrixEntry));
488 self->objToPos = NSCreateMapTable(NSNonOwnedPointerMapKeyCallBacks,
489 NSObjectMapValueCallBacks,
495 [self removeAllObjects];
498 NSFreeMapTable(self->objToPos);
515 - (void)setDelegate:(id)_delegate {
516 self->delegate = _delegate;
519 [_delegate respondsToSelector:
520 @selector(tableCalcMatrix:shouldProcessColumn:forObject:)];
522 [_delegate respondsToSelector:
523 @selector(tableCalcMatrix:shouldProcessRow:forObject:)];
526 return self->delegate;
529 /* clearing the structure */
531 - (void)removeAllObjects {
534 if (self->objToPos) {
535 NSResetMapTable(self->objToPos);
536 self->objToPos = NULL;
539 if (self->matrix == NULL)
542 for (y = 0; y < self->height; y++) {
543 for (x = 0; x < self->width; x++) {
546 e = entryAt(self, x, y);
551 [e->items release]; e->items = nil;
558 - (BOOL)object:(id)_obj possibleInRow:(unsigned)_y {
559 /* optimization method, can always return 'YES' */
560 if (self->rowCheck) {
561 return [self->delegate tableCalcMatrix:self
568 - (BOOL)object:(id)_obj possibleInColumn:(unsigned)_x {
569 /* optimization method, can always return 'YES' */
570 if (self->columnCheck) {
571 return [self->delegate tableCalcMatrix:self
572 shouldProcessColumn:_x
578 - (BOOL)object:(id)_obj matchesCellAt:(unsigned)_x:(unsigned)_y {
579 return [self->delegate tableCalcMatrix:self
580 shouldPlaceObject:_obj
584 /* adding object to structure */
586 - (void)addObject:(id)_obj toCellAt:(unsigned)_x:(unsigned)_y {
587 WETableCalcMatrixPositionArray *positions;
590 if ((positions = NSMapGet(self->objToPos, _obj)) == nil) {
591 positions = [[WETableCalcMatrixPositionArray alloc] init];
592 NSMapInsert(self->objToPos, _obj, positions);
596 [positions checkForDuplicates];
598 e = entryAt(self, _x, _y);
601 e->items = [[NSMutableArray alloc] init];
603 [e->items addObject:_obj];
605 [positions checkForDuplicates];
606 [positions addPosition:_x:_y];
607 [positions checkForDuplicates];
610 /* placing objects */
612 - (void)placeObject:(id)_object {
615 if (NSMapGet(self->objToPos, _object)) {
616 //NSLog(@"already placed object %@ !", _object);
620 if (self->rowCheck) {
621 for (y = 0; y < self->height; y++) {
622 if (![self object:_object possibleInRow:y])
625 for (x = 0; x < self->width; x++) {
626 if ([self object:_object matchesCellAt:x:y]) {
627 /* add to cell x:y */
628 [self addObject:_object toCellAt:x:y];
634 for (x = 0; x < self->width; x++) {
635 if (![self object:_object possibleInColumn:x])
638 for (y = 0; y < self->height; y++) {
639 if ([self object:_object matchesCellAt:x:y]) {
640 /* add to cell x:y */
641 [self addObject:_object toCellAt:x:y];
648 - (void)placeObjects:(NSArray *)_objects {
651 if ((oc = [_objects count]) == 0)
654 for (i = 0; i < oc; i++)
655 [self placeObject:[_objects objectAtIndex:i]];
660 - (NSArray *)objectsInColumn:(unsigned)_x {
665 set = [[NSMutableSet alloc] init];
667 for (y = 0; y < self->height; y++) {
670 e = entryAt(self, _x, y);
672 [set addObjectsFromArray:e->items];
674 result = [set allObjects];
678 - (NSArray *)objectsInRow:(unsigned)_y {
683 set = [[NSMutableSet alloc] init];
685 for (x = 0; x < self->width; x++) {
688 e = entryAt(self, x, _y);
690 [set addObjectsFromArray:e->items];
692 result = [set allObjects];
697 - (NSArray *)spansOfColumn:(unsigned)_x {
698 WETableCalcMatrixStripe *stripe;
699 NSEnumerator *objects;
702 stripe = [[WETableCalcMatrixStripe alloc]
703 initWithSize:self->height
705 delegate:self->delegate];
706 stripe = [stripe autorelease];
708 objects = [[self objectsInColumn:_x] objectEnumerator];
709 while ((object = [objects nextObject]) != nil) {
710 WETableCalcMatrixPositionArray *pos;
714 pos = NSMapGet(self->objToPos, object);
715 [pos checkForDuplicates];
717 indices = [pos indicesInColumn:_x count:&idxCount];
718 NSAssert(indices, @"available in column, but no indices ?");
720 [stripe addObject:object atPositions:indices count:idxCount];
723 return [stripe threadSpans];
725 - (NSArray *)spansOfRow:(unsigned)_y {
726 WETableCalcMatrixStripe *stripe;
727 NSEnumerator *objects;
730 stripe = [[WETableCalcMatrixStripe alloc]
731 initWithSize:self->width
733 delegate:self->delegate];
734 stripe = [stripe autorelease];
736 objects = [[self objectsInRow:_y] objectEnumerator];
737 while ((object = [objects nextObject])) {
738 WETableCalcMatrixPositionArray *pos;
742 pos = NSMapGet(self->objToPos, object);
743 [pos checkForDuplicates];
745 indices = [pos indicesInRow:_y count:&idxCount];
746 NSAssert(indices, @"available in column, but no indices ?");
748 [stripe addObject:object atPositions:indices count:idxCount];
751 return [stripe threadSpans];
754 - (NSArray *)columnSpans {
755 id objs[self->width];
758 for (i = 0; i < self->width; i++) {
759 objs[i] = [self spansOfColumn:i];
760 if (objs[i] == nil) objs[i] = [NSArray array];
762 return [NSArray arrayWithObjects:objs count:self->width];
764 - (NSArray *)rowSpans {
765 id objs[self->height];
768 for (i = 0; i < self->height; i++) {
769 objs[i] = [self spansOfRow:i];
770 if (objs[i] == nil) objs[i] = [NSArray array];
772 return [NSArray arrayWithObjects:objs count:self->height];
777 - (unsigned)widthOfColumn:(unsigned)_x {
781 for (y = 0, count = 0; y < self->height; y++) {
784 e = entryAt(self, _x, y);
785 if ([e->items count] > count)
786 count = [e->items count];
791 - (unsigned)countOfColumn:(unsigned)_x {
792 return [[self objectsInColumn:_x] count];
795 @end /* WETableCalcMatrix */