import os
from time import time

class Node: # declaracion de variables para crear los nodos
    # properties
    probability = 0.0 # inicializamos
    symbol = ""
    encoding = ""
    visited = False
    parent = -1 # longitud de 0 a -1

class Huffman: # declaracion de variables para la creacion del arbol de Huffman
    Tree = None # retornar arbol
    Root = None # retornar raiz
    Nodes = [] #Lista
    probs = {} #bloque
    dictEncoder = {}

    # methods
    def __init__(self, symbols):
        self.initNodes(symbols)
        self.buildTree()
        self.buildDictionary()

    def initNodes(self, probs): # creamos los nodos con sus respectivas probabiliddes
        for symbol in probs:
            node = Node() # inicializamos el node
            node.symbol = symbol
            node.probability = probs[symbol] # asignamos una probabilidad a cada simbolo o letra
            node.visited = False # variable q no es fija que va ir cambiando
            self.Nodes.append(node) # creamos una lista por cada nodo creado
            self.probs[symbol]=probs[symbol]  # establece para cada probabilidad un simbolo


    def buildTree(self): # Realizamos las operaciones de acuerdo al regamente para la construccion del arbol de Huffman
        indexMin1 = self.getNodeWithMinimumProb() # Buscamos el menor numero de la primera probabilidad
        indexMin2 = self.getNodeWithMinimumProb() # Buscamos el menor numero de la segunda probabilidad

        while indexMin1 != -1 and indexMin2 != -1: # != evalúa como verdadero si 2 variables son diferentes
            node = Node() # inicializamos
            node.symbol = "."
            node.encoding = ""
            # llamamos a las dos probabilidades minimas
            prob1 = self.Nodes[indexMin1].probability
            prob2 = self.Nodes[indexMin2].probability
            node.probability = prob1 + prob2 # sumamos las probabilidades
            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 probabilidad.
            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()

    def getNodeWithMinimumProb(self): # realizamos una comparacion para obteener el nodo de menor probabilidad
        minProb = 1.0   # La minima probabilidad no puede ser mayor de 1
        indexMin = -1 # indice para restar a la probalidad

        for index in range(0, len(self.Nodes)): # index es el numero de probabilidad
            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

    def showSymbolEncoding(self, symbol): # designamos un codigo binario a cada simbolo resuelto por el arbol de Huffman
        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: # encontro
            while index != -1: # si son diferentes
                encoding = "%s%s" % (self.Nodes[index].encoding, encoding)
                index = self.Nodes[index].parent
        else:
            encoding = "simbolo desconocido"

        return encoding

    def buildDictionary(self): # creamos un diccionario, guardamos todos los simbolos con sus respectivos codigos binarios
                               # resueltos por el arbol de Huffman
        for symbol in self.probs:
            encoding = self.showSymbolEncoding(symbol)
            self.dictEncoder[symbol] = encoding

    def encode(self, plain): # agrupa los codigos binarios codificados de acuerdo al mensaje escrito en 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 enviado desde el emisor para decodificar
        index = 0
        decoded = ""


        while index < len(encoded): # mientras buscamos en la longitud de la parte codificada


            founf = False # establesemos una variable

            aux = encoded[index:] # va a buscar a cada parte codificada un simbolo
                                  # no va ser fija va ir buscando cual es compatible con cada una


            for symbol in self.probs:
                if aux.startswith(self.dictEncoder[symbol]): # se comprueba si la cadena es verdadera o falsa. si la parte axuliar inicia dentro del diccionario encodificado  nos va a dar
                    decoded = "%s%s" % (decoded, symbol) # parte decodificada
                    index = index + len(self.dictEncoder[symbol]) # busqueda para cada simbolo a cada probabilidad
                    break

        return decoded

    #FIN DE LA DECODIFICACION ..........................................................................................................................................................
if __name__=="__main__":

    print ("INGRESAR LOS SIMBOLOS O UN MENSAJE QUE DESEA COMPRIMIR:")
    print (" " )
    mensaje=input()
    print (" ")

    print ("NUMERO TOTAL DE SIMBILOS O BITS INTRODUCIDOS PARA SER ENVIADOS:  %s" % (len(mensaje)))
    print (" ")
    print ("[ 1 PASO]: NUMERO DE SIMBOLOS O BITS, ERRADOS O REPETIDOS ")
    print (" ")
    simbolos=''
    probabilidad=[]
    msm=mensaje
    d=0

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

    symbols=dict(zip(simbolos, probabilidad))
    print (" ")
    print ("NUMERO DE SIMBOLOS COMPRIMIDOS=",d)
    print (" ")
    print ("[ 2 PASO]:PROBABILIDAD DE CADA SIMBOLO P(S)= (numero de bit errados) / (numero total de bit enviados)")
    print (" ")
    print (symbols)
    print (" ")
    print ("[ 3-4 PASO]: LA FUNCION [buildTree] DEL CODIGO. ORDENA LAS PROBABILIDADES DE MENOR A MAYOR PROBABILIDAD")
    print ("           Y REALIZA LAS OPERACIONES YA EXPLICADAS QUE SE REQUIEREN PARA IR ARMANDO EL ARBOL DE HUFFMAN")
    print (" ")


    tiempo_inicial= time()


    # codificar instancia
    huffman = Huffman(symbols)
    print ("...........................................................................")
    print ("...........................CODIFICACION....................................")
    print ("...........................................................................")
    print (" ")
    print (" ")
    print ("[ 5 PASO]:CODIFICACION BINARIA USANDO EL ARBOL DE HUFFMAN:")
    print ( " ")
    for symbol in symbols:
        print ("Simbolo: %s; Codificacion: %s" % (symbol, huffman.showSymbolEncoding(symbol)))

    encoded = huffman.encode(mensaje)
    print (" ")
    print ("Mensaje que se esta codificando: %s;" % (mensaje))
    print (" ")
    print ("Codificacion en bits : %s" % (encoded))
    print (" ")
    print ("La longitud de codigo binario es:  %s" % (len(encoded)))
    data = encoded
    print (" ")
    print ("Codigo codificado que esta siento enviado al receptor:  %s" % (data))

    # DECODIFICACION
    print (" ")
    print (" ")
    print (" ")
    print (" ")
    print ("...........................................................................")
    print ("...........................DECODIFICACION..................................")
    print ("...........................................................................")
    print (" ")
    print (" ")
    print ("Esperando el mensaje del emisor para su decodificacion......")


    decoded = huffman.decode(data)
    print (" ")
    print ("CODIGO BINARIO RECIBIDO ES :", data )
    print (" ")
    print ("DECODIFICANDO EL CODIGO....................................")
    print (" ")
    print ("Mensaje decodificado : %s " % (decoded))

    # FIN


    tiempo_final= time()
    tiempo_ejecucion= tiempo_final - tiempo_inicial
    print (" ")
    print ('El tiempo de transmisiOn es:',tiempo_ejecucion) #En segundos)



os._exit(0)