Advertisement
Guest User

Untitled

a guest
May 24th, 2015
194
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.66 KB | None | 0 0
  1. #include "Huffman.h"
  2. #include "../../InputOutput/Interface/Reader.h"
  3. #include "../../InputOutput/Interface/Writer.h"
  4.  
  5.  
  6. HuffmanArchiver::HuffmanArchiver()
  7. {
  8.     for(int i = 0; i < kCharNum; i++)
  9.         code_[i] = "xx";
  10.     for(int i = 0; i < kMaxNum; i++)
  11.         sym_[i] = 'x';
  12.     root_ = NULL;
  13.     was_build_ = false;
  14.     tree_num_ = 0;
  15.     sym_num_ = 0;    
  16.     decompressed_index_ = 0;
  17. }
  18. HuffmanArchiver::~HuffmanArchiver(){}
  19.  
  20. bool HuffmanArchiver::comp(Node a, Node b)
  21. {
  22.     return (a.num > b.num);
  23. }
  24.  
  25. void HuffmanArchiver::TreeSave(Node *v, unsigned short ParentNum, int type)
  26. {
  27.     parent_[tree_num_] = ParentNum;
  28.     type_[tree_num_] = (unsigned char) (char)type;
  29.     tree_num_++;  
  30.     int x = tree_num_ - 1;
  31.    
  32.     if (v->value.length() > 1)
  33.     {
  34.         TreeSave(v->l, x, 0);
  35.         TreeSave(v->r, x, 1);    
  36.     }
  37.     else
  38.     {
  39.         is_sym_[x] = true;  
  40.         sym_[x] = (unsigned char)v->value[0];
  41.     }    
  42.  
  43. }
  44.  
  45. void HuffmanArchiver::Code(Node *a, string prefix)
  46. {    
  47.     if (a->value.length() == 1)
  48.     {
  49.         code_[(int)a->value[0]] = prefix;      
  50.         return;
  51.     }
  52.     Code(a->l, prefix + "0");  
  53.     Code(a->r, prefix + "1");                            
  54.  
  55. }
  56. void HuffmanArchiver::CompressInit(Reader *reader, Writer *writer)
  57. {    
  58.     unsigned char sym;
  59.     file_length_ = 0;
  60.     for (int i = 0; i < kCharNum; i++)
  61.         num_[i] = 0;
  62.     while (reader->GetChar(&sym))
  63.     {
  64.         file_length_++;
  65.         num_[(int)sym]++;    
  66.     }  
  67.  
  68. }
  69. void HuffmanArchiver::Compress(Reader *reader, Writer *writer)
  70. {    
  71.     unsigned short n = 0;
  72.     long long sym_to_read = 0;
  73.     unsigned char sym;
  74.     bool b;
  75.     Node comp_tree[kMaxNum];
  76.     Reader *newreader = reader->Clone();
  77.     CompressInit(reader,writer);                          
  78.    
  79.     for(int i = 0; i < kCharNum; i++)
  80.         if (num_[i] > 0)
  81.         {
  82.             comp_tree[n].value = char(i);        
  83.             comp_tree[n].num = num_[i];    
  84.             n++;                        
  85.         }
  86.     sym_num_ = n;
  87.     std::sort(comp_tree, comp_tree + n, comp);    
  88.     while (n > 1)
  89.     {
  90.         Node *n1 = new Node;
  91.         Node *n2 = new Node;
  92.         *n1 = comp_tree[n-2];      
  93.         *n2 = comp_tree[n-1];        
  94.         n--;
  95.         comp_tree[n-1].l = n1;
  96.         comp_tree[n-1].r = n2;
  97.         comp_tree[n-1].value = n1->value + n2->value;
  98.         comp_tree[n-1].num = n1->num + n2->num;
  99.         std::sort(comp_tree, comp_tree + n, comp);
  100.     }
  101.     root_ = &comp_tree[0];    
  102.     Code(root_, "");
  103.     for(int i = 0; i < kCharNum; i++)
  104.         if (num_[i] > 0)
  105.             sym_to_read += num_[i] * code_[i].length();
  106.  
  107.     for (int i = 0; i < kMaxNum; i++)
  108.         is_sym_[i] = false;
  109.     tree_num_ = 0;    
  110.     TreeSave(root_,0,0);
  111.    
  112.     writer->PutShort(tree_num_);    
  113.  
  114.     for(int i = 0; i < tree_num_; i++)
  115.     {
  116.         writer->PutShort(parent_[i]);
  117.         writer->PutChar(type_[i]);                     
  118.     }
  119.  
  120.     writer->PutShort(sym_num_);    
  121.     for(unsigned short i = 0; i < tree_num_; i++)
  122.     {
  123.         if (is_sym_[i])
  124.         {
  125.             writer->PutShort(i);
  126.             writer->PutChar(sym_[i]);
  127.         }    
  128.     }
  129.  
  130.  
  131.    
  132.     writer->PutLong(sym_to_read);                          
  133.     writer->Flush();
  134.    
  135.     while(newreader->GetChar(&sym))
  136.     {      
  137.         int k = int(sym);
  138.         for(size_t j = 0; j < code_[k].length(); j++)
  139.             if (code_[k][j] == '0')
  140.                 writer->PutBit(false);                     
  141.             else   
  142.                 writer->PutBit(true);                              
  143.     }
  144.    
  145.     writer->Flush();  
  146. }
  147.  
  148. void HuffmanArchiver::Decompress(Reader *reader, Writer *writer)
  149. {  
  150.  
  151.     while (PutNextDecompressedPart(reader,writer));
  152.  
  153. }
  154. bool HuffmanArchiver::PutNextDecompressedPart(Reader *reader, Writer *writer)
  155. {
  156.     if (!was_build_)
  157.     {
  158.         TreeBuild(reader, writer);
  159.         was_build_ = true; 
  160.         reader->GetLong(&file_length_);
  161.     }                            
  162.  
  163.     int read_num = 0;
  164.     bool b,end_of_file = false;
  165.     Node *cur_node;
  166.     cur_node = &tree_[0];
  167.  
  168.     while(read_num <= kOpNum && reader->GetBit(&b))
  169.     {    
  170.         decompressed_index_++;
  171.         if (decompressed_index_ > file_length_)
  172.             break;
  173.         if (cur_node->value.length() > 1)
  174.         {
  175.             if (!b)
  176.                 cur_node = cur_node->l;
  177.             else
  178.                 cur_node = cur_node->r;  
  179.         }
  180.         else
  181.         {
  182.             read_num++;        
  183.             writer->PutChar(cur_node->value[0]);            
  184.  
  185.             cur_node = &tree_[0];            
  186.             if (!b)
  187.                 cur_node = cur_node->l;
  188.             else
  189.                 cur_node = cur_node->r;
  190.         }
  191.         if (cur_node->value.length() == 1 && read_num == kOpNum)
  192.         {
  193.             writer->PutChar(cur_node->value[0]);
  194.             break;
  195.         }
  196.     }
  197.  
  198.     writer->Flush();    
  199.     if (read_num < kOpNum)
  200.         end_of_file = true;        
  201.     return (!end_of_file);
  202. }
  203.  
  204.  
  205. void HuffmanArchiver::TreeBuild(Reader *reader, Writer *writer)
  206. {
  207.     unsigned char type,sym;
  208.     unsigned short num;    
  209.     unsigned short sym_num;
  210.  
  211.     reader->GetShort(&tree_num_);        
  212.     tree_[0].value = "xx";
  213.     reader->GetShort(&num);
  214.     reader->GetChar(&type);
  215.  
  216.     for(int i = 1; i < tree_num_; i++)
  217.     {  
  218.         tree_[i].value = "xx";
  219.         reader->GetShort(&num);
  220.         reader->GetChar(&type);
  221.         if (type == 0)
  222.             tree_[num].l = &tree_[i];
  223.         else
  224.             tree_[num].r = &tree_[i];
  225.     }
  226.  
  227.     reader->GetShort(&sym_num);
  228.     for(unsigned short i = 0; i < sym_num; i++)
  229.     {    
  230.         reader->GetShort(&num);
  231.         reader->GetChar(&sym);        
  232.         tree_[num].value = "x";
  233.         tree_[num].value[0] = sym;
  234.     }
  235.  
  236. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement