import typing

"""
Explanation: Algorithme de Lempel-Ziv-Welch
Références

https://fr.wikipedia.org/wiki/Lempel-Ziv-Welch
https://www.geeksforgeeks.org/lzw-lempel-ziv-welch-compression-technique/

Illustrations

http://igm.univ-mlv.fr/~dr/XPOSE2013/La_compression_de_donnees/lzw.html
https://fr.planetcalc.com/9069/

Implémentations

Ici dans ce notebook, qui est aussi sur mon GitHub de notebooks : https://github.com/Naereen/notebooks/blob/master/Coding_and_Decoding_Lempel-Ziv-Welch_in_Python.ipynb
https://rosettacode.org/wiki/LZW_compression plein d'implémentations
End of explanation
"""


def encodage_LZW(mot: str) -> typing.List[int]:
    # les entiers écrits pour le message compressé
    codes_ecrits = []
    # le dictionnaire initial, mapping de str (1+ lettres) vers entiers
    dictionnaire = { chr(i): i for i in range(255) }
    # on saute la valeur 256
    prochain_code = 257
    mot_actuel = ""

    n = len(mot)
    for i in range(n):
        # on lit la i-ième lettre du mot d'entrée
        lettre = mot[i]
        # le mot actuel a une lettre de plus
        mot_actuel = mot_actuel + lettre
        print("Lecture de ième = {}ème lettre = {}, mot actuel = {}".format(i, lettre, mot_actuel))
        # si ce mot actuel n'est pas dans le dictionnaire
        if mot_actuel not in dictionnaire:
            print("Ajout de '{}' au dictionnaire, de code = {}".format(mot_actuel, prochain_code))
            dictionnaire[mot_actuel] = prochain_code
            prochain_code += 1
            # on produit le code du mot_actuel sans sa dernière lettre
            code_actuel = dictionnaire[mot_actuel[:-1]]
            codes_ecrits.append(code_actuel)
            print("On écrit {} , code de '{}', dans le code de sortie...".format(code_actuel, mot_actuel[:-1]))
            # on garde juste la dernière lettre du mot actuel pour continuer
            mot_actuel = mot_actuel[-1]

    # on écrit le dernier mot
    if mot_actuel in dictionnaire:
        code_actuel = dictionnaire[mot_actuel]
        codes_ecrits.append(code_actuel)
        print("On écrit {} dans le code de sortie...".format(code_actuel))
    # Statistique à la fin
    print("Pour un mot d'entrée de taille = {}, le code de sortie est de taille {} ({:.1f}% de gain).".format(
        len(mot), len(codes_ecrits), 100*len(mot)/float(len(codes_ecrits))))
    return codes_ecrits

encodage_LZW("barbapapa")

encodage_LZW("Nous sommes des étudiants en informatique au Lycée Kléber en MP2I")

"""
Explanation: 1. Encodage de Lempel-Ziv-Welch
End of explanation
"""


def decodage_LZW(code_lu: typing.List[int]) -> str:
    # Mot produit en sortie, vide au début
    mot_lu = ""
    # Dictionnaire mappant les entiers à la chaîne associée
    dictionnaire = { i: chr(i) for i in range(255) }
    # On saute la valeur 256
    prochain_code = 257
    # Mot actuel, vide au début
    mot_actuel = ""
    
    m = len(code_lu)
    # Si le code lu est vide, on renvoie un texte vide
    if m == 0: return ""
    
    # On lit le premier entier du code lu
    code_actuel = code_lu[0]
    # Il est forcément déjà dans le dictionnaire, on le décode directement
    mot_actuel = dictionnaire[code_actuel]
    # Et on l'écrit
    mot_lu += mot_actuel
    # On commence avec w = mot_actuel d'une lettre
    w = mot_actuel

    for i in range(1, m):
        # On lit le ième code suivant
        code_actuel = code_lu[i]
        # S'il est déjà dans le dictionnaire, le mot actuel correspond au code donné par le dict.
        if code_actuel in dictionnaire:
            mot_actuel = dictionnaire[code_actuel]
            print("Code lu = {}, mot correspondant = {}.".format(
                code_actuel, mot_actuel))
        # Sinon c'est nécessaire la prochaine valeur non encore ajoutée dans le dictionnaire
        elif code_actuel == prochain_code:
            # le mot actuel est le mot + la lettre du début de ce mot
            mot_actuel = w + w[0]
            print("Code lu = {}, mot correspondant = {}.".format(
                code_actuel, mot_actuel))
        else:
            raise ValueError("Mauvaise compression code_actuel = {}".format(code_actuel))
        # On écrit ce mot actuel
        mot_lu += mot_actuel
        print("Ajout de {} au dictionnaire, de valeur = '{}'".format(
            prochain_code, w + mot_actuel[0]))
        # On ajoute dans le dictionnaire w + mot_actuel[0]
        dictionnaire[prochain_code] = w + mot_actuel[0]
        prochain_code += 1
        # Et le w suivant est mot_actuel
        w = mot_actuel
    return mot_lu

"""
Explanation: 2. Décodage de Lempel-Ziv-Welch
End of explanation
"""


decodage_LZW([98, 97, 114, 257, 112, 97, 261])

decodage_LZW([78, 111, 117, 115, 32, 115, 111, 109, 109, 101, 260, 100, 266, 32, 233, 116, 117, 100, 105, 97, 110, 116, 260, 101, 110, 32, 105, 110, 102, 111, 114, 109, 97, 116, 105, 113, 117, 101, 32, 97, 117, 32, 76, 121, 99, 233, 294, 75, 108, 233, 98, 101, 114, 32, 280, 32, 77, 80, 50, 73])

"""
Explanation: Exemples :
End of explanation
"""


