#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct point{
    char letter;
    int freq;
    char huff[50];
    struct point *next;
    struct point *left;
    struct point *right;
    }point_t;

point_t *entry;
point_t *start;
point_t *start2;
point_t *root;
point_t *curr;
point_t *prev;
point_t *hold;

int to_base10(char chop[]){
    int a,a2,b,prod,prod2,sum=0;
    for(a=0;a<8;a++)
    {
        prod=1;
        switch(chop[a])
        {
            case '1': b=1; break;
            case '0': b=0; break;
        }
        for(a2=a;a2>0;a2--)
        {
            prod=prod*2;
        }
        prod2=b*prod;
        sum=sum+prod2;
    }
    return (sum);
}

void to_ascii(char str[], int count,char *argv){
    FILE *ascii;
    int arr[count/8];
    char chop[9];
    int i,j,k,l,ctr;
    for(i=0,l=0;i<count-1;i+=8,l++)
    {
        for(j=i,k=7;j<i+8;j++,k--)
        {
            chop[k]=str[j];
        }
        arr[l]=to_base10(chop);
    }
    ascii=fopen(argv, "w");
    for(ctr=0;ctr<count/8;ctr++)
    {
        fprintf(ascii, "%c", (char)(arr[ctr]));
    }
    fclose(ascii);
}

void freq_table(char *argv){
    start=NULL;
    FILE *ascii;
    char ch;
    ascii=fopen(argv, "r");
    while(!feof(ascii))
    {
        ch=getc(ascii);
        if(start==NULL)
        {
            start=(point_t*)malloc(sizeof(point_t));
            start->letter=ch;
            start->freq=1;
            start->next=NULL;
        }
        else
        {
            curr=start;
            while(curr!=NULL)
            {
                if(ch==curr->letter)
                {
                    curr->freq=(curr->freq)+1;
                    break;
                }
                curr=curr->next;
            }
            if(curr==NULL)
            {
                entry=(point_t*)malloc(sizeof(point_t));
                entry->letter=ch;
                entry->freq=1;
                entry->next=NULL;
                curr=start;
                while(curr!=NULL)
                {
                    if(entry->letter<curr->letter)
                    {
                        if(curr==start)
                        {
                            entry->next=curr;
                            start=entry;
                        }
                        else
                        {
                            entry->next=curr;
                            prev->next=entry;
                        }
                        break;
                    }
                    prev=curr;
                    curr=curr->next;
                }
                if(curr==NULL)
                {
                    prev->next=entry;
                }
            }
        }
    }
    curr=start;
    start=start->next;
    curr->next=NULL;
    free(curr);}

void sortbyfreq(){
    start2=NULL;
    curr=start;
    while(curr!=NULL)
    {
        hold=curr;
        entry=(point_t*)malloc(sizeof(point_t));
        entry->letter=curr->letter;
        entry->freq=curr->freq;
        entry->next=NULL;
        entry->left=NULL;
        entry->right=NULL;
        if(start2==NULL)
        {
            start2=entry;
        }
        else
        {
            curr=start2;
            while(curr!=NULL)
            {
                if(entry->freq<=curr->freq)
                {
                    if(curr==start2)
                    {
                        entry->next=curr;
                        start2=entry;
                    }
                    else
                    {
                        entry->next=curr;
                        prev->next=entry;
                    }
                    break;
                }
                prev=curr;
                curr=curr->next;
            }
            if(curr==NULL)
            {
                prev->next=entry;
            }
            curr=hold;
        }
        curr=curr->next;
    }
}

void huffman_tree(long num){

    if(start2->freq==num){}
    else
    {
        root=(point_t*)malloc(sizeof(point_t));
        root->left=start2;
        root->right=start2->next;
        root->freq=(root->left->freq)+(root->right->freq);
        root->next=NULL;
        hold=start2;
        start2=start2->next->next;
        hold->next->next=NULL;
        if(start2==NULL)
        {
            start2=root;
        }
        else
        {
            curr=start2;
            while(curr!=NULL)
            {
                if(root->freq<=curr->freq)
                {
                    if(curr==start2)
                    {
                        root->next=curr;
                        start2=root;
                    }
                    else
                    {
                        prev->next=root;
                        root->next=curr;
                    }
                    break;
                }
                prev=curr;
                curr=curr->next;
            }
            if(curr==NULL)
            {
                prev->next=root;
            }

        }
        huffman_tree(num);
    }
}

void huffman_encoding(point_t *curr, char encode[], char let, int ctr){
    if(curr==NULL)
    {
        encode[ctr-1]='\0';
        hold=start;
        while(hold!=NULL)
        {
            if(prev->letter==hold->letter)
            {
                strcpy(hold->huff, encode);
                break;
            }
            hold=hold->next;
        }
    }
    else
    {
        prev=curr;
        if(ctr==0){}
        else
        {
            encode[ctr-1]=let;
        }
        huffman_encoding(curr->left,encode,'0',ctr+1);
        huffman_encoding(curr->right,encode,'1',ctr+1);
    }
}

void to_prefix(char *argv){
    FILE *prefix;
    prefix=fopen(argv, "w");
    curr=start;
    while(curr!=NULL)
    {
        fprintf(prefix, "%c\t%d\t%s\n", curr->letter,curr->freq,curr->huff);
        curr=curr->next;
    }
    fclose(prefix);
}

void to_output(char *argv1, char *argv2)
{
    FILE *ascii;
    FILE *output;
    char get;
    ascii=fopen(argv1, "r");
    output=fopen(argv2,"w");
    while(!feof(ascii))
    {
        get=getc(ascii);
        curr=start;
        while(curr!=NULL)
        {
            if(get==curr->letter)
            {
                fprintf(output,"%s", curr->huff);
                break;
            }
            curr=curr->next;
        }
    }
    fclose(output);
    fclose(ascii);
}

void to_output(char *argv1, char *argv2);

int main(int argc, char *argv[])
{
    if(argc!=5)
    {
        printf("HOW TO USE: <input file> <ASCII file> <prefix file> <output file>\n");
        exit(1);
    }

    FILE *input;
    char c, encode[50],let;
    int x,y,z,ctr=0;
    long count=0;
    if((input=fopen(argv[1], "r"))==NULL)
    {
        printf("INVALID!\n");
        exit(1);
    }
    while(!feof(input))
    {
        c=getc(input);
        count++;
    }
    char str[count];
    rewind(input);
    while(!feof(input))
    {
        fscanf(input,"%s", str);
    }
    fclose(input);

    to_ascii(str,count,argv[2]);
    freq_table(argv[2]);
    sortbyfreq();
    huffman_tree(count/8);
    curr=root;
    huffman_encoding(curr,encode,let,ctr);
    to_prefix(argv[3]);
    to_output(argv[2],argv[4]);
}