Trie

#ifndef TRIE_INCLUDED
#define TRIE_INCLUDED

#include <cassert>

//Estado: Pasa tests (valgrind incluido) con un diccionario de 847 palabras.
/*BUGS Y DETALLES CONOCIDOS:
    Sobreescribe el valor si hay repetidos, lo cual genera perdidas de memoria. Se pide que la clave no este previamente definida para eso.
    No tiene soporte para letras en mayuscula ni numeros ni caracteres
*/

#define ALPHABET_SIZE 26
char alphabet[ALPHABET_SIZE] = {
    'a','b','c','d','e','f','g','h',
    'i','j','k','m','n','l','o','p','q',
    'r','s','t','u','v','w','x','y','z'};

int chr2int(char c){
    for(int i = 0; i < ALPHABET_SIZE; i++)
        if(alphabet[i] == c) return i;
    return -1;
}

template<typename T>
class DiccString{
    public:
        DiccString();
        ~DiccString();
        bool estaDef(std::string);
        T & obtener(std::string); //PRE: la key esta definida en el diccionario
        void definir(std::string, T e); //PRE: la key no esta definida
    private:
        struct Nodo{
            T * value;
            Nodo * keys[ALPHABET_SIZE];
            Nodo(){
                value = NULL;
                for(int i = 0; i < ALPHABET_SIZE; i++)
                    keys[i] = NULL;
            }
            void destruir(){
                for(int i = 0; i < ALPHABET_SIZE; i++)
                    if(keys[i] != NULL){
                        keys[i]->destruir();
                        delete keys[i];
                    }
                if(value != NULL){
                    delete value;
                }
            }
        };
        Nodo * root;
};

template<typename T>
DiccString<T>::DiccString(){
    root = NULL;
}

template<typename T>
DiccString<T>::~DiccString(){
    if(root != NULL){
        root->destruir();
        delete root;
    }
}


template<typename T>
void DiccString<T>::definir(std::string s, T e){
    if(root == NULL) root = new Nodo();
    Nodo * n = root;

    for(unsigned int i = 0; i < s.size(); i++){
        if(n->keys[chr2int(s[i])] == NULL)
            n->keys[chr2int(s[i])] = new Nodo();

        n = n->keys[chr2int(s[i])];
    }

    n->value = new T(e);
}

template<typename T>
bool DiccString<T>::estaDef(std::string s){
    Nodo * n = root;
    unsigned int i = 0;
    for(i; i < s.size(); i++){
        if(n == NULL) break;
        n = n->keys[chr2int(s[i])];
    }

    return i == s.size();
}

template<typename T>
T & DiccString<T>::obtener(std::string s){
    Nodo * n = root;
    for(unsigned int i = 0; i < s.size(); i++)
        n = n->keys[chr2int(s[i])];

    return *(n->value);
}

#endif