After having saved a huffman tree to a file, I am trying to read and rebuild this same tree again, with the same structure it had before. I follow this post and write this function to do that:
void build_tree(BinaryTree<HuffmanNode> * tree, List<NodeTree<HuffmanNode>> * list, int start, int end) {
if(start > end)
return;
tree->insert(list->get(start)->getData().getData());
int i;
for(i = start; i <= end; i++) {
if(list->get(i)->getData().getData() > list->get(start)->getData().getData()) {
break;
}
}
build_tree(tree, list, start + 1, i - 1);
build_tree(tree, list, i, end);
}
the classes List and BinaryTree in the example are:
List.h
template<class T>
class List {
private:
NodeList<T> * first;
public:
List();
~List();
void insert(T data);
void update(int index, T data);
void remove(int index);
int size();
NodeList<T> * get(int index);
void set(int index, NodeList<T> * value);
int find(T data);
void sort();
void print();
T * toArray();
};
NodeList.h
template<class T>
class NodeList {
private:
T data;
NodeList * next;
public:
NodeList();
~NodeList();
T getData();
void setData(T value);
NodeList * getNext();
void setNext(NodeList<T> * next);
void setNext(NodeList<T> next);
};
binaryTree.h
template<class T>
class BinaryTree {
protected:
NodeTree<T> * root;
public:
BinaryTree();
~BinaryTree();
NodeTree<T> * getRoot();
void setRoot(NodeTree<T> * node);
void insert(T value);
void update(T old_value, T new_value);
void remove(T value);
List<T> preOrder();
List<T> inOrder();
List<T> postOrder();
void preOrder(NodeTree<T> * node, List<T> * list);
void inOrder(NodeTree<T> * node, List<T> * list);
void postOrder(NodeTree<T> * node, List<T> * list);
List<T> level(int value);
int levelOf(T data);
int levelOf(NodeTree<T> * node, T data, int level);
int height();
int height(NodeTree<T> * node, int height);
List<T> leafs();
};
NodeTree.h
template<class T>
class NodeTree {
private:
T data;
NodeTree * left;
NodeTree * right;
public:
NodeTree();
NodeTree(T data);
~NodeTree();
T getData();
void setData(T value);
NodeTree * getLeft();
void setLeft(NodeTree<T> * left);
void setLeft(NodeTree<T> left);
NodeTree * getRight();
void setRight(NodeTree<T> * right);
void setRight(NodeTree<T> right);
};
HuffmanNode is implemented like this:
struct HuffmanNode {
char data;
int frequency;
bool operator==(HuffmanNode other) { return this->data == other.data; }
bool operator==(char data) { return this->data == data; }
bool operator!=(HuffmanNode other) { return this->data != other.data; }
bool operator!=(char data) { return this->data != data; }
bool operator<(HuffmanNode other) { return frequency < other.frequency; }
bool operator<=(HuffmanNode other) { return frequency <= other.frequency; }
bool operator>(HuffmanNode other) { return frequency > other.frequency; }
bool operator>=(HuffmanNode other) { return frequency >= other.frequency; }
HuffmanNode operator++() { this->frequency++; return *this; }
HuffmanNode operator++(int) { this->frequency++; return *this; }
HuffmanNode operator--() { this->frequency--; return *this; }
HuffmanNode operator--(int) { this->frequency--; return *this; }
friend ostream &operator<<( ostream &output, const HuffmanNode &node ) { output << node.data << " ( " << node.frequency << " ) "; return output; }
friend istream &operator>>( istream &input, HuffmanNode &node ) { input >> node.data >> node.frequency; return input; }
};
typedef struct HuffmanNode HuffmanNode;
Anyone can tell me what I am doing wrong here?
full code: https://pastebin.com/5dfHRhLe
UPDATE
After some searches, I change my code based on the answers I found here and here. The second one, I am using the 2 functions exactly as they are show in the answer. I try adapt the first one to my use case, but I suspect that is something wrong.
For write the file, I have this:
getCode(&encodeTable, toEncode.getRoot());
if (output.is_open()) {
List<HuffmanNode> list = toEncode.preOrder();
vector<bool> bits;
for(int i=1; i<=list.size(); i++) {
HuffmanNode node = list.get(i)->getData();
if(node.data == 0x0)
bits.push_back(true);
else
bits.push_back(false);
}
cout << endl;
binary_write(output, bits);
for(long unsigned int i=1; i<=bits.size(); i++) {
HuffmanNode node = list.get(i)->getData();
if(node.data != 0x0) {
char c = node.data;
output.write(&c, sizeof(c));
}
}
input.clear();
input.seekg(0, ios::beg);
string encoded_file = "";
char c;
while (input.get(c))
if(encodeTable.get(c) != nullptr)
encoded_file = encoded_file + encodeTable.get(c)->getValue();
if(encoded_file.length() % 8 != 0)
encoded_file = encoded_file + getSubstring(encoded_file.length() % 8);
for(long unsigned int i=0; i<encoded_file.length(); i+=8) {
string data = encoded_file.substr(i, 8);
bitset<8> b(data);
unsigned long x = b.to_ulong();
unsigned char c = static_cast<unsigned char>( x );
output.write(reinterpret_cast<char*>(&c), sizeof(c));
}
}
for read the bits from the file, I have that:
string coded_file = "";
if (input.is_open()) {
vector<bool> bits;
binary_read(input, bits);
toDecode.insert(HuffmanNode());
NodeTree<HuffmanNode> * temp = toDecode.getRoot();
for(long unsigned int i=1; i<bits.size();) {
if(bits[i++]) {
temp->setLeft(NodeTree<HuffmanNode>());
temp = temp->getLeft();
} else {
char c;
input.read(&c, sizeof(c));
HuffmanNode node;
node.data = c;
temp->setLeft(NodeTree<HuffmanNode>(node));
}
if(bits[i++]) {
temp->setRight(NodeTree<HuffmanNode>());
temp = temp->getRight();
} else {
char c;
input.read(&c, sizeof(c));
HuffmanNode node;
node.data = c;
temp->setRight(NodeTree<HuffmanNode>(node));
}
}
char c;
while(input.read(reinterpret_cast<char*>(&c), sizeof(c))) {
bitset<8> b(c);
coded_file = coded_file + b.to_string();
}
}
getCode(&decodeTable, toDecode.getRoot());
