Code:
/*************************************
* Filename: CSC310-Assignment5.cpp
* Description: Prompts the user for an input file, which is
* assumed to contain one character (including ' '), followed
* by a blank space, followed by a frequency number, on each
* line. A Huffman tree is then built from these values. Finally
* the user is prompted for an output file, which the program
* writes each char followed by a blank, followed by it's
* appropriate Huffman code, in asscending alphabetical order.
*************************************************************/
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
struct node
{
char key; int val;
node *left, *right, *next, *prev;
};
typedef node* node_ptr;
void add_tree(node_ptr &head, node_ptr &list);
/**************************************************
* Description: Creates a parent node from two smallest adjacent nodes on
* the list.
*************************************************/
void add_list(node_ptr &head, node_ptr &list, int value, int character);
/**************************************************
* Description: Adds nodes to a list with a character and number
* attached to each node.
*************************************************/
void sort_list(node_ptr &head, node_ptr &list);
/**************************************************
* Description: Sorts the nodes on the list directly via insertion
* sort. Ensures children links are maintained.
*************************************************/
void find_code(node_ptr &root, node_ptr &list, char matrix[][32]);
/**************************************************
* Description: Finds the Huffman code for each char that was read
* in and attached to the tree. Reads each char and it's adjacent
* code into matrix[][32]
*************************************************/
void sort_array(char a[], int size);
/**************************************************
* Description: Simply uses an insertion sort to sort a given
* array. In this case, the char array for refrencing when
* printing to file in alphabetical order.
*************************************************/
void print_matrix(char matrix[][32], int count, char a[]);
/**************************************************
* Description: Prints each char, followed by a space, followed
* by it's appropriate Huffman code, to a user designated output
* file in ascending alphabetical order.
*************************************************/
int main(void)
{
node_ptr root=NULL, list=NULL; // initialize root and list pointer
int v = 0,size = 0; // v = frequency #, size = number of characters in file
char ifilename[15];
char matrix[128][32]; // holds the chars with corresponding code for sorthing
char a[128]; // index of chars stored for refrencing
ifstream read;
/************ Prompt for input file & open stream **************************/
cout <<"Enter a file name to read from: ";
cin>> ifilename;
read.open(ifilename);
if (read.fail())
{
cout << "File not found, exiting..." << endl;
exit(1);
}
/** End file input stream opening **/
/************* read from file ********************************************/
while(read.get(a[size])) // read char into array
{
sort_array(a, size); // keep array sorted.
read.get(); // get the next char, which should be ' '
read >> v; // read the frequency number
add_list(root, list, v, a[size]); // add the node to the list
size++; // increment size
read.ignore(1,'\n');
}
read.close(); // read from stream finished, close stream
/*************** End read from file ***************************************/
/*************** Build Huffman tree from list *****************************/
while(list->next != NULL)
{
sort_list(root, list); // ensure 1st 2 nodes are the smallest on list...
add_tree(root,list); // ..if two are equal, node with a char is 1st
if(root->next == NULL)break; // breakes when the root is the only node left
}
/*************** Huffman tree building is complete *************************/
/************** Here, find each char in the tree and encode ***************/
find_code(root, list, matrix);
/***************** End encoding ********************************************/
/**************** Print to file ********************************************/
print_matrix(matrix, size, a);
/**************** End of print to file *************************************/
return 0;
}
void add_tree(node_ptr &head, node_ptr &list)
{
list = head; // set node to root
node_ptr tmp = new node; // create node to be used as parent node
tmp->key = 0; /* to avoid confusion, parent nodes will have an
escape sequence char (shouldnt be in a file) */
tmp->val = list->val + list->next->val; // set node's value to the sum of children
tmp->left = list; // connect smallest node to the left
tmp->right = list->next; /* connect the next node, which should be more or equal
to the right. */
tmp->right->prev = tmp; // point prev links of children nodes to parent
tmp->left->prev = tmp;
if(list->next->next != NULL)
{
/****** Disconnect children from list ***/
list = list->next->next;
list->prev->prev->prev = tmp;
list->prev->prev->next = NULL;
list->prev->prev = tmp;
list->prev->next = NULL;
list->prev = NULL;
head = list;
/**** cycle through list and connect parent to the end ***/
while(list->next != NULL)list = list->next;
list->next = tmp; tmp->prev = list; tmp->next = NULL;
}
else
{ // case if parent is last node on list
list->next->prev = NULL;
list->next = NULL;
head = tmp;
}
list = head;
}
void add_list(node_ptr &head, node_ptr &list, int value, int character)
{
if (!list) // if list is empty
{ // set val and key, and set as head
list = new node;
list->key = character;
list->val = value;
head = list;
list->next = NULL;
list->prev = NULL;
}
else
{
while (list->next != NULL) list = list->next; //cycle to end of list
node_ptr tmp = new node; // create new node
tmp->key = character; // set key and val
tmp->val = value;
list->next = tmp; // conenct previous node to new node
tmp->next = NULL; // next node == NULL
tmp->prev = list; // set prev link to previous node
}
}
void sort_list(node_ptr &head, node_ptr &list)
{
node_ptr temp; //pointer for sorting
node_ptr tmp = head; // set temp to head
/*********************************************************
* Begining with the 2nd node, cycle through the list until
* a node is encounered that is greater than the previous node.
* Then continue cycling back through the list changing links
* until the node is in it's correct place.
***********************************************************/
for (tmp = tmp->next; tmp; tmp = tmp->next)
{
list = tmp;
while(list->prev->val > list->val)
{
temp = list->prev;
temp->next = list->next;
if(temp->prev != NULL) //if temp is not at the beginning of the list
{
temp->prev->next = list; // set the previous link to list
list->prev = temp->prev; // set list's prev link to the node before temp
}
else
{
list->prev = NULL; // set list->prev to NULL
head = list; // point beginning of list to node
}
if(list->next != NULL) list->next->prev = temp; //sets next node prev to temp
temp->prev = list; // temp's previous link is pointing to list
list->next = temp; // list's next link is pointing to temp
if(!list->prev)break; // break if at beginning of list
}
}
}
void find_code(node_ptr &root, node_ptr &list, char matrix[][32])
{
char code[30]; //code for character to be encoded (30 bit implementation)
int count = 0; //counts # of lines needed in output file
for (int i = 0; list; i++)
{
if(list->left != NULL)
{
code[i] = '0'; // insert 0 in code when left branch is taken
list = list->left; // take left branch
}
else if(list->right != NULL) // should only evaluate to true if right is taken
{
code[i] = '1'; // insert 1 if right branch is taken
list = list->right; // take right branch
}
else // leaf is reached
{
if(list->key != 0) // only consider nodes containg chars other than 0
{
matrix[count][0] = list->key; // sets 1st element to char
matrix[count][1] = ' '; // sets 2nd element to blank space
for (int j = 2; j < i + 2; j++)
{
matrix[count][j] = code[j-2]; // adds huffman code to adjacent char
matrix[count][j+1] = '\0'; // ensures '/0' is in the correct position
}
count++;
}
if(code[i-1] == '0') // delete leftmost node if it was read
{
list->prev->left = NULL;
delete list;
}
else if (list->prev == NULL) // breaks if last node is root
break;
else // delete right node if it was read
{
list->prev->right = NULL;
delete list;
}
i = -1; //sets i to 0 on next run
list = root; // set list pointer to top of tree
}
}
}
void sort_array(char a[], int size)
{
/** Simple insertion sort to sort array of characters for file output ***/
int temp = 0, j = 0;
for (int i = 0; i < size; i++)
{
temp = a[i]; j = i;
while( a[j-1] > temp)
{
a[j] = a[j - 1];
j--;
}
a[j] = temp;
}
}
void print_matrix(char matrix[][32], int count, char a[])
{
ofstream write;
char ofilename[15]; // output file name
/**** Prompt user for output file ***/
cout << "Enter an output file to write to: ";
cin >> ofilename;
/***** End Output file prompt ******/
/*** Open Output File ****/
write.open(ofilename);
if(write.fail())
{
cout << "Error encountered!" << endl;
exit(1);
}
/*** End File Opening ****/
for (int i = 0; i < count; i++)
{
for (int j = count-1; j > -1; j--)
{
if (a[i] == matrix[j][0]) // cycle through matrix until equal to
{ // a[i]. Array a[i] is sorted.
for (int k = 0; matrix[j][k] != '\0'; k++)
write << matrix[j][k]; // output <char> <blankspace> <huffman code>
}
}
write << endl; // write new line
}
write.close(); // close output
}