# -*- coding: utf-8 -*-

############################################################
# Tracé d'un arbre binaire avec le module Turtle de Python
# Version 8
# nsi.gecif.net
# Octobre 2026
############################################################

import turtle

############################################################
# Arbre binaire : (valeur, gauche, droite)
############################################################

def taille_arbre(a):
    if a is None:
        return 0
    return 1 + taille_arbre(a[1]) + taille_arbre(a[2])

def profondeur(a):
    if a is None:
        return 0
    return 1 + max(profondeur(a[1]), profondeur(a[2]))

def parcours_infixe(a, niveau, infos):
    if a is None:
        return
    parcours_infixe(a[1], niveau+1, infos)
    infos.append((a, niveau))
    parcours_infixe(a[2], niveau+1, infos)

############################################################
# Calcul positions logiques (avant zoom/déplacement)
############################################################

def calcul_positions(a):
    infos = []
    parcours_infixe(a, 0, infos)
    if not infos:
        return {}, 0, 0

    n = len(infos)
    prof_max = max(niv for (_, niv) in infos)

    largeur = 800.0
    hauteur = 800.0
    marge = 120.0

    if n > 1:
        esp_x = (largeur - 2*marge) / (n - 1)
    else:
        esp_x = 0

    if prof_max > 0:
        esp_y = (hauteur - 2*marge) / prof_max
    else:
        esp_y = 0

    positions = {}
    for i, (noeud, niv) in enumerate(infos):
        x = -largeur/2 + marge + i*esp_x
        y = hauteur/2 - marge - niv*esp_y
        positions[id(noeud)] = (x, y, noeud[0])

    return positions, esp_x, esp_y

############################################################
# Transformations (zoom / déplacement)
############################################################

scale = 1.0
offset_x = 0.0
offset_y = 0.0

def to_screen(x, y):
    return x * scale + offset_x, y * scale + offset_y

def from_screen(xs, ys):
    x = (xs - offset_x) / scale
    y = (ys - offset_y) / scale
    return x, y

############################################################
# Dessin
############################################################

def dessiner_noeud(x, y, r, val):
    turtle.penup()
    turtle.goto(x, y - r)
    turtle.pendown()
    turtle.color("black")
    turtle.circle(r)
    turtle.penup()
    turtle.goto(x, y - r/2)
    turtle.color("red")
    turtle.write(str(val), align="center", font=("Arial", int(r), "normal"))
    turtle.color("black")

def dessiner_arete(x1, y1, x2, y2):
    turtle.penup()
    turtle.goto(x1, y1)
    turtle.pendown()
    turtle.goto(x2, y2)

############################################################
# Redessin complet
############################################################

def dessiner_arbre(a):
    global positions, rayon, arbre

    turtle.clear()

    positions, esp_x, esp_y = calcul_positions(a)

    base_r = min(25, esp_x/3 if esp_x > 0 else 25, esp_y/3 if esp_y > 0 else 25)
    base_r = max(base_r, 12)
    rayon = base_r * scale

    def rec(noeud):
        if noeud is None:
            return
        x, y, val = positions[id(noeud)]
        xs, ys = to_screen(x, y)

        if noeud[1] is not None:
            xg, yg, _ = positions[id(noeud[1])]
            xgs, ygs = to_screen(xg, yg)
            dessiner_arete(xs, ys - rayon, xgs, ygs + rayon)
            rec(noeud[1])

        if noeud[2] is not None:
            xd, yd, _ = positions[id(noeud[2])]
            xds, yds = to_screen(xd, yd)
            dessiner_arete(xs, ys - rayon, xds, yds + rayon)
            rec(noeud[2])

    rec(a)

    for k in positions:
        x, y, val = positions[k]
        xs, ys = to_screen(x, y)
        dessiner_noeud(xs, ys, rayon, val)

    turtle.title("Arbre de taille " + str(taille_arbre(arbre)))
    print("Arbre mis à jour :", arbre)

############################################################
# Interaction : recherche de nœud
############################################################

selected = None
arbre = (1, (2, None, None), (3, None, None))
next_value = 4

def trouver_noeud(xs, ys):
    for k in positions:
        x, y, val = positions[k]
        nx, ny = to_screen(x, y)
        if abs(xs - nx) <= rayon and abs(ys - ny) <= rayon:
            return k
    return None

def chercher(a, target_id):
    if a is None:
        return None
    if id(a) == target_id:
        return a
    g = chercher(a[1], target_id)
    if g is not None:
        return g
    return chercher(a[2], target_id)

############################################################
# Suppression d'une feuille / sous-arbre
############################################################

def supprimer_feuille(a, target_id):
    if a is None:
        return None
    if id(a) == target_id:
        return None
    return (a[0],
            supprimer_feuille(a[1], target_id),
            supprimer_feuille(a[2], target_id))

def supprimer_sous_arbre(a, target_id):
    if a is None:
        return None
    if id(a) == target_id:
        return None
    return (a[0],
            supprimer_sous_arbre(a[1], target_id),
            supprimer_sous_arbre(a[2], target_id))

############################################################
# Remplacement du tuple dans l'arbre
############################################################

def noeud_global_replace(a, target_id, new_tuple):
    if a is None:
        return None
    if id(a) == target_id:
        return new_tuple
    return (a[0],
            noeud_global_replace(a[1], target_id, new_tuple),
            noeud_global_replace(a[2], target_id, new_tuple))

############################################################
# Gestion clic gauche (ajout de fils)
############################################################

def clic_gauche(event):
    global selected, arbre, next_value

    xs = event.x - 400
    ys = 400 - event.y

    noeud_id = trouver_noeud(xs, ys)

    if noeud_id is not None:
        selected = noeud_id
        return

    if selected is None:
        return

    sx, sy, sval = positions[selected]
    sxs, sys = to_screen(sx, sy)
    cote = "gauche" if xs < sxs else "droite"

    noeud = chercher(arbre, selected)

    if cote == "gauche":
        if noeud[1] is not None:
            print("Fils gauche déjà existant")
            selected = None
            return
        val = next_value
        next_value += 1
        noeud = (noeud[0], (val, None, None), noeud[2])
        arbre = noeud_global_replace(arbre, selected, noeud)
    else:
        if noeud[2] is not None:
            print("Fils droit déjà existant")
            selected = None
            return
        val = next_value
        next_value += 1
        noeud = (noeud[0], noeud[1], (val, None, None))
        arbre = noeud_global_replace(arbre, selected, noeud)

    selected = None
    dessiner_arbre(arbre)

############################################################
# Gestion clic droit (suppression feuille)
# Shift + clic droit : suppression sous-arbre
############################################################

def clic_droit(event):
    global arbre

    xs = event.x - 400
    ys = 400 - event.y

    noeud_id = trouver_noeud(xs, ys)
    if noeud_id is None:
        return

    noeud = chercher(arbre, noeud_id)

    # Shift + clic droit → suppression sous-arbre
    if event.state & 0x0001:  # Shift enfoncé (Windows)
        arbre = supprimer_sous_arbre(arbre, noeud_id)
        print("Sous-arbre supprimé")
        dessiner_arbre(arbre)
        return

    # Clic droit simple → suppression feuille
    if noeud[1] is None and noeud[2] is None:
        arbre = supprimer_feuille(arbre, noeud_id)
        print("Feuille supprimée")
        dessiner_arbre(arbre)
    else:
        print("Ce noeud n'est pas une feuille")

############################################################
# Déplacement (clic milieu + drag)
############################################################

dragging = False
drag_start_x = 0
drag_start_y = 0
orig_offset_x = 0
orig_offset_y = 0

def middle_press(event):
    global dragging, drag_start_x, drag_start_y, orig_offset_x, orig_offset_y
    dragging = True
    drag_start_x = event.x
    drag_start_y = event.y
    orig_offset_x = offset_x
    orig_offset_y = offset_y

def middle_release(event):
    global dragging
    dragging = False

def middle_motion(event):
    global offset_x, offset_y
    if not dragging:
        return
    dx = event.x - drag_start_x
    dy = event.y - drag_start_y
    offset_x = orig_offset_x + dx
    offset_y = orig_offset_y - dy
    dessiner_arbre(arbre)

############################################################
# Zoom (molette)
############################################################

def on_wheel(event):
    global scale, offset_x, offset_y, rayon

    # event.delta > 0 : zoom avant, < 0 : zoom arrière
    if event.delta > 0:
        factor = 1.1
    else:
        factor = 1/1.1

    # zoom centré sur le point (event.x, event.y)
    cx = event.x - 400
    cy = 400 - event.y

    # convertir en coordonnées logiques avant zoom
    lx, ly = from_screen(cx, cy)

    scale *= factor

    # recalcul offset pour garder le point sous la souris
    sx, sy = lx * scale, ly * scale
    offset_x = cx - sx
    offset_y = cy - sy

    dessiner_arbre(arbre)

############################################################
# Lancement
############################################################

print("Voici les interactivités à utiliser pour contrôler l'arbre binaire :");
print(" - Clic gauche : ajoute une feuille (fils gauche ou fils droit)");
print(" - Clic droit : supprime une feuille");
print(" - Shift + clic droit : supprime tout un sous-arbre entier");
print(" - Molette : zoom avant ou zoom arrière");
print(" - Clic milieu + déplacement : translation de l’arbre\n");

turtle.setup(800, 800, 400, 0)
turtle.speed(0)
turtle.hideturtle()
turtle.tracer(0)

dessiner_arbre(arbre)

turtle.listen()

canvas = turtle.getcanvas()
canvas.bind("<Button-1>", clic_gauche)         # clic gauche
canvas.bind("<Button-3>", clic_droit)          # clic droit
canvas.bind("<Shift-Button-3>", clic_droit)    # Shift + clic droit
canvas.bind("<Button-2>", middle_press)        # clic milieu
canvas.bind("<ButtonRelease-2>", middle_release)
canvas.bind("<B2-Motion>", middle_motion)      # drag milieu
canvas.bind("<MouseWheel>", on_wheel)          # molette

turtle.done()