/*優(yōu)先隊(duì)列*/
#ifndef _priorityqueue_H
#define _priorityqueue_H
struct heapstruct;
typedef struct heapstruct *priorityqueue;
typedef struct HuffmanTree *Pos;
typedef Pos Tree;
struct NODE
{
    long i;
    unsigned char c;
};
struct HuffmanTree
{
    struct NODE elements;
    Tree LeftTree;
    Tree RightTree;
};
typedef Tree elementtype;
struct heapstruct
{
    int max;
    int size;
    elementtype *elements;
};
priorityqueue initialize(int MAX);
void insert(elementtype x, priorityqueue q);
elementtype deletemin(priorityqueue q);
int isfull(priorityqueue q);
int isempty(priorityqueue q);
#endif
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"priorityqueue.h"
#define MIN -1;
priorityqueue initialize(int MAX)
{
    priorityqueue H = NULL;
    H = (priorityqueue)malloc(sizeof(struct heapstruct));
    if(NULL == H)
    {
        printf("NO MEMORY!!!\n");
        return NULL;
    }
    else
    {
        if((H->elements = (elementtype*)malloc((MAX+1) * sizeof(elementtype))) != NULL)
        {
            H->elements[0] = (Tree)malloc(sizeof(struct HuffmanTree));
            H->elements[0]->elements.c = 0;
            H->elements[0]->elements.i = MIN;
            H->elements[0]->LeftTree = NULL;
            H->elements[0]->RightTree = NULL;
            H->max = MAX;
            H->size = 0;
            return H;
        }
        else
        {
            free(H);
            return NULL;
        }
    }
}
void insert(elementtype x,priorityqueue q)
{
    assert(!isfull(q));
    int j = 0;
    q->size = q->size + 1;
    for(j = q->size; x->elements.i < q->elements[j/2]->elements.i;j = j/2)
    {
        q->elements[j] = q->elements[j/2];
    }
    q->elements[j] = x;
}
elementtype deletemin(priorityqueue q)
{
    assert(!isempty(q));
    elementtype x ;
    elementtype last;
    int i = 0;
    int child = 0;
    last = q->elements[q->size];
    q->size = q->size - 1;
    x = q->elements[1];
    for(i = 1; 2*i <= q->size;i = child )
    {
        child = 2 * i;
        if(2*i != q->size && q->elements[child]->elements.i > q->elements[child+1]->elements.i)
        {
            child++;
        }
        if(last->elements.i > q->elements[child]->elements.i)
        {
            q->elements[i] = q->elements[child];
        }
        else
        {
            break;
        }
    }
    q->elements[i] = last;
    return x;
}
int isfull(priorityqueue q)
{
    assert(NULL != q);
    return q->size == q->max ?1:0;
}
int isempty(priorityqueue q)
{
    assert(NULL != q);
    return q->size == 0?1:0;
}
/*實(shí)現(xiàn)huffman編碼壓縮*/
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"priorityqueue.h"

long FileSize = 0;
struct CODE
{
    char CodeString[256];
    unsigned char c;
    long i;
}
G_CODE[256];

struct HuffmanTree CodeTree[512];
void copyc_str(char c ,char *s,int n);
Tree BuildTree(priorityqueue Q);
void EnCode(char s[],Tree T);
void SaveTree(Tree T);

void HuffmanCode(void)
{
    char s[256] = {'\0'};
    Tree T = NULL;
    priorityqueue Q = NULL;
    Q = initialize(512);
    unsigned char c = 0;
    int i = 0;
    FILE *FpFrom = NULL;
    FpFrom = fopen("test.txt", "rb");
    for(i = 0; i < 256 ; i++)
    {
        G_CODE[i].i = 0;
    }
    if(NULL != FpFrom)
    {
        while(!feof(FpFrom))
        {
            c = fgetc(FpFrom);
            G_CODE[c].c = c;
            G_CODE[c].i++;
            FileSize++;
        }
    }
    fclose(FpFrom);
    for(i = 0; i < 256 ; i++)
    {
        if(G_CODE[i].i > 0)
        {
            T = (Tree)malloc(sizeof(struct HuffmanTree));
            if(NULL == T)
            {
                printf("NO Memory!!!\n");
            }
            else
            {
                T->elements.c = G_CODE[i].c;
                T->elements.i = G_CODE[i].i;
                T->LeftTree = NULL;
                T->RightTree = NULL;
                insert(T,Q);
            }
        }
    }
    T = BuildTree(Q);
    EnCode(s,T);
    SaveTree(T);
    FreeTree(T);
}

FreeTree(Tree T)
{
    if(NULL != T)
    {
        FreeTree(T->LeftTree);
        FreeTree(T->RightTree);
        free(T);
    }
}

Tree BuildTree(priorityqueue Q)
{
    Tree LeftTree = NULL;
    Tree RightTree = NULL;
    Tree T = NULL;
    while(Q->size >= 2)
    {
        T = (Tree)malloc(sizeof(struct HuffmanTree));
        if(NULL != T)
        {
            T->elements.c = '-';
            LeftTree = deletemin(Q);
            RightTree = deletemin(Q);
            T->LeftTree = LeftTree;
            T->RightTree = RightTree;
            T->elements.i = T->LeftTree->elements.i + T->RightTree->elements.i;
            insert(T,Q);
        }
    }
    T = deletemin(Q);
    return T;
}
void EnCode(char s[],Tree T)
{
    char Left[256];
    char Right[256];
    if((NULL == T->RightTree) && (NULL == T->LeftTree))
    {
        strcpy(G_CODE[T->elements.c].CodeString , s);
    }
    else
    {
        strcpy(Left,s);
        copyc_str('0',Left,256);
        strcpy(Right,s);
        copyc_str('1',Right,256);
        EnCode(Right,T->RightTree);
        EnCode(Left,T->LeftTree);
    }
}
void SaveTree(Tree T)
{
    int i = 0;
    int k = 0;
    CodeTree[0] = *T;
    /*free(T);*/
    for(k = 0;i <= k; i++)
    {
        if(NULL != CodeTree[i].RightTree && NULL != CodeTree[i].LeftTree)
        {
            int m = k+1;
            int n = k+2;
            CodeTree[m] = *(CodeTree[i].LeftTree);
            CodeTree[i].LeftTree = m;
            CodeTree[n] = *(CodeTree[i].RightTree);
            CodeTree[i].RightTree = n;
            //free(CodeTree[i].LeftTree);
            //free(CodeTree[i].RightTree);
            k = k + 2;
        }
        else
        {
            CodeTree[i].LeftTree = -1;
            CodeTree[i].RightTree = -1;
        }
    }
}
void copyc_str(char c ,char *s,int n)
{
    assert(n > strlen(s));
    char *p = NULL;
    p = s;
    while('\0' != *p)
    {
        p++;
    }
    *p = c;
    p++;
    *p = '\0';
}
void compress(void)
{
    int i = 0;
    int j = 0;
    unsigned char c = '0';
    unsigned char code = 0;
    FILE *FpCompressed = NULL;
    FILE *FpFrom = NULL;
    HuffmanCode();
    FpFrom = fopen("test.txt", "rb");
    FpCompressed = fopen("test.hf", "wb");
    if(NULL != FpFrom&&NULL != FpCompressed)
    {
        fprintf(FpCompressed,"%c%c", 'H','F');
        fprintf(FpCompressed, "%ld", FileSize);
        for(i = 0; i < 512 ; i++)
        {
            fprintf(FpCompressed ,"%c,%d,%d,", CodeTree[i].elements.c, CodeTree[i].LeftTree, CodeTree[i].RightTree);
        }
        while(!feof(FpFrom))
        {
            char temp[512] = {'\0'};
            c = fgetc(FpFrom);
            strcpy(temp,G_CODE[c].CodeString);
            int k = strlen(temp);
            char *p = temp;
            for(; k > 0; k--,p++)
            {
                if(*p == '0')
                {
                    code = code<<1;
                    j++;
                    if(8 == j)
                    {
                        fputc(code,FpCompressed);
                        j = 0;
                    }
                }
                else if(*p == '1')
                {
                    code = (code<<1) + 1;
                    j++;
                    if(8 == j)
                    {
                        fputc(code,FpCompressed);
                        j = 0;
                    }
                }
            }
        }
    }
    fclose(FpFrom);
    if(0 != j)
    {
        j = 8-j;
        code = code<<j;
        fputc(code,FpCompressed);
    }
    fclose(FpCompressed);
}
main()
{
    printf("compressing......\n");
    compress();
    UnCompress();
    printf("ok\n");
    return 0;
}
int UnCompress(void)
{
    int i = 0;
    int j = 0;
    long size = 0;
    unsigned char c = '0';
    struct CodeTreeToUncompress
    {
        unsigned char c;
        int Left;
        int Right;
    }CTTU[512];
    FILE *FpCompressed = NULL;
    FILE *UnCompressed = NULL;
    UnCompressed = fopen("test.t", "wb");
    FpCompressed = fopen("test.hf", "rb");
    if(NULL != UnCompressed && NULL != FpCompressed)
    {
        if(fgetc(FpCompressed) == 'H')
        {
            if(fgetc(FpCompressed) == 'F')
            {
                ;
            }
            else
            {
                printf("error\n");
                return 0;
            }
        }
        else
        {
            printf("error\n");
            return 0;
        }
        fscanf(FpCompressed,"%ld", &size);
        for(i = 0;i < 512; i++)
        {
            fscanf(FpCompressed,"%c,%d,%d,", &CTTU[i].c, &CTTU[i].Left, &CTTU[i].Right);
        }
        while(!feof(FpCompressed)&&size > 0)
        {
            c = fgetc(FpCompressed);
            for(i = 0; i < 8; i++)
            {
                if((c>>7)|0 != 0)
                {
                    j = CTTU[j].Right;
                    if(CTTU[j].Right == -1 && CTTU[j].Left == -1)
                    {
                        fputc(CTTU[j].c,UnCompressed);
                        j = 0;
                        size--;
                    }
                }
                else
                {
                    j = CTTU[j].Left;
                    if(CTTU[j].Right == -1 && CTTU[j].Left == -1)
                    {
                        fputc(CTTU[j].c,UnCompressed);
                        j = 0;
                        size--;
                    }
                }
                c = c<<1;
            }
        }
    }
        fclose(FpCompressed);
        fclose(UnCompressed);
}