/**
   RGB成分用パレット構造体
**/
struct RGB
{
  // 型宣言
  typedef unsigned int color_type;    // 色成分の型
  typedef unsigned char primary_type; // RGB各成分の型
  typedef size_t size_type;           // 添字の型

  // 定数宣言
  static const primary_type MAX = UCHAR_MAX; // RGB各成分の最大値
  static const color_type MASK = UCHAR_MAX;  // RGB各成分のマスク
  static const primary_type BIT = CHAR_BIT;  // RGB各成分のビット数

  // 添字定義用定数
  static const size_type RED = 0;       // 赤成分の添字
  static const size_type GREEN = 1;     // 緑成分の添字
  static const size_type BLUE = 2;      // 青成分の添字
  static const size_type ALPHA = 3;     // アルファチャンネル成分の添字
  static const size_type RGB_SIZE = 3;  // (アルファチャンネルを除いた)RGB成分のサイズ
  static const size_type RGBA_SIZE = 4; // RGBA成分のサイズ

  // 公開メンバ変数
  primary_type r; // 赤成分
  primary_type g; // 緑成分
  primary_type b; // 青成分
  primary_type a; // アルファチャンネル

  /* 色コードから各成分を取得する関数 */

  /// 色コードから赤成分を抽出する
  ///
  /// 赤成分は、color_type の下位より 16 から 23 ビットまでとする
  /// ... OOOOOOOO xxxxxxxx xxxxxxxx
  ///
  /// color 対象の色コード
  /// 戻り値 抽出した赤成分
  static primary_type getRed( color_type color ) { return( ( color >> 16 ) & MASK ); }

  /// 色コードから緑成分を抽出する
  ///
  /// 緑成分は、color_type の下位より 8 から 15 ビットまでとする
  /// ... OOOOOOOO xxxxxxxx
  ///
  /// color 対象の色コード
  /// 戻り値 抽出した緑成分
  static primary_type getGreen( color_type color ) { return( ( color >> 8 ) & MASK ); }

  /// 色コードから青成分を抽出する
  ///
  /// 青成分は、color_type の下位より 0 から 7 ビットまでとする
  /// ... OOOOOOOO
  ///
  /// color 対象の色コード
  /// 戻り値 抽出した青成分
  static primary_type getBlue( color_type color ) { return( color & MASK ); }

  /// 色コードからアルファチャンネルを抽出する
  ///
  /// アルファチャンネルは、color_type の下位より 24 から 31 ビットまでとする
  /// ... OOOOOOOO xxxxxxxx xxxxxxxx xxxxxxxx
  ///
  /// color 対象の色コード
  /// 戻り値 抽出したアルファチャンネル
  static primary_type getAlpha( color_type color ) { return( ( color >> 24 ) & MASK ); }

  /* コンストラクタ */

  /// RGB各成分からの構築
  ///
  /// alpha 値を指定しない場合はデフォルト値として RGB::MAX で初期化される
  ///
  /// red 赤成分
  /// green 緑成分
  /// blue 青成分
  /// alpha アルファチャンネル
  RGB( primary_type red, primary_type green, primary_type blue, primary_type alpha = MAX )
    : r( red ), g( green ), b( blue ), a( alpha ) {}
  /// 色コードからの構築
  ///
  /// c 対象の色コード
  /// hasAlpha アルファチャンネルを持つか ?
  RGB( color_type c, bool hasAlpha )
  {
    r = getRed( c );
    g = getGreen( c );
    b = getBlue( c );
    a = ( hasAlpha ) ? getAlpha( c ) : MAX;
  }
  /// デフォルト・コンストラクタ
  ///
  /// RGB 成分は全てゼロ、アルファチャンネルもゼロとする
  RGB() : r( 0 ), g( 0 ), b( 0 ), a( 0 ) {}

  /* 各成分の取得 */

  /// RGB各成分とアルファチャンネルを引数側に渡す
  ///
  /// red 赤成分を渡す変数へのポインタ
  /// green 緑成分を渡す変数へのポインタ
  /// blue 青成分を渡す変数へのポインタ
  /// alpha アルファチャンネルを渡す変数へのポインタ
  void sendToParam( primary_type* red, primary_type* green, primary_type* blue, primary_type* alpha ) const
  {
    if ( red != 0 ) *red = r;
    if ( green != 0 ) *green = g;
    if ( blue != 0 ) *blue = b;
    if ( alpha != 0 ) *alpha = a;
  }

  /// RGB各成分を引数側に渡す
  ///
  /// red 取得した赤成分
  /// green 取得した緑成分
  /// blue 取得した青成分
  void sendToParam( primary_type* red, primary_type* green, primary_type* blue ) const
  {
    if ( red != 0 ) *red = r;
    if ( green != 0 ) *green = g;
    if ( blue != 0 ) *blue = b;
  }

  /// 引数から渡された RGBA 各成分をセットする
  ///
  /// red セットする赤成分
  /// green セットする緑成分
  /// blue セットする青成分
  /// alpha セットするアルファチャンネル
  void receiveFromParam( primary_type red, primary_type green, primary_type blue, primary_type alpha = RGB::MAX )
  { r = red; g = green; b = blue; a = alpha; }

  /// 添字を利用して各成分への参照を返す
  ///
  /// index 対象の成分への添字
  /// 戻り値 対象の成分への参照
  primary_type& operator[]( size_type index );
};

/*
  RGB::operator[] : 添字を利用して各成分への参照を返す

  未定義の size_type が指定された場合、例外を投げるようにしている。
*/
RGB::primary_type& RGB::operator[]( size_type index )
{
  switch ( index ) {
  case RED :
    return( r );
  case GREEN :
    return( g );
  case BLUE :
    return( b );
  case ALPHA :
    return( a );
  default :
    throw std::out_of_range( "Out of range at RGB::operator[]" );
  }
}

/*
  operator&= : RGB どうしの論理積
*/
RGB& RGB::operator&=( RGB mask )
{
  r &= mask.r;
  g &= mask.g;
  b &= mask.b;

  return( *this );
}

/*
  operator&= : 同一成分による RGB との論理積
*/
RGB& RGB::operator&=( primary_type mask )
{
  r &= mask;
  g &= mask;
  b &= mask;

  return( *this );
}
  :

/*
  operator>>= : RGB 各成分の右ビットシフト
*/
RGB& RGB::operator>>=( unsigned int shift )
{
  r >>= shift;
  g >>= shift;
  b >>= shift;

  return( *this );
}
  :

/**
   RGB 成分への処理用関数インターフェース

   RGB 成分に対して処理を行う関数オブジェクトを呼び出す場合に利用するインターフェース。
**/
struct RGB_Op_IF
{
  /// RGB 成分への処理 (純粋仮想関数)
  virtual bool operator()( RGB* rgb ) = 0;

  /// 仮想デストラクタ (何もしない)
  virtual ~RGB_Op_IF() {}
};

/**
   RGB 成分への処理用関数

   RGB 成分に対する演算子の多重定義関数を呼び出すことができる
**/
template<class T> class RGB_Op : public RGB_Op_IF
{
 public:

  typedef RGB& (RGB::*Op)( T ); // RGB 成分に対する演算子の多重定義関数の型

 private:

  Op f_; // RGB 成分に対する演算子の多重定義関数
  T t_;  // f_ に渡す第二引数

 public:

  /* コンストラクタ */

  /// RGB 成分に対する演算子の多重定義関数とその第二引数の値を指定して構築
  ///
  /// 例えば、以下のコードは白色 (FF,FF,FF) をグレー (F0,F0,F0) に変える
  ///
  /// RGB_Op<RGB::primary_type> op( operator&=, 0xF0 );
  /// RGB rgb( 0xFF, 0xFF, 0xFF );
  /// op( &rgb );
  ///
  /// f RGB 成分に対する演算子の多重定義関数
  /// t f に渡す第二引数
  RGB_Op( Op f, const T& t )
   : f_( f ), t_( t ) {}

  /// コンストラクタで指定した多重定義関数 f を呼び出す
  ///
  /// rgb 処理対象の RGB 成分へのポインタ
  /// 戻り値 f が未定義だった場合は false
  virtual bool operator()( RGB* rgb )
  {
    if ( f_ == 0 ) return( false );

    ( rgb->*f_ )( t_ );
    return( true );
  }
};

/**
   色のマスキング用クラス
**/
template<class T> struct MaskColor : public RGB_Op<T>
{
  /* コンストラクタ */

  /// マスクパターンを指定して構築
  ///
  /// mask マスクパターン
  /// andMask 論理積をとるか (true)、論理和をとるか (false)
  MaskColor( const T& mask, bool andMask )
    : RGB_Op<T>( ( ( andMask ) ?
                  static_cast<typename RGB_Op<T>::Op>( &RGB::operator&= ) :
                  static_cast<typename RGB_Op<T>::Op>( &RGB::operator|= ) ),
                mask ) {}
};

/*
  Make_RGBMask : 指定した階調(ビット数) bit のマスクパターンを作成して返す

  bitInv が true なら作成したマスクパターンを反転して返す
*/
RGB::primary_type Make_RGBMask( unsigned char bit, bool bitInv = false )
{
  RGB::primary_type mask = RGB::MAX; // マスクパターン(全ビットを 1 に初期化)

  if ( bit < RGB::BIT )
    for ( unsigned char i = 0 ; i < RGB::BIT - bit ; ++i )
      mask <<= 1;

  return( ( bitInv ) ? ~mask : mask );
}

/**
  色の量子化処理用クラス
**/
struct Quantize : public MaskColor<RGB::primary_type>
{
  /* コンストラクタ */

  /// 階調(ビット数) bit を指定して構築する
  ///
  /// setBit が true ならマスクする下位ビットを 1 に、そうでないならゼロにする
  /// 例えば、bit = 3, setBit = false ならマスクパターンは 1110_0000 になる。
  /// bit = 5, setBit = true とすると、マスクパターンは反転して 0000_0111 になる。
  ///
  /// bit 階調(残すビットの数)
  /// setBit マスクしたビットを ON にするなら true にする
  Quantize( unsigned char bit, bool setBit = false );
};

/**
  色の量子化処理後にコントラストを調整するクラス
**/
class QuantizeAndScaling : public RGB_Op_IF
{
  unsigned char exBit_; // 量子化によって除外するビット数(0-7)
  unsigned int qMax_;   // 量子化後の最大値

 public:

  /* コンストラクタ */

  /// 階調(ビット数) bit を指定して構築する
  ///
  /// bit 階調(残すビットの数)
  QuantizeAndScaling( unsigned char bit );

  /* メンバ関数 */

  /// 色の量子化処理とコントラスト調整を行う
  ///
  /// rgb 処理結果を代入する RGB 構造体へのポインタ
  virtual bool operator()( RGB* rgb );
};

/*
  Quantize コンストラクタ

  階調(ビット数) bit を指定して構築する
  setBit が true ならマスクする下位ビットを 1 に、そうでないならゼロにする
*/
Quantize::Quantize( unsigned char bit, bool setBit )
  : MaskColor<RGB::primary_type>( Make_RGBMask( bit, setBit ), ! setBit ) {}

/*
  QuantizeAndScaling コンストラクタ

  階調(ビット数) bit を指定して構築する
*/
QuantizeAndScaling::QuantizeAndScaling( unsigned char bit )
  : exBit_( ( bit >= RGB::BIT ) ? 0 : RGB::BIT - bit ),
    qMax_( Make_RGBMask( exBit_, true ) ) {}

/*
  QuantizeAndScaling::operator() : 色の量子化とコントラスト調整を行い、結果を rgb に代入する
*/
bool QuantizeAndScaling::operator()( RGB* rgb )
{
  // rgb が未定義な場合 false を返す
  if ( rgb == 0 ) return( false );

  *rgb >>= exBit_;
  rgb->r = RGB::Check_RGBPrimary<unsigned int>
    ( static_cast<unsigned int>( rgb->r ) * static_cast<unsigned int>( RGB::MAX ) / qMax_ );
  rgb->g = RGB::Check_RGBPrimary<unsigned int>
    ( static_cast<unsigned int>( rgb->g ) * static_cast<unsigned int>( RGB::MAX ) / qMax_ );
  rgb->b = RGB::Check_RGBPrimary<unsigned int>
    ( static_cast<unsigned int>( rgb->b ) * static_cast<unsigned int>( RGB::MAX ) / qMax_ );

  return( true );
}

/// 浮動小数点型のデータを小数点以下四捨五入して整数型として返す
///
/// d 対象データ(浮動小数点型)
/// 戻り値 四捨五入した整数値
inline int RoundHalfUp( double d )
{
  if ( d > 0 )
    d += 0.5;
  else
    d -= 0.5;

  return( static_cast<int>( d ) );
}

/*
  MakeDitherMatrix : サイズ size のディザ・マトリックスを dither 上に作成する

  size は 2 のべき数を表すので、実際に作成される行列のサイズは 2 の size 乗になる
  また、size の有効範囲は 1 から CHAR_BIT までとし、
  ゼロなら 1 に、CHAR_BIT より大きければ CHAR_BIT に変換してから処理を行う
*/
void MakeDitherMatrix( unsigned char size, vector<int>* dither )
{
  if ( size == 0 ) size = 1;
  if ( size > CHAR_BIT ) size = CHAR_BIT;
  unsigned int matSize = ( size > 0 ) ? ( 1 << size ) : 2;
  dither->resize( matSize * matSize );

  // 2 x 2 サイズで初期化
  ( *dither )[0] = 0;
  ( *dither )[1] = 2;
  ( *dither )[matSize] = 3;
  ( *dither )[matSize + 1] = 1;

  // ひとつ前のサイズの行列の要素を元に構築
  for ( unsigned int cnt = 2 ; cnt < matSize ; cnt *= 2 ) {
    for ( unsigned int r = 0 ; r < cnt ; ++r ) {
      for ( unsigned int c = 0 ; c < cnt ; ++c ) {
        ( *dither )[r * matSize + c] *= 4;
        ( *dither )[r * matSize + cnt + c] = ( *dither )[r * matSize + c] + 2;
        ( *dither )[( r + cnt ) * matSize + c] = ( *dither )[r * matSize + c] + 3;
        ( *dither )[( r + cnt ) * matSize + cnt + c] = ( *dither )[r * matSize + c] + 1;
      }
    }
  }

  // 中央値で減算する(平均値をゼロにする)
  for ( unsigned int r = 0 ; r < matSize ; ++r )
    for ( unsigned int c = 0 ; c < matSize ; ++c )
      ( *dither )[r * matSize + c] -= matSize * matSize / 2;
}

/**
  オーダード・ディザ処理用クラス

  量子化等の処理をする前に、オーダード・ディザ処理を行う。
  例えば、

  Quantize q( 3 ); // 3 ビットを残して量子化
  OrderedDither od( 3, 0.5, q ); // ディザ・マトリックスの大きさは 2 の 3 乗 = 8、比率は 0.5
  GBox::FillBox( draw, od, Coord<int>( 0, 0 ), Coord<int>( 99, 99 ) );

  とすることで、オーダード・ディザ処理をした上で量子化処理を行うことができる。
**/
class OrderedDither : public GPixelOp
{
  unsigned char ditherSize_; // dither_ の行列数
  double rate_;              // dither_ 成分を加算するときの比率
  RGB_Op_IF& op_;            // RGB 成分の処理用関数オブジェクト (量子化など)

  std::vector<int> dither_;  // ディザ・マトリックス

 public:

  /* コンストラクタ */

  /// ディザ・マトリックスのサイズと加算時の比率、後処理用の関数オブジェクトを指定して構築
  ///
  /// sz ディザ・マトリックスの行列数 ( 2 のべき数で表現 )
  /// rate ディザ・マトリックスの成分を加算するときの比率 ( 負値も可 )
  /// op RGB 成分の処理用関数オブジェクト ( 量子化など )
  OrderedDither( unsigned char sz, double rate, RGB_Op_IF& op );

  /// オーダード・ディザ処理を行う
  ///
  /// draw 描画領域
  /// c 変換対象の位置
  virtual bool operator()( DrawingArea_IF& draw, Coord<int> c );
};

/*
  OrderedDither コンストラクタ

  ディザ・マトリックスの行列数を 2 の sz 乗、
  成分を加算するときの比率を rate、
  後処理用関数オブジェクトを op
  として構築する
*/
OrderedDither::OrderedDither( unsigned char sz, double rate, RGB_Op_IF& op )
  : ditherSize_( sz ), rate_( rate ), op_( op )
{
  MakeDitherMatrix( ditherSize_, &dither_ );
}

/*
  AddDither : ディザ・マトリックスの要素 dither をパレット rgb に加算する

  rate は加算する比率を表す
*/
void AddDither( double dither, double rate, RGB* rgb )
{
  int add = RoundHalfUp( dither * rate );
  rgb->r = RGB::Check_RGBPrimary<int>( static_cast<int>( rgb->r ) + add );
  rgb->g = RGB::Check_RGBPrimary<int>( static_cast<int>( rgb->g ) + add );
  rgb->b = RGB::Check_RGBPrimary<int>( static_cast<int>( rgb->b ) + add );
}

/*
  OrderedDither::operator() : 描画領域 draw の位置 c にオーダード・ディザ処理を行う
*/
bool OrderedDither::operator()( DrawingArea_IF& draw, Coord<int> c )
{
  if ( &op_ == 0 || &draw == 0 ) return( false );

  RGB rgb;
  if ( ! draw.point( c, &rgb ) ) return( false );
  AddDither( dither_[( c.x % ditherSize_ ) + ( c.y % ditherSize_ ) * ditherSize_], rate_, &rgb );
  if ( ! op_( &rgb ) ) return( false );
  if ( ! draw.pset( c, rgb ) ) return( false );

  return( true );
}

/*
  AddError : 誤差成分 error を RGB 成分 src に加算する

  但し、補正のため量子化するビットマスク notMask の半分だけ減算する
*/
void AddError( const RGB& error, RGB::primary_type notMask, RGB* src )
{
  *src += error;
  *src -= notMask / 2;
}

/*
  ErrorDispersion : 描画領域 draw に対し、誤差分散法による処理を行う

  errorBit は誤差成分として扱う階調(ビット数)を表す。
  op は誤差分散法を適用した後に行う変換処理(量子化処理など)の関数オブジェクトへの参照
  errorBit と op は独立しているので、誤差成分として扱うビット数を量子化のそれと一致させる必要はない
  量子化をせずに下位ビットを周囲に分散するようなこともできる

  (cpos) の誤差は以下の形で周囲に分散される。[mod] は分散された後に残った剰余分。

  (cpos) [1/2]
  [mod]  [1/8] [1/4]
*/
void ErrorDispersion( DrawingArea_IF& draw, unsigned char errorBit, RGB_Op_IF& op )
{
  // 誤差成分を保持するバッファ
  // 1 本は現在のライン上、もう 1 本はすぐ下側のライン上の誤差成分を保持する
  vector< vector<RGB> > buffer( 2 );

  RGB::primary_type errorMask = Make_RGBMask( errorBit, true ); // 端数計算用ビットパターン
  Coord<int> sz = draw.size(); // 画像サイズ

  // ラインの長さ + 2 分だけバッファを確保
  // +2 は両端からはみ出した分専用。両端で左下、右下への計算をしても問題ないようにするため。
  // 従って、このはみ出した部分はピクセルへの加算はされない。
  for ( unsigned int i = 0 ; i < buffer.size() ; ++i )
    buffer[i].assign( sz.x + 2, RGB( 0, 0, 0 ) );

  Coord<int> c;
  RGB rgb;
  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      draw.point( c, &rgb );

      AddError( buffer[c.y % 2][c.x + 1], errorMask, &rgb );
      RGB error = ( rgb & errorMask ) >> 1; // 端数の 1 / 2

      op( &rgb );
      draw.pset( c, rgb );

      // 端数の 1 / 2 を右側に加算
      buffer[c.y % 2][c.x + 2] += error;
      // 端数を 1 / 4 にして右下に代入
      error >>= 1;
      buffer[( c.y % 2 ) ^ 1][c.x + 2] = error;
      // 端数を 1 / 8 にして左下に加算
      RGB error_div8 = error >> 1;
      buffer[( c.y % 2 ) ^ 1][c.x] += error_div8;

      // x = 0 の場合は下側を初期化
      if ( c.x == 0 )
        buffer[( c.y % 2 ) ^ 1 ][c.x + 1] = RGB( 0, 0, 0 );

      // 端数の残りを計算して下側に加算
      error -= error_div8;
      buffer[( c.y % 2 ) ^ 1][c.x + 1] += error;
    }
  }
}

/*
  RGBtoY RGB各成分から Y 成分を求める

  Y 成分を求める計算式は Y = 0.299R + 0.587G + 0.114B

  const RGB& rgb : 対象の RGB 成分
  戻り値 : 求めた Y 成分
*/
double RGBtoY( const RGB& rgb )
{
  return( ( 0.299 * static_cast<double>( rgb.r ) ) +
          ( 0.587 * static_cast<double>( rgb.g ) ) +
          ( 0.114 * static_cast<double>( rgb.b ) ) );
}

/**
  モノクロ変換用関数オブジェクト
**/
struct Monochrome : public RGB_Op_IF
{
  /* メンバ関数 */

  /// モノクロ変換を行う
  ///
  /// rgb 処理結果を代入する RGB 構造体へのポインタ
  virtual bool operator()( RGB* rgb );
};

/*
  Monochrome::operator() : rgb にモノクロ化処理を行う
*/
bool Monochrome::operator()( RGB* rgb )
{
  if ( rgb == 0 ) return( false );

  rgb->r = rgb->g = rgb->b = RGB::Check_RGBPrimary<int>( RoundHalfUp( RGBtoY( *rgb ) ) );

  return( true );
}

/*
  WriteCoordToCharArray : int型の座標値 coord をunsigned char型配列 buffer に登録する
*/
void WriteCoordToCharArray( const Coord<int>& coord, vector<unsigned char>* buffer )
{
  unsigned int intSz = sizeof( coord.x ) / sizeof( char ); // int 型のサイズ

  // 上位側から順に書き込む
  for ( unsigned int i = intSz ; i > 0 ; --i ) {
    unsigned char c = ( coord.x >> ( i - 1 ) * CHAR_BIT ) & UCHAR_MAX;
    buffer->push_back( c );
  }
  for ( unsigned int i = intSz ; i > 0 ; --i ) {
    unsigned char c = ( coord.y >> ( i - 1 ) * CHAR_BIT ) & UCHAR_MAX;
    buffer->push_back( c );
  }
}

/*
  ReadCoordFromCharArray : unsigned char型配列の反復子 it から要素を取り出し int 型の座標値に変換する

  変換した値は coord に代入される
  e は配列の終端の反復子を示し、これを超えてアクセスしようとした場合は処理を中断して false を返す
*/
bool ReadCoordFromCharArray( vector<unsigned char>::const_iterator& it, vector<unsigned char>::const_iterator e, Coord<int>* coord )
{
  unsigned int intSz = sizeof( coord->x ) / sizeof( char ); // int 型のサイズ

  // 上位側から順に登録されていることを前提
  for ( unsigned int i = intSz ; i > 0 ; --i ) {
    if ( it == e ) return( false );
    coord->x |= ( *it++ << ( i - 1 ) * CHAR_BIT );
  }
  for ( unsigned int i = intSz ; i > 0 ; --i ) {
    if ( it == e ) return( false );
    coord->y |= ( *it++ << ( i - 1 ) * CHAR_BIT );
  }

  return( true );
}

/*
  lessRGB : RGB の大小比較用関数オブジェクト
*/
struct lessRGB
{
  /*
    operator() : rgb1 < rgb2 なら true を返す

    r, g, b の順に大きさを比較し、等しければ次の要素の結果を返すようにする
  */
  bool operator()( const RGB& rgb1, const RGB& rgb2 )
  {
    if ( rgb1.r != rgb2.r ) return( rgb1.r < rgb2.r );
    if ( rgb1.g != rgb2.g ) return( rgb1.g < rgb2.g );
    if ( rgb1.b != rgb2.b ) return( rgb1.b < rgb2.b );

    return( false );
  }
};

/*
  PackPalet : 描画領域 draw の内容からパレット paletTable を作成し、packedData 上でデータを圧縮する

  パレット数が上限 UCHAR_MAX を超えた場合は false を返す
*/
bool PackPalet( const DrawingArea_IF& draw, vector<RGB>* paletTable, vector<unsigned char>* packedData )
{
  std::set<RGB,lessRGB> setPalet; // 画素の RGB 成分に対するインデックスを保持するテーブル
  Coord<int> sz = draw.size();    // 画像サイズ

  packedData->clear();
  WriteCoordToCharArray( sz, packedData ); // 画像サイズの書き込み

  // パレットの作成
  Coord<int> c;
  RGB rgb;
  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      draw.point( c, &rgb );
      setPalet.insert( rgb );
      if ( setPalet.size() > UCHAR_MAX ) return( false );
    }
  }
  paletTable->assign( setPalet.begin(), setPalet.end() );

  // データの圧縮
  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      draw.point( c, &rgb );
      packedData->push_back( static_cast<unsigned char>( std::distance( setPalet.begin(), setPalet.find( rgb ) ) ) );
    }
  }

  return( true );
}


/*
  UnpackPalet : パレット paletTable を使って packedData のデータを描画領域 draw に展開する

  画像展開前にデータを全て読み込んだ場合は false を返す
*/
bool UnpackPalet( const vector<RGB>& paletTable, const vector<unsigned char>& packedData, DrawingArea_IF* draw )
{
  Coord<int> sz; // 画像サイズ
  vector<unsigned char>::const_iterator it = packedData.begin();
  if ( ! ReadCoordFromCharArray( it, packedData.end(), &sz ) ) return( false ); // 画像サイズの読み込み
  draw->resize( sz );

  Coord<int> c;
  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      if ( it == packedData.end() ) return( false );
      draw->pset( c, paletTable[*it++] );
    }
  }

  return( true );
}

const unsigned int LRU_TABLE_SIZE = UCHAR_MAX - 1; // LRU テーブルのサイズ
const unsigned int LRU_IDENT = LRU_TABLE_SIZE + 1; // パレット・色コード判別子

/*
  LRU_Info : パレットとアクセス場所の記録用構造体
*/
struct LRU_Info {
  RGB rgb;            // 色コード
  unsigned int count; // 最後にアクセスされたときのピクセル番号
  // コンストラクタ
  LRU_Info( const RGB& rgb_, unsigned int count_ )
    : rgb( rgb_ ), count( count_ ) {}
};

/*
  パレット LRU_Table から lruInfo と同色のパレットを探し、なければ追加する
  テーブルが満杯だった場合、一番古くにアクセスされた場所に上書きする(LRU法)
*/
vector<LRU_Info>::iterator Insert_LRU_Table( const LRU_Info& lruInfo, vector<LRU_Info>* LRU_Table )
{
  vector<LRU_Info>::iterator it = LRU_Table->begin(); // パレットのアクセス位置を最初の要素に初期化
  vector<LRU_Info>::iterator minCntInfo = it;        // 最も古くに参照された要素を最初の位置で初期化

  for ( ; it != LRU_Table->end() ; ++it ) {
    // 一致する色コードが見つかったらその場所を返す
    if ( it->rgb == lruInfo.rgb ) {
      it->count = lruInfo.count; // FIFO法にする場合は、この行を削除
      return( it );
    }
    // 最も古くに参照された場所を保持
    if ( minCntInfo->count > it->count )
      minCntInfo = it;
  }

  // すでにテーブルはいっぱい
  if ( LRU_Table->size() >= LRU_TABLE_SIZE ) {
    *minCntInfo = lruInfo;
  // まだ空きがある
  } else {
    LRU_Table->push_back( lruInfo );
  }

  return( LRU_Table->end() );
}

/*
  LRU法を使い、画像 draw を packedData にデータ圧縮する
*/
void Pack_LRU_Table( const DrawingArea_IF& draw, vector<unsigned char>* packedData )
{
  Coord<int> sz = draw.size();

  vector<LRU_Info> LRU_Table;
  LRU_Info lru( RGB( 0, 0, 0 ), 0 );

  packedData->clear();
  WriteCoordToCharArray( sz, packedData );

  Coord<int> c;
  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      draw.point( c, &( lru.rgb ) );
      lru.count = c.y * sz.x + c.x;
      vector<LRU_Info>::iterator it = Insert_LRU_Table( lru, &LRU_Table );
      // パレットに同じ色があったらパレットコードを登録
      if ( it != LRU_Table.end() ) {
        packedData->push_back( static_cast<unsigned char>( std::distance( LRU_Table.begin(), it ) ) );
        // パレットに同じ色がなかったら識別子と色コードを登録
      } else {
        packedData->push_back( LRU_IDENT );
        packedData->push_back( lru.rgb.r );
        packedData->push_back( lru.rgb.g );
        packedData->push_back( lru.rgb.b );
      }
    }
  }
}

/*
  LRU法を使った圧縮データ packedData を描画領域 draw に展開する
*/
bool Unpack_LRU_Table( const vector<unsigned char>& packedData, DrawingArea_IF* draw )
{
  Coord<int> sz; // 画像サイズ
  vector<unsigned char>::const_iterator it = packedData.begin();
  if ( ! ReadCoordFromCharArray( it, packedData.end(), &sz ) ) return( false );
  draw->resize( sz );

  vector<LRU_Info> LRU_Table;
  LRU_Info lru( RGB( 0, 0, 0 ), 0 );
  Coord<int> c;

  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      unsigned char palet = *it++;
      if ( palet == LRU_IDENT ) {
        lru.rgb.r = *it++;
        lru.rgb.g = *it++;
        lru.rgb.b = *it++;
        lru.count = c.y * sz.x + c.x;
        // パレットには同じ色はないはず
        if ( Insert_LRU_Table( lru, &LRU_Table ) != LRU_Table.end() )
          return( false );
      } else {
        lru.rgb = LRU_Table[palet].rgb;
        // FIFO法にする場合は、下行を削除
        LRU_Table[palet].count = c.y * sz.x + c.x; // ピクセル番号を更新
      }
      draw->pset( c, lru.rgb );
    }
  }

  return( true );
}