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