#include<iostream>
#include<fstream>
#include<string>
using namespace std;
const int defaultsize =256;
struct bintreenode
{
	bintreenode(){leftchild =NULL;rightchild=NULL;}
	bintreenode(char item,bintreenode*left=NULL,bintreenode*right=NULL)
	{
		data=item;
		leftchild=left;
		rightchild=right;
	}
	char data;  //字符
	int lengthofmark;//編碼碼長
    string mark;//字符編碼
	bintreenode *leftchild,*rightchild,*parent;
};
class bintree
{
public:
		bintreenode*root;
	    bintree(){root=NULL;}
		~bintree(){}
		int isempty()const {return root==NULL;}
		bintreenode* maketree(const char &item,bintree&left,bintree&right);
		bintreenode*parent(bintreenode*start,bintreenode*current);
		void preorder();
private:
      void preorder(bintreenode*current);
};
////////////////////////////////////////////////////////////
bintreenode*bintree::parent(bintreenode*start,bintreenode*current)
{
	if(start==NULL)return NULL;
	if(start->leftchild==current||start->rightchild==current)return start;
	bintreenode*p;
	if((p=parent(start->leftchild,current))!=NULL)return p;
	else return parent(start->rightchild,current);
}
bintreenode*bintree::maketree(const char&item,bintree&left,bintree&right)
{
	root=new bintreenode(item,left.root,right.root);
	left.root=right.root=NULL;
	return root;
}
void bintree:: preorder()
{
	preorder(root);                                                                                                        
}
void bintree::preorder(bintreenode*current)
{
	if(current!=NULL)
	{
		cout<<current->data<<"**"<<endl;
	   preorder(current->leftchild);
	   preorder(current->rightchild);
	}
}
//////////////////////////////////////////////////////////////
struct huffman
{
	bintree tree;
	int weight;//權(quán)值
};
class minheap
{
public:
     minheap(int maxsize=defaultsize);
	 minheap(huffman arr[],int n);
	 ~minheap(){delete[]heap;}
	 int insert(const huffman&x);
	 huffman removemin(huffman&x);
	 int isempty()const{return currentsize==0;}
	 int isfull()const{return currentsize==maxheapsize;}
	 huffman getheap(int i){return heap[i];}
private:
	  huffman*heap;
	  int currentsize;
	  int maxheapsize;
	  void filterdown(int i,int m);
	  void filterup(int i);
};
minheap::minheap(int maxsize)
{
	maxheapsize=defaultsize<maxsize?maxsize:defaultsize;
	heap=new huffman[maxheapsize];
    currentsize=0;
}
minheap::minheap(huffman arr[],int n)
{
   maxheapsize=n;
   heap=new huffman[n];
   currentsize=n;
   for(int i=0;i<currentsize;i++)
	   {
	      heap[i].weight=arr[i].weight;
		  heap[i].tree=arr[i].tree;
   }
   int currentpos=(currentsize-2)/2;
   while(currentpos>=0)
   { 
	   filterdown(currentpos,currentsize-1);
	   currentpos--;
   }
}
void minheap::filterdown(const int start ,const int endofheap)
{
	int i=start,j=2*i+1;
	huffman temp=heap[i];
	while(j<=endofheap)
	{
		if(j<endofheap&&heap[j].weight>heap[j+1].weight)j++;
		if(temp.weight<=heap[j].weight)break;
		else 
		{
			heap[i].weight=heap[j].weight;
			heap[i].tree=heap[j].tree;
			i=j;
			j=2*j+1;
		}
	}
		heap[i].weight=temp.weight;
		heap[i].tree=temp.tree;
}
void minheap::filterup(int start)
{
	int j=start,i=(j-1)/2;
	huffman temp=heap[j];
	while(j>0)
	{
		if(heap[i].weight<=temp.weight)break;
		else 
		{
			heap[j].weight=heap[i].weight;
			heap[j].tree=heap[i].tree;
			j=i;
			i=(i-1)/2;
		}
	}
	heap[j].weight=temp.weight;
	heap[j].tree=temp.tree;
}
int minheap::insert(const huffman&x)
{
	if(isfull()){cerr<<"heap full"<<endl;return 0;}
	heap[currentsize]=x;
	filterup(currentsize);
	currentsize++;
	return 1;
}
huffman minheap::removemin(huffman&x)
{
	if(isempty()){cerr<<"heap empty"<<endl;}
	x=heap[0];
	heap[0]=heap[currentsize-1];
	currentsize--;
	if(currentsize==0)filterdown(0,0);
 else if(currentsize>0)
	filterdown(0,currentsize-1);
	return x;
}
////////////////////////////////////////////////////
class compress
{
public:
	compress(){NOofchar=0;}
	void readfile(string filename);
	char*getdata(){return data;}//得到所有的字符
	char getcertaindata(int i);//得到數(shù)組元素第i個元素所對應(yīng)的字符
	int*getfrequence(){return frequence;}//得到所有字符的權(quán)值
	int getNOofchar(){return NOofchar;}//字符的個數(shù)
	int getNOofcertainchar(int i);//第i個元素所對應(yīng)的字符的個數(shù)
private:
	char data[256];//字符
    int frequence[256];//權(quán)值
	int NOofchar;
};
int total;
char compress::getcertaindata(int i)
{
	if(i>=0&&i< NOofchar)
		return data[i];
	return '/';
}
int compress::getNOofcertainchar(int i)
{
	if(i>=0&&i< NOofchar)
		return frequence[i];
	return 0;
}
//////////////////////////////////////////////////////////
/*readfile這個函數(shù)的作用是通過掃描文件近而統(tǒng)計字符的種類個數(shù)和權(quán)值，由于是以二進制的形式打開文件
因此字符的種類個數(shù)和權(quán)值個數(shù)最多有256個
*/
void compress::readfile(string filename)
{
   ifstream in;
	in.open(filename.c_str(),ios::binary);
     if (!in.is_open())
	{
    	cerr<<"couldn't open the file"<<endl;
	}
	int i=0,j;	char ch;
loop: while(in.read(&ch, sizeof(char)))
	{
        total++;
		for(j=0;j<i;j++)
		{
			if(ch == data[j])
			{
				frequence[j]++;	
				goto loop;
			}
		}
		   data[i] = ch;
		   frequence[i] = 1;
		 i++;
	 }
	  NOofchar=i;
	in.close();
}
///////////////////////////////////////////////////////
class edithuffman
{
friend class minheap;
public:
	edithuffman(){Frequence=0;}
    ~edithuffman(){delete []w;}
    void huffmantree(int *arr,int n,char* b);//建一棵霍夫曼樹
	void code();//霍夫曼樹的編碼工作
    void print();//完成打印工作
	void encompress(string oldfilename,string newfilename);//完成壓縮功能
	void dcompress(string oldfilename,string newfilename);//完成解壓縮功能
private:
	int Frequence,len;
	huffman x,y;
	bintree z,zero;
    huffman*w;
	void print(huffman &h);//完成打印工作
	void codehuffman(bintreenode *current,bintreenode*end,string &m,int &no);//霍夫曼樹的編碼工作
    unsigned long string_to_long(string str);
};
//////////////////////////////////////////////////////
void edithuffman::huffmantree(int *arr,int n,char* b)
{
	int i;
	w=new huffman[Frequence=n];
	for(i=0;i<Frequence;i++)
	{
		z.maketree(b[i],zero,zero);
		w[i].weight=arr[i];
		w[i].tree=z;
	}
   minheap h(w,Frequence);
	bintreenode *t1,*t2;
    for(i=0;i<Frequence-1;i++)
	{
		h.removemin(x);	
		t1=x.tree.root;
	    h.removemin(y);
		t2=y.tree.root;
        z.maketree(0,x.tree,y.tree);
        x.weight+=y.weight;
		x.tree=z;
		h.insert(x);
		t1->parent=x.tree.root;
		t2->parent=x.tree.root;
	}
	h.removemin(x);
	  code();
}
///////////////////////////////////////////////
void edithuffman::code()
{
	for(int i=0;i<Frequence;i++)
	  codehuffman(w[i].tree.root,x.tree.root,w[i].tree.root->mark,w[i].tree.root->lengthofmark);
//	print();
}
void edithuffman::codehuffman(bintreenode *current,bintreenode*end,string &m,int &no)
{  
   char *u;
	string str;
    int i;
	no=2;
	while(current->parent!=NULL)
	 {
		 if( current->parent->leftchild==current)
		  u="0";
	     else if(current->parent->rightchild==current)
		  u="1";
		  current=current->parent;
		  str+=u;
		 if(current==end)break;
			no++;
	 }
	const char*h=str.c_str();
	 for(i=str.length()-1;i>=0;i--) m=m+h[i];
}
/////////////////////////////////////////////////
void edithuffman::print(huffman &h)
{ 
	cout<<h.weight<<"**"<<h.tree.root->data<<"**"<<h.tree.root->mark<<"**"<<h.tree.root->lengthofmark<<"**"<<endl;;
}
void edithuffman::print()
{
  for(int i=0;i<Frequence;i++)print(w[i]);
}
///////////////////////////////////////////////
unsigned long edithuffman::string_to_long(string str)
{
	const char*code=str.c_str();
	unsigned long ret = 0;
	int len = (int)strlen(code);
	for(int i = len - 1; i >= 0; i--)
		if (code[i] == '1')
			ret |= (1ul << (len - i - 1));
	return ret;
}
/////////////////////////////////////////////////////////
void edithuffman::encompress(string oldfilename,string newfilename)
{
	ifstream in;
	ofstream out;
	compress temp;
	char ch,d,t;
	int D,i;
   unsigned long key;
	 string k,m;
	 cout<<"COMPRES"<<endl;
	in.open(oldfilename.c_str(),ios::binary);
	out.open(newfilename.c_str(),ios::binary);
	temp.readfile(oldfilename);
	huffmantree(temp.getfrequence(),temp.getNOofchar(),temp.getdata());
    for(int q=0;q<Frequence;q++)
	  {
         d= temp.getcertaindata(q);
		 D=temp.getNOofcertainchar(q);
		 out.write((char*)&d,sizeof(char));
		 out.write((char*)&D,sizeof(unsigned int ));
	  }
	  while(in.read(&ch, sizeof(char)))
	  { 
		  for(i=0;i<Frequence;i++)
			  if(ch==w[i].tree.root->data)k=k+w[i].tree.root->mark;
            if(k.length()<8)continue;
			else
			{
				m = k.substr(0, 8);
                k.erase(0, 8);
	           key=string_to_long(m);
		       t=char(key);
		      out.write(&t,sizeof(char));
			}
	  }
      if(k.length()<8)
	  {
		   len=8-k.length();
		  switch (k.length())
		 {
	       case 1 : k+="0000000"; break;
	       case 2 : k+="000000"; break;
	       case 3 : k+="00000"; break;
	       case 4 : k+="0000"; break;
	       case 5 : k+="000"; break;
	       case 6 : k+="00"; break;
	       case 7 : k+="0"; break;
	       default : break;
		}
	  }
   key=string_to_long(k);
   t=char(key);
  out.write(&t,sizeof(char));
    in.close();
	out.close();
}
void edithuffman::dcompress(string oldfilename,string newfilename)
{
  	ifstream in;
	ofstream out;
	in.open(oldfilename.c_str(),ios::binary);
    char t,ch,store[8],te;
	int i,fre,count=0;
	string temp,m;
	int *cart=new int[Frequence];
	char*dd=new char[Frequence];
	cout<<"DEPRESS"<<endl;
	for ( i = 0; i < Frequence; i++ )
	{
		in.read((char*)&t,sizeof(char));
		dd[i]= t;
		in.read((char*)&fre,4);
		cart[i]= fre;
	}
	out.open(newfilename.c_str(),ios::binary);
	huffmantree(cart,Frequence,dd);
	bintreenode *current=x.tree.root;
loop: while(in.read(&ch, sizeof(char)))
	{
	   for ( int i = 0 ; i < 8 ; i++ )
	   {
			if ( ch & 128 ){ te = '1'; }
			else { te = '0'; }
			ch = ch << 1;
			store [ i ] = te;
		}
	 temp=store;
	   while(current!=NULL)
	   {
         if(count==total)break;
		   if(temp.length()>0)
		   {
		      m=temp.substr(0,1);
			  if(m=="0")
			  current=current->leftchild;
		     else if(m=="1")
			  current=current->rightchild; 
		       temp=temp.erase(0, 1);
			   if(current->data==0)continue;
              else if(current->data!=0)
			  {
				  char o=current->data;
				  count++;
				  out.write(&o,sizeof(char));
				  current=x.tree.root;
			      if(temp.length()>0)continue;
			      else  break;
			  }
		   }
		  else
			  goto loop;
		  }
       }
	in.close();
    out.close();
}
void main()
{
	edithuffman f;
	f.encompress("原始文件.txt","壓縮后的文件.txt");
    f.dcompress("壓縮后的文件.txt","解壓縮文件.txt");

}