##Q1. 
"""10 bits permettent d’obtenir 210 = 1024 valeurs. Etant donné qu’elles sont signées, on pourra représenter des entiers de - 512 à 511 (on a le zéro qui prend une des valeurs).
"""

##Q2. 
"""La résolution est de : 10 / 1023 = 0,009 775 V / mesure.
"""

##Q3.
def check(mesure,CheckSum):
    somme =0
    for i in range ( len ( mesure )):
        somme += abs ( mesure [ i ])
    if somme % 10000 == CheckSum :
        return True
    else :
        return  False
#test
import numpy as np
mesure=[555+275*np.exp(-i/40) for i in np.arange(0,200,1)]
mesure =np.array(mesure,dtype=(int))
print(check(mesure,1963))

##Q4.
import matplotlib.pyplot as pl

mesure=[555+275*np.exp(-i/40) for i in np.arange(0,200,1)]
def affichage (mesure) :
    t=np.arange(0,len(mesure)*2,2)
    mesure =np.array(mesure)*4e-3
    pl.axis([0,t[-1]+1,2,3.6])
    pl.plot(t,mesure)
    pl.show()
affichage(mesure)
    
##Q5.
# SELECT nSerie FROM testfin WHERE ( Imoy > Imin AND Imoy < Imax)
# 
##Q6. 
# La sous requête permettant d’obtenir la valeur moyenne de l’écart type est : 
# SELECT AVG(Iec) FROM testfin
# 
# La requête complète est : 
# SELECT nSerie, Iec, fichierMes FROM testfin WHERE Iec > (SELECT AVG(Iec) FROM testfin)
# 
##Q7. 
# SELECT nSerie,fichierMes FROM testfin WHERE nSerie NOT IN (SELECT nSerie FROM production)

###########################################################################
### Arbre de Huffman : Auto Generation
###########################################################################
def make_leaf (symbol , weight ):
    return (symbol , weight )

def test (x):
    return isinstance (x, tuple ) and len(x) == 2 and isinstance (x[0] , str) and isinstance (x[1] , int)

def get1 (x):
    return x[0]

def get2 (x):
    return x[1]

def get3 ( huff_tree ):
    return huff_tree[0]

def get4 ( huff_tree ):
    return huff_tree[1]

def get5 ( huff_tree ):
    if test ( huff_tree ):
        return [ get1 ( huff_tree )] # Attention le symbole est dans une liste
    else :
        return huff_tree[2]

def get6 ( huff_tree ):
    if test ( huff_tree ):   
        return get2( huff_tree )
    else :
        return huff_tree[3]

def make_huffman_tree ( left_branch , right_branch ):
    return [ left_branch , right_branch , get5 ( left_branch ) + get5 ( right_branch ), get6 ( left_branch ) + get6 ( right_branch )]

##Q8.
node1= [('F',1),('E',1), ['F','E'],2] 
node2= [('D',1),('B',1), ['D','B'],2]
##Q9.
node3 = [ [('F',1),('E',1), ['F','E'],2], [('D',1),('B',1), ['D','B'],2], ['F','E','D','B'], 4]

##Q10.
def freq_table(txt):
    ftble = {}
    for c in txt: 
        if c not in ftble :
            ftble [c] = 1
        else :
            ftble [c] += 1
    return ftble
#test        
T=freq_table("ABRACADABRA")
print(T)
print(T.items())

##Q11. Construction de l' arbre de Huffman
from heapq import heappush, heappop, heapify

def encode_Huffman(dico):
    heap = [[wt, [sym, ""]] for sym, wt in dico.items()]
    print(1,heap)
    heapify(heap)
    print(2,heap)
    while len(heap) > 1:
        lo = heappop(heap)
        hi = heappop(heap)
        print(3,lo)
        print(3,hi)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
        print(4,heap)
    h=heappop(heap)[1:]
    print(5,h)
    #huffman=sorted(h, key=lambda p: (len(p[-1]), p))
    return dict(h)
"""
1.	construire une table des occurrences à partir du dictionnaire des fréquences dico.items())
2.	on reclasse la liste en arbre
3.   si la liste a au moins 2 éléments : on enlève les 2 premiers elements du tas
4.      	construction d’un noeud de huffman avec les deux feuilles/noeuds de poids le plus faible
4.	     insertion du noeud créé dans la liste à la bonne position pour avoir une liste de noeuds triés par poids croissant en mettant le code binaire associé en fonction du code déja utilisé
5.    classement de la liste par nombre binaire le moins long au plus long petite à la plus grande 
6.    on transforme enfin la liste en dictionnaire au return
"""
#test
C = encode_Huffman(T)
print(C)

##Q12.
def  encodage(texte,code):
    texte_binaire = ''
    for c in texte:
        texte_binaire = texte_binaire + code[c]
    return texte_binaire

#test
text1=encodage("ABRACADABRA",C)
print(text1)
#01101001110011110110100

##Q13.
def  decodage(code,texte_binaire):
    code_inv = dict((code[str(bits)], bits) for bits in code)
    print(code_inv)
    # construit le dictionnaire inverse
    texte = ''
    tampon = ''
    for b in texte_binaire:
        tampon = tampon+b
        if tampon in code_inv:
            texte = texte+code_inv[tampon]
            tampon = ''
    return texte

#test
text_decode=decodage(C,text1)
print(text_decode)

##Q14.
def fusion(L1,L2):#Fusion de deux listes triées, méthode récursive
    if len(L1)==0:
        return L2
    if len(L2)==0:
        return L1
    if L1[0]>L2[0]:
        return [L2[0]]+fusion(L1,L2[1:])
    else:
        return [L1[0]]+fusion(L1[1:],L2)

def trifusion(L):#Tri fusion
    if len(L)==1:
        return L
    else:
        return fusion(trifusion(L[:len(L)//2]),trifusion(L[len(L)//2:]))

#test
from random import shuffle
liste=[i for i in range(100)]
shuffle(liste)
print(liste)
print(trifusion(liste))