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

//structure used to define a node
typedef struct node_t {
    struct node_t *left, *right;
    int freq;
    char c;
} *node;

//global variables
int n_nodes = 0, qend = 1; //global variables for keep track of no.of nodes and end of the que
struct node_t pool[256] = {{0}}; //pool of nodes
node qqq[255], *q = qqq - 1; //the priority que
char *code[128] = {0}, buf[1024]; //a string array of the codes for each letter
int input_data = 0, output_data = 0, i;

//function used to create a new node
node new_node(int freq, char c, node a, node b)
{
    node n = pool + n_nodes++;
    if (n == NULL) {
        printf("Error: memory allocation failed\n");
        return NULL;
    }
    if (freq != 0) {
        n->c = c; //assign the character 'c' to the character of the node (eventually a leaf)
        n->freq = freq; //assign frequency
    } else {
        n->left = a, n->right = b; //if there is no frequency provided with the invoking
        n->freq = a->freq + b->freq; //the removed nodes at the end of the que will be added to left and right
    }
    return n;
}

//function used to insert a node into the priority que
void qinsert(node n)
{
    if (n == NULL) {
        printf("Error: null pointer\n");
        return;
    }
    int j, i = qend++;
    while ((j = i / 2)) {
        if (q[j]->freq <= n->freq)
            break;
        q[i] = q[j], i = j;
    }
    q[i] = n;
}

node qremove()
{
    if (qend < 2) {
        printf("Error: queue is empty\n");
        return NULL;
    }
    int i, l;
    node n = q[i = 1];

    qend--;
    while ((l = i * 2) < qend) {
        if (l + 1 < qend && q[l + 1]->freq < q[l]->freq)
            l++;
        q[i] = q[l], i = l;
    }
    q[i] = q[qend];
    return n; //return the node
}

//go along the builded huffman tree and assign the code for each character
void build_code(node n, char *s, int len)
{
    if (n == NULL || s == NULL) {
        printf("Error: null pointer\n");
        return;
    }
    static char *out = buf;
    if (n->c) {
        s[len] = 0; //if the provided node is a leaf (end node)
        strcpy(out, s); //it contains a character
        code[(int)n->c] = out; //therefore the code is copied in to the relevant character.
        out += len + 1; //out pointer is incremented
        return;
    }

    s[len] = '0';
    build_code(n->left, s, len + 1); //recurring is used to write out the code
    s[len] = '1';
    build_code(n->right, s, len + 1); //if right add a 1 and if right add a 0
}

void import_file(FILE *fp_in, unsigned int *freq, int *fd)
{
    if (fp_in == NULL || freq == NULL || fd == NULL) {
        printf("Error: null pointer\n");
        return;
    }
    char c, s[16] = {0}; //temporary variables
    int i = 0;
    printf("File Read:\n");
    while ((c = fgetc(fp_in)) != EOF) {
        freq[(int)c]++; //read the file character by character and increment the particular frequency
        putchar(c);
    }
    for (i = 0; i < 128; i++)
        if (freq[i])
            qinsert(new_node(freq[i], i, 0, 0)); //insert new nodes into the que if there is a frequency
    while (qend > 2)
        qinsert(new_node(0, 0, qremove(), qremove())); //build the tree
    build_code(q[1], s, 0); //build the code for the characters

    // send frequency data to child process
    close(fd[0]); // close unused read end
    write(fd[1], freq, 128 * sizeof(unsigned int));
    close(fd[1]); // close write end
}

void encode(FILE *fp_in, FILE *fp_out, unsigned int *freq)
{
    if (fp_in == NULL || fp_out == NULL || freq == NULL) {
        printf("Error: null pointer\n");
        return;
    }
    char in, c, temp[20] = {0};
    int i, j = 0, k = 0, lim = 0;
    rewind(fp_in);
    for (i = 0; i < 128; i++) {
        if (freq[i])
            lim += (freq[i] * strlen(code[i]));
    }
    output_data = lim; //The output data is equal to the limit
    fprintf(fp_out, "%04d\n", lim);
    printf("\nEncoded:\n");
    for (i = 0; i < lim; i++) {
        if (temp[j] == '\0') {
            in = fgetc(fp_in);
            strcpy(temp, code[in]);
            printf("%s", code[in]);
            j = 0;
        }
        if (temp[j] == '1')
            c = c | (1 << (7 - k)); //shifts 1 to relevant position and OR with the temporary char
        else if (temp[j] == '0')
            c = c | (0 << (7 - k)); //shifts 0 to relevant position and OR with the temporary char
        else {
            printf("ERROR: Wrong input!\n");
            return;
        }
        k++; // k is used to divide the string into 8 bit chunks and save
        j++;
        if (((i + 1) % 8 == 0) || (i == lim - 1)) {
            k = 0; //reset k
            fputc(c, fp_out); //save the character
            c = 0; //reset character
        }
    }
    putchar('\n');
}

void print_code(unsigned int *freq)
{
    if (freq == NULL) {
        printf("Error: null pointer\n");
        return;
    }
    int i;
    printf("\n---------CODE TABLE---------\n----------------------------\nCHAR  FREQ  CODE\n----------------------------\n");
    for (i = 0; i < 128; i++) {
        if (isprint((char)i) && code[i] != NULL && i != ' ')
            printf("%-4c  %-4d  %16s\n", i, freq[i], code[i]);
        else if (code[i] != NULL) {
            switch (i) {
            case '\n':
                printf("\\n  ");
                break;
            case ' ':
                printf("\' \' ");
                break;
            case '\t':
                printf("\\t  ");
                break;
            default:
                printf("%0X  ", (char)i);
                break;
            }
            printf("  %-4d  %16s\n", freq[i], code[i]);
        }
    }
    printf("----------------------------\n");
}

void decode(FILE *fp_huffman, FILE *fp_out, unsigned int *freq)
{
    if (fp_huffman == NULL || fp_out == NULL || freq == NULL) {
        printf("Error: null pointer\n");
        return;
    }
    int i = 0, lim = 0, j = 0;
    char c;
    node n = q[1];

    fscanf(fp_huffman, "%d", &lim); //get the length of the bit stream from header
    fseek(fp_huffman, 1, SEEK_CUR); //seek one position to avoid new line character of the header

    printf("Decoded : \n");
    for (i = 0; i < lim; i++) {
        if (j == 0)
            c = fgetc(fp_huffman);
        //if the anding of the character with b1000 0000 is true then,
        if (c & 128)
            n = n->right; //1 go right
        else
            n = n->left; //else go left
        if (n->c) { //until a leaf (node with a character) meets
            putchar(n->c); //spit that character out and
            fputc(n->c, fp_out); //save the character in file
            n = q[1]; //reset the que
        }
        c = c << 1; //shift the character by 1
        if (++j > 7)
            j = 0;
    }

    putchar('\n');
    if (q[1] != n)
        printf("garbage input\n"); //the last node should end with a character which reset the que
}