from PIL import Image
from PIL.ImageDraw import Draw
from random import shuffle

def draw_cross(im, cross_color = (0, 0, 0)):
    """Dessine une croix de couleur cross_color (noire par défaut)
       au milieu de l'image im"""

    (w, h) = im.size
    x_middle, y_middle = w//2, h//2

    for x in range(w):
        im.putpixel((x, y_middle), cross_color)

    for y in range(h):
        im.putpixel((x_middle, y), cross_color)


def draw_line(draw, l, row, palette, pix_size=4):
    """
    Dessine la ligne de numéro row de l'image en associant à chaque élément x
    de l un carré de taille pix_size et de couleur donnée dans palette.
    """

    col = 0
    for e in l:
        pix = palette[e%len(palette)]
        draw.rectangle(((col, row), (col+pix_size, row+pix_size)), pix)
        col += pix_size

def draw_steps(steps, pix_size = 4):
    """
    Le paramètre steps est une matrice (liste de listes de même taille)
    d'entiers. Construit une image correspondant à cette matrice en associant
    une couleur à chaque entier
    """

    # Construction d'une palette de 128 couleurs
    palette = [0] * 128
    for i in range(32):
        palette[i]    = (255-8*i,     255, 255-8*i)
        palette[32+i] = (    8*i, 255-8*i,       0)
        palette[64+i] = (    255,     8*i,       0)
        palette[96+i] = (255-8*i, 255-8*i,       0)

    width = len(steps[0])*pix_size
    height = len(steps)*pix_size
    im = Image.new('RGB', (width, height), (255, 255, 255))

    # Pour dessiner efficacement on utilise un objet Draw du module
    # PIL.ImageDraw
    draw = Draw(im)

    # On dessine les lignes de bas en haut
    row = height-pix_size

    for step in steps:
        draw_line(draw, step, row, palette, pix_size)
        row -= pix_size

    return im

def bubble_sort_steps(l):
    """
    Trie la liste l en utilisant bubble_sort ; retourne une liste des copies de
    l à chaque étape de l'algo.
    """

    last = len(l)
    steps = []

    while last > 0:
        i_max = 0
        for i in range(0, last-1):
            steps.append(l.copy())
            if l[i] > l[i+1]:
                i_max = i+1
                l[i], l[i+1] = l[i+1], l[i]
        last = i_max

    steps.append(l.copy())
    return steps

def test_sort(n, sort_algo = bubble_sort_steps, filename="bubbles.png"):
    """
    Le paramètre sort_algo doit être une fonction implémentant un algo de tri
    et retournant une liste des différents états de la liste triées pendant
    l'exécution de l'algo.

    Construit une liste au hasard de taille n, la trie et dessine une image
    correspondant à l'exécution du sort_algo sur cette liste
    """

    l = list(range(n))
    shuffle(l)
    steps = sort_algo(l)
    print("exécution en %d étapes de calcul" % len(steps))
    im = draw_steps(steps)
    im.save(filename)
    print("%s sauvé" %filename)