import os
from time import time

class Node: #Declaración de variables para crear los nodos
    probability =0.0 #Declarada como fload
    symbol = " " #Variable vacia
    encodings = ""
    visited = False #variable Boolean
    parent = -1 #Longitud de 0 a -1 variable entera
class Huffman: #Declaración de variables para la creación del arbol de Huffman
    Tree = None #Retornar arbol
    Root = None #Retornar raiz
    Nodes = []
    probs = {} #bloque, instancia el método
    dictEncoder = {}

    #1
    def __init__(self,symbols): #Inicianilizamos las funciones, con los atributos que va a utilizar
        self.initNodes(symbols) #retorna valores
        self.buildTree()
        self.buildDictionary()
    #2

    def initNodes(self,probs): #creamos los nodos con sus respectivas posibilidades
        for symbol in probs:
            node =Node() #inicializamos el node
            node.symbol = symbol
            node.probability = probs[symbol] # Asiganamos una probabilidad a cada simbolo o letra
            node.visited = False #Variable que no es fija que va a ir cambiando
            self.Nodes.append(node) #creamos una lista para cada nodo creado
            self.probs[symbol]=probs[symbol] #Establece para ca probabilidad de simbolo
    #3

    def buildTree(self): #Realizamos las operaciones de acuerdo a la lógica de Huffman
        indexMin1 = self.getNodeWithMinimumProb() #buscamos el menor número de la primera probabilidad
        indexMin2 = self.getNodeWithMinimumProb() #buscamos el menor número de la segunda probabilidad

        while indexMin1 != -1 and indexMin2 !=-1: #(!= evalua como verdadero si 2 variable son diferentes)
            node =Node()
            node.symbol="." # se llama el simbolo digitado para que salga el resultado
            node.encodings=""
            #llamamos a las dos probabilidades minimas
            prob1 = self.Nodes[indexMin1].probability
            prob2 = self.Nodes[indexMin2].probability
            node.probability = prob1 + prob2
            node.visited =False #false =1
            node.parent = -1 #restamos la probabilidad a -1
            self.Nodes.append(node)
            self.Nodes[indexMin1].parent = len(self.Nodes) - 1 #lista o cadena que queremos medir
            self.Nodes[indexMin2].parent = len(self.Nodes) - 1

            #Regla: 0 a mayor probabilidad, 1 a menor probalidad
            if prob1 >= prob2:
                self.Nodes[indexMin1].encoding = "0"
                self.Nodes[indexMin2].encoding = "1"
            else:
                self.Nodes[indexMin1].encoding = "1"
                self.Nodes[indexMin2].encoding = "0"
            indexMin1 = self.getNodeWithMinimumProb()
            indexMin2 = self.getNodeWithMinimumProb()
    #4
    def getNodeWithMinimumProb(self):
        minProb = 1.0
        indexMin = -1
        for index in range(0, len(self.Nodes)):
            if (self.Nodes[index].probability) < minProb and (not self.Nodes[index].visited):
                minProb = self.Nodes[index].probability
                indexMin = index

        if indexMin != -1:
            self.Nodes[indexMin].visited = True
        return indexMin
    #5
    def showSymbolEncoding(self, symbol):
        found = False
        index = 0
        encoding = ""
        for i in range(0, len(self.Nodes)):
            if self.Nodes[i].symbol ==symbol:
                found = True
                index = i
                break
        if found:
            while index != -1:
                encoding = "%s%s" % (self.Nodes[index].encoding, encoding)
                index = self.Nodes[index].parent
        else:
            encoding = "simbolo desconocido"
        return encoding

    # 6
    def buildDictionary(self):  # Creacion de diccionaio, se guardan los simbolos con sus respectivos
    # codigos binarios resueltos por el arbol
        for symbol in self.probs:
            encoding = self.showSymbolEncoding(symbol)
            self.dictEncoder[symbol] = encoding

    # 7
    def encode(self, plain): #Agrupa los codigos binarios codificados de acuerdo al mensaje escrito
        #en la consola
        encoded =""
        for symbol in plain:
            encoded = "%s%s" % (encoded, self.dictEncoder[symbol])
        return encoded

    # Inicio de la decodificacion
    def decode(self, encoded):  # Recibe la cadena del codigo binario
        index = 0
        decoded = ""

        while index < len(encoded):
            found = False
            #Busca cada en parte codificada un simbolo, buscando cuál es compatible
            #con otra
            aux = encoded[index:]

            for symbol in self.probs:
                if aux.startswith(self.dictEncoder[symbol]):
                    decoded = "%s%s" % (decoded, symbol)
                    index = index + len(self.dictEncoder[symbol])
                    break

            return decoded
    #Fin

if __name__ == "__main__":
    print ("\n\n............CODIFICACION........\n\n")
    mensaje =input("Ingrese la palabra u oracion: ")
    print ("\n\nTotal de simbolos: \n\n %s"% (len(mensaje)))
    simbolos=''
    probabilidad=[]
    msm=mensaje
    d=0

    for i in mensaje:
        if i in msm:
            simbolos+=i
            probabilidad.append(float(float ( msm.count(i))/float(len(mensaje))))
            msm=msm.replace(i, '')
            d+= 1

    symbols=dict(zip(simbolos, probabilidad)) #Funcion para llamar al simbolo y a su probabilidad
    print ("\n\nSimbolos comprimidos: \n\n" ,d) #Imprime la cantidad de simbolos que contabilizalo la funcion count
    print ("\n\nPROBABILIDAD DE CADA SIMBOLO:\n\n" , symbols)
    tiempo_inicial=time() #Funcion para determinar el tiempo del programa
    #Codificacion de los simbolos
    huffman=Huffman(symbols) #Llamamos a la clase Huffman
    print ("\n\nSimbolos codificados usando el arbol de Huffman: \n\n")
    for symbol in symbols:
        print ("Simbolo: %s; Codificacion: %s" % (symbol, huffman.showSymbolEncoding(symbol)))
    encoded = huffman.encode(mensaje) #Llama funcion tras funcion para el procedimiento de codificacion
    print ("\n\nMensaje que se esta codificando: \n\n%s" % (mensaje))
    print ("\n\nCodificacion en bits : \n\n%s" % (encoded)) #Notamos el msj en bits
    print ("\n\nLa longitud de codigo binario es: \n\n%s" % (len(encoded)))
    data = encoded

#Decodificacion
    print ("\n\n..................DECODIFICACION..................\n\n")
    decoded = huffman.decode(data) #Llamamos a las funciones correspondientes y el mensaje llamado data
    print ("El codigo binario a decodificar es:\n\n", data )
    print ("\n\nEl mensaje decodificando es: \n\n %s" % (decoded)) #Imprimimos el resultado de la funcion decoded

#Calculo para el tiempo del procedimiento
    tiempo_final= time()
    tiempo_ejecucion= tiempo_final - tiempo_inicial
    print ('\n\nEl tiempo de transmision es: ',tiempo_ejecucion)
os._exit(0)