/* Talin's Region Manager */

/* ===================================================================== *
   Includes
 * ===================================================================== */

#include "std.h"
#include "rect.h"
#include "regions.h"

/* ===================================================================== *
   Internal classes
 * ===================================================================== */

    // Used for iterating through rectangles in a strip

class StripWalker {
public:

  RegionRect		*rect;
  int16			coord;
  int16			state;
  int16			final;

  StripWalker( RegionRect *list, int16 finalCoord );
  void nextCoord( int16 minCoord );
};

    // Used for iterating through strips in a region

class RegionWalker {
public:

  RegionStrip		*strip;
  int16			y;
  bool			nullStrip;
  int16			final;
  RegionStrip		tempStrip;
  RegionRect		tempRect;

  RegionWalker( const Region *reg, int16 yMin, int16 yMax );
  ~RegionWalker() { tempStrip.rectList = NULL; }
  void nextStrip( int16 minCoord );
};

/* ===================================================================== *
   RegionRect member functions
 * ===================================================================== */

RegionRect::RegionRect()
{
    next = NULL;
}

/* ===================================================================== *
   RegionStrip member functions
 * ===================================================================== */

RegionStrip::RegionStrip()
{
    next = NULL;
    rectList = lastRect = NULL;
}

RegionStrip::~RegionStrip()
{
    RegionRect		*rect;

	// Delete all strips in the region.

    while ((rect = rectList) != NULL)
    {
	rectList = rectList->next;
	delete( rect );
    }
}

bool RegionStrip::stripsEqual( RegionStrip &strip )
{
    RegionRect		*rect1,
			*rect2;

    for (rect1 = rectList, rect2 = strip.rectList;
	 rect1;
	 rect1 = rect1->next, rect2 = rect2->next )
    {
	if (rect2 == NULL
	    || rect1->x != rect2->x
	    || rect1->width != rect2->width)
	    return FALSE;
    }
    if (rect2) return FALSE;

    return TRUE;
}

    // Add a rectangle to a strip...

void RegionStrip::addRect( int16 xPos, int16 width )
{
    RegionRect		*rr;

	// If new rectangle overlaps the previous rectangle,
	// Then simply add to the width of that rectangle.

    if (lastRect)
    {
	if (xPos < lastRect->x)
	{
	    printf( "Strip integrity error.\n" );
	    exit( 0 );
	}

	if (xPos <= lastRect->x + lastRect->width)
	{
	    lastRect->width
		= max( lastRect->width, xPos + width - lastRect->x );
	    return;
	}
    }

	// Otherwise, allocate a new rectangle

    rr = new RegionRect;
    rr->x = xPos;
    rr->width = width;

    if (lastRect) lastRect->next = rr;
    else rectList = rr;

    lastRect = rr;
}

RegionStrip *RegionStrip::copy( int16 y, int16 h )
{
    RegionRect		*rect;
    RegionStrip		*newStrip;

    newStrip = new RegionStrip;
    if (newStrip == NULL) return NULL;

    newStrip->yPos = y;
    newStrip->height = h;

	// Walk the list of rectangles and make a copy of each one

    for (rect = rectList; rect; rect = rect->next )
    {
	RegionRect	*rr;

	rr = new RegionRect;
	rr->x = rect->x;
	rr->width = rect->width;

	if (newStrip->lastRect) newStrip->lastRect->next = rr;
	else newStrip->rectList = rr;

	newStrip->lastRect = rr;
    }

    return newStrip;
}

    // Return the left edge and width of entire strip.

void RegionStrip::stripExtent( int16 &leftEdge, int16 &width )
{
    if (lastRect == NULL)
    {
	leftEdge = 0;
	width = 0;
    }
    else
    {
	leftEdge = rectList->x;
	width = lastRect->x + lastRect->width - leftEdge;
    }
}

    // Do horiztonal boolean operation...
    // Note that this is a pipelined function, we don't store a rect
    // until the next rect changes

RegionStrip *RegionStrip::combine(
    Rect16		stripExtent,		// extent of strip
    RegionStrip		&strip,			// region strip to combine with
    int16		op )			// boolean operator
{
    int16		outState;		// output state: TRUE or FALSE
    int16		xPos = stripExtent.x,
			prevPos;		// previous output coord

	// last x position of strip
    int16		finalPos = xPos + stripExtent.width;

    RegionStrip		*newStrip;				// allocated strip structure

	// Two StripWalkers to keep track of where we are in the strips.
    StripWalker		sw1( rectList, finalPos ),
			sw2( strip.rectList, finalPos );

	// Allocate an output strip
    newStrip = new RegionStrip;
    newStrip->yPos = stripExtent.y;
    newStrip->height = stripExtent.height;

	// Initialize the last procesed position.
    prevPos = xPos;

	// While xPos is less than the final position.
    while (xPos < finalPos)
    {
	    // Choose the nearer of the two transitions, and insure
	    // that it does not go beyond the final position.
	xPos = min( sw1.coord, sw2.coord );
	if (xPos > finalPos) xPos = finalPos;

	    // Compute the output state as a boolean function.
	outState = evalOp( op, sw1.state, sw2.state );

	    // If the output state is TRUE, then emit a RegionRect
	    // to the new strip, with width equal to the distance
	    // between the current point and the previously processed
	    // point.
	if (outState && xPos > prevPos)
	    newStrip->addRect( prevPos, xPos - prevPos );

	    // Update the previous position to the newly written one.
	prevPos = xPos;

	    // Update both strips to beyond the last processed point.
	sw1.nextCoord( xPos );
	sw2.nextCoord( xPos );
    }

    if (newStrip->rectList == NULL)
    {
	delete( newStrip );
	return NULL;
    }

    return newStrip;
}

/* ===================================================================== *
   StripWalker member functions
 * ===================================================================== */

StripWalker::StripWalker( RegionRect *list, int16 finalCoord )
{
    final = finalCoord;
    rect = list;
    coord = rect ? rect->x : final;
    state = 0;
}

void StripWalker::nextCoord( int16 minCoord )
{
    if (rect == NULL)				// if past end of strip
    {
	coord = final;				// then set coord to xMax
	state = 0;				// set state to "between rects"
	return;
    }

    while (coord <= minCoord)
    {
	if (state)				// if within a rect
	{
	    state = 0;				// set state to "between rects"

	    rect = rect->next;			// skip to next rect
	    if (rect)
	    {
		coord = rect->x;		// set coord to rect start
	    }
	    else
            {
                coord = final;
		return;
            }
	}
	else					// else if between rects
	{
	    state = 1;				// set state to "within rect"
	    coord = rect->x + rect->width;	// set coord to rect end
	}
    }
}

/* ===================================================================== *
   RegionWalker member functions
 * ===================================================================== */

RegionWalker::RegionWalker( const Region *reg, int16 yMin, int16 yMax )
{
    final = yMax;

    if (reg->flags & Region::empty)
    {
	strip = NULL;
	nullStrip = 1;
	y = yMax;
	return;
    }

    if (reg->flags & Region::simpleRect)
    {
	tempStrip.next = NULL;
	tempStrip.yPos = reg->bounds.y;
	tempStrip.height = reg->bounds.height;
	tempStrip.rectList = tempStrip.lastRect = &tempRect;

	tempRect.x		= reg->bounds.x;
	tempRect.width	= reg->bounds.width;
	tempRect.next = NULL;
	
	strip = &tempStrip;
    }
    else
    {
	strip = reg->stripList;
    }

    if (strip->yPos > yMin)
    {
	nullStrip = 1;
	y = strip->yPos;
    }
    else
    {
	nullStrip = 0;
	y = strip->yPos + strip->height;
    }
}

void RegionWalker::nextStrip( int16 minCoord )
{
    while (strip && strip->yPos + strip->height <= minCoord)
    {
	strip = strip->next;
    }

    if (strip == NULL)
    {
	y = final;
	nullStrip = 1;
    }
    else if (strip->yPos > minCoord)
    {
	y = strip->yPos;
	nullStrip = 1;
    }
    else
    {
	y = strip->yPos + strip->height;
	nullStrip = (strip->rectList) ? 0 : 1;
    }
}

/* ===================================================================== *
   Region member functions
 * ===================================================================== */

		//	Constructor and destructor
Region::Region()
{
    flags = empty | simpleRect;
    stripList = NULL;
}

Region::~Region()
{
    clearRegion();
}

#if 0
Region::Region( Region &rgn, Point16 &pt )
{
    flags = rgn.flags;
    bounds = rgn.bounds + pt;

	// now duplicate & shift strips

    RegionStrip		*oldStrip = rgn.stripList,
			**newStrip = &stripList;

    stripList = NULL;

    while (oldStrip)
    {
	*newStrip = oldStrip->copy( oldStrip->yPos + pt.y, oldStrip->height);

	if (pt.x)
	{
		// Walk the list of rectangles and shift each one
	    for (RegionRect	*rect = (*newStrip)->rectList; rect; rect = rect->next )
	    {
		rect->x += pt.x;
	    }
	}
    }
}
#endif

void Region::extractRegion( Region &rgn )
{
    rgn.flags = flags;
    rgn.bounds = bounds;
    rgn.stripList = stripList;

    stripList = NULL;
    flags = empty | simpleRect;
}

void Region::clearRegion()
{
    RegionStrip		*strip;

	// Delete all strips in the region.

    while ((strip = stripList) != NULL)
    {
	stripList = stripList->next;
	delete( strip );
    }
    stripList = NULL;
    
    flags = empty | simpleRect;
}

    // Here's where all the real work is done. Another pipelined function,
    // meaning that we don't emit a strip until the succeeding strip is
    // finished.

void Region::boolOpRegion( const Region &rgn, int16 op )
{
    Rect16		r;
    int16		stripTop,				// previous output coord
			yPos,
			finalPos;				// last x position of strip
    RegionStrip		*firstStrip = NULL,
			*lastStrip = NULL;
    int16		xMin = maxint16,
			xMax = minint16;

	// Assume for a start that the new region's bounds are the
	// combined extent of both regions.
    r = ::bound( bounds, rgn.bounds );

    RegionWalker	rw1( this, r.y, r.y + r.height ),
			rw2( &rgn, r.y, r.y + r.height );

	// Compute the starting and ending points of the region walk
    yPos = stripTop = r.y;
    finalPos = yPos + r.height;

	// Loop through all the strips.
    while (yPos < finalPos)
    {
	    // Build a strip that represents the strip of pixels between
	    // the last processed scanline, and the nearest end-of-strip.
	    // Clip the y position to the bottom of the region bounds.
	yPos = min( rw1.y, rw2.y );
	if (yPos > finalPos) yPos = finalPos;

	    // If the strip we're making is of >0 height
	if (yPos > stripTop)
	{
	    RegionStrip	*newStrip;
	    int16	h = yPos - stripTop;

	    if (rw1.nullStrip)
	    {
		    // If the first strip is empty, check the OP
		    // to see whether to copy or ignore the other
		    // strip
		if (evalOp( op, 0, !rw2.nullStrip ))
		{
		    newStrip = rw2.strip->copy( stripTop, h );
		}
		else newStrip = NULL;
	    }
	    else if (rw2.nullStrip)
	    {
		    // If the second strip is empty, check the OP
		    // to see whether to copy or ignore the other
		    // strip
		if (evalOp( op, 1, 0 ))
		{
		    newStrip = rw1.strip->copy( stripTop, h );
		}
		else newStrip = NULL;
	    }
	    else
	    {
		    // Create a new strip by combining the old ones.
		newStrip = rw1.strip->combine(
		    Rect16( r.x, stripTop, r.width, h ),
		    *rw2.strip,
		    op );
	    }

	    if (newStrip)
	    {
		    // Check to see if the new strip is identical in form
		    // to the last one generated. If so, then fold it
		    // into the the previous strip.
		if ( lastStrip
		     &&	stripTop <= lastStrip->yPos + lastStrip->height
		     &&	lastStrip->stripsEqual( *newStrip ))
		{
		    lastStrip->height = yPos - lastStrip->yPos;
		    delete( newStrip );
		}
		else
		{
		    int16	leftEdge,
				width;

			// Get the extent of the strip, for later
		    newStrip->stripExtent( leftEdge, width );

		    xMin = min( leftEdge, xMin );
		    xMax = max( leftEdge + width, xMax );

			// Link the strip into the strip list
		    if (lastStrip) lastStrip->next = newStrip;
		    else firstStrip = newStrip;

		    lastStrip = newStrip;
		}
	    }
	}

	stripTop = yPos;

	rw1.nextStrip( yPos );
	rw2.nextStrip( yPos );
    }

	// delete old strips in destination region
    clearRegion();

    if (firstStrip == NULL)
    {
	    // If new region contains no strips
	bounds = r;
    }
    else if ( firstStrip == lastStrip
	      && firstStrip->rectList == firstStrip->lastRect)
    {
	    // If region only contains a single rectangle
	bounds.x = firstStrip->rectList->x;
	bounds.width = firstStrip->rectList->width;
	bounds.y = firstStrip->yPos;
	bounds.height = firstStrip->height;
	flags = simpleRect;
	delete( firstStrip );
    }
    else
    {
	bounds.x = xMin;
	bounds.y = firstStrip->yPos;
	bounds.width = xMax - xMin;
	bounds.height = lastStrip->yPos + lastStrip->height - firstStrip->yPos;
	
	stripList = firstStrip;
	flags = 0;
    }
}

void Region::boolOpRect( const Rect16 &r, int16 op )
{
    if (flags & empty)			// if region is empty
    {
	if (op & 2)			// check "empty" op rect
	{
	    bounds = r;			// set region to rectangle
	    flags = simpleRect;
	}
    }
    else
    {
	Region		tempReg;
	
	tempReg.bounds = r;
	tempReg.flags = simpleRect;
	
	boolOpRegion( tempReg, op );
    }
}

void Region::addRect( const Rect16 &r )
{
    boolOpRect( r, regOpOr );
}

void Region::addRegion( const Region &reg )
{
    boolOpRegion( reg, regOpOr );
}

void Region::subtractRect( const Rect16 &r )
{
    boolOpRect( r, regOpAndInverted );
}

void Region::subtractRegion( const Region &reg )
{
    boolOpRegion( reg, regOpAndInverted );
}

/* ===================================================================== *
   RegionIterator member functions
 * ===================================================================== */

RegionIterator::RegionIterator( const Region *reg, const Rect16 &search )
{
    region = reg;
    searchRect = search;
    rect = NULL;

    if (reg->flags & Region::simpleRect)
    {
	simpleFlag = TRUE;
	strip = NULL;
    }
    else
    {
	simpleFlag = FALSE;
	strip = reg->stripList;
    }
}

bool RegionIterator::next( Rect16 &clipRect )
{
    for (;;)
    {
	if (rect == NULL)
	{
	    if (strip == NULL)
	    {
		if (simpleFlag)
		{
		    clipRect = region->bounds;
		    simpleFlag = FALSE;
		    return TRUE;
		}
		else return FALSE;
	    }

	    rect = strip->rectList;
	    stripYPos = strip->yPos;
	    stripHeight = strip->height;
	    strip = strip->next;
	}
	else
	{
	    clipRect.x = rect->x;
	    clipRect.y = stripYPos;
	    clipRect.width = rect->width;
	    clipRect.height = stripHeight;

	    rect = rect->next;
	    
	    if (clipRect.overlap( searchRect )) break;
	}
    }

    return TRUE;
}

#if 0
	// Test code...

#include <dos.h>
#include <mem.h>
#include <malloc.h>
//#include <bios.h>

#include "input.h"
#include "vdraw.h"
#include "vsdraw.h"
#include "gpalette.h"
#include "pointer.h"

bool	appRunning;			// true while app is running

	//	Mouse Pointer

gDisplayPort		mainPort;
gMousePointer		pointer( mainPort );	// the actual pointer
gPen				mainPens[ cStdPenCount ],// the array of pens
					requesterPens[ cStdPenCount ];// the array of pens
gPaletteEntry penColors[ cStdPenCount ] = {	// the ideal pen colors
	0,0,0,									// black (transparent)
	0,0,0,									// black
	255,255,255,							// white

	139,139,139,							// dk. grey
	191,191,191,							// lt. grey
	 96, 96, 96,							// dk. grey

	191,191,191,							// lt. grey
	255,255,255,							// white
	139,139,139,							// dk. grey

	159,159,235,							// lt. blue
};

	//	A font for testing purposes

extern "C" {
extern gFont		agateFont;
};
gFont				*mainFont = &agateFont;	// main font (agate)

extern gPalette mainPalette;			// default color palette
extern gMappedImage	arrowPtr;

void cleanup();
void showRegion( Region &reg );

void main()
{
	Region			reg1,
					reg2;

	atexit( cleanup );

	initSVGAGraphics( mainPort );			// init graphics
	initPanels( mainPort );					// init panel controls

	mainPort.setFont( mainFont );

	pointer.hide();
	pointer.setImage( arrowPtr, 0, 0 );		// Set the mouse pointer image
	pointer.show();

	reg1.addRect( Rect16( 10, 10, 200, 100 ) );
	reg1.addRect( Rect16( 50, 60, 200, 100 ) );
	showRegion( reg1 );
	getchar();
	reg1.subtractRect( Rect16( 100, 70, 50, 150 ) );
	showRegion( reg1 );
	getchar();
	reg1.addRect( Rect16( 100, 70, 50, 150 ) );
	showRegion( reg1 );
	getchar();
	reg1.addRect( Rect16( 300, 240, 300, 200 ) );
	showRegion( reg1 );
	getchar();
	reg1.subtractRect( Rect16( 400, 290, 100, 100 ) );
	showRegion( reg1 );
	getchar();

	appRunning = TRUE;
//	EventLoop( appRunning );				// run the main loop

	exit( EXIT_SUCCESS );
}

bool		in_cleanup = FALSE;

void cleanup()
{
		//	This prevents any functions in the cleanup from calling
		//	exit() and thereby causing an infinite loop

	in_cleanup = TRUE;

	cleanupPanels();
	cleanupSVGAGraphics();
}

void ApplicationTask()
{
}

void showRegion( Region &reg )
{
	Rect16			r;
	RegionIterator	iter( &reg, Rect16( 0, 0, 640, 480 ) );

	mainPort.setColor( 2 );
	mainPort.clear();

//	r = reg.getBounds();
//	mainPort.setColor( 49 );
//	mainPort.frameRect( r, 1 );

	while (iter.next( r ))
	{
		mainPort.setColor( 0 );
		mainPort.frameRect( r, 1 );
		r.expand( -1, -1 );
		mainPort.setColor( 48 );
		mainPort.frameRect( r, 2 );
	}
}

#endif