#include "stdio.h"
#include "string.h"
#include "conio.h"
#include "math.h"
#include "malloc.h"

const int SIZE=256;
typedef char* string;
static string Codes[SIZE];

class aTree
{
public:
	aTree* left;
	aTree* right;
	char character;
	char code[SIZE];
	int leaf;  //1 - лист, 0 - ветвь
	long weight;

	aTree()
	{
		this->left=NULL;
		right=NULL;
		leaf=0;
		weight=0;
	};
	~aTree() {};
	aTree(char c, long w, int flag);
	void Traverse(char sh[SIZE]);
};
aTree::aTree(char c, long w, int flag)
{
	*(this->code)='\0';
   this->left=NULL; this->right=NULL;
	this->character=c;
	this->leaf=flag;
	this->weight=w;
};
void aTree::Traverse(char sh[SIZE])
{
	if (this->leaf==1)
   {
		Codes[((int)this->character)-1]=new char[strlen(sh)+1];
      *Codes[((int)this->character)-1]='\0';
   	strcpy(Codes[((int)this->character)-1],sh);
      //*(sh+strlen(sh)-1)='\0';
   }
	if (this->left!=NULL)
   {
		strcat(sh,"0");
   	this->left->Traverse(sh);
      *(sh+strlen(sh)-1)='\0';
   }
	if (this->right!=NULL)
   {
   	this->right->Traverse(strcat(sh,"1"));
      *(sh+strlen(sh)-1)='\0';
   }
}


static aTree* Forest[SIZE];
static long Weights[SIZE];
static char InfoName[200],RName[200],FileName[200];
static long TotalLength=0;


int FindMinTree(int used)
{
	int min=0;
	for (int i=1; i<used; i++)
		if ((*Forest[i]).weight<(*Forest[min]).weight) min=i;
	return min;
};

void GrowTree()
{
	int used=0;
	for (int i=0; i<SIZE; i++)
		if (Weights[i]!=0) Forest[used++]=new aTree(i+1,Weights[i],1);
	while (used>1)
	{
		int min=FindMinTree(used);
		int x=Forest[min]->weight;
		aTree* z=new aTree();
		z->left=Forest[min];
		Forest[min]=Forest[--used]; //??????
		min=FindMinTree(used);
		z->right=Forest[min];
		z->weight=x+Forest[min]->weight;
		Forest[min]=z;
	}
};

void GenerateCodes()
{
	Forest[0]->Traverse("");
};

int  Shyfr(char* FileName)
{
	FILE *src,*dest;
   char *f;
   f=new char[strlen(FileName)+1];
   strcpy(f,FileName);
	src=fopen(f,"r");
  	if (src==NULL)
	{
		printf("File %s not found.\n",FileName);
      getch();
		fclose(src);
		return 1;
	}
	*RName='\0';
	strcpy(RName,FileName);
	char* x=strchr(RName,(int)'.');
	if (x==NULL) strcat(RName,".huf");
	else 
	{
		*(x+1)='h';
		*(x+2)='u';
		*(x+3)='f';
		*(x+4)='\0';
	};
	dest=fopen(RName,"w");
	char rez[200],*str;
	TotalLength=0;
	char word[9]="";
	while (feof(src)==0)
	{
		*rez='\0'; 
		str=(char*)malloc(sizeof(char)*26);
		*str='\0';
		fread(str,sizeof(char),25,src);
		for (int i=0; i<strlen(str); i++)
			strcat(rez,Codes[str[i]]);
		while (strlen(str)>0)
		{
				*word='\0';
				strcpy(word,str);
				TotalLength+=strlen(word);
				str+=strlen(word);//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1
				int d=0;
				for (int k=strlen(word)-1; k>=0; k--)
					if (word[k]=='1') d+=(int)exp((strlen(word)-1-k)*log(2));
				fputc((char)d,dest);
		}
	};
	fclose(src);
	fclose(dest);
	dest=fopen(InfoName,"a");
	if (!dest) { fclose(dest); printf("Can't append info file!/n"); return 1;}
	fwrite(&TotalLength,sizeof(long),1,dest);
	fclose(dest);
	return 0;
}

char *DeShyfr(char* src)
{
	char* rez=NULL;
	return rez;
}

int AnalyzeFile(char* FileName)
{
	FILE* temp;
	temp=fopen(FileName,"r");
	if (temp==NULL)
	{
		printf("File %s not found.\n",FileName);
		fclose(temp);
		return 1;
	}
	for (int i=0; i<SIZE; i++) Weights[i]=0;
	char c;
	while (feof(temp)==0)
	{
		c=fgetc(temp);
		if ((c>0)&&(c<=256))Weights[(int)c-1]+=1;
	}
	fclose(temp);
	//char InfoName[200]="";
	*InfoName='\0';
	strcpy(InfoName,FileName);
	char* x=strchr(InfoName,(int)'.');
	if (x==NULL) strcat(InfoName,".nfo");
	else
	{
		*(x+1)='n';
		*(x+2)='f';
		*(x+3)='o';
		*(x+4)='\0';
	};
	temp=fopen(InfoName,"w");
	if (temp==NULL)
	{
		printf("Info-File was not created.\n");
		fclose(temp);
		return 1;
	}
	fwrite(Weights,sizeof(long),SIZE,temp);
	fclose(temp);
	return 0;
}

int LoadStatistic(char * FileName)
{
	FILE * temp;
	temp=fopen(FileName,"r");
	if (temp==NULL)
	{
		printf("File %s not found.\n",FileName);
		fclose(temp);
		return 1;
	}
	for (int i=0; i<SIZE; i++) Weights[i]=0;
	fread(Weights,sizeof(long),SIZE,temp);
	fread(&TotalLength,sizeof(long),1,temp);
	fclose(temp);
	return 0;
}

int main()
{
	printf("              *************************************\n");
	printf("              ***  Huffman compressing program  ***\n");
	printf("              *************************************\n\n\n");
	char Key=0;
	int f;
	while (Key!=27)
	{
		printf("\n Choose action: \n");
		printf("(1)    Compress file \n");
		printf("(2)    Decompress file \n");
		printf("(Esc)  Exit program \n");
		Key=getch();
		switch (Key)
		{
		case '1':  printf("Enter the path to the object: \n");
				   gets(FileName);
				   f=AnalyzeFile(FileName);
				   if (f!=0) {printf("Error");getch();break;}
				   GrowTree();
				   GenerateCodes();
				   Shyfr(FileName);
				   printf("Compressing accomplished. \n");
				   break;
		case '2':  printf("Enter the path to the object: \n");
				   gets(FileName);
				   f=LoadStatistic(FileName);
				   if (f!=0) {printf("Error");getch();break;}
				   GrowTree();
				   GenerateCodes();
				   DeShyfr(FileName);
				   printf("Decompressing accomplished. \n");
				   break;
		}
	}

	return 0;
}