#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')//convertim un caracter intr-un index
//structura pentru un nod din arbore
typedef struct Trie
{
    char data;
    int final_string;
    struct Trie *next[26];
}Node;
//structura pentru stiva
typedef struct ELEM
{
    Node *valoare;
    struct ELEM *next;
}stackNode;
//declaram functiile
Node *createNode ();
void insertNode ( Node *root, char *sir );
int searchNode (Node *root, char *sir );
int isLeaf ( Node * root );
void push ( stackNode **top, Node *v );
Node *pop ( stackNode **top );
void DeleteStack ( stackNode **top );
void sugestie ( Node *root, char *sir );
int autocomplete ( Node *root, char *sir );

int main()
{
   Node *root = NULL;
   root = createNode ();

   insertNode ( root, "hello" );
   printf ( "%d\n", searchNode ( root, "hello" ) );
   insertNode ( root, "hel" );
   printf ( "%d\n", searchNode ( root, "hel" ) );
   insertNode ( root, "ana" );
   printf ( "%d\n", searchNode ( root, "ana" ) );
   insertNode ( root, "hell" );
   printf ( "%d\n", searchNode ( root, "hell" ) );
   insertNode ( root, "help" );
   printf ( "%d\n", searchNode ( root, "help" ) );
   insertNode ( root, "anabel" );
   printf ( "%d\n", searchNode ( root, "anabel" ) );
   insertNode ( root, "helps" );
   printf ( "%d\n", searchNode ( root, "helps" ) );
   insertNode ( root, "ce" );
   printf ( "%d\n", searchNode ( root, "ce" ) );
   insertNode ( root, "helping" );
   printf ( "%d\n", searchNode ( root, "helping" ) );

   int comp = autocomplete ( root, "hel" );
   if ( comp == -1 )
        printf ( "Nu s-au gasit alte cuvinte cu acest prefix" );
   else if ( comp == 0)
        printf ( "Nu s-a gasit niciun cuvant cu acest prefix" );
   return 0;

}

Node *createNode ()
{
    int i;
    Node *newNode = malloc ( sizeof (Node) );
    newNode -> final_string = 0;
    for ( i = 0; i < 26; i++ )
        newNode -> next[i] = NULL;
    return newNode;
}

void insertNode ( Node *root, char *sir )
{
    Node *current = root;
    while (*sir)
    {
        if ( current -> next [ *sir - 'a' ] == NULL )
            current -> next [ *sir - 'a' ] = createNode ();
        current = current -> next [ *sir - 'a' ];
        sir ++;
    }
    current -> final_string = 1;
}

int searchNode (Node *root, char *sir )
{
    if ( root == NULL )
        return 0;

    Node *current = root;
    while (*sir)
    {
        current = current -> next [ *sir - 'a' ];
        if ( current == NULL )
            return 0;
        sir++;
    }

    return current -> final_string;
}

int isLeaf ( Node * root )
{
    int i;
    for ( i = 0; i < 26; i++ )
        if ( root -> next[i])
            return 1;
    return 0;
}

//adaugare element in stiva
void push ( stackNode **top, Node *v )
{
    stackNode *newNode = malloc ( sizeof (Node) );
    newNode -> valoare -> data = v -> data;
    newNode -> next = *top;
    *top = newNode;//adaugam doar in varful stivei
}
//scoatere element din stiva
Node *pop ( stackNode **top )
{
    if ( isEmpty ( *top ) )
        return NULL;//daca e goala,returnez NULL
    stackNode *temp = (*top);//stochez adresa varfului in temp
    Node *d = NULL;
    strcpy ( d, temp -> valoare );//stochez valoarea din varf intr_un auxiliar
    *top = (*top) -> next;//sterg elementul din varf
    free (temp);//eliberez memeoria ocupata de temp
    return d;
}
//stergere stiva
void DeleteStack ( stackNode **top )
{
    stackNode *topCopy = *top, *temp;
    while ( topCopy != NULL )
    {
        temp = topCopy;
        topCopy = topCopy -> next;
        printf ( "%s", temp -> valoare ->data );
        free (temp);
    }
    *top = NULL;
}

void sugestie ( Node *root, char *sir)
{
    sir = malloc ( 26 * sizeof (char) );
    stackNode *S = NULL;
    if ( root -> final_string )
    {
        printf ( "%s", sir );
        printf ("\n");
    }

    if ( isLeaf (root) )
        return ;

    int i;
    for ( i = 0; i < 26; i++ )
    {
        if ( root -> next[i] )
        {
            push ( &S, root );
            sugestie ( root -> next[i], sir );
            sir= pop (&S);
        }
    }
    DeleteStack (&S);
}

int autocomplete ( Node *root, char *sir )
{
    Node *temp = root;
    int i, n;
    sir = malloc ( 40 * sizeof (char) );
    n = strlen (sir) - 1;
    int index;
    for ( i = 0; i < n; i ++ )
    {
        index = CHAR_TO_INDEX ( sir[i] );
        if ( ! temp -> next[index] )
            return 0;
        temp = temp -> next[index];
    }

    if ( temp -> final_string == 1 && isLeaf (temp) )
    {
        printf ( "%s\n", sir );
        return -1;
    }

    char *prefix = malloc ( n * sizeof (char) );
    if ( isLeaf (temp) )
    {
        prefix = sir;
        sugestie ( temp, prefix );
        return 1;
    }

}