vendredi 25 novembre 2016

Huffman Coding Issue C++

I am trying to practice compression in C++ using Huffmann coding. I have tried debugging my code in a6.hpp extensively, yet I am unable to find the errors in the logic/code. Please help me and considering that I am just a novice in the forum, please avoid downvoting. Thank you!!

NOTE: File in question is a6.hpp

a6.cpp

#include "symbol.hpp"
#include "a6.hpp"

#include <fstream>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>


template <typename IterIn, typename IterOut>
void symbols(IterIn first, IterIn last, IterOut out) {
std::vector<int> count(256, 0);

for (; first != last; ++first) {
    const std::string& s = *first;
    for (int i = 0; i < s.size(); ++i) count[s[i]]++;
} // for first

for (int c = 0; c < 256; ++c) {
    if (count[c] > 0) *out++ = symbol(static_cast<char>(c), count[c]);
}
} // symbols

int main(int argc, char* argv[]) {
if (argc != 2) {
    std::cout << "usage: ./a6 file" << std::endl;
    return -1;
}

// get input text
std::ifstream f(argv[1]);

std::string s;
std::vector<std::string> lines;

while (!f.eof()) {
    s = "";
    std::getline(f, s);
    if (!s.empty()) lines.push_back(s);
}

f.close();

// create a list of symbols
std::vector<symbol> A;
symbols(lines.begin(), lines.end(), std::back_inserter(A));

// process the list (student's code)
bnode<symbol>* tree = huffman_tree(A.begin(), A.end());

// print dictionary (student's code)
print_dictionary(std::cout, tree);

// free memory (student's code)
release_tree(tree);

return 0;

} // main

a6.hpp

#ifndef A6_HPP
#define A6_HPP

#include <iostream>
#include "symbol.hpp"
#include <queue>
#include <vector>
typedef bnode<symbol> ht_node;

// MAKE SURE TO UPDATE YOUR INFORMATION IN THE HEADER OF THIS FILE
// IMPLEMENT ALL REQUIRED FUNCTIONS BELOW
// YOU ARE NOT ALLOWED TO ALTER ANY INTERFACE
// INSIDE A FUNCTION YOU CAN DO WHATEVER YOU LIKE

// IMPLEMENT YOUR FUNCTION huffman_tree
template <typename Iter>
bnode<symbol>* huffman_tree(Iter first, Iter last) {

std::priority_queue<ht_node*, std::vector<ht_node*>> pq;
for (; first != last; ++first) { pq.push(new ht_node(*first)); }

while (pq.size() != 1)
{
    // Extract the two minimum freq items from min heap
    ht_node* left = pq.top();
    pq.pop();

    ht_node* right = pq.top();
    pq.pop();

    symbol* sym = new symbol('$', left->value.count + right->value.count);
    ht_node* res = new ht_node(*sym, left, right);
    pq.push(res);
    delete sym;
}

return pq.top();    
}

// IMPLEMENT YOUR FUNCTION print_dictionary
void print_dictionary(std::ostream& os, bnode<symbol>* root) {

if(!root) {return;}

if(root->value.value != '$') {
os << root->value.value << " ";
print_dictionary(os << "0", root->left);
print_dictionary(os << "1", root->right);
os << "\n";
}
}

// IMPLEMENT YOUR FUNCTION release_tree
void release_tree(bnode<symbol>* root) {
ht_node* n = root;
if(n->left != 0){
    release_tree(n->left);
}
if(n->right != 0){
    release_tree(n->right);
}
delete n;
}

#endif // A5_HPP

symbol.hpp

#ifndef SYMBOL_HPP
#define SYMBOL_HPP

struct symbol {
explicit symbol(char av = 0, int ac = 0) : value(av), count(ac) { }
char value; // actual symbol, by default 0 (empty)
int count;  // count of the symbol, by default 0
}; // symbol

// compare two symbols
// symbol with a lower count is "less than" symbol with a higher count
// symbols with equal count are compare lexicographically
inline bool operator<(const symbol& lhs, const symbol& rhs) {
return ((lhs.count < rhs.count) || (!(rhs.count < lhs.count) && (lhs.value <     rhs.value)));
} // operator<

template <typename T> struct bnode {
explicit bnode(const T& t = T(), bnode* l = nullptr, bnode* r = nullptr)
    : value(t), left(l), right(r) { }

T value;      // payload

bnode* left;  // left child
bnode* right; // right child
}; // struct bnode

#endif // SYMBOL_HPP

Aucun commentaire:

Enregistrer un commentaire