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

typedef struct node {
    bool is_char;
    char ch;

    struct node *left;
    struct node *right;
} node_t;

node_t *node_char_create(char ch);
// left right flipped because tree has to be inverted for some reason
node_t *node_link_create(node_t* right, node_t* left);
void node_free(node_t *root);
void node_print(node_t *root, int indent);

size_t read_tree_data(char *buf);
node_t *read_tree_shape(char *char_buf, size_t bits);
char read_decoded(node_t *root);
void decode();

FILE *in;
FILE *out;

node_t *root;

char read_decoded(node_t *root)
{
    static size_t i = 0;
    static char cur_byte = 0;

    if(root == NULL) {
        fprintf(stderr, "ERROR: real_decoded: root cannot be NULL");
        exit(1);
    }

    if(root->is_char) return root->ch;

    if(i % 8 == 0) {
        if(fread(&cur_byte, sizeof(char), 1, in) <= 0) {
            fprintf(stderr, "ERROR: An error has occured while reading the encoded bytes\n");
            exit(1);
        }
        i = 0;
    }

    char bit = (cur_byte >> i++) & 1;
    if(bit == 0) {
        return read_decoded(root->left);
    }

    return read_decoded(root->right);
}

void decode()
{
    char buf[256] = {0};
    size_t chars = read_tree_data(buf);
    root = read_tree_shape(buf, chars*2 - 1);

    size_t text_len;
    fread(&text_len, sizeof(size_t), 1, in);

    for(int i = 0; i < text_len; i++) {
        char ch = read_decoded(root);
        fwrite(&ch, sizeof(char), 1, out);
    }
}

int main(void)
{
    in = stdin;
    out = stdout;

    // in = fopen(argv[1], "rb");
    // if(!in) {
    //     fprintf(stderr, "ERROR: Could not open file %s\n", argv[1]);
    //     exit(1);
    // }

    // out = fopen(argv[1], "wb");
    // if(!out) {
        // fprintf(stderr, "ERROR Could not open file %s\n", argv[1]);
        // exit(1);
    // }

    decode();

    node_free(root);

    // fclose(in);
    // fclose(out);
    return 0;
}

size_t read_tree_data(char *buf)
{
    unsigned int chars = 0;
    fread(&chars, sizeof(char), 1, in);
    fread(buf, sizeof(char), chars, in);
    return chars;
}

node_t *read_tree_shape(char *char_buf, size_t bits)
{
    static size_t buf_i = 0;
    static size_t read_bits = 0;
    static char cur_byte = 0;

    if(read_bits == bits) {
        fprintf(stderr, "ERROR: An error has occred while reading the tree shape (read_bits == bits)");
        exit(1);
    }

    if(read_bits % 8 == 0) {
        if(fread(&cur_byte, sizeof(char), 1, in) <= 0) {
            fprintf(stderr, "ERROR: An error has occured while reading the tree shape\n");
            exit(1);
        }
    }

    node_t *root;

    char bit = (cur_byte >> (read_bits++ % 8)) & 1;
    if(bit == 0) {
        root = node_link_create(read_tree_shape(char_buf, bits),
                                read_tree_shape(char_buf, bits));
    } else {
        root = node_char_create(char_buf[buf_i++]);
    }

    return root;
}

node_t *node_char_create(char ch)
{
    node_t *node = malloc(sizeof(node_t));

    node->is_char = true;
    node->ch = ch;
    node->left = NULL;
    node->right = NULL;

    return node;
}
node_t *node_link_create(node_t* right, node_t* left)
{
    node_t *node = malloc(sizeof(node_t));

    node->is_char = false;
    node->ch = 0;
    node->left = left;
    node->right = right;

    return node;
}

void node_free(node_t *root)
{
    if(root == NULL) return;

    node_free(root->left);
    node_free(root->right);

    free(root);
}

void node_print(node_t *root, int indent)
{
    if(root == NULL) return;

    for(int i = 0; i < indent; i++) fprintf(stderr, " ");

    fprintf(stderr, "%d '%c'\n", root->is_char, (root->ch == 0) ? '-' : root->ch);

    node_print(root->left, indent + 2);
    node_print(root->right, indent + 2);
}