/* functie creare a unui nod */
struct NOD * creare_nod(){
    struct NOD * nod;

    /* alocare memorie nod*/
    nod = (struct NOD * ) malloc(sizeof(struct NOD));

    if (nod == NULL) {
        printf("Eroare: memoria nu a putut fi alocata!\n");
        return NULL;
    }

    /* citire valori nod */
    printf("\nIntroduceti cuvant:");
    scanf("%s", nod -> cuvant);

    nod -> next = NULL;

    return nod;
}

/* functie populare lista cu n cuvinte */
struct NOD * populare_lista(struct NOD * head, int n){
    int i;
    for (i = 0; i < n; i++){
        head = adaugare_nod_sfarsit_lista(head);
    }
    return head;
}

/* functie afisare lista cuvinte */
void afisare_lista(struct NOD * head){
    int i = 0;
    struct NOD * nod_curent;

    if (head == NULL) {
        printf("Atentie, lista este goala!\n");
        return;
    }

    nod_curent = head;

    while (nod_curent != NULL) {
        /* afisare valoare curenta si pozitionare nod urmator */
        printf("%d: %s\n", i++, nod_curent -> cuvant);
        nod_curent = nod_curent -> next;
    }
}

/* functie adaugare cuvant la sfarsitul listei */
struct NOD * adaugare_nod_sfarsit_lista(struct NOD * head) {
    int i = 0;
    struct NOD * nod_curent, * nod_nou;

    if (head == NULL) {
        printf("Atentie: lista este goala.");
        head = creare_nod();
        printf("Cuvantul a fost adaugat.\n");
        return head;
    }

    /*parcurge lista element cu element pentru a ajunge la ultimul nod*/
    nod_curent = head;

    while (nod_curent != NULL) {
        if (nod_curent -> next == NULL) {
            /* creare si inserare nod nou in lista */
            nod_nou = creare_nod();
            nod_curent -> next = nod_nou;

            printf("Cuvantul a fost adaugat.\n");
            return head;
        }
        nod_curent = nod_curent -> next;
    }
}

typedef struct llist
{
    char nume[256];
    int loc;
    struct llist* next;

} list;

typedef struct con
{
    int x;
    int y;
} configuratie;

list* addToSortedList(list* head, char* name, int loca)
{
    if(head == NULL)
    {
        return create(name, loca);
    }

    list* cur = head;
    list* newEl = (list*) malloc(sizeof(list));
    list* prev;
    list* aux;

    strcpy(newEl->nume, name);
    newEl->loc = loca;
    newEl->next = NULL;

    int i = 0;

    while(cur != NULL)
    {
        if(loca < cur->loc)
        {
            //Daca e mai mic decat head
            if(i == 0)
            {
                newEl->next = head;
                return newEl;
            }
            //Daca e mai mic ca urmatoru numar
            else
            {
                prev = get(head, i - 1);
                prev->next = newEl;
                newEl->next = cur;
                return head;
            }
        }
        else
        {
            if(getLastElement(head) == cur)
            {
                cur->next = newEl;
                return head;
            }
            //Locu e mai mare decat ala dinaintea lui
            else
            {
                //Locu e mai mic decat urmatoru
                if(loca < (cur->next)->loc)
                {
                    aux = cur->next;
                    cur->next = newEl;
                    newEl->next = aux;
                    return head;
                }
            }
        }

        cur = cur->next;
        if(cur == NULL) break;
        i++;
    }

    return head;
}

typedef struct nod{
    char key[30];
    struct nod * next;
} lista;

struct hashtable{
    struct nod** entries;
    int size; // dimensiunea maxima a vectorului de hash-uri
    int count; // numarul de elemente continute de hash table
};

int hashing(char* c)
{
    int i = 0;
    int suma = 0;

    while(*(c+i) != '\0')
    {
        suma += *(c+i);
    }

    return suma % 7;
}

/*functie creare nod nou */
struct NOD* creare_nod(int x)
{
    struct NOD * nod_nou;

    /*alocare memorie nod*/
    nod_nou = (struct NOD *) malloc(sizeof(struct NOD));

    if (nod_nou == NULL)
    {
        printf("Eroare: Memoria nu a putut fi alocata! \n");
        return NULL;
    }

    /*initializare informatii */
    nod_nou->x = x;
    nod_nou->NOD_stanga = NULL;
    nod_nou->NOD_dreapta = NULL;

    return nod_nou;
}

/*inserare nod in arbore */
struct NOD* inserare_nod(struct NOD *prim, int x)
{
    struct NOD *nod_nou, *nod_curent, *nod_parinte;

    nod_nou = creare_nod(x);

    if (prim == NULL)
    {
        /*arborele este vid */
        prim = nod_nou;
        printf("A fost adaugat primul nod: %d. \n", prim->x);
        return prim;
    }
    else
    {
        /*pozitionare in arbore pe parintele nodului nou */
        nod_curent = prim;

        while (nod_curent != NULL)
        {
            nod_parinte = nod_curent;

            if (x < nod_curent->x) /*parcurgere spre stanga */
                nod_curent = nod_curent->NOD_stanga;
            else /*parcurgere spre dreapta */
                nod_curent = nod_curent->NOD_dreapta;
        }

        /*creare legatura nod parinte cu nodul nou */
        if (x < nod_parinte->x)
        {
            /*se insereaza la stanga nodului parinte */
            nod_parinte->NOD_stanga = nod_nou;
            printf("Nodul %d a fost inserat la stanga nodului %d. \n", x, nod_parinte->x);
        }
        else
        {
            /*se insereaza la dreapta nodului parinte */
            nod_parinte->NOD_dreapta = nod_nou;
            printf("Nodul %d a fost inserat la dreapta nodului %d.\n",
                x, nod_parinte->x);
        }

        return prim;
    }
}

/*parcurgere arbore in preordine */
void afisare_preordine(struct NOD *prim)
{
    if (prim != NULL)
    {
        /*parcurgere radacina, stanga, dreapta */
        printf("%d \n", prim->x);
        afisare_preordine(prim->NOD_stanga);
        afisare_preordine(prim->NOD_dreapta);
    }
}

/*parcurgere arbore in inordine */
void afisare_inordine(struct NOD *prim)
{
    if (prim != NULL)
    {
        /*parcurgere stanga, radacina, dreapta */
        afisare_inordine(prim->NOD_stanga);
        printf("%d \n", prim->x);
        afisare_inordine(prim->NOD_dreapta);
    }
}

/*parcurgere arbore in postordine */
void afisare_postordine(struct NOD *prim)
{
    if (prim != NULL)
    {
        /*parcurgere stanga, dreapta, radacina */
        afisare_postordine(prim->NOD_stanga);
        afisare_postordine(prim->NOD_dreapta);
        printf("%d \n", prim->x);
    }
}

/*stergerea unui arbore sau subarbore */
struct NOD* stergere_arbore(struct NOD *tmp)
{
    if (tmp != NULL)
    {
        stergere_arbore(tmp->NOD_stanga);
        stergere_arbore(tmp->NOD_dreapta);
        free(tmp);
    }

    return NULL;
}

/*cautarea unui nod dorit */
struct NOD* cauta_nod(struct NOD *tmp, int x)
{
    if (tmp != NULL)
    {
        if (x == tmp->x)
        {
            printf("Nodul a fost gasit. \n");
            return tmp;
        }
        else if (x < tmp->x)
            return cauta_nod(tmp->NOD_stanga, x);
        else
            return cauta_nod(tmp->NOD_dreapta, x);
    }
    else
    {
        printf("Nodul dorit nu exista in arbore.\n");
        return NULL;
    }
}

typedef struct arb
{
    int x;
    struct arb* stanga;
    struct arb* dreapta;
} arbore;

arbore* create(int val)
{
    arbore* a = (arbore*) malloc(sizeof(arbore));
    a->x = val;
    a->stanga = NULL;
    a->dreapta = NULL;
    return a;
}

arbore* addToTree(arbore* root, int val)
{
    arbore* current;

    if(root == NULL)
    {
        create(val);
    }
    else
    {
        current = root;

        while(current != NULL)
        {
            root = current;

            //Mergem spre stanga
            if(val < current->val)
            {
                current = current->stanga;
            }
            else
            {
                current = current->dreapta;
            }
        }

        //Acum current e null, deci apelam la root-ul lui
        if(val < root->x)
        {
            root->stanga = create(val);
        }
        else
        {
            root->dreapta = create(val);
        }
    }
}

typedef struct arb
{
    struct arb *stanga;
    struct arb *dreapta;
    int val;
} arbore;

arbore* search(arbore *root, int val)
{
    if(root != NULL)
    {
        if(root->val == val)
        {
            return root;
        }
        else if(val < root->val)
        {
            return search(root->stanga, val);
        }
        else
        {
            return search(root->dreapta, val);
        }
    }
}

arbore* remove(arbore* root)
{
    if(root != NULL)
    {
        remove(root->stanga);
        remove(root->dreapta);
        free(root);
    }

    return NULL;
}

arbore* add(arbore *root, int val)
{
    if(root == NULL)
    {
        return create(val);
    }
    else
    {
        arbore *current;
        arbore *parent;

        current = root;

        while(current != NULL)
        {
            parent = current;

            if(val < current->val)
            {
                current = current->stanga;
            }
            else
            {
                current = current->dreapta;
            }
        }

        if(val < parent->val)
        {
            parent->stanga = create(val);
        }
        else
        {
            parent->dreapta = create(val);
        }

        return root;
    }
}