/***********************************************************
	huffman3.c -- Huffman (ハフマン) 法
	outcountはputbitを呼び出すごとに自動カウント
2005/06/06 頻度freq[i]の書き込みと読み込みを改善
***********************************************************/
#include "bitio.c"              /* ビット入出力 */
#define N       256             /* 文字の種類 */
#define CHARBITS  8             /* 1バイトのビット数 */
#define MIN_INIT 1000000
int parent[2*N-1], left[2*N-1], right[2*N-1];  /* Huffman木 */
int Y_N[2*N-1];/* ハフマン木をつくるとき調べようとしている語を，
			   すでに調べた=1，まだ調べていない=0　*/
unsigned long int freq[2*N-1];  /* 各文字の出現頻度 */

/* プロトタイプ宣言 */
int choose(void);
void encode(void);
void decode(unsigned long int);

int main(int argc, char *argv[])
{
	int c;
	unsigned long int size;  /* 元のバイト数 */

	if (argc != 4 || ((c = *argv[1]) != 'E' && c != 'e'
	                            && c != 'D' && c != 'd'))
		error("使用法は本文を参照してください");
	if ((infile  = fopen(argv[2], "rb")) == NULL)
		error("入力ファイルが開きません");
	if ((outfile = fopen(argv[3], "wb")) == NULL)
		error("出力ファイルが開きません");
	if (c == 'E' || c == 'e') {
		fseek(infile, 0L, SEEK_END);  /* infile の末尾を探す */
		size = ftell(infile);     /* infile のバイト数 */
		fwrite(&size,sizeof size,1,outfile);
		rewind(infile);
		encode();  /* 圧縮 */
	} else {
		fread(&size, sizeof size, 1, infile);  /* 元のバイト数 */
		decode(size);  /* 復元 */
	}
	fclose(infile);  fclose(outfile);
	return EXIT_SUCCESS;
}

int choose(){
  int i,index=-1;
  unsigned long int min=MIN_INIT;
  for(i=0;i<2*N-1;i++){
    if((freq[i]<min)&&(Y_N[i]==0)){
      min = freq[i];
      index = i;
    }
  }
  if(index != -1){
    Y_N[index]=1;
  }
  return(index);
}

void encode(void)  /* 圧縮 */
{
  int i, j, k;
  unsigned long int incount;
  static char codebit[CHARBITS];  /* 符号語 */

 
}


void decode(unsigned long int size)  /* 復元 */
{
  int i,j,root;
  unsigned long int k;
 
  for (i = 0; i < 2*N-1; i++){
    freq[i] = 0, Y_N[i] = 1;  /* 頻度等の初期化 */
  }
  for(i=0;i<N;i++){
    fread(&freq[i], sizeof(unsigned long int), 1, infile);
  }
  for(i=0;i<N;i++){
    if(freq[i] != 0){
      Y_N[i] = 0;
    }
  }
  for (i = 0; i < 2 * N - 1; i++){
    left[i] = 0,right[i] = 0;  /* 念のため */
  }
  k = N;  /* 以下のループでハフマン木を作る */
  while((i=choose())!=-1&&(j=choose())!=-1){  /* 最小の要素と２番目に小さい要素を取り出す */
    Y_N[k] = 0;
    freq[k] = freq[i] + freq[j];  /* 頻度を合計 */
    left[k] = i;  right[k] = j;  /* 木を作る */
    k++;
  }

  root = k - 1;  /* 木を読む */
  for (k = 0; k < size; k++) {  /* 各文字を復元 */
    j = root;  /* 根 */
    while (j >= N) if (getbit()) j = right[j];  else j = left[j];
    putc(j, outfile);
  }
}