Cool, Many thanks I'm back in business!!
"Adriano Dal Bosco" <adbosco@kais.kyoto-u.ac.jp> wrote in message
news:c7052k$msh$1@caraway.media.kyoto-u.ac.jp...[color=blue]
> 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[/color]
size_t),[color=blue]
> 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][/color]
=[color=blue]
> currentString;
>
> or you can just keep it as it is and change the type of Represented to[/color]
int.[color=blue]
>
> 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" <slick_mick_00@hotmail.com> wrote in message
> news:c6u9le$g8r$1@sparta.btinternet.com...[color=green]
> > Guys,
> > I'm trying to compile this code to build a huffman tree, but I'm getting[/color][/color]
a[color=blue][color=green]
> > runtime error and my degugger ends up somewhere in the STL files. What[/color][/color]
am[color=blue]
> i[color=green]
> > 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);
> > }
> > }
> >
> >[/color]
>[/color]
