import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation  as animation
import matplotlib.colors as colors
import time
def p(e):
    print(e)
    return e

def alealiste(n,M):
    return np.array(np.random.random((n,))*M,dtype=int)
    
def ytrinsertion(L):
    if len(L)<=1:
        return L
    out = np.empty((len(L),),dtype=int)
    out[0] = L[0]
    out[1:] = yield from ytrinsertion(L[1:])
    for i in range(len(out)-1):
        if out[i+1]>=L[0]:
            out[i]=L[0]
            return out
        out[i] = out[i+1]
        out[i+1] = L[0]
        yield out
    out[-1]=L[0]
    yield out
    
def triRapideEnPlace(l,a=None,b=None):
    """
        Trie la liste l entre a et b
    """
    if a==None: a = 0
    if b==None: b = len(l)
    
    if b-a==0:
        return l
    if b-a==1:
        return l
    n = a+(b-a)//2
    pivot = l[n]
    i = n
    maxindex = b
    minindex = a
    while maxindex != minindex:
        # On souhaite ranger l'élément i dans la bonne moitié
        # On suppose que i n'est pas dans les parties rangées
        if l[i] < pivot or (l[i]==pivot and np.random.randint(0,2)==1):
            l[i],l[minindex] = l[minindex],l[i]
            minindex += 1
        else:
            l[i],l[maxindex-1] = l[maxindex-1],l[i]
            maxindex -= 1
        yield l
        # On prend un i pas dans les parties triées
        i = (maxindex-minindex)//2 + minindex
    yield from triRapideEnPlace(l,a,maxindex)
    yield from triRapideEnPlace(l,maxindex,b)


def triFusionRec(l,index):
    if len(l)==0:
        return l
    if len(l)==1:
        return l
    n = len(l)//2
    l1,l2 = triFusionRec(l[:n],0),triFusionRec(l[n:],n)
    out = []
    i,j = 0,0
    while i<len(l1) or j<len(l2):
        if j>=len(l2) or (i<len(l1) and l1[i]<=l2[j]):
            out.append(l1[i])
            i+=1
        else:
            out.append(l2[j])
            j+=1
        V[index:index+len(out+l1[i:]+l2[j:])] = np.array(out+l1[i:]+l2[j:])
        print(V)
        update()
    return out
    
def update():
    time.sleep(1)
   
N = 100
v = 100
X = np.linspace(0,N-1,N,dtype=int)
L = np.arange(N)
np.random.shuffle(L)



fig=plt.figure()

#trieur = triFusionRec(L)
V = L.copy()
barcollection = plt.bar(X,L,width=1.0)

def animate(i):
    y = V
    for i, b in enumerate(barcollection):
        b.set_height(y[i])
        b.set_color(colors.hsv_to_rgb((y[i]/v,1.0,1.0)))

import threading
class Foo (threading.Thread):
    def __init__(self):
        threading.Thread.__init__(self)
    def run (self):
          ytrinsertion(V,0)

Foo().start()

anim=animation.FuncAnimation(fig,animate,repeat=False,blit=False, interval=1)

plt.show()