#include <stdio.h>
#include "defs.h"
#include "types.h"
#include "exports.h"

#define	MAXINT		2147483647		/* 2^31 - 1 */

#define	FILEBUFSIZE	( (int) (BUFSIZ / sizeof( Edge )) * sizeof( Edge ) )


/*
 * Functions that communicate with the back-end
 */
public	void	(*OutputVline)();		/* Output Verical Line */
public	void	(*OutputHline)();		/* Output Horizontal Line */
public	void	(*OutputRect)();		/* Output Filled Rectangle */
public	void	(*ChangeLayer)();		/* Change stipple-pattern */


/*
 * Use a doubly linked list of edges to define each scan line.
 */
typedef struct HorizLine
  {
    EdgeP		edge;
    int			leftRect;
    struct HorizLine	*prev;
    struct HorizLine	*next;
  } HorizLine, *HLine;


private	Edge		firstEdge = { -MAXINT, MAXINT, -MAXINT, 0 };
private	Edge		lastEdge = { MAXINT, MAXINT, MAXINT, 0 };
private	HorizLine	firstLine = { &firstEdge, 0, NULL, NULL };
private	HorizLine	lastLine = { &lastEdge, 0, NULL, NULL };

private	Edge		oneEdgeBuff;
private	EdgeP		oneEdgeP = &oneEdgeBuff;
private	EdgeP		*nextEdge;
private	int		nEdges;

private	HLine		freeList;
private	FILE		*fin;
private	int		lineAllocSize;



#define NewLine( line, e )					\
  {								\
    if( freeList != NULL )					\
      {								\
	line = freeList;					\
	freeList = freeList->next;				\
      }								\
    else							\
	if( (line = (HLine) Malloc( lineAllocSize )) == NULL )	\
	    Crash( "Out of memory for edges", 2 );		\
    if( fin == NULL )						\
	line->edge = e;						\
    else							\
      {								\
	line->edge = (EdgeP) &(line[1]);			\
	*(line->edge) = *e;					\
      }								\
    line->leftRect = e->left;					\
  }								\


#define FreeLine( line )					\
  {								\
    line->next = freeList;					\
    freeList = line;						\
  }								\



private void DummyFunction( r )
  IRect *r;
  {
	/* do nothing => rectangles are not visible anyhow */
  }



/*
 * Pre-Initialize the 1st and last elements of the list.  This makes
 * insertion and deletions of individual elements much simpler.  Also
 * initialize the first edge to be read (from the sorted list or the
 * sorted file), depending on the value of 'ep'.
 */
private void InitScanLine( n, ep, fname )
  int	n;
  EdgeP	*ep;
  char	*fname;
  {
    nEdges = n;

    firstLine.next = &lastLine;
    firstLine.prev = NULL;
    lastLine.next = NULL;
    lastLine.prev = &firstLine;
    freeList = NULL;
    
    if( ep != NULL )		/* input edges are kept in sorted list 'ep' */
      {
	nextEdge = ep;
	lineAllocSize = sizeof( HorizLine );
	fin = NULL;
      }
    else			/* input edges are kept in file 'fname' */
      {
	if( (fin = fopen( fname, "r" )) == NULL )
	    Crash( "can't reopen tmp file '%s'\n", 2, fname );
	setbuf( fin, Malloc( FILEBUFSIZE ) );
	nextEdge = &oneEdgeP;
	(void) fread( &oneEdgeBuff, sizeof( Edge ), 1, fin );
	lineAllocSize = sizeof( HorizLine ) + sizeof( Edge );
      }
  }



/*
 * Merge the elements of the next scan line ( with left == currx ) into the
 * current list.  The list is kept sorted in 'y'.  Edges with equal 'y' values
 * are kept in [ BOTTOM, TOP ] order in such a way that the first BOTTOM edge
 * is always the longest (in x) and the last TOP is always the longest (in x)
 * This reduces the number of cases in the hidden-line elimination algorithm
 * and allows for maximizing horizontal lines.  A B-tree structure could be
 * used for the scan line, improving the insertion time, but then traversing
 * and deleting would be more expensive.
 */
private MergeScaneLine( currx )
  int  currx;
  {
    register HLine	p, q;
    register EdgeP	next;
    HLine		s;
    
    p = &firstLine;
    next = *nextEdge;
    while( next->left == currx )
      {
	while( p->edge->y < next->y )
	    p = p->next;
	
	if( p->edge->y == next->y )
	  {
	    switch( next->dir )
	      {
		case BOTTOM :
		    if( p->edge->dir == BOTTOM )
		      {
			if( p->edge->right == next->left )
			    /* abutting lines */
			    MAX( p->edge->right, next->right )
			else
			  {	/* overlapping lines */
			    register tmp = max( p->edge->right, next->right );
			    MIN( next->right, p->edge->right )
			    p->edge->right = tmp;
			    NewLine( q, next );
			    q->next = p->next;
			    q->prev = p;
			    p->next->prev = q;
			    p->next = q;
			  }
		      }
		    else	/* old line is TOP, insert before p */
		      {
			NewLine( q, next );
			q->next = p;
			q->prev = p->prev;
			p->prev->next = q;
			p->prev = q;
			p = q;
		      }
		    break;
		case TOP :
		    s = p;
		    while( p->next->edge->y == next->y )
			p = p->next;
		    if( p->edge->dir == TOP )
		      {
			if( p->edge->right == next->left )
			    /* abutting lines */
			    MAX( p->edge->right, next->right )
			else
			  {
			    register tmp = max( p->edge->right, next->right );
			    MIN( next->right, p->edge->right )
			    p->edge->right = tmp;
			    NewLine( q, next );
			    q->prev = p->prev;
			    q->next = p;
			    p->prev->next = q;
			    p->prev = q;
			  }
		      }
		    else
		      {
			NewLine( q, next );
			q->next = p->next;
			q->prev = p;
			p->next->prev = q;
			p->next = q;
		      }
		    p = s;
		    break;
	      }
	  }
	else		/* p->edge->y > next->y */
	  {
	    NewLine( q, next );
	    q->next = p;
	    q->prev = p->prev;
	    p->prev->next = q;
	    p->prev = q;
	    p = q;
	  }
	if( --nEdges > 0 )
	  {
	    if( fin == NULL )
	      {
		nextEdge++;
		next = *nextEdge;
	      }
	    else
	      {
		(void) fread( &oneEdgeBuff, sizeof( Edge ), 1, fin );
	      }
	  }
	else
	  {
	    nextEdge = &oneEdgeP;
	    oneEdgeBuff.left = MAXINT;
	    return;
	  }
      }
  }



/*
 * Generate the Filled Rectangles and the Outline for the layer in progress.
 * The algorithm generates the outline defined by the rectangles of the layer
 * as well as the areas to be filled (rectangles).  The rectangles generated
 * will be non-overlapping (though abutting) and maximized in the x-direction.
 * The algorithm uses a scan line approach, and is based on:
 *	An O(N log N) Algorithm for Boolean Mask Operations
 *	Ulrich Lauthner
 *	18th Design Automation Conference (pg. 555 - 561)
 */
public void GenerateRect_Outline( n, sortArr, fname, layNum )
  int	n;
  EdgeP	*sortArr;
  char	*fname;
  int	layNum;
  {
    register int	currX;
    int			nextX;
    HLine		scanY, nextY;
    register EdgeP	edge;
    register int	countLeft, countRight;
    register int	left, lastLeft;
    register int	right, lastRight;
    H_Line		hline;
    V_Line		vline;
    IRect		rect;
    int			rectFlag;
    void		(*tmpFunction)();
    
    if( not IsVisible( layNum ) )	/* stipple pattern is all 0's */
      {
	tmpFunction = OutputRect;
	OutputRect = DummyFunction;
      }
    ChangeLayer( layNum );
    InitScanLine( n, sortArr, fname );
    currX = (*nextEdge)->left;
    
    while( currX < MAXINT )
      {
	MergeScaneLine( currX );
	scanY = firstLine.next;
	countLeft = 0;
	countRight = 0;
	lastLeft = 0;
	lastRight = 0;
	nextX = MAXINT;
	rectFlag = FALSE;
	while( scanY != NULL )
	  {
	    nextY = scanY->next;
	    edge = scanY->edge;
	    if( edge->left < currX )
		countLeft += edge->dir;
	    if( edge->right > currX )
		countRight += edge->dir;
	    left = (countLeft)? 1 : 0;
	    right = (countRight)? 1 : 0;
	    switch( (lastLeft << 3) + (lastRight << 2) + (left << 1) + right )
	      {
		case 0 :
		    break;
		case 1 :
		    vline.x = currX;
		    vline.bot = edge->y;
		    break;
		case 2 :
		    vline.x = currX;
		    vline.bot = edge->y;
		    hline.y = edge->y;
		    hline.left = edge->left;
		    hline.right = currX;
		    OutputHline( &hline );
		    rect.bot.y = edge->y;
		    break;
		case 3 :
		    rect.bot.y = edge->y;
		    break;
		case 4 :
		    vline.top = edge->y;
		    OutputVline( &vline );
		    break;
		case 5 :
		    break;
		case 6 :
		    break;
		case 7 :
		    vline.top = edge->y;
		    OutputVline( &vline );
		    hline.y = edge->y;
		    hline.left = edge->left;
		    hline.right = currX;
		    OutputHline( &hline );
		    rect.bot.y = edge->y;
		    rectFlag = TRUE;
		    break;
		case 8 :
		    vline.top = edge->y;
		    OutputVline( &vline );
		    hline.y = edge->y;
		    hline.left = edge->left;
		    hline.right = currX;
		    OutputHline( &hline );
		    rect.bot.x = scanY->leftRect;
		    rect.top.x = currX;
		    rect.top.y = edge->y;
		    OutputRect( &rect );
		    rectFlag = FALSE;
		    break;
		case 9 :
		    break;
		case 10 :
		    break;
		case 11 :
		    vline.top = edge->y;
		    OutputVline( &vline );
		    edge->left = currX;
		    rectFlag = TRUE;
		    break;
		case 12 :
		    if( rectFlag )
		      {
			rect.bot.x = scanY->leftRect;
			rect.top.x = currX;
			rect.top.y = edge->y;
			rectFlag = FALSE;
			scanY->leftRect = currX;
			OutputRect( &rect );
		      }
		    break;
		case 13 :
		    vline.x = currX;
		    vline.bot = edge->y;
		    hline.y = edge->y;
		    hline.left = edge->left;
		    hline.right = currX;
		    OutputHline( &hline );
		    rect.bot.x = scanY->leftRect;
		    rect.top.x = currX;
		    rect.top.y = edge->y;
		    OutputRect( &rect );
		    rectFlag = FALSE;
		    break;
		case 14 :
		    vline.x = currX;
		    vline.bot = edge->y;
		    edge->left = currX;
		    scanY->leftRect = currX;
		    break;
		case 15 :
		    break;
	      }
	    if( edge->right == currX )
	      {
		scanY->prev->next = scanY->next;
		scanY->next->prev = scanY->prev;
		FreeLine( scanY );
	      }
	    else
		MIN( nextX, edge->right );
	    
	    lastLeft = left;
	    lastRight = right;
	    scanY= nextY;
	  }
	currX = min( (*nextEdge)->left, nextX );
      }
    if( not IsVisible( layNum ) )
	OutputRect = tmpFunction;
  }



/*
 * Same as GenerateRect_Outline except that the outline is not generated,
 * only the rectangles to be filled.
 */
public void GenerateRectangles( n, sortArr, fname, layNum )
  int	n;
  EdgeP	*sortArr;
  char	*fname;
  int	layNum;
  {
    register int	currX;
    int			nextX;
    HLine		scanY, nextY;
    register EdgeP	edge;
    register int	countLeft, countRight;
    register int	left, lastLeft;
    register int	right, lastRight;
    IRect		rect;
    int			rectFlag;
    
    if( not IsVisible( layNum ) )
	return;
    ChangeLayer( layNum );
    InitScanLine( n, sortArr, fname );
    currX = (*nextEdge)->left;
    
    while( currX < MAXINT )
      {
	MergeScaneLine( currX );
	scanY = firstLine.next;
	countLeft = 0;
	countRight = 0;
	lastLeft = 0;
	lastRight = 0;
	nextX = MAXINT;
	rectFlag = FALSE;
	while( scanY != NULL )
	  {
	    nextY = scanY->next;
	    edge = scanY->edge;
	    if( edge->left < currX )
		countLeft += edge->dir;
	    if( edge->right > currX )
		countRight += edge->dir;
	    left = (countLeft)? 1 : 0;
	    right = (countRight)? 1 : 0;
	    switch( (lastLeft << 3) + (lastRight << 2) + (left << 1) + right )
	      {
		case 0 :
		    break;
		case 1 :
		    break;
		case 2 :
		    rect.bot.y = edge->y;
		    break;
		case 3 :
		    rect.bot.y = edge->y;
		    break;
		case 4 :
		    break;
		case 5 :
		    break;
		case 6 :
		    break;
		case 7 :
		    rect.bot.y = edge->y;
		    rectFlag = TRUE;
		    break;
		case 8 :
		    rect.bot.x = scanY->leftRect;
		    rect.top.x = currX;
		    rect.top.y = edge->y;
		    OutputRect( &rect );
		    rectFlag = FALSE;
		    break;
		case 9 :
		    break;
		case 10 :
		    break;
		case 11 :
		    edge->left = currX;
		    rectFlag = TRUE;
		    break;
		case 12 :
		    if( rectFlag )
		      {
			rect.bot.x = scanY->leftRect;
			rect.top.x = currX;
			rect.top.y = edge->y;
			rectFlag = FALSE;
			scanY->leftRect = currX;
			OutputRect( &rect );
		      }
		    break;
		case 13 :
		    rect.bot.x = scanY->leftRect;
		    rect.top.x = currX;
		    rect.top.y = edge->y;
		    OutputRect( &rect );
		    rectFlag = FALSE;
		    break;
		case 14 :
		    edge->left = currX;
		    scanY->leftRect = currX;
		    break;
		case 15 :
		    break;
	      }
	    if( edge->right == currX )
	      {
		scanY->prev->next = scanY->next;
		scanY->next->prev = scanY->prev;
		FreeLine( scanY );
	      }
	    else
		MIN( nextX, edge->right );
	    
	    lastLeft = left;
	    lastRight = right;
	    scanY= nextY;
	  }
	currX = min( (*nextEdge)->left, nextX );
      }
  }