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

/** test des différentes fonctions **/
void test(utree a, char *name) {

  /// affichage de l'arbre
  simple_print_utree_graph(a, name ? name : "");
  parenthesis_print_utree_graph(a, name ? name : "");
  putchar('\n');

  /// 1.	Vérifier qu’un arbre (représenté par l’adresse de sa racine) est vide.
  printf("%s %s vide !\n", name ? name : "l'arbre", is_empty_utree(a) ? "est" : "n'est pas");
  /// 2.	Créer et initialiser un nœud d’arbre (c’est à dire un arbre singleton).

  /// 3.	Parcourir un arbre et afficher les éléments qu’il contient :
  /// o	A Suivant un parcours itératif de gauche à droite, en largeur.
  width_walker_utree_printer(a);

  /// o	B Suivant un parcours itératif de gauche à droite, en profondeur.
  depth_walker_utree_printer(a);

  /// o	C Suivant un parcours récursif de gauche à droite, en profondeur.
  if (a) printf("infix_walker_printer : ");
  infix_walker_utree_printer(a);
  putchar('\n');

  /// 5.	Retourner le nombre d’éléments d’un arbre.
  printf("%s comporte %u elements !\n", name ? name : "l'arbre", nr_elements(a));

  /// 6.	Retourner la hauteur d’un arbre.
  printf("%s a une hauteur de %u !\n", name ? name : "l'arbre", get_depth(a));

  /// 7.	Vérifier qu’un arbre b est le sous-arbre d’un arbre a.
  printf("b = a->sad->sad->sad->sad->sag s'il existe, et l'arbre vide sinon :\n");
  utree b = NULL;
  if (a && a->sad && a->sad->sad && a->sad->sad->sad && a->sad->sad->sad->sad && a->sad->sad->sad->sad->sag)
    b = a->sad->sad->sad->sad->sag;

  if (is_sub_tree(a, b)) {
    printf("=> b est un sous arbre de a\n");
    printf("La branche [a, b] est : ");
    /// 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.
    print_list_graph(get_branch(a, b), "[a, b]");
  } else printf("=> b n'est pas un sous arbre de a\n");

  /// 10.	Vérifier qu’un arbre binaire est un arbre binaire de recherche.
  printf("%s %s un ABR !\n", name ? name : "l'arbre", is_bst(a) ? "est" : "n'est pas");
  unsigned min, max;
  if (is_bst_v2(a, &min, &max)) {
    if (a) printf("%s est un ABR de min %u et de max %u !\n", name ? name : "l'arbre", min, max);
    else printf("%s est l'arbre vide donc un ABR !\n", name ? name : "l'arbre");
  } else printf("%s n'est pas un ABR !\n", name ? name : "l'arbre");

  /// 4.	Libérer la mémoire occupée par un arbre.
  printf("%s detruit : %u noeuds liberes !\n", name ? name : "l'arbre", delete_tree(a));
}

int main() {
  printf("\n\nTP 3 - Manipulations sur les arbres\n\n");
  init_indent(); /// initialisation à laisser pour un bon fonctionnement des affichages

  printf("\t\t>> Abre null <<\n\n");
  utree t = NULL;
  test(t, "Arbre null");

  /// création de l'arbre de Syracuse jusqu'à la profondeur n
  unsigned n = 7;
  printf("\t\t>> Arbre de Syracuse jusqu'a la profondeur %d <<\n\n", n);
  syracuse_tree_growth(&t, n);
  test(t, "Arbre de Syracuse");

  /// 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).
  n = 5;
  printf("\t\t>> ABR parfait de profondeur %d <<\n\n", n);
  t = new_perfect_tree(n, 1);
  test(t, "ABR parfait");

  return 0;
}