#include "useSDL.h"
#include "HuffCoding.h"

/* 画像のRGBデータを表示する */
void
printRGB(SDL_Surface* surface)
{
  int i, j;

  for (i = 0; i < surface->h; i++) {
    for (j = 0; j < surface->w; j++) {
      printf("Red: %u ", getRGB(surface, getPixel(surface, i, j)).r);
      printf("Green: %u ", getRGB(surface, getPixel(surface, i, j)).g);
      printf("Blue: %u\n", getRGB(surface, getPixel(surface, i, j)).b);
    }
  }
  printf("\n");
}

/* 色の出現頻度の集計、ハフマン木の生成を行う */
int
initHuff(SDL_Surface* surface, NodePtr node)
{
  int freeNode, root;
  int min1, min2;
  int i, j;

  /* フラグとカウント初期化 */
  for (i = 0; i <= NODE_SIZE; i++) {
    node[i].count = 0;
    node[i].frag = 0;
  }

  /* 最小値探索やハフマン木作成に必要な要素 */
  node[INDEX_NODE].count = 10000;

  /* 画素値毎の登場回数を集計 */
  for (i = 0; i < surface->h; i++) {
    for (j = 0; j < surface->w; j++) {
      /* 今回はグレイスケールなのでR,G,Bどの値でもおｋ */
      node[getRGB(surface, getPixel(surface, i, j)).r].count++;
      node[getRGB(surface, getPixel(surface, i, j)).r].frag = 1;
    }
  }

  /* 最小値を探してハフマン木の親子関係を定義 */
  for (freeNode = CHARA_NUM+1; freeNode < INDEX_NODE; freeNode++) {    
    seachMin(node, &min1, &min2);

    if (min2 == INDEX_NODE) {
      root = freeNode-1;
      break;
    }

    makeTree(node, freeNode, min1, min2);
  }
  
  return root;
}

/* 出現頻度の最小となる2値を求める */
void
seachMin(NodePtr node, int* min1, int* min2)
{
  int i;
  
  *min1 = *min2 = INDEX_NODE;
  
  for (i = INDEX_NODE-1; i >= 0; i--){
    if (node[i].frag == 1) {
      if (node[i].count < node[*min1].count) {
	*min2 = *min1;
	*min1 = i;
      }
      else if (node[i].count < node[*min2].count){
	*min2 = i;
      }
    }
  }
}

/* ハフマン符号化のルールに基づいてハフマン木をつくる */
void
makeTree(NodePtr node, int freeNode, int min1, int min2)
{
  node[freeNode].child = min1;
  node[freeNode].last_child = min2;

  node[freeNode].count = node[min1].count + node[min2].count;
  node[freeNode].frag = 1;
  
  node[min1].parent = node[min2].parent = freeNode;
  node[min1].frag = node[min2].frag = 0;
}

/* ハフマン符号化したコードを返す */
void
putHuffCode(NodePtr node, int root)
{
  int depth = root - (CHARA_NUM+1);
  int* bit_buff = (int *)malloc(sizeof(int)*depth);
  int bitp, codep;
  int parent;
  int i, j;


  for (i = 0; i <= CHARA_NUM; i++) {
    bitp = codep = 0;
    
    if (node[i].count != 0 ) {
      j = i;
      
      do {
	parent = node[j].parent;
	bit_buff[bitp] = (node[parent].child == j) ? 0 : 1;
	j = parent;
	bitp++;
      } while (j != root);
      
      do {
	if (bit_buff[bitp--] == 1) {
	  node[i].code[codep] = '1';
	} else {
	  node[i].code[codep] = '0';
	}
	codep++;
      } while (bitp > 0);
    }
  }
  free(bit_buff);
}