### Spring 2022 ECE 264 :: Purdue University

⚠ This is a PAST SEMESTER (Spring 2022).
Due 4/15

# Huffman 3: linked list of trees

## Learning goals

You should learn:

1. Practice using linked lists and trees.
2. Combining linked lists with trees
3. Learning objectives: structures and dynamic structures

## Overview

This is part 3 in an 8-part series in which you are implementing the Huffman Coding algorithm to compress files.

1. HW15: Implement priority queue for future use
2. HW16: Calculate character frequencies from a file
3. HW17: Create a priority queue of trees from the character frequencies in a file. ◀◀◀ this homework
4. HW18: Build a single Huffman tree.
5. HW19: Implement functions to write arbitrary bits to a file, for future use.
6. HW20: Write the Huffman Tree to the disk.
7. HW21: Write the encoded file contents to the disk.
8. huffman_8: Create a command-line interface for compressing files.

### Multiple files

In this homework, your code will be split into many files. You already have several files with code that serves coherent purposes. In HW16, you created frequencies.c and frequencies.h, for calculating character frequencies in files. In HW15, you created files for a priority queue. You will be renaming those to priority_queue.c and priority_queue.h for this homework.

You will definitely want to use your Makefile for this homework, even if you weren't doing so before. Unlike previous assignments, you will be compiling four (4) C files together. That's too much to type every time!

## Getting Started

There is no starter code. By the time you leave this class you should be able to set up a project from scratch. We have given detailed instructions below.

1. Set up your HW17 directory with the files you will need.
1. Create a directory for HW17.
```you@ecegrid-thin1 ~/ \$ ````mkdir hw17`
```you@ecegrid-thin1 ~/ \$ ````cp hw16/{frequencies.c,frequencies.h} hw17/`
3. Copy your priority queue code from HW15 into your HW17, changing the names from huffman.c to priority_queue.c, and huffman.h to priority_queue.h.
```you@ecegrid-thin1 ~/ \$ ````cp hw15/huffman.c hw17/priority_queue.c`
```you@ecegrid-thin1 ~/ \$ ````cp hw15/huffman.h hw17/priority_queue.h`
4. Change into your HW17 directory.
```you@ecegrid-thin1 ~/ \$ ````cd hw17`
2. Edit your priority_queue.c and priority_queue.h.
1. In priority_queue.c, change `#include "huffman.h"` to `#include "priority_queue.h"` .
```you@ecegrid-thin1 hw17/ \$ ````vim priority_queue.c`
2. In priority_queue.h, change the include guard from `__HUFFMAN_H__` to `__PRIORITY_QUEUE_H__`.
3. Create a new huffman.h
```you@ecegrid-thin1 hw17/ \$ ````vim huffman.h`
2. Add a `#include` statement for stdlib.h (for `size_t`).
3. Add `#include` statements for frequencies.h, priority_queue.h. Be sure to use double quotes (`#include "▒▒▒.h"`) not angle brackets (`#include <▒▒▒.h>`), since these are your header files.
4. Add a struct type called `TreeNode` in huffman.h using `typedef` syntax. It should have four fields: `character` (`uchar`), `frequency` (`size_t`), `left` (`TreeNode*`), and `right` (`TreeNode*`).
5. Add a function declaration, exactly as below:
`Node* make_huffman_pq(Frequencies freqs);`
4. Create a new huffman.c.
```you@ecegrid-thin1 hw17/ \$ ````vim huffman.c`
1. Add `#include` statements for the usual standard header files (stdbool.h, stdio.h, stdlib.h, assert.h).
2. Add `#include` statements for huffman.h. (You don't need to explicitly include priority_queue.h and frequencies.h since they are included by way of huffman.h).
```you@ecegrid-thin1 hw17/ \$ ````vim Makefile`
1. Set your `SRC_C` variable (at the top) to `huffman.c priority_queue.c frequencies.c`.
2. Set your `SRC_H` variable (at the top) to `huffman.h priority_queue.h frequencies.h miniunit.h clog.h`.
3. Set your `TEST_C` variable (at the top) to `test_huffman.c`.
4. Set your `EXECUTABLE` variable (at the top) to `test_huffman`.
5. Verify that running `make` results in this compilation command:
gcc -std=c11 -g -Wall -Wshadow --pedantic -Wvla -Werror test_huffman.c huffman.c priority_queue.c frequencies.c -o test_huffman
… and likewise for `make test` but with the addition of `-DDEBUG`.
The order can be different (as long as `-o` is immediately before `test_huffman`).
6. Modify your `SUBMIT_FILES` variable to include all of the files you need to submit. As always, it should using existing variable names wherever possible. You will end up with something like this:
`SUBMIT_FILES=\$(SRC_C) \$(SRC_H) \$(TEST_C) Makefile`

## Example

Suppose you have a file called a.txt containing `abc\nabca\n` .

Your code calls `calc_frequencies(freqs, "a.txt", &error)` and then `make_huffman_pq(freqs)`

The resulting list should look like this:

┌────┬───┐ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ │ █ │ █─┼────►│ █ │ █─┼────►│ █ │ █─┼────►│ █ │ █─┼──┐ └─┼──┴───┘ └─┼─┴───┘ └─┼─┴───┘ └─┼─┴───┘ ▼ │ │ │ │ NULL ▼ ▼ ▼ ▼ ┌─┴──┬───┬─┬─┐ ┌─┴─┬───┬─┬─┐ ┌─┴─┬───┬─┬─┐ ┌─┴─┬───┬─┬─┐ │'\n'│ 2 │█│█│ │'b'│ 2 │█│█│ │'c'│ 2 │█│█│ │'a'│ 3 │█│█│ └────┴───┴┼┴┼┘ └───┴───┴┼┴┼┘ └───┴───┴┼┴┼┘ └───┴───┴┼┴┼┘ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ NULL NULL NULL NULL NULL NULL NULL NULL

`malloc(…)` should be called eight (8) times.

`free(…)` should not be called at all.

a.txt should not be accessed in any way.

## How much work is this?

In the instructor's solution, the body of `make_huffman_pq(…)` is 9 sloc. The body of the compare function is 4 sloc. That is not counting the function signature and ending brace of those functions.

The `cloc` command can measure sloc for individual files if you add the `--by-file` flag.

```aq@ecegrid-thin1 asg_info.asg_nickname_lower \$ ````cloc --by-file frequencies.? huffman.? priority_queue.?`
6 text files. 6 unique files. 0 files ignored. github.com/AlDanial/cloc v 1.75 T=0.04 s (159.2 files/s, 4005.6 lines/s) ------------------------------------------------------------------------------- File blank comment code ------------------------------------------------------------------------------- priority_queue.c 7 6 42 huffman.c 2 0 23 frequencies.c 2 1 19 huffman.h 3 0 13 priority_queue.h 7 1 12 frequencies.h 4 1 8 ------------------------------------------------------------------------------- SUM: 25 9 117 -------------------------------------------------------------------------------

## Requirements

1. Your submission must contain each of the following files, as specified:
file contents
huffman.c functions
`make huffman pq(Frequencies freqs)`
return type: Node✶
Create a priority queue where the value at each node is a tree node containing a character and its frequency.
• `freqs` is as returned by `calc_frequencies(…)` in HW16.
• Ex: `freqs['a'] == 3` for the file containing `abc\nabca\n` .
• Caller must free the memory using `destroy_list(…)` from your HW15.
• Do not create nodes for characters with frequency zero.
• Use your `pq_enqueue(…)` from your HW15.
• You will need to create a compare function.
• Sort by frequency (ascending). The least frequent nodes should come first.
• For nodes with the same frequency, sort by character value (e.g., `'A'` before `'B'`)
• Compare function is not listed in the requirements table because it a helper function.
• As with all helper functions:
• Function name should start with `'_'`.
• It should be declared as `static`.
• We will not test your compare function directly.
• Return the address of the head for the newly created list.
• Do not make this complicated. These “trees” are size=1 (i.e., single node with no children).
• Do not call `free(…)`.
• Do not open or close any files.
huffman.h struct type
TreeNode
Struct type definition for a node in your Huffman tree.
• Use `typedef` syntax.
• It should have four fields:
• `character` (`uchar`)
• `frequency` (`size_t`)
• `left` (`TreeNode*`)
• `right` (`TreeNode*`)
function declaration
`make huffman pq(Frequencies freqs)`
return type: Node✶
Declaration of `make_huffman_pq(…)`.
• This should have no curly braces, and should end with a semicolon.
test_huffman.c functions
`main(int argc, char✶ argv[])`
return type: int
• 100% code coverage is required in huffman.c only.
• Direct testing of frequencies.c and priority_queue.c is optional this time.
2. stdio.h `fputc`, `fputs`, `stdout` `test_huffman.c` `printf`, `fputc` `test_huffman.c` stdlib.h `EXIT_SUCCESS`, `EXIT_FAILURE`, `free` `test_huffman.c` assert.h `assert` `huffman.c`, `test_huffman.c` stdbool.h `bool`, `true`, `false` `huffman.c`, `test_huffman.c` Feel free to ask if there is something else you would like to use. -->
3. Submissions must meet the code quality standards and other course policies on homework.

## Submit

To submit HW17 from within your hw17 directory, type

`make submit`

That should result in the following command: `264submit HW17 huffman.c huffman.h frequencies.c frequencies.h priority_queue.c priority_queue.h test_huffman.c miniunit.h clog.h Makefile`

## Pre-tester ●

The pre-tester for HW17 has been released and is ready to use.

1. ▒▒▒?
▒▒▒