#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 new_node(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(new_node(freq[i], i, 0, 0));

    while (k_koniec > 2)
        k_dodaj(new_node(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)
{
    int a;
    puts("----- KOMPRESJA HUFFMANA -----");

    char str[2048] = { 0 }, buf[1024];
    printf("Podaj tekst: ");
    scanf(" %[^\n]s", str);

    puts("Kodowanie: 1");
    puts("Dekodowanie: 2");
    scanf("%d", &a);

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

    if(a==1)
    {
        kodowanie1(str, buf);
        printf("zakodowane: %s\n", buf);
        dekodowanie(buf, q[1]);
    }

    if(a==2)
    {
        kodowanie1(str, buf);
        printf("odkodowane: ");
        dekodowanie(buf, q[1]);
    }

    return 0;
}