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

#define MAX 128

// poredimo dva karaktera
int cmp_chars(const void* first, const void* second)
{
	char f = *(char*)first;
	char s = *(char*)second;

	return f-s;
}

// levi i desni polja sadrze NULL akko je cvor list
typedef struct cvor{
	unsigned cnt;
	char* ch;
	struct cvor* levi;
	struct cvor* desni;
} cvor;

// pomocna funkcija za pravljenje cvora od podataka
cvor* make_cvor(unsigned cnt, char* ch, cvor* levi, cvor* desni)
{
	cvor* n = (cvor*)malloc(sizeof(cvor));
	if(!n)
	{
		perror("malloc: ");
		exit(EXIT_FAILURE);
	}

	n->levi = levi;
	n->desni = desni;
	n->ch = ch;
	n->cnt = cnt;

	return n;
}

// sortiramo sve karaktere tako da su jednaki jedan do drugog
char* sort_chars(const char* s)
{
	char *string;
	string = (char*)malloc(strlen(s)+1);
	if(!string)
	{
		printf("4\n");
		perror("malloc: ");
		exit(EXIT_FAILURE);
	}
	strcpy(string, s);
	qsort(string, strlen(string), sizeof(char), cmp_chars);
	return string;
}

// brojimo sva slova u niski i pravimo niz pokazivaca na cvor duzine len za svako od razlicitih slova u niski s
cvor** count_all(const char* s, int* len)
{
	// sort the string, qsort
	
	char *string = sort_chars(s);
	
	cvor** arr;
	
	// count each symbol
	arr = (cvor**)malloc(sizeof(cvor*)*strlen(string));
	if(!arr)
	{
		printf("3\n");
		perror("malloc: ");
		exit(EXIT_FAILURE);
	}

	int i = -1, cnt = 0;
	char* c = string;
	char prev = -1;

	while(*c)
	{	
		// ako je trenutni simbol razlicit od prethodnog, pravimo novi element niza
		// na sledecoj poziciji
		cnt++;
		if(*c != prev)
		{
			char *tmp_ch = (char*)malloc(2);
			tmp_ch[0] = *c;
			tmp_ch[1] = 0;
			arr[++i] = make_cvor(1, tmp_ch, NULL, NULL);
			prev = *c;
			c++;	
		}
		else // inace je prethodni simbol jednak trenutnom pa samo uvecavamo broj
		{
			arr[i]->cnt++;
			c++;
		}
	}
	
	*len = i+1;	
	return arr;
}

// poredimo dva cvora po broju pojavljivanja
int cmp_cvor_r(const void* first, const void* second)
{
	cvor* f = *(cvor**)first;
	cvor* s = *(cvor**)second;

	return (f->cnt)-(s->cnt);
}

// funkcija koja kreira Hafmanovo stablo za dati skup cvorova
cvor* huffman_stablo(cvor** arr, int len)
{
	qsort(arr, len, sizeof(cvor*), cmp_cvor_r);

	if(len < 1)
	{
		fprintf(stderr, "Ne mozemo za manje od 1 elementa!\n");
		exit(EXIT_FAILURE);
	}
	if(len == 1)
	{
		return arr[0];
	}
	else
	{
		char* ch = (char*)malloc(strlen(arr[0]->ch) + strlen(arr[1]->ch));
		strcpy(ch, arr[0]->ch);
		strcat(ch, arr[1]->ch);
		arr[1] = make_cvor(arr[0]->cnt + arr[1]->cnt, ch, arr[0], arr[1]);
		
		return huffman_stablo(arr+1, len-1);
	}

}

// funkcija za obrtanje stringa
char* obrni_string(const char* string)
{
	char* s = (char*)malloc(strlen(string)+1);
	int i;
	if(!s)
	{
		printf("7\n");
		perror("malloc: ");
		exit(EXIT_FAILURE);
	}

	s[strlen(string)] = 0;
	for(i = 0; i < strlen(string); i++)
	{
		s[i] = string[strlen(string) - i - 1];
	}

	return s;
}

// ukoliko smo dosli do lista, upisujemo karakter u karakteri[*indeks], njegov kod u kodovi[*indeks]
// i frekvenciju u frekvencije[*indeks]
void upisi_kodove(cvor* drvo, const char* prefix, char* kodovi[], char karakteri[], int frekvencije[], int* indeks)
{
	if(strlen(drvo->ch) == 1)
	{
		kodovi[*indeks] = obrni_string(prefix);
		karakteri[*indeks] = drvo->ch[0];
		frekvencije[*indeks] = drvo->cnt;
		(*indeks)++;
		return;
	}

	// 1 za terminirajucu nulu i 1 za dodataka
	char* s = malloc(strlen(prefix)+2);
	if(!s)
	{
		printf("6\n");
		perror("malloc: ");
		exit(EXIT_FAILURE);
	}

	s[0] = '0';
	s[1] = 0;
	strcat(s, prefix);
	upisi_kodove(drvo->levi, s, kodovi, karakteri, frekvencije, indeks);

	s[0] = '1';
	s[1] = 0;
	strcat(s, prefix);
	upisi_kodove(drvo->desni, s, kodovi, karakteri, frekvencije, indeks);

	free(s);
}

// rekurzivno oslobadjanje memorije
void free_stablo(cvor* koren)
{

	if(koren)
	{
		free(koren->ch);
		free_stablo(koren->levi);
		free_stablo(koren->desni);
		free(koren);
	}
}

int main(int argc, char* argv[])
{
	cvor **forest;
	cvor* huffman;
	int len, i;
	char* kodovi[MAX];
	char karakteri[MAX];
	int frekvencije[MAX];
	int indeks = 0;
	char* text;	
	int br_bitova;
	int suma_bitova;

	if(argc < 2)
	{
		printf("Nacin koriscenja: ./huffman \"tekst koji zelite da unesete\"");
		exit(EXIT_FAILURE);
	}

	text = argv[1];
	forest = count_all(text, &len);
	br_bitova = (int)ceil(log(len)/log(2));
	suma_bitova = strlen(text)*br_bitova;
	
	printf("Imamo %d razlicitih karaktera u tekstu.\n", len);
	printf("Ukupno nam treba %d bitova pre kompresije!\n", suma_bitova);

	huffman = huffman_stablo(forest, len);
	upisi_kodove(huffman, "", kodovi, karakteri, frekvencije, &indeks);
	printf("Ispis kodova za svaki karakter:\n");
	suma_bitova = 0;
	for(i = 0; i < indeks; i++)
	{	
		suma_bitova += frekvencije[i]*strlen(kodovi[i]);
		printf("%c %s\n", karakteri[i], kodovi[i]);

	}

	printf("Ukupno nam treba %d bitova posle kompresije!\n", suma_bitova);
	free_stablo(huffman);
	return 0;
}