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


#define MAX_CHARS    256



typedef struct btNode
{
    struct btNode *parent;

    struct btNode *left,
                  *right;

    char ch;
    int freq;
} binTree;


typedef struct node
{
    struct node *next;

    binTree *root;
} listRootNodes;


typedef struct chElement
{
    char ch;
    char *code;

    binTree *node;

    int freq;
} chArrayElement;


listRootNodes *firstRootNode,
              *lastRootNode;

chArrayElement chArray[MAX_CHARS];


int numChArrayElements;
int textLen;






void _Init
   (
   )

{
    firstRootNode=NULL;
    lastRootNode =NULL;

    numChArrayElements=0;
}


binTree *_AllocBTNode
   (
    binTree *parent,
    char ch,
    int freq
   )

{
    binTree *cBTNode;


    cBTNode=(binTree *)malloc(sizeof(binTree));

    cBTNode->parent=parent;

    cBTNode->left =NULL;
    cBTNode->right=NULL;

    cBTNode->ch  =ch;
    cBTNode->freq=freq;


    return(cBTNode);
}



binTree *_NewBTNode
   (
    binTree **root,
    binTree *node,
    char ch,
    int freq
   )

{
    binTree *cBTNode;


    if (!(*root))
    {
        (*root)=_AllocBTNode(NULL,ch,freq);


        return(*root);
    }
    else
    if (freq<node->freq)
    {
        if (node->left)
        {
            return(_NewBTNode(root,node->left,ch,freq));
        }
        else
        {
            cBTNode=_AllocBTNode(node,ch,freq);

            node->left=cBTNode;


            return(cBTNode);
        }
    }
    else
    {
        if (node->right)
        {
            return(_NewBTNode(root,node->right,ch,freq));
        }
        else
        {
            cBTNode=_AllocBTNode(node,ch,freq);

            node->right=cBTNode;


            return(cBTNode);
        }
    }
}




listRootNodes *_NewListNode
   (
   )

{
    listRootNodes *cNode;


    if (!firstRootNode)
    {
        firstRootNode=(listRootNodes *)malloc(sizeof(listRootNodes));

        firstRootNode->next=NULL;
        cNode=firstRootNode;
    }
    else
    {
        cNode=(listRootNodes *)malloc(sizeof(listRootNodes));

        cNode->next=NULL;
        lastRootNode->next=cNode;
    }

    lastRootNode=cNode;


    return(cNode);
}


int _DeleteListNode
   (
    listRootNodes *node
   )

{
    listRootNodes *prevNode;


    if (!node)
    {
        return(0);
    }

    if (node==firstRootNode)
    {
        firstRootNode=firstRootNode->next;

        free(node);
    }
    else
    {
        prevNode=firstRootNode;

        while (prevNode)
        {
            if (prevNode->next==node)
            {
                break;
            }

            prevNode=prevNode->next;
        }

        if (!prevNode)
        {
            return(0);
        }

        prevNode->next=node->next;

        if (node==lastRootNode)
        {
            lastRootNode=prevNode;
        }

        free(node);
    }


    return(1);
}



void _FreeList
   (
   )

{
    while (firstRootNode)
    {
        lastRootNode=firstRootNode->next;

        free(firstRootNode);

        firstRootNode=lastRootNode;
    }

    firstRootNode=NULL;
    lastRootNode =NULL;
}



void _DeleteAllBTNodes
   (
    binTree *root,
    binTree *node
   )

{
    binTree *cNode;


    if (!root)
    {
        return;
    }

    if (
        (!node->left)&&
        (!node->right)
       )
    {
        cNode=node;

        free(node);

        if (cNode==root)
        {
            root=NULL;
        }
    }
    else
    {
        if (node->left)
        {
            _DeleteAllBTNodes(root,node->left);

            node->left=NULL;
        }

        if (node->right)
        {
            _DeleteAllBTNodes(root,node->right);

            node->right=NULL;
        }
    }
}



int _GetBTNodeKeyDepth
   (
    binTree *node,
    char ch,
    int depth
   )

{
    int retLeft,retRight;


    if (!node)
    {
        return(-1);
    }

    if (node->ch==ch)
    {
        return(depth);
    }
    else
    {
        retLeft =-1;
        retRight=-1;

        if (node->left)
        {
            retLeft=_GetBTNodeKeyDepth(node->left,ch,depth+1);
        }

        if (node->right)
        {
            retRight=_GetBTNodeKeyDepth(node->right,ch,depth+1);
        }

        if (retLeft!=-1)
        {
            return(retLeft);
        }
        else
        {
            return(retRight);
        }
    }


    return(-1);
}



void _PrintTree
   (
    binTree *root,
    binTree *node,
    int level,
    int brachType
   )

{
    int i,len;
    binTree *tNode;


    if (!node)
    {
        return;
    }


    printf("\n");

    for (i=0; i<level; i++)
    {
        printf("\t");
    }


    if (node==root)
    {
        printf("Radacina (%c,%d)",node->ch,node->freq);
    }
    else
    {
        if (!brachType)
        {
            printf("Fiu stang (%c,%d)",node->ch,node->freq);
        }
        else
        {
            printf("Fiu drept (%c,%d)",node->ch,node->freq);
        }
    }

    if (node->left)
    {
        _PrintTree(root,node->left,level+1,0);
    }

    if (node->right)
    {
        _PrintTree(root,node->right,level+1,1);
    }
}


int _TryInsertCh
   (
    char ch
   )

{
    int i;


    for (i=0; i<numChArrayElements; i++)
    {
        if (chArray[i].ch==ch)
        {
            chArray[i].freq++;


            return(1);
        }
    }


    chArray[numChArrayElements].ch=ch;
    chArray[numChArrayElements].freq=1;
    chArray[numChArrayElements].code=NULL;

    numChArrayElements++;


    return(0);
}


void _ReadList
   (
   )

{
    char str[MAX_CHARS+1];
    int i;
    listRootNodes *cNode;


    printf("\n\nDati stringul: ");
    fgets(str,MAX_CHARS,stdin);
    str[MAX_CHARS]='\0';

    str[strchr(str,'\n')-str]='\0';

    textLen=strlen(str);

    for (i=0; i<textLen; i++)
    {
        _TryInsertCh(str[i]);
    }


    for (i=0; i<numChArrayElements; i++)
    {
        cNode=_NewListNode();

        cNode->root=NULL;
        cNode->root=_NewBTNode(&cNode->root,NULL,chArray[i].ch,chArray[i].freq);

        chArray[i].node=cNode->root;
    }
}


void _Replace2Chars
   (
   )

{
    int minFreq;
    listRootNodes *cNode,*minNode1,*minNode2;
    binTree *cBTNode;


    if (firstRootNode==lastRootNode)
    {
        return;
    }

    cNode=firstRootNode;

    minFreq=cNode->root->freq;
    minNode1=cNode;

    cNode=cNode->next;

    while (cNode)
    {
        if (cNode->root->freq<minFreq)
        {
            minFreq=cNode->root->freq;
            minNode1=cNode;
        }

        cNode=cNode->next;
    }


    ////
    cNode=firstRootNode;

    if (cNode==minNode1)
    {
        cNode=cNode->next;
    }

    minFreq=cNode->root->freq;
    minNode2=cNode;

    cNode=cNode->next;

    while (cNode)
    {
        if (cNode==minNode1)
        {
            cNode=cNode->next;

            continue;
        }

        if (cNode->root->freq<minFreq)
        {
            minFreq=cNode->root->freq;
            minNode2=cNode;
        }

        cNode=cNode->next;
    }


    ////
    cBTNode=_AllocBTNode(NULL,'X',minNode1->root->freq+minNode2->root->freq);

    if (minNode1->root->freq<minNode2->root->freq)
    {
        cBTNode->left =minNode1->root;
        cBTNode->right=minNode2->root;
    }
    else
    {
        cBTNode->left =minNode2->root;
        cBTNode->right=minNode1->root;
    }

    minNode1->root->parent=cBTNode;
    minNode2->root->parent=cBTNode;

    minNode1->root=cBTNode;

    _DeleteListNode(minNode2);

    _Replace2Chars();
}


void _BuildCodes
   (
   )

{
    int i,len,count;
    binTree *pNode,*node;


    for (i=0; i<numChArrayElements; i++)
    {
        len=_GetBTNodeKeyDepth(firstRootNode->root,chArray[i].ch,0);

        chArray[i].code=(char *)malloc(len+1);
        chArray[i].code[len]='\0';

        node=chArray[i].node;

        count=0;

        do
        {
            pNode=node->parent;

            if (!pNode)
            {
                break;
            }

            if (pNode->left==node)
            {
                chArray[i].code[len-1-count]='0';
            }
            else
            {
                chArray[i].code[len-1-count]='1';
            }

            node=pNode;

            count++;
        }
        while (1);
    }
}


void _PrintCodeFreqTable
   (
   )

{
    int i;


    printf("\n\nTabel de coduri Huffmann: ");

    for (i=0; i<numChArrayElements; i++)
    {
        printf("\nCaracter: %c   Frecventa: %d  Cod: %s",chArray[i].ch,chArray[i].freq,chArray[i].code);
    }
}


void _PrintNeededBits
   (
   )

{
    int i,sum;


    sum=0;

    for (i=0; i<numChArrayElements; i++)
    {
        sum+=chArray[i].freq*strlen(chArray[i].code);
    }

    printf("\n\nStringul dat necesita %d biti (%d bytes) pentru a fi stocat + marimea tabelului de coduri!..in comparatie cu %d bits (%d bytes).\nProcent de compresie aprox: %.2f%%",sum,(sum+7)>>3,textLen<<3,textLen,(float)sum*100/(textLen<<3));
}




int main
   (
    int argc,
    char **argv
   )
{
    _Init();
    _ReadList();

    _Replace2Chars();

    _PrintTree(firstRootNode->root,firstRootNode->root,0,-1);
    _BuildCodes();
    _PrintCodeFreqTable();
    _PrintNeededBits();

    _DeleteAllBTNodes(firstRootNode->root,firstRootNode->root);
    _FreeList();


    getch();

    return(0);
}