Hi, I have a question realted to C++, I am trying to implement the HuffmanTree::
ID: 3686598 • Letter: H
Question
Hi,
I have a question realted to C++, I am trying to implement the HuffmanTree::HuffmanHeap::HuffmanHeap(istream &instr){} function and is having difficulties at the end of the function when I have to create struct TreeNodes for each element in the vectors like the following:
Store the content of vector pV that contains the priorities (i.e 4 1 2 8) into the protected 'priority' member in Heap class
Store the content of vector wordV that contains the line of format '<word> <code>' (i.e LedZeppelin 001 Nirvana 1 Queen 01 TheBeatles 0001) into the string * word member in TreeNode
So the treeNode in content[0] of the Heap<TreeNodes*> will have a *word == LedZeppelin 001 and priority==4.
and store these TreeNodes into the vector<TreeNode* > content in the Heap class.
I want to use a function void push(T data, unsigned int priority) that is provided in the class Heap to add the nodes to the vector<TreeNode* > content but doesn't seem to work.. Just wondering where I did wrong! Or should I use other methods to approach the problem?? I pasted the code below and added //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!PROBLEM!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! where I think the problem is, Thanks a lot!!!
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
#include <iostream>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
//QUESTION 1 - 0 credit
// ----- HuffmanHeap(istream &) --------
// constructor from an input file: a TreeNode is constructed for every node in the input file
// with no children and with priority equal to the frequency of the word in the file
HuffmanTree::HuffmanHeap::HuffmanHeap(istream &instr) {
//Store the first word from the istream
string wstr;// A string to store the whole line from the istream
getline(instr,wstr);// store the whole line into a string
string element;//string to store the element
vector<string> v;// for storing each element
int vp=0;// storing the position of vector
cout<<wstr.size()-1<<endl;
// for storing all elements into a vector so its easier to compare
for(int j=0;j<wstr.size()+1;j++){
if(wstr[j]==' '){// if the loop reaches to a white space or the end of the string
v.push_back(element);//store element into the vector
element="";//clear element
//cout<<element<<endl;//For checking
}else if(j == wstr.size()){
cout<<j<<endl;
v.push_back(element);
}else{
element+=wstr[j];
}
//cout<<j<<endl;
}
string same;
vector<string> compare=v;// for storing vector to count from
//Clearing away the replicated elements
sort( v.begin(), v.end() );
v.erase( unique( v.begin(), v.end() ), v.end() );
vector<int> pV;//Vector for storing the priorities
vector<string> codeV;// for storing the code
//Count the number of same elements
int count=0;// for counting the number of same elements in the string
string code;// the string to stoe the code
for(auto i:v){//loop though the vector withough replication
count=0;
for(auto j:compare){//loop through the vector with replicated elements and count
if(i==j){
count++;
}
}
pV.push_back(count);//for storing the number of counts
// Change the count to binary
while (count!=0) {// when the number of counts does not equal to 0
if(count%2==0){//if the number can be divided by 2
code+="0";
count=count/2;
} else {//if number cannot be divided by 2
code+="1";
count=count/2;
}
}
//store code into vector
codeV.push_back(code);
code="";
}
vector<string> wordV;//for storing in the format of <word> <code>.
for(int i=0;i<v.size();i++){
string temp;//temp for storing string <word> <code>
temp+= v[i] + " " +codeV[i];
wordV.push_back(temp);
}
//CHECKING
for(auto e:wordV){
//for(int i = 0;i<=v.size();i++){
cout<<e<<endl;// print out he whole string
}
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!PROBLEM!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//Store the content of vector pV that contains the priorities of the bands (i.e 4 1 2 8) into the protected 'priority' member in Heap class
//Store the content of vector wordV that contains the line of format '<word> <code>'
// (i.e LedZeppelin 001 Nirvana 1 Queen 01 TheBeatles 0001) into the string * word member in TreeNode
for(int i = 0;i<wordV.size();i++){
TreeNode t;// Create a treeNode for storing
string temp1 =wordV[i];
t.word = new string(temp1); //store the address storing '<word> <code>'in vector into string *word
Heap<TreeNode *> h;//Create a heap for storing the treeNodes
h.push(&t,pV[i]); /////WHY ERROR???
}
//PROBLEM: all the priorities are 8....can only access node member on an object of type 'HuffmanTree::HuffmanHeap'
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
}
class HuffmanTree {// dont need to write, just understand
private:
// ----- TreeNode ------
// A node in the Huffman Tree
struct TreeNode {
// ---------
// links to children. these are nullptr is any of the children is non-existent
TreeNode* children[2];
// ---------
// link to the string representation of the word
string *word;
// ---------
// --------- TreeNode() --------
// default constructor : all links are nullptr
TreeNode() {
children[0] = children[1] = nullptr;
word = nullptr;
}
// ---------
// --------- TreeNode(string) --------
// children are nullptr both, and word is a link to a new string
TreeNode(string s) {
word = new string(s);
children[0] = children[1] = nullptr;
}
// ---------
// --------- TreeNode(string) --------
// children are nullptr taken from the params(could be nullptr) and
// the word is a nullptr
TreeNode(TreeNode *t1, TreeNode *t2) {
word = nullptr;
children[0] = t1;
children[1] = t2;
}
// ---------
// --------- TreeNode(string) --------
// copy constructor
TreeNode(const TreeNode &t) {
if( t.children[1] != nullptr) children[0] = new TreeNode(*t.children[0]);
if( t.children[1] != nullptr) children[1] = new TreeNode(*t.children[1]);
if( t.word != nullptr) word = new string(*t.word);
}
// --------- ~TreeNode() --------
// destructor - deallocates the memory at the node and its descendants
~TreeNode() {
if (word != nullptr) delete word;
if (children[0] != nullptr) delete children[0];
if (children[1] != nullptr) delete children[1];
}
};
// ----- HuffmanHeap --------
class HuffmanHeap : Heap<TreeNode *> {
public:
// -----
// ----- HuffmanHeap(istream &) --------
// constructor from an input file: a TreeNode is constructed for every node in the input file
// with no children and with priority equal to the frequency of the word in the file
HuffmanHeap(istream &); //Q1 TODO
// -----
// ----- pop() --------
// removes the items with the two highest priorities, creates a new TreeNode with these two items as children and no string content, and adds this new Node in the heap with priority equal to the sum of the priorities of the two removed nodes.
// does not do anything if the number of elements is less than 2
void pop(); //TODO
// -----
// ----- lastElement() -----
// returns the top element when the heap has only one element
// EXEPT: throws 1 if the number of elements is not 1
TreeNode* lastElement() {
if (content.size() != 1) throw 1;
return *(content[0]->data);
}
// -----
// ----- hasOneElementLeft() -----
// returns true only if the heap has one element
bool hasOneElementLeft() const {
return (content.size() == 1);
}
};
// -----
TreeNode *root; //the root of the tree
TreeNode *iter; //an iterator that keeps track of a moving position in the tree
// ----
public:
// ----
// ---- HuffmanTree(const HuffmanCode &) -----
// constructor builds a tree that corresponds to the codes given as parameter
// EXCEPT: throws 1 if the code is not a prefix code
// EXCEPT: throws 2 if the codes are not all sequences of 0s and 1s
HuffmanTree(const HuffmanCode &); //TODO
// ----
// ---- HuffmanTree(istream &) -----
// constructor builds a tree from a file containing a block of text. It builds a Huffman Heap
// and pops from it until only one element is left
HuffmanTree(istream &input) {
HuffmanHeap h(input);
while(!h.hasOneElementLeft()) {
h.pop();
}
root = h.lastElement();
iter = root;
}
// ----
// ---- HuffmanTree(const HuffmanTree &) ----
// copy constructor
HuffmanTree(const HuffmanTree &h) {
root = new TreeNode(*h.root);
iter = root;
}
// ----
// ---- resetIterator() ----
// moves iterator back to the root
void resetIterator() {
iter = root;
}
// ----
// ---- moveDownOnZero() ----
// moves iterator down a 0 branch
// EXCEPT: throws 0 if no such branch exists
void moveDownOnZero() {
if (iter->children[0] == nullptr) throw 0;
iter = iter->children[0];
}
// ----
// ---- moveDownOnOne() ----
// moves iterator down a 1 branch
// EXCEPT: throws 1 if no such branch exists
void moveDownOnOne() {
if (iter->children[1] == nullptr) throw 1;
iter = iter->children[1];
}
// ----
// ---- getWordFromIter() ----
// returns a pointer to the string corresponding to
// the iterator
// EXCEPT: throws 2.0 if no such string exists
const string *getWordFromIter() const{
if ( iter->word == nullptr) throw 2.0;
return iter->word;
}
// ----
// ---- dfs(HuffmanCode& hc, TreeNode *tn, string &s) ----
// performs dfs starting at node tn. The string keeps track of the branches one has
// to follow from the root to this node. It adds to hc all leaf nodes
//
void dfs(HuffmanCode& hc, TreeNode *tn, string &s);
// ----
// ---- getCode() ----
// returns a HuffmanCode corersponding to the current HuffmanTree
HuffmanCode getCode() {
HuffmanCode toRet;
string ss("");
dfs(toRet, root, ss);
return toRet;
}
};
template <class T>
class Heap {
protected:
// ----
// Nodes
struct Node {
unsigned int priority;
const T *data;
};
// ----
// Content -> pointers to nodes
vector<Node *> content;
typedef typename vector<Node *>::size_type heapIndex;
// default constructor
// ---- map of existing Nodes
unordered_map<T, Node> items;
// default constructor
// ---- private methods
void swap(Node* &a, Node* &b);
void heapifyUp(heapIndex);
void heapifyDown(heapIndex);
// ----
public:
// ---------
// default constructor
Heap() {} //default constructor
// ---------
// ----- top() ------
// returns the element with best priority
// EXEPT: throws 0 if the heap is empty
T top() const;
// ---------
// ----- empty() ------
// returns true only if there are no elements in the heap
bool empty() const;
// ---------
// ----- push(T, unsigned int) -----
// inserts the element 'data' in the heap with the given priority
// the method performs heapify up
// if item is already there, will not push it again.
void push(T data, unsigned int priority);
// ---------
// ----- pop() -----
// removes the top element and heapifies down the last element in the heap.
// does not do anything if the heap is empty
void pop();
// ---------
// ----- operator[] ----
// returns the priority of the element
// EXEPT: throws 0 if the heap does not contain that element
unsigned int operator[](T) const;
};
// -------------------------------------------- //
// ---------------HEAP IMPLEMENTATION----------- //
// -------------------------------------------- //
template <class T>
void Heap<T>::swap(Node* &a, Node* &b){
Node *tmp;
tmp = a;
a = b;
b = tmp;
}
template <class T>
void Heap<T>::heapifyUp(Heap<T>::heapIndex index) {
// base case and invalid input
if (index == 0 || index >= content.size()) return;
// get items to compare
auto &child = content[index];
auto indexParent = (index - 1) / 2;
auto &parent = content[indexParent];
// swap if heap property is violated
if(child->priority < parent->priority){
swap(child, parent);
// recursively heapify up the item at index of parent
heapifyUp(indexParent);
}
}
template <class T>
void Heap<T>::heapifyDown(Heap<T>::heapIndex index) {
// save length
auto length = content.size();
// ----
// base case
if (2 * index + 1 >= length ) return;
// ----
// find index of best priority
auto indexOfBest = index;
auto indexLeft = 2*index + 1;
auto indexRight = 2*index + 2;
// if priority of left child is better than the current best, update best
if (content[indexLeft]->priority < content[indexOfBest]->priority) {
indexOfBest = indexLeft;
}
// ----
// if right child exists and its priority is better than the current best, update best
if (indexRight < length &&
content[indexRight]->priority < content[indexOfBest]->priority) {
indexOfBest = indexRight;
}
// ----
// if bestIndex changed, swap content at the best index with the index of the parent
if (indexOfBest != index) {
swap(content[indexOfBest], content[index]);
// recursively heapify down content
heapifyDown(indexOfBest);
}
}
template <class T>
T Heap<T>::top() const {
if(empty()) throw 0;
return *(content[0]->data);
}
template <class T>
bool Heap<T>::empty() const { return content.empty(); }
template <class T>
void Heap<T>::push(T data, unsigned int priority) {
// if item is already there, will not push it again.
if (items.find(data) != items.end()) return;
auto insertionResult = items.insert(make_pair(data, Node()));
if (!insertionResult.second) return;
// get the insertion result
const T &insertedString = insertionResult.first->first;
Node &insertedNode = insertionResult.first->second;
// set data
insertedNode.data = &insertedString;
// set priority
insertedNode.priority = priority;
// push the Node at the end of the content list
content.push_back(&insertedNode);
// the heap priority might be violated. Use heapify up to fix this
heapifyUp(content.size()-1);
}
template <class T>
void Heap<T>::pop() {
// save the data at the top
auto toRet = content.front()->data;
// store data at the last element to the top
content.front() = content.back();
//remove the item from the map
items.erase(items.find(*toRet));
// remove the last element in content
content.pop_back();
// heapify down the top element
heapifyDown(0);
}
template <class T>
unsigned int Heap<T>::operator[](T s) const {
// search for element and return the priority
auto item = items.find(s);
if (item != items.end()){
return item->second.priority;
} else throw 0;
}
int main() {
// test the dfs method
string simple = "TheBeatles TheBeatles LedZeppelin LedZeppelin Queen TheBeatles LedZeppelin TheBeatles TheBeatles LedZeppelin TheBeatles TheBeatles TheBeatles Nirvana Queen";
istringstream syrup(simple);
cout << "-------------------------------" << endl;
cout << "- Testing dfs... -" << endl;
cout << "-------------------------------" << endl;
HuffmanTree htSimple(syrup);
//HuffmanCode hcDFS = htSimple.getCode();// HuffmanCode is in a map format
/*for(auto entry : hcDFS) {
cout << entry.first << " " << entry.second << endl;// first is the <word>, second is the <code>
}
cout << "- The output should be the following, or the negative (0s replaced with ones)-" << endl;
cout << "LedZeppelin 01 Nirvana 000 Queen 001 TheBeatles 1" << endl;
*/
return 0;
}
Explanation / Answer
Hello user! I will try to help you in this situation of yours, quite a long code to read! :D
This kind of question are complicated because of the amount of code it needs to be read and analyzed, and you probably need to post this code as individual questions... Nevertheless, I read some of the code where you think there is the problem, and I noted some unusual code:
"Heap<TreeNode *> h;//Create a heap for storing the treeNodes
h.push(&t,pV[i]); /////WHY ERROR???"
This declaration is in a loop(for), it is intentional of you to create wordV.size() number of heaps? Because it seems that you are creating N heaps, each one with only one pushed element.
If tried to compile your code and it gave several errors, but maybe it is my own compiler version. If you have any doubts or breakthrough about it, I would love to hear about it! :D Have a nice day.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.