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

typedef struct puusolmu_t {
    int luku;
    short tila; /* tasapainoilmaisin */
    struct puusolmu_t *vasen, *oikea;
} puusolmu, *puuosoitin;


void lisaa_solmu(puuosoitin *emo, int luku, int *etp);
void oikea_kierto(puuosoitin *emo, int *etp);
void tulosta_puu(puuosoitin solmu);
void vasen_kierto(puuosoitin *emo, int *etp);
void etsi_puusta(puuosoitin solmu, int haku);
int maxDepth(puuosoitin solmu);
void structure (puuosoitin solmu, int level );



int main(void)
{
    FILE* myFile;
    myFile = fopen("/Users/oskar/OneDrive/Koulu/Tietorakenteet/Luento8/numerot.txt", "r");

    /*read file into array*/
    int luvut[16];
    int x;

    if (myFile == NULL){
        printf("Error Reading File\n");
        exit (0);
    }

    for (x = 0; x < 16; x++){
        fscanf(myFile, "%d,", &luvut[x] );
    }

    fclose(myFile);

    int choice = 4, adder, haku;
    int etp = 0, i;
    puuosoitin puu = NULL;

    for(i = 0; luvut[i] != 0; i++)
    {
        lisaa_solmu(&puu, luvut[i], &etp);
        printf("Vaihto\n");
        structure(puu,0);
    }
    printf("Nykyinen puu: ");
    structure(puu,0);


    printf("\n");

    while(choice != 0){
        printf("\n1) Tulosta puu\n"
                       "2) Etsi puusta\n"
                       "3) Lisää puuhun\n"
                       "0) Lopeta\n"
                       "Valintasi: ");
        scanf("%d",&choice);
        if (choice == 1){

        } else if (choice == 2){
            printf("Anna haettava luku: ");
            scanf("%d",&haku);
            etsi_puusta(puu, haku);

        }else if (choice == 3){
            printf("Anna lisättävä luku: ");
            scanf("%d",&adder);
            structure(puu,0);
            lisaa_solmu(&puu,adder,&etp);
            structure(puu,0);


        }else if (choice == 0){
            printf("Kiitos");
            return 0;
        }else{
            printf("Virheellinen valinta");
        }
    }





}


void lisaa_solmu(puuosoitin *emo, int luku, int *etp)
{

    if(!(*emo))
    {
        *etp = 1;
        if(!(*emo = (puuosoitin)malloc(sizeof(puusolmu))))
        {
            perror("malloc");
            exit(1);
        }
        (*emo)->vasen = (*emo)->oikea = NULL;
        (*emo)->tila = 0;
        (*emo)->luku = luku;
    } else if(luku < (*emo)->luku)
    {
        lisaa_solmu(&(*emo)->vasen, luku, etp);
        if(*etp)
        {
            switch((*emo)->tila)
            {
                case -1:
                    (*emo)->tila = 0;
                    *etp = 0;
                    break;
                case 0:
                    (*emo)->tila = 1;
                    break;
                case 1:
                    vasen_kierto(emo, etp);
            }
        }
    } else if(luku > (*emo)->luku)
    {
        lisaa_solmu(&(*emo)->oikea, luku, etp);
        if(*etp)
        {
            switch((*emo)->tila)
            {
                case 1:
                    (*emo)->tila = 0;
                    *etp = 0;
                    break;
                case 0:
                    (*emo)->tila = -1;
                    break;
                case -1:
                    oikea_kierto(emo, etp);
            }
        }
    } else
    {
        *etp = 0;
        printf("Luku %d on jo puussa\n", luku);
    }
}



void vasen_kierto(puuosoitin *emo, int *etp)
{
    puuosoitin lapsi, lapsenlapsi;

    lapsi = (*emo)->vasen;
    if(lapsi->tila == 1) /* LL-kierto */
    {
        printf("LL-kierto\n");
        (*emo)->vasen = lapsi->oikea;
        lapsi->oikea = *emo;
        (*emo)->tila = 0;
        (*emo) = lapsi;
    } else /* LR-kierto */
    {
        printf("LR-kirto\n");
        lapsenlapsi = lapsi->oikea;
        lapsi->oikea = lapsenlapsi->vasen;
        lapsenlapsi->vasen = lapsi;
        (*emo)->vasen = lapsenlapsi->oikea;
        lapsenlapsi->oikea = *emo;
        switch(lapsenlapsi->tila)
        {
            case 1:
                (*emo)->tila = -1;
                lapsi->tila = 0;
                break;
            case 0:
                (*emo)->tila = lapsi->tila = 0;
                break;
            case -1:
                (*emo)->tila = 0;
                lapsi->tila = 1;
        }
        *emo = lapsenlapsi;
    }
    (*emo)->tila = 0;
    *etp = 0;
}

void oikea_kierto(puuosoitin *emo, int *etp){

    puuosoitin lapsi, lapsenlapsi;

    lapsi = (*emo)->oikea;
    if(lapsi->tila == -1) /* LL-kierto --> RR */
    {
        printf("RR-kierto\n");
        (*emo)->oikea = lapsi->vasen;
        lapsi->vasen = *emo;
        (*emo)->tila = 0;
        (*emo) = lapsi;
    } else /* LR-kierto --> RL*/
    {
        printf("RL-kierto\n");
        lapsenlapsi = lapsi->vasen;
        lapsi->vasen = lapsenlapsi->oikea;
        lapsenlapsi->oikea = lapsi;
        (*emo)->oikea = lapsenlapsi->vasen;
        lapsenlapsi->vasen = *emo;
        switch(lapsenlapsi->tila)
        {
            case 1:
                (*emo)->tila = -1;
                lapsi->tila = 0;
                break;
            case 0:
                (*emo)->tila = lapsi->tila = 0;
                break;
            case -1:
                (*emo)->tila = 0;
                lapsi->tila = 1;
        }
        *emo = lapsenlapsi;
    }
    (*emo)->tila = 0;
    *etp = 0;

}

void etsi_puusta(puuosoitin solmu, int haku){

    int found = 0;
    while (solmu != NULL){
        if(solmu->luku > haku){
            solmu = solmu->vasen;
        }else if (solmu->luku < haku){
            solmu = solmu->oikea;
        } else if(solmu->luku == haku){
            printf("Luku löytyi puusta\n");
            found = 1;
            break;
        }
    }
    if (found == 0){
        printf("Lukua ei löytynyt\n");
    }

}


void tulosta_puu(puuosoitin solmu)
{
    if(!solmu) {
        return;
    }
    tulosta_puu(solmu->vasen);
    printf("%d ", solmu->luku);

    tulosta_puu(solmu->oikea);
}

int maxDepth(puuosoitin solmu)
{
    if (solmu==NULL)
        return 0;
    else
    {

        /* compute the depth of each subtree */
        int lDepth = maxDepth(solmu->vasen);
        int rDepth = maxDepth(solmu->oikea);


        /* use the larger one */
        if (lDepth > rDepth)
            return(lDepth+1);
        else return(rDepth+1);
    }
}


void padding ( char ch, int n )
{
    int i;
    for ( i = 0; i < n; i++ )
        putchar ( ch );
}
void structure (puuosoitin solmu, int level )
{
    if ( solmu == NULL ) {
        padding ( '\t', level );
        puts ( "~" );
    }
    else {
        structure ( solmu->oikea, level + 1 );
        padding ( '\t', level );
        printf ( "%d\n", solmu->luku );
        structure ( solmu->vasen, level + 1 );
    }
}