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

typedef struct wezel_t {
	struct wezel_t *left, *right;
	int freq;
	char c;
} *wezel;

struct wezel_t pool[256] = {{0}};
wezel kolejka[255], *q = kolejka - 1;
int n_wezly=0, k_koniec=1;
char *code[128] = {0}, buf[1024];

wezel nowy_wezel(int freq, char c, wezel a, wezel b)
{
	wezel n = pool + n_wezly++;
	if (freq) n->c = c, n->freq = freq;
	else {
		n->left = a, n->right = b;
		n->freq = a->freq + b->freq;
	}
	return n;
}

void k_dodaj(wezel n)
{
	int j, i = k_koniec++;
	while ((j = i / 2)) {
		if (q[j]->freq <= n->freq) break;
		q[i] = q[j], i = j;
	}
	q[i] = n;
}

wezel k_usun()
{
	int i, l;
	wezel n = q[i = 1];

	if (k_koniec < 2) return 0;
	k_koniec--;
	while ((l = i * 2) < k_koniec) {
		if (l + 1 < k_koniec && q[l + 1]->freq < q[l]->freq) l++;
		q[i] = q[l], i = l;
	}
	q[i] = q[k_koniec];
	return n;
}

void kodowanie(wezel n, char *s, int len)
{
	static char *out = buf;
	if (n->c) {
		s[len] = 0;
		strcpy(out, s);
		code[n->c] = out;
		out += len + 1;
		return;
	}

	s[len] = '0'; kodowanie(n->left,  s, len + 1);
	s[len] = '1'; kodowanie(n->right, s, len + 1);
}

void start(const char *s)
{
	int i, freq[128] = {0};
	char c[16];

	while (*s) freq[(int)*s++]++;

	for (i = 0; i < 128; i++)
		if (freq[i]) k_dodaj(nowy_wezel(freq[i], i, 0, 0));

	while (k_koniec > 2)
		k_dodaj(nowy_wezel(0, 0, k_usun(), k_usun()));

	kodowanie(q[1], c, 0);
}

void kodowanie1(const char *s, char *out)
{
	while (*s)
    {
		strcpy(out, code[*s]);
		out += strlen(code[*s++]);
	}
}

void dekodowanie(const char *s, wezel t)
{
	wezel n = t;
	while (*s) {
		if (*s++ == '0') n = n->left;
		else n = n->right;

		if (n->c) putchar(n->c), n = t;
	}

	putchar('\n');
	if (t != n) printf("zle dane\n");
}

int main(void)
{
	const char *str = "nasz tekst", buf[1024];

	start(str);
	for (int i = 0; i < 128; i++)
		if (code[i]) printf("%c: %s\n", i, code[i]);

		kodowanie1(str, buf);
	printf("zakodowane: %s\n", buf);

	printf("odkodowane: ");
    dekodowanie(buf, q[1]);

	return 0;
}