Using a queue for Huffman 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;
}

                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
336:
337:
338:
339:
340:
341:
342:
343:
344:
345:
346:
347:
348:
349:
350:
351:
352:
353:
354:
355:
356:
357:
358:
359:
360:
361:
362:
363:
364:
365:
366:
367:
368:
369:
370:
371:
372:
373: