
// This object tracks the dirty rectangle of the frame buffer.
// If two rects overlap, they are coalesced.  If they don't
// overlap, they are kept separate.  This way, when a redraw
// is done, we have two flushes that are small rather than one
// large flush.  (The large flush would draw *lots* of unnecessary
// pixels!)

#import <gamekit/gamekit.h>

#import <appkit/appkit.h>
#import <dpsclient/dpsNeXT.h>
#import <stdio.h>
#import <math.h>
#import <sys/param.h>  // MAX()  MIN()  macros

@interface DirtPile(private)
- _coalesce;
@end

// It might be faster to call NXRectClipList() and then
// composite the whole buffer.  I'll have to test this. *****
// leaving this undefined flushes each rect explicitly
// Note that this only changes the default; you can set it
// yourself via the -setManyFlushes: method.
// #define DIRTPILE_USECLIPLIST // use the clipping

// function to coalesce two rectangles if they overlap.
// Returns NO if they don't, returns YES if they do and
// leaves the union rect in *r1.  I suppose that I could
// have used NXIntersectsRect() and NXUnionRect(), but
// this is just as easy.  This should probably be inline. *****
BOOL coalesce(NXRect *r1, NXRect *r2, double percent)
{
	NXRect r3, r4; double overlap;
	
	// see if the two rects intersect.  If they don't, return NO.
	// Saving the overhead of a function call to NXIntersectsRect()...
	if (((NX_X(r1) + NX_WIDTH(r1)) < NX_X(r2)) ||
		((NX_X(r2) + NX_WIDTH(r2)) < NX_X(r1)) ||
		((NX_Y(r1) + NX_HEIGHT(r1)) < NX_Y(r2)) ||
		((NX_Y(r2) + NX_HEIGHT(r2)) < NX_Y(r1))) return NO;
	
	// take the union of the rects; the new, larger rect is in r3
	NX_X(&r3) = MIN(NX_X(r1), NX_X(r2));
	NX_Y(&r3) = MIN(NX_Y(r1), NX_Y(r2));
	NX_WIDTH(&r3) = MAX(NX_MAXX(r1), NX_MAXX(r2)) - NX_X(&r3);
	NX_HEIGHT(&r3) = MAX(NX_MAXY(r1), NX_MAXY(r2)) - NX_Y(&r3);

	// get the inersection of the rects in r4
	NX_X(&r4) = MAX(NX_X(r1), NX_X(r2));
	NX_Y(&r4) = MAX(NX_Y(r1), NX_Y(r2));
	NX_WIDTH(&r4) = MIN(NX_MAXX(r1), NX_MAXX(r2)) - NX_X(&r4);
	NX_HEIGHT(&r4) = MIN(NX_MAXY(r1), NX_MAXY(r2)) - NX_Y(&r4);

	// how much overlap??  If not enough overlap, don't coalesce
	// this amounts to %of redraw == dirty area / coalesced area;
	// if we will end up adding too much undirty area, we won't coalesce
	// dirty area = dirty area 1 + dirty area 2 - union area of 1&2
	// (subtract union area so it isn't counted twice)
	// for speed we could ignore the union area, in which case the
	// percent param ranges from (.50 == always) to (2.0 == never)
	overlap = (((NX_WIDTH(r1) * NX_HEIGHT(r1)) +
				(NX_WIDTH(r2) * NX_HEIGHT(r2))) -
				(NX_WIDTH(&r4) * NX_HEIGHT(&r4))) /
				(NX_WIDTH(&r3) * NX_HEIGHT(&r3));
	if (overlap < percent) return NO;
	*r1 = r3;
	return YES;	// tell them we coalesced it.
}


@implementation DirtPile

- init		// initialize the instance
{
	[super init];
	// reset instance variables.
	maxRects = MAX_RECTS;
	numRects = 0; allDirty = NO;
	coalesceFrequency = MAXINT; // only do it on a flush
	rectsAdded = 0;
#ifdef DIRTPILE_USECLIPLIST	// define it or not to change the default
	manyFlushes = NO;
	percentOverlap = 0.95;	// almost never coalesce overlapping rects
							// since postscript will do this for us
#else
	manyFlushes = YES;
	percentOverlap = 0.5;	// always coalesce overlapping rects to
							// reduce the number of flushes we send
#endif
	return self;
}


- addRegion:(float)x :(float)y :(float)w :(float)h	// add a dirty rect
{
	register NXRect *r;
	if (allDirty) return self;
	// make sure we have enough room.  Complain if we don't.  (Shouldn't
	// ever get the printf(), though! )
	if (numRects >= maxRects) {
		fprintf(stderr, "Need more rects allocated in DirtPile!\n");
		return self;
	}
	
	// copy coords into the rect list
	r = &rectList[numRects];
	NX_X(r) = x; NX_Y(r) = y;
	NX_WIDTH(r) = w; NX_HEIGHT(r) = h;
	
	// update number of rects in list
	numRects++;
	
	// do a coalesce?
	if (++rectsAdded >= coalesceFrequency) {
		rectsAdded = 0;
		[self _coalesce];
	}
	return self;
}

- addRegion:(const NXRect *)rect	// add a dirty rect
{
	return [self addRegion:NX_X(rect) :NX_Y(rect)
		:NX_WIDTH(rect) :NX_HEIGHT(rect)];
}

- fullRedraw:sender :buffer	// assumed to be a view
{ // ***** inefficient; just use composite:toPoint and remove sender arg
	// (Of course, that change requires that the lockedView/buffer have a
	// proper clipping path set!)
	NXRect bounds = {{0.0, 0.0}, {0.0, 0.0}};
	
	[sender getBounds:&bounds];
	[buffer composite:NX_COPY fromRect:&bounds
			toPoint:&(bounds.origin)];
	numRects = 0; allDirty = NO; rectsAdded = 0;
	return self;
}

- _coalesce
{	// I need to come up with a faster way to do this; it
	// tends to be an n^3 algorithm!  *****
	register int i, j;
	BOOL changed = NO;
	register NXRect *r1, *r2;
	r1 = &rectList[0];	// unneeded; silences a compiler warning
	do {
		changed = NO;
		for (i=0; i<(numRects-1); i++) {
			r1 = &rectList[i];
			for (j=i+1; j<numRects; j++) {
				r2 = &rectList[j];
				if (coalesce(r1, r2, percentOverlap)) {
					changed = YES;
					numRects--;
					for (; j<numRects; j++) {
						*r2 = *(r2+1);
						r2++;
					}
				}
			}
		}
	} while (changed);
	return self;
}

// Flush dirty parts of the buffer to the currently focused view.
// The view should be in a retained window for this to actually
// work as it is supposed to do.
- doRedraw:buffer
{
	NXPoint zero = { 0.0, 0.0 };
	register int i;

	rectsAdded = 0;
	if (allDirty) {
		allDirty = NO;
		[buffer composite:NX_COPY toPoint:&zero];
	}
	
	// Leave if nothing here to flush.
	if (!numRects) return self;
	[self _coalesce];
	
	// flush dirty rects from buffer onto the screen
	if (!buffer) { // use internal color if no buffer
		NXSetColor(noBufferColor);
		NXRectFillList(rectList, numRects);
	} else {
		// do the buffer flush.  Two ways to do it:  clip and then
		// flush all, or flush each rect explicitly.
		if (manyFlushes) {
			for (i=0; i<numRects; i++) {
				[buffer composite:NX_COPY fromRect:&rectList[i]
						toPoint:&rectList[i].origin];
			}
		} else {
			NXRectClipList(rectList, numRects);
			[buffer composite:NX_COPY toPoint:&zero];
		}
	}
	// if using a buffered window instead of retained, you
	// need to flush the window here.
	// reset dirty list, since it's all clean now
	numRects = 0;
	return self;
}

- setAllDirty { numRects = 0; allDirty = YES; return self; }

- sendDirtTo:aDirtPile		// add all our dirty rects to aDirtPile
{
	register int i;
	if (!numRects) return self; // no work to do 'cause we're clean
	[self _coalesce]; // do this efficiently...
	for (i=0; i<numRects; i++) {
		[aDirtPile addRegion:&rectList[i]];
	}
	return self;
}

- setNoBufferColor:(NXColor)aColor // set color to draw if no buffer
{
	noBufferColor = aColor;
	return self;
}

- (double)percentDirtyForCoalesce { return percentOverlap; }
- setPercentDirtyForCoalesce:(double)val { percentOverlap = val; return self; }
- (int)coalesceFrequency { return coalesceFrequency; }
- setCoalesceFrequency:(int)val { coalesceFrequency = val; return self; }
- (BOOL)manyFlushes { return manyFlushes; }
- setManyFlushes:(BOOL)flag { manyFlushes = flag; return self; }

@end
