#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. **/
int is_empty_utree(utree t) {
  printf("is_empty_utree not yet implemented !\n");
  return 0;
}

/** 2.	Créer et initialiser un nœud d’arbre (c’est à dire un arbre singleton). **/
utree new_singleton_utree(unsigned content) {
  printf("new_singleton_utree not yet implemented !\n");
  return NULL;
}

/** 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("width_walker_utree_printer not yet implemented !\n");
}

/** 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(')');
  }
}