###########################################################################
### 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. def freq_table (txt) ?? A compléter


#test######
# T=freq_table("ABRACADABRA")
# print(T)
# print(T.items())

##Q17. 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)
    return dict(h)