/*

描画アルゴリズム

void do_line_cont(int x1,int y1,int x2,int y2,void func(int x,int y)!)
void do_line(int x1,int y1,int x2,int y2,void func(int x,int y)!)

do_paint
void do_blot(int x, int y, int branch, int depth,
			 void pset(int x,int y,int gray)!)
void do_polygon(POINT* points, int nPoint, void hline(int x1,int x2,int y)!)

*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <winb.h>
#include <te.h>
#include <fntb.h>
#include <gui.h>
#include <egb.h>
#include <wgb.h>
#include <msdos.cf>
#include "art.h"
#include "guisub.h"
#include "wgbmac.H"

#include "subgrp.h"
#include "imath.h"

#define swap(a,b)  { int t; t=(a); (a)=(b); (b)=t; }


/*--------------------------------------------------------*/
/*                    描画アルゴリズム                    */
/*--------------------------------------------------------*/

void do_line_cont(int x1,int y1,int x2,int y2,void func(int x,int y)!)
{
	int xr,yr,r,x,y;
	xr=abs(x2-x1),yr=abs(y2-y1);
	if (xr==0 && yr==0)
		;
	else if (xr > yr)
	{
		r=(yr<<16)/xr; if(y1>y2) r=-r;
		if (x1 < x2)
			for (x=x1+1,y=(y1<<16)+0x8000+r; x<=x2; x++,y+=r)
				func(x,(y>>16));
		else 
			for (x=x1-1,y=(y1<<16)+0x8000+r; x>=x2; x--,y+=r)
				func(x,(y>>16));
	}
	else
	{
		r=(xr<<16)/yr; if(x1>x2) r=-r;
		if (y1 < y2)
			for (y=y1+1,x=(x1<<16)+0x8000+r; y<=y2; y++,x+=r)
				func((x>>16),y);
		else
			for (y=y1-1,x=(x1<<16)+0x8000+r; y>=y2; y--,x+=r)
				func((x>>16),y);
	}
}

void do_line(int x1,int y1,int x2,int y2,void func(int x,int y)!)
{
	func(x1,y1);	// 最初の点
	do_line_cont(x1,y1,x2,y2,func);
}

void do_boxline(int x1,int y1,int x2,int y2,void func(int x,int y)!)
{
	int i;
	if (x2<x1) swap(x1,x2);
	if (y2<y1) swap(y1,y2);
	for(i=x1;i<=x2;i++) func(i,y1);
	if(y1<y2)
		for(i=x1;i<=x2;i++) func(i,y2);
	for(i=y1+1;i<y2;i++) func(x1,i);
	if(x1<x2)
		for(i=y1+1;i<y2;i++) func(x2,i);
}

void do_boxfill(int x1,int y1,int x2,int y2,void func(int x1,int x2,int y)!)
{
	int i;
	if (x2<x1) swap(x1,x2);
	if (y2<y1) swap(y1,y2);
	for(i=y1;i<=y2;i++) func(x1,x2,i);
}

void do_ellipse(int x,int y,int rx,int ry,void func(int x,int y)!)
{
#if 0
	#define	ELLIPSE(RX,RY,X0,Y0,X1,Y1)							\
		{														\
			int x0=RX,s=x0;										\
			int y0=0;											\
			int px0=-1,py0=-1,px1=-1,py1=-1;					\
			while(x0>=y0)										\
			{													\
				int x1=x0*RY/RX;						\
				int y1=y0*RY/RX;						\
				if(px0!=X0||py1!=Y1)					\
				{													\
					func(x+X0,y+Y1);if(X0!=0)func(x-X0,y+Y1);		\
					if (Y1!=0)										\
					 { func(x+X0,y-Y1);if(X0!=0)func(x-X0,y-Y1); }	\
				}													\
				if (py0!=Y0||px1!=X1)								\
				{												\
					func(x+Y0,y+X1);if(Y0!=0)func(x-Y0,y+X1);		\
					if (X1!=0)										\
					 { func(x+Y0,y-X1);if(Y0!=0)func(x-Y0,y-X1); }	\
				}												\
				s-=2*y0+1; if(s<0)s+=2*(x0-1),x0--;				\
				y0++;											\
				px0=X0,py0=Y0,px1=X1,py1=Y1;					\
			}													\
		}
	#
	if (rx==0 && ry==0)
		func(x,y);
	else if (rx>ry)
		ELLIPSE(rx,ry,x0,y0,x1,y1)
	else
		ELLIPSE(ry,rx,x1,y1,x0,y0)
	#undef ELLIPSE
#endif
	if (rx==0 && ry==0)
		{ func(x,y); return; }
	int px,py,prey;
	int a2,b2;
	int c1,c2;
	int e;
	a2=rx*rx,b2=ry*ry;
	px=0,py=ry;
	c1=4*b2,c2=8*a2;
	e=a2*(1-4*ry);
	while(b2*px<=a2*py)
	{
		func(x+px,y+py); if(px!=0)func(x-px,y+py);
		func(x+px,y-py); if(px!=0)func(x-px,y-py);
		prey=py;
		e+=c1*(2*px+1),px++; if(e>0) e-=c2*py,py--;
	}
	px=rx,py=0;
	c1=4*a2,c2=8*b2;
	e=b2*(1-4*rx);
	while(a2*py<=b2*px && py<prey)
	{
		func(x+px,y+py); if(px!=0)func(x-px,y+py);
		if(py!=0) { func(x+px,y-py); if(px!=0)func(x-px,y-py); }
		e+=c1*(2*py+1),py++; if(e>0) e-=c2*px,px--;
	}
}

void do_ellipsefill(int x,int y,int rx,int ry,void func(int x1,int x2,int y)!)
{
#if 0
	#define	ELLIPSE(RX,RY,X0,Y0,X1,Y1)					\
		{												\
			int x0=RX,s=x0;								\
			int y0=0;									\
			int py0,py1;								\
			py0=py1=INT_MIN;							\
			while(x0>=y0)								\
			{											\
				int x1=x0*RY/RX;						\
				int y1=y0*RY/RX;						\
				if (y+Y1 != py0)						\
				{										\
					py0=y+Y1;							\
					func(x-X0,x+X0,py0);				\
					func(x-X0,x+X0,y-Y1);				\
				}										\
				if (y+X1 != py1)						\
				{										\
					py1=y+X1;							\
					func(x-Y0,x+Y0,py1);				\
					func(x-Y0,x+Y0,y-X1);				\
				}										\
				s-=2*y0-1; if(s<0)s+=2*(x0-1),x0--;		\
				y0++;									\
			}											\
		}
	#
	if (rx==0&&ry==0)
		func(x,x,y);
	else if (rx>ry)
		ELLIPSE(rx,ry,x0,y0,x1,y1)
	else
		ELLIPSE(ry,rx,x1,y1,x0,y0)
	#undef ELLIPSE
#endif
	if (rx==0 && ry==0)
		{ func(x,x,y); return; }
	int px,py,prey;
	int a2,b2;
	int c1,c2;
	int e;
	a2=rx*rx,b2=ry*ry;
	px=0,py=ry;
	c1=4*b2,c2=8*a2;
	e=a2*(1-4*ry);
	prey=-1;
	while(b2*px<=a2*py)
	{
		e+=c1*(2*px+1);
		if(e>0)
		{
			func(x-px,x+px,y+py); func(x-px,x+px,y-py);
			prey=py;
		 	e-=c2*py,py--;
		}
		px++;
	}
	px=rx,py=0;
	c1=4*a2,c2=8*b2;
	e=b2*(1-4*rx);
	while(a2*py<=b2*px && py<prey)
	{
		func(x-px,x+px,y+py);
		if(py!=0) func(x-px,x+px,y-py);
		e+=c1*(2*py+1),py++; if(e>0) e-=c2*px,px--;
	}
}

/*--------------------------------------------------------*/
/*                    ペイントルーチン                    */
/*--------------------------------------------------------*/

typedef struct {
	short int  x,y;
	short int  px1,px2,py;
	BOOL mark;
} STACK;

void do_paint(int x,int y, int picwid, int picht,
              void hline(int x1,int x2,int y)!,
			  BOOL shouldPaint(int x,int y)!,	// point(x,y) == border
              int srchleft(int x,int y)!,
              int srchright(int x,int y)!)
{
	#define STACKSIZE 600
  // ラスタリージョンの追加を行う関数
	STACK *check(int px1,int px2,int py,int sx1,int sx2,int sy,
	             int y, STACK *stack,int stacksize, STACK *sp)
		// 新しい sp を返す
	{
		int x;
		BOOL in_border;
		if (y<0 || picht<=y)
			return sp;
		in_border = TRUE;
		for (x=sx1; x<=sx2; x++) {
			if (in_border) {
				if (shouldPaint(x,y)) {
					if (!(y==py&&px1<=x&&x<=px2) && sp+1 < stack+stacksize) {
						sp++;
						sp->x = x;
						sp->y = y;
						sp->px1 = sx1;
						sp->px2 = sx2;
						sp->py = sy;
						sp->mark = TRUE;
					}
					in_border = FALSE;
				}
			} else {
				if (!shouldPaint(x,y))
					in_border = TRUE;
			}
		}
		return sp;
	}
  // ラスタリージョンの削除を行う関数
	void delete(int sx1,int sx2,int sy,STACK *oldsp, STACK *stack, STACK *sp)
	{
		STACK *p,*q;
		for (p=stack; p<=oldsp; p++) {
			if (p->y == sy && sx1 <= p->x && p->x <= sx2) {
				p->mark = FALSE;
				for (q = oldsp+1; q<=sp; q++) {
					if (q->y == p->py && p->px1 <= q->x && q->x <= p->px2)
						q->mark = FALSE;
				}
			}
		}
	}
	STACK stack[STACKSIZE];
	STACK *sp;
	STACK *oldsp;
	int sx,sx1,sx2,sy;
	int px1,px2,py;

	sp = stack;
	sp->x = x;
	sp->y = y;
	sp->px1 = 0;
	sp->px2 = 0;
	sp->py = 0;
	sp->mark = TRUE;
	while (sp >= stack) {
		if (sp->mark) {
			sx = sp->x;
			sy = sp->y;
			px1 = sp->px1;
			px2 = sp->px2;
			py = sp->py;
			sx1 = srchleft(sx,sy);
			// 	for (sx1=sx,ip=(short*)EIMadrs(sx1,sy);
			//		 sx1 > 0 && *(ip-1) == border;
			//		 sx1--,ip--)
			//		;
			sx2 = srchright(sx,sy);
			//	for (sx2=sx,ip=(short*)EIMadrs(sx2,sy);
			//		 sx2 < EIMgetxsize()-1 && *(ip+1) == border;
			//		 sx2++,ip++)
			//		;
			hline(sx1,sx2,sy);
			oldsp = --sp;
			sp=check(px1,px2,py,sx1,sx2,sy,sy+1, stack,STACKSIZE, sp);
			sp=check(px1,px2,py,sx1,sx2,sy,sy-1, stack,STACKSIZE, sp);
			delete(sx1,sx2,sy,oldsp, stack,sp);
		} else
			sp--;
	}
}

void do_blot(int x, int y, int branch, int depth,
			 void pset(int x,int y,int gray)!)
// branch : 枝分かれする数
// depth : 何回再帰するか
// gray : 0..50 程度
{
	if (depth <= 0)
		return;
	deci branchsub = IntToDeci(branch)/_max(1,depth/3);
	void blot_plot_sub(int x,int y,deci branch,int depth,
					   deci grad, deci gradsub)
	{
		if (depth <= 0 || grad <= 0)
			return;
		pset(x,y,DeciToInt(grad));
		int b;
		for (b=0; b<_max(1,DeciToInt(branch)); b++)
		{
			int nx,ny;
			nx = x + rand() % 3 - 1;
			ny = y + rand() % 3 - 1;
			blot_plot_sub(nx,ny,branch-branchsub,depth-1,grad-gradsub,gradsub);
		}
	}
	blot_plot_sub(x,y,IntToDeci(branch),depth,
				  IntToDeci(50),IntToDeci(50)/depth);
}

#define MAXY 2000

static short **xbuf = NULL;	// ポリゴン指定用ワーク
#define XBUFMAX 10
#define	RIGHTMAX	0x7fff

void do_polygon(POINT* points, int nPoint, void hline(int x1,int x2,int y)!)
{
	if (xbuf == NULL)
	{
		if ((xbuf = TL_calloc(1,sizeof(short*)*MAXY)) == NULL)
			return;
		short* buf = TL_calloc(sizeof(short),XBUFMAX*MAXY);
		if (buf == NULL)
			{ TL_free(xbuf); xbuf = NULL; return; }
		for (int i=0; i<MAXY; i++)
			xbuf[i] = buf + XBUFMAX*i;
	}
	int i;
	for (i=0; i<MAXY; i++)
		xbuf[i][0] = RIGHTMAX;
	int getsign(int n)
	  { return (n<0 ? -1 : n>0 ? 1 : 0); }
	int pnum = nPoint;	// 頂点の数
	int f1,f2;
	// 始点での頂点の例外処理のために､前の辺の符号をきめる
	f1=0;
	for (i=1; i<pnum; i++) {
		f2=getsign(points[i].y-points[i-1].y);
		if (f2!=0)
			f1=f2;
	}
	f2=getsign(points[0].y-points[pnum-1].y);
	if (f2!=0)
		f1=f2;
	// x 座標リストの作成
	void makebuf(int x1,int y1,int x2,int y2)
	{
		void sort_x() // (x1,y1) をバッファに登録する
		{
			if (y1 < 0 || MAXY <= y1)
				return;
			for (int i=0; i<XBUFMAX; i++)
			{
				if (xbuf[y1][i] > x1)
				{
					if (i==XBUFMAX-1)
					{
						xbuf[y1][i] = x1;
						return;
					}
					for (int j=XBUFMAX-1; j>i; j--)
						xbuf[y1][j] = xbuf[y1][j-1];
					xbuf[y1][i] = x1;
					break;
				}
			}
		}
		int f2;
		f2 = getsign(y2-y1);
		if (f2==0)
			return;
		if (f1*f2==-1)
			sort_x();
		int dx,dy,ux,uy;
		dx = abs(x2-x1);
		dy = abs(y2-y1);
		ux = getsign(x2-x1);
		uy = getsign(y2-y1);
		if (dx >= dy) {
			int r = dx/2;
			for (;;) {
				if (x1==x2) {
					f1=f2;
					break;
				}
				x1 += ux, r += dy;
				if (r >= dx) {
					r -= dx, y1 += uy;
					sort_x();
				}
			}
		} else {
			int r = dy/2;
			for (;;) {
				if (y1==y2) {
					f1=f2;
					break;
				}
				y1 += uy, r += dx;
				if (r >= dy)
					r -= dy, x1 += ux;
				sort_x();
			}
		}
	}
	for (i=0; i<pnum-1; i++)
		makebuf(points[i].x,points[i].y,points[i+1].x,points[i+1].y);
	makebuf(points[pnum-1].x,points[pnum-1].y,points[0].x,points[0].y);
	for (i=0; i<MAXY; i++) {
		for (int j=0; j<XBUFMAX; j+=2) {
			if (_max(xbuf[i][j],xbuf[i][j+1]) < RIGHTMAX)
				hline(xbuf[i][j],xbuf[i][j+1],i);
			else
				break;
		}
	}
}