#include <cmath>
#include <ctime>
#include <string>
#include <fstream>
#include <iomanip>
#include <iostream>
using namespace std;

//#define Tv 10
#define ColorNum 256
#define ColorDepth 3
#define max_size 1024

unsigned int Tv;
unsigned int ClusterNum;
unsigned int TotalEmbeddedBits;
unsigned int im_height, im_width;
unsigned int PaletteNum, indexsize, DuPosiLen;

double 		luminance[ColorNum];
double 		sortstack[ColorNum];
double		ColorDifference[ColorNum][ColorNum];

unsigned int	ColorClSi[ColorNum];
unsigned int  	ClusterSize[ColorNum];					//用來記錄每一個cluster的大小(size)
unsigned int  	IndexImage[max_size*max_size];					//Image的block指標
unsigned int 	Palette[ColorNum][ColorDepth];
unsigned int  	ClusterIndex[ColorNum][ColorNum];		//紀錄每個Cluster中有哪些codebook中codeword的指標
unsigned char 	InImage[max_size][max_size][ColorDepth];


double EmbedDiff(int,int);
int main(int, char* []);
int Product_Palette();
void SortPalette();
void PaletteIndex();
void ReadBMP(char []);							//讀出影像檔
void ProductCluster();
void PaletteChange(int);
void InputErrorPrintf();
void WriteIndex(char []);
void ComputeDiffOfColors();
void Quicksort(const int ,const int);


//====================================================================================
void Quicksort(const int left,const int right)
{
	int i, j;
	double pivot,temp;
	
	if(left<right)
	{
		i=left;
		j=right+1;
		pivot=sortstack[left];
		do{
    		do{
				i++;			
			}while(sortstack[i]<pivot);
			do{
				j--;
			}while(sortstack[j]>pivot);
			if(i<j)
			{
				temp=sortstack[i];
				sortstack[i]=sortstack[j];
				sortstack[j]=temp;
			}
		}while(i<j);
    	temp=sortstack[left];		
		sortstack[left]=sortstack[j];
		sortstack[j]=temp;		
	    
		Quicksort(left,j-1);
    	Quicksort(j+1,right);
	}
}
//====================================================================================

//====================================================================================
void PaletteChange(int p)			//using for SortPalette()
{
	int i;
	int ColorTemp[ColorDepth];
	
	for(i; i<ColorDepth; i++)
		ColorTemp[i]=Palette[p][i];
	for(i; i<ColorDepth; i++)
		Palette[p][i]=Palette[p][p+1];
	for(i; i<ColorDepth; i++)
		Palette[p+1][i]=ColorTemp[i];
}
//====================================================================================

//====================================================================================
void SortPalette()
{
	cout<<"SortPalette"<<endl;
	int i, j, k, l;
	int appear = 0;
	int Reco[ColorNum];
	int Temp[ColorNum][ColorDepth];
	
	for(i=0; i<PaletteNum; i++){
		for(j=0; j<ColorDepth; j++){
			Temp[i][0] = Palette[i][0];
		    Temp[i][1] = Palette[i][1];
		    Temp[i][2] = Palette[i][2];
		}
	}
	
	for(i=0; i<PaletteNum; i++){
		luminance[i] = 0.3*Palette[i][0]+0.59*Palette[i][1]+0.11*Palette[i][2];
		sortstack[i] = 0.3*Palette[i][0]+0.59*Palette[i][1]+0.11*Palette[i][2];		
	}
	
	Quicksort(0, (PaletteNum-1));
	
	l = 0;
	for(i=0; i<=PaletteNum; i++){	
		for(j=0; j<PaletteNum; j++){			
			if(sortstack[(PaletteNum-1)-i]==luminance[j]){
				appear = 0;
				for(k=0; k<l; k++){
					if(Reco[k]==j)
						appear = 1;
				}
				if(appear==0){
					for(k=0; k<ColorDepth; k++)
						Palette[i][k] = Temp[j][k];
					Reco[l] = j;
					l++;
					break;
				}
			}
		}		
	}
	
	for(i=0; i<PaletteNum; i++)
		luminance[i] = sortstack[(PaletteNum-1)-i];
	
	for(i=0; i<(PaletteNum-1); i++){		
		if(luminance[i]==luminance[i+1]){
			if(Palette[i][0]<Palette[i+1][0]){
				PaletteChange(i);
			}
			else if(Palette[i][0]==Palette[i+1][0]){
				if(Palette[i][1]<Palette[i+1][1]){
					PaletteChange(i);
				}
				else if(Palette[i][1]==Palette[i+1][1]){
					if(Palette[i][2]<Palette[i+1][2])
						PaletteChange(i);
				}
			}
		}
	}		
}
//====================================================================================

//====================================================================================
void PaletteIndex()							//將影像轉成Palette Index
{
	int i, j, k;		
	int CountOfIndex;	
	
	CountOfIndex=0;
	
	for(i=0; i<im_height; i++){
		for(j=0; j<im_width; j++){
			for(k=0;k<PaletteNum;k++){
				if((InImage[i][j][0]==Palette[k][0]) && (InImage[i][j][1]==Palette[k][1]) && (InImage[i][j][2]==Palette[k][2])){					
					IndexImage[CountOfIndex]=k;
					CountOfIndex++;
				}
			}
		}
	}	
	if(CountOfIndex != indexsize){
		cout<<"Error!!Size isn't same!! - VQIndex\n";
		exit(1);
	}	
}
//====================================================================================

//====================================================================================
void ComputeDiffOfColors()
{
	cout<<"ComputeDiffOfColors"<<endl;
	int i, j, k;
	double sum;
		
	//建立Palette中每個Color間的Difference
	for(i=0; i<PaletteNum; i++){
		for(j=0; j<PaletteNum; j++){
			sum = 0.0;
			for(k=0; k<ColorDepth; k++)
				sum += (Palette[i][k]-Palette[j][k])*(Palette[i][k]-Palette[j][k]);
			ColorDifference[i][j]=sqrt(sum);
		}
	}
}
//====================================================================================

//====================================================================================
int Product_Palette()
{
	int i, j, k, pn, reseen;
	pn = 0;
	for(i=0;i<im_height;i++){
		for(j=0;j<im_width;j++){
			reseen = 0;
			for(k=0; k<pn; k++){							
				if((Palette[k][0]==InImage[i][j][0]) && (Palette[k][1]==InImage[i][j][1]) && (Palette[k][2]==InImage[i][j][2]))
					reseen = 1;
		    }
		    if(reseen == 0){
		    	Palette[pn][0] = InImage[i][j][0];
		    	Palette[pn][1] = InImage[i][j][1];
		    	Palette[pn][2] = InImage[i][j][2];
		    	pn++;
		    }		    
		}
	}		
	
	return pn;
}
//====================================================================================

//====================================================================================
void ProductCluster()			//讀進Cluster(分群結果)--這裡使用 C 的讀檔方法
{
	cout<<"ProductCluster"<<endl;
	int i,j,k,p,ppp, pi, pj, ci;
	int DCP, timecl, tempclustersize;
	int tempci[ColorNum];
	int IndexCount[ColorNum];
	int appear[ColorNum];
	double MinDiff, MaxDiff;				
	
	//Init.
	for(i=0;i<PaletteNum;i++){
		appear[i] = 0;
		IndexCount[i] = 0;
		sortstack[i] = 0;
		ClusterSize[i] = 1;
		ClusterIndex[i][0] = i;
	}
	tempclustersize = PaletteNum;
	
	DCP = PaletteNum-ClusterNum;		
	
	//計算Index出現次數
	for(i=0;i<im_height;i++){
		for(j=0;j<im_width;j++){
			IndexCount[IndexImage[i*im_width+j]]++;
			sortstack[IndexImage[i*im_width+j]]++;
		}
	}
	
	//for(i=0;i<PaletteNum; i++)
	//	cout<<IndexCount[i]<<" ";
	//cout<<endl;
	
	Quicksort(0, (PaletteNum-1));
	
	timecl = 0;
	ppp = 0;
	while(tempclustersize>ClusterNum && timecl<PaletteNum){
		
		cout<<tempclustersize<<"::"<<ClusterNum<<"  "<<timecl<<endl;
		
		//依據大小(由大到小)找出出現最多次的Index
		for(i=0; i<PaletteNum; i++){			
			if(sortstack[(PaletteNum-1)-ppp] == IndexCount[i] && appear[i]==0){
				appear[i]=1;
				ci = i;
				timecl++;
				break;
			}
		}		
		for(i=0; i<tempclustersize; i++){			
			for(j=0;j<ClusterSize[i];j++){
				if(ci==ClusterIndex[i][j]){
					pi = i;
					pj = j;
				}
			}
		}
		
		/*
		for(i=0; i<tempclustersize; i++){			
			for(j=0;j<ClusterSize[i];j++){				
				appear = 0;
				for(k=0; k<timecl; k++){
					if(ClusterIndex[i][j]==tempci[k]){
						appear = 1;
						break;
					}
				}
				if(appear == 0){		//尚未放入tempci[]中
					if(sortstack[(PaletteNum-1)-ppp] == IndexCount[ClusterIndex[i][j]]){
						tempci[timecl]=ClusterIndex[i][j];
						pi = i;
						pj = j;
						timecl ++ ;
						break;
					}
				}
			}
		}
		*/
		
		//找不在本身Cluster中的最相近的color放入cluster當中
		MinDiff = 999999;		
		for(i=0; i<tempclustersize; i++){
			if(i!=pi){
				MaxDiff = 0;
				for(k=0; k<ClusterSize[pi]; k++){
					for(j=0;j<ClusterSize[i];j++){						
						if(ColorDifference[ClusterIndex[pi][k]][ClusterIndex[i][j]]>MaxDiff)
							MaxDiff = ColorDifference[ClusterIndex[pi][k]][ClusterIndex[i][j]];
					}
				}
				if(MaxDiff<MinDiff){
					MinDiff = MaxDiff;
					p=i;
				}
			}
		}
		
		if(MinDiff<=Tv){		//合併 pi和p 這兩個Cluster	
			cout<<"pi"<<pi<<" :: p"<<p<<endl;		
			for(i=0; i<ClusterSize[p]; i++){
				ClusterIndex[pi][ClusterSize[pi]] = ClusterIndex[p][i];
				ClusterSize[pi]++;
			}			
			for(i=p; i<(tempclustersize-1); i++){
				ClusterSize[i] = ClusterSize[i+1];
				for(j=0; j<ClusterSize[i+1]; j++){
					ClusterIndex[i][j]=ClusterIndex[i+1][j];
				}
			}
			
			tempclustersize--;			
			
			for(i=0;i<tempclustersize;i++)
				cout<<ClusterSize[i]<<" ";	
			cout<<endl;
		}
		ppp++;						
	}
	
	if(timecl==PaletteNum)
		ClusterNum = tempclustersize;
	
	//==Show Information
	cout<<"Tv: "<<Tv<<endl;
	cout<<"Number of Cluster is "<<ClusterNum<<endl;
	cout<<"Every Cluster Size is:"<<endl;
	for(i=0;i<ClusterNum;i++)
		cout<<ClusterSize[i]<<" ";	
	cout<<endl;
	
	for(i=0;i<ClusterNum;i++){
		for(j=0;j<ClusterSize[i];j++){
			cout<<ClusterIndex[i][j]<<" ";
		}
		cout<<" ; ";
	}
	cout<<endl;
	
}
//====================================================================================

//====================================================================================
void ReadBMP(char inputname[25])	//讀影像檔(.Raw)
{
	int i, j, k;
	char ch;		
	ifstream infile(inputname,ios::binary);
	for(i=0;i<im_height;i++){
		for(j=0;j<im_width;j++){
			for(k=0; k<ColorDepth; k++){
				infile.get(ch);				
				if (infile.eof())
					break;	
				else
					InImage[i][j][k] = ch;	
			}
		}
	}
	infile.close();	
}
//====================================================================================

//====================================================================================
void WriteIndex(char ClusterFileName[50]){	
	
	FILE *wcb;
	int i, j,k;
	unsigned int tempci[ColorNum];
	if ((wcb=fopen(ClusterFileName,"wb"))==NULL){
		cout<<"Unable to write Cluster.txt."<<endl;
		exit(1);
	}
	/*
	cout<<endl<<"MinFitness is "<<bestFitness<<endl;
	for(i=0;i<BestChromosomeSize;i++){
		cout<<setw(4)<<OutSize[i];		
	}
	cout<<endl<<"================"<<endl;
	for(i=0;i<BestChromosomeSize;i++){
		for(j=0;j<OutSize[i];j++)
			cout<<setw(4)<<OutIndex[i][j];
		cout<<endl;
	}
	*/
	
	//記錄分群數目
	fwrite(&ClusterNum,sizeof(unsigned int),1,wcb);
	//記錄每個群的大小
	fwrite(ClusterSize,sizeof(unsigned int),ClusterNum,wcb);
	//記錄各自的index
	k=0;
	for(i=0;i<ClusterNum;i++){  	
		for(j=0;j<ClusterSize[i];j++){
   			tempci[k]=ClusterIndex[i][j];
   			k++;
    	}    	   			      		  					
	}	
	fwrite(tempci,sizeof(unsigned int),PaletteNum,wcb);
	
	fclose(wcb);
}
//====================================================================================

//====================================================================================
void InputErrorPrintf()
{
	//		  0		  1		  2	      3       4			//
	cout<<"$HCDHPI [Item1] [Item2] [Item3] [Item4] [Item5]"<<endl;
	cout<<"	$HCDHPI [Stego-Image File] [Image Height] [Image Width] [Tv] [Clustering Size]"<<endl;
	exit(1);
}
//====================================================================================

//====================================================================================
int main(int argc, char* argv[])
{
	int i, j, k;
	double ms, ps;
	char ClusterIndexFile[40]="OCluster_";		
	
	if(argc!=6 )
		InputErrorPrintf();	
	
	//先將高和寬讀入::因為讀圖檔需要"高"和"寬"
	im_height = 0;	
	for(i=0;i<strlen(argv[2]);i++){
		if( 48<=argv[2][i] && argv[2][i]<=57)
			im_height = im_height*10 + argv[2][i]-48;
	}		
	im_width = 0;	
	for(i=0;i<strlen(argv[3]);i++){
		if( 48<=argv[3][i] && argv[3][i]<=57)
			im_width = im_width*10 + argv[3][i]-48;
	}
	if(im_height>max_size || im_width>max_size){
		cout<<"超過Image Size!!"<<endl;
		exit(1);
	}
	indexsize = im_height*im_width;
	
	//==讀檔==		
	ReadBMP(argv[1]);					//讀入cover image
	PaletteNum = Product_Palette();		//將cover image的調色盤產生出來,得到調色盤的顏色總數
	//========
	
	//==調色盤分群資訊==
	SortPalette();						//將調色盤中所有的顏色做大小的排序
	PaletteIndex();						//將每個Pixel用Index來表示
	ComputeDiffOfColors();				//建立Palette中每個的Color間的Difference
		
	Tv = 0;
	for(i=0;i<strlen(argv[4]);i++){
		if( 48<=argv[4][i] && argv[4][i]<=57)
			Tv = Tv*10 + argv[4][i]-48;
	}
	
	ClusterNum = 0;
	for(i=0;i<strlen(argv[5]);i++){
		if( 48<=argv[5][i] && argv[5][i]<=57)
			ClusterNum = ClusterNum*10 + argv[5][i]-48;
	}
	if(ClusterNum>PaletteNum){
		cout<<"Cluster Size超過Palette Size!!"<<endl;
		cout<<"The number of the palette is "<<PaletteNum<<endl;
		exit(1);
	}
	ProductCluster();						
	
	strcat(ClusterIndexFile, argv[1]);
	strcat(ClusterIndexFile, "_");
	strcat(ClusterIndexFile, argv[5]);
	strcat(ClusterIndexFile, ".txt");
	WriteIndex(ClusterIndexFile);
	
	return 0;
}
//====================================================================================

