#include <iostream>
#include <vector>

#include "MakePalette.h"
#include "CBitMap.h"

using namespace std;


// フォントを作成する
void MakeFont( const char *infile, const char *outfile)
{
	CBitMap bmp( infile);

	if ( 0 >= bmp.GetImageSize())
	{
		cout << "ファイルのオープンに失敗" << endl;
		return;
	}
	if ( 24 != bmp.GetColorBit())
	{
		cout << "24bitじゃありません" << endl;
		return;
	}

	// パレットデータ
	Palette	palette;
	int	width =  bmp.GetWidth();
	int height =  bmp.GetHeight();

	// ビットマップデータが８の倍数の矩形であることをチェック
	if ( 0 != width % 8 || 0 != height % 8)
	{
		cout << "画像データのサイズが不正" << endl;
		return;
	}

	unsigned char *buf = new unsigned char[ bmp.GetImageSize()];
	bmp.GetImageData( buf);

	CreatePalette( palette, buf, width, height);

	// 15色に減色する
	ReducePalette( palette, 15);

	CreateFontFromPaletteBmp( buf, palette, width, height);

/*
	BITMAPINFOHEADER	tab;
	ZeroMemory( &tab, sizeof( BITMAPINFOHEADER));
	tab.biSize = sizeof( BITMAPINFOHEADER);
	tab.biWidth = bmp.GetWidth();
	tab.biHeight = bmp.GetHeight();
	tab.biSizeImage = bmp.GetImageSize();
	tab.biPlanes = 1;
	tab.biBitCount = bmp.GetColorBit();

	 CBitMap des( (( BITMAPINFO *)&tab), buf, bmp.GetImageSize());
	des.SaveBitmapFile( outfile);
*/
	delete[] buf;

	ofstream file( outfile);
	CreateFontFromPaletteText( file, palette, width, height);
}


// フォントを作成する
void MakeFontChips( const char *infile, const char *outfile)
{
	CBitMap bmp( infile);

	if ( 0 >= bmp.GetImageSize())
	{
		cout << "ファイルのオープンに失敗" << endl;
		return;
	}
	if ( 24 != bmp.GetColorBit())
	{
		cout << "24bitじゃありません" << endl;
		return;
	}
	// パレットデータ
	PaletteList	PalList;
	int	width =  bmp.GetWidth();
	int height =  bmp.GetHeight();

	// ビットマップデータが８の倍数の矩形であることをチェック
	if ( 0 != width % 8 || 0 != height % 8)
	{
		cout << "画像データのサイズが不正" << endl;
		return;
	}

	unsigned char *buf = new unsigned char[ bmp.GetImageSize()];
	bmp.GetImageData( buf);

	// 画像全体を8*8チップとしてすべてをパレットデータにまとめる
	for ( int j = 0; j < height; j += 8)
	{
		for ( int i = 0; i < width; i += 8)
		{
			Palette tmpPalette;
			CreatePaletteCips( tmpPalette, buf, width, height, i, j, 8);
			// 15色に減色する
			ReducePalette( tmpPalette, 15);
			// 減色した結果同じパレットになった時は合わせてしまう
			PaletteList::iterator pal = SearchIncludedPalette( PalList, tmpPalette);
			if ( PalList.end() != pal)
				MergePalette( *pal, tmpPalette);
			else
				PalList.push_back( tmpPalette);
		}
	}
	cout << "ファイルの読み込み成功" << endl;

	// パレットを減らしていく
	cout << "減色処理を開始します" << endl;
	while ( PalList.size() > 16)
	{
		cout << "現在のパレット数:" << dec << PalList.size() << endl;
		PaletteList::iterator first, second;
#ifdef _DEBUG
		DWORD distance = SerchMinimumPalette( &first, &second, PalList);
#else
		DWORD distance = SerchMinimumPaletteSlow( &first, &second, PalList);
#endif
		_ASSERT( first != second);
		AddPalette( *first, *second);
		ReducePalette( *first, 15);
		PalList.erase( second);
	}
	cout << "減色完了" << endl;

/*	デバッグ用 BMPファイルを吐き出す

	for ( PaletteList::iterator ite = PalList.begin(); ite != PalList.end(); ++ite)
	{
		CreateFontFromPaletteBmp( buf, *ite, width, height);
	}

	BITMAPINFOHEADER	tab;
	ZeroMemory( &tab, sizeof( BITMAPINFOHEADER));
	tab.biSize = sizeof( BITMAPINFOHEADER);
	tab.biWidth = bmp.GetWidth();
	tab.biHeight = bmp.GetHeight();
	tab.biSizeImage = bmp.GetImageSize();
	tab.biPlanes = 1;
	tab.biBitCount = bmp.GetColorBit();


	CBitMap des( (( BITMAPINFO *)&tab), buf, bmp.GetImageSize());
	des.SaveBitmapFile( outfile);
*/
	delete[] buf;

	// テキストファイルに書き出していく
	ofstream file( outfile);
	CreateFontFromPaletteChipsText( file, PalList, width, height);
	cout << "ファイルへの出力完了" << endl;
}


// パレットを合わせる 前もってlhsパレットにrhsパレットが使っている色が含まれることを
// 調べておくこと
// 二つのパレットを合成して，新しいパレットを作る
void MergePalette( Palette &lhs, Palette &rhs)
{
	Palette::iterator i;
	for ( i = rhs.begin(); i != rhs.end(); ++i)
	{
		// 結合先の色を検索
		Palette::iterator ins = FindColor( lhs.begin(), lhs.end(), i->GetColor());
		_ASSERT( lhs.end() != ins);
		// パレットに格納
		ins->AddPixelList( *i);
	}
}

// 単純にパレットを加え合わせる
void AddPalette( Palette &lhs, const Palette &rhs)
{
	for ( Palette::const_iterator i = rhs.begin(); i != rhs.end(); ++i)
	{
		// 挿入先カラーを探す
		Palette::iterator ins = FindColor( lhs.begin(), lhs.end(), i->GetColor());
		if ( lhs.end() == ins)
			lhs.push_back( *i);
		else
			ins->AddPixelList( *i);
	}
}

// パレット内の色数を指定の色数にに減色する
void ReducePalette( Palette &palette, const int color)
{
	// 減色する
	while ( palette.size() > color)
	{
		Palette::iterator	first, second;
		SearchMinimumDistance( palette.begin(), palette.end(), first, second);
		first->Merge( &(*second));
		palette.erase( second);
	}
}

// パレット内のカラーがすべて同一かどうか調べる
bool ComparePaletteColor( const Palette &lhs, const Palette &rhs)
{
	if ( lhs.size() != rhs.size())
		return false;

	Palette::const_iterator	i;
	for ( i = lhs.begin(); i != lhs.end(); ++i)
	{
		if ( rhs.end() == FindColor( rhs.begin(), rhs.end(), i->GetColor()))
			return false;
	}
	return true;
}

// rhsパレットがlhsパレットに含まれているかどうかを調べる
bool PaletteIncluded( const Palette &lhs, const Palette &rhs)
{
	if ( lhs.size() < rhs.size())
		return false;

	Palette::const_iterator	i;
	for ( i = rhs.begin(); i != rhs.end(); ++i)
	{
		if ( lhs.end() == FindColor( lhs.begin(), lhs.end(), i->GetColor()))
			return false;
	}
	return true;
}

// 同じカラーデータの組を持つパレットを探す
PaletteList::iterator SearchSameColorPalette( PaletteList &List, const Palette &tmpPalette)
{
	PaletteList::iterator i;
	for ( i = List.begin(); i != List.end() && !ComparePaletteColor( *i, tmpPalette); ++i)
		;
	return i;
}

// カラーデータを内包しているパレットを探す
PaletteList::iterator SearchIncludedPalette( PaletteList &List, const Palette &tmpPalette)
{
	PaletteList::iterator i;
	for ( i = List.begin(); i != List.end() && !PaletteIncluded( *i, tmpPalette); ++i)
		;
	return i;
}

// 24Bitビットマップデータとして，ビットマップを作成する
void CreateFontFromPaletteBmp(  BYTE *bmp, const Palette &SourcePalette, const int width, const int height)
{
	// パレットをビットマップに展開する

	Palette::const_iterator i;
	for ( i = SourcePalette.begin(); i != SourcePalette.end(); i++)
	{
		RgbColor Col( i->GetColor());
		Col <<= 4;
		PixelList PiLi( i->GetPixelList());

		for ( PixelList::const_iterator j = PiLi.begin(); j != PiLi.end(); j++)
		{
			int index = (( height - j->y() - 1) * width + j->x()) * 3;
			_ASSERT( index >= 0);
			bmp[ index] = Col.GetRed();
			bmp[ index + 1] = Col.GetGreen();
			bmp[ index + 2] = Col.GetBlue();
		}
	}
}

// 24Bitカラービットマップファイルを処理
// ビットマップから使用している色と，その色を使う画素の対応表を作成する
void CreatePalette( Palette &DestinationPalette, unsigned char *bmp, const int width, const int height)
{
	int i, j;

	// ビットマップデータが８の倍数の矩形であることをチェック
	if ( 0 != width % 8 || 0 != height % 8)
		return;

	// ビットマップデータをすべて操作
	for ( j = height - 1; j >= 0; j--)
	{
		for ( i = 0; i < width; i++)
		{
			RgbColor ColData( bmp[ ( j * width + i) * 3], bmp[ ( j * width + i) * 3 + 1], bmp[ ( j * width + i) * 3 + 2]);
			// バッファに格納して処理する
			// 減色する
			ColData >>= 4;

			Palette::iterator ins = FindColor( DestinationPalette.begin(), DestinationPalette.end(), ColData);
			if ( ins == DestinationPalette.end())
			{
				// 新しくパレットに追加
				DestinationPalette.push_back( PaletteCell( ColData, PixelCoordinates( i, -j - 1 + height)));
			} else {
				// 画素を追加
				ins->AddPixelCoordinates( PixelCoordinates( i, -j - 1 + height));
			}
			_ASSERT(  -j - 1 + height >= 0);
		}
	}
}

// 24Bitカラービットマップファイルを処理
// ビットマップから使用している色と，その色を使う画素の対応表を作成する
// パレット数複数を行う版
// bmp に画像データの先頭へのポインタ
// width に画像全体の幅 (8の倍数)
// height に画像全体の幅 (8の倍数)
// x,yに対象正方形の座標
// squareに正方形の一辺の長さの
void CreatePaletteCips( Palette &DestinationPalette, unsigned char *bmp, const int width, const int height,
					   int x, int y, int square)
{
	int i, j;

	// ビットマップデータをすべて操作
	for ( j = height - 1 - y; j >  height - 1 - y - square; j--)
	{
		for ( i = x; i < x + square; i++)
		{
			RgbColor ColData( bmp[ ( j * width + i) * 3], bmp[ ( j * width + i) * 3 + 1], bmp[ ( j * width + i) * 3 + 2]);
			// バッファに格納して処理する
			// 減色する
			ColData >>= 4;

			Palette::iterator ins = FindColor( DestinationPalette.begin(), DestinationPalette.end(), ColData);
			if ( ins == DestinationPalette.end())
			{
				// 新しくパレットに追加
				DestinationPalette.push_back( PaletteCell( ColData, PixelCoordinates( i, -j - 1 + height)));
			} else {
				// 画素を追加
				ins->AddPixelCoordinates( PixelCoordinates( i, -j - 1 + height));
			}
			_ASSERT(  -j - 1 + height >= 0);
		}
	}
}

// パレットデータの最小ノルムとそのパレットセルへのイテレータを計算する
// 引数:
//     first: 一つ目のカラーデータへのイテレータを受け取る
//     second: 二つ目のカラーデータへのイテレータを受け取る
int SearchMinimumDistance( Palette::iterator begin, Palette::iterator end,
								  Palette::iterator &first, Palette::iterator &second)
{
	int MinimumDistance = INT_MAX;
	Palette::iterator i, j;

	for ( i = begin; i != end; ++i)
	{
		for ( j = i, ++j; j != end; ++j)
		{
			int dis = i->GetColor().Distance( j->GetColor());
			if ( dis < MinimumDistance)
			{
				MinimumDistance = dis;
				first = i;
				second = j;
			}
		}
	}
	return MinimumDistance;
}


// 指定したものと同じ色を探す
Palette::iterator FindColor( Palette::iterator first, Palette::iterator last, const RgbColor &Target)
{
	for ( 	Palette::iterator i = first; i != last && !i->CompareColor( Target); ++i)
		;
	return i;
}


Palette::const_iterator FindColor( Palette::const_iterator first, Palette::const_iterator last, const RgbColor &Target)
{
	for ( Palette::const_iterator i = first; i != last && !i->CompareColor( Target); ++i)
		;
	return i;
}

// 一番近い色を探すとの距離を返す
int FindNearColorDistance( Palette::const_iterator begin, Palette::const_iterator end, const RgbColor &Target)
{
	int minimum = INT_MAX;
	for ( Palette::const_iterator i = begin; i != end && minimum != 0; ++i)
	{
		int tmp = Target.Distance( i->GetColor());
		if ( tmp < minimum)
			minimum = tmp;
	}
	return minimum;
}


// パレットデータ内のカラーデータの和を取って
// 代表値(ベクトル)を作成する
ColorVector MakeVector( Palette::const_iterator begin, Palette::const_iterator end)
{
	if ( begin == end)
		return ColorVector();

	Palette::const_iterator i = begin;
	ColorVector vec( i->GetColor());
	int num = i->GetPixelListSize();
	++i;
	for ( ; i != end; ++i)
	{
		// すべてのパレットカラーに対して加重平均を取っていく
		vec = vec.WeightedMean( num, i->GetColor(), i->GetPixelListSize());
		num += i->GetPixelListSize();
	}
	return vec;
}



// 一番近いと思われるパレットをさがす．
// 検索結果をfirstとsecondに格納して返す
DWORD SerchMinimumPalette( PaletteList::iterator *first, PaletteList::iterator *second, PaletteList &Source)
{
	unsigned int MinimumDistance = UINT_MAX;
	PaletteList::iterator i, j;
	int k, l, distance;

	vector< ColorVector>	VecList;
	VecList.reserve( Source.size());

	// 各パレットの代表値を求める
	for ( i = Source.begin(); i != Source.end(); i++)
		VecList.push_back( MakeVector( i->begin(), i->end()));
	// 最も近い組み合わせを見つける
	for ( k = 0, i = Source.begin(); k < VecList.size() - 1; ++k, ++i)
	{
		j = i;
		for ( l = k + 1, ++j; l < VecList.size(); ++l, ++j)
		{
			_ASSERT( j != Source.end());
			_ASSERT( i != j);

			DWORD dis = VecList[ k].DisVector( VecList[ l]);
			if ( dis < MinimumDistance)
			{
				// 出力用のデータを作成する
				MinimumDistance = dis;
				distance = PaletteDistance( i->begin(), i->end(), j->begin(), j->end());
				*first = i;
				*second = j;
			}
			else if ( dis == MinimumDistance)	// 最小値が同じだった場合より近いほうを選択
			{
				// パレットの全色比較を行う
				int tmp = PaletteDistance( i->begin(), i->end(), j->begin(), j->end());
				// より近い色の場合は更新する
				if ( tmp < distance)
				{
					*first = i;
					*second = j;
				}
			}
		}
	}
	return MinimumDistance;
}


// 一番近いと思われるパレットをさがす．
// 検索結果をfirstとsecondに格納して返す
// 丁寧に行う
DWORD SerchMinimumPaletteSlow( PaletteList::iterator *first, PaletteList::iterator *second, PaletteList &Source)
{
	unsigned int MinimumDistance = UINT_MAX;
	PaletteList::iterator i, j;

	// 最も近い組み合わせを見つける
	for ( i = Source.begin(); i != Source.end(); ++i)
	{
		j = i;
		for ( ++j; j != Source.end() && 0 != MinimumDistance; ++j)
		{
			// パレットの全色比較を行う
			int dis = PaletteDistance( i->begin(), i->end(), j->begin(), j->end());
			if ( dis < MinimumDistance)
			{
				// 出力用のデータを作成する
				MinimumDistance = dis;
				*first = i;
				*second = j;
			}
		}
	}
	return MinimumDistance;
}




// パレットの全色を比較して
// その類型誤差を返す
int PaletteDistance( Palette::const_iterator lhs_begin, Palette::const_iterator lhs_end,
						 Palette::const_iterator rhs_begin, Palette::const_iterator rhs_end)
{
	int distance = 0;
	for ( Palette::const_iterator i = rhs_begin; i != rhs_end; ++i)
	{
		distance += FindNearColorDistance( lhs_begin, lhs_end, i->GetColor());
	}
	return distance;
}


// パレットデータからフォントデータを作成する
// パレットは15色構成とする
void CreateFontFromPaletteText( ofstream &File, const Palette &SourcePalette, const int width, const int height)
{
	// パレットをビットマップに展開する
	char *map = new char[ height * width];
	memset( map, 0, height * width);

	int index = 0;
	File << "unsigned short pal[16] = {" << endl;
	File << "\t0x000, "; 
	Palette::const_iterator i;
	for ( i = SourcePalette.begin(); i != SourcePalette.end(); ++i, ++index)
	{
		WORD col = i->GetColor().GetBlue();
		col <<= 4;
		col += i->GetColor().GetGreen();
		col <<= 4;
		col += i->GetColor().GetRed();

		File << "0x" << uppercase << hex << col << ", ";

		const PixelList	tmp( i->GetPixelList());
		for ( PixelList::const_iterator j = tmp.begin(); j != tmp.end(); ++j)
			map[ j->y() * width + j->x()] = index + 1;
	}
	File << "};" << endl;

	// テキストデータとして吐き出す
	WriteBuffer( File, map, width, height);
	delete[] map;
}


// パレットデータからフォントデータを作成する
// パレットチップを使った場合用
// パレットは15色構成とする
void CreateFontFromPaletteChipsText( ofstream &File, const PaletteList &PalList, const int width, const int height)
{
	// パレットをビットマップに展開する
	char *map = new char[ height * width];
	memset( map, 0, height * width);

	// ブロック数を計算する
	int BlockX = width / 8;
	int BlockY = height / 8;
	char *PalMap = new char [ BlockX * BlockY];
	memset( PalMap, 0, BlockX * BlockY);

	// パレットを使っているブロック番号を調べる
	PaletteList::const_iterator i;
	int num;
	for ( i = PalList.begin(), num = 0; i != PalList.end(); ++i, ++num)
	{	// numはパレット番号
		CheckBlock( PalMap, i->begin(), i->end(), num, BlockX, BlockY);
	}
	// パレットのデータを書き出す
	File << "unsigned short pal[][ 16] = {" << endl;
	for ( i = PalList.begin(); i != PalList.end(); ++i)
	{
		// mapにパレットのインデクスリストを作成
		// それとともに，パレットのデータを書き出す
		int index = 0;	// パレットナンバー0は透明色
		File << "\t{ 0x000, "; 
		for ( Palette::const_iterator j = i->begin(); j != i->end(); ++j, ++index)
		{
			WORD col = j->GetColor().GetBlue();
			col <<= 4;
			col += j->GetColor().GetGreen();
			col <<= 4;
			col += j->GetColor().GetRed();

			File << "0x" << uppercase << hex << col << ", ";

			// マップにパレットインデクスを書き出す
			const PixelList	tmp( j->GetPixelList());
			for ( PixelList::const_iterator k = tmp.begin(); k != tmp.end(); ++k)
				map[ k->y() * width + k->x()] = index + 1;
		}
		File << "}," << endl;
	}
	File << "};" << endl;

	// 使用パレットのデータを吐き出す
	File << "unsigned char palmask[] = {" << endl;
	for ( int k = 0; k < BlockY; ++k)
	{
		for ( int l = 0; l < BlockX; ++l)
			File << "0x" << hex << static_cast< int>( PalMap[ k * BlockX + l]) << ", ";
		File << endl;
	}
	File << "};" << endl;
	// パレットインデクスデータをテキストデータとして吐き出す
	WriteBuffer( File, map, width, height);

	delete[] PalMap;
	delete[] map;
}


void CheckBlock( char *buf, Palette::const_iterator begin, Palette::const_iterator end, const char value, const int MaxX, const int MaxY)
{
	// パレットに含まれるすべての画素をチェックする
	for ( Palette::const_iterator i = begin; i != end; ++i)
	{
		const PixelList	tmp( i->GetPixelList());
		for ( PixelList::const_iterator j = tmp.begin(); j != tmp.end(); ++j)
		{
			// ブロック番号を調べる
			int index = ( j->y() / 8 * MaxX) + j->x() / 8;
			// 使っているパレット番号を書き込む
			buf[ index] = value;
		}
	}
}

// ビットマップに展開したインデクスデータを書き出す
void WriteBuffer( ofstream &out, const char *buf, const int width, const int height)
{
	// パレットインデクスデータをテキストデータとして吐き出す
	out << "#define bmp_width " << dec << ( width / 8) << endl;
	out << "#define bmp_height " << dec << ( height / 8) << endl;
	out << "unsigned long bmp[] = {" << endl;

	for ( int y = 0; y < height; y += 8)
	{
		for ( int x = 0; x < width; x += 8)
		{
			out << "\t";
			for ( int bit_y = 0; bit_y < 8; bit_y++)
			{
				int label = (y + bit_y) * width + x;
				DWORD index = 0;
				index += ( buf[ label + 6] << 4) + buf[ label + 7];
				index <<= 8;
				index += ( buf[ label + 4] << 4) + buf[ label + 5];
				index <<= 8;
				index += ( buf[ label + 2] << 4) + buf[ label + 3];
				index <<= 8;
				index += ( buf[ label] << 4) +  buf[ label + 1];

				out << "0x" << uppercase << hex << index << ", ";
			}
			out << endl;
		}
		out << endl;
	}
	out << "};" << endl;
}