#ARCH_2 Compact_Trie

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

#define VERTS_COUNT 2

typedef struct{
        char *value;
        char* leaf;
        struct vertex *parent;
        struct vertex *arcs[VERTS_COUNT];
        int arcs_count;
} vertex;

void init_vertex(vertex* v){
        v->value = 0;
        v->leaf = 0;
        v->parent = 0;
        memset(v->arcs,0,sizeof(vertex*) * VERTS_COUNT);
        v->arcs_count = 0;
}

vertex* malloc_and_init_vertex(){
        vertex* v = (vertex*)malloc(sizeof(vertex));
        init_vertex(v);
        return v;
}

//считает длину совпадающего префикса в двух строках
int get_identical_symbols_count(char* s1,char* s2){
        int c_count = 0;
        char* s1_p = s1;
        char* s2_p = s2;
        while(s1_p[0] && s2_p[0]){
                if (s1_p[0] != s2_p[0]) break;
                c_count++;
                s1_p++;
                s2_p++;
        }
        return c_count;
}

//разворачивает leaf узла дерева в цепочку потомков
vertex* expand_leaf_and_ret_child(vertex* head_v, int syms_count){
        vertex* cv = head_v;
        int i;
        for (i = 0; i != syms_count; i++){
                char c = head_v->leaf[i];
                int index = c - '0';
                //создаем новую вершину
                vertex* new_v = malloc_and_init_vertex();
                new_v->parent = cv;
                cv->arcs_count++;
                cv->arcs[index] = new_v;
                cv = new_v;
        }

        //сохраняем остаток leaf в cv
        if (strlen(head_v->leaf) > syms_count) cv->leaf = strdup(head_v->leaf + syms_count);
        //free (head_v->leaf);
        head_v->leaf = 0;
        if (head_v->value){
                //переносим значение в конец цепочки
                cv->value = head_v->value;
                head_v->value = 0;
        }
        return cv;
}
//вставка ключа
void insert_key(vertex* head_v, char* key, char* value){
        vertex* current_vertex = head_v;
        char* current_key = key;

        while (strlen(current_key)){
                char c = current_key[0];
                int index = c - '0';
                vertex* nv = current_vertex->arcs[index];
                if (!nv){
                        //такой дуги еще нет.
                        //прежде чем ее создавать - проверяем leaf
                        if (current_vertex->leaf != 0){
                                if (strcmp(current_vertex->leaf,current_key)==0){
                                        //нашли ключ. заменяем значение
                                        //if (current_vertex->value) free (current_vertex->value);
                                        current_vertex->value = strdup(value);//создает строку value и возвр указатель на нее
                                        return ;
                                }
                                //leaf не пустой. проверяем - сколько первых символов совпадают в leaf и current_key
                                int eq_syms_count = get_identical_symbols_count(current_vertex->leaf,current_key);
                                if (eq_syms_count>0){
                                        //надо распределить первые символы leaf, создать новый элемент и перейти в него
                                        vertex* arc_v = expand_leaf_and_ret_child(current_vertex,eq_syms_count);
                                        current_key += eq_syms_count;
                                        current_vertex = arc_v;

                                } else{
                                        //в leaf и current_key первые символы разные
                                        //оставляем leaf как есть, создаем новый элемент, переходим в него
                                        vertex* arc_v = malloc_and_init_vertex();
                                        arc_v->parent = current_vertex;
                                        current_vertex->arcs[index] = arc_v;
                                        current_vertex->arcs_count++;
                                        current_key++;
                                        current_vertex = arc_v;
                                }
                        } else{
                                //leaf пустой. смотрим значение
                                if (!current_vertex->value){
                                        //значения нет.
                                        //сохраняем key -> leaf
                                        current_vertex->leaf = strdup(current_key);
                                        //value -> current_vertex->value
                                        current_vertex->value = strdup(value);
                                        return ;
                                } else{
                                        //уже есть значение
                                        //создаем потомка
                                        vertex* arc_v = malloc_and_init_vertex();
                                        arc_v->parent = current_vertex;
                                        current_vertex->arcs[index] = arc_v;
                                        current_vertex->arcs_count++;
                                        current_vertex = arc_v;
                                        current_key++;
                                }
                        }
                } else{
                        //такая дуга уже есть. переходим в нее
                        current_key++;
                        current_vertex = nv;
                }
        }
        //полностью перебрали ключ, нашли последнюю вершину
        if (current_vertex){
                //у него может быть leaf
                //убираем leaf в дугу
                if (current_vertex->leaf) {vertex* v1 = expand_leaf_and_ret_child(current_vertex,1);};
                //if (current_vertex->value) free(current_vertex->value);
                current_vertex->value = strdup(value);
        }
}
//спуск по дереву до определенного ключа
vertex* descent_to(vertex* head_v, char* key){
        vertex* cv = head_v;
        char* current_key = key;
        while (strlen(current_key) > 0){
                //есть leaf?
                if (cv->leaf)
                        //leaf совпадает с ключем
                        if (strcmp(cv->leaf,current_key)==0) break;
                        char c = current_key[0];
                        int index = c - '0';
                        vertex* v = cv->arcs[index];
                        if (!v) return 0;// такой дуги нет
                        //такая дуга есть, переходим в нее
                        current_key++;
                        cv = v;
        }
        //дошли до конца
        return cv;
}

char* lookup_key(vertex* head_v, char* key){
        vertex* v = descent_to(head_v,key);
        char* ret_value = 0;
        if (v) ret_value = v->value;
        return ret_value;
}

int delete_key(vertex* head_v, char* key){
        int e_count = 0;

        vertex* v = descent_to(head_v,key);
        if (!v) return 0;
        //весь ключ в leaf
        if (v->leaf){
                //free (v->leaf);
                v->leaf = 0;
        }
        if (v->value){
                //free (v->value);
                v->value = 0;
        }
        //если узел не конечный - выходим
        if (v->arcs_count) return 0;
        //надо удалять узел и двигаться вверх по дереву
        do{
                vertex* parent_v = v->parent;
                int i;
                if (!parent_v) break;
                for (i = 0; i != VERTS_COUNT; i++)
                        if (parent_v->arcs[i] == v){
                                parent_v->arcs[i] = 0;
                                parent_v->arcs_count--;
                                //if (v->value) free (v->value);
                                //free (v);
                                e_count ++;
                                //узел удалили, начинаем проверять родителя
                                v = parent_v;
                                break;
                        }
                //если поднялись на самый верх - выходим
                if (!v) break;
        }
        while ((v->arcs_count==0)&&(v->leaf==0)&&(v->value==0));

        return e_count;
}

#define SIZE 22000
#define AVG_LEN 80

int main(int argc,char** argv){
        vertex head_vertex;
        init_vertex(&head_vertex);

        int i, j, n;
        char word_arr[SIZE][AVG_LEN+1];
        double time1, time4;

        FILE *fp = fopen("test_80_200k_bin_firstsame_3qtrs.txt", "r");
        if (NULL == fp) printf("cannot open file\n");
        FILE *ff = fopen("test_80_200k_bin_firstsame_3qtrs_RESULT.csv", "w");
    //"test_5_200k_bin.txt"
    //"test_40_200k_bin.txt"
    //"test_40_200k_bin_firstsame.txt"
    //"test_80_200k_bin_first34same.txt"

        for (i = 0; i < SIZE; i++) fscanf(fp, "%s\n", word_arr[i]);

        fprintf(ff, "Num of keys;Time");
        for (j = 0; j <= SIZE; j+=2000) {
            time1 = clock();
            for (i = 0; i < j; i++) insert_key(&head_vertex, word_arr[i], "");
            time4 = clock() - time1;
            fprintf(ff, "%d;=%.3G\n", j, time4);
        }


        printf("Compact\n");
        printf("i=%d\n", i);
        printf("time4=%.2lf\n", time4);

        fclose(fp);
        fclose(ff);
/*
        char command[10], key[1000], value[1000];
        scanf("%d", &n);                        //num of commands
        for (i = 0; i < n; i++) {
                scanf("%s", command);
                if ('i' == command[0]) {        //insert
                        scanf("%s%s", key, value);
                        insert_key(&head_vertex,key, value);
                }
                if ('d' == command[0]) {        //delete
                        int d_count = 0;
                        scanf("%s", key);
                        d_count = delete_key(&head_vertex,key);
                        printf("deleted %d nodes\n",d_count);
                }
                if ('l' == command[0]) {        //lookup
                        scanf("%s", key);
                        char *value;
                        value = lookup_key(&head_vertex,key);
                        if (value) printf("%s\n",value);
                }
        }*/
        return 0;
}