/**
   LZ77 符号の定義

   xxxxxxxxxxYYYYYYY
   |         |
   位置情報  データ数情報
**/
template<class Code>
class LZ77_CodeGenerator
{
  size_t indexBit_; // 位置情報の符号長
  size_t countBit_; // 一致したデータ数情報の符号長

  // 位置情報とデータ数の符号に対するマスク
  Code indexMask_;
  Code countMask_;

 public:

  /// 位置情報とデータ数のビット数 indexBit, countBit を指定して構築
  LZ77_CodeGenerator( size_t indexBit, size_t countBit )
    : indexBit_( indexBit ), countBit_( countBit )
  {
    indexMask_ = ~( ~( static_cast<Code>( 0 ) ) << indexBit_ );
    countMask_ = ~( ~( static_cast<Code>( 0 ) ) << countBit_ );
  }

  /// 位置情報 index とデータ数 count の情報を符号化して返す
  ///
  /// 位置情報・データ数のいずれも符号長を超えていないことを前提として処理する
  Code encode( Code index, Code count ) const
  { return( ( index << countBit_ ) | count ); }

  /// 符号 code から位置情報 index とデータ数 count を取得する
  void decode( Code code, Code* index, Code* count ) const
  {
    *index = ( code >> countBit_ ) & indexMask_;
    *count = code & countMask_;
  }

  /// 符号長を返す
  size_t bits() const
  { return( indexBit_ + countBit_ ); }
};

/**
   Sliding Window 上のデータ探索用関数オブジェクト
**/
template<class In,class Code>
  struct SW_Search
{
  /// 現在のデータ列の先頭 dataStart が辞書バッファの中で一致する部分を探し、
  /// 位置と長さを index, count に返す
  ///
  /// dataEnd はデータ列の末尾の次の反復子、winSize は Sliding Window のサイズ
  void operator()( In dataStart, In dataEnd, Code winSize, Code maxCountSize, Code* index, Code* count );
};

/**
   現在のデータ列の先頭 dataStart が辞書バッファの中で一致する部分を探し、
   位置と長さを index, count に返す

   dataEnd はデータ列の末尾の次の反復子、winSize は Sliding Window のサイズ
**/
template<class In,class Code>
  void SW_Search<In,Code>::operator()( In dataStart, In dataEnd, Code winSize, Code maxCountSize, Code* index, Code* count )
{
  // 反復子 In の差分に対する型
  typedef typename std::iterator_traits<In>::difference_type difference_type;

  // 位置とデータ数はデフォルト値(ゼロ)で初期化
  *index = *count = Code();

  // Sliding Window の先頭
  In winStart = dataStart;
  std::advance( winStart, -static_cast<difference_type>( winSize ) );

  for ( ; winStart != dataStart ; ++winStart ) {
    In winP = winStart; // 辞書バッファ内の比較対象データの先頭

    // 符号化するデータと一致する部分を探索
    for ( In dataP = dataStart ; *winP == *dataP ; ++dataP ) {
      if ( dataP == dataEnd ) break;
      ++winP;
    }

    // 一致部分のデータ位置と個数を更新
    size_t sz = std::distance( winStart, winP );
    if ( sz > *count ) {
      *index = std::distance( winStart, dataStart );
      *count = sz;
    }
    // 比較対象のデータ数を超えたら処理をやめる
    if ( *count >= maxCountSize ) {
      *count = maxCountSize;
      break;
    }
  }
}

/**
   辞書バッファ ( Sliding Window )

             winStart_       winStart_ + curIndex_
             |               |
             +-------------->+               sliding window
   +---------------------------------------+ data
   |                                       |
   dataStart                               dataEnd_
**/
template<class In,class Code>
class SlidingWindow
{
  // 反復子 In の値に対する型
  typedef typename std::iterator_traits<In>::value_type value_type;

  In dataStart_; // データ列の開始
  In dataEnd_;   // データ列の末尾の次
  In curIndex_;  // 符号化するデータの開始(辞書バッファの末尾の次)

  Code winSize_;      // Sliding Window のサイズ
  Code maxWinSize_;   // Sliding Window の最大サイズ
  Code maxCountSize_; // 比較対象のデータ数最大値

 public:

  /// 対象データ列の開始(s)・末尾の次(e)の反復子を指定して構築
  ///
  /// Sliding Window のサイズはゼロで初期化され、符号化されるに従って maxWinSize まで増大する
  SlidingWindow( In s, In e, Code maxWinSize, Code maxCountSize )
    : dataStart_( s ), dataEnd_( e ), curIndex_( s ),
    winSize_( 0 ), maxWinSize_( maxWinSize ), maxCountSize_( maxCountSize )
  {
    // データ列が Sliding Window の最大サイズに満たない場合、データ列の大きさを設定する
    if ( std::distance( s, e ) < maxWinSize_ )
      maxWinSize_ = std::distance( s, e );
  }

  /// データ列 container を指定して構築
  ///
  /// Sliding Window のサイズはゼロで初期化され、符号化されるに従って maxWinSize まで増大する
  template<class Container>
    SlidingWindow( const Container& container, Code maxWinSize, Code maxCountSize )
    : dataStart_( container.begin() ), dataEnd_( container.end() ), curIndex_( container.begin() ),
    winSize_( 0 ), maxWinSize_( maxWinSize ), maxCountSize_( maxCountSize ) {}

  /// 現在のデータ列の先頭が辞書バッファの中で一致する部分を探し、位置と長さを返す
  ///
  /// search は探索用関数オブジェクトへの参照
  template< template<class,class> class SW_Search >
    void search( SW_Search<In,Code>& search, Code* index, Code* count ) const
    { search( curIndex_, dataEnd_, winSize_, maxCountSize_, index, count ); }

  /// 現在の読み込み位置の値を返す
  value_type value() const
  { return( *curIndex_ ); }

  /// 全てのデータ列を読み終えたか
  bool empty() const
  { return( curIndex_ == dataEnd_ ); }

  /// 次に読み込むデータ列の位置を n だけ進める
  void inc( size_t n );
};

/**
   次に読み込むデータ列の位置を n だけ進める
**/
template<class In,class Code>
  void SlidingWindow<In,Code>::inc( size_t n )
{
  if ( static_cast<size_t>( std::distance( curIndex_, dataEnd_ ) ) < n ) {
    curIndex_ = dataEnd_;
  } else {
    std::advance( curIndex_, n );
  }

  if ( winSize_ < maxWinSize_ ) {
    winSize_ += n;
    if ( winSize_ > maxWinSize_ )
      winSize_ = maxWinSize_;
  }
}

/**
   LZ77法によりデータ列 data を符号化して packed に登録する

   符号は LZ77_CodeGenerator により作成され、Code で定義された型で返される。
   indexBit は位置情報(現在の位置からの相対距離)のビット数を表し、その他に一致した
   データ列の長さ (countBit) もまとめて符号列に保持される。
   indexBit + countBit が符号のビット数となるように countBit が求められる。
   符号列 packed は、処理前に初期化(要素のクリア)がなされる。
   データ列 data は符号なし値であることを想定している

   テンプレート引数の T は data の要素の型
   テンプレート引数の SW_SearchType は Sliding Window への探索用関数オブジェクトの型

   swSearch は Sliding Window への探索用関数オブジェクト
**/
template<class T,class Code,template<class,class> class SW_SearchType>
bool LZ77Encode( const std::vector<T>& data,
                 std::vector<Code>* packed,
                 size_t indexBit,
                 SW_SearchType<typename std::vector<T>::const_iterator,Code>& swSearch )
{
  // 定数宣言
  const size_t szCode = sizeof( Code ) / sizeof( char );    // 符号長(バイト数)
  const size_t bitCode = std::numeric_limits<Code>::digits; // 符号のビット数
  const size_t szValue = sizeof( T ) / sizeof( char );      // 値のバイト数
  const size_t bitValue = std::numeric_limits<T>::digits;   // 値のビット数

  if ( &data == 0 || packed == 0 ) return( false );

  // indexBit は符号のビット数より小さくなければならない
  if ( indexBit >= bitCode )
    return( false );

  size_t countBit = bitCode - indexBit;       // 一致したデータ数情報のビット数
  Code maxWinSize = pow( 2, indexBit ) - 1;   // Sliding Window の最大値
  Code maxCountSize = pow( 2, countBit ) - 1; // 一致したデータ数情報の最大値

  // 符号ジェネレータ
  LZ77_CodeGenerator<Code> codeGen( indexBit, countBit );
  // Sliding Window
  SlidingWindow<typename std::vector<T>::const_iterator,Code>
    sWin( data, maxWinSize, maxCountSize );

  Code cacheCode = 0;  // 符号のキャッシュ
  size_t cacheLen = 0; // キャッシュされた符号のビット数
  Code index = 0;      // 位置情報
  Code count = 0;      // 一致したデータ長

  packed->clear(); // 符号列の初期化
  while ( ! sWin.empty() ) {
    sWin.search( swSearch, &index, &count );
    // 符号化
    if ( count * szValue > szCode ) {
      // 先頭ビットに符号を表す 1 を書き込む
      WriteToArray( static_cast<Code>( 1 ), static_cast<size_t>( 1 ), &cacheCode, &cacheLen, packed );
      // 符号の書き込み
      WriteToArray( codeGen.encode( index, count ), codeGen.bits(), &cacheCode, &cacheLen, packed );
      sWin.inc( count );
    // データ列をそのまま登録
    } else {
      // 先頭ビットに値を表す 0 を書き込む
      WriteToArray( static_cast<Code>( 0 ), static_cast<size_t>( 1 ), &cacheCode, &cacheLen, packed );
      // 符号の書き込み
      WriteToArray( sWin.value(), bitValue, &cacheCode, &cacheLen, packed );
      sWin.inc( 1 );
    }
  }

  // 残りビット列の出力
  if ( cacheLen > 0 )
    packed->push_back( cacheCode << ( bitCode - cacheLen ) );

  return( true );
}

/**
   LZ77法により符号列 packed を復号化して data に登録する

   indexBit は位置情報(現在の位置からの相対距離)のビット数を表し、
   データ列の長さ (countBit) は indexBit + countBit が符号のビット数となるように求められる。

   テンプレート引数の T は data の要素の型
   dataCount は復号化するデータ数
**/
template<class T,class Code>
bool LZ77Decode( const std::vector<Code>& packed, std::vector<T>* data,
                 size_t indexBit, typename std::vector<T>::size_type dataCount )
{
  // 定数宣言
  const size_t szCode = sizeof( Code ) / sizeof( char );    // 符号長(バイト数)
  const size_t bitCode = std::numeric_limits<Code>::digits; // 符号のビット数
  const size_t bitValue = std::numeric_limits<T>::digits;   // 値のビット数

  if ( &packed == 0 || data == 0 ) return( false );

  // indexBit は符号のビット数 - 符号長 ( = countBit ) より小さくなければならない
  if ( indexBit + szCode >= bitCode )
    return( false );

  size_t countBit = bitCode - indexBit; // 一致したデータ数情報のビット数

  Code cacheCode = 0;  // 符号のキャッシュ
  size_t cacheLen = 0; // キャッシュされた符号のビット数
  Code code;           // 符号情報
  Code index = 0;      // 位置情報
  Code count = 0;      // 一致したデータ長
  T isCode;            // 符号・データ判別フラグ
  T t;                 // 符号列からデータを読み込むための変数

  // 符号ジェネレータ
  LZ77_CodeGenerator<Code> codeGen( indexBit, countBit );

  // 符号データの現在位置
  typename std::vector<Code>::const_iterator cit = packed.begin();
  // 復号化したデータ数
  typename std::vector<T>::size_type st = 0;

  while ( st < dataCount ) {
    // 先頭ビットの取り込み
    if ( ! ReadFromArray( &cit, packed.end(), &cacheCode, &cacheLen, &isCode, static_cast<size_t>( 1 ) ) )
      return( false );
    // 符号の場合
    if ( isCode != 0 ) {
      if ( ! ReadFromArray( &cit, packed.end(), &cacheCode, &cacheLen, &code, codeGen.bits() ) )
        return( false );
      codeGen.decode( code, &index, &count );
      typename std::vector<T>::size_type read = data->size() - index; // 前のデータの読み込み開始位置
      for ( size_t sz = 0 ; sz < count ; ++sz ) {
        data->push_back( (*data)[read] );
        ++read;
      }
      st += count;
    // データの場合
    } else {
      if ( ! ReadFromArray( &cit, packed.end(), &cacheCode, &cacheLen, &t, bitValue ) )
        return( false );
      data->push_back( t );
      ++st;
    }
  }

  return( true );
}

/**
   Sliding Window 上のデータ探索用関数オブジェクト

   std::map / std::unordered_map を利用して、データ列の先頭が等しい位置を
   あらかじめコンテナに登録しておく。データ列の一致する部分を探索する時、
   このコンテナを使って対象を絞り込む。
**/
template<class In,class Code,class Map>
  class SW_Search_UseMap
{
  // operator() 関数で前回登録した反復子の次(=今回登録する反復子)
  // insert 関数で Fragment 型を要素とするコンテナに登録する時、
  // curIndex_ から現在位置までをまとめて登録するために使う
  In curIndex_;

  Map map_; // 反復子登録用マップ型コンテナ

  // 反復子 s をコンテナ map_ に追加する
  typename Map::mapped_type* insert( In s );

 public:

  /// データ列の開始を指定して構築
  SW_Search_UseMap( In dataStart )
    : curIndex_( dataStart ) {}

  /// 現在のデータ列の先頭 dataStart が辞書バッファの中で一致する部分を探し、
  /// 位置と長さを index, count に返す。
  ///
  /// dataEnd はデータ列の末尾の次の反復子、winSize は辞書バッファのサイズ、
  /// maxCountSize はデータ列を比較する長さの最大値。
  void operator()( In dataStart, In dataEnd, Code winSize, Code maxCountSize,
                   Code* index, Code* count );
};

/**
   反復子 s をコンテナに追加する
**/
template<class In,class Code,class Map>
  typename Map::mapped_type*
  SW_Search_UseMap<In,Code,Map>::insert( In s )
{
  typename Map::iterator it = map_.find( s );
  if ( it == map_.end() ) {
    map_[s].push_back( s );
    return( 0 );
  } else {
    ( it->second ).push_back( s );
    return( &( it->second ) );
  }
}

/**
   現在のデータ列の先頭 dataStart が辞書バッファの中で一致する部分を探し、
   位置と長さを index, count に返す

   dataEnd はデータ列の末尾の次の反復子、winSize は辞書バッファのサイズ
   fragment は Fragment を保持するコンテナで、ここからデータ列が一致する候補を探索する
**/
template<class In,class Code,class Map>
  void SW_Search_UseMap<In,Code,Map>::operator()
  ( In dataStart, In dataEnd, Code winSize, Code maxCountSize,
    Code* index, Code* count )
{
  // 位置とデータ数はデフォルト値(ゼロ)で初期化
  *index = *count = Code();

  // 未登録分を追加
  while ( curIndex_ != dataStart ) {
    insert( curIndex_ );
    ++curIndex_;
  }

  // 現在位置をコンテナに追加し、同時に先頭のデータ列が同じ要素のリストを取得
  typename Map::mapped_type* inList = insert( dataStart );
  if ( inList == 0 ) return;

  typename Map::mapped_type::const_iterator winList = --( inList->end() );

  while ( winList-- != inList->begin() ) {
    In winStart = *winList; // 辞書バッファ内の比較対象データの先頭

    // Sliding Window 外なら処理終了
    if ( std::distance( winStart, dataStart ) > winSize )
      break;

    In winP = winStart;   // 辞書バッファ内の比較対象データの先頭
    In dataP = dataStart; // 符号化対象のデータの先頭

    // 符号化するデータと一致する部分を探索
    size_t sz = 0; // 一致部分のデータ数
    while ( dataP != dataEnd ) {
      if ( *winP != *dataP || sz == maxCountSize ) break;
      ++winP;
      ++dataP;
      ++sz;
    }

    // index と count の更新
    if ( sz > *count ) {
      *index = std::distance( winStart, dataStart );
      *count = sz;
    }
    // 比較対象の最大データ数に達したら処理をやめる
    if ( *count == maxCountSize ) {
      break;
    }
  }
}

/**
   SW_Search_UseMap を利用して Sliding Window 上のデータを探索する

   コンテナは std::map を利用
**/
template<class In,class Code>
  class SW_Search_Map
{
  // 二つの反復子の先頭から符号化可能な最小の長さまで
  // データの大小を比較する関数オブジェクト
  struct LessFragment;

  // 反復子登録用マップ型コンテナ
  typedef std::map
  < In,
    std::vector<In>,
    LessFragment > container_type;

  // 探索用オブジェクト (SW_Search_UseMap)
  SW_Search_UseMap<In,Code,container_type> search_;

 public:

  /// データ列の開始を指定して構築
  SW_Search_Map( In dataStart )
    : search_( dataStart ) {}

  /// 現在のデータ列の先頭 dataStart が辞書バッファの中で一致する部分を探し、
  /// 位置と長さを index, count に返す。
  ///
  /// dataEnd はデータ列の末尾の次の反復子、winSize は辞書バッファのサイズ、
  /// maxCountSize はデータ列を比較する長さの最大値。
  void operator()( In dataStart, In dataEnd,
                   Code winSize, Code maxCountSize,
                   Code* index, Code* count )
  { search_( dataStart, dataEnd, winSize, maxCountSize, index, count ); }
};

/**
   二つの反復子の先頭から符号化可能な最小の長さまで
   データの大小を比較する関数オブジェクト
**/
template<class In,class Code>
  struct SW_Search_Map<In,Code>::LessFragment
{
  // データの先頭の大小を比較する
  bool operator()( In s1, In s2 ) const
  {
    // 反復子 In の値に対する型
    typedef typename std::iterator_traits<In>::value_type value_type;

    // 符号化した方が圧縮できるデータ数
    const size_t szCmp = sizeof( Code ) / sizeof( value_type ) + 1;

    for ( size_t st = 0 ; st < szCmp ; ++st ) {
      if ( *s1 < *s2 ) return( true );
      if ( *s1++ > *s2++ ) return( false );
    }
    return( false );
  }
};

template<typename T>
struct Node
{
  T value;            // 値
  size_type bros;     // 兄弟の節へのリンク
  size_type child;    // 子の節へのリンク
};

/**
   トライ木 (Trie) クラス
**/
template<typename T>
class Trie
{
  struct Node; // 節 Node の前方宣言

 public:

  typedef typename std::vector<Node> array_type;    // 節の配列の型
  typedef typename array_type::size_type size_type; // 配列の添字・大きさの型

 private:

  array_type nodes; // 節の配列

 public:

  /// NULL を表す添字を返す
  size_type nullNode()
  { return( nodes.max_size() ); }

  /// 根の節の添字を返す
  static size_type rootNode()
  { return( 0 ); }

 private:

  /**
     節を表す内部クラス
  **/
  struct Node
  {
    T value;            // 値
    size_type bros;     // 兄弟の節へのリンク
    size_type parent;   // 親の節へのリンク
    size_type child;    // 子の節へのリンク
    unsigned int level; // 根からの距離

    // 値・親の節の添字とレベルを指定して構築
    Node( T t, size_type p, unsigned int l )
    : value( t ), parent( p ), level( l ) {}
  };

 public:

  /// デフォルト・コンストラクタ
  ///
  /// 根の節だけを追加する。根の節の添字は必ずゼロになる。
  Trie() { init(); }

  /// 木の初期化
  ///
  /// 要素を全消去して根の節だけを追加する。
  void init()
  {
    nodes.clear();
    add( nullNode(), 0 );
    setChild( rootNode(), nullNode() );
    setBros( rootNode(), nullNode() );
  }

  /// 登録されている節の個数を返す
  size_type size() const
  { return( nodes.size() ); }

  /// parent を親として、newVal を値に持つ新たな節を追加する
  ///
  /// 戻り値として新しい節の添字を返す
  size_type add( size_type parent, T newVal );

  /// 添字 index の節の子から値が value と一致するものを探し、その添字を返す
  ///
  /// 子供の節がない場合は新規に追加を行い nullNode を返す
  size_type findChild( size_type index, T value );

  /// 添字 index の節の兄弟から値が value と一致するものを探し、その添字を返す
  ///
  /// 見つからない場合は新規に追加を行い nullNode を返す
  size_type findBros( size_type index, T value );

  /// 添字 index の節の値を返す
  T operator[]( size_type index ) const
  { return( nodes.at( index ).value ); }

  /// 添字 child の節の親を返す
  size_type parent( size_type child ) const
  { return( nodes.at( child ).parent ); }

  /// 添字 index の節のレベルを返す
  unsigned int level( size_type index ) const
  { return( nodes.at( index ).level ); }

  /// 添字 child の節を添字 parent の節の子としてリンクする
  void setChild( size_type parent, size_type child )
  { nodes.at( parent ).child = child; }

  /// 添字 littleBros の節を添字 bigBros の節の弟としてリンクする
  void setBros( size_type bigBros, size_type littleBros )
  { nodes.at( bigBros ).bros = littleBros; }
};

/// parent を親として、newVal を値に持つ新たな節を追加する
template<typename T>
typename Trie<T>::size_type Trie<T>::add( size_type parent, T newVal )
{
  nodes.push_back( Node( newVal, parent, ( parent == nullNode() ) ? 0 : nodes.at( parent ).level + 1 ) );
  nodes.back().child = nodes.back().bros = nullNode();

  return( nodes.size() - 1 );
}

/// 添字 index の節の子から値が value と一致するものを探し、その添字を返す
///
/// 子供の節がない場合は新規に追加を行い nullNode を返す
template<typename T>
typename Trie<T>::size_type Trie<T>::findChild( size_type index, T value )
{
  if ( nodes.at( index ).child == nullNode() ) {
    setChild( index, add( index, value ) );
    return( nullNode() );
  } else {
    return( findBros( nodes.at( index ).child, value ) );
  }
}

/// 添字 index の節の兄弟から値が value と一致するものを探し、その添字を返す
///
/// 見つからない場合は新規に追加を行い nullNode を返す
template<typename T>
typename Trie<T>::size_type Trie<T>::findBros( size_type index, T value )
{
  for ( ; nodes.at( index ).value != value ; index = nodes.at( index ).bros ) {
    if ( nodes.at( index ).bros == nullNode() ) {
      setBros( index, add( nodes.at( index ).parent, value ) );
      return( nullNode() );
    }
  }

  return( index );
}

/// LZW 符号の型
/// unsigned char 型の Trie クラスの size_type を型とする
typedef Trie<unsigned char>::size_type lzw_code_type;

/*
  辞書を初期化する

  Trie 型の辞書 trie の根に unsigned char 型の要素を子の節として追加する
*/
void SetDefaultNode( Trie<unsigned char>* trie )
{
  trie->init();

  // 値ゼロの節を根の最初の子として登録
  lzw_code_type bigBros = trie->add( trie->rootNode(), 0 );
  trie->setChild( trie->rootNode(), bigBros );
  // 兄弟の節の末尾に逐次追加する
  for ( unsigned int i = 1 ; i <= std::numeric_limits<unsigned char>::max() ; i++ ) {
    lzw_code_type littleBros = trie->add( trie->rootNode(), i );
    trie->setBros( bigBros, littleBros );
    bigBros = littleBros;
  }
}

/*
  添字 index のビット数を数えて返す
*/
lzw_code_type GetBitSize( lzw_code_type index )
{
  /// 添字の最大ビット数
  lzw_code_type maxBitSize = std::numeric_limits<lzw_code_type>::digits;

  lzw_code_type res = 0; // 求めるビット数
  for ( lzw_code_type i = 1 ; i <= maxBitSize ; ++i ) {
    if ( ( index & 1 ) != 0 ) res = i;
    index >>= 1;
  }

  return( res );
}

/*
  LZW法により data を符号化して packed に登録する

  packed は符号化の前に初期化(要素のクリア)を行う
*/
bool LZWEncode( const std::vector<unsigned char>& data, std::vector<lzw_code_type>* packed )
{
  // Trie 型の辞書
  Trie<unsigned char> dictionary;
  SetDefaultNode( &dictionary );
  // 読み込んだデータを持つ節の添字(符号として登録される値)
  lzw_code_type dicIdx = dictionary.rootNode();
  // 登録した符号の最大値
  lzw_code_type maxDicIdx = dicIdx;

  std::vector<lzw_code_type> buffer; // 符号列を一時的に保持する配列

  std::vector<unsigned char>::const_iterator src = data.begin(); // データの読み込み位置
  while ( src != data.end() ) {
    // dicIdx の節に対して、次に読み込んだデータを持つ子の節を探す
    lzw_code_type childIdx = dictionary.findChild( dicIdx, *src );
    // 見つかった場合、dicIdx を子の節の添字に置換して次のデータを読む
    if ( childIdx != dictionary.nullNode() ) {
      dicIdx = childIdx;
      ++src;
    // 見つからなければ dicIdx 節の添字を符号列に追加して根の節の添字に初期化する
    } else {
      // 添字の最小値は根を除いた 1 なので、ゼロになるように 1 を減算しておく
      --dicIdx;
      buffer.push_back( dicIdx );
      if ( dicIdx > maxDicIdx ) maxDicIdx = dicIdx; // 符号の最大値チェック
      dicIdx = dictionary.rootNode();
    }
  }

  // 符号列に登録されていない最後の添字を追加する
  if ( dicIdx != dictionary.nullNode() ) {
    // 添字の最小値は根を除いた 1 なので、ゼロになるように 1 を減算しておく
    --dicIdx;
    if ( dicIdx > maxDicIdx ) maxDicIdx = dicIdx;
    buffer.push_back( dicIdx );
  }

  // 実際の符号の最大ビット数に合わせて詰めて登録する
  size_t bitSize = GetBitSize( maxDicIdx ); // 符号の最大ビット数
  lzw_code_type cacheCode = 0;              // 符号のキャッシュ
  size_t cacheLen = 0;                      // キャッシュされた符号のビット数

  packed->clear();              // 符号列の初期化
  packed->push_back( bitSize ); // 符号列の先頭に最大ビット数を登録する
  for ( std::vector<lzw_code_type>::const_iterator cit = buffer.begin() ;
        cit != buffer.end() ; ++cit ) {
    WriteToArray( *cit, bitSize, &cacheCode, &cacheLen, packed );
  }
  // 残りビット列の出力
  if ( cacheLen > 0 )
    packed->push_back( cacheCode << ( std::numeric_limits<lzw_code_type>::digits - cacheLen ) );

  return( true );
}

/*
  LZW法により符号列 packed を復号して data に登録する

  異なる符号列からまとめて複合できるように、data は初期化(要素のクリア)は行わない。
*/
bool LZWDecode( const std::vector<lzw_code_type>& packed, std::vector<unsigned char>* data,
                std::vector<unsigned char>::size_type dataCount )
{
  // Trie 型の辞書
  Trie<unsigned char> dictionary;
  SetDefaultNode( &dictionary );
  // 直前に読み込んだ符号
  lzw_code_type preIndex = dictionary.nullNode();

  // 復号データの初期サイズ
  std::vector<unsigned char>::size_type startCnt = data->size();

  // 符号列の読み込み位置
  std::vector<lzw_code_type>::const_iterator src = packed.begin();
  if ( src == packed.end() ) return( false );

  size_t bitSize = *src++;     // 符号のビット数は符号列の先頭から取得
  lzw_code_type index;         // 読み込んだ符号(=節の添字)
  lzw_code_type cacheCode = 0; // 符号のキャッシュ
  size_t cacheLen = 0;         // キャッシュされた符号のビット数

  while ( data->size() - startCnt < dataCount ) {
    if ( ! ReadFromArray( &src, packed.end(), &cacheCode, &cacheLen, &index, bitSize ) )
      return( false );
    ++index; // 符号化の時、最小値がゼロになるように 1 減算していたため補正

    // 辞書の追加
    // 読み込んだ節から先頭の要素を取得して、直前の節を親として追加する
    if ( preIndex != dictionary.nullNode() ) {
      lzw_code_type root = ( index >= dictionary.size() ) ? preIndex : index;
      while ( dictionary.parent( root ) != dictionary.rootNode() )
        root = dictionary.parent( root );
      dictionary.add( preIndex, dictionary[root] );
    }
    preIndex = index; // 符号の更新

    // パレットの展開
    unsigned int level = dictionary.level( index ); // 節のレベル(=読み込むデータ数)
    data->resize( data->size() + level );           // 読み込む数だけリサイズ
    std::vector<unsigned char>::iterator d = data->end();
    while ( dictionary.parent( index ) != dictionary.nullNode() ) {
      *( --d ) = dictionary[index];
      // レベルよりたどった数が多くなることはあり得ない
      if ( level-- == 0 ) return( false );
      index = dictionary.parent( index );
    }
  }

  return( true );
}