#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Definicao de tipos */
/* String eh um ponteiro de char (um vetor de char) */
typedef unsigned char *String;

/* Dicionario eh um ponteiro de String (um vetor de string)
   Ou seja, eh uma matriz de char */
/* Dicionario[i] representa o caractere da posicao i da tabela ascii */
typedef String *Dicionario;

/* Variavel global que indica o tamanho do dicionario */
int tam = 0;

void imprimeDicionario (Dicionario dic) {
	int i = 0;

	for (i = 0; i <= tam; i++)
		printf("%d %s\n", i, dic[i]);
}

/* Inicializa o dicionario com os valores de 0 ate 255 da tabela ascii e retorna o dicionario */
Dicionario inicializaDicionario () {
	Dicionario d;
	int i;

	d = (Dicionario)malloc(sizeof(String)*1048576);
	for (i = 0; i < 256; i++) {
		d[i] = (String)malloc(sizeof(unsigned char)*1048576);
		sprintf(d[i], "%c", i);
	}
	tam = 255;
	return d;
}

/* Imprime o menu de opcoes para o usuario */
void imprimeMenu () {
	printf("\e[H\e[2J");
	printf("########## Compactador LZW ##########\n");
	printf("#           1 - Compactar           #\n");
	printf("#           2 - Descompactar        #\n");
	printf("#           0 - Sair                #\n");
	printf("#####################################\n");
}

/* Detecta se a string s esta contida no dicionario
   Retorna 1 se a string estiver no dicionario e 0 no caso contrario */
int estaNoDicionario (Dicionario dic, String s) {
	int i;

	for (i = 0; i <= tam; i++) {
		if (strstr(dic[i], s) != NULL)
			return 1;
	}
	return 0;
}

/* Transfere todo o conteudo de uma string b para uma string a */
void transfereString(char a[], char b[]) {
	int i;

	for (i = 0; i < 255; i++)
		a[i] = b[i];
}

/* Insere uma string s no dicionario */
Dicionario insereNoDicionario (Dicionario d, String s) {
	d[tam+1] = (String)malloc(sizeof(char)*1048576);
	sprintf(d[tam+1], "%s", s);
	//printf("%d %s\n", tam+1, d[tam+1]);

	/* Eh importante lembrar de incrementar o tamanho do dicionario apos fazer uma insercao */
	tam++;
}

/* Retorna a posicao de uma string s dentro do dicionario
   Retorna -1 caso a string nao seja encontrada */
int posicaoNoDicionario (Dicionario dic, String s) {
	int i;
	char aux[256];

	for (i = 0; i < 256; i++)
		aux[i] = '\0';

	for (i = 0; i <= tam; i++) {
		// printf("%d: Estou comparando %s com %s\n", i, s, dic[i]);
		if (strcmp(dic[i], s) == 0)
			return i;
	}

	/* for (i = 0; i < 256; i++)
		aux[i] = s[i];
	for (i = 0; aux[i] != '\0'; i++);
	aux[i-1] = '\0';
	posicaoNoDicionario(dic, aux); */
	/* Caso se deseje saber a posicao de uma string que nao esta no dicionario, ela eh adicionada ao dicionario e a busca eh chamada novamente */
	insereNoDicionario(dic, s);
	posicaoNoDicionario(dic, s);
}

/* Funcao de compressao */
void LZW (FILE *entrada, FILE *saida, Dicionario dic) {
	int i = 0;
	int cont = 0;
	// String old = (String)malloc(sizeof(char));
	// String neu = (String)malloc(sizeof(char));

	/* neu eh o pedaco do texto que esta sendo tratado agora e old eh o pedaco do texto que foi tratado na ultima iteracao
	   eh importante fazer essa separacao porque se neu NAO estiver no dicionario, old deve ser escrito na saida */
	char I[256];
	char IC[256];
	char c;

	/* Inicializa old e neu */
	for (i = 0; i < 256; i++) {
		IC[i] = '\0';
		I[i] = '\0';
	}

	/* A funcao eh executada ate encontrar o fim do arquivo */
	while (!feof(entrada)) {

		/* Analisa o caractere atual do texto e une com a ultima sequencia lida que nao estava no dicionario */
		fscanf(entrada, "%c", &c);
		for (i = 0; i < 256; i++) {
			IC[i] = I[i];
		}
		for (i = 0; IC[i] != '\0'; i++);
		IC[i] = c;
		IC[i+1] = '\0';

		/* Se IC esta no dicionario, apenas transfere o seu conteudo para IC e continua as iteracoes */
		if (estaNoDicionario(dic, IC)) {
			// fprintf(saida, "%s esta no dicionario\n", IC);
			transfereString(I, IC);
		}

		/* Se I NAO esta no dicionario, ele eh inserido no dicionario, sua posicao eh escrita no
		   arquivo de saida e I eh "zerado" */
		else {
			insereNoDicionario(dic, IC);
			// fprintf(saida, "%s nao esta no dicionario\n", IC);
			// fprintf(saida, "%s ", I);
			fprintf(saida, "%d ", posicaoNoDicionario(dic, I));
			// fprintf(saida, "%s\n", I);
			for (i = 0; i < 256; i++) {
				I[i] = '\0';
			}
			I[0] = c;
			// fseek(entrada, -sizeof(char), SEEK_CUR);
		}
	}
	// fprintf(saida, "%d ", posicaoNoDicionario(dic, I));
	// fprintf(saida, "%s\n", I);
	rewind(entrada);
	rewind(saida);
}

/* Igual a funcao estaNoDicionario, mas analiza o codigo da string, e nao a string em si */
int intEstaNoDicionario (int codigo, Dicionario dic) {
	if (tam < codigo)
		return 0;
	return 1;
}

/* Funcao de descompressao */
/* entrada vai ser o arquivo intermediario e saida o arquivo descomprimido */
void desLZW (FILE *entrada, FILE *saida, Dicionario dic) {

	/* neu eh o pedaco do texto que esta sendo tratado agora e aux eh apenas um vetor auxiliar
	   para guardar o valor de neu + palavra[0] */
	char aux[4096];
	char neu[4096];

	/* palavra eh a palavra que esta em dic[codigo] */
	String palavra = (String)malloc(sizeof(char)*1048576);
	char c;
	int i;

	/* codigo eh o codigo que esta sendo analizado no arquivo intermediario */
	int codigo;

	for (i = 0; i < 256; i++) {
		aux[i] = '\0';
		neu[i] = '\0';
	}

	/* A funcao eh executada ate encontrar o fim do arquivo */
	while (!feof(entrada)) {
		fscanf(entrada, "%d", &codigo);
		if (intEstaNoDicionario(codigo, dic)) {
			// palavra = (String)realloc(palavra, sizeof(palavra) + sizeof(char));
			palavra = dic[codigo];
			fprintf(saida, "%s", palavra);
			for (i = 0; i < 4096; i++)
				aux[i] = neu[i];
			for (i = 0; aux[i] != '\0'; i++);
			aux[i] = palavra[0];
			aux[i+1] = '\0';
			insereNoDicionario(dic, aux);
		}
		else {
			for (i = 0; i < 4096; i++)
				palavra[i] = neu[i];
			palavra[i] = neu[0];
			fprintf(saida, "%s", palavra);
		}
		for (i = 0; i < 4096; i++)
			neu[i] = palavra[i];
	}
	rewind(entrada);
	rewind(saida);
}

int main (int argc, char *argv[]) {
	int i, op;
	char lixo;
	FILE *entrada;
	FILE *intermediario;
	FILE *saida;
	Dicionario dic;

	/* Checa se o programa esta sendo executado da maneira certa.
		 Caso nao esteja, ele e abortado */
	if (argc != 4) {
		printf("Por favor, execute o programa na forma:\n");
		printf("$ ./LZW <arquivo de entrada> <arquivo intermediario> <arquivo de saida>\n");
		return -1;
	}
	else {
		/* Inicializa os arquivos de texto, onde:
		   entrada e o arquivo onde esta o texto a ser comprimido
			 intermediario e o arquivo onde esta o codigo ascii do texto "entrada" apos ser comprimido
			 saida e o arquivo onde ficara o texto descompactado a partir de "intermediario" */
		entrada = fopen(argv[1], "r");
		intermediario = fopen(argv[2], "w+");
		saida = fopen(argv[3], "w+");

		dic = inicializaDicionario();
		// imprimeMenu();

		LZW(entrada, intermediario, dic);
		printf("%s foi compactado em %s\n", argv[1], argv[2]);
		desLZW(intermediario, saida, dic);
		printf("%s foi descompactado em %s\n", argv[2], argv[3]);

		/* Mostra o menu para o usuario e pergunta quais operacoes ele quer realizar
		   Esse loop de escolher opcoes se mantem ate o usuario entrar com 0 e abortar o programa */
		/* scanf("%d", &op);
		lixo = getchar();
		while (op != 0) {
			if (op == 1) {
				LZW(entrada, intermediario, dic);
				imprimeMenu();
				printf("%s foi compactado.\n", argv[1]);
				// imprimeDicionario(dic);
				scanf("%d", &op);
				lixo = getchar();
			}
			else {
				if (op == 2) {
					desLZW(intermediario, saida, dic);
					imprimeMenu();
					printf("%s foi descompactado.\n", argv[2]);
					scanf("%d", &op);
					lixo = getchar();
				}
				else {
					imprimeMenu();
					printf("Comando invalido.\n");
					scanf("%d", &op);
					lixo = getchar();
				}
			}
		}
		printf("Programa encerrado.\n"); */
	}
	fclose(entrada);
	fclose(intermediario);
	fclose(saida);
}