/********************************************
*
* file d:\lsu\cujhuff2.c
*
********************************************/
#include "d:\lsu\cujhuff.h"
/*
create_huffman_code(item_array)
This routine is the top of the routines that create
the codes. Create the codes xxxxx010 for the characters
read in. You use the item_array which contains the
counts of occurances and so on.
*/
create_huffman_code (item_array)
struct item_struct item_array[];
{
int counter,
i,
not_ended;
struct item_struct temp;
sort_item_array(item_array);
disable_zero_counts(item_array);
/***********************************
*
* The following short loop is the
* heart of the algorithm. The
* rest is the implementation detail
* which is not trivial.
*
************************************/
counter = 0;
not_ended = 1;
while(not_ended){
if( (counter % 50) == 0) printf("\n> Creating code ");
printf(".");
combine_and_code_2_smallest_items(item_array, ¬_ended);
sort_item_array(item_array);
counter++;
} /* ends while not_ended */
reverse_order_of_coded(item_array);
} /* ends create_huffman_code */
/*
sort_item_array(item_array)
This is a very simple bubble sort algorithm.
It does use the Microsoft C ability to
set one struct equal to another. Some
compilers do not support this.
*/
sort_item_array(item_array)
struct item_struct item_array[];
{
int i,
not_finished,
swapped;
struct item_struct temp;
not_finished = 1;
while(not_finished){
swapped = 0;
for(i=0; i<LENGTH-1; i++){
if(item_array[i].count < item_array[i+1].count){
swapped = 1;
temp = item_array[i];
item_array[i] = item_array[i+1];
item_array[i+1] = temp;
} /* ends if you need to swap */
} /* ends loop over i */
if(swapped == 0)
not_finished = 0;
} /* ends while not_finished */
/* Perform an extra pass through the sort to
ensure all 'D'isbaled items are below all
'E'nabled items in the item_array */
not_finished = 1;
while(not_finished){
swapped = 0;
for(i=0; i<LENGTH-1; i++){
if( (item_array[i].indicator == 'D') &&
(item_array[i+1].indicator == 'E')){
swapped = 1;
temp = item_array[i];
item_array[i] = item_array[i+1];
item array[i+1] = temp;
} /* ends if you need to swap */
} /* ends loop over i */
if(swapped == 0)
not_finished = 0;
} /* ends while not_finished */
} /* ends sort_item_array */
/*
disable_zero_counts(item_array)
You do not want to work on the characters
that were not in the input file so you
disable them.
*/
disable_zero_counts(item_array)
struct item_struct item_array[];
{
int i;
for(i=0; i<LENGTH; i++){
if(item_array[i].count == 0)
item_array[i].indicator = 'D';
} /* ends loop over i */
} /* ends disable_zero_counts */
/*
combine_and_code_2_smallest_items(item_array, not_ended)
This function calls other functions to find the two
smallest items and then combine or link them.
*/
combine_and_code_2_smallest_items(item_array, not_ended)
struct item_struct item_array[];
int *not_ended;
{
char r[80];
int next_smallest, smallest;
find_smallest_item(item_array, &smallest);
if(smallest <= 0){
*not_ended = 0;
}
else{
next_smallest = smallest;
find_next_smallest_item(item_array, &next_smallest);
code_2_smallest_items(item_array, smallest, next_smallest);
combine_2_smallest_items(item_array, smallest,
next_smallest);
}
} /* ends combine_and_code_2_smallest_items */
/*
find_smallest_item(item_array, smallest)
You are working with a sorted item_array
so you start looking at the bottom of the
array. You look until you find the first
'E'nabled indicator then you stop.
*/
find_smallest_item(item_array, smallest)
struct item_struct item_array[];
int *smallest;
{
int i,
searching;
*smallest = 0;
searching = 1;
i = 255;
while(searching){
if(item_array[i].indicator == 'E'){
*smallest = i;
searching = 0;
} /* ends if indicator == 'E' */
else{
i = i-1;
if(i<0){
*smallest = -1;
searching = 0;
}
} /* ends else indicator != 'E' */
} /* ends while searching */
} /* ends find_smallest_item */
/*
find_next_smallest_item(item_array, next_smallest)
You are working with a sorted item_array
so you start looking at the smallest item of the
array. You look until you find the first
'E'nabled indicator then you stop.
*/
find_next_smallest_item(item_array, next_smallest)
struct item_struct item_array[];
int *next_smallest;
{
int i,
searching;
searching = 1;
i = *next_smallest-1;
while(searching){
if(item_array[i].indicator == 'E'){
*next_smallest = i;
searching = 0;
} /* ends if indicator == 'E' */
else{
i = i-1;
if(i<0){
*next_smallest = -1;
searching = 0;
}
} /* ends else indicator != 'E' */
} /* ends while searching */
} /* ends find_next_smallest_item */
/*
combine_2_smallest_items(...
. add the two counts together
. disable the smallest one
. link the smallest one to the next smallest one
*/
combine_2_smallest_items(item_array, smallest, next_smallest)
struct item_struct item_array[];
int next_smallest, smallest;
{
int i, not_finished;
item_array[next_smallest].count = item_array[smallest].count
+
item_array[next_smallest].count;
item_array[smallest].count = item_array[next_smallest].count;
item_array[smallest].indicator = 'D';
i = 0;
not_finished = 1;
while(not_finished){
if(item_array[next_smallest].includes[i] == 256){
item_array[next_smallest].includes[i] = smallest;
not_finished = 0;
}
else{
i++;
if(i > LLENGTH){
printf("\n\n> Ran out of links\n\n");
exit(1);
}
}
} /* ends while not_finished */
} /* ends combine_2_smallest_items */
/*
code_2_smallest_items (...
The smallest item is coded with a ONE
The next smallest item is coded with a ZERO
*/
code_2_smallest_items(item_array, smallest, next_smallest)
struct_item struct item_array[];
int next_smallest, smallest;
{
code_smallest_item(item_array, smallest);
code_next_smallest_item(item_array, next_smallest);
} /* code_2_smallest_items */
/*
code_smallest_item(item_array, smallest)
You must code the item as well as
all the other items included with it
on down to the end.
Set the code to ONE.
*/
code_smallest_item(item_array, smallest)
struct item_struct item_array[];
short smallest;
{
int i,
j,
k,
setting;
j = smallest;
setting = 1;
i = 0;
/* set code ONE */
while(setting){
if(item_array[j].coded[i] == OTHER) {
item_array[j].coded[i] = ONE;
setting = 0;
} /* ends if == OTHER */
else
i++;
} /* ends while setting */
/* Recursive calls */
for(k=0; k<LLENGTH; k++)
if(item_array[j].includes[k] != 256)
code_smallest_item(item_array,
item_array[j].includes[k];
} /* ends code_smallest_item */
/*
code_next_smallest_item(item_array, smallest)
You must code the item as well as
all the other items included with it
on down to the end.
Set the code to ZERO
*/
code_next_smallest_item(item_array, smallest)
struct item_struct item_array[];
short smallest;
{
int i,
j,
k,
setting;
j = smallest;
setting = 1;
i = 0;
/* set code ZERO */
while(setting){
if(item_array[j].coded[i] == OTHER){
item_array[j].coded[i] = ZERO;
setting = 0;
} /* ends if == OTHER */
else
i++;
} /* ends while setting */
/* Recursive calls */
for(k=0; k<LLENGTH; k++)
if(item_array[j].includes[k] != 256)
code_next_smallest_item(item_array,
item_array[j].includes[k]);
} /* ends code_next_smallest_item */
/*
reverse_order_of_coded(item_array)
Now trace backwards
*/
reverse_order_of_coded(item_array)
struct item_struct item_array[];
{
char temp;
int i, j;
for(i=0; i<LENGTH; i++){
if(item_array[i].coded[0] != OTHER){
for(j=0; j<(CODE_LENGTH/2); j++){
temp = item_array[i].coded[j];
item_array[i].coded[j] =
item_array[i].coded [CODE_LENGTH-1-j];
item_array[i].coded[CODE_LENGTH-1-j] = temp;
} /* ends loop over j */
} /* ends if coded[0] != OTHER */
} /* ends loop over i */
} /* reverse_order_of coded */
/* End of File */