#include "huff.h"
#define SIZE 100
#define ASCII 256



int main(int argc, char *argv[]){
    /*args check*/
    int  in, out, freqs[ASCII], *freqs2, i,j, chars,
    pqSize, *val, codelen, toAddSize, carrySize, carryChar;
    int codes[ASCII], codelens[ASCII];
    uint8_t toPack;
    char buff[SIZE];
    Node *head, *temp1, *temp2;
    head = NULL;
    temp1 = NULL;
    temp2 = NULL;
    codelen = 0;
    out = 1;
    chars = 0;
    carryChar = 0;
    toAddSize = 0;
    pqSize = 0;
    j = 0;
    carrySize = 0;
    codelen = 0;
    for(i = 0; i< 256; i++){
        codelens[i] = 0;
    }


    /*check in file*/
    if(argc > 3 || argc < 2){
        printf("usage: hencode infile [ outfile ]\n");
        return -1;
    }
    if( (in = open(argv[1], O_RDONLY)) < 1){
        printf("usage: hencode infile [ outfile ]\n");
        return -1;
    }

    /*check outfile*/
    if(argc == 3 &&
       (out = open(argv[2], O_WRONLY | O_CREAT | O_TRUNC, 0666)) < 0){
        exit(-1);
    }

    /*init the freq table*/
    for(i = 0; i < ASCII; i++){
        freqs[i] = 0;
    }
    /*zero out the buff*/
    for(i = 0; i < SIZE; i++ ){
        buff[i] = (char) 0;
    }
    while(read(in, buff, SIZE) > 0){
        i = 0;
        while(buff[i] != 0){
            freqs[(int)buff[i]]++;
            buff[i] = (char)0;
            i++;
        }
    }


    /*create PQ and count used chars*/
    initPQ(freqs, i, &chars, &pqSize, &head);
    if(chars != 0){


        /*make tree*/
        head = makeTree(pqSize, &head, temp1, temp2);

        /*create huffcodes*/
        makecode(head,0,codes, codelen, codelens);
    }


    /*make out file header */
    /*write numchars*/
    val = (int *)malloc(chars*sizeof(int));
    freqs2 = (int *)malloc(chars* sizeof(int));

    if(chars != 0){
        for(i = 0, j = 0; i < ASCII; i++){
            if(freqs[i]!= 0){
                freqs2[j] = freqs[i];
                val[j]  = i;
                j++;
            }
        }
    }

    /*initialize these guys*/
    toAddSize = 0;
    carrySize = 0;
    carryChar = -1;
    writeHeaderOut(out, i, &chars, freqs2, val);
    if(chars !=0 ){
        writeBodyOut(in, out, i, codelens,
                     toAddSize, &toPack, carrySize, carryChar, codes, buff, j);
    }
    /*free tree*/
    freeTree(head);
    /*free val and freqs2*/
    free(val);
    free(freqs2);


    return 0;
}
void freeTree(Node *node){
    if(node != NULL){
        /*call on right and left*/
        freeTree(node->right);
        freeTree(node->left);
        free(node);
    }
}

void writeBodyOut(int in, int out, int i, const int *codelens,
        int toAddSize, uint8_t *toPack, int carrySize, int carryChar,
                  const int *codes, char *buff, int j) {
    /*write encoded document*/
    /*reset to begining of document*/
    lseek(in,0,SEEK_SET);
    for(i =0; i < 100; i++){
        buff[i] = 0;
    }
    /*start write*/
    while(read(in,(void *) buff, SIZE) > 0){
        i = 0;
        j = 0;

        while(buff[i] != 0 && i < SIZE){
            /*until you read the whole line
            * reset packing int, size*/
            (*toPack) = 0;
            toAddSize = 0;
            if(carrySize >8){
                /*if can't be written in one carry*/
                while(carrySize >= 8){
                    (*toPack) |= (codes[(int)buff[i]] << (8 - carrySize));
                    write(out, toPack, 1);
                    carrySize = 8 - carrySize;
                }
            }
            if(carrySize > 0 && carrySize < 8){
                /*if theres a left over, pack
                 * the rest of it but needs more packed*/
                (*toPack) |= (codes[carryChar] << (8 - carrySize));
            }
            /*reset carries*/
            carryChar = 0;
            carrySize = 0;
            while(toAddSize < 8 && i < 100 && buff[i] != 0){
                /*find out how many chars we can write*/
                toAddSize += codelens[(int)buff[i]];
                (*toPack) |= (codes[(int)buff[i]] << (8 - toAddSize));
                i++;
                j++;
            }
            if(toAddSize > 8){
                /*if there is leftover, save the char
                * and the amount that didn't get written*/
                carryChar = buff[i];
                carrySize = toAddSize - 8;
            }
            write(out, toPack, 1);

        }
        for(i =0; i < 100; i++){
            buff[i] = (char)0;
        }
    }
}

void initPQ(const int *freqs, int i, int *chars, int *pqSize, Node **head) {
    (*chars) = 0;
    (*pqSize) = 0;
    /*create PQ and count used chars*/
    for(i = 0; i < ASCII; i++){
        if(freqs[i] != 0){
            if((*head) == NULL){
                (*head) = newNode(i, freqs[i]);
                (*pqSize)++;
            }else{
                push(head, i, freqs[i]);
                (*pqSize)++;
            }
            (*chars)++;
        }
    }
}

Node *makeTree(int pqSize, Node **head, Node *temp1, Node *temp2) {
    while(pqSize > 1){
        temp1 = pop(head);
        temp2 = pop(head);
        pushTree(head, temp1, temp2);
        pqSize--;
    }
    return (*head);
}

void writeHeaderOut(int out, int i, int *chars, const int *freqs2,
                    const int *val) {
    /*write header files, start w amount of codes*/

    uint8_t buff1;
    uint32_t buff2;
    buff2 = *chars;
    write(out, &buff2, 4);
    for(i = 0; i < (*chars) ; i++){
        buff1 = (uint8_t) val[i];
        buff2 = (uint32_t) freqs2[i];
        write(out, &buff1, 1);
        write(out, &buff2, 4);
    }

}


/* Function to Create A New Node*/
Node* newNode(int d, int p)
{
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = d;
    temp->priority = p;
    temp->next = NULL;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}


/*Removes the element with the
 highest priority form the list*/
Node *pop(Node** head)
{
    Node* temp = *head;
    (*head) = (*head)->next;
    return temp;
}

/*Function to push according to priority*/
void push(Node** head, int d, int p)
{
    Node* start = (*head);
    /*Create new Node*/
    Node* temp = newNode(d, p);
    /*Special Case: The head of list has lesser*/
    /*priority than new node. So insert new
    node before head node and change head node.*/
    if ((*head)->priority > p) {
        /*Insert New Node before head*/
        temp->next = *head;
        (*head) = temp;
    }
    else {
        /*Traverse the list and find a
        position to insert new node*/
        while (start->next != NULL &&
               start->next->priority < p) {
            start = start->next;
        }
        /*Either at the ends of the list
        or at required position*/
        temp->next = start->next;
        start->next = temp;
    }
}

void pushTree(Node** head, Node *temp1, Node* temp2)
{
    Node *start, *temp;
    int p;
    p = temp1->priority+ temp2->priority;
    start = (*head);
    temp1->next = NULL;
    temp2->next = NULL;
    /*Create new Node*/
    temp = newNode(-1, p);
    temp->left = temp1;
    temp->right = temp2;
    /*Special Case: The head of list has lesser*/
    /*priority than new node. So insert new
    node before head node and change head node.*/
    if(*head != NULL){
        if ((*head)->priority >= p) {
            /*Insert New Node before head*/
            temp->next = *head;
            (*head) = temp;
        }
        else {
            /*Traverse the list and find a
            position to insert new node*/
            while (start->next != NULL &&
                   start->next->priority <= p) {
                start = start->next;
            }
            /*Either at the ends of the list
            or at required position*/
            temp->next = start->next;
            start->next = temp;
        }
    }else{
        temp->next = NULL;
        *head = temp;
    }

}

void makecode(Node *curr, int code,int *codes, int codelen, int *codelens){
    /*is a leaf node*/
    codelen++;
    if(curr->left == NULL && curr->right == NULL){
        codes[curr->data] = code;
        codelens[curr->data] = codelen;
    }
    if(curr->left){
        code = code << 1;

        makecode(curr->left,code,codes,codelen, codelens);
    }
    if(curr->right){
        /*code = code << 1;*/
        code++;
        /*codelen++;*/
        makecode(curr->right,code,codes,codelen, codelens);
    }
}