/*
Grupo:
Matteo Domiciano Varnier - 10390247
Daniel Reis Raske - 10223349
Fernando Pegoraro Bilia - 10402097
*/

/*
Oque nosso codigo faz:
Codigo é a codificao e a descoficacao de um texto salvo em um arquvio txt,
a codificao e descoficacao do texto é feito por meio de um algoritmo de Huffman, 
ele ira ler no in.txt e ira escrever oque foi codificado em um arquivo chamado encoded.txt,
apos isso, ele ira descodificar e salvar no arquivo out.txt .
*/

/* 
ler_arquivo(Arquivo, Texto) :- Lê o arquivo inicial (in.txt) onde estará o texto para leitura 
*/
ler_arquivo(Arquivo, Texto) :-
    open(Arquivo, read, Fluxo),
    get_code(Fluxo, C1),
    ler_arquivo_codigos(Fluxo, C1, Codigos),
    close(Fluxo),
    string_codes(Texto, Codigos).

ler_arquivo_codigos(Fluxo, -1, []) :- !.
ler_arquivo_codigos(Fluxo, Codigo, [Codigo|Codigos]) :-
    get_code(Fluxo, ProximoCodigo),
    ler_arquivo_codigos(Fluxo, ProximoCodigo, Codigos).

/* 
amostra(Texto) :- Lê o conteúdo que está dentro do in.txt 
*/
amostra(Texto) :-
    ler_arquivo('in.txt', Texto).

/* 
escrever_arquivo(Arquivo, Texto) :- Escreve no arquivo as informações desejadas 
*/
escrever_arquivo(Arquivo, Texto) :-
    open(Arquivo, write, Fluxo),
    escrever_codigos(Fluxo, Texto),
    close(Fluxo).

escrever_codigos(_, []).
escrever_codigos(Fluxo, [Codigo|Codigos]) :-
    put_code(Fluxo, Codigo),
    escrever_codigos(Fluxo, Codigos).

escrever_no_arquivo(Arquivo, Texto) :-
    open(Arquivo, write, Fluxo),
    write_term(Fluxo, Texto, [quoted(true)]),
    close(Fluxo).


/* 
frequencia_letra(Texto, Frequencia) :- Calcula a frequência de caracteres em um texto e retorna uma lista de pares [Caractere, Vezes que o caractere se repetiu] 
*/
frequencia_letra(Texto, Frequencia) :-
    frequencia_letra(Texto, [], Frequencia).
frequencia_letra([], Acc, Acc).
frequencia_letra([UElemento|Texto], Acc, Frequencia) :-
    frequencia_auxilio(Texto, UElemento, 1, Contagem, RemTexto),
    frequencia_letra(RemTexto, [[UElemento, Contagem]|Acc], Frequencia).

frequencia_auxilio([Elemento|Texto], Elemento, Acc, Contagem, RemTexto) :-
    Acc1 is Acc+1,
    frequencia_auxilio(Texto, Elemento, Acc1, Contagem, RemTexto).
frequencia_auxilio(RemTexto, _, Acc, Acc, RemTexto).

/*
frequencia_para_folhas(Frequencia, Folhas) :- Converte uma lista de frequências de caracteres em uma lista de folhas de uma árvore 
*/
frequencia_para_folhas(Frequencia, Folhas) :-
    frequencia_para_folhas(Frequencia, [], Folhas).
frequencia_para_folhas([], Acc, Acc).
frequencia_para_folhas([[Letra, Contagem]|Frequencia], Acc, Folhas) :-
    frequencia_para_folhas(Frequencia, [arvore(folha, Letra, Contagem, na, na)|Acc], Folhas).

construir_arvore([Huffman], Huffman).
construir_arvore([arvore(Tipo1, Letra1, Frequencia1, Esquerda1, Direita1), arvore(Tipo2, Letra2, Frequencia2, Esquerda2, Direita2)|Folhas], Arvore) :-
    SomaFrequencia is Frequencia1+Frequencia2,
    construir_arvore([arvore(nodo, na, SomaFrequencia, arvore(Tipo1, Letra1, Frequencia1, Esquerda1, Direita1), arvore(Tipo2, Letra2, Frequencia2, Esquerda2, Direita2))|Folhas], Arvore).

/*
codigo_huffman(Arvore, Codigos) :- Gera códigos de Huffman para os caracteres com base na árvore de Huffman.
*/
codigo_huffman(Arvore, Codigos) :-
    codigo_huffman(Arvore, [], Codigos).
codigo_huffman(na, Acc, Acc).
codigo_huffman(arvore(folha, Letra, _, na, na), Acc, Codigos) :-
    reverse(Acc, Acc1), % Para obter o código Huffman na ordem correta
    codigo_huffman(na, [Letra, Acc1], Codigos).
codigo_huffman(arvore(nodo, na, _, Esquerda, _), Acc, Codigos) :-
    codigo_huffman(Esquerda, [0|Acc], Codigos).
codigo_huffman(arvore(nodo, na, _, _, Direita), Acc, Codigos) :-
    codigo_huffman(Direita, [1|Acc], Codigos).

/*
codificar(Texto, CodigoHuffman, Codificado) :- Codifica um texto ASCII usando os códigos de Huffman fornecidos.
*/
codificar(Texto, CodigoHuffman, Codificado) :-
    reverse(Texto, TextoReverso),
    codificar(TextoReverso, CodigoHuffman, [], Codificado).
codificar([], _, Acc, Acc).
codificar([Letra|Texto], CodigoHuffman, Acc, Codificado) :-
    buscar_letra(Letra, CodigoHuffman, Codigo),
    append(Codigo, Acc, Acc1),
    codificar(Texto, CodigoHuffman, Acc1, Codificado).

/*
decodificar(Codificado, CodigoHuffman, ASCII) :- Decodifica um texto codificado usando os códigos de Huffman fornecidos.
*/
decodificar(Codificado, CodigoHuffman, ASCII) :-
    decodificar(Codificado, CodigoHuffman, [], [], ASCIIReverso),
    reverse(ASCIIReverso, ASCII).
decodificar([], _, _, Acc, Acc).
decodificar([Bit|Codificado], CodigoHuffman, Buffer, Acc, ASCII) :-
    append(Buffer, [Bit], Buffer1), % Senão, verificamos as letras invertidas, rs
    (   buscar_letra(Letra, CodigoHuffman, Buffer1) -> decodificar(Codificado, CodigoHuffman, [], [Letra|Acc], ASCII) ; decodificar(Codificado, CodigoHuffman, Buffer1, Acc, ASCII)).

/*
buscar_letra(Letra, [[Letra, Codigo]|_], Codigo). - Procura um caractere ou seu código de Huffman em uma lista de pares letra-código.
*/
buscar_letra(Letra, [[Letra, Codigo]|_], Codigo).
buscar_letra(Letra, [_|CodigoHuffman], Codigo) :-
    buscar_letra(Letra, CodigoHuffman, Codigo).

/*
teste() :- Executa um teste completo, codificando e decodificando um texto de exemplo.
*/
teste() :-
    amostra(Texto),
    string_to_list(Texto, ASCII),
    msort(ASCII, ASCIIOrdenado), % Não remove duplicatas

    frequencia_letra(ASCIIOrdenado, Frequencia),
    frequencia_para_folhas(Frequencia, Folhas),
    sort(3, @=<, Folhas, FolhasOrdenadas), % Ordenar as folhas por frequência
    construir_arvore(FolhasOrdenadas, Arvore),
    findall(Codigos, codigo_huffman(Arvore, Codigos), CodigoHuffman),
    codificar(ASCII, CodigoHuffman, Codificado),
    decodificar(Codificado, CodigoHuffman, Decodificado),
    string_to_list(CodificadoDecodificado, Decodificado),

    escrever_no_arquivo('encoded.txt', Codificado), % Escrever texto codificado no arquivo
    escrever_arquivo('out.txt', Decodificado), % Escrever texto decodificado no arquivo

   true.

/*
teste(Entrada, TextoCodificado) :- Realiza a codificação de um texto de entrada, retornando o texto codificado.
*/
teste(Entrada, TextoCodificado) :-
    string_to_list(Entrada, ASCII),
    msort(ASCII, ASCIIOrdenado), % Não remove duplicatas
    frequencia_letra(ASCIIOrdenado, Frequencia),
    frequencia_para_folhas(Frequencia, Folhas),
    sort(3, @=<, Folhas, FolhasOrdenadas), % Ordenar as folhas por frequência
    construir_arvore(FolhasOrdenadas, Arvore),
    findall(Codigos, codigo_huffman(Arvore, Codigos), CodigoHuffman),
    codificar(ASCII, CodigoHuffman, TextoCodificado).