/*
 * 作者：antigloss at http://cpp.ga-la.com
 * 最后修改：05-10-2 15:35
 * 螞蟻的 C/C++ 標準編程
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../header/huffmantree.h"
#include "../mylib/error_handler.h"

static const char *msg[] = { "Please input a character: ",
                             "Please input its weight: ",
                             "Invalid input!! You should input an integer."};

/* Begin of creat_hufftree 05-10-2 13:10 */
void creat_hufftree(HuffmanTree ht, unsigned n) /* 形成赫夫曼樹 */
{
    unsigned i, s1, s2, size = 2 * n - 1;
    
	for ( i = n + 1; i <= size; ++i ) {
		s1 = s2 = 0;
		Select(ht, i, &s1, &s2); /* 選擇 parent 為 0，且 weight 最小的兩個結(jié)點 */
		ht[s1].parent = ht[s2].parent = i;
		ht[i].lchild = s1;
		ht[i].rchild = s2;
		ht[i].weight = ht[s1].weight + ht[s2].weight;
	}
} /* End of creat_hufftree */

/* Begin of destroy_huffcode 05-10-2 14:50 */
void destroy_huffcode(HuffmanCode hc, unsigned n) /* 銷毀赫夫曼編碼 */
{
     unsigned i;
     
     for ( i = 1; i <= n; ++i ) {
         free(hc[i]);
     }
     free(hc);
} /* End of destroy_huffcode */

/* Begin of encode_hufftree 05-10-2 15:00 */
HuffmanCode encode_hufftree(HuffmanTree ht, unsigned n)
{ /* 從葉子到根逆向求每個字符的赫夫曼編碼 */
	char *cd;
	unsigned start, i, child, parent;
	HuffmanCode hc;
	
    hc = malloc( (n + 1) * sizeof *hc ); /* 分配 n 個字符編碼的頭指針向量 */
	if ( !hc ) {
		return NULL;
    }
    
	cd = malloc( n * sizeof *cd ); /* 分配編碼的工作空間 */
	if ( !cd ) {
        free(hc);
		return NULL;
    }
    
	cd[n-1] = '\0'; /* 編碼結(jié)束符 */	
	for ( i = 1; i <= n; ++i ) { /* 逐個字符求赫夫曼編碼 */
		start = n - 1; /* 編碼結(jié)束位置 */
		for ( child = i, parent = ht[i].parent; parent != 0;
              child = parent, parent = ht[parent].parent ) { /* 從葉子到根逆向求編碼 */
			if ( ht[parent].lchild == child ) {
				cd[--start]='0';
            } else {
				cd[--start]='1';
            }
		}
		hc[i] = malloc( (n - start) * sizeof *hc[i] ); /* 為第i個字符編碼分配空間 */
		if ( !hc[i] ) {
            destroy_huffcode( hc, i - 1 );
            free(cd);
			return NULL;
        }
		strcpy(hc[i], &cd[start]);
	}
	
	free(cd); /* 釋放工作空間 */	
	return hc;
} /* End of encode_hufftree */
                             
/* Begin of HuffmanTree 05-10-2 12:10 */
HuffmanTree init_hufftree(unsigned n) /* 初始化赫夫曼樹 */
{
	int tmp, chk;
    unsigned i, size = 2 * n - 1;
	HuffmanTree ht, p;
	
    ht = malloc( (size + 1) * sizeof *ht ); /* 不使用 0 號單元 */
    if ( !ht ) {
        return NULL;
    }
    
    for ( p = ht + 1, i = 1; i <= n; ++i, ++p) {
		fputs(msg[0], stdout);
		tmp = getchar();
		if ( tmp != '\n' && tmp != EOF ) {
            flush_stdin();
        }
        p->data = tmp;
        
        fputs(msg[1], stdout);
		while ( ( chk = scanf("%u", &p->weight) ) != 1 ) {
            if ( chk != EOF ) {
                flush_stdin();
            }
            printf("%s\n\n%s", msg[2], msg[1]);
        }
        flush_stdin();
		p->lchild = p->parent = p->rchild = 0;
	}
	
	for ( ; i <= size; ++i, ++p ) {
		p->lchild = p->parent = p->rchild = p->weight = 0;
    }
    
    return ht;
} /* End of HuffmanTree */

/* Begin of print_huffcode 05-10-2 15:15 */
void print_huffcode(HuffmanCode hc, HuffmanTree ht, unsigned n) /* 輸出赫夫曼編碼 */
{
    unsigned i;
    
    for ( i = 1; i <= n; ++i ) {
        printf("%c: %s\n", ht[i].data, hc[i]);
    }
} /* End of print_huffcode */

/* Begin of Select 05-10-2 13:00 */
void Select(HuffmanTree p, unsigned i, unsigned *s1, unsigned *s2)
{ /* 選擇 parent 為 0，且 weight 最小的兩個結(jié)點 */
	unsigned j;

	for ( j = 1; j < i; ++j ) {
		if ( !p[j].parent ) {
			if ( !*s1 ) {
				*s1 = j;
            } else if ( p[*s1].weight > p[j].weight ) {
				*s2 = *s1;
				*s1 = j;
			} else {
				*s2 = j;
            }
		}
		
		if ( *s1 && *s2 ) break;
	}
	
	for ( ++j; j < i; ++j ) {
		if ( !p[j].parent ) {
			if ( p[*s1].weight > p[j].weight ) {
				*s2 = *s1;
				*s1 = j;
			} else if( p[*s2].weight > p[j].weight ) {
					*s2 = j;
			}
		}
	}
} /* End of Select */