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

#include "tree.h"
#include "list.h"
#include "iles.h"

/** Retourne le prédécesseur impair de n tel que n = prec * 3 + 1 s'il existe 0 sinon **/
unsigned prec_inf(unsigned n) { return n % 6 == 4 ? (n - 1) / 3 : 0; }

/** Produit l'arbre de Syracuse (tête valant 1) jusqu'à la profondeur n **/
/** voir interlude Syracusien, p144, dans Exercices & Problèmes d'Algorithmique **/
void syracuse_tree_growth(utree *pt, unsigned depth) {
  if (depth == 0) return;
  if (DEBUG_TRACE) printf("syracuse_tree_growth(%u)\n", depth);
  utree t = *pt;
  if (!t) *pt = t = new_singleton_utree(1);
  unsigned n = t->content;
  depth--;
  unsigned nn = 2 * n;
  t->sad = new_singleton_utree(nn);
  syracuse_tree_growth(&(t->sad), depth);

  unsigned prec_inf_n = prec_inf(n);
  if (prec_inf_n > 1) {
    t->sag = new_singleton_utree(prec_inf_n);
    syracuse_tree_growth(&(t->sag), depth);
  }
}

/** 1.	Vérifier qu’un arbre (représenté par l’adresse de sa racine) est vide. **/ // FAIT
int is_empty_utree(utree t) // renvoi 1 quand vide
{
  if (t==NULL)
  {
      return 1;
  }
  return 0;
}

/** 2.	Créer et initialiser un nœud d’arbre (c’est à dire un arbre singleton). **/ // FAIT
utree new_singleton_utree(unsigned content)
{
    // Allocation de la mémoire
  utree noeud=(utree)malloc(sizeof(utree_node));

    // Remplir les infos
    noeud->content=content;
    noeud->sad=NULL;
    noeud->sag=NULL;
  return noeud;
}

/** 3.  Parcourir un arbre et afficher les éléments qu’il contient
    A   Suivant un parcours itératif de gauche à droite, en largeur. **/
void width_walker_utree_printer(utree t)
{
    printf("LAMAAAAAAA");
  if(t==NULL)
  {
      printf("Arbre vide !");
      return;
  }
  lQueue* f=(lQueue*)malloc(sizeof(lQueue));
    f->length=0;
    f->head=NULL;
    f->queue=NULL;
    qPush(t, f);
  while (!(isEmptyQueue(f)))
  {
      if(f->length==1)
      {
          printf("     test long1 ");
          printf("    %d     ", t->content);
            f=NULL;
      }
      else
      {
          printf("test");
          printf("    %p     ", f->head->content);
          int v=qPop((void**)&t, f);
          if(is_empty_utree(t->sag)==0)
          {
                printf (" test sag");

              qPush(t->sag, f);
          }
          if(is_empty_utree(t->sad)==0)
          {
                printf (" test sad");
              qPush(t->sad, f);
          }
      }
  }
  printf (" test 2");
}

/** 3.  Parcourir un arbre et afficher les éléments qu’il contient
    B   Suivant un parcours itératif de gauche à droite, en profondeur. **/
void depth_walker_utree_printer(utree t) {
  printf("depth_walker_utree_printer not yet implemented !\n");
}

/** 3.  Parcourir un arbre et afficher les éléments qu’il contient
    C   Suivant un parcours infixe de gauche à droite. **/
void infix_walker_utree_printer(utree t) {
  printf("infix_walker_utree_printer not yet implemented !\n");
}

/** 4.	Libérer la mémoire occupée par un arbre (retourne le nombre de noeuds libérés). **/
unsigned delete_tree(utree t) {
  printf("delete_tree not yet implemented !\n");
  return 0;
}

/** 5.	Retourner le nombre d’éléments d’un arbre. **/
unsigned nr_elements(utree t) {
  printf("nr_elements not yet implemented !\n");
  return 0;
}

/** 6.	Retourner la hauteur d’un arbre. **/
unsigned get_depth(utree t) {
  printf("get_depth not yet implemented !\n");
  return 0;
}

/** 7.	Vérifier qu’un arbre b est le sous-arbre d’un arbre a **/
int is_sub_tree(utree a, utree b) {
  printf("is_sub_tree not yet implemented !\n");
  return 0;
}

/** 8.	Retourner une liste simplement chaînée qui représente la branche [a, b]
        d’un arbre a si celle-ci existe, et une liste vide sinon. **/
list get_branch(utree a, utree b) {
  printf("get_branch not yet implemented !\n");
  return NULL;
}

/** 9.	Créer un arbre parfait de profondeur n dont les valeurs des nœuds sont exactement
        les index des nœuds suivant un parcours en largeur (index 1 pour la racine). **/
utree new_perfect_tree(unsigned n, unsigned e) {
  printf("new_perfect_tree not yet implemented !\n");
  return NULL;
}

/** 10.	Vérifier qu’un arbre binaire est un arbre binaire de recherche. **/
utree min(utree t) {
  printf("min not yet implemented !\n");
  return NULL;
}

utree max(utree t) {
  printf("max not yet implemented !\n");
  return NULL;
}

int is_bst(utree t) {
  printf("is_bst not yet implemented !\n");
  return 0;
}

int is_bst_v2(utree t, unsigned *min, unsigned *max) {
  printf("is_bst_v2 not yet implemented !\n");
  return 0;
}

///
/// Affichage
///

static unsigned _indent;
void init_indent() { _indent = 0; }
unsigned get_indent() { return _indent; }
void indent_forward() { _indent++; }
void indent_backward() { if (_indent > 0) _indent--; }
char *build_regular_string(char c, unsigned n) {
  char *str = (char *) calloc(n + 1, sizeof(char));
  unsigned i = n;
  for (i = 0; i < n; i++) str[i] = c;
  str[n] = '\0';
  return str;
}
char *nindent(unsigned ntabs) { return build_regular_string(' ', 2 * ntabs); }
char *indent() { return nindent(get_indent()); }

void simple_print_utree_graph(utree t, const char *name) {
  if (name) printf("%s :\n", name);
  if (!t) {
    printf("%s.\n", indent());
    return;
  }
  printf("%s%u\n", indent(), t->content);
  indent_forward();
  simple_print_utree_graph(t->sag, NULL);
  simple_print_utree_graph(t->sad, NULL);
  indent_backward();
}

void parenthesis_print_utree_graph(utree t, const char *name) {
  if (name) printf("%s : \n", name);
  if (!t) {
    printf("%s_", indent());
    return;
  }
  printf("%u", t->content);
  if (t->sag || t->sad) {
    putchar('(');
    parenthesis_print_utree_graph(t->sag, NULL);
    printf(", ");
    parenthesis_print_utree_graph(t->sad, NULL);
    putchar(')');
  }
}