Michael,
Karthik had the right hint. Represented not only happens to be a char
(and you are using it as an index to a vector -- which should be a size_t),
but worse, you allow it to assume values out of range to your vector. The
problem is here:
if(Represented != -1) v[Represented] = currentString;
I don't understand the conversion very well, but it will run if you only
change the above line to:
if(Represented < -1) v[Represented] = currentString;
or:
if(Represented > -1) v[Represented] = currentString;
(and I guess this gives the result you want)
or even:
if((Represented != -1) && (size_t(Represented) < v.size())) v[Represented] =
currentString;
or you can just keep it as it is and change the type of Represented to int.
This solves this problem, but I think other may appear further on.
Especially because you are using new to allocate memory, but you are not
deleting the new objects anywhere. Another problem is that you are not
defining a copy constructor and an assignment operator. This produce
surprising restults in many cases. The problem is that you have pointer
members and if you don't tell the compiler how to copy them, the compiler
will copy only their *addressess*.
So, I recomend that you define a destructor, a copy constructor and an
assignment operator for HuffmanNode.
Below is a code that compiles an runs withou errors (I just included some
extra headers and changed the type of Represented to int)
// -------------- start --------------------
#include <iostream>
#include <assert.h>
#include <vector>
#include <list>
#include <string>
using namespace std;
class HuffmanNode
{
public:
HuffmanNode* pLeft;
HuffmanNode* pRight;
int Represented;
float frequency;
HuffmanNode() : pLeft(NULL), pRight(NULL), Represented(-1),
frequency(-1) {}
void AddSubTreeToVector(vector<string>& v, string currentString);
};
int main()
{
list<HuffmanNode> nodes;
for(int i=0;i<256;i++)
{
HuffmanNode n;
n.Represented = i;
n.frequency = (i*i *10 )% 300;
nodes.push_back(n);
}
cout << "Populated Source List: " << nodes.size();
while(nodes.size() >1)
{
cout << "\n\tListSize: " << nodes.size();
HuffmanNode newNode;
newNode.pLeft = new HuffmanNode;
newNode.pRight = new HuffmanNode;
list<HuffmanNode>::iterator it;
list<HuffmanNode>::iterator smallest = nodes.begin();
//Find Smallest
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pLeft = *(smallest);
newNode.frequency = smallest->frequency;
nodes.erase(smallest);
//Find the next Snmallest
smallest = nodes.begin();
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pRight = *smallest;
newNode.frequency += smallest->frequency;
nodes.erase(smallest);
//Add the New Node
nodes.push_back(newNode);
}
HuffmanNode hmt = *(nodes.begin());
//Move Tree into vector for encoding:
vector<string> HuffmanCodes;
for(int i=0;i<256;i++)
{
string str;
HuffmanCodes.push_back(str);
}
hmt.AddSubTreeToVector(HuffmanCodes,"");
for(int i=0;i<256;i++)
{
string str = HuffmanCodes[i];
cout << i << ": " << str.c_str() << endl;
}
system("PAUSE");
}
void HuffmanNode::AddSubTreeToVector(vector<string>& v, string
currentString)
{
if(!this) return;
if(Represented != -1) v[Represented] = currentString;
//LeftSubTree
if(pLeft)
{
string LeftString;
LeftString = currentString;
LeftString.append("0");
pLeft->AddSubTreeToVector(v,LeftString);
}
//RightSubTree
if(pRight)
{
string RightString;
RightString = currentString;
RightString.append("0");
pRight->AddSubTreeToVector(v,RightString);
}
}
// -------------- end --------------------
"Michael" <sl***********@hotmail.com> wrote in message
news:c6**********@sparta.btinternet.com...
Guys,
I'm trying to compile this code to build a huffman tree, but I'm getting a
runtime error and my degugger ends up somewhere in the STL files. What am
i doing wrong. I appreciate its not effiecient/stylistic, etc, it was just
something i wanted to try
Thanks
Mike
#include <assert.h>
#include <vector>
#include <list>
using std::list;
using std::vector;
class HuffmanNode
{
public:
HuffmanNode* pLeft;
HuffmanNode* pRight;
char Represented;
float frequency;
HuffmanNode() : pLeft(NULL), pRight(NULL), Represented(-1),
frequency(-1) {}
void AddSubTreeToVector(vector<string>& v, string currentString);
};
int main()
{
list<HuffmanNode> nodes;
for(int i=0;i<256;i++)
{
HuffmanNode n;
n.Represented = i;
n.frequency = (i*i *10 )% 300;
nodes.push_back(n);
}
cout << "Populated Source List: " << nodes.size();
while(nodes.size() >1)
{
cout << "\n\tListSize: " << nodes.size();
HuffmanNode newNode;
newNode.pLeft = new HuffmanNode;
newNode.pRight = new HuffmanNode;
list<HuffmanNode>::iterator it;
list<HuffmanNode>::iterator smallest = nodes.begin();
//Find Smallest
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pLeft = *(smallest);
newNode.frequency = smallest->frequency;
nodes.erase(smallest);
//Find the next Snmallest
smallest = nodes.begin();
for(it = nodes.begin();it != nodes.end();it++)
if(it->frequency <= smallest->frequency) smallest = it;
*newNode.pRight = *smallest;
newNode.frequency += smallest->frequency;
nodes.erase(smallest);
//Add the New Node
nodes.push_back(newNode);
}
HuffmanNode hmt = *(nodes.begin());
//Move Tree into vector for encoding:
vector<string> HuffmanCodes;
for(int i=0;i<256;i++)
{
string str;
HuffmanCodes.push_back(str);
}
hmt.AddSubTreeToVector(HuffmanCodes,"");
for(int i=0;i<256;i++)
{
string str = HuffmanCodes[i];
cout << i << ": " << str.c_str() << endl;
}
system("PAUSE");
}
void HuffmanNode::AddSubTreeToVector(vector<string>& v, string
currentString)
{
assert(this);
if(Represented != -1) v[Represented] = currentString;
//LeftSubTree
if(pLeft)
{
string LeftString;
LeftString = currentString;
LeftString.append("0");
pLeft->AddSubTreeToVector(v,LeftString);
}
//RightSubTree
if(pRight)
{
string RightString;
RightString = currentString;
RightString.append("0");
pRight->AddSubTreeToVector(v,RightString);
}
}