/* アルゴリズム−２ */

#include	<stdio.h>
#include	<malloc.h>
#include	<mos.h>
#include	"inc\s_button.h"

/* 関数のプロトタイプ宣言(なんかポインタの表現が変だけど(^^;)) */
int		SOP_selPal(short *pal,short col[],int dotnum,int level);
int		SOP_selPal2(short *pal,short col[],int dotnum,int level,short thru);
int		SOP_optimize(char *pat,short pal[16],short *buf,int dotnum);
int		SOP_optimize2(
				char *pat,short pal[16],short *buf,int dotnum,short thru);
void 	SOP_qsort	(short a[],int left,int right);
void	SPM_MC_tokei();
void	SPM_MC_fude();
void	SPM_MC_ya();
static	void SOP_qsort2	(short a[],short b[],int left,int right);


/* 構造体の定義 */
typedef struct
{
	int		r,g,b;
} RGB;					/* そのものずばり！ */




/* マクロ */
#define		US		unsigned
#define		_SQ(x)	((x)*(x))	/* 自乗 */
#define		_DIFF(a,b) ((a)>(b)) ? ((a)-(b)) : ((b)-(a))	/* 差 */
#define		_DIST(a,b) _SQ(_R(a)-_R(b))*900 + _SQ(_G(a)-_G(b))*3364 + _SQ(_B(a)-_B(b))*144	/* 色空間における距離の自乗 */
#define		_DISTC(r1,g1,b1,r2,g2,b2)	_SQ(r1-r2)*900 + _SQ(g1-g2)*3364 + _SQ(b1-b2)*144	/* 色空間における距離の自乗(rgbで入力) */






/* グローバル変数の定義 */

extern	char	mpwork[258];




/*
short	coldat[20]={200,300,100,200,300,
		1000,201,200,300,400,
		12,201,3003,20,99,
		109,209,222,100,900};

short	coldat[20]={1,1,3,3,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
*/


static void	debug(short *pt,int n)
{
	int		i;
	for (i=0;i<n;i++)
		printf("%d\t",pt[i]);
	return;
}


/* マウスカーソルを時計にする */
void	SPM_MC_tokei()
{
	MOS_disp(0);
	MOS_typeRom(116,0,0,mpwork);
	MOS_disp(1);
	return;
}

/* マウスカーソルを矢印に */
void	SPM_MC_ya()
{
	MOS_disp(0);
	MOS_typeRom(81,0,0,mpwork);
	MOS_disp(1);
	return;
}

/* マウスカーソルを筆にする */
void	SPM_MC_fude()
{
	MOS_disp(0);
	MOS_typeRom(113,0,0,mpwork);
	MOS_disp(1);
	return;
}


#if 0
int		main()
{
	int		i,ret;
	char	pat[20/2];	/* 最適化後のパターン */
	short	pal[16];	/* パレット */
	
	
	debug(coldat,20);
	puts("");
	
	ret=SOP_selPal(pal,coldat,20);
	if (ret!=0)
		return(-1);
	debug(pal,16);
	puts("");
	
	ret=SOP_optimize(pat,pal,coldat,20);
	for (i=0;i<10;i++)
		printf("%d:%d|",pat[i]/16,pat[i]%16);
	puts("");
	for (i=0;i<10;i++)
		printf("%d:%d\t",pal[pat[i]/16],pal[pat[i]%16]);
	
	
	puts("");
	
	
	return(0);
}
#endif


/* 色数カウント＆最適16色パレットデータ格納関数 */
int		SOP_selPal(short *pal,short col[],int dotnum,int level)
{
	int		colnum=0;
	int		i,j,ref,min,d,min_i,min_j;
	int		colp,flag;
	short	*buf,*buf2,*buf3;
	
	SPM_MC_tokei();
	
	/* バッファを確保 */
	if ( (buf=malloc(dotnum*2))==NULL)
	{	SPM_MC_ya();	return(-1);	}
	
	/* バッファにコピー */
	_move(col,buf,dotnum*2);
	
	/* 色番号順にソート */
	SOP_qsort(buf,0,dotnum-1);
	
	/* ソート直後のデータを *buf2 に保存 */
	if ( (buf2=malloc(dotnum*2))==NULL)
	{	SPM_MC_ya();	return(-1);	}
	_move(buf,buf2,dotnum*2);
	
	/* バッファ内の整理と色数のカウント...buf[dotnum]に格納 */
	ref=buf[0]; colnum++;
	for (i=1;i<dotnum;i++)
	{
		if (ref!=buf[i])
		{ ref=buf[i];buf[colnum]=ref; colnum++; }
	}
	
	/* 16色以内だったら？ */
	if (colnum<=16)
	{
		for (i=0;i<colnum;i++)
			pal[i]=buf[i];
		for (i=colnum;i<16;i++)
			pal[i]=0;
		free(buf);	free(buf2);
		SPM_MC_ya();
		return(0);
	}
	
	
	/* それぞれの色が何度使われているか？...buf3[colnum]に格納 */
	if ( (buf3=(short *)malloc(2*colnum))==NULL)
	{	SPM_MC_ya();	return(-1);	}
	
	_fill_char(buf3,colnum*2,0);
	ref=0;
	for (i=0;i<colnum;i++)
	{
		label:;
		if (buf[i]==buf2[ref])
		{
			ref++; buf3[i]++;
			goto label;
		}
	}
	free(buf2);
	
	
	/* 使われる回数の少ない順にソート(buf3と全く同じようにbufもソート) */
	SOP_qsort2(buf3,buf,0,colnum-1);
	
	free(buf3);		/* buf3も用済み */
	
	/* 末尾の１６色だけ抽出(色コードにして格納) */
	for (i=0;i<16;i++)
		pal[i]=buf[colnum-i-1];
	
	/* 選んだパレットの内、似通った色があるなら一色にまとめる */
	colp=16;flag=0;
	while (1)
	{
		min=1000000000;		/* エレガントさが無い(^^;) */
		for (i=1;i<16;i++)
		{
			for (j=0;j<i;j++)
			{
				if ( (d=_DIST(pal[i],pal[j])) < min )
				{
					min=d;	min_i=i;  min_j=j;
				}
			}
		}
		
		if (min>level)
			break;
		
		pal[min_i]=buf[colnum-colp-1];
		colp++;
		if (colp>=colnum)
			break;
	}
	
	/* パレットのソート */
	SOP_qsort(pal,0,15);
	
	free(buf);
	
	/* は〜い、おつかれ〜♪ */
	SPM_MC_ya();
	return(0);
}




/* 色数カウント＆最適15色+透過色パレットデータ格納関数 */
int		SOP_selPal2(short *pal,short col[],int dotnum,int level,short thru)
{
	int		colnum=0;
	int		i,j,ref,min,d,min_i,min_j;
	int		colp,flag;
	short	*buf,*buf2,*buf3;
	
	SPM_MC_tokei();
	
	/* バッファを確保 */
	if ( (buf=malloc(dotnum*2))==NULL)
	{	SPM_MC_ya();	return(-1);	}
	
	/* バッファにコピー */
	_move(col,buf,dotnum*2);
	
	/* 色番号順にソート */
	SOP_qsort(buf,0,dotnum-1);
	
	/* ソート直後のデータを *buf2 に保存 */
	if ( (buf2=malloc(dotnum*2))==NULL)
	{	SPM_MC_ya();	return(-1);	}
	ref=0;
	for (i=0;i<dotnum;i++)
	{
		if (buf[i]==thru)
			continue;
		buf2[ref]=buf[i];
		ref++;
	}
	
	/* バッファ内の整理と色数のカウント...buf[dotnum]に格納 */
	ref=-1;
	for (i=0;i<dotnum;i++)
	{
		if (buf[i]==thru)
			continue;
		if (ref!=buf[i])
		{ ref=buf[i];buf[colnum]=ref; colnum++; }
	}
	
	/* 15色以内だったら？ */
	if ( colnum<= 15 )
	{
		for (i=0;i<colnum;i++)
			pal[i+1]=buf[i];
		for (i=colnum;i<15;i++)
			pal[i+1]=0;
		
		pal[0]= (thru==-1) ? 0 : thru;
		
		free(buf);	free(buf2);
		SPM_MC_ya();
		return(0);
	}
	
	
	/* それぞれの色が何度使われているか？...buf3[colnum]に格納 */
	if ( (buf3=(short *)malloc(2*colnum))==NULL)
	{	SPM_MC_ya();	return(-1);	}
	
	_fill_char(buf3,colnum*2,0);
	ref=0;
	for (i=0;i<colnum;i++)
	{
		label:;
		if (buf[i]==buf2[ref])
		{
			ref++; buf3[i]++;
			goto label;
		}
	}
	free(buf2);
	
	
	/* 使われる回数の少ない順にソート(buf3と全く同じようにbufもソート) */
	SOP_qsort2(buf3,buf,0,colnum-1);
	
	free(buf3);		/* buf3も用済み */
	
	/* 透過色を0番に持ってくる */
	pal[0]= (thru==-1) ? 0 : thru;
	
	/* 末尾の１５色だけ抽出(色コードにして格納) */
	for (i=0;i<15;i++)
		pal[i+1]=buf[colnum-i-1];
	
	/* 選んだパレットの内、似通った色があるなら一色にまとめる */
	/* 実はものすごく無駄がある・・・でも面倒(^^;) */
	colp=15;flag=0;
	while (1)
	{
		min=1000000000;		/* エレガントさが無い(^^;) */
		for (i=2;i<16;i++)
		{
			for (j=1;j<i;j++)
			{
				if ( (d=_DIST(pal[i],pal[j])) < min )
				{
					min=d;	min_i=i;  min_j=j;
				}
			}
		}
		
		if (min>level)
			break;
		
		pal[min_i]=buf[colnum-colp-1];
		colp++;
		if (colp>=colnum)
			break;
	}
	
	/* パレットのソート */
	SOP_qsort(pal,1,16);
	
	free(buf);
	
	/* は〜い、おつかれ〜♪ */
	SPM_MC_ya();
	return(0);
}




int		SOP_optimize(char *pat,short palbuf[16],short *buf,int dotnum)
{
	US char	*buf8;	/* ８ビットで格納された最適化済４ビットデータ */
	int		i,j,min,dat,minpal,bytes;
	int		dist,r,g,b;	
	RGB		pal[16];
	
	SPM_MC_fude();
	
	/* パレットデータを計算しやすい形式に直す */
	for (i=0;i<16;i++)
	{
		dat=palbuf[i];
		pal[i].r=_R(dat);
		pal[i].g=_G(dat);
		pal[i].b=_B(dat);
	}
	
	/* バッファの確保 */
	if ( (buf8=(US char *)malloc(dotnum))==NULL)
	{	SPM_MC_ya();	return(-1);	}
	
	/* 差の最も少ない組み合わせを選ぶ */
	for (i=0;i<dotnum;i++)
	{
		min=1000000000;		/* すぐに更新されそうな数 */
		dat = buf[i];
		r = _R(dat);
		g = _G(dat);
		b = _B(dat);
		for (j=0;j<16;j++)
		{
			dist=_DISTC(pal[j].r,pal[j].g,pal[j].b,r,g,b);
			if (min>dist)
			{
				min=dist;
				minpal=j;
			}
		}
		buf8[i]=minpal;
	}
	
	/* ８ビットデータを４ビットデータに */
	bytes=((1+dotnum)>>1);
	
	/* 上位４、下位４の順に評価される？ */
	for (i=0;i<bytes;i++)
		pat[i]=(buf8[i*2] << 4)+buf8[i*2+1];
	
	free(buf8);
	SPM_MC_ya();
	return(0);
}



/* 透過色付きの最適化 */
int		SOP_optimize2(char *pat,short palbuf[16],short *buf,int dotnum,short thru)
{
	US char	*buf8;	/* ８ビットで格納された最適化済４ビットデータ */
	int		i,j,min,dat,minpal,bytes;
	int		dist,r,g,b;	
	RGB		pal[16];
	
	SPM_MC_fude();
	
	/* パレットデータを計算しやすい形式に直す */
	for (i=0;i<16;i++)
	{
		dat=palbuf[i];
		pal[i].r=_R(dat);
		pal[i].g=_G(dat);
		pal[i].b=_B(dat);
	}
	
	/* バッファの確保 */
	if ( (buf8=(US char *)malloc(dotnum))==NULL)
	{	SPM_MC_ya();	return(-1);	}
	
	
	/* 差の最も少ない組み合わせを選ぶ */
	for (i=0;i<dotnum;i++)
	{
		min=1000000000;		/* すぐに更新されそうな数 */
		dat = buf[i];
		
		if ( thru==dat )	/* 透過色と合致 */
		{
			buf8[i]=0;
			continue;
		}
		
		r=_R(dat);	g=_G(dat);	b=_B(dat);
		
		for (j=1;j<16;j++)
		{
			dist=_DISTC(pal[j].r,pal[j].g,pal[j].b,r,g,b);
			if (min>dist)
			{
				min=dist;
				minpal=j;
			}
		}
		buf8[i]=minpal;
	}
	
	/* ８ビットデータを４ビットデータに */
	bytes=((1+dotnum)>>1);
	
	/* 上位４、下位４の順に評価される？ */
	for (i=0;i<bytes;i++)
		pat[i]=(buf8[i*2+1] << 4)+buf8[i*2];
	
	free(buf8);
	SPM_MC_ya();
	return(0);
}




/* クイックソート関数 */

void	SOP_qsort(short a[],int left,int right)
{
	int		s,t,i,j;
	
	if (left<right)
	{
		s=a[(left+right)/2];
		i=left-1; j=right+1;
		while(1)
		{
			while (a[++i]<s)	;
			while (a[--j]>s)	;
			if (i>=j)
				break;
			t=a[i]; a[i]=a[j]; a[j]=t;
		}
		
		SOP_qsort(a,left,i-1);
		SOP_qsort(a,j+1,right);
	}
	return;
}


/* クイックソート２ */
static	void	SOP_qsort2(short a[],short b[],int left,int right)
{
	int		s,t,i,j;
	
	if (left<right)
	{
		s=a[(left+right)/2];
		i=left-1; j=right+1;
		while(1)
		{
			while (a[++i]<s)	;
			while (a[--j]>s)	;
			if (i>=j)
				break;
			t=a[i]; a[i]=a[j]; a[j]=t; t=b[i]; b[i]=b[j]; b[j]=t;
		}
		
		SOP_qsort(a,left,i-1);
		SOP_qsort(a,j+1,right);
	}
	return;
}