I have been trying to create a huffman tree in C++. I have a custom Huffman Node class and a Huffman tree class, whose header and source file contents are shown below:
This is my main() function:
#include <iostream> // Includes the input and output stream header file.
#include <string> // Includes the string library.
#include <exception> // Includes the exceptions header file.
#include "HuffmanNode.h" // Includes the Huffman node class and all its respective components.
#include "HuffmanTree.h" // Includes the Huffman tree class and all its respective components.
#include <fstream> // Includes the file stream header file.
using namespace FOOBAR; // Declare the use of my custom made namespace.
int main(int argc, char* argv[]) {
std::string input_file, output_file;
try {
std::cout << "" << std::endl;
input_file = std::string(argv[1]); output_file = std::string(argv[2]);
HuffmanTree my_huffman_tree = HuffmanTree(/*fptr compare*/);
my_huffman_tree.generateMap(input_file);
my_huffman_tree.createHuffmanNodes();
std::cout << "" << std::endl;
}
catch(std::exception e) {
std::cout << "" << std::endl;
std::cout << "Error: " << e.what() << std::endl; // Print out the exact nature of the error.
std::cout << "" << std::endl;
exit(0); // Terminate program execution.
}
return 0;
}
This is my Huffman Node header file:
// Preprocessor directives that guard against redeclaration should image_manipulator.h be defined elsewhere in the program
#ifndef HUFFMANNODE_H
#define HUFFMANNODE_H
// These are the included header files that are required for the execution of the program.
#include <memory>
// This is my custom namespace for the program.
namespace FOOBAR {
class HuffmanNode {
private:
char character; int frequency; // These are the constituents of each node i.e. consists of a character as well as a frequency.
std::shared_ptr<HuffmanNode> left_node, right_node; // Left and right attributes for my left and right nodes.
public:
HuffmanNode(char the_char, int the_frequency); // Declaration of default constructor.
HuffmanNode(int the_frequency); // Declaration of default constructor.
HuffmanNode(const HuffmanNode& rhs); // Copy constructor.
HuffmanNode(const HuffmanNode&& rhs); // Move constructior.
HuffmanNode & operator=(const HuffmanNode& rhs); // Copy assignment operator.
HuffmanNode && operator=(const HuffmanNode&& rhs); // Move assignment operator.
char getCharacter() const; // Retrieve a key in the map.
int getFrequency() const; // retrieve a value in the map.
std::shared_ptr<HuffmanNode> getLeftNode(); // Fetch the left node.
std::shared_ptr<HuffmanNode> getRightNode(); // Fetch the right node.
~HuffmanNode(); // Destructor.
// Declare other methods to be used here.
};
}
#endif
This is my Huffman Node source file:
#include "HuffmanNode.h"
namespace CHRTIN006 {
// This is the implementation one of the Huffman Node constructor method.
HuffmanNode::HuffmanNode(char the_char, int the_frequency) {
HuffmanNode::character = the_char; HuffmanNode::frequency = the_frequency;
}
// This is the implementation one of the Huffman Node constructor method.
HuffmanNode::HuffmanNode(int the_frequency) {
HuffmanNode::frequency = the_frequency;
}
// This is the implementation of the Huffman Node copy constructor.
HuffmanNode::HuffmanNode(const HuffmanNode &rhs) {
HuffmanNode::character = rhs.HuffmanNode::character;
HuffmanNode::frequency = rhs.HuffmanNode::frequency;
}
// This is the implementation of the Huffman Node move constructor.
HuffmanNode::HuffmanNode(const HuffmanNode &&rhs) {
}
// This is the implementation of the Huffman Node copy assignment operator.
HuffmanNode& HuffmanNode::operator=(const HuffmanNode &rhs) {
if(this == &rhs) {
return *this;
}
HuffmanNode::character = rhs.HuffmanNode::character;
HuffmanNode::frequency = rhs.HuffmanNode::frequency;
return *this;
}
// This is the implementation of the Huffman Node move assignment operator.
HuffmanNode && HuffmanNode::operator=(const HuffmanNode &&rhs) {
}
// This method will return the key of an entry in the map.
char HuffmanNode::getCharacter() const{
return HuffmanNode::character;
}
// This method will return the value of an entry in the map.
int HuffmanNode::getFrequency() const{
return HuffmanNode::frequency;
}
// Retrieve the left most node of that particular branch.
std::shared_ptr<HuffmanNode> HuffmanNode::getLeftNode() {
return HuffmanNode::left_node;
}
// Retrieve the right most node of that particular branch.
std::shared_ptr<HuffmanNode> HuffmanNode::getRightNode() {
return HuffmanNode::right_node;
}
// This is the implementation of the Huffman Node destructor.
HuffmanNode::~HuffmanNode() {
}
}
This is my header file contents for my Huffman Tree class:
// Preprocessor directives that guard against redeclaration should HuffmanTree.h be defined elsewhere in the program.
#ifndef HUFFMANTREE_H
#define HUFFMANTREE_H
// These are the included header files that are required for the execution of the program.
#include <queue> // For building the huffman tree.
#include "HuffmanNode.h" // Includes the Huffman Node header file.
#include <unordered_map> // Header file for my map that is going to store the respective frequencies of each letter.
#include <memory> // For making use of smart pointers.
#include <vector> // For making use of vectors within the program.
#include <functional> // For including the comparison method in the constructor of the queue.
// This is my custom namespace for the program.
namespace FOOBAR {
class HuffmanTree { // This is where my Huffman tree class starts.
public: // Objects an variables declared under this specifier are treated as being public.
// Going to be used to determine how to order entries in the queue.
typedef bool (*fptr)(const HuffmanNode&, const HuffmanNode&);
bool compare(const HuffmanNode& node_a, const HuffmanNode& node_b); /////////////////////////////
HuffmanTree(/*fptr compare*/); // Default constructor.
HuffmanTree(const HuffmanTree& rhs); // Copy constructor.
HuffmanTree(const HuffmanTree&& rhs); // Move constructior.
HuffmanTree& operator=(const HuffmanTree& rhs); // Copy assignment operator.
HuffmanTree&& operator=(const HuffmanTree&& rhs); // Move assignment operator.
~HuffmanTree(); // Destructor.
// This method is going to count the number of occurrences of each letter.
void generateMap(std::string file);
// Create Huffman nodes and populate them in the priority queue.
void createHuffmanNodes();
// Declare other methods to be used here.
private: // Objects an variables declared under this specifier are treated as being private.
std::shared_ptr<HuffmanNode> root_node; // The root node for the Huffman tree.
std::unordered_map<char, int> my_map; // Map containing the respective frequencies of each letter.
std::unordered_map<char, int>::iterator my_iterator; // Iterator for indexing every element in my map.
// This is the queue that is going to have entries of my shared pointers.
std::priority_queue<HuffmanNode, std::vector<HuffmanNode>, fptr> my_queue;
}; // This is where my Huffman tree class ends.
} // End of namespace.
#endif
This is the source file for my Huffman Tree class:
#include "HuffmanTree.h"
#include <fstream>
#include <iostream>
#include <boost/lexical_cast.hpp> // Includes the lexical cast functionlaity from the boost library.
namespace FOOBAR {
// This is the implementation of the Huffman Tree default constructor method.
HuffmanTree::HuffmanTree(/*fptr compare*/) /*: my_queue(compare)*/ {
root_node = nullptr;
}
// This is the implementation of the Huffman Tree copy constructor.
HuffmanTree::HuffmanTree(const HuffmanTree& rhs) {
root_node = rhs.root_node;
}
// This is the implementation of the Huffman Tree move constructor.
HuffmanTree::HuffmanTree(const HuffmanTree&& rhs) {
}
// This is the implementation of the Huffman Tree copy assignment operator.
HuffmanTree& HuffmanTree::operator=(const HuffmanTree& rhs) {
if(this == &rhs) {
return *this;
}
root_node = rhs.root_node;
return *this;
}
// This is the implementation of the Huffman Tree move assignment operator.
HuffmanTree&& HuffmanTree::operator=(const HuffmanTree&& rhs) {
}
// This is the implementation of the compare method that is going to be used to determine how to order entries in the queue.
bool compare(const HuffmanNode& node_a, const HuffmanNode& node_b) { ////////////////////////////////////////
if(node_a.getFrequency() > node_b.getFrequency()) {
return true;
}
else {
return false;
}
}
// This method is going to count the number of occurrences of each letter.
void HuffmanTree::generateMap(std::string file) {
std::ifstream input_stream(file); std::string line = "";
if(input_stream.fail()) {
std::cerr << "Error: Could not open the file specified." << std::endl; // Print this error message.
}
else {
while(std::getline(input_stream, line)) {
for(int i = 0; i < line.length(); i++) {
char my_character = line.at(i);
my_iterator = HuffmanTree::my_map.find(my_character);
if(my_iterator == my_map.end()) {
HuffmanTree::my_map.insert(std::make_pair(my_character, 1));
}
else {
my_iterator -> second++;
}
}
}
}
}
void HuffmanTree::createHuffmanNodes() {
for(my_iterator = my_map.begin(); my_iterator != my_map.end(); ++my_iterator) {
HuffmanNode some_huffman_node = HuffmanNode(boost::lexical_cast<char>(my_iterator -> first), boost::lexical_cast<int>(my_iterator -> second));
//my_queue.push(some_huffman_node); <---- Causes Segfault error
}
}
// This is the implementation of the Huffman Tree destructor.
HuffmanTree::~HuffmanTree() {
HuffmanTree::root_node = nullptr;
}
}
Any input text can be used.
But as soon as I try to push a newly created huffman node, i get the following error:
Makefile:32: recipe for target 'run' failed make: * [run] Segmentation fault (core dumped)**
I have been stuck on this part alone for the past 3 days. Can somebody help me please? Thank you in advance.
HuffmanNodeis missing. It's only in the comment above that you mention where it fails.HuffmanNodeinstance. Which code, you haven't shown. In other words, your code fails somewhere you haven't shown. So, please add there relevant code, otherwise you can't be helped.