import java.awt.image.BufferedImage;
import java.io.File;
import javax.imageio.ImageIO;
import java.io.IOException;


// 元画像のRGBを格納するクラス(bitの３次元配列)
class ColorCube
{
	private int m_data[];

	// 初期化
	public ColorCube()
	{
		// intは32bitなので、256x256x256を32で割っている
		m_data = new int[ 256 * 256 * 256 / 32 ];
		// 全データを0にする
		for ( int i = 0; i < m_data.length; ++ i ) m_data[ i ] = 0;
	}

	
	// RGBの値から配列の添え字を計算
	public int data_position( int r, int g, int b )
	{
		if ( ( 0 > r ) || ( 255 < r ) ) return -1;
		if ( ( 0 > g ) || ( 255 < g ) ) return -1;
		if ( ( 0 > b ) || ( 255 < b ) ) return -1;

		return ( ( r * 256 + g ) * 256 + b ) / 32;
	}
	

	// 指定のRGBの位置にbit=1を設定
	public boolean set( int r, int g, int b )
	{
		int dpos;

		dpos = data_position( r, g, b );
		if ( 0 > dpos ) return false;

		//
		m_data[ dpos ] = m_data[ dpos ] |
				 ( (int)0x80000000 >> ( b % 32 ) );

		return true;
	}
	

	// 指定のRGBの位置のbitが1かを判定
	public boolean get( int r, int g, int b )
	{
		int dpos;

		dpos = data_position( r, g, b );
		if ( 0 > dpos ) return false;

		//
		if ( 0 != ( m_data[ dpos ] &
			 ( (int)0x80000000 >> ( b % 32 ) ) ) ) return true;

		return false;
	}


	// 指定のRGBの範囲のbit=1の個数を返す
	public int pixel_number( int rmin, int rmax, int gmin, int gmax,
								 int bmin, int bmax )
	{
		int r, g, b;
		int pixnum;

		pixnum = 0;
		for ( r = rmin; r <= rmax; ++ r ) {
			for ( g = gmin; g <= gmax; ++ g ) {
				for ( b = bmin; b <= bmax; ++ b ) {
					if ( true == get( r, g, b ) ) ++ pixnum;
				}
			}
		}

		return pixnum;
	}


	// 指定のRGBの範囲をR軸で半分に分けるr値を返す
	public int get_median_r( int rmin, int rmax,
					 int gmin, int gmax, int bmin, int bmax )
	{
		int r, rrange;
		int pixnum[], pnum, pixtotal, pixhalf;
		
		rrange = rmax - rmin + 1;
		if ( 0 > rrange ) return rmin;

		//
		pixnum = new int[ rrange ];
		for ( int i = 0; i < rrange; ++ i ) pixnum[ i ] = 0;

		//
		pixtotal = 0;
		for ( r = rmin; r <= rmax; ++ r ) {
			pixnum[ r - rmin ] = pixel_number( r, r, gmin, gmax,
									 bmin, bmax );
			pixtotal = pixtotal + pixnum[ r - rmin ];
		}

		//
		pixhalf = pixtotal / 2;
		pnum = 0;
		for ( r = rmin; r <= rmax; ++ r ) {
			if ( ( pnum + pixnum[ r - rmin ] ) >= pixhalf ) return r;
			pnum = pnum + pixnum[ r - rmin ];
		}

		//
		return -1;
	}


	// 指定のRGBの範囲をG軸で半分に分けるg値を返す
	public int get_median_g( int rmin, int rmax,
					 int gmin, int gmax, int bmin, int bmax )
	{
		int g, grange;
		int pixnum[], pnum, pixtotal, pixhalf;
		
		grange = gmax - gmin + 1;
		if ( 0 > grange ) return gmin;

		//
		pixnum = new int[ grange ];
		for ( int i = 0; i < grange; ++ i ) pixnum[ i ] = 0;

		//
		pixtotal = 0;
		for ( g = gmin; g <= gmax; ++ g ) {
			pixnum[ g - gmin ] = pixel_number( rmin, rmax, g, g,
									 bmin, bmax );
			pixtotal = pixtotal + pixnum[ g - gmin ];
		}

		//
		pixhalf = pixtotal / 2;
		pnum = 0;
		for ( g = gmin; g <= gmax; ++ g ) {
			if ( ( pnum + pixnum[ g - gmin ] ) >= pixhalf ) return g;
			pnum = pnum + pixnum[ g - gmin ];
		}

		//
		return -1;
	}


	// 指定のRGBの範囲をB軸で半分に分けるb値を返す
	public int get_median_b( int rmin, int rmax,
					 int gmin, int gmax, int bmin, int bmax )
	{
		int b, brange;
		int pixnum[], pnum, pixtotal, pixhalf;
		
		brange = bmax - bmin + 1;
		if ( 0 > brange ) return bmin;

		//
		pixnum = new int[ brange ];
		for ( int i = 0; i < brange; ++ i ) pixnum[ i ] = 0;

		//
		pixtotal = 0;
		for ( b = bmin; b <= bmax; ++ b ) {
			pixnum[ b - bmin ] = pixel_number( rmin, rmax, gmin, gmax,
										 b, b );
			pixtotal = pixtotal + pixnum[ b - bmin ];
		}

		//
		pixhalf = pixtotal / 2;
		pnum = 0;
		for ( b = bmin; b <= bmax; ++ b ) {
			if ( ( pnum + pixnum[ b - bmin ] ) >= pixhalf ) return b;
			pnum = pnum + pixnum[ b - bmin ];
		}

		//
		return -1;
	}
}


// 分割されたRGBの範囲と含まれる色の個数を格納するクラス
class ColorCore
{
	public int rmin = 0, rmax = 0;
	public int gmin = 0, gmax = 0;
	public int bmin = 0, bmax = 0;
	public int pixnumber = 0;
}


// メディアンカット本体
public class MedianCut {
	public static void main( String[] args ) {
		boolean result;		// 結果格納フラグ
		int     maxcorecount;	//減色後の色数

		// ColorCube
		ColorCube cube = new ColorCube();

		// ColorCore
		int corenumber;
		ColorCore core[];

		// ファイル名
		String inname, outname;
		// 画像格納クラス
		BufferedImage img = null;

		// 入力した引数が3つ以上かを調べる
		if ( 3 > args.length ) {
			// 入力した引数が２つ未満の場合、使用方法を表示する
			System.out.println(
				 "MedianCut [入力JPEG名] [出力JPEG名] [色数]" );
			return;
		}

		// 入力JPEG名をinnameに代入（拡張子".jpg"省略なし）
		inname  = args[ 0 ];
		// 出力JPEG名をoutnameに代入（拡張子".jpg"省略なし）
		outname = args[ 1 ];
		
		// 引数を変換し、コア数に代入
		try {
			maxcorecount = Integer.valueOf( args[ 2 ] );
			if ( 2 > maxcorecount ) {
				System.out.println( "色数を２以上を指定してください" );
				return;
			}
			core = new ColorCore[ maxcorecount ];
		}
		catch( NumberFormatException ne )
		{
			System.out.println( "引数が不正です" );
			return;
		}		
		
		// JPEGの読み込み
		try {
			// inname(入力JPEG)を読み込んでimgにセット
			img = ImageIO.read( new File( inname ) );
		} catch (Exception e) {
			// inname(入力JPEG)の読み込みに失敗したときの処理
			 e.printStackTrace();
			return;
		}

		// 画像の色の持ち方をチェック
		if ( BufferedImage.TYPE_3BYTE_BGR != img.getType() )
		{
			System.out.println( "対応していないカラーモデルです！("
									 + inname +")" );
			return;
		}

		// 減色処理
		int x, y;
		int width, height;
		int r, g, b, color;
		int rmin, rmax;
		int gmin, gmax;
		int bmin, bmax;
		int dr, dg, db, dmax;
		int maxcore, maxpix;
		int cutp;

		// 画像サイズの取得
		width = img.getWidth();
		height= img.getHeight();

		// ColorCubeにRGB値を格納
		rmin = gmin = bmin = 256;
		rmax = gmax = bmax = -1;
		for ( y = 0; y < height; ++ y ) {
			for ( x = 0; x < width; ++ x ) {
				// (x,y)の色を取得
				color = img.getRGB( x, y );

				// 色をr,g,bに分解
				r = ( color >> 16 ) & 0xff;
				g = ( color >> 8 ) & 0xff;
				b = color & 0xff;

				// ColorCubeにrgbを格納
				cube.set( r, g, b );

				// rの範囲をrmin,rmaxに格納
				if ( r < rmin ) rmin = r;
				if ( r > rmax ) rmax = r;

				// gの範囲をgmin,gmaxに格納
				if ( g < gmin ) gmin = g;
				if ( g > gmax ) gmax = g;

				// bの範囲をbmin,bmaxに格納
				if ( b < bmin ) bmin = b;
				if ( b > bmax ) bmax = b;
			}
		}

		// ColorCubeから減色テーブルを作成する

		// core[]の初期値を設定
		corenumber = 0;
		core[ corenumber ] = new ColorCore();
		core[ corenumber ].rmin = rmin;
		core[ corenumber ].rmax = rmax;
		core[ corenumber ].gmin = gmin;
		core[ corenumber ].gmax = gmax;
		core[ corenumber ].bmin = bmin;
		core[ corenumber ].bmax = bmax;
		core[ corenumber ].pixnumber = cube.pixel_number( rmin, rmax,
							 gmin, gmax, bmin, bmax );
		++ corenumber;

		// coreの数がmaxcorecountになるまで実行
		while ( corenumber < maxcorecount ) {
			// core[]の中でが画素数が最大のものを選択
			maxcore = 0;
			maxpix = 0;
			for ( int i = 0; i < corenumber; ++ i ) {
				if ( ( 0 == i ) || ( core[ i ].pixnumber > maxpix ) ) {
					maxcore = i;
					maxpix = core[ i ].pixnumber;
				}
			}

			rmin = core[ maxcore ].rmin;
			rmax = core[ maxcore ].rmax;
			gmin = core[ maxcore ].gmin;
			gmax = core[ maxcore ].gmax;
			bmin = core[ maxcore ].bmin;
			bmax = core[ maxcore ].bmax;

			// 選択したcoreのr,g,bの範囲をdr,dg,dbに代入
			dr = rmax - rmin;
			dg = gmax - gmin;
			db = bmax - bmin;
		
			// dr,dg,dbの最大値を求める
			dmax = Math.max( dr, Math.max( dg, db ) );
			if ( 0 == dmax ) break;

			// dr,dg,dbのうち、最大の成分でcoreを分割
			if ( dmax == dr ) {
				// r成分でcoreを分割

				// 分割するrをcutpに代入
				cutp = cube.get_median_r( rmin, rmax, gmin, gmax,
										 bmin, bmax );
				if ( rmin > cutp ) break;
				// 分割処理
				core[ corenumber ] = new ColorCore();
				core[ corenumber ].rmin = cutp + 1;
				core[ corenumber ].rmax = core[ maxcore ].rmax;
				core[ corenumber ].gmin = core[ maxcore ].gmin;
				core[ corenumber ].gmax = core[ maxcore ].gmax;
				core[ corenumber ].bmin = core[ maxcore ].bmin;
				core[ corenumber ].bmax = core[ maxcore ].bmax;
				core[ corenumber ].pixnumber
					 = cube.pixel_number( cutp + 1, rmax, gmin, gmax,
										 bmin, bmax );
				++ corenumber;
				//
				core[ maxcore ].rmax = cutp;
				core[ maxcore ].pixnumber
					 = cube.pixel_number( rmin, cutp, gmin, gmax,
									 bmin, bmax );
			}
			else {
				if ( dmax == dg ) {
					// g成分でcoreを分割

					// 分割するgをcutpに代入
					cutp = cube.get_median_g( rmin, rmax, gmin, gmax,
										 bmin, bmax );
					if ( gmin > cutp ) break;
					// 分割処理
					core[ corenumber ] = new ColorCore();
					core[ corenumber ].rmin = core[ maxcore ].rmin;
					core[ corenumber ].rmax = core[ maxcore ].rmax;
					core[ corenumber ].gmin = cutp + 1;
					core[ corenumber ].gmax = core[ maxcore ].gmax;
					core[ corenumber ].bmin = core[ maxcore ].bmin;
					core[ corenumber ].bmax = core[ maxcore ].bmax;
					core[ corenumber ].pixnumber
						 = cube.pixel_number( rmin, rmax,
									 cutp + 1, gmax, bmin, bmax );
					++ corenumber;
					//
					core[ maxcore ].gmax = cutp;
					core[ maxcore ].pixnumber
						 = cube.pixel_number( rmin, rmax,
									 gmin, cutp, bmin, bmax );
				}
				else {
					// b成分でcoreを分割

					// 分割するbをcutpに代入
					cutp = cube.get_median_b( rmin, rmax, gmin, gmax,
										 bmin, bmax );
					if ( bmin > cutp ) break;
					// 分割処理
					core[ corenumber ] = new ColorCore();
					core[ corenumber ].rmin = core[ maxcore ].rmin;
					core[ corenumber ].rmax = core[ maxcore ].rmax;
					core[ corenumber ].gmin = core[ maxcore ].gmin;
					core[ corenumber ].gmax = core[ maxcore ].gmax;
					core[ corenumber ].bmin = cutp + 1;
					core[ corenumber ].bmax = core[ maxcore ].bmax;
					core[ corenumber ].pixnumber
						 = cube.pixel_number( rmin, rmax,
									 gmin, gmax, cutp + 1, bmax );
					++ corenumber;
					//
					core[ maxcore ].bmax = cutp;
					core[ maxcore ].pixnumber 
						= cube.pixel_number( rmin, rmax, gmin, gmax,
										 bmin, cutp );
				}
			}
		}

		// ColorCubeから減色テーブルを作成する
		int index_r[] = new int[ corenumber ];
		int index_g[] = new int[ corenumber ];
		int index_b[] = new int[ corenumber ];
		
		for ( int i = 0; i < corenumber; ++ i ) {
			// 色はコアの中心とする
			index_r[ i ] = ( core[ i ].rmin  + core[ i ].rmax ) / 2;
			index_g[ i ] = ( core[ i ].gmin  + core[ i ].gmax ) / 2;
			index_b[ i ] = ( core[ i ].bmin  + core[ i ].bmax ) / 2;
		}

		// 元の画像の色を減色する
		int l, minl;
		int rl, gl, bl;
		int searchindex;
		int newcolor;
		
		for ( y = 0; y < height; ++ y ) {
			for ( x = 0; x < width; ++ x ) {
				// (x,y)の色を取得
				color = img.getRGB( x, y );

				// 色をr,g,bに分解
				r = ( color >> 16 ) & 0xff;
				g = ( color >> 8 ) & 0xff;
				b = color & 0xff;

				// r,g,bに最も近い色をindexから検索
				rl = r - index_r[ 0 ];
				gl = g - index_g[ 0 ];
				bl = b - index_b[ 0 ];
				minl = rl * rl + gl * gl + bl * b;
				searchindex = 0;

				for ( int i = 1; i < corenumber; ++ i ) {
					//
					rl = r - index_r[ i ];
					gl = g - index_g[ i ];
					bl = b - index_b[ i ];
					l = rl * rl + gl * gl + bl * bl;
					if ( l < minl ) {
						minl = l;
						searchindex = i;
					}
				}
				
				// 最も近い色をr,g,bに設定
				r = index_r[ searchindex ];
				g = index_g[ searchindex ];
				b = index_b[ searchindex ];
				
				// r,g,bの色を合成
				newcolor = ( r << 16 ) + ( g << 8 ) + b;

				// 合成した色を(x,y)に設定
				img.setRGB( x, y, newcolor );
			}
		}

		//　色を変更した画像を保存
		try {
			// imgをoutname(出力JPEG)に保存
			result = ImageIO.write( img, "jpeg", new File( outname ) );
		} catch ( Exception e ) {
			// outname(出力JPEG)の保存に失敗したときの処理
			e.printStackTrace();
			return;
		}

		// 正常に終了
		System.out.println( "正常に終了しました" );
	}
}