cad=list()
referencias=list()
final=list()
caracteres={}
cadena_final=''
import networkx as nx
import matplotlib.pyplot as plt

G=nx.Graph()


class Arbol:
    def __init__(self,datos,izquierda=None,derecha=None):
      #  print 'creo arbol'
        self.datos=datos
        self.izquierda=izquierda
        self.derecha=derecha
        
        
def crear(final,cadena):
    global cadena_final
    arboles=list()
    while ((len(final) > 1)):
       # print "raiz", final[0][1] + final[1][1]
        raiz = Arbol(final[0][1] + final[1][1],final[0][0],final[1][0])
       # print "nodo izquierdo",final[0][0]
       # print "nodo derecho",final[1][0]
        final.append((raiz,final[0][1] + final[1][1]))
        del final[0]
        del final[0]
        final=sorted(final,key=lambda it: it[1])
    mostrararbolinorden(final[0][0],'')
    #dibujar(final[0][0],100,100)
    #print caracteres
    for i in cadena:
        cadena_final+=caracteres[i]
    return final[0][0]

def mostrararbolinorden(final,cam):
    if final==None:
        return cam[:-1]
    if type(final.datos)==str:
        print final.datos,': ',cam
    caracteres[final.datos]=cadena_final=mostrararbolinorden(final.izquierda,cam=cam+'0')
    caracteres[final.datos]=cadena_final=mostrararbolinorden(final.derecha,cam=cam+'1')
    
def dibujar(final,x,y):
    print 'dibujar'
    print 'final',final
    if final==None:
        return  x,y 
    dibujar(final.izquierda,x=x-(x/2),y=-(y*.5)+y)
 
    dibujar(final.derecha,x=((x)*.5)+x,y=-((y)*.5)+y)
    return

def ordenar(cadena):
    for i in cadena:
        if (i) not in referencias:
            referencias.append(i)
            cad.append((Arbol(i),caracteres[i]))
    final=sorted(cad,key=lambda it: it[1])
    print 'final-prueba',final
    raw_input()
    return final

def agrupar(cadena):
    for i in cadena:
        if i not in caracteres:
            caracteres[i]=1
        else:
            caracteres[i]=caracteres[i]+1
    return

def descomprimir(arbol):
    var=arbol
    palabra=''
    for i in cadena_final:
        if i=='0':
            var=var.izquierda
            if var.izquierda==None and var.derecha==None:
              palabra+=var.datos
              var=arbol
        else:
            var=var.derecha
            if var.izquierda==None and var.derecha==None:
                palabra+=var.datos
                var=arbol
    print 'Cadena descomprimida: ',palabra
            

def main():
    cadena=raw_input('Cadena a utilizar: ')
    agrupar(cadena)
    final=ordenar(cadena)
    arbol=crear(final,cadena)
    print 'Cadena comprimida: ',cadena_final
    descomprimir(arbol)
    #dibujar(final[0][0],10,10)
    #nx.draw(G)
    plt.show()

main()