#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>


typedef struct Cvor {
    int info;
    struct Cvor* levo;
    struct Cvor* desno;
    struct Cvor* roditelj;
}Cvor;


int ternarnaPretraga(int* tabela, int* vektor, int br_kljuceva, int faktor_uvecanja, int zadati_kljuc, int* indeks, int* n);
int* napraviNiz(int* br_kljuceva, int faktor_uvecanja);
void ispis(int* tabela, int n);
void stek_stavi(int* stek, int* top, int broj);
int* stek_skini(int* stek, int* top);
Cvor* napraviStablo(int* tabela, int* vektor, int* indeks, int* n, int zadati_kljuc, int br_kljuceva);
Cvor* napraviCvor(int broj);
Cvor* ubaciCvor(Cvor* koren, int broj);
Cvor* BSTubaci(Cvor* koren, Cvor* novi);
void obradiDesnoPodstablo(int* stek, int* top, Cvor* koren);
Cvor* BSTPretraga(Cvor* koren, int k);
void printInorder(Cvor* node);
void ispisStabla(Cvor* koren);
void ispisiRed(int* red, int* front, int* rear);

int main() {

    int br_kljuceva, zadati_kljuc = 0, kljuc, indeks, opcija, provera, n, broj, k;
    int* tabela; int* vektor;


    printf("Unesite broj elemenata niza\n");
    scanf("%d", &br_kljuceva);




    int faktor_uvecanja = 1;
    tabela = napraviNiz(&br_kljuceva, faktor_uvecanja);
    n = br_kljuceva;
    //ispis(tabela, n);

    vektor = malloc(n * sizeof(int));


    for (int i = 0; i < n; i++)
        vektor[i] = 1;


    Cvor* koren = napraviStablo(tabela, vektor, &indeks, &n, zadati_kljuc, br_kljuceva);


    printInorder(koren);



    printf("\nUnesite opciju\n");
    printf("1. Formiranje stabla\n");
    printf("2. Pretraga na zadatu vrednost\n");
    printf("3. Umetanje kljuca\n");
    printf("4. Ispis stabla\n");
    printf("5. Brisanje stabla\n");

    scanf("%d", &opcija);


    switch (opcija) {

    case 1:
        break;

    case 2: printf("Unesite kljuc\n");
        scanf("%d", &k);
        Cvor* trazeni_cvor = BSTPretraga(koren, k);
        if (trazeni_cvor != NULL) {
            printf("Trazeni cvor je: %d\n", trazeni_cvor->info);
        }
        else {
            printf("Trazeni cvor ne postoji\n");
        }
        break;

    case 3: printf("Unesite kljuc koji zelite da ubacite\n");
        scanf("%d", &k);
        Cvor* novi = napraviCvor(k);
        BSTubaci(koren, novi);
        printInorder(koren);
        break;



        scanf("%d", &opcija);

        printf("\nUnesite opciju\n");
        printf("1. Formiranje stabla\n");
        printf("2. Pretraga na zadatu vrednost\n");
        printf("3. Umetanje kljuca\n");
        printf("4. Ispis stabla\n");
        printf("5. Brisanje stabla\n");


    }
    printf("\nISPIS PO LEVEL ORDERU\n");
    ispisStabla(koren);
    printf("Nisam puko\n");

}

int* napraviNiz(int* br_kljuceva, int faktor_uvecanja) {


    int a, i, j, n;

    printf("Unesite elemente\n");
    n = (*br_kljuceva) * faktor_uvecanja;

    int* pomocni_niz = malloc(n * sizeof(int));

    for (i = 0; i < n; i++) {
        scanf("%d", &a);
        pomocni_niz[i] = a;
        for (j = 1; j < faktor_uvecanja; j++) {
            pomocni_niz[i + j] = a;
        }
        i = i + j - 1;

    }

    return pomocni_niz;

}

int ternarnaPretraga(int* tabela, int* vektor, int br_kljuceva, int faktor_uvecanja, int zadati_kljuc, int* indeks, int* n) {

    int prvi, poslednji, srednji1, srednji2, i, j;



    prvi = 0; poslednji = *n - 1;

    while (prvi <= poslednji) {

        srednji1 = prvi + (poslednji - prvi) / 3;
        srednji2 = poslednji - (poslednji - prvi) / 3;

        if (zadati_kljuc == tabela[srednji1]) {
            if (vektor[srednji1] == 1) {
                *indeks = srednji1;
                return tabela[srednji1];

            }
            else {
                int k = srednji1;
                while (zadati_kljuc == tabela[k])
                {
                    k--;
                }

                if (vektor[k + 1] == 1) {
                    *indeks = k + 1;
                    return tabela[srednji1];

                }
                else {
                    return 0;
                }


            }


        }


        if (zadati_kljuc == tabela[srednji2]) {
            if (vektor[srednji2] == 1) {
                *indeks = srednji2;
                return tabela[srednji2];

            }
            else {
                int k = srednji2;
                while (zadati_kljuc == tabela[k])
                {
                    k--;
                }

                if (vektor[k + 1] == 1) {
                    *indeks = srednji2;
                    return tabela[srednji2];
                }
                else {
                    //printf("\nne postoji kljuc\n");
                    return 0;
                }
            }
        }


        if (zadati_kljuc < tabela[srednji1]) {
            poslednji = srednji1 - 1;
        }
        if (zadati_kljuc > tabela[srednji1]) {
            prvi = srednji1 + 1;
        }
        if (zadati_kljuc < tabela[srednji2]) {
            poslednji = srednji2 - 1;
        }
        if (zadati_kljuc > tabela[srednji2]) {
            prvi = srednji2 + 1;
        }

    }

    if ((zadati_kljuc == tabela[prvi]) && (vektor[prvi] == 1)) {
        *indeks = prvi;
        return tabela[prvi];
    }
    else {
        *indeks = prvi;
        return 0;
    }


}

void ispis(int* tabela, int n) {

    for (int w = 0; w < n; w++) {
        printf("%d ", tabela[w]);
    }

    printf("\n");

}

void stek_stavi(int* stek, int* top, int broj) {

    if (stek == NULL) {
        printf("Greska na steku\n");
    }

    stek[++(*top)] = broj;

}

int* stek_skini(int* stek, int* top) {

    if (stek == NULL) {
        printf("Greska na steku2\n");
    }

    return stek[(*top)--];


}


Cvor* napraviStablo(int* tabela, int* vektor, int* indeks, int* n, int zadati_kljuc, int br_kljuceva) {

    Cvor* koren = NULL;
    Cvor* trenutni = NULL;

    int prvi, poslednji, srednji, srednji_prethodni, vrednost, brojac = 0, provera;

    provera = 1;
    int* stek = calloc(50, sizeof(int));
    int top = -1;

    poslednji = (*n);

    prvi = 0;
    srednji_prethodni = poslednji;

    //srednji_prethodni = srednji_prethodni + 1;

    while (1) {

        zadati_kljuc = (tabela[0] + tabela[srednji_prethodni - 1]) / 2;

        vrednost = ternarnaPretraga(tabela, vektor, n, 1, zadati_kljuc, indeks, n);

        srednji = *indeks;

        for (int j = srednji + 1; j < srednji_prethodni; j++) {

            stek_stavi(stek, &top, tabela[j]);
            brojac++;
        }

        /*if (provera == 1) {
            stek_stavi(stek, &top, tabela[(*n) - 1]);
            provera = 0;
        }*/

        if (brojac != 0)
            stek_stavi(stek, &top, brojac);

        brojac = 0;

        koren = ubaciCvor(koren, tabela[srednji]);

        if (srednji == 0)
            break;

        srednji_prethodni = srednji;

    }



    obradiDesnoPodstablo(stek, top, koren);

    return koren;

}

Cvor* napraviCvor(int broj) {

    Cvor* cvor = (Cvor*)malloc(1 * sizeof(Cvor));


    cvor->levo = NULL;
    cvor->desno = NULL;
    cvor->roditelj = NULL;
    cvor->info = broj;

    return cvor;

}

Cvor* ubaciCvor(Cvor* koren, int broj) {


    Cvor* cvor = napraviCvor(broj);


    if (koren == NULL) {

        koren = cvor;

        return koren;
    }

    Cvor* pomocni = koren;

    while (pomocni->levo != NULL) {
        pomocni = pomocni->levo;
    }

    pomocni->levo = cvor;
    cvor->roditelj = pomocni;

    return koren;

}

Cvor* BSTubaci(Cvor* koren, Cvor* novi) {

    //Kod prepisan iz knjige!
    Cvor* p = koren;
    Cvor* q = NULL;

    while (p != NULL) {
        q = p;

        if (novi->info == p->levo) {
            printf("Postoji kljuc\n");
            return;
        }
        else if (novi->info < p->info) {
            p = p->levo;

        }
        else
            p = p->desno;
    }

    if (q == NULL) {

        koren = novi;
    }
    else if (novi->info < q->info) {
        q->levo = novi;
        novi->roditelj = q;
    }
    else {
        q->desno = novi;
        novi->roditelj = q;
    }

    return koren;

}


void obradiDesnoPodstablo(int* stek, int top, Cvor* koren)
{
    int br_elem = 1;
    int broj, info1, info2, info3;
    Cvor* cvor1;
    Cvor* cvor2;
    Cvor* cvor3;

    int i;

    while (top > -1) {
        br_elem = stek_skini(stek, &top);

        while (br_elem != 0)
        {
            if (br_elem < 3)
            {
                for (i = 0; i < br_elem; i++)
                {
                    broj = stek_skini(stek, &top);
                    cvor1 = napraviCvor(broj);
                    BSTubaci(koren, cvor1);
                }
                br_elem -= i;
            }
            else
            {
                info3 = stek_skini(stek, &top);
                info1 = stek_skini(stek, &top);
                info2 = stek_skini(stek, &top);

                cvor1 = napraviCvor(info1);
                cvor2 = napraviCvor(info2);
                cvor3 = napraviCvor(info3);

                BSTubaci(koren, cvor1);

                cvor1->levo = cvor2;
                cvor1->desno = cvor3;

                cvor2->roditelj = cvor1;
                cvor3->roditelj = cvor1;

                br_elem -= 3;
            }
        }
    }

}

void printInorder(Cvor* koren)
{
    if (koren != NULL) {
        printInorder(koren->levo);
        printf("%d ", koren->info);
        printInorder(koren->desno);

    }

}

void red_stavi(Cvor** red, int* rear, Cvor* cvor) {

    if (red == NULL) {
        printf("Greska na redu\n");
    }
    //printf("na [%d] = %d\n", *rear, cvor->info);
    red[(*rear)++] = cvor;

}

Cvor* red_skini(Cvor** red, int* front) {

    if ((*red) == NULL) {
        printf("Greska na redu2\n");
    }
    Cvor* cvor = red[(*front)++];
    return cvor;


}

int prazan_red(int front, int rear) {
    if (front == rear) {
        printf("red je prazan\n");
        return 1;
    }
}



Cvor* BSTPretraga(Cvor* koren, int k) {

    Cvor* p = NULL;

    p = koren;

    while ((p != NULL) && (k != p->info)) {
        if (k < p->info) {
            p = p->levo;
        }
        else {
            p = p->desno;
        }
    }

    return p;
}

void ispisStabla(Cvor *koren) {

    Cvor** red = malloc(50 * sizeof(Cvor*));
    Cvor* sledeci = NULL;
    int front = 0; int rear = 0;
    int brojac = 0;
    sledeci = koren;
    int h = 0;
    red_stavi(red, &rear, sledeci);

    while (brojac < 5) {
        sledeci = red_skini(red, &front);

        printf("ispis: %d.. ___front: %d\n", sledeci->info, front);

        if (sledeci->levo != NULL) {

            red_stavi(red, &rear, sledeci->levo);
        }
        if (sledeci->desno != NULL) {
            red_stavi(red, &rear, sledeci->desno);
        }
        printf("rear: %d\n", rear);
        brojac++;


    }
    printf("\nfront: %d rear: %d", front, rear);
    front = 0;
    ispisiRed(red, &front, &rear);

    /*while (brojac > 0){

        sledeci->info = red_skini(red, &front);

        printf("%d..", sledeci->info);
        brojac--;
    }*/


}

void ispisiRed(Cvor** red, int* front, int* rear)
{
    Cvor* nesto = NULL; int i = 0, k;
    int broj = 16;
    printf("\n");
    for (i = (*front); i < (*rear); i++)
    {
        for (int j = 0; j < broj; j++) {
            printf(" ");
        }

        for ( k = 0; k < i + 1; k++) {
            printf("%d", red[k]->info);
        }


        for (int j = 0; j < broj; j++) {
                printf(" ");
        }
        printf("\n");
        i = i + k - 1;

    }
}