Huffman Trees

Implement getHuffCodes() function.

It takes as input a vector of CFreq structs (defined in header) and returns a vector of CCodes (also defined in header).

Note that there are two stages to getting character codes for a given set of characters:

1. Build the Huffman Tree
2. Assign Codes to each character (some ambiguity here - can always flip 0 and 1 and get another acceptable set of codes). The tests take this into account. The one hard condition for Huffman Codes is that no code is a prefix of another Huffman codes are prefix-free codes.

Read the code - both the unit tests (targetgtest.cpp and program4.cpp)

You may put all your code in program4.h or separate into separate files.

• I will overwrite your targetgtest.cpp and CMakeLists.txt file.
• I will not overwrite anything else in that directory.

You may use any standard library function that doesn't build the Huffman trees or trivialize the problem for you. Specifically, I am suggesting that you remember or consider that:

• you may use std::priority_queue
• you need to use std::vector at least for input and output
• you may use a stack if you like (or recursion) for assigning codes

Building and running

tar -xzvf Program_4_350.tar.gz
cd Program_4_350
mkdir build && cd build
cmake ..
make
./runUnitTests

Starter code:

#ifndef PROGRAM4_H
#define PROGRAM4_H

#include < string>
#include < vector>
#include < algorithm>
#include < queue>
#include < stack>

typedef struct char_freq{
char c;
double freq;

char_freq(char c, double freq)
:c(c),
freq(freq)
{}
} CFreq;

typedef struct char_code{
char c;
std::string code;
char_code(char c, std::string code)
:c(c),
code(code)
{}
} CCode;


//input: vector of CFreqs
//returns: vector of CCodes
std::vector< CCode> getHuffCodes(std::vector< CFreq > cfs){

//can define in separate .cpp file (make this into declaration)
//or define everything here (nothing in targetgtest.cpp)

//following is for compilation purposes
std::vector< CCode> codes;
return codes;
}

#endif //PROGRAM4_H