import matplotlib.pyplot as plt
import matplotlib.patches as patches
from matplotlib.animation import FuncAnimation
import numpy as np
import random as rd


# Ne pas modifier

class ListeDynamique:
    def __init__(self, data):
        data = list(enumerate(data))
        self.original = list(data)
        self.data = list(data)
        self.operations = []
        self.recording = False

    # =========================
    # Gestion enregistrement
    # =========================
    def start(self):
        """Lance l'enregistrement et reset à l'original."""
        self.operations = []
        self.data = list(self.original)
        self.recording = True

    def stop(self):
        """Arrête l'enregistrement."""
        self.recording = False

    # =========================
    # Accès
    # =========================
    def get(self, i):
        """Renvoie l'élément d'indice i."""
        if 0 <= i < len(self.data):
            return self.data[i][1]
        raise IndexError("Indice hors borne")
    
    def len(self):
        return len(self.data)

    # =========================
    # Opérations enregistrables
    # =========================
    def swap(self, i, j):
        """Swappe i et j (enregistre si recording)."""
        if self.recording:
            self.operations.append(("swap", i, j))
        self.data[i], self.data[j] = self.data[j], self.data[i]

    def move(self, i, j):
        """Déplace i vers j (enregistre si recording)."""
        if self.recording:
            self.operations.append(("move", i, j))
        value = self.data.pop(i)
        self.data.insert(j, value)

    # =========================
    # Animation fluide
    # =========================
    def show(self, frames_per_transition=60, interval=45, repeat=False):
        """
        Affiche l'animation fluide pixel-par-pixel des opérations.
        - frames_per_transition: frames par opération (fluidité)
        - interval: ms entre frames (vitesse)
        - repeat: boucle infinie ?
        
        Note: Assume valeurs (approximativement) uniques pour tracker les mouvements.
        """
        if not self.operations:
            # État statique si pas d'opérations
            fig, ax = plt.subplots(figsize=(max(8, len(self.original)*0.8), 3))
            self._draw_static(ax, self.original)
            plt.tight_layout()
            plt.show()
            return

        fig, ax = plt.subplots(figsize=(max(12, len(self.original)*0.8), 3))
        ax.set_xlim(-0.5, len(self.original) + 0.5)
        ax.set_ylim(-0.2, 0.8)
        ax.set_aspect('equal')
        ax.axis('off')

        n = len(self.original)
        width = 0.85
        height = 0.7
        base_y = 0.3
        x_centers = np.arange(n) + 0.5

        # Création des éléments mobiles (rect + text par valeur)
        all_values = self.original[:]
        elements = []
        for k in range(n):
            xc = x_centers[k]
            rect = patches.Rectangle(
                (xc - width/2, base_y - height/2),
                width, height,
                facecolor='lightcoral',
                edgecolor='darkred',
                linewidth=2,
                alpha=0.9
            )
            ax.add_patch(rect)
            text = ax.text(
                xc, base_y,
                str(all_values[k][1]),
                ha='center', va='center',
                fontsize=20,
                fontweight='bold',
                color='white'
            )
            elements.append({'rect': rect, 'text': text, 'value': all_values[k]})

        # Calcul des états successifs
        states = [list(self.original)]
        temp_data = list(self.original)
        for op in self.operations:
            typ, ii, jj = op
            if typ == 'swap':
                temp_data[ii], temp_data[jj] = temp_data[jj], temp_data[ii]
            elif typ == 'move':
                val = temp_data.pop(ii)
                temp_data.insert(jj, val)
            states.append(list(temp_data))

        num_transitions = len(states) - 1
        total_frames = num_transitions * frames_per_transition

        def update(frame):
            trans_idx = frame // frames_per_transition
            local_t = (frame % frames_per_transition) / frames_per_transition
            state_from = states[trans_idx]
            state_to = states[trans_idx + 1]

            for elem in elements:
                val = elem['value']
                # Position de départ et arrivée de cette valeur
                start_pos = state_from.index(val)
                end_pos = state_to.index(val)
                x_start = x_centers[start_pos]
                x_end = x_centers[end_pos]
                # Interpolation linéaire en X + arc en Y
                x = x_start + local_t * (x_end - x_start)
                y = base_y
                # Mise à jour rect
                elem['rect'].set_xy((x - width/2, y - height/2))
                # Mise à jour texte
                elem['text'].set_position((x, y))

            return [e['rect'] for e in elements] + [e['text'] for e in elements]

        anim = FuncAnimation(
            fig, update,
            frames=total_frames,
            interval=interval,
            blit=True,
            repeat=repeat
        )
        plt.tight_layout()
        plt.show()

    def _draw_static(self, ax, state):
        """Dessin statique (utilisé si pas d'ops)."""
        n = len(state)
        width, height = 0.85, 0.7
        base_y = 0.3
        x_centers = np.arange(n) + 0.5
        ax.set_xlim(-0.5, n + 0.5)
        ax.set_ylim(-0.2, 1.2)
        ax.axis('off')
        for k, val in enumerate(state):
            xc = x_centers[k]
            rect = patches.Rectangle(
                (xc - width/2, base_y - height/2),
                width, height,
                facecolor='lightcoral',
                edgecolor='darkred',
                linewidth=2
            )
            ax.add_patch(rect)
            ax.text(xc, base_y, str(val), ha='center', va='center',
                    fontsize=20, fontweight='bold', color='white')


# À modifier :

## Fonctions

def tri_insertion(L):

    n = L.len()

    for i in range(1, n):
        for j in range(0, i):
            if L.get(i) < L.get(j) :
                L.move(i, j)

def tri_bulles(L):
    # À compléter
    pass

def tri_fusion(L, mini = 0, maxi = None):
    if maxi is None:
        maxi = L.len()

    milieu = (maxi+mini)//2
    if maxi - mini <= 1:
        return
    tri_fusion(L, mini, milieu)
    tri_fusion(L, milieu, maxi)

    i = mini
    j = milieu

    while i < j and j < n :
        if L.get(i) > L.get(j) :
            L.move(j, i)
            i += 1
            j += 1
        else :
            i += 1

def tri_pivot(L, mini = 0, maxi = None):
    if maxi is None:
        maxi = L.len()
    # À compléter
    pass

## Exemple
n = rd.randint(4, 10)
L = ListeDynamique([rd.randint(0, 100) for i in range(n)])

L.start()
tri_fusion(L) # Remplace par le tri de ton choix !
L.stop()

L.show()