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

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

void lisaa_solmu(puuosoitin *, int, int *);
void oikea_kierto(puuosoitin *, int *);
void tulosta_puu(puuosoitin);
void tulosta_puu_muotoilu(puuosoitin, int, int);
void vasen_kierto(puuosoitin *, int *);
int etsi_solmu(puuosoitin *, int);
int* lue_luvut(char*);
int* generoi_luvut();

#define MAXAMOUNT 10240

int main()
{
  int etp = 0, i;
  int *luvut;
  puuosoitin puu = NULL;

  clock_t begin = clock();

  /*luvut = lue_luvut("numbers.txt");*/
  luvut = generoi_luvut();

  for(i = 0; luvut[i] != 0; i++)
  {
    lisaa_solmu(&puu, luvut[i], &etp);
    printf("Lisättiin %d. luku: %d\n", i, luvut[i]);
  }
  tulosta_puu(puu);
  printf("\n");

  clock_t end = clock();
  double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  printf("%lf", time_spent);

  /*etsi_solmu(&puu, 2);
  etsi_solmu(&puu, 12);*/

  return 0;
}

int* generoi_luvut(){
  srand(time(NULL));
  static int numerot[MAXAMOUNT];
  int i = 0;

  while(i < MAXAMOUNT){
    double scaled = (double)rand()/RAND_MAX;
    numerot[i] = (MAXAMOUNT - 1 +1)*scaled + 1;
    i++;
  }

  return numerot;
}

int* lue_luvut(char *tiedosto){
    FILE* file = fopen(tiedosto, "r");
    int n = 0, i = 0;
    static int numerot[MAXAMOUNT];

    if(file == NULL){
        perror("Error opening file!");
        return NULL;
    }

    while( fscanf(file, "%d\n", &n) > 0 )
    {
        numerot[i++] = n;
    }
    fclose(file);
    return numerot;
}

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 tulosta_puu(puuosoitin solmu)
{
  if(!solmu) return;
  char ch;

  tulosta_puu_muotoilu(solmu->oikea, 1, 1);
  printf("\n%d(%d)\t", solmu->luku, solmu->tila);
  tulosta_puu_muotoilu(solmu->vasen, 1, 0);
  printf("\n\n____________________________________________");
  //getchar();
}

void tulosta_puu_muotoilu(puuosoitin solmu, int syvyys, int oikea)
{
  if(!solmu) return;

  char *nuoli;
  if(oikea){
      nuoli = "↗";
  }else{
      nuoli = "↘";
  }

  tulosta_puu_muotoilu(solmu->oikea, syvyys + 1, 1);

  printf("\n");
  int i = 0;
  for(; i < syvyys; i++){
      printf("\t");
  }
  printf("%s %d(%d)", nuoli, solmu->luku, solmu->tila);
  tulosta_puu_muotoilu(solmu->vasen, syvyys + 1, 0);
}

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-KIERTO\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) /* RR-kierto */
  {
  	printf("RR-KIERTO\n");
    (*emo)->oikea = lapsi->vasen;
    lapsi->vasen = *emo;
    (*emo)->tila = 0;
    (*emo) = lapsi;
  } else /* RL-kierto */
  {
  	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;
}

int etsi_solmu(puuosoitin *emo, int luku){
    if(luku > (*emo)->luku){
        if((*emo)->oikea == NULL){
            printf("Solmua %d ei ole puussa!\n", luku);
            return 0;
        }
        return etsi_solmu(&(*emo)->oikea, luku);
    }else if(luku < (*emo)->luku){
        if((*emo)->vasen == NULL){
            printf("Solmua %d ei ole puussa!\n", luku);
            return 0;
        }
        return etsi_solmu(&(*emo)->vasen, luku);
    }else{
        printf("Solmu %d löytyi puusta!\n", luku);
        return 1;
    }
}