import random # Pour les tirages aleatoires
import sys # Pour quitter proprement
import pygame # Le module Pygame
import pygame.freetype # Pour afficher du texte
import math
pygame.init() # initialisation de Pygame

# Taille de la fenetre
h_surface = 250
width=800
height=3*h_surface

afficher_bulles = True
afficher_selection = True
afficher_insertion = True
mode_demo = True

nb_affiches = sum([1 for b in [afficher_bulles, afficher_selection, afficher_insertion] if b])

h_surface = height // nb_affiches

# Definition des couleurs
black = (0, 0, 0)
red = (255, 0, 0)
green = (0, 200, 0)
blue = (0, 0, 255)
white = (255, 255, 255)
# Pour le texte. Decommenter la 1e ligne et une des 2 suivantes
pygame.freetype.init()
taille_texte = 20
myfont=pygame.freetype.SysFont(None, taille_texte)
myfont_italic=pygame.freetype.SysFont(None, taille_texte, italic=True)

# Pour controler le nombre d'images par seconde
clock=pygame.time.Clock()

# Mettre ici les definitions de nouvelles fonctions
#
#

# on va de x1 à x2
def position_ellipse(x1, x2, etape=0.3, hauteur_max=20):
    xA = (x1+x2)/2
    d = (x2 - x1)/2
    angle = math.pi
    a = d
    b = min(d, hauteur_max)
    x = xA + a * math.cos(math.pi*etape + angle) - x1
    y = b * math.sin(math.pi*etape + angle)
    return (x, y)
    
def tri_bulles_step(t, i, j):
    #print(j, i, len(t)-i, t)
    permut = t[j-1] > t[j]
    j -= 1
    if j == i:
        i += 1
        j = len(t) - 1
    fini = (i==len(t)-1)
    return fini, permut, i, j

def tri_selection_step(t, i, j, k):
    permut = -1
    if t[j] < t[k]:
        k = j
    j += 1
    if j == len(t):
        if k != i:
            permut = k
        i += 1
        j = i+1
        k = i
    fini = (i==len(t)-1)
    return fini, permut, i, j, k

def tri_insertion_step(t, i, j):
    permut = j > 0 and t[j-1] > t[j]
    if permut and j > 1:
        j -= 1
    else:
        i += 1
        j = i
    fini = (i == len(t))
    return fini, permut, i, j

def echange(t, i, j):
    t[i], t[j] = t[j], t[i]
    


# t peut être un tableau de nombres ou un entier et dans ce cas on genere un tableau de longueur t.
def affichage_tri(t = [random.random() for _ in range(15)], nb_etapes = 5):
    if isinstance(t, int):
        t = [random.random() for _ in range(t)]
    screen = pygame.display.set_mode((width,height))
    pygame.display.set_caption("Algorithmes de tri")
    surface_bulles = pygame.Surface((width, h_surface))
    surface_selection = pygame.Surface((width, h_surface))
    surface_insertion = pygame.Surface((width, h_surface))


    # pos : bas gauche
    def afficher_bloc(surface, pos=(250, 250), offset=(0,0), largeur=20, hauteur=60, couleur1=red, couleur2=black):
        pygame.draw.rect(surface, couleur2, (pos[0]+offset[0], pos[1]+offset[1]-hauteur, largeur, hauteur), 0)
        pygame.draw.rect(surface, couleur1, (pos[0]+offset[0], pos[1]+offset[1]-hauteur, largeur, largeur), 0)


    def afficher_fleche(surface, x, y, texte="", longueur=30, espace=10, largeur=10, decal=0):
        pygame.draw.line(surface, black, (x, y+espace), (x, y+espace+longueur),3)
        pygame.draw.line(surface, black, (x, y+espace), (x+largeur, y+espace+largeur),3)
        pygame.draw.line(surface, black, (x, y+espace), (x-largeur, y+espace+largeur),3)
        texte, rect = myfont_italic.render(texte, black, size = 20)
        rect.midtop = (x+decal*10, y+espace+longueur+espace)
        surface.blit(texte, rect)

    def afficher_texte(surface, x, y, nb_tests, nb_echanges):
        texte, rect = myfont.render(f"nombre de tests : {nb_tests:2}   nombre d'échanges : {nb_echanges:2}", black, size = 20)
        rect.midbottom = (x, y)
        surface.blit(texte, rect)
        
    def afficher_comparaison(surface, x1, x2, y, inferieur, longueur=15, espace=10):
        if inferieur:
            texte = "\u2264"
            couleur = green
        else:
            texte = ">"
            couleur = red
        pygame.draw.lines(surface, couleur, False, [(x1, y+espace), (x1, y+espace+longueur), (x2, y+espace+longueur), (x2, y+espace)], 3)
        texte, rect = myfont.render(texte, couleur, size = 20)
        rect.midtop = ((x1+x2)/2, y+espace+longueur+15)
        surface.blit(texte,rect)

    def init_bulles(t_bulles):
        etape_bulles = 0
        i_bulles = 0
        j_bulles = len(t_bulles) - 1
        fini_bulles = i_bulles >= j_bulles
        fini_bulles_next, permut_bulles, i_bulles_next, j_bulles_next = tri_bulles_step(t_bulles, i_bulles, j_bulles)
        tests_bulles = 1
        echanges_bulles = 0
        return etape_bulles, permut_bulles, fini_bulles, i_bulles, j_bulles, fini_bulles_next, i_bulles_next, j_bulles_next, tests_bulles, echanges_bulles

    def init_insertion(t_insertion):
        etape_insertion = 0
        i_insertion = 1
        j_insertion = 1
        fini_insertion = i_insertion == len(t_insertion)
        fini_insertion_next, permut_insertion, i_insertion_next, j_insertion_next = tri_insertion_step(t_insertion, i_insertion, j_insertion)
        tests_insertion = 1
        echanges_insertion = 0
        return etape_insertion, permut_insertion, fini_insertion, i_insertion, j_insertion, fini_insertion_next, i_insertion_next, j_insertion_next, tests_insertion, echanges_insertion


    def init_selection(t_selection):
        etape_selection = 0
        i_selection = 0
        j_selection = 1
        k_selection = 0
        fini_selection = i_selection >= len(t_selection)-1
        fini_selection_next, permut_selection, i_selection_next, j_selection_next, k_selection_next = tri_selection_step(t_selection, i_selection, j_selection, k_selection)
        tests_selection = 1
        echanges_selection = 0
        return etape_selection, permut_selection, fini_selection, i_selection, j_selection, k_selection, fini_selection_next, i_selection_next, j_selection_next, k_selection_next, tests_selection, echanges_selection

    def afficher_surface_bulles(surface, t_bulles, etat_bulles):
        etape_bulles, permut_bulles, fini_bulles, i_bulles, j_bulles, fini_bulles_next, i_bulles_next, j_bulles_next, tests_bulles, echanges_bulles = etat_bulles
        if permut_bulles :
            echanger_bulles = {j_bulles: j_bulles-1, j_bulles-1: j_bulles}
        else:
            echanger_bulles = {}
        # Initialisation des variables en debut de boucle
        surface.fill(white)
        texte, rect = myfont.render("Tri à bulles", black, size = 20)
        rect.topleft = (5,5)
        surface.blit(texte,rect)
        for i in range(len(t_bulles)):
            offset = (0,0)
            couleur_haut = red
            if i < i_bulles or fini_bulles:
                couleur_haut = green
            elif i == j_bulles:
                couleur_haut = blue
            if i in echanger_bulles and etape_bulles >= nb_etapes:
                offset = position_ellipse(0, (echanger_bulles[i] - i)*eccart_blocs, (etape_bulles-nb_etapes)/nb_etapes)
            afficher_bloc(surface, (x_bloc + i*eccart_blocs, y_bloc), offset, largeur_blocs, (coeff_h*t_bulles[i]+ord_origine_h)*largeur_blocs, couleur_haut)
            #afficher_bloc(screen, blocs[i][1], (0,0) , 20, blocs[i][0]*20, couleurs[i])
        if not fini_bulles:
            if etape_bulles < nb_etapes:
                afficher_comparaison(surface, x_bloc + (j_bulles-1)*eccart_blocs + largeur_blocs/2, x_bloc + j_bulles*eccart_blocs + largeur_blocs/2, y_bloc, t_bulles[j_bulles-1]<=t_bulles[j_bulles])
            afficher_fleche(surface, x_bloc + largeur_blocs/2 + i_bulles*eccart_blocs, y_bloc, "i")
            afficher_fleche(surface, x_bloc + largeur_blocs/2 + j_bulles*eccart_blocs, y_bloc, "j")
        afficher_texte(surface, width/2, y_bloc+100, tests_bulles, echanges_bulles)
        etape_bulles += 1
        if etape_bulles == nb_etapes and permut_bulles:
            echanges_bulles += 1
        if etape_bulles > (1+permut_bulles) * nb_etapes:
            if permut_bulles:
                echange(t_bulles, j_bulles-1, j_bulles)
            fini_bulles = fini_bulles_next
            if not fini_bulles_next:
                etape_bulles = 0
                i_bulles, j_bulles = i_bulles_next, j_bulles_next
                fini_bulles_next, permut_bulles, i_bulles_next, j_bulles_next = tri_bulles_step(t_bulles, i_bulles, j_bulles)
                tests_bulles += 1
            else:
                permut_bulles = False
        return etape_bulles, permut_bulles, fini_bulles, i_bulles, j_bulles, fini_bulles_next, i_bulles_next, j_bulles_next, tests_bulles, echanges_bulles

    def afficher_surface_selection(surface, t_selection, etat_selection):   
        etape_selection, permut_selection, fini_selection, i_selection, j_selection, k_selection, fini_selection_next, i_selection_next, j_selection_next, k_selection_next, tests_selection, echanges_selection = etat_selection
        if permut_selection > -1:
            echanger_selection = {i_selection: permut_selection, permut_selection: i_selection}
        else:
            echanger_selection = {}
        # Initialisation des variables en debut de boucle
        surface.fill(white)
        texte, rect = myfont.render("Tri par sélection", black, size = 20)
        rect.topleft = (5,5)
        surface.blit(texte,rect)
        for i in range(len(t)):
            offset = (0,0)
            couleur_haut = red
            if i < i_selection or fini_selection:
                couleur_haut = green
            elif i == k_selection:
                couleur_haut = blue
            if i in echanger_selection and etape_selection >= nb_etapes:
                offset = position_ellipse(0, (echanger_selection[i] - i)*eccart_blocs, (etape_selection-nb_etapes)/nb_etapes)
            afficher_bloc(surface, (x_bloc + i*eccart_blocs, y_bloc), offset, largeur_blocs, (coeff_h*t_selection[i]+ord_origine_h)*largeur_blocs, couleur_haut)
            #afficher_bloc(screen, blocs[i][1], (0,0) , 20, blocs[i][0]*20, couleurs[i])
        if not fini_selection:
            if etape_selection < nb_etapes:
                afficher_comparaison(surface, x_bloc + (k_selection)*eccart_blocs + largeur_blocs/2, x_bloc + j_selection*eccart_blocs + largeur_blocs/2, y_bloc, t_selection[k_selection]<=t_selection[j_selection])
            if i_selection == k_selection:
                decal_i = -1
                decal_k = 1
            else:
                decal_i = 0
                decal_k = 0
            afficher_fleche(surface, x_bloc + largeur_blocs/2 + i_selection*eccart_blocs, y_bloc, "i", decal=decal_i)
            afficher_fleche(surface, x_bloc + largeur_blocs/2 + j_selection*eccart_blocs, y_bloc, "j")
            afficher_fleche(surface, x_bloc + largeur_blocs/2 + k_selection*eccart_blocs, y_bloc, "k", decal=decal_k)

        afficher_texte(surface, width/2, y_bloc+100, tests_selection, echanges_selection)
        etape_selection += 1
        if etape_selection == nb_etapes and permut_selection > -1:
            echanges_selection += 1
        if etape_selection > (1+(permut_selection>-1)) * nb_etapes:
            if permut_selection>-1:
                echange(t_selection, i_selection, permut_selection)
            fini_selection = fini_selection_next
            if not fini_selection_next:
                etape_selection = 0
                i_selection, j_selection, k_selection = i_selection_next, j_selection_next, k_selection_next
                fini_selection_next, permut_selection, i_selection_next, j_selection_next, k_selection_next = tri_selection_step(t_selection, i_selection, j_selection, k_selection)
                tests_selection += 1
            else:
                permut_selection = -1
        return etape_selection, permut_selection, fini_selection, i_selection, j_selection, k_selection, fini_selection_next, i_selection_next, j_selection_next, k_selection_next, tests_selection, echanges_selection

    def afficher_surface_insertion(surface, t_insertion, etat_insertion):
        #print(etat_insertion)
        etape_insertion, permut_insertion, fini_insertion, i_insertion, j_insertion, fini_insertion_next, i_insertion_next, j_insertion_next, tests_insertion, echanges_insertion = etat_insertion
        if permut_insertion :
            echanger_insertion = {j_insertion: j_insertion-1, j_insertion-1: j_insertion}
        else:
            echanger_insertion = {}
        # Initialisation des variables en debut de boucle
        surface.fill(white)
        texte, rect = myfont.render("Tri par insertion", black, size = 20)
        rect.topleft = (5,5)
        surface.blit(texte,rect)
        for i in range(len(t)):
            offset = (0,0)
            couleur_haut = red
            if i <= i_insertion and i != j_insertion and not fini_insertion:
                couleur_haut = blue
            elif fini_insertion:
                couleur_haut = green
            if i in echanger_insertion and etape_insertion >= nb_etapes:
                offset = position_ellipse(0, (echanger_insertion[i] - i)*eccart_blocs, (etape_insertion-nb_etapes)/nb_etapes)
            afficher_bloc(surface, (x_bloc + i*eccart_blocs, y_bloc), offset, largeur_blocs, (coeff_h*t_insertion[i]+ord_origine_h)*largeur_blocs, couleur_haut)
            #afficher_bloc(screen, blocs[i][1], (0,0) , 20, blocs[i][0]*20, couleurs[i])
        if not fini_insertion:
            if etape_insertion < nb_etapes:
                afficher_comparaison(surface, x_bloc + (j_insertion-1)*eccart_blocs + largeur_blocs/2, x_bloc + j_insertion*eccart_blocs + largeur_blocs/2, y_bloc, t_insertion[j_insertion-1]<=t_insertion[j_insertion])
            if i_insertion == j_insertion:
                decal_i = -1
                decal_j = 1
            else:
                decal_i = 0
                decal_j = 0
            afficher_fleche(surface, x_bloc + largeur_blocs/2 + i_insertion*eccart_blocs, y_bloc, "i", decal=decal_i)
            afficher_fleche(surface, x_bloc + largeur_blocs/2 + j_insertion*eccart_blocs, y_bloc, "j", decal=decal_j)
        afficher_texte(surface, width/2, y_bloc+100, tests_insertion, echanges_insertion)
        etape_insertion += 1
        if etape_insertion == nb_etapes and permut_insertion:
            echanges_insertion += 1
        if etape_insertion > (1+permut_insertion) * nb_etapes:
            if permut_insertion:
                echange(t_insertion, j_insertion-1, j_insertion)
            fini_insertion = fini_insertion_next
            if not fini_insertion_next:
                etape_insertion = 0
                i_insertion, j_insertion = i_insertion_next, j_insertion_next
                fini_insertion_next, permut_insertion, i_insertion_next, j_insertion_next = tri_insertion_step(t_insertion, i_insertion, j_insertion)
                tests_insertion += 1
            else:
                permut_insertion = False
        return etape_insertion, permut_insertion, fini_insertion, i_insertion, j_insertion, fini_insertion_next, i_insertion_next, j_insertion_next, tests_insertion, echanges_insertion


    t_bulles = t.copy()
    t_selection = t.copy()
    t_insertion = t.copy()

    t_trie = sorted(t)

    y_bloc = 150
    x_bloc = 50
    largeur_totale = width - 2*x_bloc
    largeur_blocs = 20
    eccart_blocs = largeur_blocs * 2
    largeur_total_blocs = largeur_blocs + (len(t)-1)*eccart_blocs
    if largeur_total_blocs < largeur_totale:
        #print("on a de la place")
        x_bloc = (width-largeur_total_blocs)//2
        #print(x_bloc, largeur_blocs, largeur_totale)
    else:
        #print("c'est serré")
        largeur_blocs = max(15, largeur_totale/(2*len(t)-1))
        eccart_blocs = largeur_blocs+(largeur_totale - len(t)*largeur_blocs)/(len(t)-1)
        #print(largeur_blocs, eccart_blocs)
        
    min_t, max_t = t_trie[0], t_trie[-1]

    if min_t < max_t:   
        coeff_h = ((y_bloc-40)/(largeur_blocs+1)) / (max_t-min_t)
        ord_origine_h = 1 - coeff_h*min_t
    else:
        coeff_h = 0
        ord_origine_h = 1

    etat_bulles = init_bulles(t_bulles)
    etat_selection = init_selection(t_selection)
    etat_insertion = init_insertion(t_insertion)
    
    # il faut cliquer pour commencer
    texte, rect = myfont.render("Cliquer avec la souris pour commencer", red, size = 20)
    rect.center = (width/2,height/2)
    screen.blit(texte,rect)
    pygame.display.flip()
    compteur_debut = 60
    attendre = not mode_demo
    while attendre:
        for event in pygame.event.get():
            if event.type == pygame.QUIT: sys.exit() # Pour quitter
            elif event.type == pygame.MOUSEBUTTONDOWN:
                attendre = False
        clock.tick(30)
    compteur_fin = 60
    while 1:
        # Gestion des evenements
        for event in pygame.event.get():
            if event.type == pygame.QUIT: sys.exit() # Pour quitter
        
        fini = True
        decalage = 0
        if afficher_bulles:
            etat_bulles = afficher_surface_bulles(surface_bulles, t_bulles, etat_bulles)
            screen.blit(surface_bulles, (0, 0))
            decalage = decalage + h_surface
            fini = fini and etat_bulles[2]
        if afficher_selection:
            etat_selection = afficher_surface_selection(surface_selection, t_selection, etat_selection)
            screen.blit(surface_selection, (0, decalage))
            decalage = decalage + h_surface
            fini = fini and etat_selection[2]
        if afficher_insertion:
            etat_insertion = afficher_surface_insertion(surface_insertion, t_insertion, etat_insertion)
            screen.blit(surface_insertion, (0, decalage))
            fini = fini and etat_insertion[2]
        
        # on met en pause au début
        if mode_demo and compteur_debut > 0:
            compteur_debut -= 1
            etat_bulles = init_bulles(t_bulles)
            etat_selection = init_selection(t_selection)
            etat_insertion = init_insertion(t_insertion)
        
        for i in range(1, nb_affiches):
            pygame.draw.line(screen, black, (0, i*h_surface), (width, i*h_surface),3)
        
        # Ne rien mettra apres ca
        # On affiche le resultat final a l'ecran
        pygame.display.flip()
        # On attend le temps necessaire pour avoir un FPS constant
        clock.tick(30)
        if fini and mode_demo:
            compteur_fin -= 1
            if compteur_fin <= 0:
                return True

def genere_tableau_presque_trie(n, k):
    t = list(range(n))
    for _ in range(k):
        # on fait k échanges au hasard
        echange(t, random.randint(0, n-1), random.randint(0, n-1))
    return t

"""
affichage_tri(t, nb_etapes) montre les algos de tri à bulle, par selection et par insertion trier le tableau t.
nb_etapes indique le nombre d'images pour chaque opération de base (comparaison et échange)
t peut être un entier et dans ce cas on génère un tableau de taille t rempli de valeurs aléatoires.
"""

if mode_demo:
    types = [(20, 4), (30, 1), (list(range(30, -1, -1)), 1), (genere_tableau_presque_trie(30, 4), 1)]
    i = 0
    while True:
        a, b = types[i]
        affichage_tri(a, b)
        i = (i+1)%len(types)
else:
    affichage_tri(20, 4)
    #affichage_tri(30, 1)
    #affichage_tri(list(range(30, -1, -1)), 1)
    #affichage_tri(genere_tableau_presque_trie(30, 4), 1)