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

typedef struct huffman_table {
    char *character;
    char code[10000];
    struct huffman_table *next_;
}   huffman_table;
    huffman_table *root;

typedef struct frequency {
    char *character;
    int frequency;
    struct frequency *next;
    struct frequency *left;
    struct frequency *right;
}   td_frequency;
    td_frequency *start, *start_freq, *freq_hold_x, *freq_hold_y, *pointer, *temp, *temp2;

int size = 0;

int count();
int is_present();
void generate_frequency();
td_frequency huffman_main ();
td_frequency *create_parent ();
td_frequency extract_node ();
int count_nodes ();
void generate_code ();
void print_file ();

int main (int argc, char *argv[]) {
    start = NULL;
    root = NULL;
    char code[1];

    char input[50];
    scanf("%s", input);

    if (argc != 4) {
        printf("\nSyntax: %s <input.txt> <histogram.txt> <encoded.txt>", argv[1]);
    }

    generate_frequency(input);
    puts("\nGenerating tree...");
    huffman_main();
    puts("\nGenerating code...");
    td_frequency *start_print = start;

    //traverse(start_print);

    generate_code (start, code);
    return 0;
}

void generate_frequency (const char *inserted_string) {
    int i;

    for (i = 0; i < strlen(inserted_string); i++){
        td_frequency *inserted_node = (td_frequency *)malloc(sizeof(td_frequency));
        volatile int temp_count = count(inserted_string[i], inserted_string);
        volatile int is_there = is_present(inserted_string[i], inserted_string);

        inserted_node->frequency = temp_count;
        inserted_node->character = inserted_string[i];
        inserted_node->left = NULL;
        inserted_node->right = NULL;

        if (is_present(inserted_string[i], inserted_string) == 0) {
            if(start == NULL) {
                    start =  inserted_node;
                    start->next = NULL;
            }   else if (start->frequency > temp_count) {
                    temp = start;
                    start = inserted_node;
                    start->next = temp;
            }   else {
                    temp = start;
                    temp2 = start;
                    while (temp != NULL) {
                        if (temp->frequency > temp_count) {
                                temp2->next = (td_frequency *)malloc(sizeof(td_frequency));
                                temp2 = temp2->next;
                                temp2->character = inserted_string[i];
                                temp2->frequency = temp_count;
                                temp2->right = NULL;
                                temp2->left = NULL;
                                temp2->next = temp;
                                break;
                        }   else if (temp->next == NULL) {
                                temp->next = (td_frequency *)malloc(sizeof(td_frequency));
                                temp = temp->next;
                                temp->character = inserted_string[i];
                                temp->frequency = temp_count;
                                temp->next = NULL;
                                temp->left = NULL;
                                temp->right = NULL;
                                break;
                        }   else temp2 = temp, temp = temp->next;
                    }
            }
        }
    }

    printf("\nALL ENTRIES:\n");
    pointer = start;
    while (pointer != NULL) {
        printf("\n| Chaarcter:   %c\n| Frequency:   %d\n", pointer->character, pointer->frequency);
        pointer = pointer->next;
        size++;
    }
    return;
}

td_frequency huffman_main (int size) {
    td_frequency *temp_parent;
    int i, n = count_nodes();

    if (start != NULL) {
        for (i = n; i > 1 ; i--) {
            if (count_nodes() >1) {
                printf("\nHUFFMAN MAIN!\n");
                extract_node();
                temp_parent = create_parent();
                printf("\nTemporary parent: %d", temp_parent->frequency);

                if (start == NULL) {
                    start = temp_parent;
                }   else if (start->frequency > temp_parent->frequency) {
                        temp = start;
                        start = temp_parent;
                        start->next = temp;
                }   else {
                        temp = start;
                        temp2 = start;
                        while (temp != NULL) {
                            if (temp->frequency > temp_parent->frequency) {
                                temp2->next = temp_parent;
                                temp2 = temp2->next;
                                temp2->next = temp;
                                break;
                            }   else if (temp->next == NULL) {
                                    temp->next = temp_parent;
                                    temp = temp->next;
                                    temp->next = NULL;
                                    break;
                            }   else {
                                    temp2 = temp;
                                    temp = temp->next;
                            }
                        }
                }
            }
        }
    }
    start = temp_parent;
    printf("%\nSTRT FREQ: %d\n", start->frequency);
    pointer = start;

    return;
}

td_frequency *create_parent (void) {
    td_frequency *parent = (td_frequency *)malloc(sizeof(td_frequency));
    parent->frequency = freq_hold_x->frequency + freq_hold_y->frequency;
    freq_hold_x->next = NULL;
    freq_hold_y->next = NULL;

    parent->left = freq_hold_x;
    parent->right = freq_hold_y;
    printf("\nFrequency (inside create_parent): %d\n", parent->frequency);

    return parent;
}

td_frequency extract_node (void) {
    freq_hold_x = start;
    printf("\nFrequency of x: %d\n", start->frequency);
    freq_hold_y = start->next;
    printf("Frequency of y: %d\n", start->next->frequency);
    start = start->next->next;
    return;
}

int count_nodes (void) {
    int count = 0;
    td_frequency *temp = start;

    do {
        count++;
        temp = temp->next;
    }   while (temp != NULL);
    printf("\nCOUNT: %d\n", count);
    return count;
}

int count (char *being_counted, char *input) {
    int count_dracula = 0, i;
    for (i = 0; i < strlen(input); i++) {
        if (being_counted == input[i]) count_dracula++;
    }
    return count_dracula;
}

int is_present (char *being_searched, char *input) {
    td_frequency *search = start;
    while (search != NULL) {
        if (being_searched == search->character) return 1;
        else {
            search = search->next;
        }
    }
    return 0;
}

void generate_code (td_frequency *tree, char *huffman_code) {
    /*puts("ENTERING 1.\n");
    printf("TREE->ELEMENT: %d\n",tree->frequency);
    if(tree->left != NULL) printf("TREE->LEFT: %d\n", tree->left->frequency);
    if(tree->right!=NULL) printf("TREE->RIGHT: %d\n", tree->right->frequency);
    printf("TREE IS NULL: %d\n",tree==NULL);
    printf("TREE->RIGHT IS NULL: %d\n", tree->right==NULL);
    printf("TREE->LEFT IS NULL: %d\n\n", tree->left==NULL);*/
    if (tree->left == NULL && tree->right == NULL) {
        puts("ENTERING 2.");
        huffman_table *table_ = (huffman_table *)malloc(sizeof(huffman_table));
        table_->character = tree->character;
        table_->code[10000] = huffman_code;
        table_->next_ = NULL;
        puts("ENTERING 2.1");

        if (root == NULL) {
            puts("ENTERING 2.2");
            root = table_;
            root->next_ = NULL;
        }   else {
                puts("ENTERING 2.3");
                huffman_table *tempting = root;
                while (tempting->next_ != NULL) {
                    puts("ENTERING 2.4");
                    printf("TEMP NEXT IS NULL: %d\n", tempting->next_==NULL);
                    tempting = tempting->next_;
                    puts("EXITING 2.4");
                }
                puts("ENTERING ASSIGNING PHASE!");
                //tempting->next_ = (huffman_table *)malloc(sizeof(huffman_table));
                tempting->next_ = table_;
                puts("DONE");
        }

    }   else {
        puts("ENTERING 3.");
        //printf("BEFOR STRCAT: %s\n", huffman_code);
        //printf("STRCAT RESULT: %s\n\n", strcat(huffman_code, "0"));
        generate_code(tree->left, strcat(huffman_code, "0"));
        puts("ENTERING 3.2");
        generate_code(tree->right, strcat(huffman_code, "1"));
    }

    puts("supposedly returning na");
    return 0;
}

void print_file (char *file_name) {

}

void traverse (td_frequency *rootsss) {
    if (rootsss != NULL) {
        printf("%d ", rootsss->frequency);
        puts("\nError?");
        traverse(rootsss->left);
        puts("\nError?");
        traverse(rootsss->right);
    }
}