Radix Tree - Rafael Rivas

#include <iostream>
#include <string.h>
#include <conio.h>
#include <Windows.h>
using namespace std;

class Radix {
private:
    struct node {
        node *key[26];
        string word;
        node(string word) :word(word) {
            for (int i = 0; i < 26; i++) {
                key[i] = nullptr;
            }
        }
    };
    node* root;
public:
    Radix(){
        root = new node("");
    }
    node* get_root() {
        return root;
    }
    char* findsuf(string word1,string word2) {
        string newsuf;
        int n = 0;
        int g = 0;
        for (int i = 0; i < word2.size(); i++) {
            if (word1.at(i) == word2.at(i)) {
                g = g + 1;
            }
            else
                break;
        }
        n = word1.size();
        newsuf = word1.substr(g, n);
        char *x = strdup(newsuf.c_str());
        return x;
    }
    void insert(string word) {
        node* aux = root;
        node* act = root;
        string newpref;
        bool esultimo = 0;
        int p = 0;
        int r;
        int t = word.size();
        int idx_w = 0;
        int idx_nodo = idx_w;
        int i = 0;
        int index = word.at(i) - 'a';
        act = act->key[index];
        bool proceso = false; // crear sufijo y prefijo
        if (act == nullptr) {
            aux->key[index] = new node(word);
            proceso = true;
        }
        while (act != nullptr && !proceso) {
            idx_nodo = idx_w;
            for (i = 0; i < act->word.size(); i++) {
                int e = word.at(idx_w) - 'a';
                int a = act->word.at(i) - 'a';
                if (word.at(idx_w) != act->word.at(i) && act->key[e] == nullptr && act->key[a] == nullptr) {
                    newpref = act->word.substr(0, i);
                    aux->key[index] = new node(newpref);
                    node* nuevo = aux->key[index];
                    string n_word = word.substr(idx_nodo, word.size());
                    char* E = findsuf(n_word, act->word);
                    string SE(E);
                    char* A = findsuf(act->word, n_word);
                    string SA(A);
                    nuevo->key[a] = act;
                    nuevo->key[e] = new node(E);
                    act->word = SA;
                    proceso = true;
                    break;
                }
                idx_w++;
            }
            aux = act;
            index = word.at(idx_w) - 'a';
            act = act->key[index];
        }

        if (!proceso) {
            if (t > idx_w) {
                string n_word = word.substr(idx_nodo, t);
                char* suf = findsuf(n_word, aux->word); // aguacate, agua => cate
                string SE(suf);
                aux->key[index] = new node(suf);
            }
        }
    }
    void gotoxy(int x, int y) {
        HANDLE hcon;
        hcon = GetStdHandle(STD_OUTPUT_HANDLE);
        COORD dwPos;
        dwPos.X = x;
        dwPos.Y = y;
        SetConsoleCursorPosition(hcon, dwPos);
    }
    void mostrar(node* a,int x,int y) {
        node*aux = a;
        for (int i = 0; i < 26; i++) {
            if (aux->key[i] != nullptr) {
                y++;
                gotoxy(x, y);
                if (y++) {
                    x = x - 2;
                }
                switch (y)
                {
                case 2: { x = x - 3;

                }
                //case 3: {
                //  x = x - 4;
                //}
                //case 4: {
                //  x = x - 3;
                //}
                //case 5:
                //{
                //  x = x - 2;
                //}
                }
                char *a = strdup(aux->key[i]->word.c_str());
                cout << a<<endl;
                mostrar(aux->key[i],x,y);
                y--;
                switch (y)
                {
                case 1: { x = x + 10;

                }
                case 2: {
                    x = x + 8;
                }
                case 3: {
                    x = x + 6;
                }
                case 4:
                {
                    x = x + 4;
                }
                case 5:
                {
                    x = x + 2;
                }
                }

                if (y--)
                {
                    x = x + 7;
                }

            }
        }
    }
};

void main() {
    Radix* arbol = new Radix();
    arbol->insert("jugar");
    arbol->insert("juego");
    arbol->insert("jugo");
    arbol->insert("jugare");
    arbol->insert("jugamos");
    arbol->insert("ganamos");
    arbol->insert("ganar");
    arbol->insert("gane");
    arbol->insert("gato");
    arbol->insert("gata");
    arbol->mostrar(arbol->get_root(),20,0);
    _getch();

}