C++

Forum

 
problem with huffman tree recreation

globaltourist (201)
I have made up to this point a huffman compressor with the help from @TheIdeasMan
and now i am working on the decompressor.
I ran into a problem where i see the binary tree isn't created and i cant understand why?
-I freed all memory not in use so i dont think its heap fragmentation or leak.
-the std::map<char,std::vector<bool> > reads the key perfectly (i tested it and it does exactly what it needs to - assign a code to each char in key.bin).

the full code:
-look at reCreateTree()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
 
#include<iostream>
#include<fstream>
#include<map>
#include<algorithm>
#include<vector>
#include<string>
#include<time.h>
#include<deque>
#include<sstream>

struct node {
	char		m_data{};
	std::size_t m_frequency{};
	node*		m_left;
	node*		m_right;

	node() : m_left{ nullptr }, m_right{ nullptr } {}
	node(node* left, node* right) :m_left{ left }, m_right{ right } {
		m_frequency = m_left->m_frequency + m_right->m_frequency;
	}
};

struct functor {
	bool operator()(const node* one, const node* two) const { return one->m_frequency > two->m_frequency; }
};

class Huffman {
private:
	std::map<char, std::size_t>        m_freq_table;
	std::map<char, std::vector<bool> > m_key;
	std::vector<bool>                  m_code;
	std::deque<node*>                  m_nodeData;
	std::string                        m_fileName;
	std::string                        m_fileExten;
	std::string                        m_fileContent;
	node*                              m_root{ nullptr };

	/*shared functions*/
	void readFile(const std::string& filePath);
	template<class T>
	void release(T& arg) { arg.clear(); arg.shrink_to_fit(); }
	/*shared functions*/

	/*compressor related functions*/
	void storeFreqTable(const std::map<char, std::size_t>& table);
	void createBinaryFile(const std::string& filePath);
	void createKey(const std::string& filePath) const;
	void setNameAndExten(const std::string& filePath);
	void encode(const node* const &root);
	void deleteTree(node* root);
	void UpdateFreqTable();
	node* makeTree();
	/*compressor related functions*/

	/*decompressor related functions*/
	void readKey(const std::string& keyPath);
	void reCreateThree(const std::map<char,std::vector<bool> >& key);
	/*decompressor related functions*/

public:
	void compress(const std::string& filePath, const std::string& locToCreateKey, const std::string& locToCompress);
	void decompress(const std::string& filePath, const std::string& keyPath, const std::string& locToDecompress);
};

void Huffman::storeFreqTable(const std::map<char, std::size_t>& table) {
	for (auto&& index : table) {
		node* leaf = new node;
		leaf->m_data = index.first;
		leaf->m_frequency = index.second;
		m_nodeData.emplace_back(leaf);
	}//end of for loop
	m_freq_table.clear();
}

void Huffman::createBinaryFile(const std::string& filePath) {
	char offSet{}; char buffer{};
	std::ofstream outFile(filePath + m_fileName + "Compressed.bin", std::ios::binary);
	for (const auto& data : m_fileContent) {
		buffer = data;
		m_code = m_key[buffer];
		buffer = 0;
		for (const auto& index : m_code) {
			buffer |= index << (7 - offSet);
			++offSet;
			if (offSet == 8) {
				offSet = 0;
				outFile.put(buffer);
				buffer = 0;
			}//end of if
		}//end of for loop
	}//end of for loop
	outFile.close();
	release<std::vector<bool> >(m_code);
	release<std::string>(m_fileContent);
}

void Huffman::createKey(const std::string& filePath) const {
	std::ofstream key(filePath + m_fileName + "Key.bin", std::ios::binary);
	auto&& index = m_key.begin();
	do {
		key.put(index->first);
		key.put(' ');
		for (const auto& itr : index->second) {
			if (itr) key.put('1');
			else     key.put('0');
		}//end of for
		++index;
		if (index != m_key.end()) key.put(' ');
	} while (index != m_key.end());
	key << m_fileExten;
	key.close();
}

void Huffman::setNameAndExten(const std::string& filePath) {
	std::size_t foundName = filePath.find_last_of("/\\");
	std::size_t foundExten = filePath.find_last_of('.');
	m_fileName = filePath.substr(foundName + 1, foundExten - foundName - 1);
	m_fileExten = filePath.substr(foundExten);
}

void Huffman::readFile(const std::string& filePath) {
	std::ifstream inFile(filePath, std::ios::binary);
	auto const start_pos = inFile.tellg();
	inFile.ignore(std::numeric_limits<std::streamsize>::max());
	std::streamsize char_count = inFile.gcount();
	inFile.seekg(start_pos);
	m_fileContent = std::string(static_cast<std::size_t>(char_count), '0');
	inFile.read(&m_fileContent[0], static_cast<std::streamsize> (m_fileContent.size()));
	inFile.close();
}

void Huffman::encode(const node* const &root) {
	if (root->m_left != nullptr) {
		m_code.emplace_back(false);
		encode(root->m_left);
	}//end of if
	if (root->m_right != nullptr) {
		m_code.emplace_back(true);
		encode(root->m_right);
	}//end of if 
	if (root->m_data) m_key[root->m_data] = m_code;
	if (!m_code.empty()) m_code.pop_back();
}

void Huffman::deleteTree(node* root) {
	if (root != nullptr) {
		deleteTree(root->m_left);
		deleteTree(root->m_right);
		delete root;
	}//end of if
}

void Huffman::UpdateFreqTable() {
	for (const auto& data : m_fileContent) {
		m_freq_table[data]++;
	}//end of for loop
}

node* Huffman::makeTree() {
	while (m_nodeData.size() > 1) {
		std::sort(m_nodeData.begin(), m_nodeData.end(), functor());
		node* leftSon = m_nodeData.back();
		m_nodeData.pop_back();
		node* rightSon = m_nodeData.back();
		m_nodeData.pop_back();
		node* parent = new node(leftSon, rightSon);
		m_nodeData.emplace_back(parent);
	}//end of while loop
	m_nodeData.shrink_to_fit();
	return m_nodeData.front();
}

void Huffman::compress(const std::string& filePath,const std::string& locToCreateKey,const std::string& locToCompress) {
	setNameAndExten(filePath);
	readFile(filePath);
	UpdateFreqTable();
	storeFreqTable(m_freq_table);
	m_root = makeTree();
	encode(m_root);
	createBinaryFile(locToCompress);
	createKey(locToCreateKey);
	deleteTree(m_root);
	m_root = nullptr;
	release<std::string>(m_fileExten);
	release<std::string>(m_fileName);
}

void Huffman::readKey(const std::string& keyPath) {
	char buffer;
	readFile(keyPath);
	for (std::size_t index{}; index < m_fileContent.length(); index++) {
		buffer = m_fileContent[index];
		index += 2;
		do {
			if (m_fileContent[index] == '1')     m_code.emplace_back(true);
			else if(m_fileContent[index] == '0') m_code.emplace_back(false);
			++index;
		} while ((m_fileContent[index] != ' ') && (m_fileContent[index] != '.'));
		if (m_fileContent[index] == '.') {
			m_fileExten = m_fileContent.substr(index, (m_fileContent.length() - 1));
			index = m_fileContent.length();
		}//end of if
		else {
			m_key[buffer] = m_code;
			m_code.clear();
		}//end of else
	}//end of for
	release<std::string>(m_fileContent);
	release<std::vector<bool> >(m_code);
}

void print(node* root, unsigned k = 0) {
	if (root->m_left != nullptr) {
		print(root->m_left, k + 3);
		for (unsigned i = 0; i < k; i++) {
			std::cout << "--";
		}
		if (root->m_data) std::cout << "(" << root->m_data << ")" << '\n';
		print(root->m_right, k + 3);
	}
}

void Huffman::reCreateThree(const std::map<char, std::vector<bool> >& key) {
	m_root = new node;
	node* temp = m_root;
	for (auto&& index : key) {
		for (const auto& itr : index.second) {
			if (itr) {
				node* rightSon = new node;
				m_root->m_right = rightSon;
				m_root = m_root->m_right;
			}//end of if
			else {
				node* leftSon = new node;
				m_root->m_left = leftSon;
				m_root = m_root->m_left;
			}//end of else
		}//end of for
		m_root->m_data = index.first;
		m_root = temp;
	}//end of for
	if (m_root->m_right == nullptr) { std::cout << "no tree\n"; }
	else 
	print(m_root);
}

void Huffman::decompress(const std::string& filePath, const std::string& keyPath, const std::string& locToDecompress) {
	readKey(keyPath);
	reCreateThree(m_key);

}

int main() {
	clock_t tStart = clock();
	Huffman huff;
	Huffman dehuff;
	//huff.compress("C:/Users/User/Desktop/test.txt", "C:/Users/User/Desktop/", "C:/Users/User/Desktop/");
	dehuff.decompress("", "C:/Users/User/Desktop/testKey.bin","");
	std::cout << static_cast<double>(clock() - tStart) / CLOCKS_PER_SEC << "(s)" << '\n';
	return 0;
}
globaltourist (201)
the print function should show the tree that is created but if m_root->right is nullptr print "no tree" should be printed, however none shows.

testKey.bin file content:
001 d 000 e 011 h 010 l 10 o 111 r 1101 w 1100.txt

note:first character with code 001 is space.
Last edited on
TheIdeasMan (6817)
Hi,

Was the print function supposed to be a member function?

In if (root->m_left != nullptr) if root is a nullptr, I get a segfaut there. This happens after the 17th time print is called (on line 214), I guess that's when m_left is nullptr. Because it is not a member function, m_data is always NULL (\0) so nothing is printed.

I had a go at altering your code again ( ;+) ), this time to use a priority_queue and unique_ptr, it worked for the compression (I had sensible results in the files). However it doesn't seem to work for the decompression. In your version of reCreateTree, you are default constructing the nodes, so they get nullptr's. When the tree was created in the compression, the two children were created with their data, then they were used to emplace the parent, maybe try doing that again? I think the same thing is happening in my code

So, about what I did to change your code:

I gave node a move constructor and move assignment;
Made all the raw pointers std::unique_ptr;
Changed all the occurrences of new to std::make_unique<node> ;
Put std::move everywhere it was required;
Changed NodeData to std::priority_queue .

It looks a lot more complicated, but I have achieved the removal of new and raw pointers, which is apparently supposed to be a good thing. So now if any exceptions are thrown, we won't leak memory.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
 
#include<iostream>
#include<fstream>
#include<map>
#include<algorithm>
#include<vector>
#include<string>
#include<ctime>
#include<deque>
#include<sstream>
#include <memory>
#include<queue>

struct node {
  char		                m_data{};
  std::size_t                   m_frequency{};
  std::unique_ptr<node>         m_left;
  std::unique_ptr<node>		m_right;

  node (node&&) = default;
  node& operator=(node&&) = default;

  node() : m_left(), m_right() {}

  node(std::unique_ptr<node> left ,
       std::unique_ptr<node> right)
    :

    m_left{ std::move (left) },
    m_right{ std::move(right) }

  {
    m_frequency = m_left->m_frequency + m_right->m_frequency;
  }


};

struct functor {
	bool operator()(const node* one, const node* two) const { return one->m_frequency > two->m_frequency; }
};

class Huffman {
private:
	std::map<char, std::size_t>        m_freq_table;
	std::map<char, std::vector<bool> > m_key;
	std::vector<bool>                  m_code;
	std::queue<std::unique_ptr<node>>  m_nodeData;
	std::string                        m_fileName;
	std::string                        m_fileExten;
	std::string                        m_fileContent;
	std::unique_ptr<node>              m_root;

	/*shared functions*/
	void readFile(const std::string& filePath);
	template<class T>
	void release(T& arg) { arg.clear(); arg.shrink_to_fit(); }
	/*shared functions*/

	/*compressor related functions*/
	void storeFreqTable(const std::map<char, std::size_t>& table);
	void createBinaryFile(const std::string& filePath);
	void createKey(const std::string& filePath) const;
	void setNameAndExten(const std::string& filePath);
	void encode(const std::unique_ptr<node>& root);
	void deleteTree(std::unique_ptr<node> root);
	void UpdateFreqTable();
	std::unique_ptr<node> makeTree();
	/*compressor related functions*/

	/*decompressor related functions*/
	void readKey(const std::string& keyPath);
	void reCreateTree(const std::map<char,std::vector<bool> >& key);
	/*decompressor related functions*/

public:
	void compress(const std::string& filePath, const std::string& locToCreateKey, const std::string& locToCompress);
	void decompress(const std::string& filePath, const std::string& keyPath, const std::string& locToDecompress);
};

void Huffman::storeFreqTable(const std::map<char, std::size_t>& table) {
	for (auto&& index : table) {
		std::unique_ptr<node> leaf = std::make_unique<node>();
		leaf->m_data = index.first;
		leaf->m_frequency = index.second;
		m_nodeData.emplace(std::move(leaf) );
	}//end of for loop
	m_freq_table.clear();
}

void Huffman::createBinaryFile(const std::string& filePath) {
	char offSet{};
	char buffer{};

	std::ofstream outFile(filePath + m_fileName + "Compressed.bin", std::ios::binary);

	if (!outFile) {
	    std::cout << "File: for Compressed.bin not opened" << "\n";
	    std::exit(-1);
	  }

	for (const auto& data : m_fileContent) {
		buffer = data;
		m_code = m_key[buffer];
		buffer = 0;
		for (const auto& index : m_code) {
			buffer |= index << (7 - offSet);
			++offSet;
			if (offSet == 8) {
				offSet = 0;
				outFile.put(buffer);
				buffer = 0;
			}//end of if
		}//end of for loop
	}//end of for loop
	outFile.close();
	release<std::vector<bool> >(m_code);
	release<std::string>(m_fileContent);
}

void Huffman::createKey(const std::string& filePath) const {
	std::ofstream key(filePath + m_fileName + "Key.bin", std::ios::binary);

	if (!key) {
	    std::cout << "File for Key.bin not opened" << "\n";
	    std::exit(-1);
	  }

	auto&& index = m_key.begin();
	do {
		key.put(index->first);
		key.put(' ');
		for (const auto& itr : index->second) {
			if (itr) key.put('1');
			else     key.put('0');
		}//end of for
		++index;
		if (index != m_key.end()) {key.put(' ');}
	} while (index != m_key.end());
	key << m_fileExten;
	key.close();
}

void Huffman::setNameAndExten(const std::string& filePath) {
	std::size_t foundName = filePath.find_last_of("/\\");
	std::size_t foundExten = filePath.find_last_of('.');
	m_fileName = filePath.substr(foundName + 1, foundExten - foundName - 1);
	m_fileExten = filePath.substr(foundExten);
}

void Huffman::readFile(const std::string& filePath) {
	std::ifstream inFile(filePath, std::ios::binary);

	if (!inFile) {
	    std::cout << "Input File not opened" << "\n";
	    std::exit(-1);
	  }

	auto const start_pos = inFile.tellg();
	inFile.ignore(std::numeric_limits<std::streamsize>::max());
	std::streamsize char_count = inFile.gcount();
	inFile.seekg(start_pos);
	m_fileContent = std::string(static_cast<std::size_t>(char_count), '0');
	inFile.read(&m_fileContent[0], static_cast<std::streamsize> (m_fileContent.size()));
	inFile.close();
}

void Huffman::encode(const std::unique_ptr<node>& root) {
  if (root->m_left != nullptr) {
      m_code.emplace_back(false);
      encode(root->m_left);
    }//end of if
  if (root->m_right != nullptr) {
      m_code.emplace_back(true);
      encode(root->m_right);
    }//end of if
  if (root->m_data) {m_key[root->m_data] = m_code;}
  if (!m_code.empty()) { m_code.pop_back();}
}

//void Huffman::deleteTree(std::unique_ptr<node> root) {
//	if (root != nullptr) {
//		deleteTree(root->m_left);
//		deleteTree(root->m_right);
//		delete root;
//	}//end of if
//}

void Huffman::UpdateFreqTable() {
  for (const auto& data : m_fileContent) {
      m_freq_table[data]++;
    }//end of for loop
}

std::unique_ptr<node> Huffman::makeTree() {
  while (m_nodeData.size() > 1) {
      //std::sort(std::move(m_nodeData.begin() ), std::move (m_nodeData.end() ), functor());
      std::unique_ptr<node> leftSon = std::move (m_nodeData.front() );
      m_nodeData.pop();
      std::unique_ptr<node> rightSon = std::move ( m_nodeData.front() );
      m_nodeData.pop();
      auto parent = std::make_unique<node>(std::move(leftSon), std::move(rightSon) );
      m_nodeData.emplace(std::move(parent) );
    }//end of while loop
  //m_nodeData.shrink_to_fit();
  return std::move(m_nodeData.front() );
}

void Huffman::compress(const std::string& filePath,
		       const std::string& locToCreateKey,
		       const std::string& locToCompress)
{
	setNameAndExten(filePath);
	readFile(filePath);
	UpdateFreqTable();
	storeFreqTable(m_freq_table);
	m_root = std::move( makeTree() );
	encode(m_root);
	createBinaryFile(locToCompress);
	createKey(locToCreateKey);
//	deleteTree(std::move( m_root) );
	m_root = nullptr;
	release<std::string>(m_fileExten);
	release<std::string>(m_fileName);
}


TheIdeasMan (6817)
The rest of my version of your code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
void Huffman::readKey(const std::string& keyPath) {
	char buffer;
	readFile(keyPath);
	for (std::size_t index{}; index < m_fileContent.length(); index++) {
		buffer = m_fileContent[index];
		index += 2;
		do {
			if (m_fileContent[index] == '1')     m_code.emplace_back(true);
			else if(m_fileContent[index] == '0') m_code.emplace_back(false);
			++index;
		} while ((m_fileContent[index] != ' ') && (m_fileContent[index] != '.'));
		if (m_fileContent[index] == '.') {
			m_fileExten = m_fileContent.substr(index, (m_fileContent.length() - 1));
			index = m_fileContent.length();
		}//end of if
		else {
			m_key[buffer] = m_code;
			m_code.clear();
		}//end of else
	}//end of for
	release<std::string>(m_fileContent);
	release<std::vector<bool> >(m_code);
}

void print(std::unique_ptr<node> root, unsigned k = 0) {
	if (root->m_left != nullptr) {
		print(std::move( root->m_left ), k + 3);
		for (unsigned i = 0; i < k; i++) {
			std::cout << "--";
		}
		if (root->m_data ) std::cout << "(" << root->m_data << ")" << '\n';
		print(std::move( root->m_right ), k + 3);
	}
}

void Huffman::reCreateTree(const std::map<char, std::vector<bool> >& key) {
	m_root = std::make_unique<node>();
	std::unique_ptr<node> temp = std::move(m_root);
	for (auto&& index : key) {
		for (const auto& itr : index.second) {
			if (itr) {
				auto rightSon = std::make_unique<node>();
				m_root->m_right = std::move(rightSon);
				m_root = std::move(m_root->m_right);
			}//end of if
			else {
				auto leftSon =  std::make_unique<node>();
				m_root->m_left = std::move(leftSon);
				m_root = std::move(m_root->m_left);
			}//end of else
		}//end of for
		m_root->m_data = index.first;
		m_root = std::move(temp);
	}//end of for
	if (m_root->m_right == nullptr) { std::cout << "no tree\n"; }
	else
	print(std::move(m_root) );
}

void Huffman::decompress(const std::string& filePath, const std::string& keyPath, const std::string& locToDecompress) {
	readKey(keyPath);
	reCreateTree(m_key);

}

int main() {
	std::clock_t tStart = std::clock();
	Huffman huff;
	Huffman dehuff;
	huff.compress("elf.h", "/home/TheIdeasMan/projects/qt/Huffman/", "/home/TheIdeasMan/projects/qt/Huffman/");
	dehuff.decompress("", "/home/TheIdeasMan/projects/qt/Huffman/elfKey.bin","");
	std::cout << static_cast<double>(clock() - tStart) / CLOCKS_PER_SEC << "(s)" << '\n';
	return 0;
}
globaltourist (201)
Hello again! :)
Thanks for putting in your time !
I have read the code you wrote and it is a great solution to get rid of memory leaks but there is one problem, the key doesn't generate properly for example:
I have a file named
test.txt
with the only content being
hello world


In the code i posted the key would be:

001 d 000 e 011 h 010 l 10 o 111 r 1101 w 1100.txt


with your changes it is:

000 d 001 e 010 h 011 l 100 o 101 r 110 w 111.txt


the problem behind this imo is that you disabled the std::sort function in line 196 which was responsible for making a correct binary tree. Let me explain why:
lets say we have 4 elements inside our queue with frequencies in the following order:
21
3
45
2
without sort we would make 21 + 3 into a parent whereas the correct order should of been 2+3 = 5 than 5 + 21 =26 and lastly 26+45 = 71


+ I noticed a strange behavior with print in your program:
It straight up crashes the program if i put print(std::move(m_root)); after the maketree function (note: i forward declared print after the class Huffman)

remade print function to use inside compress:
1
2
3
4
5
6
7
8
9
10
11
 
void print(std::unique_ptr<node> root, unsigned k = 0) {
	if (root->m_left != nullptr) {
		print(std::move(root->m_left), k + 3);
		for (unsigned i = 0; i < k; i++) {
			std::cout << "--";
		}
		if (root->m_data) std::cout << root->m_frequency << "(" << root->m_data << ")\n";
		else std::cout << root->m_frequency << '\n';
		print(std::move(root->m_right), k + 3);
	}
}


while in the code i posted, the same function without the unique pointer would work perfectly
and print out the correct tree (in fact it was the way i tested if i made the tree correctly in the first place).

Was the print function supposed to be a member function?

no

When the tree was created in the compression, the two children were created with their data, then they were used to emplace the parent, maybe try doing that again? I think the same thing is happening in my code

I don't see a viable way to do it as if we were compressing because now we create individual branches that lead to characters and together they form a binary tree

Last edited on
TheIdeasMan (6817)
Hi,

I must be going mad in my old age !! I was trying to do a priority_queue (but just had queue instead) The PQ doesn't need a sort, because it happens every time there is an emplace. But I then got into a hell of a tangle trying to do that with unique_ptr. It seems there a quite a lot of restrictions on doing that.

I apologise, my suggestions aren't helping.

Some more questions though:

With this, everything is happening at the back, before there was pop_front and an emplace _back at the end. I see why now, you have reversed the functor. I hadn't realised that, so the last code I posted will be incorrect in that respect.

1
2
3
4
5
6
7
8
9
10
11
12
13
 
node* Huffman::makeTree() {
	while (m_nodeData.size() > 1) {
		std::sort(m_nodeData.begin(), m_nodeData.end(), functor());
		node* leftSon = m_nodeData.back();
		m_nodeData.pop_back();
		node* rightSon = m_nodeData.back();
		m_nodeData.pop_back();
		node* parent = new node(leftSon, rightSon);
		m_nodeData.emplace_back(parent);
	}//end of while loop
	m_nodeData.shrink_to_fit();
	return m_nodeData.front();
}


I don't see a viable way to do it as if we were compressing because now we create individual branches that lead to characters and together they form a binary tree


I meant starting at the root. At the moment, (with your code) IMO it crashed because of the default construction of the nodes - they set their members to nullptr. So I was saying create the first 2 children with their member data, and use them to make the root using the constructor taking 2 nodes as arguments.

Any way, good luck hopefully I won't lead you astray any further !

Regards :+)

Last edited on
TheIdeasMan (6817)
Hi,

I guess you will see this topic:

http://www.cplusplus.com/forum/general/214750/

In particular this part :

mbozzi wrote:

Also worth mentioning is that while new+delete are error prone, it wouldn't be too hard to do this with only raw pointers in an exception-safe manner: the only data carried by the nodes is POD, and (usually) nothing will throw in a fixed-size container of POD.


So you are probably quite correct in what you are doing, a Huffman node is only ever going to have a char and a frequency, so it looks as though the use of new will probably be fine :+)

I guess the thing is that if one was doing something else which had something which could throw, then it looks like one is better off with smart pointers.

At least this shows that my philosophy of wanting to use smart pointers wasn't completely wrong - it was just that I wasn't aware of the details.

Good Luck, hopefully others will answer as well if you have more questions.

Regards :+)
globaltourist (201)
Hello!
Thanks again for coming for the rescue :)

At least this shows that my philosophy of wanting to use smart pointers wasn't completely wrong - it was just that I wasn't aware of the details.

I fully agree with your philosophy and the only reason that i stick to new and delete is because i am fairly new to smart pointers and if i get into some nasty errors i will have no idea what to do :( BTW bought the book modern effective c++ had a look at smart pointers there it seems like everything is covered for 0-100% including what to use when and why.

I guess you will see this topic:

Viewed
globaltourist (201)
I have made some progress if it can be called so:
I made a separate program to "synthetically" make a test tree and print out the result.
Good news: it doesn't crash!
Bad news: it doesn't look like it should.

the program:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
#include<iostream>
#include<vector>
#include<map>

struct node {
	char		m_data{};
	std::size_t m_frequency{};
	node*		m_left;
	node*		m_right;

	node() : m_left{ nullptr }, m_right{ nullptr } {}
	node(node* left, node* right) :m_left{ left }, m_right{ right } {
		m_frequency = m_left->m_frequency + m_right->m_frequency;
	}
};

void print(node* root, unsigned k=0) {
	if (root != nullptr) {
		print(root->m_left, k + 3);
		for (unsigned i{}; i < k; i++) {
			std::cout << "  ";
		}//end of for
		if (root->m_data) std::cout << root->m_frequency << "(" << root->m_data << ")\n";
		else std::cout << root->m_frequency << '\n';
		print(root->m_right, k + 3);
	}//end of if
}

void release(std::vector<bool>& vec) {
	vec.clear();
	vec.shrink_to_fit();
}

node* m_root = new node;
node* temp = m_root;

int main() {
	std::map<char, std::vector<bool> > m_key;
	std::vector<bool> code;

	for (auto itr : { true,false,false,true }) {
		code.push_back(itr);
	}//end of for

	m_key['a'] = code;
	release(code);

	for (auto itr : { false,false,false,true }) {
		code.push_back(itr);
	}//end of for

	m_key['b'] = code;
	release(code);

	for (auto itr : { true,true,false,true }) {
		code.push_back(itr);
	}//end of for

	m_key['c'] = code;
	release(code);

	for (auto itr : { true,false,true,true }) {
		code.push_back(itr);
	}//end of for

	m_key['d'] = code;
	release(code);

	for (const auto& itr : m_key) {
		for (const auto& index : itr.second) {
			if (index) {
				node* right = new node;
				m_root->m_right = right;
				m_root->m_frequency = 1;
				m_root = m_root->m_right;
			}//end of if
			else {
				node* left = new node;
				m_root->m_left = left;
				m_root->m_frequency = 0;
				m_root = m_root->m_left;
			}//end of else
		}//end of for
		m_root->m_data = itr.first;
		m_root = temp;
	}//end of for

	print(temp);
	return 0;
}
globaltourist (201)
Never mind no help is needed atm, i solved the problem.
Once i finish the full code will be posted to help others.
Topic archived. No new replies allowed.