?
Solved

Using a queue for Huffman code

Posted on 2009-04-09
6
Medium Priority
?
2,982 Views
Last Modified: 2012-05-06
Hello,

I am working on creating a Huffman Code (tree).  I currently read all symbols and frequencies from a file into Nodes, stored in an array of node *'s, then I sort the array based on frequency and push the sorted nodes into a queue.  Now when I try to combine the Nodes I receive and error.  I pop the first to nodes from queue and have temp vairables for them, I create a new node and combine the frequencies and alpha characters.  However when I try to push the new node back into the queue I receive error message: "deque iteration not referencable".  
Please tell me how I can fix this, so that I can pop and push to the same queue?
I created another queue and I am able to push the node * to that queue, so I know it is a problem with accessing the same queue I am popping from.  Can someone tell me how I can push a node * back into the same queue?

// Proj 5 Huffman Code.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <iomanip>
#include <queue>
#define ARRAYSIZE 26
using namespace std;
struct treeNode
{
	char alpha[ARRAYSIZE];
	float freq;
	int level;
	struct treeNode *leftPtr, *rightPtr, *parent;
};
typedef struct treeNode TreeNode;
typedef TreeNode *TreeNodePtr; 
TreeNodePtr rootPtr = NULL; 
treeNode * node_position[ARRAYSIZE];
FILE *fp;
queue<treeNode*> q;
queue<treeNode*> huff;
void insertSymbols(); //creates leaf nodes and stores in pointer array
void sortArray(struct treeNode * node_position[]); //sort the array of node pointers
void printSortedArray(struct treeNode * node_position[]); //prints symbols and freq. read from symbol.txt file
void enQueue(struct treeNode * node_position[]); //insert nodes into queue
void createHuff();
int _tmain(int argc, _TCHAR* argv[])
{
	insertSymbols();
	sortArray(node_position);
	printSortedArray(node_position);
	//enQueue(node_position);
	createHuff();
	return 0;
}
void sortArray(struct treeNode * node_position[])//sort the array
{
	int pass; //pass counter
	int c; //comparison counter
	treeNode * hold;  //temp locaion to swap elements
	for(pass=0; pass<ARRAYSIZE; pass++)
	{
		for(c=0; c<ARRAYSIZE-1; c++)
		{
			if(node_position[c]->freq>node_position[c+1]->freq)
			{
				hold=node_position[c];
				node_position[c]=node_position[c+1];
				node_position[c+1]=hold;
			}
		}
	}
}
void printSortedArray(struct treeNode * node_position[])
{
	int i;
	for(i=0; i<ARRAYSIZE; i++)
	{
		cout<<"Symbol is:  "<<node_position[i]->alpha<<"\t"<<"Frequency is:  "<<node_position[i]->freq<<endl;
	}
}
void insertSymbols()
{
	int i;
	fp = fopen("N:\\symbol.txt", "r");
	for(i=0; i<ARRAYSIZE; i++)
	{		
		struct treeNode * treePtr;
		treePtr = (struct treeNode *) malloc (sizeof(treeNode));
		fscanf(fp, "%s", &treePtr->alpha);
		fscanf(fp, "%f", &treePtr->freq);
		node_position[i]=treePtr;
	}
}
void enQueue(struct treeNode * node_position[])
{
	int i;
	for(i=0; i<ARRAYSIZE; i++)
	{		
		q.push(node_position[i]);
	}
	return ;
}
void createHuff()
{
	treeNode *temp1, *temp2;
	treeNode *treePtr;
	
	while (!q.empty())
	{
		temp1=q.front();
		q.pop();
		temp2=q.front();
		q.pop();
		
		treePtr = (struct treeNode*) malloc (sizeof(treeNode));
 
		if(rootPtr==NULL)
			rootPtr=treePtr;
 
		temp1->parent=treePtr;
		temp2->parent=treePtr;
		treePtr->leftPtr=temp1;
		treePtr->rightPtr=temp2;
		strcpy(treePtr->alpha, temp1->alpha);
		strcat(treePtr->alpha,temp2->alpha);
		treePtr->freq=temp1->freq+temp2->freq;
		rootPtr=treePtr;
		q.push(treePtr); /*this causes a problem*/
	                      /*huff.push(treePtr); I can successfully push to this queue*/
	}
}

Open in new window

symbol.txt
0
Comment
Question by:Zorniac
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
6 Comments
 
LVL 1

Author Comment

by:Zorniac
ID: 24111730
I had this function called commented out //enQueue(node_position);
but it shouldn't have been I was experimenting when I posted the question.  Please uncomment if you try to compile
0
 
LVL 84

Expert Comment

by:ozo
ID: 24111990
I don't think you want to push the new node into a queue,
you want the  nodes in order of size, so a heap may be a more appropriate data structure than  a queue
0
 
LVL 1

Author Comment

by:Zorniac
ID: 24112296
I found the problem on line 97, when i only had one element in the queue, I was attempted to do two pops.  this was caused by the while loop logic being set to while( !q.empty()), I changed this to
while(q.size>1). I am able to consolidate all nodes into one tree and all alpha symbols to my rootPtr.
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 1

Author Comment

by:Zorniac
ID: 24112323
I think they may be out of order, I need to make a drawing and then see how the tree comes out by hand
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24135822
Just a note about this :

>>                 strcpy(treePtr->alpha, temp1->alpha);
>>                 strcat(treePtr->alpha,temp2->alpha);

Are you sure that the alpha field's size (25 characters) is big enough to hold these concatenations ? Be careful to avoid buffer overflows.
0
 
LVL 1

Accepted Solution

by:
Zorniac earned 0 total points
ID: 24197771
I fixed the initial problem by changing the while loop logic.  I corrected the tree's nodes being out of order, by sorting the queue until there was only one node left in the queue.  popped two elements, combined them, push new node to the queue, moved queue elements to the array, sorted the array and requed all elements in the array, started pops over again.

Infininty, yes, you are right, seems like I should have been one character short, however when all nodes are combined I am able to hold the string concatenation.  I am not sure why this worked.
In case anyone is interested here is my completed code
3/11/2009
Project 5 Huffman Code Tree*/
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <queue>
#define ARRAYSIZE 26
#define NUMNODES 51
#define MAXPATH 10
using namespace std;
char outFile[40];
char symbolFile[40];
char bitFile[40];
struct treeNode
{
	char alpha[ARRAYSIZE];
	int path[9];
	float freq;
	int level;
	struct treeNode *leftPtr, *rightPtr, *parent;
};
typedef struct treeNode TreeNode;
typedef TreeNode *TreeNodePtr; 
TreeNodePtr rootPtr = NULL;
TreeNodePtr treePtr=NULL;
treeNode * node_position[ARRAYSIZE];
treeNode * levelArray[NUMNODES];
treeNode * leafArray[ARRAYSIZE];
FILE *fp;
queue<treeNode*> q;
queue<treeNode*> levelQ;
void insertSymbols(); //creates leaf nodes and stores in pointer array
void sortArray(struct treeNode * a[]); //sort the array of node pointers
void printSortedArray(struct treeNode * a[]); //prints symbols and freq. read from symbol.txt file
void enQueue(struct treeNode * a[]); //insert nodes into queue
void createHuff(); //combines leaf nodes into Huffman Tree
void moveToArray(); //moves queue to array after every two pops; called from createHuff
void inOrder(TreeNodePtr treePtr); //prints huffman tree inOrder
void bfs(treeNode* pNode); //gets all nodes from tree and copies mem addr to array
void setLevel(treeNode * levelArray[]); //sets nodes level and prints nodes in level order
void readBitFile(); //reads binary pattern from file and outputs text
void startGetLeaves(treeNode* node);
void getLeavesRecur(treeNode* node, int path[], int pathLen);//
void goRight(treeNode * node, int path[], int pathLen);//tracks huff code
void goLeft(treeNode * node, int path[], int pathLen);//tracks huff code
void getLeaves(treeNode * node, int ints[], int len);//captures leafs to * array
void alphabetizeArray(treeNode *leafArray[]);//sorts leafs in alpha order
void printHuffCode(treeNode * leafArray[]);//prints symbols and code
int _tmain(int argc, _TCHAR* argv[])
{
	ofstream myout;
	cout<<"Enter FULL path to OUTPUT file."<<endl;
	cin>>outFile;
	cout<<"Enter FULL path to SYMBOL file."<<endl;
	cin>>symbolFile;
	cout<<"Enter FULL path to bit file."<<endl;
	cin>>bitFile;
	myout.open(outFile, ios::app);
	insertSymbols();
	sortArray(node_position);
	printSortedArray(node_position);
	enQueue(node_position);
	createHuff();
	myout<<endl<<"The inOrder traversal is:"<<endl;
	cout<<endl<<"The inOrder traversal is:"<<endl;
	inOrder( rootPtr);
	bfs(rootPtr);
	myout<<endl<<"Printing the tree in levelOrderTraversal"<<endl;
	cout<<endl<<"Printing the tree in levelOrderTraversal"<<endl;
	setLevel(levelArray);
	startGetLeaves(rootPtr);
	alphabetizeArray(leafArray);
	printHuffCode(leafArray);
	readBitFile();	
	myout.close();
	return 0;
}
void sortArray(struct treeNode * a[])//sort the array
{
	int pass; //pass counter
	static int count = 0;
	int c; //comparison counter
	treeNode * hold;  //temp locaion to swap elements
	for(pass=0; pass<ARRAYSIZE-count; pass++)
	{
		for(c=0; c<ARRAYSIZE-count-1; c++)
		{
			if(a[c]->freq>a[c+1]->freq)
			{
				hold=a[c];
				a[c]=a[c+1];
				a[c+1]=hold;
			}
		}
	}
	count++;
}
void printSortedArray(struct treeNode * a[])
{
	int i;
	ofstream myout;
	myout.open(outFile, ios::app);
	for(i=0; i<ARRAYSIZE; i++)
	{
		if(a[i]!=NULL)
		{			
			myout<<"Symbol is:  "<<a[i]->alpha<<"\t"<<"Frequency is:  "<<a[i]->freq<<endl;
			cout<<"Symbol is:  "<<a[i]->alpha<<"\t"<<"Frequency is:  "<<a[i]->freq<<endl;
		}
	}
	myout.close();
}
void insertSymbols()
{
	int i;
	fp = fopen(symbolFile, "r");
	for(i=0; i<ARRAYSIZE; i++)
	{	
		treePtr = new treeNode;
		treePtr->leftPtr=treePtr->rightPtr=treePtr->parent=NULL;
		fscanf(fp, "%s", &treePtr->alpha);
		fscanf(fp, "%f", &treePtr->freq);
		node_position[i]=treePtr;
	}
	fclose(fp);
}
void enQueue(struct treeNode * a[])
{
	int i;
	for(i=0; i<ARRAYSIZE; i++)
	{	
		if(a[i]!=NULL)
		{
			q.push(a[i]);
			a[i]=NULL;
		}
	}
}
void createHuff()
{
	treeNode *temp1, *temp2;
	while(q.size()>1)
	{
		temp1=q.front();
		q.pop();
		temp2=q.front();
		q.pop();
		treePtr = new treeNode;	
		treePtr->leftPtr=treePtr->rightPtr=treePtr->parent=NULL;
		temp1->parent=temp2->parent=treePtr;
		treePtr->leftPtr=temp1;
		treePtr->rightPtr=temp2;
		strcpy(treePtr->alpha, temp1->alpha);
		strcat(treePtr->alpha,temp2->alpha);
		treePtr->freq=temp1->freq+temp2->freq;
		q.push(treePtr);
		moveToArray();
		sortArray(node_position);
		printSortedArray(node_position);
		enQueue(node_position);		
	}
	rootPtr=treePtr;
	rootPtr->level=0;
}
void moveToArray()
{
	int i;
	for(i=0; i<ARRAYSIZE; i++)
	{
		if(!q.empty())
		{
			node_position[i]=q.front();
			q.pop();
		}
		else
			node_position[i]=NULL;
	}
}
void inOrder( TreeNodePtr treePtr )
{
	ofstream myout;
	myout.open(outFile, ios::app);
	if ( treePtr != NULL ) 
	{
		inOrder( treePtr->leftPtr );
		myout<<"Frequency:    "<<treePtr->freq<<"  Symbol:  "<<treePtr->alpha<<endl;
		cout<<"Frequency:    "<<treePtr->freq<<"  Symbol:  "<<treePtr->alpha<<endl;
		inOrder( treePtr->rightPtr );
   } 
	myout.close();
}
void bfs(treeNode* pNode)
{  
	int inc=0;
	levelQ.push(pNode);
	while (!levelQ.empty())
	{
		pNode = levelQ.front();
		if (pNode->leftPtr)
			levelQ.push(pNode->leftPtr);
		if (pNode->rightPtr)
			levelQ.push(pNode->rightPtr);
		levelArray[inc]=levelQ.front();
		inc++;
		levelQ.pop();
	}
}
void setLevel(treeNode * levelArray[])
{
	int i;
	ofstream myout;
	myout.open(outFile, ios::app);
	for(i=0; i<NUMNODES; i++)
	{		
		if(levelArray[i]->parent!=NULL)
			levelArray[i]->level=levelArray[i]->parent->level+1;
		myout<<"At level "<<levelArray[i]->level<<":   Symbol:  "<<levelArray[i]->alpha<<endl;		
		cout<<"At level "<<levelArray[i]->level<<":   Symbol:  "<<levelArray[i]->alpha<<endl;
	}
	myout<<endl;
	myout.close();
	cout<<endl;
}
void startGetLeaves(treeNode* node) { 
  int path[MAXPATH]; 
  getLeavesRecur(node, path, 0); 
} 
void getLeavesRecur(treeNode* node, int path[], int pathLen) { 
  if (node==NULL) return; 
  
  // it's a leaf, so print the path that led to here 
  if (node->leftPtr==NULL && node->rightPtr==NULL) 
	  getLeaves(node, path, pathLen); 
 
  else 
  { 
	  // otherwise try both subtrees
	  goLeft(node, path, pathLen);
	  goRight(node, path, pathLen);
  } 
} 
void getLeaves(treeNode * node, int ints[], int len) { 
  int i;
  static int c=0;  
  leafArray[c]=node;
  c++;
  for (i=0; i<len; i++) 
  {
	  node->path[i]=ints[i];
  } 
} 
void goLeft(treeNode * node, int path[], int pathLen)
{
	path[pathLen]=0;
	pathLen++;
	getLeavesRecur(node->leftPtr, path, pathLen);
}
void goRight(treeNode * node, int path[], int pathLen)
{
	path[pathLen]=1;
	pathLen++;
	getLeavesRecur(node->rightPtr, path, pathLen);
}
void alphabetizeArray(treeNode *leafArray[])
{
	int pass; //pass counter
	static int count = 0;
	int c; //comparison counter
	treeNode * hold;  //temp locaion to swap elements
	for(pass=0; pass<ARRAYSIZE; pass++)
	{
		for(c=0; c<ARRAYSIZE-1; c++)
		{
			if(leafArray[c]->alpha>leafArray[c+1]->alpha)
			{
				hold=leafArray[c];
				leafArray[c]=leafArray[c+1];
				leafArray[c+1]=hold;
			}
		}
	}	
}
void printHuffCode(treeNode * leafArray[])
{			
	int i, j;
	ofstream myout;
	myout.open(outFile, ios::app);
	for(i=0; i<ARRAYSIZE; i++)
	{
		myout<<"symbol:  "<<leafArray[i]->alpha<<" "<<"HuffmanCode:  ";
		cout<<"symbol:  "<<leafArray[i]->alpha<<" "<<"HuffmanCode:  ";
		
		for(j=0; j<9; j++)
		{
			if((leafArray[i]->path[j]==1)|(leafArray[i]->path[j]==0))
			{
				myout<<leafArray[i]->path[j];
				cout<<leafArray[i]->path[j];
			}
		}
		myout<<endl;
		cout<<endl;
	}
	myout<<"symbol:  "<<rootPtr->alpha<<" "<<"HuffmanCode:  "<<endl;
	cout<<"symbol:  "<<rootPtr->alpha<<" "<<"HuffmanCode:  "<<endl;	
	myout.close();
}
void readBitFile()
{
	char item;
	treePtr=rootPtr;
	fp = fopen(bitFile, "r");
	ofstream myout;
	myout.open(outFile, ios::app);
	myout<<endl;
	cout<<endl;
	while(!feof((fp)))
	{
		fscanf(fp, "%c", &item);
		if(item=='0')
		{
			treePtr=treePtr->leftPtr;
			if((treePtr->leftPtr==NULL)&&(treePtr->rightPtr==NULL))
			{
				myout<<treePtr->alpha;
				cout<<treePtr->alpha;
				treePtr=rootPtr;
			}
		}
		if(item=='1')
		{
			treePtr=treePtr->rightPtr;
			if((treePtr->rightPtr==NULL)&&(treePtr->leftPtr==NULL))
			{
				myout<<treePtr->alpha;
				cout<<treePtr->alpha;
				treePtr=rootPtr;
			}
		}
		if(item=='.')
		{
			myout<<".  ";
			cout<<".  ";
			treePtr=rootPtr;
		}
		if(item==' ')
		{
			myout<<" ";
			cout<<" ";
			treePtr=rootPtr;
		}
		if(item=='-')
		{
			myout<<"-";
			cout<<"-";
			treePtr=rootPtr;
		}
		if(item==',')
		{
			myout<<", ";
			cout<<", ";
			treePtr=rootPtr;
		}	
	}
	myout<<endl;
	myout.close();
	fclose(fp);
	cout<<endl;
}

Open in new window

0

Featured Post

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

The following diagram presents a diamond class hierarchy: As depicted, diamond inheritance denotes when two classes (e.g., CDerived1 and CDerived2), separately extending a common base class (e.g., CBase), are sub classed simultaneously by a fourt…
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

719 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question