Huffman

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#include "huffman.h"

#define DEBUG 0

typedef int data_t;
typedef int bst_key_t;

typedef struct bin_node_t {
    data_t data;
    bst_key_t key;
    struct bin_node *left;
    struct bin_node *right;
} bin_node;

typedef struct bst_tag {
    bin_node *root;
    int tree_size;
} bst;


//-----------Functions for binary trees

// creates a binary tree and returns a pointer to it
bst *bst_construct()
{
    bst *L;
    L = (bst *) malloc(sizeof(bst));
    L->root = NULL;

    L->tree_size = 0;

    return L;
}

// function to tear down binary tree
void bst_destruct(bst *tree)
{
    while(tree->root != NULL)
    {
        bin_node *node;
        node = tree->root;
        while(node->left != NULL && node->right != NULL)
        {
            if(node->left != NULL) node = (bin_node *)node->left;
            if(node->right != NULL) node = (bin_node *)node->right;
        }
        free(node);
        node = NULL;
    }
    free(tree);
    tree = NULL;
}



// function to insert node into tree
int bst_insert(bst *tree, int *chars, int *char_freqs)
{
    bin_node *new;
    bin_node node_array[256];
    int i, j, k;

    //if our tree is empty, create new node and set it as root
    /*
    if(tree->root == NULL)
    {
        new = (bin_node *)malloc(sizeof(bin_node));
        new->right = NULL;
        new->left = NULL;
        new->key = char_frequency;
        new->data = character;

        tree->root = new;
        tree->size++;

        return 1;
    }
    */

    // create a node out ot every char[] index
    for(i=0;i<256;i++)
    {
        node_array[i].key = char_freqs[i];
        node_array[i].data = chars[i];
        node_array[i].left = node_array[i].right = NULL;
    }

    // loop through every index of the array, sorting as we go through
    for(i=0;i<256;i++)
    {
        // if frequency is 0, don't add that node to the tree
        if(node_array[i].key == 0) continue;

        // combine the first two nodes of array
        new = (bin_node *)malloc(sizeof(bin_node));
        new->right = &node_array[i+1];
        new->left = &node_array[i];
        new->key = node_array[i].key + node_array[i+1].key;
        new->data = -1;
        // find the point that the next key is not equal to or less
        // than the current key, save that index in j
        j = i+1;
        while(new->key <= node_array[j+1]->key)
            j++;

        // shift every element of array from j down to zero down
        // by one index
        for(k=0;k<j;k++)
            node_array[k] = node_array[k+1];

        // put our new node in the slot we just opened up by shifting
        node_array[j] = new;


    }
}








//-----------END Functions for binary trees




// function prints off the contents of the frequency array
void printUnsortedFreq(int *freq)
{
    int i;
    printf("\nFREQUENCIES:\n");
    for(i=0;i<256;i++)
    {
        printf("Character %d occurs %d times\n", i, freq[i]);
    }
    printf("END FREQUENCIES\n\n");
}

// function to print of sorted frequency array
void printSortedFreq(int *freq, int *chars)
{
    int i;
    printf("\nSORTED FREQUENCIES:\n");
    for(i=0;i<256;i++)
    {
        printf("Character %c occurs %d times\n",chars[i],freq[i]);
    }
}

// function to find the max value of an array
// used for sorting the frequencies of characters
// from largest to smallest
int findMax(int *freq)
{
    int max = 0;
    int i;
    for(i=0;i<256;i++)
    {
        if(freq[i] > max)
            max = i;
    }
    return max;
}

// function to find the min value of an array
// used for sorting the frequencies of characters
// from smallest to largest
int findMin(int *freq)
{
    int min = 256;
    int i;
    for(i=0;i<256;i++)
    {
        if(freq[i] < min)
            min = i;
    }
    return min;
}

int main(int argc, char *argv[])
{
    FILE *fptInput, *fptOutput;
    int i;
    int freq[256];          // freq is an array that holds the
                            // frequencies of the 256 different possible values
    int sortedFreq[256];    // array to hold the sorted list of frequencies
    int sortedChars[256];   // array to hold the sorted characters themselves,
    int newSortedFreq[256];
    int newSortedChars[256];
                            // from most common to least common
    char currentChar;       // holds the most recently read character from
                            // the input file
    int max;                // placeholder for return of findMax()

    // make sure correct command line arguments
    if(argc != 3)
    {
        printf("Error, not enough command line arguments.\n");
        printf("Usage: ./huffman [-c or -d] [filename]\n");
        exit(0);
    }

    // open input file from command line and check for correctness
    if((fptInput=fopen(argv[2], "rb"))==NULL)
    {
        printf("Error opening file %s \n",argv[2]);
        exit(0);
    }

    // initialize freq, sortedFreq, and sortedChars
    for(i=0;i<256;i++)
    {
        freq[i] = sortedFreq[i] = sortedChars[i] = 0;
    }
    // printUnsortedFreq(freq);



    // use string compare to see if we're in compress mode
    if(!strcmp(argv[1],"-c"))
    {
        printf("You've selected compress mode.\n");

        // while there are still bytes to be read, read in a byte,
        // and increment the frequency of that byte
        while(fread(&currentChar, 1, 1, fptInput))
        {
            freq[(int)currentChar]++;
            if(DEBUG) printf("Character %c has a value %d and occurs %d times\n",
                currentChar, (int)currentChar, freq[(int)currentChar]);

        }\

        // run through each element of the frequency array, and sort from most
        // common to least common
        for(i=0;i<256;i++)
        {
            max = findMax(freq);
            sortedFreq[i] = freq[max];
            sortedChars[i] = max;
            freq[max] = 0;
        }

        // reverse array
        for(i=0;i<256;i++)
        {

            newSortedFreq[255-i] = sortedFreq[i];
            newSortedChars[255-i] = sortedChars[i];
        }


        // printUnsortedFreq(freq);
        // printSortedFreq(newSortedFreq, newSortedChars);

    // use string compare to see if we're in decompress mode
    } else if(!strcmp(argv[1],"-d"))
    {
        printf("You've selected decompress mode.\n");

    // if the second command line argument isn't -c or -d, then there
    // was a usage error
    } else
    {
        printf("Error. Incorrect input flags, must be -c or -d.\n");
        printf("Usage: ./huffman [-c or -d] [filename]\n");
    }

    // close files we opened
    fclose(fptInput);
}