#include<iostream>
#include<string.h>
#include<cstdlib>
//#include "trie.h"

using namespace std;

#define MAX_LINE_LENGTH 23
class Trie{

    private:
        unsigned int w_count;
        unsigned int nodes_count;

        Trie *nodes[26]; // este folosit alfabetul englez: a..z

    public:

        Trie();
        ~Trie();

        bool insert_word(char* word);
        bool erase_word(char* word);
        unsigned int get_word_count(char* word);
        unsigned int get_prefix_length(char* word);
};
FILE* input;
FILE* output;
char* line;
Trie* root;

void delete_data(){
    if(input){
        fclose(input);
        input = nullptr;
    }
    if(output){
        fclose(output);
        output = nullptr;
    }
    if(root){
        delete root;
        root = nullptr;
    }
    if(line){
        free(line);
        line = nullptr;
    }
}
int main(){

    input = fopen("trie.in", "r");
    if(!input){
        printf("[-] Error: no input file\n");
        delete_data();
        return -1;
    }
    output = fopen("trie.out", "w+");
    if(!output){
        printf("[-] Error: no output\n");
        delete_data();
        return -1;
    }

    line = (char*)malloc(MAX_LINE_LENGTH * sizeof(char));
    if(!line){
        printf("[-] Error: alloc word has failed\n");
        delete_data();
        return -1;
    }
    
    int word_count = 0, prefix_length = 0;

    root = new Trie();

    if(!root){
        printf("[-] Error: trie alloc has failed\n");
        delete_data();
        return -1;
    }
    while(fgets(line, MAX_LINE_LENGTH, input)){
        
        switch(line[0]){
            case '0': 
            {
                if(!root->insert_word(line + 2)){
                    printf("[-] Error: root insert string %s has failed\n", line + 2);
                    delete_data();
                    return -1;
                }
                printf("[+] Insert success\n");
                break;
            }
            case '1':
            {
                if(root->erase_word(line + 2)){
                    printf("[-] Error: root delete string: %s has failed\n", line + 2);
                    delete_data();
                    return -1;
                }
                printf("[+] Delete success\n");
                break;
            }
            case '2':
            {
                word_count = root->get_word_count(line + 2);

                if(word_count == -1){
                    printf("[-] Error: word count has failed\n");
                    delete_data();
                    return -1;
                }
                printf("[+] Word count success: %d\n", word_count);
                fprintf(output, "%d\n", word_count);
                break;
            }
            case '3':
            {
                prefix_length = root->get_prefix_length(line + 2);

                if(prefix_length == -1){
                    printf("[-] Error: word count has failed\n");
                    delete_data();
                    return -1;
                }
                printf("[+] Prefix length success: %d\n", prefix_length);
                fprintf(output, "%d\n", prefix_length);
                break;
            }
        }
    }     
    delete_data();
    return 0;
}

Trie::Trie(){

    this->w_count = 0;
    this->nodes_count = 0;

    for(unsigned int i=0; i<26; i++){
        this->nodes[i] = nullptr;
    }
    
}

Trie::~Trie(){

   this->w_count = 0;
   this->nodes_count = 0;

    for(unsigned int i=0; i<26; i++){
        if(!this->nodes[i]){
            continue;
        }
        delete this->nodes[i];
        this->nodes[i] = nullptr;
    }
}

bool Trie::insert_word(char* word){
    
    if(!*word){
        // end of word
        this->w_count++;
        return true;
    }

    if(!this->nodes[*word - 'a']){

        this->nodes[*word - 'a'] = new Trie();
        if(!this->nodes[*word - 'a']){
            printf("[-] Error: alloc trie has failed\n");
            return false;
        }
        this->nodes_count++;
    }

    return (this->nodes[*word - 'a'])->insert_word(word + 1);
}

bool Trie::erase_word(char* word){
    
    if(!*word){
        this->w_count--;
    }
    else if(this->nodes[*word - 'a']->erase_word(word + 1)){

        delete this->nodes[*word - 'a'];
        this->nodes[*word - 'a'] = nullptr;

        //TODO:verificari
        if(this->nodes_count)
            this->nodes_count--;
    }
     
    if(this->w_count == 0 && this->nodes_count == 0)
        return 1;
    
    return 0;
}

unsigned int Trie::get_word_count(char* word){
    
    if(!*word){
        return this->w_count;
    }

    if(this->nodes[*word - 'a']){
        return this->nodes[*word - 'a']->get_word_count(word + 1);
    }
    return 0;
}

unsigned int Trie::get_prefix_length(char* word){
    
    if(!*word || !(this->nodes[*word - 'a'])){
        return 0;
    }
    return 1 + this->nodes[*word - 'a']->get_prefix_length(word + 1); 
}