#include "huffman.h"

huffman::huffman()
{
	m_ht = NULL;
	m_hcd = NULL;
}

huffman::~huffman()
{
	if (m_ht != NULL)
	{
		delete m_ht;
	}

	if (m_hcd != NULL)
	{
		delete m_hcd;
	}
}

void huffman::getdata()  
{
  int i;

  cout << "輸入需要編碼的字符個(gè)數(shù):";
  cin >> m_num; 

  m_ht = new huffnode[2 * m_num];

  for (i=1; i<=m_num; i++)
  {    
 	cout << "輸入第" << i << "個(gè)字符和它的權(quán)值:";
	cin >> m_ht[i].data >> m_ht[i].weight;   
  } 
}

void huffman::createhfmtree()  
{
  int i, k, x1, x2, m1, m2;  /* m1為最小權(quán)值，x1為其在ht中的下標(biāo)；m2為第二小權(quán)值，x2為其下標(biāo) */
 
  for (i=1; i<=2*m_num-1; i++)
  {
	  m_ht[i].parent = m_ht[i].left = m_ht[i].right = 0;  /* 對(duì)ht的parent，left，right域進(jìn)行初始化 */
  }

  for (i=m_num+1; i<=2*m_num-1; i++)
  {
     m1 = m2 = 10000;                   /* m1，m2初值無限大 */
     x1 = x2 = 0;                       /* x1, x2初值為0 */

     for (k=1; k<=i-1; k++)             /* k為可以進(jìn)行比較的結(jié)點(diǎn)的下標(biāo) */
	 {
		 if (m_ht[k].parent == NULL) 	/* 當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)不存在時(shí) */
		 {
			 if (m_ht[k].weight < m1)   /* 當(dāng)前結(jié)點(diǎn)的權(quán)值比最小權(quán)值還小時(shí) */
			 {
				 m2 = m1;
				 x2 = x1;
				 m1 = m_ht[k].weight;
				 x1 = k;
			 }
			 else if (m_ht[k].weight < m2)    /* 當(dāng)前結(jié)點(diǎn)的權(quán)值比最小權(quán)值大但比第二小權(quán)值大時(shí) */
			 {
				 m2 = m_ht[k].weight;
				 x2 = k;
			 }
		 }
	 }

     m_ht[x1].parent = i;
     m_ht[x2].parent = i;
     m_ht[i].weight = m_ht[x1].weight + m_ht[x2].weight;
     m_ht[i].left = x1;
     m_ht[i].right = x2;
  }
}

void huffman::disphfcode()  
{
  huffcode d;
  int i,c,f,x,k;

  m_hcd = new huffcode[m_num+1];

  
  for (i=1; i<=m_num; i++)
  {
    d.start = m_num + 1;        /* d.start為棧頂 */
    c = i;                      /* c存放當(dāng)前結(jié)點(diǎn) */
    f = m_ht[i].parent;         /* f存放當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn) */

    while (f != 0)
    {
      if (m_ht[f].left == c)    /* 若當(dāng)前結(jié)點(diǎn)在其父結(jié)點(diǎn)的左邊時(shí) */
	  {
		  d.cd[--d.start] = '0';
	  }
      else
	  {
		  d.cd[--d.start] = '1'; /* 當(dāng)前結(jié)點(diǎn)在其父結(jié)點(diǎn)的右邊時(shí) */
	  }

      c = f;                     /*  當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)賦予c */
      f = m_ht[f].parent;        /* c的父結(jié)點(diǎn)賦予f */
    }

    m_hcd[i] = d;  
  } 
  
  cout << "各字符的human編碼如下" << endl;
  
  for(i=1; i<=m_num; i++)  
  {
    cout << m_ht[i].data <<":";
    x = m_hcd[i].start;

	for(k=x; k<=m_num; k++)      /* 通過棧輸出哈夫曼編碼 */
	{
	   cout << m_hcd[i].cd[k];
	}

	cout << endl;    
  } 
}

void huffman::coding() 
{
  int i,j,n,k,x;
  char string[maxleng];

  cout << "輸入要編碼的字符串：";
  cin >> string;  
  n = strlen(string);

  cout << "字符串" << string << "的編碼是：";

  for(i=0; i<n; i++)
  {
    for(j=1; j<=m_num; j++)  
	{
		if(string[i] == m_ht[j].data)  /* 若輸入字符和一個(gè)帶權(quán)結(jié)點(diǎn)相同 */
		{
			x = m_hcd[j].start;

			for(k=x; k<=m_num; k++)
			{
				cout << m_hcd[j].cd[k];
			}
		}
	}
  }

  cout << endl;
}

void huffman::decoding() 
{
  int i,j,n,k,x,w;
  char string[maxleng];
  i=0;                                   /* i為string數(shù)組的下標(biāo) */
  
  cout << "輸入要解碼的字符串：";
  cin >> string;  
  n=strlen(string);

  cout << "字符串" << string << "的解碼是:";
  
  while(i<n)
  {
    for(j=1; j<=m_num; j++)  
      {
        x=m_hcd[j].start;

        for(k=x,w=i; k<=m_num; k++,w++)   /* k為m_hcd[j].cd[]的下標(biāo) */
		{
			if(string[w] != m_hcd[j].cd[k])
			{
				break;
			}
		}

		if(k > m_num)
        {
			cout << m_ht[j].data;             
	     	break;
		}
      }

    i = w;
  }  
  cout << endl;
}