In the file Huffman.cc, there are two ADTs defined. The first is the Huffman Tre
ID: 3684570 • Letter: I
Question
In the file Huffman.cc, there are two ADTs defined. The first is the Huffman Tree. The Huffman Tree has a very simple interface: there is only a constructor, but no other operations.
The Huffman Tree constructor take a FrequencyList as input. As we saw in lecture, the algorithm for building a Huffman Tree is discussed in the Hints below. Here’s the current constructor:
Your job is to complete this function.
Hints
The Huffman algorithm removes the two smallest trees in the list, and you can call remove_smallest() twice in a row. You have to create a new TreeNode record with these two tree records as subtrees, and put it into the list. Remember that each TreeNode stores a Frequency record. Each time you take two Treenodes out of the FrequencyList, you have to create a new Trenode with a new Frequency record; the new Frequency record needs a character, but the character is not important (use any character). Note: the frequency has to be the sum of the frequencies of the two TreeNodes you removed (the two smallest). When there is exactly record left in the list, it is the final tree, and you should return it.
There is an example of the algorithm visually on the Moodle page. There may be ties when seeking the two smallest trees; using any of the smallest trees is correct. The new TreeNode you create has 2 subtrees, but it doesn’t matter which one is left or right. For these reasons, there may be many correct Huffman trees for any given message.
Exercise Summary
1. Complete createHuffmanTree() constructor as indicated.
2. Build the testADT app, and run it.
3. If your code does the right things, tests 42-45 should all report "Passed."
What to hand in:
The file Huffman.cc containing your code for the constructor described above.
Grading
4 marks: createHuffmanTree() repeatedly removes the two smallest subtrees in the FrequencyList.
4 marks: createHuffmanTree() correctly builds a new TreeNode from these two subtrees.
2 marks: createHuffmanTree() correctly puts the new TreeNode into the FrequencyList.
2 marks: createHuffmanTree() correctly terminates when there is exactly 1 TreeNode in the FrequencyList.
2 marks: createHuffmanTree() correctly returns a newly allocated HuffmanTree record containing the TreeN- ode.
HUFFMAN.CC
// HuffmanTree
// HuffmanCodec
#include "LOCALE.h"
#include "Huffman.h"
#include "TreeNode.h"
#include "Frequency.h"
#include "List.h"
#include "FrequencyList.h"
#include "copy.h"
#include <cstring>
#include <iostream>
using namespace std;
// createHuffmanTree(frequencies)
// Pre: frequencies is a reference to a FrequencyList
// Post: allocates a new HuffmanTree record
// return: a reference to the Huffman tree, if the list is not empty
HuffmanTree *createHuffmanTree(FrequencyList *frequencies) {
// TODO: complete this function
return NULL;
}
// createHuffmanCodec(htree)
// Pre: htree is a reference to a HuffmanTree
// Post: allocates a new HuffmanCodec record
// return: a reference to the Huffman codec
HuffmanCodec *createHuffmanCodec(HuffmanTree *t) {
HuffmanCodec *hcdc = new HuffmanCodec;
hcdc->huffTree = t;
//initialize codebook
for (int i = 0; i < ASCII_SIZE; i++){
hcdc->codebook[i] = NULL;
}
// build the codebook using the Tree
char *acode = new char[height(t->root)+1];
find_codes(hcdc, t->root, acode, 0);
return hcdc;
}
// find_codes(codec,tree,store,index)
// recursively find Huffman codes from a given tree
// pre: codec is a reference to Huffman Codec
// tree is a reference to a TreeNode in the HuffmanTree
// store is a character array used to store partial solutions
// index is the next unused index in store
// post: the Huffman codes have been printed.
void find_codes(HuffmanCodec *hcdc, TreeNode *t, char s[], int d){
if (t == NULL){
return;
}
else if (isLeaf(t)){
s[d] = '';
hcdc->codebook[(int) getData(getData(t))] = copy(s);
}
else {
s[d] = '0';
find_codes(hcdc, getLeft(t), s, d+1);
s[d] = '1';
find_codes(hcdc, getRight(t), s, d+1);
}
}
// delete_huffman_helper(t)
// deallocate the huffman tree and frequency records
// Pre: t::refToTreeNode
// Post: the tree t and its subtrees have been deleted
// as well as their contents.
void delete_huffman_helper(TreeNode *t){
if (t == NULL){
return;
}
delete_huffman_helper(getLeft(t));
delete_huffman_helper(getRight(t));
//delete the Frequency record
delete getData(t);
//delete the current Tree node
delete t;
}
// DESTRUCTOR
// destroyHuffmanTree(ht)
// Pre: ht is a reference to a HuffmanTree
// Post: memory for ht is deallocated
void destroyHuffmanTree(HuffmanTree *ht){
delete_huffman_helper(ht->root);
delete ht;
}
// destroyHuffmanCodec(hcdc)
// Pre: hcdc is a reference to a HuffmanCodec
// Post: memory for ht is deallocated
void destroyHuffmanCodec(HuffmanCodec *hcdc){
destroyHuffmanTree(hcdc->huffTree);
for (int i = 0; i < ASCII_SIZE; i++){
if (hcdc->codebook[i] != NULL){
delete [] hcdc->codebook[i];
}
}
}
// encode(hcdc, message)
// encode a message using the Huffman Codec
// Pre: hcdc is a referene to a HuffmanCodec
// message:: a cstring to encode
// Return a cstring containing the encoded message
char *encode(HuffmanCodec *h, const char message[]){
// TODO: complete this function
return NULL;
}
// decode_char(tnode, message, d){
// decode one character from the message.
// Pre: tnode is a node in a huffman tree
// message:: cstring, the whole message to decode
// d:: a reference to an int containing the current
// index in the message
// Post: d has been increased by the number of 0s and 1s used to
// encode the character
// Return: the decoded character
char decode_char(TreeNode *t, char message[], int *d){
// TODO: complete this function
return '.'; // dot returned for no good reason
}
// decode(hcdc, message)
// decode the given message
// Pre: hcdc is a reference to a HuffmanCodec
// message:: cstring containing the coded message
// return: a reference to a cstring containing the decoded message
char *decode(HuffmanCodec *h, char message[]){
int d = 0; // index for the coded message
int i = 0; // index for the de-coded message
// Note: We've simplified by using a fixed size array
// we could estimate the length of the message
// more accurately than this by using the length
// of the message to decode and the tree height.
char *decoded_msg = new char[MESSAGE_LIMIT];
// go through the whole message
while (d < strlen(message)){
// decode one character using the Huffman Tree
decoded_msg[i] = decode_char(h->huffTree->root, message, &d);
i++;
}
// ensure the C-string is properly terminated
decoded_msg[i] = '';
// then make a copy
char *result = copy(decoded_msg);
delete [] decoded_msg;
return result;
}
// eof
Explanation / Answer
main.cpp
#include <iostream>
#include "List.h"
#include "TreeNode.h"
#include "Frequency.h"
#include "FrequencyList.h"
#include "Huffman.h"
using namespace std;
// function to make testing a little neater
// Pre: passed is a boolean which is true if the test passed, and false if it didn't
void testDecider(int *number, int *nFailed, bool passed,
const char *testannounce, const char *iffailed) {
*number += 1;
cout << "Test " << *number << ": " << testannounce;
if (passed) {
cout << "Passed!";
}
else {
*nFailed += 1;
cout << "Error: " << iffailed << " **** ";
}
cout << endl;
}
int testall(){
Frequency *freq_for_testing = createFrequency('f',5);
// test the frequency record
int testNumber = 0;
int testFailed = 0;
testDecider(&testNumber, &testFailed,
getData(freq_for_testing) == 'f',
"Frequency getData() ",
"inconsistent character stored in Frequency record");
setData(freq_for_testing,'g');
testDecider(&testNumber, &testFailed,
getData(freq_for_testing) == 'g',
"Frequency setData() ",
"setData() seemed to have no effect!");
testDecider(&testNumber, &testFailed,
getCount(freq_for_testing) == 5,
"Frequency getCount(): ",
"inconsistent count stored in Frequency record");
setCount(freq_for_testing,6);
testDecider(&testNumber, &testFailed,
getCount(freq_for_testing) == 6,
"Frequency setCount(): ",
"setCount() seemed to have no effect!");
if (testFailed > 10) return testFailed;
TreeNode *tree_for_testing = createTreeNode(freq_for_testing);
testDecider(&testNumber, &testFailed,
isLeaf(tree_for_testing),
"TreeNode isLeaf(): ",
"tree record should be a leaf, but isn't");
testDecider(&testNumber, &testFailed,
getData(tree_for_testing) == freq_for_testing,
"TreeNode getData(): ",
"tree record should contain the frequency object, but doesn't");
testDecider(&testNumber, &testFailed,
height(tree_for_testing) == 1,
"TreeNode height(): ",
"tree record should have height 1, but doesn't");
testDecider(&testNumber, &testFailed,
getLeft(tree_for_testing) == NULL,
"TreeNode getLeft(): ",
"Unexpected left subtree not NULL");
testDecider(&testNumber, &testFailed,
getRight(tree_for_testing) == NULL,
"TreeNode getRight(): ",
"Unexpected right subtree not NULL");
if (testFailed > 10) return testFailed;
TreeNode *another_tree = createTreeNode(createFrequency('x',12));
setRight(tree_for_testing, another_tree);
testDecider(&testNumber, &testFailed,
getRight(tree_for_testing) == another_tree,
"TreeNode setRight(): ",
"set right subtree failed");
another_tree = createTreeNode(createFrequency('q',314));
setLeft(tree_for_testing, another_tree);
testDecider(&testNumber, &testFailed,
getLeft(tree_for_testing) == another_tree,
"TreeNode setLeft(): ",
"set left subtree failed");
testDecider(&testNumber, &testFailed,
!isLeaf(tree_for_testing),
"TreeNode isLeaf(): ",
"tree record seems to be a leaf, but shouldn't be!");
testDecider(&testNumber, &testFailed,
height(tree_for_testing) == 2,
"TreeNode height(): ",
"tree record should have height 2, but doesn't");
if (testFailed > 10) return testFailed;
another_tree = getRight(tree_for_testing);
testDecider(&testNumber, &testFailed,
height(another_tree) == 1,
"TreeNode height(): ",
"tree record should have height 1, but doesn't");
setRight(tree_for_testing,NULL);
testDecider(&testNumber, &testFailed,
getRight(tree_for_testing) == NULL,
"TreeNode setRight(): ",
"tree record should have NULL right subtree, but doesn't");
testDecider(&testNumber, &testFailed,
height(tree_for_testing) == 2,
"TreeNode height(): ",
"tree record should still have height 2, but doesn't");
if (testFailed > 10) return testFailed;
List *list_for_testing = createList();
// check is empty?
testDecider(&testNumber, &testFailed,
isEmpty(list_for_testing),
"List isEmpty(): ",
"new list record should be empty, but isn't");
// check for zero elements
testDecider(&testNumber, &testFailed,
getNumElements(list_for_testing) == 0,
"List getNumElements(): ",
"new list record shold have zero elements, but doesn't");
// add tree to the list
testDecider(&testNumber, &testFailed,
insert(list_for_testing,tree_for_testing),
"List insert(): ",
"should have succeeded, but didn't!");
// test the tree record again
testDecider(&testNumber, &testFailed,
getNumElements(list_for_testing) == 1,
"List getNumElements(): ",
"new list record should have one element, but doesn't");
testDecider(&testNumber, &testFailed,
remove(list_for_testing, tree_for_testing),
"List remove(): ",
"remove() failed! ");
testDecider(&testNumber, &testFailed,
insert(list_for_testing,tree_for_testing),
"List insert(): ",
"should have succeeded, but didn't!");
// add another tree to the list
testDecider(&testNumber, &testFailed,
insert(list_for_testing,another_tree),
"List insert(): ",
"should have succeeded, but didn't!");
// test the tree record again
testDecider(&testNumber, &testFailed,
getNumElements(list_for_testing) == 2,
"List getNumElements(): ",
"new list record should have one element, but doesn't");
testDecider(&testNumber, &testFailed,
remove(list_for_testing, another_tree),
"List remove(): ",
"remove() failed! ");
testDecider(&testNumber, &testFailed,
insert(list_for_testing,another_tree),
"List insert(): ",
"should have succeeded, but didn't!");
// test the tree record again
testDecider(&testNumber, &testFailed,
getNumElements(list_for_testing) == 2,
"List getNumElements(): ",
"new list record should have one element, but doesn't");
if (testFailed > 10) return testFailed;
Iterator *lTrav_for_testing = createIterator(list_for_testing);
testDecider(&testNumber, &testFailed,
hasNext(lTrav_for_testing),
"Iterator hasNext(): ",
"there should be something in the list to look at, but isn't");
testDecider(&testNumber, &testFailed,
next(lTrav_for_testing) == tree_for_testing,
"Iterator next(): ",
"should have gotten the tree record, but didn't");
testDecider(&testNumber, &testFailed,
hasNext(lTrav_for_testing),
"Iterator hasNext(): ",
"there should be something in the list to look at, but isn't");
testDecider(&testNumber, &testFailed,
next(lTrav_for_testing) == another_tree,
"Iterator next(): ",
"should have gotten a tree record, but didn't");
testDecider(&testNumber, &testFailed,
!hasNext(lTrav_for_testing),
"Iterator hasNext(): ",
"there shouldn't be anything in the list to look at, but there is");
if (testFailed > 10) return testFailed;
// ----------------------------------------------
// Testing FrequencyList ADT
FrequencyList *flist = createFrequencyList("122333");
// check is empty?
testDecider(&testNumber, &testFailed,
!isEmpty(flist),
"FrequencyList isEmpty(): ",
"new frequency list record should not be empty, but seems to be");
testDecider(&testNumber, &testFailed,
getNumElements(flist) == 3,
"FrequencyList getNumElements(): ",
"new frequency list record should have 3 elements, but doesn't");
TreeNode *smallest = remove_smallest(flist);
testDecider(&testNumber, &testFailed,
getData(getData(smallest)) == '1',
"FrequencyList remove_smallest(): ",
"tried to find the smallest Frequency in the list, but didn't");
testDecider(&testNumber, &testFailed,
getNumElements(flist) == 2,
"FrequencyList getNumElements(): ",
"new frequency list record should have 2 elements, but doesn't");
TreeNode *middlest = remove_smallest(flist);
testDecider(&testNumber, &testFailed,
getData(getData(middlest)) == '2',
"FrequencyList remove_smallest(): ",
"tried to find the smallest Frequency in the list, but didn't");
testDecider(&testNumber, &testFailed,
getNumElements(flist) == 1,
"FrequencyList getNumElements(): ",
"new frequency list record should have 1 element, but doesn't");
testDecider(&testNumber, &testFailed,
insert(flist,middlest),
"FrequencyList insert(): ",
"couldn't insert a treenode");
testDecider(&testNumber, &testFailed,
getNumElements(flist) == 2,
"FrequencyList getNumElements(): ",
"new frequency list record should have 2 elements, but doesn't");
testDecider(&testNumber, &testFailed,
insert(flist,smallest),
"FrequencyList insert(): ",
"couldn't insert a treenode");
if (testFailed > 10) return testFailed;
// ----------------------------------------------
// Testing HuffmanTree ADT
HuffmanTree *hufft = createHuffmanTree(flist);
testDecider(&testNumber, &testFailed,
hufft != NULL,
"HuffmanTree createHuffmanTree(): ",
"couldn't create a HuffmanTree");
// this test violates the ADT
testDecider(&testNumber, &testFailed,
height(hufft->root) == 3,
"HuffmanTree createHuffmanTree(): ",
"HuffmanTree is the wrong size!");
// this test violates the ADT
testDecider(&testNumber, &testFailed,
getCount(getData(hufft->root)) == 6,
"HuffmanTree createHuffmanTree(): ",
"HuffmanTree calculated the wrong frequency at the root!");
if (testFailed > 10) return testFailed;
// ----------------------------------------------
// Testing HuffmanCodec ADT
HuffmanCodec *huffcdc = createHuffmanCodec(hufft);
testDecider(&testNumber, &testFailed,
huffcdc != NULL,
"HuffmanCodec createHuffmanTree(): ",
"HuffmanCodec returned a NULL Codec!");
char *one, *two, *three;
> cout << "Test " << testNumber << ": Code for '1' is " << one
<< " (should be 2 bits long)" << endl;
testNumber++;
two = huffcdc->codebook[(int)'2'];
cout << "Test " << testNumber << ": Code for '2' is " << two
<< " (should be 2 bits long)" << endl;
testNumber++;
three = huffcdc->codebook[(int)'3'];
cout << "Test " << testNumber << ": Code for '3' is " << three
<< " (should be 1 bit long)" << endl;
char *coded = encode(huffcdc, "123");
testDecider(&testNumber, &testFailed,
coded != NULL,
"HuffmanCodec encode(): ",
"HuffmanCodec returned a NULL string as a code!");
cout << "Test " << testNumber << ": Code for "123" is " << coded
<< " (should be : " << one << two << three << ")" << endl;
char *decoded = decode(huffcdc, one);
testDecider(&testNumber, &testFailed,
decoded != NULL,
"HuffmanCodec decode(): ",
"returned a NULL string for 1!");
cout << "Test " << testNumber << ": Decoding "" << one << "" gives "
<< decoded
<< " (should be : 1)" << endl;
delete [] decoded;
decoded = decode(huffcdc, two);
testDecider(&testNumber, &testFailed,
decoded != NULL,
"HuffmanCodec decode(): ",
"returned a NULL string for 2!");
cout << "Test " << testNumber << ": Decoding "" << two << "" gives "
<< decoded
<< " (should be : 2)" << endl;
delete [] decoded;
decoded = decode(huffcdc, three);
testDecider(&testNumber, &testFailed,
decoded != NULL,
"HuffmanCodec decode(): ",
"returned a NULL string for 3!");
cout << "Test " << testNumber << ": Decoding "" << three << "" gives "
<< decoded
<< " (should be : 3)" << endl;
delete [] decoded;
decoded = decode(huffcdc, coded);
testDecider(&testNumber, &testFailed,
decoded != NULL,
"HuffmanCodec decode(): ",
"returned a NULL string for 123!");
cout << "Test " << testNumber << ": Decoding "" << coded << "" gives "
<< decoded
<< " (should be : 123)" << endl;
cout << "No more tests!" << endl;
// tidy up
destroyFrequency( freq_for_testing );
destroyTreeNode( tree_for_testing );
destroyList( list_for_testing );
destroyIterator( lTrav_for_testing );
destroyHuffmanCodec( huffcdc );
return testFailed;
}
int main() {
int failed = testall();
if (failed == 0) {
cout << "Congratulations! You passed all the tests!" << endl;
}
else if (failed >= 10) {
cout << "You failed at least 10 tests, skipped the rest." << endl;
}
else {
cout << "You failed less than 10 tests. Getting pretty close!" << endl;
}
return 0;
}
Huffman.cpp
#include "LOCALE.h"
#include "Huffman.h"
#include "TreeNode.h"
#include "Frequency.h"
#include "List.h"
#include "FrequencyList.h"
#include "copy.h"
#include <cstring>
#include <iostream>
using namespace std;
HuffmanTree *createHuffmanTree(FrequencyList *frequencies) {
if (frequencies == NULL || isEmpty(frequencies)){
return NULL;
}
HuffmanTree* huffTree = new HuffmanTree;
while(getNumElements(frequencies) > 1){
TreeNode *leftTree, *rightTree, *combineTree;
leftTree = remove_smallest(frequencies);
rightTree = remove_smallest(frequencies);
combineTree = createTreeNode(getData(leftTree));
setCount(getData(combineTree), getCount(getData(leftTree)) + getCount(getData(rightTree)));
setLeft(combineTree, leftTree);
setRight(combineTree, rightTree);
insert(frequencies, combineTree);
}
huffTree->root = remove_smallest(frequencies);
return huffTree;
}
HuffmanCodec *createHuffmanCodec(HuffmanTree *t) {
HuffmanCodec *hcdc = new HuffmanCodec;
hcdc->huffTree = t;
//initialize codebook
for (int i = 0; i < ASCII_SIZE; i++){
hcdc->codebook[i] = NULL;
}
// build the codebook using the Tree
char *acode = new char[height(t->root)+1];
find_codes(hcdc, t->root, acode, 0);
return hcdc;
}
void find_codes(HuffmanCodec *hcdc, TreeNode *t, char s[], int d){
if (t == NULL){
return;
}
else if (isLeaf(t)){
s[d] = '';
hcdc->codebook[(int) getData(getData(t))] = copy(s);
}
else {
s[d] = '0';
find_codes(hcdc, getLeft(t), s, d+1);
s[d] = '1';
find_codes(hcdc, getRight(t), s, d+1);
}
}
void delete_huffman_helper(TreeNode *t){
if (t == NULL){
return;
}
delete_huffman_helper(getLeft(t));
delete_huffman_helper(getRight(t));
//delete the Frequency record
delete getData(t);
//delete the current Tree node
delete t;
}
void destroyHuffmanTree(HuffmanTree *ht){
delete_huffman_helper(ht->root);
delete ht;
}
void destroyHuffmanCodec(HuffmanCodec *hcdc){
destroyHuffmanTree(hcdc->huffTree);
for (int i = 0; i < ASCII_SIZE; i++){
if (hcdc->codebook[i] != NULL){
delete [] hcdc->codebook[i];
}
}
}
char *encode(HuffmanCodec *h, const char message[]){
if (message == NULL || h == NULL){
return NULL;
}
char* coded = new char[10000];
for(int i = 0; message[i] != ''; i++){
strcat(coded, h->codebook[(int) message[i]]);
}
return coded;
}
char decode_char(TreeNode *t, char message[], unsigned int *d){
if(isLeaf(t)){
return getData(getData(t));
}
else{
if(message[*d] == '0'){
*d = *d + 1;
return decode_char(getLeft(t), message, d);
}
else{
*d = *d + 1;
return decode_char(getRight(t), message, d);
}
}
}
char *decode(HuffmanCodec *h, char message[]){
unsigned int d = 0; // index for the coded message
int i = 0; // index for the de-coded message
char *decoded_msg = new char[MESSAGE_LIMIT];
// go through the whole message
while (d < strlen(message)){
// decode one character using the Huffman Tree
decoded_msg[i] = decode_char(h->huffTree->root, message, &d);
i++;
}
// ensure the C-string is properly terminated
decoded_msg[i] = '';
// then make a copy
char *result = copy(decoded_msg);
delete [] decoded_msg;
return result;
}
// eof
Huffman.h
#include "TreeNode.h"
#include "FrequencyList.h"
#include "LOCALE.h"
#ifndef _HUFFMAN_H_
#define _HUFFMAN_H_
struct HuffmanTree {
TreeNode *root;
};
struct HuffmanCodec {
HuffmanTree *huffTree;
char *codebook[ASCII_SIZE];
};
HuffmanTree *createHuffmanTree(FrequencyList *frequencies) ;
HuffmanCodec *createHuffmanCodec(HuffmanTree *t) ;
void find_codes(HuffmanCodec *hcdc, TreeNode *t, char s[], int d);
char *encode(HuffmanCodec *h, const char message[]);
char *decode(HuffmanCodec *h, char message[]);
// DESTRUCTOR
void delete_huffman_helper(TreeNode *t);
void destroyHuffmanTree(HuffmanTree *ht);
void destroyHuffmanCodec(HuffmanCodec *hcdc);
#endif
Frequency.cpp
#include "Frequency.h"
#include <iostream>
using namespace std;
Frequency *createFrequency(char d, int c){
Frequency* f = new Frequency;
f->data = d;
f->count = c;
return f;
}
// ACCESSORS
char getData(Frequency *f){
// check error condition first
if (f == NULL) {
cerr << "Error in getData(Frequency): given NULL Frequency."
<< " Unrecoverable from here. Application crashing immediately..."
<< endl;
}
// normal behaviour starts here
return f->data;
}
int getCount(Frequency *f){
// check error condition first
if (f == NULL) {
cerr << "Error in getCount(Frequency): given NULL Frequency."
<< " Unrecoverable from here. Application crashing immediately..."
<< endl;
}
// normal behaviour starts here
return f->count;
}
// MUTATORS
void setData(Frequency *f, char d){
// check error condition first
if (f == NULL) {
cerr << "Error in setData(Frequency): given NULL Frequency."
<< " Unrecoverable from here. Application crashing immediately..."
<< endl;
}
// normal behaviour starts here
f->data = d;
}
void setCount(Frequency *f, int c){
// check error condition first
if (f == NULL) {
cerr << "Error in setCount(Frequency): given NULL Frequency."
<< " Unrecoverable from here. Application crashing immediately..."
<< endl;
}
// normal behaviour starts here
f->count = c;
}
void destroyFrequency(Frequency *f) {
// check error condition first
if (f == NULL) {
cerr << "Error in setCount(Frequency): given NULL Frequency."
<< endl;
return;
}
// normal behaviour starts here
delete f;
}
// eof
Frequency.h
#ifndef _Frequency_H_
#define _Frequency_H_
struct Frequency {
char data; // the character being represented
int count; // the number of occurrences of the character
};
Frequency *createFrequency(char d, int c);
// ACCESSORS
char getData(Frequency *f);
int getCount(Frequency *f);
// MUTATORS
void setData(Frequency *f, char d);
void setCount(Frequency *f, int c);
void destroyFrequency(Frequency *f);
#endif
FrequencyList.h
//NSID: shl083
#include "List.h"
#include "LOCALE.h"
#ifndef _FREQUENCYLIST_H_
#define _FREQUENCYLIST_H_
struct FrequencyList {
List *freqs;
};
FrequencyList *createFrequencyList(const char message[]);
//ACCESSORS
bool isEmpty(FrequencyList *l);
int getNumElements(FrequencyList *l);
//MUTATORS
bool deleteHead(FrequencyList *l, Element *elt);
bool insert(FrequencyList *l, Element dataIn);
bool remove(FrequencyList *l, Element toRemove);
TreeNode *remove_smallest(FrequencyList *freqs);
void destroyFrequencyList(FrequencyList *l);
#endif
FrequencyList.cpp
#include "FrequencyList.h"
#include "Frequency.h"
#include "List.h"
#include "TreeNode.h"
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
// CONSTRUCTORS
FrequencyList *createFrequencyList(const char* message){
if (message == NULL)
{
cerr << "Error in createFrequencyList(): NULL message!" << endl;
return NULL;
}
List* freqlist = createList();
FrequencyList* FreqList = new FrequencyList;
int counts[ASCII_SIZE]; // ASCII_SIZE is defined in LOCALE.h
for (int i = 0; i<ASCII_SIZE; i++){
counts[i] = 0;
}
for(int i = 0; message[i] != ''; i++){
counts[(int) message[i]] = counts[(int) message[i]] + 1;
}
for(int i = 0; i<ASCII_SIZE; i++){
if (counts[i] > 0){
insert(freqlist, createTreeNode(createFrequency(char(i), counts[i])));
}
}
FreqList->freqs = freqlist;
return FreqList;
}
TreeNode *remove_smallest(FrequencyList *l){
if (l == NULL) {
cerr << "Error in remove_smallest: given NULL list"
<< " Returning NULL, but anything could happen."
<< endl;
return NULL;
}
Element smallest = l->freqs->head->data;
Iterator* iter = createIterator(l->freqs);
while(hasNext(iter)){
Element temp = next(iter);
if (temp->data->count < smallest->data->count){
smallest = temp;
break;
}
}
destroyIterator(iter);
remove(l, smallest);
return smallest;
}
void destroyFrequencyList(FrequencyList *l) {
if (l == NULL) {
cerr << "Error in destroyFrequencyList(): given NULL list"
<< endl;
return;
}
if (l->freqs != NULL) {
destroyList(l->freqs);
}
delete l;
}
//ACCESSORS
bool isEmpty(FrequencyList *l){
if (l == NULL) {
cerr << "Error in isEmpty(): given NULL list"
<< " Returning true, but anything could happen."
<< endl;
return true;
}
return isEmpty(l->freqs);
}
int getNumElements(FrequencyList *l){
if (l == NULL) {
cerr << "Error in getNumElemnts(): given NULL list"
<< " Returning 0, but anything could happen."
<< endl;
return 0;
}
return getNumElements(l->freqs);
}
//MUTATORS
bool deleteHead(FrequencyList *l, Element *elt){
if (l == NULL) {
cerr << "Error in deleteHead(): given NULL list"
<< " Returning false, but anything could happen."
<< endl;
return false;
}
return deleteHead(l->freqs, elt);
}
// return: true if successful, false iotherwise
bool insert(FrequencyList *l, Element dataIn){
if (l == NULL) {
cerr << "Error in insert(): given NULL list"
<< " Returning false, but anything could happen."
<< endl;
return false;
}
return insert(l->freqs, dataIn);
}
bool remove(FrequencyList *l, Element toRemove){
if (l == NULL) {
cerr << "Error in remove(): given NULL list"
<< " Returning false, but anything could happen."
<< endl;
return false;
}
return remove(l->freqs,toRemove);
}
// eof
LOCALE.h
#define ASCII_SIZE 128
// the size of input buffers
#define MESSAGE_LIMIT 1000
// eof
List.cpp
#include <cstdlib>
#include <iostream>
#include "List.h"
using namespace std;
// CONSTRUCTORS
List *createList(){
List *l = new List;
l->head = NULL;
l->numElements = 0;
return l;
}
ListNode *createNode(Element dataIn){
ListNode *n = new ListNode;
n->data = dataIn;
n->next = NULL;
return n;
}
Iterator *createIterator(List *l){
// check error condition first
if (l == NULL) {
cerr << "Error in createIterator(): given a NULL list!" << endl;
return NULL;
}
// non-error behaviour starts here
Iterator *it = new Iterator;
it->cur = l->head;
return it;
}
//ACCESSORS
bool isEmpty(List *l){
// check error condition first
if (l == NULL) {
cerr << "Error in isEmpty(List): given a NULL list!"
<< " Returning true, but anything could happen!"
<< endl;
return true;
}
// non-error behaviour starts here
return (l->numElements == 0);
}
int getNumElements(List *l){
// check error condition first
if (l == NULL) {
cerr << "Error in getNumElements(List): given a NULL list!"
<< " Returning 0, but anything could happen!"
<< endl;
return 0;
}
// non-error behaviour starts here
return l->numElements;
}
//MUTATORS
bool deleteHead(List *l, Element *elt){
// check error condition first
if (l == NULL) {
cerr << "Error in deleteHead(List): given a NULL list!"
<< " Returning false, but anything could happen!"
<< endl;
return false;
}
// non-error behaviour starts here
if (l->head==NULL){
return false;
}
else {
*elt = l->head->data;
ListNode *temp = l->head;
l->head = l->head->next;
delete temp;
l->numElements--;
return true;
}
}
bool insert(List *l, Element dataIn){
// check error condition first
if (l == NULL) {
cerr << "Error in insert(List): given a NULL list!"
<< " Returning false, but anything could happen!"
<< endl;
return false;
}
// non-error behaviour starts here
ListNode *newNode = createNode(dataIn);
if( newNode == NULL) return false;
if (l->head == NULL) {
l->head = newNode;
}
else {
ListNode *cur = l->head;
while(cur->next != NULL) {
cur = cur->next;
}
cur->next = newNode;
}
l->numElements++;
return true;
}
bool remove(List *l, Element toRemove){
// check error condition first
if (l == NULL) {
cerr << "Error in remove(List): given a NULL list!"
<< " Returning false, but anything could happen!"
<< endl;
return false;
}
if (l->head == NULL){
return false;
}
ListNode *rPre, *rTemp;
rPre = NULL;
rTemp = l->head;
while(rTemp != NULL){
if(rTemp->data == toRemove) break;
rPre = rTemp;
rTemp = rTemp->next;
}
if(rPre == NULL){ //remove head
l->head = l->head->next;
}
else if(rTemp == NULL){ //no match found
return false;
}
else if(rTemp->next == NULL){ //remove tail
rPre->next = NULL;
}
else{
rPre->next = rTemp->next;
}
l->numElements = l->numElements - 1;
return true;
}
bool hasNext(Iterator *it){
if (it == NULL) {
cerr << "Error in hasNext(): given a NULL Iterator!"
<< " Returning false, but anything could happen!"
<< endl;
return false;
}
// non-error behaviour starts here
return (it->cur != NULL);
}
Element next(Iterator *it){
if (it == NULL) {
cerr << "Error in next(): given a NULL Iterator!"
<< " Returning NULL, but anything could happen!"
<< endl;
return NULL;
}
// non-error behaviour starts here
Element d = it->cur->data;
it->cur = it->cur->next;
return d;
}
void destroyList(List *l) {
// check error condition first
if (l == NULL) {
cerr << "Error in destroyList(): given a NULL list!"
<< endl;
return;
}
// non-error behaviour starts here
while (l->head != NULL) {
ListNode *temp = l->head;
l->head = l->head->next;
delete temp;
}
delete l;
}
void destroyIterator(Iterator *it) {
if (it == NULL) {
cerr << "Error in destroyIterator(): given a NULL Iterator!"
<< endl;
return;
}
// non-error behaviour starts here
delete it;
}
// eof
List.h
#include "Element.h"
#ifndef _LIST_H_
#define _LIST_H_
struct ListNode {
Element data; // stores a pointer to data in node
ListNode *next; // reference to next node in list
};
struct List {
ListNode *head; // reference to the first node in the list
int numElements; // the number of nodes in the list
};
struct Iterator {
ListNode *cur; // a reference to the current node in the traversal
};
List *createList();
Iterator *createIterator(List *l);
//ACCESSORS
bool isEmpty(List *l);
int getNumElements(List *l);
//MUTATORS
bool deleteHead(List *l, Element *elt);
bool insert(List *l, Element dataIn);
bool remove(List *l, Element toRemove);
void destroyList(List *l);
bool hasNext(Iterator *it);
Element next(Iterator *it);
void destroyIterator(Iterator *it);
#endif
TreeNode.cpp
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include "TreeNode.h"
using namespace std;
TreeNode *createTreeNode(TreeElement d){
TreeNode* treenode = new TreeNode;
treenode->data = d;
treenode->left = NULL;
treenode->right = NULL;
return treenode;
}
//ACCESSORS
// return: the data element in the TreeNode
TreeElement getData(TreeNode *n){
// check error condition first
if (n == NULL) {
cerr << "Error in getData(TreeNode): given NULL TreeNode. "
<< "Unrecoverable from here. Application crashing immediately..."
<< endl;
}
// non-error behaviour starts here
return n->data;
}
TreeNode *getLeft(TreeNode *n){
// check error condition first
if (n == NULL) {
cerr << "Error in getLeft(TreeNode): given NULL TreeNode."
<< " Returning NULL, but anything could happen."
<< endl;
return NULL;
}
// non-error behaviour starts here
return n->left;
}
TreeNode *getRight(TreeNode *n){
// check error condition first
if (n == NULL) {
cerr << "Error in getRight(TreeNode): given NULL TreeNode."
<< " Returning NULL, but anything could happen."
<< endl;
return NULL;
}
// non-error behaviour starts here
return n->right;
}
bool isLeaf(TreeNode *n){
// check error condition first
if (n == NULL) {
cerr << "Error in isLeaf(TreeNode): given NULL TreeNode."
<< " Returning true, but anything could happen."
<< endl;
return true;
}
// non-error behaviour starts here
return ((n->left == NULL) && (n->right == NULL));
}
int height(TreeNode *n){
if (n == NULL){
return 0;
}
if (n->left == NULL && n->right == NULL){
return 1;
}
else{
int leftheight = 0, rightheight = 0;
if(n->left != NULL){
leftheight = 1 + leftheight + height(n->left);
}
if(n->right != NULL){
rightheight = 1 + rightheight + height(n->right);
}
return max(leftheight, rightheight);
}
}
//MUTATORS
void setData(TreeNode *n, TreeElement d){
// check error condition first
if (n == NULL) {
cerr << "Error in setData(TreeNode): given NULL TreeNode."
<< "Unrecoverable from here. Application crashing immediately..."
<< endl;
}
// non-error behaviour starts here
n->data = d;
}
void setLeft(TreeNode *n, TreeNode *l){
// check error condition first
if (n == NULL) {
cerr << "Error in setLeft(TreeNode): given NULL TreeNode."
<< "Unrecoverable from here. Application crashing immediately..."
<< endl;
}
// non-error behaviour starts here
n->left = l;
}
void setRight(TreeNode *n, TreeNode *r){
// check error condition first
if (n == NULL) {
cerr << "Error in setRight(TreeNode): given NULL TreeNode."
<< "Unrecoverable from here. Application crashing immediately..."
<< endl;
}
// non-error behaviour starts here
n->right = r;
}
void destroyTreeNode(TreeNode *n) {
// check error condition first
if (n == NULL) {
cerr << "Error in destroyTreeNode(): given NULL TreeNode."
<< endl;
return;
}
// non-error behaviour starts here
delete n;
}
// eof
TreeNode.h
#include "TreeElement.h"
#ifndef _TREENODE_H_
#define _TREENODE_H_
struct TreeNode {
TreeElement data; //stores a pointer to the data in this tree node
TreeNode *left; //reference to the left child tree
TreeNode *right; //reference to the right child tree
};
TreeNode *createTreeNode(TreeElement d);
//ACCESSORS
TreeElement getData(TreeNode *n);
TreeNode *getLeft(TreeNode *n);
TreeNode *getRight(TreeNode *n);
bool isLeaf(TreeNode *n);
int height(TreeNode *n);
//MUTATORS
void setData(TreeNode *n, TreeElement d);
void setLeft(TreeNode *n, TreeNode *l);
void setRight(TreeNode *n, TreeNode *r);
void destroyTreeNode(TreeNode *n) ;
#endif
copy.cpp
#include <cstring>
#include <iostream>
using namespace std;
char *copy(char *s) {
if (s == NULL) {
cerr << "Error in copy(): given NULL string to copy." << endl;
}
char *temp = new char[strlen(s)+1];
strcpy(temp,s);
return temp;
}
// eof
copy.h
#ifndef _COPY_H_
#define _COPY_H_
char *copy(char *s);
#endif
TreeElement.h
#include "Frequency.h"
#ifndef _TREEELEMENT_H_
#define _TREEELEMENT_H_
typedef Frequency* TreeElement;
#endif
Element.h
#include "TreeNode.h"
#ifndef _ELEMENT_H_
#define _ELEMENT_H_
typedef TreeNode* Element;
#endif
sample output
Test 1: Frequency getData() Passed!
Test 2: Frequency setData() Passed!
Test 3: Frequency getCount(): Passed!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.