import heapq 

# Applica l'algoritmo di Huffman ad una lista di frequenze, i cui elementi sono costituite
# da tuple (simbolo, frequenza) dove simbolo è uno dei simboli dell'alfabeto
# della sorgente e frequenza è la frequenza relativa di quel simbolo

# ESEMPIO DI UTILIZZO
# import huffman
# freq = [('A',0.3),('B',0.20),('C',0.1),('D',0.40)]
# tree = huffman.albero(freq)
# tree.codice               # restituisce un dizionario con il codice (simbolo -> codice binario)
# tree.reverse_code         # restituisce un dizionario con il codice inverso (codice binario -> simbolo)

# Restituisce un dizionario che rappresenta il codice ottimo, calcolato con l'algoritmo 
# di Huffman, sotto forma di dizionario in cui le chiavi sono i simboli e 
# i valori il codice binario assegnato a quel simbolo

# Per utilizzarlo importare questo file come package (import huffman senza estensione .py)
# Il file definisce una classe albero che va istanziata, fornendo la lista delle frequenza

# es. albero_frequenze = huffman.albero(frequenze)
# dove frequenze è la lista contenente i dati di input

# L'oggetto restituito potrà fornire i seguenti dati:

# albero_frequenze.codice()          # restituisce il codice sotto forma di dizionario 
# albero_frequenze.reverse_code()    # restituisce il codice inverso: chiave la sequenz abinaria, valore
#                                    # il simbolo corrispondente
# albero_frequenza.freq              # le frequenze con cui è stato inizializzato

# Gli elementi che desideriamo inserire sono oggetti che costituiranno i nodi di un albero
# Conterranno come attributi il carattere, la sua frequenza e i puntatori ai figli 
# sinistro e destro, a loro volta oggetti di tipo nodo

class Nodo:
    def __init__(self,car,freq):
        self.car = car
        self.freq = freq
        self.left = None
        self.right = None

    # dobbiamo ridefinire il metodo per effettuare il confronto necessario all'ordinamento
        
    def __lt__(self,other):
        if other == None:
            return True
        if not isinstance (other,type(self)):
            return True
        else:
            return (self.freq < other.freq)
class Albero:
    def __init__(self,freq):
        self.freq = freq
        self.tree = []       
        self.codice= {}
        self.reverse_code = {}
        self.riempi_lista()
        self.costruisci_albero()
        self.assegna(self.tree[0],"")

    def riempi_lista(self):
        for elem in self.freq:
            n = Nodo(elem[0],elem[1])
            heapq.heappush(self.tree,n)

    def costruisci_albero(self):
        while(len(self.tree)>1):
            node1 = heapq.heappop(self.tree)
            node2 = heapq.heappop(self.tree)

            merged = Nodo(None, node1.freq + node2.freq)
            merged.left = node1
            merged.right = node2

            heapq.heappush(self.tree, merged)
    
    def assegna(self,root, current_code):
      # assegna i codici attraversando l'albero
        if(root == None):
            return

        if(root.car != None):
            self.codice[root.car] = current_code
            self.reverse_code[current_code] = root.car
            return  

        self.assegna(root.left, current_code + "0")
        self.assegna(root.right, current_code + "1")