###########################################################################
### 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 )]

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

##Q16.
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())
print(T.keys())
print(T.get('A'))
print(T.get('E'))


## 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)

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

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

##Q18.
def  decodage(dico,texte_binaire):
    dico_inv = dict((dico[cle], cle) for cle in dico)
    print(dico_inv)
    # construit le dictionnaire inverse
    texte = ''
    tampon = ''
    for b in texte_binaire:
        tampon = tampon+b
        if tampon in dico_inv:
            texte = texte+dico_inv[tampon]
            tampon = ''
    return texte

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