#include <stdio.h>
#include <string.h>
#define PLIK "kf.txt"

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(int argc, char* argv[])
{
    int i;
    int strsize = 0;
    for (i=1; i<argc; i++)
    {
        strsize += strlen(argv[i]);
        if (argc > i+1)
            strsize++;
    }

    printf("strsize: %d\n", strsize);

    if(strsize == 0)
    {
        puts("brak podanego tesktu");
        return 0;
    }
    char str[2048] = { 0 }, buf[1024] = { 0 };
    str[0] = '\0';

    for (i=1; i<argc; i++)
    {
        strcat(str, argv[i]);
        if (argc > i+1)
            strcat(str, " ");
    }

    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);
    dekodowanie(buf, q[1]);

    return 0;
}