Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 2983
  • Last Modified:

Using a queue for Huffman code

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
Zorniac
Asked:
Zorniac
  • 4
1 Solution
 
ZorniacAuthor Commented:
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
 
ozoCommented:
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
 
ZorniacAuthor Commented:
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 Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
ZorniacAuthor Commented:
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
 
Infinity08Commented:
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
 
ZorniacAuthor Commented:
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

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now