huffman

from operator import itemgetter
from string import ascii_lowercase
from math import isclose
letters = [letter for letter in ascii_lowercase]


def phase_one(alphabet:list) -> tuple:
    """
    Fase 1 dell'algoritmo: riduce la lista di tuple in un'unica tupla contente tutti gli elementi dell'alfabeto
    Ad ogni passo i due simboli meno probabili vengono fusi insieme
    :param alphabet: lista di tuple relativa alla distribuzione dei simboli
    :return: tupla contenente tutti gli elementi dell'alfabeto
    """

    # ordinamento in base alla probabilità
    alphabet.sort(key=itemgetter(1))

    while len(alphabet) > 1:
        # dato che la lista è ordinata, i due elementi con probabilità minore sono i primi due
        min_1, min_2 = alphabet[0], alphabet[1]

        alphabet.remove(min_1)
        alphabet.remove(min_2)

        # si fa in modo che l'eventuale lettera singola viene messa come prima nella tupla
        if isinstance(min_2[0], str) and not isinstance(min_1[0], str):
            newElem = ((min_2[0], min_1[0]), min_1[1] + min_2[1])
        else:
            newElem = ((min_1[0], min_2[0]), min_1[1] + min_2[1])

        # aggiunta del nuovo elemento
        alphabet.append(newElem)
        # ordinamento in base alla probabilità
        alphabet.sort(key=itemgetter(1))

    return alphabet[0][0]

def phase_two(element, li, code) -> None:
    """
    Fase 2 dell'algoritmo di Huffman. Si aggiungono i codici in maniera ricorsiva
    :param element: elemento da codificare
    :param li: lista in cui inserire i simboli con relativa codifica
    :param code: codifica per il simbolo
    """

    if isinstance(element, str):
        li.append((element, code))
    else:
        # chiamata sull'elemento sinistro della tupla
        phase_two(element[0], li, code + "0")
        # chiamata sull'elemento destro della tupla
        phase_two(element[1], li, code + "1")

def huffman(alphabet) -> list:
    mergedElements = phase_one(alphabet)
    print("Phase one output: " + str(mergedElements))
    li = []
    phase_two(mergedElements, li, "")
    print("Phase two output: " + str(li))
    return li

def encoding(string, code):
    encodedStr = ""
    code = dict(code)

    for letter in string:
        encodedStr += code[letter]

    return encodedStr

def prefixFreeDecoding(string, code):
    """
    Decodifica una stringa binaria codificata tramite codice prefix-free
    :param string: stringa binaria da decodifcare
    :param code: codice prefix-free
    :return: messaggio decodificato
    """

    codings = [elem[1] for elem in code]
    message = ""

    while string != "":
        block = ''
        index = 0

        # lettera di un bit alla volta e ci si ferma appena si incontra un blocco di bit presente tra le possibili codifiche. Ciò è possibile perchè il codice è prefix-free
        while block not in codings:
            block += string[index]
            index += 1

        # ricerca del blocco di bit nelle tuple
        symbol = [elem for elem in code if block in elem]
        message += symbol[0][0]
        # rimozione del blocco nella stringa
        string = string[len(block):]

    return message

def main():

    # inserimento della distribuzione di probabilità
    distribution = []
    value = float(input("Please insert next value of the distribution or -1 to exit: "))
    while value != -1:
        if value > 0 and value < 1:
            distribution.append(value)
        else:
            print("ERROR: value not inserted. Try another")

        value = float(input("Please insert next value of the distribution or -1 to exit: "))

    sum = 0
    for elem in distribution:
        sum += elem

    if not isclose(sum, 1, rel_tol=1e-6):
        print("ERROR: insert a valid probability distribution (sum : " + str(sum) + ")")
        return


    alphabet = []
    for i in range(len(distribution)):
        elem = (letters[i], distribution[i])
        alphabet.append(elem)

    print("Alphabet: " + str(alphabet))
    alphabet.sort(key=itemgetter(1))
    print("Sorted Alphabet: " + str(alphabet))

    code = huffman(alphabet)

    string = input("insert a string for encoding/decoding test: ")
    encodedStr = encoding(string, code)

    print("encoded string: " + encodedStr)
    message = prefixFreeDecoding(encodedStr, code)
    print("decoded string: " + message)

if __name__ == '__main__':
    main()