/*hdecode.c by Evan Fukumoto
 * decodes a huffman encoded file*/

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

int main(int argc, char *argv[]){
    /*argument checks*/
    int in, out, i, *chars, *counts, pqSize;
    int mask;
    char buff, toPrint;
    uint32_t numChars, currCount;
    uint8_t  currChar;
    Node *head, *curr;
    pqSize = 0;
    mask = 12;

    /*check infile*
     * default to stdin if can't open or file can't be opened*/
    if(argc > 1){
        if(strcmp(argv[1],"-") == 0){
            in = 0;
        }else if((in = open(argv[1], O_RDONLY)) < 1){
            printf("usage: hdecode [(infile|-) [ outfile ]]"
                   "\nIn file can't be opened \n");
            return -1;
        }
    }else{
        in = 0;
    }
    printf("%d\n", in);
    /*check out file
     * default to stdout if can't open or no file provided*/
    if(argc > 2){
        if((out = open(argv[2], O_WRONLY | O_CREAT | O_TRUNC, 0666)) < 1){
            out = 1;
        }
    }else{
        out = 1;
    }
    /*read the number of chars used*/
    lseek(in, 0,SEEK_SET );
    buff = 0;

    printf("%d",read(in, &buff, 1));
    for(i = 0; i < 3; i++){
        numChars = buff << 4;
        printf("%d",read(in, &buff, 1));

    }

    if(numChars == 0){
        return -1;
    }


    chars = (int *)malloc(numChars* sizeof(int));
    counts = (int *)malloc(numChars* sizeof(int));
    /*build a PQ w the chars*/
    for(i = 0; i < numChars; i++){
        read(in, &currChar, 1);
        read(in, &currCount, 4);
        if(head == NULL){
            head = newNode(currChar,currCount);
            pqSize++;
        }else{
            push(&head, currChar, currCount);
            pqSize++;
        }
        chars[i] = (int) currChar;
        counts[i] = (int) currCount;
    }
    head = makeTreeDecode(pqSize, &head);
    /*read in sequence byte by byte
     * traverse tree by byte, if a leaf, write char and*/
    curr = head;
    while(read(in, &buff, 1)){
        for(i = 0; i < 4; i++){
            if(mask & buff){
                /*is a 1*/
                curr = curr->right;
            }else{
                /*is a 0*/
                curr = curr->left;
            }
            /*check for leaf node*/
            if(curr->left == NULL && curr->right == NULL){
                /*write out the character
                 * and reset curr to head*/
                toPrint = (char)curr->data;
                write(out, &toPrint, 1);
                curr = head;
            }
            buff = buff << 1;
        }
    }
    /*free chars and counts*/
    free(chars);
    free(counts);
    return 0;
}

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

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);
    /*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;
    }

}