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

struct NoeudSt {
    int masse;
    float longueur_droite;
    float longueur_gauche;
    struct NoeudSt * fils_gauche;
    struct NoeudSt * fils_droit;
};
typedef struct NoeudSt * Mobile;

Mobile creer_noeud(float longueur_gauche,float longueur_droite, Mobile fils_gauche, Mobile fils_droit) {

    Mobile resultat;

    resultat = (Mobile)malloc(sizeof(struct NoeudSt));
    if (resultat == NULL) {
        fprintf(stderr, "Erreur: impossible d'allouer un nouveau noeud.\n");
        exit(-1);
    }
    resultat->masse = 0;
    resultat->longueur_gauche = longueur_gauche;
    resultat->longueur_droite = longueur_droite;
    resultat->fils_gauche = fils_gauche;
    resultat->fils_droit = fils_droit;

    return resultat;
}

Mobile creer_feuille(int masse) {

    Mobile resultat;

    resultat = (Mobile)malloc(sizeof(struct NoeudSt));
    if (resultat == NULL) {
        fprintf(stderr, "Erreur: impossible d'allouer un nouveau noeud.\n");
        exit(-1);
    }
    resultat->masse = masse;
    resultat->longueur_gauche = 0;
    resultat->longueur_droite = 0;
    resultat->fils_gauche = NULL;
    resultat->fils_droit = NULL;

    return resultat;
}
int est_barre(Mobile m) {
    if ((m->masse == 0) && (m->longueur_gauche > 0.0f) && (m->longueur_droite > 0.0f)) return 1;
    else return 0;
}

int est_objet(Mobile m) {
    if ((m->masse > 0) && (m->longueur_gauche == 0.0f) && (m->longueur_droite == 0.0f)) return 1;
    else return 0;
}

int masse_mobile(Mobile m) {
    if (m == NULL) return 0;
    else if (est_objet(m)) return m->masse;
    else return (masse_mobile(m->fils_gauche) + masse_mobile(m->fils_droit));
}

int barre_horizontale(Mobile m) {
    if (m == NULL) return 1;
    else if ((masse_mobile(m->fils_gauche)* m->longueur_gauche) == (masse_mobile(m->fils_droit) * m->longueur_droite)) return 1;
    else return 0;
}

int est_equilibre(Mobile m) {
    if (m == NULL) return 1;
    else if (barre_horizontale(m)) return barre_horizontale(m->fils_gauche) * barre_horizontale(m->fils_droit);
    else return 0;
}

int encombrement(Mobile m) {
    if (m == NULL) return 0;
    else {
        float max_l = encombrement(m->fils_gauche) + m->longueur_gauche;
        float max_r = encombrement(m->fils_droit) + m->longueur_droite;
        return (int)((max_l > max_r) ? max_l : max_r);
    }
}

int barre_assez_large(Mobile m) {
    if (m == NULL) return 1;
    int enc_l = encombrement(m->fils_gauche);
    int enc_r = encombrement(m->fils_droit);
    if (m->longueur_droite < enc_r) return 0;
    else if (m->longueur_gauche < enc_l) return 0;
    else return 1;
}

int mobile_libre(Mobile m) {
    if (m == NULL) return 1;
    else if (!est_equilibre(m)) return 0;
    else if (barre_assez_large(m)) return mobile_libre(m->fils_gauche) * mobile_libre(m->fils_droit);
    else return 0;
}

Mobile libere(Mobile m) {
    if (m == NULL) return NULL;
    if (est_barre(m)) {
        int ret_l_l = m->longueur_gauche;
        int ret_l_r = m->longueur_droite;
        if (barre_assez_large(m) == 0) {
            int max_l = encombrement(m->fils_gauche);
            int max_r = encombrement(m->fils_droit);
            if (m->longueur_gauche < max_l) ret_l_l = max_l + 1;
            if (m->longueur_droite < max_r) ret_l_r = max_r + 1;
        }
        return creer_noeud(ret_l_l, ret_l_r, libere(m->fils_gauche), libere(m->fils_droit));
    }
    else {
        return creer_feuille(m->masse);
    }
}

int main() {
    Mobile m1 = creer_noeud(5.0f, 5.0f,
        creer_noeud(2.0f, 2.0f, creer_feuille(2), creer_noeud(3.0f, 6.0f, creer_feuille(4), creer_feuille(2))),
        creer_noeud(3.0f, 3.0f, creer_feuille(4), creer_feuille(4)));
    Mobile m2 = NULL;
    Mobile m4 = creer_noeud(5.0f, 5.0f,
        creer_noeud(6.0f, 7.0f, creer_feuille(1), creer_noeud(1.0f, 3.0f, creer_feuille(12), creer_feuille(22))),
        creer_noeud(3.0f, 3.0f, creer_feuille(40), creer_feuille(46)));
    Mobile m3 = creer_feuille(10);
    Mobile m5 = creer_noeud(5.0f, 5.0f,
        creer_noeud(2.0f, 2.0f, creer_feuille(2), creer_feuille(2)),
        creer_feuille(4));
    printf("Masse totale");
    printf("\n%d", masse_mobile(m1));
    printf("\n%d", masse_mobile(m2));
    printf("\n%d", masse_mobile(m3));
    printf("\n%d", masse_mobile(m4));
    printf("\n%d", masse_mobile(m5));
    printf("\n______________________________\nBarre Horizontale");
    printf("\n%d", barre_horizontale(m1));
    //printf("\n%d", barre_horizontale(m2));
    printf("\n%d", barre_horizontale(m3));
    printf("\n%d", barre_horizontale(m4));
    printf("\n%d", barre_horizontale(m5));
    printf("\n______________________________\nEst Equilibre");
    printf("\n%d", est_equilibre(m1));
    //printf("\n%d", est_equilibre(m2));
    printf("\n%d", est_equilibre(m3));
    printf("\n%d", est_equilibre(m4));
    printf("\n%d", est_equilibre(m5));
    printf("\n______________________________\nEncombrement");
    printf("\nCercle de rayon : %d", encombrement(m1));
    printf("\nCercle de rayon : %d", encombrement(m3));
    printf("\nCercle de rayon : %d", encombrement(m4));
    printf("\nCercle de rayon : %d", encombrement(m5));
    printf("\n______________________________\nBarre assez large");
    printf("\nAssez large : %d", barre_assez_large(m1));
    printf("\nAssez large : %d", barre_assez_large(m1->fils_droit));
    printf("\nAssez large : %d", barre_assez_large(m3));
    printf("\nAssez large : %d", barre_assez_large(m4));
    printf("\nAssez large : %d", barre_assez_large(m5));
    printf("\n______________________________\nMobile Libre");
    printf("\nLibre : %d", mobile_libre(m1));
    printf("\nLibre : %d", mobile_libre(m1->fils_droit));
    printf("\nLibre : %d", mobile_libre(m3));
    printf("\nLibre : %d", mobile_libre(m4));
    printf("\nLibre : %d", mobile_libre(m5));
    _getch();
}