1/* 2 Copyright (C) 2000-2005 SKYRIX Software AG 3 4 This file is part of SOPE. 5 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 9 later version. 10 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. 15 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 19 02111-1307, USA. 20*/ 21 22#include "WETableCalcMatrix.h" 23#include "common.h" 24#include <string.h> 25 26typedef struct { 27 NSMutableArray *items; 28} MatrixEntry; 29 30typedef struct { 31 unsigned x; 32 unsigned y; 33} MatrixCoord; 34 35typedef struct { 36 id *objects; 37} MatrixThread; 38 39typedef enum { WERow, WEColumn } WEOrientation; 40 41static NSNull *null = nil; 42 43@implementation WETableCalcMatrixSpan 44 45+ (id)spanWithObject:(id)_obj range:(NSRange *)_range { 46 id span; 47 span = [[WETableCalcMatrixSpan alloc] initWithObject:_obj range:_range]; 48 return [span autorelease]; 49} 50- (id)initWithObject:(id)_obj range:(NSRange *)_range { 51 self->object = [_obj retain]; 52 self->range = *_range; 53 return self; 54} 55- (void)dealloc { 56 [self->object release]; 57 [super dealloc]; 58} 59 60/* accessors */ 61 62- (id)object { 63 return self->object; 64} 65- (NSRange)range { 66 return self->range; 67} 68 69/* calculations */ 70 71- (BOOL)startsAtIndex:(unsigned)_idx { 72 return (_idx == self->range.location) ? YES : NO; 73} 74- (BOOL)occupiesIndex:(unsigned)_idx { 75 if (_idx < self->range.location) 76 return NO; 77 if (_idx >= (self->range.location + self->range.length)) 78 return NO; 79 return YES; 80} 81- (unsigned)size { 82 return self->range.length; 83} 84 85/* description */ 86 87- (NSString *)description { 88 return [NSString stringWithFormat: 89 @"<0x%p[%@]: object=0x%p start=%d len=%d>", 90 self, NSStringFromClass([self class]), 91 [self object], 92 (int)self->range.location, 93 (int)self->range.length]; 94} 95 96@end /* WETableCalcMatrixSpan */ 97 98@interface WETableCalcMatrixStripe : NSObject 99{ 100@private 101 unsigned size; 102 MatrixThread *threads; 103 short threadCount; 104 WETableCalcMatrix *matrix; /* non-retained */ 105 id delegate; /* non-retained */ 106} 107 108- (unsigned)threadCount; 109- (NSArray *)threads; 110- (NSArray *)threadSpans; 111 112/* modification */ 113 114- (void)addObject:(id)_obj atPositions:(unsigned *)_pos count:(unsigned)_c; 115 116@end 117 118@implementation WETableCalcMatrixStripe 119 120+ (void)initialize { 121 if (null == nil) null = [[NSNull null] retain]; 122} 123 124- (id)initWithSize:(unsigned)_h 125 matrix:(WETableCalcMatrix *)_matrix 126 delegate:(id)_delegate 127{ 128 self->size = _h; 129 self->matrix = _matrix; 130 131 if ([_delegate respondsToSelector: 132 @selector(tableCalcMatrix:spanForObject:range:)]) 133 self->delegate = _delegate; 134 135 return self; 136} 137- (void)dealloc { 138 if (self->threads) { 139 unsigned i; 140 141 for (i = 0; i < (unsigned)self->threadCount; i++) { 142 if (self->threads[i].objects) { 143 unsigned j; 144 145 for (j = 0; j < self->size; j++) 146 [self->threads[i].objects[j] release]; 147 free(self->threads[i].objects); 148 } 149 } 150 free(self->threads); 151 } 152 [super dealloc]; 153} 154 155/* accessors */ 156 157- (unsigned)threadCount { 158 return self->threadCount; 159} 160 161- (NSArray *)threadAtIndex:(unsigned)_idx { 162 id *objs; 163 unsigned i; 164 NSArray *result; 165 166 objs = calloc(self->size, sizeof(id)); 167 NSAssert(objs, @"could not allocate memory .."); 168 NSAssert(self->size > 0, @"invalid size .."); 169 170 for (i = 0; i < self->size; i++) { 171 objs[i] = self->threads[_idx].objects[i]; 172 173 if (objs[i] == nil) 174 objs[i] = null; 175 } 176 result = [NSArray arrayWithObjects:objs count:self->size]; 177 free(objs); 178 return result; 179} 180- (NSArray *)spansAtIndex:(unsigned)_idx { 181 id *spans; 182 unsigned i, spanCount; 183 NSArray *result; 184 185 spans = calloc(self->size, sizeof(id)); 186 187 for (i = 0, spanCount = 0; i < self->size; ) { 188 WETableCalcMatrixSpan *span; 189 id obj; 190 NSRange r; 191 192 span = nil; 193 obj = self->threads[_idx].objects[i]; 194 195 if ((i + 1) == self->size) { 196 /* last entry */ 197 r.location = i; 198 r.length = 1; 199 i++; 200 } 201 else { 202 /* look ahead for similar entries */ 203 unsigned j; 204 205 r.location = i; 206 r.length = 0; 207 208 for (j = i + 1; j < self->size; j++) { 209 id nextObj; 210 211 nextObj = self->threads[_idx].objects[j]; 212 if (nextObj != obj) 213 break; 214 } 215 r.length = (j - i); 216 217 /* continue at end of this object */ 218 i = j; 219 } 220 221 span = nil; 222 if (self->delegate) { 223 span = [self->delegate tableCalcMatrix:self->matrix 224 spanForObject:obj 225 range:r]; 226 } 227 if (span == nil) { 228 span = [[WETableCalcMatrixSpan alloc] initWithObject:obj range:&r]; 229 AUTORELEASE(span); 230 } 231 232 spans[spanCount] = span; 233 spanCount++; 234 } 235 result = [NSArray arrayWithObjects:spans count:spanCount]; 236 free(spans); 237 return result; 238} 239 240- (NSArray *)threads { 241 if (self->threadCount == 0) 242 return nil; 243 if (self->threadCount == 1) 244 return [NSArray arrayWithObject:[self threadAtIndex:0]]; 245 246 { 247 id threadArrays[self->threadCount]; 248 unsigned i; 249 250 for (i = 0; i < (unsigned)self->threadCount; i++) 251 threadArrays[i] = [self threadAtIndex:i]; 252 253 return [NSArray arrayWithObjects:threadArrays count:self->threadCount]; 254 } 255} 256- (NSArray *)threadSpans { 257 if (self->threadCount == 0) 258 return nil; 259 else if (self->threadCount == 1) 260 return [NSArray arrayWithObject:[self spansAtIndex:0]]; 261 else { 262 NSArray *threadArrays[self->threadCount]; 263 unsigned i; 264 265 for (i = 0; i < (unsigned)self->threadCount; i++) { 266 threadArrays[i] = [self spansAtIndex:i]; 267 } 268 269 return [NSArray arrayWithObjects:threadArrays count:self->threadCount]; 270 } 271} 272 273/* addition */ 274 275- (unsigned)threadForPositions:(unsigned *)_pos count:(unsigned)_c { 276 unsigned i; 277 void *tmp; 278 279 if (self->threadCount == 0) { 280 self->threads = calloc(1, sizeof(MatrixThread)); 281 self->threads[0].objects = calloc(self->size, sizeof(id)); 282 self->threadCount = 1; 283 return 0; 284 } 285 286 /* check each column */ 287 for (i = 0; i < (unsigned)self->threadCount; i++) { 288 unsigned j; 289 MatrixThread *column; 290 BOOL ok; 291 292 column = &(self->threads[i]); 293 294 /* check each required position in column */ 295 for (j = 0, ok = YES; j < _c; j++) { 296 unsigned requiredPos; 297 298 requiredPos = _pos[j]; 299 NSAssert(requiredPos < self->size, @"index to high .."); 300 301 if (column->objects[requiredPos] != nil) { 302 /* position already assigned */ 303 ok = NO; 304 break; 305 } 306 } 307 if (ok) { 308 /* all required position available, return column */ 309 return i; 310 } 311 /* check next column */ 312 } 313 314 /* all available threads are full, make new one .. */ 315 tmp = self->threads; 316 self->threads = calloc(self->threadCount + 1, sizeof(MatrixThread)); 317 memcpy(self->threads, tmp, self->threadCount * sizeof(MatrixThread)); 318 self->threads[self->threadCount].objects = calloc(self->size, sizeof(id)); 319 self->threadCount++; 320 return (self->threadCount - 1); 321} 322 323- (void)addObject:(id)_obj atPositions:(unsigned *)_pos count:(unsigned)_c { 324 unsigned thread; 325 unsigned i; 326 327 if (_c == 0) return; 328 329 /* find row */ 330 thread = [self threadForPositions:_pos count:_c]; 331 NSAssert(thread < (unsigned)self->threadCount, @"invalid idx"); 332 333 /* place object */ 334 for (i = 0; i < _c; i++) { 335 unsigned requiredIdx; 336 337 requiredIdx = _pos[i]; 338 339#if DEBUG 340 NSAssert(requiredIdx < self->size, @"index to high .."); 341 NSAssert3(self->threads[thread].objects[requiredIdx] == nil, 342 @"index %i is already marked (by=0x%p, my=0x%p) !", 343 requiredIdx, self->threads[thread].objects[requiredIdx], _obj); 344#endif 345 346 self->threads[thread].objects[requiredIdx] = RETAIN(_obj); 347 } 348} 349 350@end 351 352@interface WETableCalcMatrixPositionArray : NSObject 353{ /* mutable array of matrix coordinates */ 354@private 355 unsigned count; 356 MatrixCoord *positions; 357} 358 359- (void)addPosition:(unsigned)_x :(unsigned)_y; 360- (void)checkForDuplicates; 361 362/* narrow set to row or column */ 363- (unsigned *)indicesInColumn:(unsigned)_x count:(unsigned *)_count; 364- (unsigned *)indicesInRow:(unsigned)_y count:(unsigned *)_count; 365 366@end 367 368@implementation WETableCalcMatrixPositionArray 369 370- (void)dealloc { 371 if (self->positions) free(self->positions); 372 [super dealloc]; 373} 374 375- (void)checkForDuplicates { 376 unsigned j; 377 378 for (j = 0; j < self->count; j++) { 379 unsigned i; 380 381 for (i = 0; i < j; i++) { 382 NSAssert4(!((self->positions[j].x) == self->positions[i].x && 383 (self->positions[j].y) == self->positions[i].y), 384 @"duplicate coordinate at %d and %d: %d/%d !", 385 j, i, self->positions[j].x, self->positions[j].y); 386 } 387 } 388} 389 390- (void)addPosition:(unsigned)_x :(unsigned)_y { 391 if (self->positions == NULL) { 392 self->positions = calloc(1, sizeof(MatrixCoord)); 393 self->positions[0].x = _x; 394 self->positions[0].y = _y; 395 self->count = 1; 396 } 397 else { 398 unsigned oldCount = self->count; 399 void *tmp; 400 401 tmp = self->positions; 402 self->positions = calloc(oldCount + 1, sizeof(MatrixCoord)); 403 memcpy(self->positions, tmp, (oldCount * sizeof(MatrixCoord))); 404 405 self->positions[oldCount].x = _x; 406 self->positions[oldCount].y = _y; 407 self->count++; 408 } 409} 410 411- (unsigned *)indicesIn:(WEOrientation)o index:(unsigned)_idx 412 count:(unsigned *)_count 413{ 414 unsigned i, rowCount; 415 unsigned *pos, *p; 416 417 /* first count */ 418 for (i = 0, rowCount = 0; i < self->count; i++) { 419 unsigned j; 420 421 j = (o == WEColumn) ? self->positions[i].x : self->positions[i].y; 422 if (j == _idx) 423 rowCount++; 424 } 425 if (rowCount == 0) 426 return NULL; 427 428 /* then copy */ 429 pos = calloc(rowCount, sizeof(unsigned)); 430 *_count = rowCount; 431 432 for (i = 0, p = pos; i < self->count; i++) { 433 unsigned j; 434 435 j = (o == WEColumn) ? self->positions[i].x : self->positions[i].y; 436 437 if (j == _idx) { 438 *p = (o == WEColumn) 439 ? self->positions[i].y 440 : self->positions[i].x; 441 p++; 442 } 443 } 444 return pos; 445} 446 447- (unsigned *)indicesInRow:(unsigned)_y count:(unsigned *)_count { 448 return [self indicesIn:WERow index:_y count:_count]; 449} 450- (unsigned *)indicesInColumn:(unsigned)_x count:(unsigned *)_count { 451 return [self indicesIn:WEColumn index:_x count:_count]; 452} 453 454- (NSString *)description { 455 return [NSString stringWithFormat:@"<%p[%@]: count=%d>", 456 self, NSStringFromClass([self class]), 457 self->count]; 458} 459 460@end /* WETableCalcMatrixPositionArray */ 461 462@implementation WETableCalcMatrix 463 464static inline MatrixEntry *entryAt(WETableCalcMatrix *self, unsigned x, 465 unsigned y) { 466 return self->matrix + 467 (x * self->height * sizeof(MatrixEntry)) + 468 (y * sizeof(MatrixEntry)); 469} 470 471- (id)initWithSize:(unsigned)_width :(unsigned)_height { 472 if (_width == 0 || _height == 0) { 473 [self logWithFormat:@"ERROR: specified invalid matrix dimensions: %ix%i", 474 _width, _height]; 475 [self release]; 476 return nil; 477 } 478 479 NSAssert(_width > 0 && _height > 0, @"invalid args .."); 480 self->width = _width; 481 self->height = _height; 482 self->matrix = (void *)calloc(_width * _height, sizeof(MatrixEntry)); 483 memset(self->matrix, 0, _width * _height * sizeof(MatrixEntry)); 484 485 self->objToPos = NSCreateMapTable(NSNonOwnedPointerMapKeyCallBacks, 486 NSObjectMapValueCallBacks, 487 64); 488 489 return self; 490} 491- (void)dealloc { 492 [self removeAllObjects]; 493 494 if (self->objToPos) 495 NSFreeMapTable(self->objToPos); 496 497 if (self->matrix) 498 free(self->matrix); 499 500 [super dealloc]; 501} 502 503/* accessors */ 504 505- (unsigned)width { 506 return self->width; 507} 508- (unsigned)height { 509 return self->height; 510} 511 512- (void)setDelegate:(id)_delegate { 513 self->delegate = _delegate; 514 515 self->columnCheck = 516 [_delegate respondsToSelector: 517 @selector(tableCalcMatrix:shouldProcessColumn:forObject:)]; 518 self->rowCheck = 519 [_delegate respondsToSelector: 520 @selector(tableCalcMatrix:shouldProcessRow:forObject:)]; 521} 522- (id)delegate { 523 return self->delegate; 524} 525 526/* clearing the structure */ 527 528- (void)removeAllObjects { 529 unsigned y, x; 530 531 if (self->objToPos) { 532 NSResetMapTable(self->objToPos); 533 self->objToPos = NULL; 534 } 535 536 if (self->matrix == NULL) 537 return; 538 539 for (y = 0; y < self->height; y++) { 540 for (x = 0; x < self->width; x++) { 541 MatrixEntry *e; 542 543 e = entryAt(self, x, y); 544 545 if (e->items == nil) 546 continue; 547 548 [e->items release]; e->items = nil; 549 } 550 } 551} 552 553/* queries */ 554 555- (BOOL)object:(id)_obj possibleInRow:(unsigned)_y { 556 /* optimization method, can always return 'YES' */ 557 if (self->rowCheck) { 558 return [self->delegate tableCalcMatrix:self 559 shouldProcessRow:_y 560 forObject:_obj]; 561 } 562 return YES; 563} 564 565- (BOOL)object:(id)_obj possibleInColumn:(unsigned)_x { 566 /* optimization method, can always return 'YES' */ 567 if (self->columnCheck) { 568 return [self->delegate tableCalcMatrix:self 569 shouldProcessColumn:_x 570 forObject:_obj]; 571 } 572 return YES; 573} 574 575- (BOOL)object:(id)_obj matchesCellAt:(unsigned)_x :(unsigned)_y { 576 return [self->delegate tableCalcMatrix:self 577 shouldPlaceObject:_obj 578 atPosition:_x:_y]; 579} 580 581/* adding object to structure */ 582 583- (void)addObject:(id)_obj toCellAt:(unsigned)_x :(unsigned)_y { 584 WETableCalcMatrixPositionArray *positions; 585 MatrixEntry *e; 586 587 if ((positions = NSMapGet(self->objToPos, _obj)) == nil) { 588 positions = [[WETableCalcMatrixPositionArray alloc] init]; 589 NSMapInsert(self->objToPos, _obj, positions); 590 RELEASE(positions); 591 } 592 593 [positions checkForDuplicates]; 594 595 e = entryAt(self, _x, _y); 596 597 if (e->items == nil) 598 e->items = [[NSMutableArray alloc] init]; 599 600 [e->items addObject:_obj]; 601 602 [positions checkForDuplicates]; 603 [positions addPosition:_x:_y]; 604 [positions checkForDuplicates]; 605} 606 607/* placing objects */ 608 609- (void)placeObject:(id)_object { 610 unsigned y, x; 611 612 if (NSMapGet(self->objToPos, _object)) { 613 //NSLog(@"already placed object %@ !", _object); 614 return; 615 } 616 617 if (self->rowCheck) { 618 for (y = 0; y < self->height; y++) { 619 if (![self object:_object possibleInRow:y]) 620 continue; 621 622 for (x = 0; x < self->width; x++) { 623 if ([self object:_object matchesCellAt:x:y]) { 624 /* add to cell x:y */ 625 [self addObject:_object toCellAt:x:y]; 626 } 627 } 628 } 629 } 630 else { 631 for (x = 0; x < self->width; x++) { 632 if (![self object:_object possibleInColumn:x]) 633 continue; 634 635 for (y = 0; y < self->height; y++) { 636 if ([self object:_object matchesCellAt:x:y]) { 637 /* add to cell x:y */ 638 [self addObject:_object toCellAt:x:y]; 639 } 640 } 641 } 642 } 643} 644 645- (void)placeObjects:(NSArray *)_objects { 646 unsigned oc, i; 647 648 if ((oc = [_objects count]) == 0) 649 return; 650 651 for (i = 0; i < oc; i++) 652 [self placeObject:[_objects objectAtIndex:i]]; 653} 654 655/* formatting */ 656 657- (NSArray *)objectsInColumn:(unsigned)_x { 658 unsigned y; 659 NSMutableSet *set; 660 NSArray *result; 661 662 set = [[NSMutableSet alloc] init]; 663 664 for (y = 0; y < self->height; y++) { 665 MatrixEntry *e; 666 667 e = entryAt(self, _x, y); 668 if (e->items) 669 [set addObjectsFromArray:e->items]; 670 } 671 result = [set allObjects]; 672 RELEASE(set); 673 return result; 674} 675- (NSArray *)objectsInRow:(unsigned)_y { 676 unsigned x; 677 NSMutableSet *set; 678 NSArray *result; 679 680 set = [[NSMutableSet alloc] init]; 681 682 for (x = 0; x < self->width; x++) { 683 MatrixEntry *e; 684 685 e = entryAt(self, x, _y); 686 if (e->items) 687 [set addObjectsFromArray:e->items]; 688 } 689 result = [set allObjects]; 690 RELEASE(set); 691 return result; 692} 693 694- (NSArray *)spansOfColumn:(unsigned)_x { 695 WETableCalcMatrixStripe *stripe; 696 NSEnumerator *objects; 697 id object; 698 699 stripe = [[WETableCalcMatrixStripe alloc] 700 initWithSize:self->height 701 matrix:self 702 delegate:self->delegate]; 703 stripe = [stripe autorelease]; 704 705 objects = [[self objectsInColumn:_x] objectEnumerator]; 706 while ((object = [objects nextObject]) != nil) { 707 WETableCalcMatrixPositionArray *pos; 708 unsigned *indices; 709 unsigned idxCount; 710 711 pos = NSMapGet(self->objToPos, object); 712 [pos checkForDuplicates]; 713 714 indices = [pos indicesInColumn:_x count:&idxCount]; 715 NSAssert(indices, @"available in column, but no indices ?"); 716 717 [stripe addObject:object atPositions:indices count:idxCount]; 718 } 719 720 return [stripe threadSpans]; 721} 722- (NSArray *)spansOfRow:(unsigned)_y { 723 WETableCalcMatrixStripe *stripe; 724 NSEnumerator *objects; 725 id object; 726 727 stripe = [[WETableCalcMatrixStripe alloc] 728 initWithSize:self->width 729 matrix:self 730 delegate:self->delegate]; 731 stripe = [stripe autorelease]; 732 733 objects = [[self objectsInRow:_y] objectEnumerator]; 734 while ((object = [objects nextObject])) { 735 WETableCalcMatrixPositionArray *pos; 736 unsigned *indices; 737 unsigned idxCount; 738 739 pos = NSMapGet(self->objToPos, object); 740 [pos checkForDuplicates]; 741 742 indices = [pos indicesInRow:_y count:&idxCount]; 743 NSAssert(indices, @"available in column, but no indices ?"); 744 745 [stripe addObject:object atPositions:indices count:idxCount]; 746 } 747 748 return [stripe threadSpans]; 749} 750 751- (NSArray *)columnSpans { 752 id objs[self->width]; 753 unsigned i; 754 755 for (i = 0; i < self->width; i++) { 756 objs[i] = [self spansOfColumn:i]; 757 if (objs[i] == nil) objs[i] = [NSArray array]; 758 } 759 return [NSArray arrayWithObjects:objs count:self->width]; 760} 761- (NSArray *)rowSpans { 762 id objs[self->height]; 763 unsigned i; 764 765 for (i = 0; i < self->height; i++) { 766 objs[i] = [self spansOfRow:i]; 767 if (objs[i] == nil) objs[i] = [NSArray array]; 768 } 769 return [NSArray arrayWithObjects:objs count:self->height]; 770} 771 772/* counting */ 773 774- (unsigned)widthOfColumn:(unsigned)_x { 775 unsigned y; 776 unsigned count; 777 778 for (y = 0, count = 0; y < self->height; y++) { 779 MatrixEntry *e; 780 781 e = entryAt(self, _x, y); 782 if ([e->items count] > count) 783 count = [e->items count]; 784 } 785 return count; 786} 787 788- (unsigned)countOfColumn:(unsigned)_x { 789 return [[self objectsInColumn:_x] count]; 790} 791 792@end /* WETableCalcMatrix */ 793