/*
    SD 2023 - Trie
*/

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

#define ALPHABET_SIZE 26
#define ALPHABET "abcdefghijklmnopqrstuvwxyz"

typedef struct trie_node_t trie_node_t;
struct trie_node_t {
    /* Value associated with key (set if end_of_word = 1) */
    void* value;

    /* 1 if current node marks the end of a word, 0 otherwise */
    int end_of_word;

    trie_node_t** children;
    int n_children;
};

typedef struct trie_t trie_t;
struct trie_t {
    trie_node_t* root;
    
    /* Number of keys */
    int size;

    /* Generic Data Structure */
    int data_size;

    /* Trie-Specific, alphabet properties */
    int alphabet_size;
    char* alphabet;

    /* Callback to free value associated with key, should be called when freeing */
    void (*free_value_cb)(void*);

    /* Optional - number of nodes, useful to test correctness */
    int nNodes;
};
trie_node_t* trie_create_node(trie_t * trie) {
    trie_node_t* new_node = (trie_node_t*)malloc(sizeof(trie_node_t));

    new_node->value = NULL;
    new_node->end_of_word = 0;
    new_node->n_children = trie->alphabet_size;
    new_node->children = (trie_node_t**)calloc(trie->alphabet_size, sizeof(trie_node_t));

    trie->nNodes++;

    return new_node;
}

trie_t* trie_create(int data_size, int alphabet_size, char* alphabet, void (*free_value_cb)(void*)) {
    trie_t* trie = (trie_t*)malloc(sizeof(trie_t));

    trie->size = 0;
    trie->data_size = data_size;
    trie->alphabet_size = alphabet_size;
    trie->alphabet = strdup(alphabet);trie->root = trie_create_node(trie);
    trie->free_value_cb = free_value_cb;
    trie->nNodes = 0;

    return trie;
}

void trie_insert(trie_t* trie, char* key, void* value) {
    trie_node_t* current_node = trie->root;

    for(int i = 0; i < strlen(key); ++i) {
        char letter = key[i];

        if(!current_node->children) {
            current_node->children = malloc(ALPHABET_SIZE * sizeof(trie_node_t*));
            for (int j = 0; j < ALPHABET_SIZE; ++j)
                current_node->children[j] = NULL;
        }

        if(!current_node->children[letter - 'a']) {
            current_node->children[letter - 'a'] = trie_create_node(trie);
        }

        current_node = current_node->children[letter - 'a'];
    }

    current_node->end_of_word = 1;
    current_node->value = malloc(trie->data_size);
    memcpy(current_node->value, value, trie->data_size);
    ++trie->size;
}

void* trie_search(trie_t* trie, char* key) {
    trie_node_t* current_node = trie->root;

    for(int i = 0; i < strlen(key); ++i) {
        int char_index = key[i] - 'a';

        if(!current_node->children[char_index]) {
            return NULL;
        }

        current_node = current_node->children[char_index];
    }

    if(current_node != NULL && current_node->end_of_word) {
        return current_node->value;
    }

    return NULL;
}

int delete_helper(trie_t* trie, trie_node_t* node, char* key, int level) {
    if (node) {
        if (level == strlen(key)) {
            if (node->end_of_word) {
                node->end_of_word = 0;

                if (node->children == NULL || node->n_children == 0) {
                    if(trie->free_value_cb && node->value)
                        trie->free_value_cb(node->value);
                    node->value = NULL;
                    trie->nNodes--;
                    return 1;
                }
                return 0;
            }
        } else {
            int char_index = key[level] - 'a';

            if (delete_helper(trie, node->children[char_index], key, level + 1)) {
                free(node->children[char_index]);
                node->children[char_index] = NULL;

                if (!node->end_of_word) {
                    for (int i = 0; i < trie->alphabet_size; ++i) {
                        if (node->children[i]) {
                            return 0;
                        }
                    }

                    trie->nNodes--;
                    return 1;
                }
            }
        }
    }
    
    return 0;
}

void trie_remove(trie_t* trie, char* key) {
    int level = 0;
    if (delete_helper(trie, trie->root, key, level)) {
        free(trie->root->children[key[0] - 'a']);
        trie->root->children[key[0] - 'a'] = NULL;
        trie->root->n_children--;
    }
    
}


void trie_free_node(trie_t* trie, trie_node_t* node) {
    if(!node) {
        return;
    }
    for(int i = 0; i < trie->alphabet_size; ++i) {
        trie_free_node(trie, node->children[i]);
    }

    if(node->value && trie->free_value_cb) {
        trie->free_value_cb(node->value);
    }

    free(node->children);
    free(node);
    trie->nNodes--;
}

void trie_free(trie_t** pTrie) {
    trie_t* trie = *pTrie;

    trie_free_node(trie, trie->root);
    free(trie->alphabet);
    free(trie);

    *pTrie = NULL;
}

/* Needed for Lambda tests, ignore :) */
void cleanup_example_string(char* str) {
    int len = strlen(str);
    
    if(len >= 2 && str[len-2] == '\\') {
        str[len-2] = '\0';
    }
}

int main() {
    int n, value;
    char alphabet[] = ALPHABET;
    char buf[256], key[256], op;
    
    trie_t* trie = trie_create(sizeof(int), ALPHABET_SIZE, alphabet, free);
    
    fgets(buf, 256, stdin);
	sscanf(buf, "%d\n", &n);

    for(int i = 0; i < n; ++i) {
        fgets(buf, 256, stdin);
	    sscanf(buf, "%c", &op);

        if(op == 'i') {
	        sscanf(buf, "%c %s %d\n", &op, key, &value);
            trie_insert(trie, key, &value);
        } else if(op == 'r') {
	        sscanf(buf, "%c %s\n", &op, key);
            cleanup_example_string(key);
            printf("nNodes before removing %s: %d\n", key, trie->nNodes);
            trie_remove(trie, key);
            printf("nNodes after removing %s: %d\n", key, trie->nNodes);
        } else if(op == 's') {
            sscanf(buf, "%c %s\n", &op, key);
            cleanup_example_string(key);

            if(key[0] == '_') {
                key[0] = '\0';
            }

            int* found = trie_search(trie, key);
            printf("%s: ", key[0] == '\0' ? "_" : key);

            if(found) {
                printf("%d\n", *found);
            } else {
                printf("not found\n");
            }
        }
    }

    trie_free(&trie);

    return 0;
}