fork download 
  1. //bitstring.cpp
  2. #include "bitstring.h"
  3.  
  4. BitStringWrite::BitStringWrite(std::ostream &_out_f) : _byte(0), _pos(0), _out_f(_out_f) {}
  5.  
  6. void BitStringWrite::writeBit(bool bit) {
  7.     if (_pos == 8)
  8.         flush();
  9.     if (bit == 1) {
  10.         _byte |= (1 <<   _pos);
  11.     }
  12.     _pos++;
  13. }
  14.  
  15. void BitStringWrite::writeByte(char b){
  16.     for(int i = 0; i < 8; i++)
  17.         this -> writeBit((b >> i) & 1);
  18. }
  19.  
  20. void BitStringWrite::flush() {
  21.     if (_pos != 0) {
  22.         _out_f.write(&_byte, sizeof(char));
  23.         _pos = 0;
  24.         _byte = 0;
  25.     }
  26. }
  27.  
  28.  
  29. BitStringRead::BitStringRead(std::istream &_in_f) : _pos(8), _in_f(_in_f) {}
  30.  
  31. bool BitStringRead::readBit() {
  32.     if (_pos == 8) {
  33.         _in_f.read(&_byte, sizeof(char));
  34.         _pos = 0;
  35.     }
  36.     return (_byte >> _pos++) & (char)1;
  37. }
  38.  
  39. char BitStringRead::readByte() {
  40.     char sym = (char)0;
  41.     for (int i = 0; i < 8; i++){
  42.         sym |= ((1 & readBit()) << (i));
  43.     }
  44.     return sym;
  45. }
  46.  
  47. BitStringWrite::~BitStringWrite() {
  48.     flush();
  49. }
  50.  
  51.  
  52.  
  53. ____________________________________________
  54. //archiver.cpp
  55.  
  56. #include "archiver.h"
  57. #include <fstream>
  58.  
  59. void Archiver::encodeTree(BitStringWrite& bw, TreeNode* node){
  60.     if (node -> isLeaf()) {
  61.         bw.writeBit(1);
  62.         char symb = node->getChar();
  63.         bw.getStream().write(&symb, sizeof(symb));
  64.     }
  65.     else {
  66.         bw.writeBit(0);
  67.         encodeTree(bw, node->getLeftTree());
  68.         encodeTree(bw, node->getRightTree());
  69.     }
  70. }
  71.  
  72. TreeNode* Archiver::decodeTree(BitStringRead& br, TreeNode* cur){
  73.     if (br.readBit()) {
  74.         return new TreeNode(br.readByte(), 0, false, NULL, NULL);
  75.     }
  76.     else {
  77.         TreeNode* left = decodeTree(br, cur-> getLeftTree());
  78.         TreeNode* right = decodeTree(br, cur-> getRightTree());
  79.         decodeTree(br, cur-> getRightTree());
  80.         return new TreeNode(0, 0, false, left, right);
  81.     }
  82. }
  83.  
  84. void Archiver::buildCodes(TreeNode* n, std::vector<bool>& cur) {
  85.     if (n -> isLeaf()) {
  86.         codes[cur] = n->getChar();
  87.         return;
  88.     }
  89.     cur.push_back(0);
  90.     buildCodes(n->getLeftTree(), cur);
  91.     cur.pop_back();
  92.     cur.push_back(1);
  93.     buildCodes(n->getRightTree(), cur);
  94. }
  95.  
  96.  
  97. void Archiver::compress(std::ifstream &ifs, std::ofstream &ofs, HuffmanTree *tree) {
  98.     ifs.seekg(0, ifs.beg);
  99.     BitStringRead br(ifs);
  100.     BitStringWrite bw(ofs);
  101.     tree->buildTable();
  102.     encodeTree(bw, tree -> getRoot());
  103.     char symb = 0;
  104.     while(!ifs.eof()){
  105.         ifs.read(&symb, sizeof(symb));
  106.         int sz = tree->getTable()[symb].size();
  107.         std::vector<bool> out = tree->getTable()[symb];
  108.         std::cout << std::endl;
  109.         for(int i = 0; i < sz; i++)
  110.             bw.writeBit(out[i]);
  111.     }
  112. }
  113.  
  114. void Archiver::decompress(std::ifstream &ifs, std::ofstream &ofs, HuffmanTree *tree) {
  115.     ifs.seekg(0, ifs.beg);
  116.     BitStringRead br(ifs);
  117.     BitStringWrite bw(ofs);
  118.     decodeTree(br, tree->getRoot());
  119.     std::vector<bool> cur;
  120.   /*  buildCodes(tree->getRoot(), cur);
  121.     while(!ifs.eof()){
  122.         std::vector<bool> v;
  123.         while(!(getCodes().count(v))) {
  124.             bool b = br.readBit();
  125.             v.push_back(b);
  126.         }
  127.         char s = getCodes()[v];
  128.         v.clear();
  129.         ofs.write(&s, sizeof(s));
  130.     }*/
  131. }
  132.  
  133.  
  134. _________________________________
  135. //huffman.cpp
  136.  
  137. #include "huffman.h"
  138. #include "archiver.h"
  139. #include <sstream>
  140. #include <queue>
  141. using namespace std;
  142.  
  143. HuffmanTree::HuffmanTree(std::map<char, int>& count_map) {
  144.     if (count_map.empty()) {
  145.         std::stringstream ss;
  146.         ss << "Compressor requires a non-empty text.";
  147.         throw std::runtime_error{ss.str()};
  148.     }
  149.  
  150.     std::priority_queue<TreeNode*, std::vector<TreeNode*>, HuffmanTree::NodeComparator> queue;
  151.  
  152.     for(auto a : count_map)
  153.         queue.push(new TreeNode(a.first, a.second, true, NULL, NULL));
  154.  
  155.     while (queue.size() > 1) {
  156.         TreeNode* node1 = queue.top(); queue.pop();
  157.         TreeNode* node2 = queue.top(); queue.pop();
  158.         queue.push(merge(node1, node2));
  159.     }
  160.  
  161.     root = queue.top(); queue.pop();
  162. }
  163.  
  164. std::map<char, vector<bool> > HuffmanTree::buildTable() {
  165.     deque< pair<TreeNode *, code_t> > q;
  166.     q.push_back(make_pair(this->getRoot(), code_t()));
  167.     while (!q.empty()) {
  168.         TreeNode *node, *lc, *rc;
  169.         code_t code;
  170.         node = q.front().first;
  171.         code = q.front().second;
  172.         q.pop_front();
  173.         lc = node->getLeftTree();
  174.         rc = node->getRightTree();
  175.         if (lc) {
  176.             code_t code_cp(code);
  177.             q.push_back(make_pair(lc, (code.push_back(0), code)));
  178.             q.push_back(make_pair(rc, (code_cp.push_back(1), code_cp)));
  179.         }
  180.         else {
  181.             lookup.insert(make_pair(node->getChar(), code));
  182.            cout << "(" << node->getChar() << ", ";
  183.             for (unsigned i = 0; i < code.size(); i++) {
  184.                 cout << code[i];
  185.             }
  186.             cout << ")" << endl;
  187.         }
  188.     }
  189.     return lookup;
  190. }
  191.  
  192. void BuildTable(TreeNode *root, std::vector<bool> &code, std::map<std::vector<bool>, char > &table){
  193.     if (root->getLeftTree()){
  194.         code.push_back(0);
  195.         BuildTable(root->getLeftTree(), code, table);
  196.     }
  197.  
  198.     if (root->getRightTree()){
  199.         code.push_back(1);
  200.         BuildTable(root->getRightTree(), code, table);
  201.     }
  202.  
  203.     if (root->getChar())
  204.         table[code] = root->getChar();
  205.  
  206.     if (code.size())
  207.         code.pop_back();
  208. }
  209.  
  210. void HuffmanTree::recursiveNodeDelete(TreeNode* node) {
  211.     if (node == NULL) {
  212.         return;
  213.     }
  214.  
  215.     recursiveNodeDelete(node->getLeftTree());
  216.     recursiveNodeDelete(node->getRightTree());
  217.  
  218.     delete node;
  219. }
  220.  
  221. HuffmanTree::~HuffmanTree() {
  222.     recursiveNodeDelete(root);
  223. }
  224.  
  225. TreeNode* HuffmanTree::merge(TreeNode* node1, TreeNode* node2) {
  226.     TreeNode* new_node = new TreeNode(0, node1->getCount() + node2->getCount(), false, NULL, NULL);
  227.  
  228.     if (node1->getCount() < node2->getCount()) {
  229.         new_node->setLeftTree(node1);
  230.         new_node->setRightTree(node2);
  231.     }
  232.  
  233.     else {
  234.         new_node->setLeftTree(node2);
  235.         new_node->setRightTree(node1);
  236.     }
  237.  
  238.     new_node->setChar(std::max(node1->getChar(), node2->getChar()));
  239.  
  240.     return new_node;
  241. }
  242.  
  243. ______________________________________________
  244.  
  245. //main.cpp
  246.  
  247. #include <iostream>
  248. #include <bits/stdc++.h>
  249. #include "huffman.h"
  250. #include "archiver.h"
  251. using namespace std;
  252.  
  253. std::map<char, int32_t> createFreqTable(const std::string &strfile){
  254.     std::ifstream file(strfile);
  255.     std::map<char, int32_t> freq;
  256.     int next = 0;
  257.     while ((next = file.get()) != EOF) {
  258.         char uc = static_cast <char> (next);
  259.         std::map<char, int32_t>::iterator iter;
  260.         iter = freq.find(uc);
  261.         if (iter != freq.end())
  262.             iter->second += 1;
  263.         else
  264.             freq[uc] = 1;
  265.     }
  266.     return freq;
  267. };
  268.  
  269. int main() {
  270.     Archiver ar;
  271.  
  272.     std::map<char, int32_t> m = createFreqTable("test.in");
  273.     HuffmanTree t(m);
  274.     std::ifstream ifs("test.in");
  275.     std::ofstream ofs("test.out");
  276.     //t.buildTable(t.getRoot());
  277.     ar.compress(ifs, ofs, &t);
  278.  
  279.  
  280.    /* HuffmanTree nt;
  281.     std::ifstream ifs("test.out");
  282.     std::ofstream ofs("testo.txt");
  283.     vector<bool> v;
  284.     ar.decompress(ifs, ofs, &nt);*/
  285.  
  286.     return 0;
  287. }
  288.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp:2:23: fatal error: bitstring.h: No such file or directory
 #include "bitstring.h"
                       ^
compilation terminated.
stdout 
Standard output is empty
https://ideone.com/XFY9nv
language:
C++14 (gcc 8.3)
created:
8 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!