fork(2) download 
  1. #include <map>
  2. #include <string>
  3. #include <vector>
  4. #include <iostream>
  5. #include <fstream>
  6. #include <algorithm>
  7. #include <string.h> 
  8. #include <assert.h>
  9. #include <cstdlib>
  10. #include <stdio.h>
  11. using namespace std;
  12.  
  13. template<typename T>
  14. void pop_front(std::vector<T>& vec)
  15. {
  16.     assert(!vec.empty());
  17.     vec.erase(vec.begin());
  18. }
  19.  
  20. struct cNode
  21. {
  22.     unsigned char ch; // character
  23.     int freq; // freqbability
  24. };
  25.  
  26. struct treeNode: public cNode
  27. {
  28. 	treeNode(){
  29. 		ch = ' ';
  30. 		freq = 0;
  31. 		left = NULL;
  32. 		right = NULL;
  33. 		min = ' ';
  34. 	}
  35. 	char min;
  36.     char lcode;
  37.     char rcode;
  38.     treeNode *left; // left child
  39.     treeNode *right; // right child
  40. };
  41. static int nodeCharCompare(const void *elem1, const void *elem2)
  42. {
  43.     const cNode a = *(cNode*)elem1;
  44.     const cNode b = *(cNode*)elem2;
  45.  
  46.     if (a.ch > b.ch)
  47.         return 1;
  48.     else if(a.ch < b.ch)
  49.         return -1;
  50.     else
  51.         return 0;
  52. }
  53. static int nodeCompare(const void *elem1, const void *elem2)
  54. {
  55.     const cNode a = *(cNode*)elem1;
  56.     const cNode b = *(cNode*)elem2;
  57.  
  58.     if (a.freq > b.freq)
  59.         return 1;
  60.     else if(a.freq < b.freq)
  61.         return -1;
  62.     else
  63.         return 0;
  64. }
  65. bool cmp(treeNode *n1,treeNode* n2){
  66. 	return n1->freq < n2->freq;
  67. }
  68. bool cmpByChar(treeNode *n1,treeNode* n2){
  69. 	return n1->ch < n2->ch;
  70. }
  71. class HCode
  72. {
  73. private:
  74.     int tsize; // table size (number of chars)
  75.     cNode *ptable; // table of freqbabilities
  76.     map<char, string> codes; // codeword for each char
  77.  
  78. public:
  79.     void enCode(const char* inputFilepath, const char* outputFilepath)
  80.     {
  81.         map<char, int> freqs; // frequency for each char from input text
  82.         int i;
  83.  
  84.         // Opening input file
  85.         //
  86.         ifstream inputFile;
  87.         inputFile.open(inputFilepath,std::ifstream::binary | std::ifstream::in);
  88.         if (!inputFile)
  89.         {
  90.             cerr<<"error: unable to open input file: " << inputFilepath <<endl;
  91.         }
  92.         char ch[1]; //char
  93.         unsigned total = 0;
  94.         while (true)
  95.         {
  96.             inputFile.read((char*)ch,sizeof(ch));
  97.             if(inputFile.eof()) 
  98.                 break;
  99.             freqs[ch[0]]++;
  100.             total++;
  101.         }
  102.         tsize = (int)freqs.size();
  103.  
  104.  
  105.         // Building decreasing freqs table
  106.         //
  107.         ptable =new cNode[tsize];
  108.         //assert(ptable);
  109.         float ftot = float(total);
  110.         map<char, int>::iterator fi;
  111.         for (fi = freqs.begin(), i = 0; fi != freqs.end();  ++fi, ++i)
  112.         {
  113.             ptable[i].ch = (*fi).first;
  114.             ptable[i].freq = (*fi).second;
  115.         }
  116.         qsort(ptable, tsize, sizeof(cNode), nodeCompare);
  117.  
  118.         // Encoding
  119.         //
  120.         EncHuffman();
  121.  
  122.         // Opening output file
  123.         //
  124.         ofstream outputFile;
  125.         outputFile.open(outputFilepath, ofstream::out | ofstream::binary);
  126.         if (!outputFile)
  127.         {
  128.             cerr<<"error: unable to open output file: " << outputFilepath <<endl;
  129.         }
  130. 		/*FILE *outputFile;
  131. 		if((outputFile = fopen(outputFilepath,"wb"))==NULL){
  132. 			cout<<"Write file failed.\n";
  133. 			exit(1);
  134. 		}*/
  135.         // Outputing ptable and codes
  136.         //
  137.         std::cout<<endl<<tsize<<endl;
  138.         outputFile<<tsize<<endl;
  139.         for (int i = 0; i < tsize; i++)
  140.         {
  141.             std::cout <<ptable[i].ch<<"\t"<<ptable[i].freq<<"\t"<<codes[ptable[i].ch].c_str()<<endl;
  142.             outputFile<<ptable[i].ch<<"\t"<<ptable[i].freq<<"\t"<<codes[ptable[i].ch].c_str()<<endl;
  143.         }
  144.  
  145.  
  146.         // Outputing encoded text
  147.  
  148.         inputFile.clear();  
  149.         inputFile.seekg(0,inputFile.beg);
  150.         std::cout<<endl;
  151.         outputFile<<endl;
  152.         while (true)
  153.         {
  154.             inputFile.read((char*)ch,sizeof(ch));
  155.             if (inputFile.eof())
  156.                 break;
  157.             std::cout<<codes[ch[0]].c_str();
  158.             outputFile<<codes[ch[0]].c_str();
  159.         }
  160.         std::cout<<endl;
  161.  
  162.         // Cleaning
  163.         //
  164.         codes.clear();
  165.         delete[] ptable;
  166.  
  167.         // Closing files
  168.         //
  169. //        outputFile.close();
  170. //        outputFile.clear();
  171. 		//fclose(outputFile);
  172.         //fclose(file);
  173.         outputFile.close();
  174.         outputFile.clear();
  175.         inputFile.close();
  176.         inputFile.clear();
  177.     }
  178.  
  179.     void Decode(const char* inputFilename, const char* outputFilename)
  180.     {
  181.                 ifstream inputFile;
  182.         inputFile.open(inputFilename,ios::in | ios::binary);
  183.         if (!inputFile)
  184.         {
  185.             cerr<<"error: unable to open input file: " << inputFilename <<endl;
  186.         }
  187.  
  188.         // Loading codes
  189.         //
  190.         inputFile>>tsize;
  191.         char ch, code[128];
  192.         float p;
  193.         int i;
  194.         inputFile.get();
  195.         for (i = 0; i < tsize; i++)
  196.         {
  197.             inputFile.get(ch);
  198.             inputFile>>p>>code;
  199.             codes[ch] = code;
  200.             inputFile.get();
  201.         }
  202.         inputFile.get();
  203.  
  204.         // Opening output file
  205.         //
  206.         ofstream outputFile;
  207.         outputFile.open(outputFilename,ios::out | ios::binary);
  208.         if (!outputFile)
  209.         {
  210.             cerr<<"error: unable to open output file: "<<outputFilename<<endl;
  211.         }
  212.  
  213.  
  214.         // Decoding and outputing to file
  215.         //
  216.         string accum = "";
  217.         map<char, string>::iterator ci;
  218.         while (true)
  219.         {
  220.             inputFile.get(ch);
  221.             if(inputFile.eof())
  222.                 break;
  223.             accum += ch;
  224.             for (ci = codes.begin(); ci != codes.end(); ++ci)
  225.             {
  226.                 if (!strcmp((*ci).second.c_str(), accum.c_str()))
  227.                 {
  228.                     accum = "";
  229.                     std::cout<<(*ci).first;
  230.                     outputFile<<(*ci).first;
  231.                 }
  232.             }
  233.         }
  234.         std::cout<<endl;
  235.  
  236.  
  237.         // Cleaning
  238.         //
  239.         outputFile.close();
  240.         outputFile.clear();
  241.         inputFile.close();
  242.         inputFile.clear();
  243.     }
  244.  
  245. private:
  246. 	treeNode* leftmost(vector<treeNode*> ptr,int i){
  247. 		treeNode *temp = ptr[i];
  248. 		while(temp->left!=NULL)temp = temp->left;
  249. 		return temp;
  250. 	}
  251.     void EncHuffman()
  252.     {
  253.         // Creating leaves (initial top-nodes)
  254.         //
  255.         treeNode *n;
  256.         vector<treeNode*> tops; // top-nodes
  257.         int i, numtop = tsize;
  258.         for (i = 0; i < numtop; i++)
  259.         {
  260.             n = new treeNode;
  261.             //assert(n);
  262.             n->ch = ptable[i].ch;
  263.             n->freq = ptable[i].freq;
  264.             n->left = NULL;
  265.             n->right = NULL;
  266.             tops.push_back(n);
  267.         }
  268.         sort(tops.begin(),tops.end(),cmpByChar);
  269. 		sort(tops.begin(),tops.end(),cmp);
  270. 		for(i=0;i<tops.size();i++){
  271. 			cout<<"chars:"<<tops[i]->ch<<" times:"<<tops[i]->freq<<endl; 
  272. 		}
  273.         // Building binary tree.
  274.         // Combining last two nodes, replacing them by new node
  275.         // without invalidating sort
  276.         //
  277.         int count=1;
  278.         while (numtop > 1)
  279.         {
  280.             n = new treeNode;
  281.             //assert(n);
  282.             n->freq = tops[0]->freq + tops[1]->freq;
  283. 	        if(tops[0]->ch!=' '&& tops[1]->ch!=' '){
  284. 	            n->left = tops[0]->ch < tops[1]->ch ? tops[0]: tops[1];
  285. 	            n->right = tops[0]->ch < tops[1]->ch ? tops[1]: tops[0];
  286. 	            n->min = tops[0]->ch < tops[1]->ch? tops[0]->ch : tops[1]->ch;
  287. 	            tops[0]->ch < tops[1]->ch ? cout<<"YES" : cout<<"NO";
  288. 	            cout<<endl;
  289. 			}
  290. 			else{
  291. 				cout<<"HI"<<endl;
  292. 				if(tops[0] ->min !=' ' && tops[1]->min ==' '){
  293. 					n->left = tops[0]->min > tops[1]->ch ? tops[1] : tops[0];
  294. 					n->right = tops[0]->min > tops[1]->ch ? tops[0] : tops[1];
  295. 				}
  296. 				else if(tops[0] ->min !=' ' && tops[1]->min !=' '){
  297. 					n->left = tops[0]->min > tops[1]->min ? tops[1] : tops[0];
  298. 					n->right = tops[0]->min > tops[1]->min ? tops[0] : tops[1];
  299. 				}
  300. 				else if(tops[0]->ch == ' '&& tops[1]->ch ==' '){
  301. 					treeNode *left_leftmost = leftmost(tops,0);
  302. 					treeNode *right_leftmost = leftmost(tops,1);
  303. 					n->left = left_leftmost->ch < right_leftmost->ch ? tops[0] : tops[1];
  304. 					n->right = left_leftmost->ch < right_leftmost->ch ? tops[1] : tops[0];
  305. 					cout<<"XCC"<<endl;
  306. 				}
  307. 				else if(tops[0]->ch == ' '){
  308. 					cout<<"GGG"<<endl;
  309. 				}
  310. 				else if(tops[1]->ch == ' '){
  311. 					treeNode *left_leftmost = leftmost(tops,0);
  312. 					treeNode *right_leftmost = leftmost(tops,1);
  313. 					n->left = left_leftmost->ch < right_leftmost->ch ? tops[0] : tops[1];
  314. 					n->right = left_leftmost->ch < right_leftmost->ch ? tops[1] : tops[0];
  315. 				}
  316. 			}
  317.             pop_front(tops);
  318.            	pop_front(tops);
  319.             tops.push_back(n);
  320.             sort(tops.begin(),tops.end(),cmpByChar);
  321. 			sort(tops.begin(),tops.end(),cmp);
  322.             cout<<count++<<endl;
  323.         	for(i=0;i<tops.size();i++){
  324.  
  325. 				cout<<"chars:"<<tops[i]->ch<<" times:"<<tops[i]->freq<<endl; 
  326. 			}
  327. 			cout<<"\n\n\n";
  328.             numtop--;
  329.         }
  330.  
  331.         // Building codes
  332.         //
  333.         cout<<"generate..."<<endl;
  334.  
  335.         treeNode *root = tops[0];
  336.         GenerateCode(root);
  337.  
  338.         // Cleaning 
  339.         // 
  340.         DestroyNode(root);
  341.         tops.clear();
  342.     }
  343.  
  344.     void GenerateCode( treeNode *node ) // for outside call: node is root
  345.     {
  346.         static string sequence = "";
  347.         if( node->left )
  348.         {
  349.             sequence += "0";
  350.             GenerateCode( node->left );
  351.         }
  352.  
  353.         if( node->right )
  354.         {
  355.             sequence += "1";
  356.             GenerateCode( node->right );
  357.         }
  358.  
  359.         if( !node->left && !node->right )
  360.             codes[node->ch] = sequence;
  361.  
  362.         int l = (int)sequence.length();
  363.         if( l > 1 ) 
  364.             sequence = sequence.substr( 0, l-1 );
  365.         else 
  366.             sequence = "";
  367.     }
  368.  
  369.     void DestroyNode( treeNode *node) // for outside call: node is root
  370.     {
  371.         if (node->left)
  372.         {
  373.             DestroyNode(node->left);
  374.             delete node->left;
  375.             node->left = NULL;
  376.         }
  377.  
  378.         if (node->right)
  379.         {
  380.             DestroyNode(node->right);
  381.             delete node->right;
  382.             node->right = NULL;
  383.         }
  384.     }
  385. };
  386.  
  387. int show_usage()
  388. {
  389.     cout<<"Usage:"<<endl; 
  390.     cout<<" huffman [OPTIONS] input [output]"<<endl;
  391.     cout<<" The defaul action is to encode the input file."<<endl;
  392.     cout<<" -d\tDecode file."<<endl;
  393.     cout<<endl;
  394.     cout<<"Examples:"<<endl;
  395.     cout<<" huffman input.txt"<<endl;
  396.     cout<<" huffman input.txt encoded.txt"<<endl;
  397.     cout<<" huffman -d encoded.txt"<<endl;
  398.     exit(0);
  399. }
  400.  
  401. int main(int argc, char **argv)
  402. {
  403.     int i = 1;
  404.     bool decFlag = false;   // decode flag
  405.     char inputFilename[128];  
  406.     char outputFilename[128];
  407.  
  408.     if (argc < 2)
  409.     {
  410.         show_usage();
  411.     }
  412.  
  413.     if (strcmp(argv[i],"-d") == 0)
  414.     {
  415.         decFlag = true;
  416.         ++i;
  417.         if (i == argc)
  418.         {
  419.             show_usage();
  420.         }
  421.     }
  422.  
  423.     strcpy(inputFilename, argv[i]);
  424.     ++i;
  425.  
  426.     if (i < argc)
  427.     {
  428.         strcpy(outputFilename, argv[i]);
  429.     }
  430.     else
  431.     {
  432.         if (decFlag) strcpy(outputFilename, "decoded.txt");
  433.         else         strcpy(outputFilename, "encoded.txt");
  434.     }
  435.  
  436.     // Calling encoding or decoding subroutine
  437.     // 
  438.     HCode *pCoder;
  439.     pCoder = new HCode;
  440.     if (!pCoder)
  441.     {
  442.         cerr<<"error: unable to create a pointer to HCode"<<endl;
  443.     }
  444.  
  445.     if (!decFlag)
  446.     {
  447.         pCoder->enCode(inputFilename, outputFilename);
  448.     }
  449.     else
  450.     {
  451.         pCoder->Decode(inputFilename, outputFilename);
  452.     }
  453.     delete pCoder;
  454.  
  455.     return 0;
  456. }
Success #stdin #stdout 0s 15272KB
comments (?)
stdin 
Standard input is empty
stdout 
Usage:
 huffman [OPTIONS] input [output]
 The defaul action is to encode the input file.
 -d	Decode file.

Examples:
 huffman input.txt
 huffman input.txt encoded.txt
 huffman -d encoded.txt
https://ideone.com/ZD7z1f
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!