CMSC216 Project 2: Bit Ops, Debugging, Data Structures

Due: 11:59pm Fri 17-Oct-2025
Approximately 4.0% of total grade
Submit to Gradescope
Projects are individual work: no collaboration with other students is allowed. Seek help from course staff if you get stuck for too long.

CODE/TEST DISTRIBUTION: p2-code.zip

VIDEO OVERVIEW: Not Yet Available

CHANGELOG: Empty

1 Introduction

This project addresses more advanced C programming topics each in its own problem.

Bit-level operations are common in C and systems programming. This assignment features a problem in which shifting and bitwise AND/OR-ing are required to complete the requirements.
Debugging is also a critical skill enabled by the debugger. The second problem in the assignment makes use of the GNU Debugger, gdb, to work through a puzzle program requiring specific inputs to pass its "phases".
Data structures pervade computing and getting some practice with them in C will improve one's skill at pointers and memory usage while also giving a great appreciation for garbage collected languages. A basic "set" application which tracks a collection of unique values is implemented, backed by a hash table.

Difficulty Notice

Past students have found this content to be more challenging than Project 1.

If you were pressed for time to finish Project 1, start this project as early as possible. Most students have found the first two problems (bit manipulations and debugging) only mildly challenging but run out of time on the larger third problem.

You have been warned.

2 Download Code and Setup

Download the code pack linked at the top of the page. Unzip this which will create a project folder. Create new files in this folder. Ultimately you will re-zip this folder to submit it.

File	State	Notes
`batt_update.c`	CREATE	Problem 1 create this file and write required function in it
`batt.h`	Provided	Problem 1 header file
`batt_main.c`	Provided	Problem 1 main() function for battmeter simulation

`batt_examples.sh`	Sample	Prints a variety of sample runs of `batt_main`

`test_batt_update.c`	Testing	Problem 1 functions tests for `batt_upate.c`
`test_batt_update.org`	Testing	Problem 1 testing data file
`puzzlebox.c`	Provided	Problem 2 Debugging problem
`input.txt`	EDIT	Problem 2 Input for `puzzlebox`, fill this in
`treeset_funcs.c`	CREATE	Problem 3 functions to write
`treeset_main.c`	CREATE	Problem 3 main function to write
`treeset.h`	Provided	Problem 3 header file
`test_treeset.org`	Testing	Problem 3 testing script

`data/stranger-demo.script`	Data	Problem 3 sample input scripts to main program
`data/1.tree`	Data	Problem 3 sample tree set save files
`data/2.tree`	Data
`data/big.tree`	Data
…
`Makefile`	Provided	Build file to compile all programs
`testy`	Testing	Test running script
`gradescope-submit`	Provided	Script to allow submission from the command line

Makefile

As in the first assignment, a Makefile is provided as part of this project. The essential targets pertinent to each problem are described in those sections. The Makefile is equipped with a brief help listing:

>> make help
Typical usage is:
  > make                          # build all programs
  > make clean                    # remove all compiled items
  > make zip                      # create a zip file for submission
  > make prob1                    # built targets associated with problem 1
  > make test                     # run all tests
  > make test-prob2               # run test for problem 2
  > make test-prob2 testnum=5     # run problem 2 test #5 only
  > make update                   # download and install any updates to project files
  > make submit                   # upload submission to Gradescope

Automated Tests

As in previous assignments, automated tests are provided and associated with problems. Each problem describes how to run tests associated with it. Generally this is done as before:

>> make test-prob1
gcc -Wall -Wno-comment -Werror -g  -c batt_main.c
gcc -Wall -Wno-comment -Werror -g  -c batt_update.c
...
./testy -o md test_batt.org 
===========================================================================
== test_batt.org : Problem 1 test_batt_update and batt_main tests
== Running 40 / 40 tests
 1) batt_from_ports_01      : ok
 2) batt_from_ports_02      : ok
 3) batt_from_ports_03      : ok
...

>> make test-prob2         # run "tests" associated with problem 2
... 
>> ./puzzlebox input.txt   # same as above: run puzzlebox to test answers

3 Problem 1: Battery Meter Simulation

3.1 Overview

You are tasked with writing code which will be run by a microcontroller in a digital battery meter. The hardware has the following relevant features.

A voltage sensor whose value can be accessed via a memory mapped port. In C this is presented as a global variable. Another port indicates whether the voltage should be displayed in Volts or Percentage of total battery capacity.
A digital display with a port control port; altering a certain global variable will change the display to show information to a user of the battery meter.
User code that you will need to write to update the display based on the sensor value.
A simulator program with Makefile to test your code

Each feature is discussed in subsequent sections.

Voltage Sensor

A voltage sensor is attached to the battery meter and can be accessed via a C global variable. This is declared in the batt.h header file as follows.

extern short BATT_VOLTAGE_PORT;
// Sensor tied to the battery, provides a measure of voltage in units
// of 0.0005 volts (half milli volts). The sensor can sense a wide
// range of voltages including negatives but the batteries being
// measured are Full when 3.8V (7600 sensor value) or above is read
// and Empty when 3.0V (6000 sensor value) or lower is read.

You do not need to define this variable as it is already there. You do NOT need to set this variable as it is automatically changed by the hardware. Instead, you will need to access its value to determine various the voltage level of the attached battery.

As indicated in the variable documentation, a common (though mildly unreliable) means of detecting how much charge is left in a battery is to read the voltage on the battery. The type of battery being measured in this case has a higher voltage when fully charged and its lower voltage continuously lowers as it discharges. Past a certain low voltage, the battery is unsafe to discharge and other hardware will disable the meter. The figure below shows the voltage range and corresponding Capacity Percentage for the battery.

Figure 1: Relationship between Voltage and Percent full for batteries being measured by the meter.

Notice the relationship between the Voltage which can be read directly and the Percent full which needs to be calculated from the voltage using the given formula:

BattV = BattVoltPort / 2
Batt% = (BattV - 3000) / 8

Note the conversion is done in millivolts (0.001 volts) and the the voltage sensor is in units of half millivolts (0.0005 volts).

Voltage Display Mode

Another global variable exposes whether the user has pressed a button which toggles between displaying Volts or Percent full in the battery.

extern unsigned char BATT_STATUS_PORT;
// The bit at index 4 indicates whether display should be in Volts (0)
// or Percent (1); the bit is tied to a user button which will toggle
// it between modes. Other bits in this char may be set to indicate
// the status of other parts of the meter and should be ignored: ONLY
// BIT 4 BIT MATTERS. C code should only read this port.

As per the documentation, only the 4th bit should be used while other bits may be nonzero and should be ignored. Bitwise operations are useful for this.

Display Port

The battery meter has a digital display which shows the remaining battery capacity. This display is controlled by a special memory area exposed as another global variable in C.

extern int BATT_DISPLAY_PORT;
// Controls battery meter display. Readable and writable. C code
// should mostly write this port with a sequence of bits which will
// light up specific elements of the LCD panel.

While listed as in int, each bit of the is actually tied to part of the LCD display screen. When bits are set to 1, part of the display is lit up while 0 means it is not lit.

The following diagrams show how various bit patterns will light up parts of the LCD display. Some bits correspond to parts of digits like "9" and "4" while others light up portions for the decimal place, Volt/Percent indicator, and bars of the leftmost visual level indicator. Above the display is the bit string which results in the elements on the display being turned on with "1" and off with a "0".

Notice the following.

The BATT_DISPLAY_PORT is a 32-bit integer but only some bits control the display
29 bits are used to control the full battery display (bits 0-28)
Bit 0 controls whether the '%' Percent indicator is shown
Bit 1 controls whether the 'V' Voltage indicator is shown
Bit 2 controls whether the decimal place is on (for Volts) or off (for Percent)
Bits 3-9 control the rightmost digit
Bits 10-16 control the middle digit
Bits 17-23 control the left digit
Each digit follows the same pattern: lowest bit controls the upper right LCD digit bar with each higher bit going in a clockwise fashion and the middle bar being controlled by the highest order bit
Bits 24-28 control the 5 'bars' in the visual level indicator
Bits 29-31 are unused

Figure 2: Full examples of how the 29 bits of the BATT_DISPLAY_PORT turns on/off parts of the LCD display. Each digit follows the same pattern of bit to bar correspondence. The lowest order (rightmost) bits control the percent, voltage, and decimal place indicator. Middle bits control "bar" of each digit starting with the top bar and proceeding around the outside clockwise with the final bit for each digit controlling the middle bar. This pattern is followed for all 3 digits. The uppermost bits control the level indicator bars.

For reference, each number to be displayed in the LCD battery meter follows the same patter of bits which is shown in the below diagram with the rightmost digit bit positions.

Figure 3: Pattern of bits for all 10 numerals and a few extra symbols

3.2 `batt_update.c`: Updating the Display with User Code

Periodically the microcontroller will run code to adjust the battery display to show the current battery level. This function is

int batt_update();

and it will be your job to write it.

Rather than write everything that needs to be done within batt_update(), several helper functions will be used to divide this task into several more manageable and testable chunks.

These should all be written in batt_update.c and are as follows.

Converting Voltage Values to a Struct

int set_batt_from_ports(batt_t *batt);
// Uses the two global variables (ports) BATT_VOLTAGE_PORT and
// BATT_STATUS_PORT to set the fields of the parameter 'batt'.  If
// BATT_VOLTAGE_PORT is negative, then battery has been wired wrong;
// no fields of 'batt' are changed and 1 is returned to indicate an
// error.  Otherwise, sets fields of batt based on reading the voltage
// value and converting to precent using the provided formula. Returns
// 0 on a successful execution with no errors. This function DOES NOT
// modify any global variables but may access global variables.
//
// CONSTRAINT: Avoids the use of the division operation as much as
// possible. Makes use of shift operations in place of division where
// possible.
//
// CONSTRAINT: Uses only integer operations. No floating point
// operations are used as the target machine does not have a FPU.
// 
// CONSTRAINT: Limit the complexity of code as much as possible. Do
// not use deeply nested conditional structures. Seek to make the code
// as short, and simple as possible. Code longer than 40 lines may be
// penalized for complexity.

This function works with the struct batt_t defined in batt.h which has the following layout.

// Breaks battery stats down into constituent parts
typedef struct{
  short mlvolts;     // voltage read from port, units of 0.0005 Volts (milli Volts)
  char  percent;     // percent full converted from voltage
  char  mode;        // 1 for percent, 2 for volts, set based on bit 4 of BATT_STATUS_PORT
} batt_t;

The function set_batt_from_ports() will read the global variables mentioned above and fill in values for the struct fields of the parameter batt. Keep the following in mind while implementing the function.

Read the BATT_VOLTAGE_PORT value directly into the volt field.
Use the previously mentioned conversion formula to convert Volts to Percentage to fill in the percent field of the struct.
```
   BattV = BattVoltPort / 2
   Batt% = (BattV - 3000) / 8
```
Note the CONSTRAINT that division should be avoided as much as possible. Employ shift operations in place of division where appropriate.
Note also the constraint: make use only of integer operations. Do not use float or double variables. This is emulates the somewhat common situation where simple microprocessors cannot perform floating point operations as they lack a Floating Point Unit (FPU).

Setting Display from a `batt_t`

int set_display_from_batt(batt_t batt, int *display);
// Alters the bits of integer pointed to by 'display' to reflect the
// data in struct param 'batt'.  Does not assume any specific bit
// pattern stored at 'display' and completely resets all bits in it on
// successfully completing.  Selects either to show Volts (mode=1) or
// Percent (mode=2). If Volts are displayed, only displays 3 digits
// rounding the lowest digit up or down appropriate to the last digit.
// Calculates each digit to display changes bits at 'display' to show
// the volts/percent according to the pattern for each digit. Modifies
// additional bits to show a decimal place for volts and a 'V' or '%'
// indicator appropriate to the mode. In both modes, places bars in
// the level display as indicated by percentage cutoffs in provided
// diagrams. This function DOES NOT modify any global variables but
// may access global variables. Always returns 0.
// 
// CONSTRAINT: Limit the complexity of code as much as possible. Do
// not use deeply nested conditional structures. Seek to make the code
// as short, and simple as possible. Code longer than 65 lines may be
// penalized for complexity.

Importantly, this function sets the bits in the integer pointed to by display which may or MAY NOT BE the global display variable.

To properly set the display bits, set_display_from_batt() will need to do bit shifting along with bitwise operations to construct the correct bit pattern for the display.

A good trick to use is to create a series of bit patterns that correspond to the various digits. For example, according to the diagrams above, the bit pattern for 9 is 0b1110111. If a 9 should appear on the display somewhere, this bit pattern should be shifted and combined with the existing bits in display so that a 9 will show. Creating similar constant mask patterns for each digit, the decimal place, the positions of the Voltage/Percent indicator, and the bars for the visual level indicator is a good way to make this problem manageable.

A detailed explanation of one approach to the problem follows.

Create an array of bit masks for each of the digits 0-9. The 0th element of the array contains a bit mask like 0b0111111 which represents the bits that should be set for a 0 digit, the 1th element of this array has a mask like 0b0000011 which are the bits to be set for a 1. There should be ten entries in this array in indices 0-9.
Use modulo to determine the integer value for right, middle, and left digits for the display from volts or percent. Each digit should have a value from 0-9 and be Stored in its own variable.
Start with an integer variable of 0 (all 0 bits).
Use left digit variable to index into your array of masks to determine the bits that should be set for it and shift them over an appropriate amount combining with the existin display bits.
Combining bits here is a bitwise operation of setting all bits that are one in the mask to 1 in the display variable. Use an appropriate bitwise operation to combine the bits, likely a bitwise OR.
Repeat this process for the middle and right digits shifting left by appropriate to where the digits should line up.
There are several special cases to consider such as leading 0's in a percent should be blanks so nothing should be drawn.
Don't forget to set the additional bits like the decimal place, the V/% indicator, and the level bars for the visual indicator. These are low order bits (rightmost).
Importantly make code as simple as possible as the target CPU has a limited amount of RAM and longer codes will occupy more RAM. Avoid nesting conditionals very deeply: if/else if/else structures are fine but nesting a conditional within this will be penalized.

Overall Update Function

int batt_update();
// Called to update the battery meter display.  Makes use of
// set_batt_from_ports() and set_display_from_batt() to access battery
// voltage sensor then set the display. Checks these functions and if
// they indicate an error, does NOT change the display.  If functions
// succeed, modifies BATT_DISPLAY_PORT to show current battery level.
// 
// CONSTRAINT: Does not allocate any heap memory as malloc() is NOT
// available on the target microcontroller.  Uses stack and global
// memory only.

This function makes use of the previous two functions and the global variables that correspond to the hardware to alter the display. It should be relatively short by making use of the previous functions.

3.3 Battery Meter Simulator

While we do not have actual hardware with the features mentioned, a simulator for the system is in the provided files batt_main.c / batt_sim.c. You do not need to modify or understand code in either file to complete the assignment though it will certainly expand you C skills to spend some time examining them.

The main() function in batt_main.c accepts two command line arguments which are the value for the voltage sensor and whether to show Voltage or Percent for the battery. It will call your functions for this problem and show results for it. You are encouraged to use this main() to test your code incrementally.

Examine whether set_batt_from_ports() is correct based on the first part of output in batt_main.c
Once set_batt_from_ports() is complete, examine whether the output of set_display_from_batt() is correct based on the latter part of the output.
Once both these functions are correct, examine whether batt_update() is correct based on the final part of the output of the main() function.

Note that there are a variety of functions in the batt_sim.c which are used to simulate how the battery meter will display. This is also where the global variables like BATT_DISPLAY_PORT are defined. However, you do not need to modify or even understand the code; it is only used to show how the display would look when the BATT_DISPLAY_PORT bits are set.

3.4 Sample Runs of `batt_main`

Below are samples generated by compiling and running the main() function in the batt_main.c file. The code is compiled by using the provided Makefile to create the batt_main program. It compiles the the functions you write in the file batt_update.c and combines them with functions in batt_main.c.

> make batt_main
make[1]: Entering directory '/home/kauffman/Dropbox/teaching/216-F2025/projects/p2-bits-gdb-datastructs/solution-p2-216'
make[1]: 'batt_main' is up to date.
make[1]: Leaving directory '/home/kauffman/Dropbox/teaching/216-F2025/projects/p2-bits-gdb-datastructs/solution-p2-216'

==========Voltage FOR 7884==========
> ./batt_main 7884 V
BATT_VOLTAGE_PORT set to: 7884
BATT_STATUS_PORT  set to: 0x6F

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3942
  .percent = 100
  .mode    = 2
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 11111 1001111 1101111 1100110 110
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 11111 1001111 1101111 1100110 110
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+  ####   ####  #  #     
|#####|     #   #  #  #  #     
|#####|     #   #  #  #  #     
|#####|  ####   ####  ####  V  
|#####|     #      #     #     
|#####|     #      #     #     
+-----+  #### o ####     #     


==========Percent FOR 7884==========
> ./batt_main 7884 P
BATT_VOLTAGE_PORT set to: 7884
BATT_STATUS_PORT  set to: 0x91

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3942
  .percent = 100
  .mode    = 1
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 11111 0000110 0111111 0111111 001
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 11111 0000110 0111111 0111111 001
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+     #   ####  ####     
|#####|     #   #  #  #  #     
|#####|     #   #  #  #  #     
|#####|     #   #  #  #  #     
|#####|     #   #  #  #  #  %  
|#####|     #   #  #  #  #     
+-----+     #   ####  ####     


==========Voltage FOR 7600==========
> ./batt_main 7600 V
BATT_VOLTAGE_PORT set to: 7600
BATT_STATUS_PORT  set to: 0x6F

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3800
  .percent = 100
  .mode    = 2
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 11111 1001111 1111111 0111111 110
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 11111 1001111 1111111 0111111 110
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+  ####   ####  ####     
|#####|     #   #  #  #  #     
|#####|     #   #  #  #  #     
|#####|  ####   ####  #  #  V  
|#####|     #   #  #  #  #     
|#####|     #   #  #  #  #     
+-----+  #### o ####  ####     


==========Percent FOR 7600==========
> ./batt_main 7600 P
BATT_VOLTAGE_PORT set to: 7600
BATT_STATUS_PORT  set to: 0x91

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3800
  .percent = 100
  .mode    = 1
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 11111 0000110 0111111 0111111 001
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 11111 0000110 0111111 0111111 001
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+     #   ####  ####     
|#####|     #   #  #  #  #     
|#####|     #   #  #  #  #     
|#####|     #   #  #  #  #     
|#####|     #   #  #  #  #  %  
|#####|     #   #  #  #  #     
+-----+     #   ####  ####     


==========Voltage FOR 7530==========
> ./batt_main 7530 V
BATT_VOLTAGE_PORT set to: 7530
BATT_STATUS_PORT  set to: 0x6F

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3765
  .percent = 95
  .mode    = 2
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 11111 1001111 0000111 0000111 110
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 11111 1001111 0000111 0000111 110
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+  ####   ####  ####     
|#####|     #      #     #     
|#####|     #      #     #     
|#####|  ####      #     #  V  
|#####|     #      #     #     
|#####|     #      #     #     
+-----+  #### o    #     #     


==========Percent FOR 7530==========
> ./batt_main 7530 P
BATT_VOLTAGE_PORT set to: 7530
BATT_STATUS_PORT  set to: 0x91

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3765
  .percent = 95
  .mode    = 1
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 11111 0000000 1101111 1101101 001
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 11111 0000000 1101111 1101101 001
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+         ####  ####     
|#####|         #  #  #        
|#####|         #  #  #        
|#####|         ####  ####     
|#####|            #     #  %  
|#####|            #     #     
+-----+         ####  ####     


==========Voltage FOR 7202==========
> ./batt_main 7202 V
BATT_VOLTAGE_PORT set to: 7202
BATT_STATUS_PORT  set to: 0x6F

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3601
  .percent = 75
  .mode    = 2
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 01111 1001111 1111101 0111111 110
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 01111 1001111 1111101 0111111 110
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+  ####   ####  ####     
|     |     #   #     #  #     
|#####|     #   #     #  #     
|#####|  ####   ####  #  #  V  
|#####|     #   #  #  #  #     
|#####|     #   #  #  #  #     
+-----+  #### o ####  ####     


==========Percent FOR 7202==========
> ./batt_main 7202 P
BATT_VOLTAGE_PORT set to: 7202
BATT_STATUS_PORT  set to: 0x91

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3601
  .percent = 75
  .mode    = 1
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 01111 0000000 0000111 1101101 001
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 01111 0000000 0000111 1101101 001
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+         ####  ####     
|     |            #  #        
|#####|            #  #        
|#####|            #  ####     
|#####|            #     #  %  
|#####|            #     #     
+-----+            #  ####     


==========Voltage FOR 7026==========
> ./batt_main 7026 V
BATT_VOLTAGE_PORT set to: 7026
BATT_STATUS_PORT  set to: 0x6F

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3513
  .percent = 64
  .mode    = 2
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00111 1001111 1101101 0000110 110
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00111 1001111 1101101 0000110 110
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+  ####   ####     #     
|     |     #   #        #     
|     |     #   #        #     
|#####|  ####   ####     #  V  
|#####|     #      #     #     
|#####|     #      #     #     
+-----+  #### o ####     #     


==========Percent FOR 7026==========
> ./batt_main 7026 P
BATT_VOLTAGE_PORT set to: 7026
BATT_STATUS_PORT  set to: 0x91

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3513
  .percent = 64
  .mode    = 1
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00111 0000000 1111101 1100110 001
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00111 0000000 1111101 1100110 001
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+         ####  #  #     
|     |         #     #  #     
|     |         #     #  #     
|#####|         ####  ####     
|#####|         #  #     #  %  
|#####|         #  #     #     
+-----+         ####     #     


==========Voltage FOR 6666==========
> ./batt_main 6666 V
BATT_VOLTAGE_PORT set to: 6666
BATT_STATUS_PORT  set to: 0x6F

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3333
  .percent = 41
  .mode    = 2
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00011 1001111 1001111 1001111 110
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00011 1001111 1001111 1001111 110
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+  ####   ####  ####     
|     |     #      #     #     
|     |     #      #     #     
|     |  ####   ####  ####  V  
|#####|     #      #     #     
|#####|     #      #     #     
+-----+  #### o ####  ####     


==========Percent FOR 6666==========
> ./batt_main 6666 P
BATT_VOLTAGE_PORT set to: 6666
BATT_STATUS_PORT  set to: 0x91

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3333
  .percent = 41
  .mode    = 1
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00011 0000000 1100110 0000110 001
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00011 0000000 1100110 0000110 001
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+         #  #     #     
|     |         #  #     #     
|     |         #  #     #     
|     |         ####     #     
|#####|            #     #  %  
|#####|            #     #     
+-----+            #     #     


==========Voltage FOR 6596==========
> ./batt_main 6596 V
BATT_VOLTAGE_PORT set to: 6596
BATT_STATUS_PORT  set to: 0x6F

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3298
  .percent = 37
  .mode    = 2
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00011 1001111 1001111 0111111 110
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00011 1001111 1001111 0111111 110
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+  ####   ####  ####     
|     |     #      #  #  #     
|     |     #      #  #  #     
|     |  ####   ####  #  #  V  
|#####|     #      #  #  #     
|#####|     #      #  #  #     
+-----+  #### o ####  ####     


==========Percent FOR 6596==========
> ./batt_main 6596 P
BATT_VOLTAGE_PORT set to: 6596
BATT_STATUS_PORT  set to: 0x91

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3298
  .percent = 37
  .mode    = 1
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00011 0000000 1001111 0000111 001
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00011 0000000 1001111 0000111 001
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+         ####  ####     
|     |            #     #     
|     |            #     #     
|     |         ####     #     
|#####|            #     #  %  
|#####|            #     #     
+-----+         ####     #     


==========Voltage FOR 6214==========
> ./batt_main 6214 V
BATT_VOLTAGE_PORT set to: 6214
BATT_STATUS_PORT  set to: 0x6F

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3107
  .percent = 13
  .mode    = 2
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00001 1001111 0000110 0000110 110
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00001 1001111 0000110 0000110 110
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+  ####      #     #     
|     |     #      #     #     
|     |     #      #     #     
|     |  ####      #     #  V  
|     |     #      #     #     
|#####|     #      #     #     
+-----+  #### o    #     #     


==========Percent FOR 6214==========
> ./batt_main 6214 P
BATT_VOLTAGE_PORT set to: 6214
BATT_STATUS_PORT  set to: 0x91

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3107
  .percent = 13
  .mode    = 1
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00001 0000000 0000110 1001111 001
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00001 0000000 0000110 1001111 001
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+            #  ####     
|     |            #     #     
|     |            #     #     
|     |            #  ####     
|     |            #     #  %  
|#####|            #     #     
+-----+            #  ####     


==========Voltage FOR 6148==========
> ./batt_main 6148 V
BATT_VOLTAGE_PORT set to: 6148
BATT_STATUS_PORT  set to: 0x6F

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3074
  .percent = 9
  .mode    = 2
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00001 1001111 0111111 0000111 110
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00001 1001111 0111111 0000111 110
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+  ####   ####  ####     
|     |     #   #  #     #     
|     |     #   #  #     #     
|     |  ####   #  #     #  V  
|     |     #   #  #     #     
|#####|     #   #  #     #     
+-----+  #### o ####     #     


==========Percent FOR 6148==========
> ./batt_main 6148 P
BATT_VOLTAGE_PORT set to: 6148
BATT_STATUS_PORT  set to: 0x91

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3074
  .percent = 9
  .mode    = 1
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00001 0000000 0000000 1101111 001
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00001 0000000 0000000 1101111 001
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+               ####     
|     |               #  #     
|     |               #  #     
|     |               ####     
|     |                  #  %  
|#####|                  #     
+-----+               ####     


==========Voltage FOR 6030==========
> ./batt_main 6030 V
BATT_VOLTAGE_PORT set to: 6030
BATT_STATUS_PORT  set to: 0x6F

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3015
  .percent = 1
  .mode    = 2
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00000 1001111 0111111 1011011 110
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00000 1001111 0111111 1011011 110
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+  ####   ####  ####     
|     |     #   #  #     #     
|     |     #   #  #     #     
|     |  ####   #  #  ####  V  
|     |     #   #  #  #        
|     |     #   #  #  #        
+-----+  #### o ####  ####     


==========Percent FOR 6030==========
> ./batt_main 6030 P
BATT_VOLTAGE_PORT set to: 6030
BATT_STATUS_PORT  set to: 0x91

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3015
  .percent = 1
  .mode    = 1
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00000 0000000 0000000 0000110 001
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00000 0000000 0000000 0000110 001
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+                  #     
|     |                  #     
|     |                  #     
|     |                  #     
|     |                  #  %  
|     |                  #     
+-----+                  #     


==========Voltage FOR 6000==========
> ./batt_main 6000 V
BATT_VOLTAGE_PORT set to: 6000
BATT_STATUS_PORT  set to: 0x6F

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3000
  .percent = 0
  .mode    = 2
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00000 1001111 0111111 0111111 110
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00000 1001111 0111111 0111111 110
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+  ####   ####  ####     
|     |     #   #  #  #  #     
|     |     #   #  #  #  #     
|     |  ####   #  #  #  #  V  
|     |     #   #  #  #  #     
|     |     #   #  #  #  #     
+-----+  #### o ####  ####     


==========Percent FOR 6000==========
> ./batt_main 6000 P
BATT_VOLTAGE_PORT set to: 6000
BATT_STATUS_PORT  set to: 0x91

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 3000
  .percent = 0
  .mode    = 1
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00000 0000000 0000000 0111111 001
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00000 0000000 0000000 0111111 001
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+               ####     
|     |               #  #     
|     |               #  #     
|     |               #  #     
|     |               #  #  %  
|     |               #  #     
+-----+               ####     


==========Voltage FOR 5964==========
> ./batt_main 5964 V
BATT_VOLTAGE_PORT set to: 5964
BATT_STATUS_PORT  set to: 0x6F

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 2982
  .percent = 0
  .mode    = 2
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00000 1011011 1101111 1111111 110
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00000 1011011 1101111 1111111 110
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+  ####   ####  ####     
|     |     #   #  #  #  #     
|     |     #   #  #  #  #     
|     |  ####   ####  ####  V  
|     |  #         #  #  #     
|     |  #         #  #  #     
+-----+  #### o ####  ####     


==========Percent FOR 5964==========
> ./batt_main 5964 P
BATT_VOLTAGE_PORT set to: 5964
BATT_STATUS_PORT  set to: 0x91

result = set_batt_from_ports( &batt );
result: 0
batt = {
  .mlvolts = 2982
  .percent = 0
  .mode    = 1
}

result = set_display_from_batt(batt, &display);
result: 0
display is
bits:  000 00000 0000000 0000000 0111111 001
index:  29    24      17      10       3   0

result = batt_update();
result: 0
BATT_DISPLAY_PORT is
bits:  000 00000 0000000 0000000 0111111 001
index:  29    24      17      10       3   0

Battery Meter Display:
+-^^^-+               ####     
|     |               #  #     
|     |               #  #     
|     |               #  #     
|     |               #  #  %  
|     |               #  #     
+-----+               ####

3.5 Problem 1 Grading Criteria grading 30

Both sets automated tests can be run with make test-p1

Weight	Criteria
	AUTOMATED TESTS
20	`make test-prob1` runs 20 tests from `test_batt_update.org` for correctness
	1 point per test
	`test_batt_update.c` provides tests for functions in `batt_update.c` and tests for
	`batt_main` are built into the testing script
	MANUAL INSPECTION of `batt_update.c`
2	`set_batt_from_ports()`
	Clear effort to do error checking of out of bounds values.
	Clear flow to how each field of `batt` is calculated.
	Correctly setting fields of `batt` via pointer dereference or arrow operator.
	Uses shift operations in place of division wherever possible.
	Adherence to constraints: no floats, no float math ops, no deeply nested conditionals
	Short, simple code that is no more than 40 lines long.
	Avoid nested conditionals wherever possible
	Make the code short as you will soon need to translate it to assembly code

5	`set_display_from_batt()`
	Clear code that calculates digits to be displayed
	Use of bit masks corresponding to digits to be displayed
	Use of bitwise operators to shift bits appropriately
	Use of bitwise operators to combine shifted digit bits
	Clear code to turn on decimal place, V/% indicator, and level indicators
	Clear dereference/set of the integer pointed to by the `display` parameter
	Adherence to constraints: no floats, no math float ops, no deeply nested conditionals
	Short, simple code that is no more than 65 lines long.
	Avoid nested conditionals wherever possible
	Make the code short as you will soon need to translate it to assembly code

3	`batt_update()`
	Use of the global variables like `BATT_DISPLAY_PORT`
	Does not re-define these variables
	Use of previous two functions
	Error checking on sensor values
	No use of `malloc()`
	Short, simple code.

4 Problem 2: Debugging the Puzzlebox

4.1 Overview

The file puzzlebox.c contains source code that reads inputs from a file named on the command line. If the inputs are correct, points are awarded. If inputs are incorrect, error messages are printed.

The puzzlebox is arranged into a series of phases each of which has some points associated with it.

Not all phases must be completed to get full credit but the phases must done in order.
Each phase reads inputs from the file provided on the command line and performs calculations on them to see if they are "correct" according to various criteria
The very first input is your internet ID like kauf0095 (first part of your UMN email address). This input is used to add randomness to the puzzle so that your answers will be different from most other students. You must you use your own internet ID.

The purpose of this problem is get familiar with using a debugger. This is a powerful tool that pauses programs, allows internal values to be printed and code to be stepped through line by line. It is nearly essential to use as the code in puzzlebox is intentionally convoluted in places. Being able to pause execution and print values at various points make it much easier to solve the puzzles.

4.2 `input.txt` Input File

Name your input file input.txt and write in it your Terpmail Email Address. Entering your address as kauf0095@terpmail.umd.edu will use the first part (your Directory ID) as a unique value to generate your answers in puzzlebox. kauf0095 will be used from the above email address.

Failing to use your exact Terpmail Email Address / DirectoryID may result in 0 credit. Pay attention to warnings that indicate problems with this.

The first phase in Puzzlebox expects numbers as input so write something like 1 2 3. Then compile and run the puzzlebox program on it.

>> make puzzlebox                             # compile puzzlebox
gcc -Wall -g -c puzzlebox.c
gcc -Wall -g -o puzzlebox puzzlebox.o

>> cat input.txt                              # show contents of input.txt
kauf0095@terpmailumd.edu
1 2 3

>> puzzlebox input.txt
========================================
PROBLEM 2: Puzzlebox
UserID 'KAUF0095' accepted: hash value = 1936486779
PHASE 1: A puzzle you say? Challenge accepted!

Ah ah ah, you didn't say the magic word...
Failure: Double debugger burger, order up!

RESULTS: 0 / 30 points

This is automated with the Makefile target make test-prob2:

>> make test-prob2                       # compile/run puzzlebox with input.txt
gcc -Wall -g -c puzzlebox.c
gcc -Wall -g -o puzzlebox puzzlebox.o
puzzlebox input.txt
========================================
PROBLEM 2: Puzzlebox
UserID 'KAUF0095' accepted: hash value = 1936486779
PHASE 1: A puzzle you say? Challenge accepted!

Ah ah ah, you didn't say the magic word...
Failure: Double debugger burger, order up!

RESULTS: 0 / 30 points

These initial forays are not positive (0 / 30 points) but the real meat of the problem is in examining the source code and determining inputs for input.txt.

4.3 `gdb` The GNU Debugger

You will definitely need to use a debugger to solve the puzzlebox and gdb is the quintessential debugger associated with our compiler gcc. It is installed by default on all lab machines and is an easy install on must Linux machines.

For a quick overview of GDB, here are some resources

Quick Guide to gdb: The GNU Debugger: Page describing how to start the debugger, a sample session using puzzlebox, an overview of the most common commands.
CppCon 2015: Greg Law "Give me 15 minutes & I'll change your view of GDB": Video giving basic overview of how to run gdb on simple programs with an emphasis on differences between "normal" mode and TUI mode
GNU GDB Debugger Command Cheat Sheet: Extensive list of commands
Debugging with GDB: Official manual for gdb

4.4 Typical Cycle

A typical cycle of working on puzzlebox will be the following.

Start the debugger with puzzlebox
```
  >> gdb -tui ./puzzlebox
```
Set the arguments array to input.txt
```
set args input.txt
```
Set a breakpoint at a phase like phase03
```
break phase03
```
Run the program
```
run
```
Do some stepping / nexting
```
step
next
```

Print some variables

print normal_val
print/x val_in_hex
print/t val_in_binary

Make some changes to input.txt in a different window
Re-run the program to see if things have changed favorably
```
kill
run
```

4.5 Kinds of Puzzles

The puzzles presented in the different phases make use of a variety of C program techniques which we have or will discuss including.

Bit-wise operations and their use in place of arithmetic
String and character array manipulations
Interpreting bits as one of several kinds of things (integer, float, character) through pointers and unions
More extensive C control structures like goto and labels

4.6 Tests for `puzzlebox.c` grading 30

puzzlebox.c itself reports how many points one can earn at the end of its execution.

Currently there are 40 points available but 30 points is considered full credit.

If any additional points are earned, they will be counted as Makeup Credit for Projects to make up for credit lost on past or future projects. Your total score on All Projects cannot exceed 100% so any points beyond will simply be dropped.

Run the following command to 'test' puzzlebox:

make test-prob2

5 Problem 3: Tree Sets in C

5.1 Overview

This problem implements a rudimentary "tree set" application in C along with a program that uses it. The architecture is similar to a past lab problem involving linked lists so reviewing that code can provide some insight.

Basic Binary Search Trees are covered in most introductory data structure classes such as CMSC131 and 132. A "Tree Set" is simply a binary search tree which only allows one copy of each unique item in it. When searching for an item, the organization of the binary search tree is exploited to speed up the location of the time or determine that it is not present. When adding items, duplicate items are discarded without altering the tree.

HINT: The basic structure of this application closely mirrors a Discussion Exercise dealing with linked lists. An efficient way to get started on the project is to copy over some of the structure from that exercise for use here.

5.2 `treeset_main` Demonstration

The intent of this problem is to develop a small application which behaves as the following demo indicates. Study this demo carefully as it illustrates most of the capabilities of the application with each capability being checked by automated tests.

> make treeset_main  # build with Makefile
gcc -Wall -Wno-comment -Werror -g  -c treeset_main.c
gcc -Wall -Wno-comment -Werror -g  -c treeset_funcs.c
gcc -Wall -Wno-comment -Werror -g  -o treeset_main treeset_main.o treeset_funcs.o

> ./treeset_main                   # run main program
Treeset Main
Commands:
  print:          shows contents of the tree in reverse sorted order
  size:           prints the number of nodes currently in the tree
  clear:          eliminates all elements from the tree
  quit:           exit the program
  add <name>:     inserts the given string into the tree, duplicates ignored
  find <name>:    prints FOUND if the name is in the tree, NOT FOUND otherwise
  preorder:       prints contents of the tree in pre-order which is how it will be saved
  save <file>:    writes the contents of the tree in pre-order to the given file
  load <file>:    clears the current tree and loads the one in the given file
TS#> add Lucas                  # add some data
TS#> add Mike
TS#> add Dustin
TS#> add Will
TS#> add El
TS#> size                       # show number of nodes in the tree
5 nodes
TS#> print                      # print tree, reverse order, indentation indicates depth/structure
    Will                        # root->right->right
  Mike                          # root->right
Lucas                           # root
    El                          # root->left->right
  Dustin                        # root->left
TS#> preorder                   # show tree in preorder, root first
Lucas                           # root
  Dustin                        # root->left
    El                          # root
  Mike                          # root->right
    Will                        # root->right->right
TS#> find Mike
FOUND
TS#> find Nancy
NOT FOUND
TS#> add Nancy                  # add Nancy
TS#> size                       # show size of tree has increased
6 nodes
TS#> print
    Will
      Nancy                     # root->right->right->left
  Mike
Lucas
    El
  Dustin
TS#> add Mike                   # adding duplicates is ignored
duplicate element ignored
TS#> add El
duplicate element ignored
TS#> find Max
NOT FOUND
TS#> add Max                    # add max
TS#> print
    Will
      Nancy
  Mike                          # root->right->left
    Max
Lucas
    El
  Dustin
TS#> find Max
FOUND
TS#> find Barb
NOT FOUND
TS#> add Barb                   # add Barb
TS#> print
    Will
      Nancy
  Mike
    Max
Lucas
    El
  Dustin
    Barb                        # root->left->left

TS#> save stranger.tree         # save tree into named file
TS#> clear                      # eliminate tree
TS#> size                       # show tree is empty now
0 nodes
TS#> print                      # print shows nothing: empty tree
TS#> add Demigorgon             # add Demigorgon to empty
TS#> print
Demigorgon                      # root
TS#> load stranger.tree         # clear tree, replace with contents of file
TS#> size                       # 8 nodes loaded from file
8 nodes
TS#> print                      # tree is restored
    Will
      Nancy
  Mike
    Max
Lucas
    El
  Dustin
    Barb
TS#> add Jim                    # add Jim
TS#> add Joyce                  # add Joyce
TS#> print                      # show tree
    Will
      Nancy
  Mike
    Max
Lucas                           # root
        Joyce                   # root->left->right->right->right
      Jim                       # root->left->right->right
    El
  Dustin
    Barb
TS#> load stranger.tree         # clear and reload from file
TS#> print                      # restored to previous contents
    Will
      Nancy
  Mike
    Max
Lucas
    El
  Dustin
    Barb
TS#> quit                       # quit program

5.3 `tree_funcs.c`: tree functions

Examine the header file tree.h to see the two C structs which will be used to represent trees.

// Nodes that go into the tree
typedef struct tsnode {
  char name[128];               // tsnode data
  struct tsnode *left;          // left branch,  NULL if not present
  struct tsnode *right;         // right branch, NULL if not present
} tsnode_t;

// Type of tree itself
typedef struct {
  tsnode_t *root;               // root of tree, NULL if tree empty
  int size;                     // number of tsnodes in tree
} treeset_t;

The tree set will track unique strings each of which is stored in a tsnode_t struct. The treeset_t struct tracks the root of the tree along with the total number of nodes in the tree.

Standard operations are supported by the tree.

Inserting item
Searching for an element
Clearing the entire tree
Printing tree in reverse sorted order which is handy for visualization
Printing the tree in pre-order (root first, then children) which is useful for saving and loading to files
Saving and loading from a file

These are broken down into the following C functions which you will need to implement in the file treeset_funcs.c. Keep in mind that to honor the binary search tree property (left less than / right greater than), you will need to use the return values of strcmp() function calls as string data is present in the tree.

Below is an outline of the functions that should be present in treeset_funcs.c along with guiding documentation about how to implement them.

// treeset_funcs.c: Provides a small library of functions that operate
// on binary search trees of unique strings.

#include "treeset.h"

void treeset_init(treeset_t *tree);
// Initialize the given tree to have a null root and have size 0.

int treeset_insert(treeset_t *tree, char name[]);
// Inserts given name into a binary search tree. Uses an ITERATIVE
// (loopy) approach to insertion which starts a pointer at the root of
// the tree and changes its location until the correct insertion point
// is located. Returns 1 if a new tsnode is created and 0 if a duplicate
// name is found in the tree already in which case the name is not
// added.

int treeset_find(treeset_t *tree, char name[]);
// Determines whether name is present or not in the tree using binary
// search. Returns 1 if name is present and 0 otherwise. Uses an
// ITERATIVE (loopy) approach which starts a pointer at the root of
// the tree and changes it until the search name is found or
// determined to not be in the tree.

void treeset_clear(treeset_t *tree);
// Eliminate all tsnodes in the tree setting its contents empty. Uses
// recursive tsnode_remove_all() function to free memory for all tsnodes.

void tsnode_remove_all(tsnode_t *cur);
// Recursive helper function which visits all tsnodes in a tree and
// frees the memory associated with them. This requires a post-order
// traversal: visit left tree, visit right tree, then free the cur
// tsnode.

void treeset_print_revorder(treeset_t *tree);
// Prints the elements of the tree in reverse order at differing
// levels of indentation which shows all elements and their structure
// in the tree. Visually the tree can be rotated clockwise to see its
// structure.

void tsnode_print_revorder(tsnode_t *cur, int indent);
// Recursive helper function which prints all elements in the tree
// rooted at cur in reverse order: traverses right subtree, prints cur
// tsnode, traverses left tree. Parameter 'indent' indicates how far to
// indent (2 spaces per indent level).

void treeset_print_preorder(treeset_t *tree);
// Print all the data in the tree in pre-order with indentation
// corresponding to the depth of the tree. Makes use of
// tsnode_write_preorder() for this.

void treeset_save(treeset_t *tree, char *fname);
// Saves the tree by opening the named file, writing the tree to it in
// pre-order with tsnode_write_preorder(), then closing the file.

void tsnode_write_preorder(tsnode_t *cur, FILE *out, int depth);
// Recursive helper function which writes/prints the tree in pre-order
// to the given open file handle. The parameter depth gives how far to
// indent tsnode data, 2 spaces per unit depth. Depth increases by 1 on
// each recursive call. The function prints the cur tsnode data,
// traverses the left tree, then traverses the right tree.

int treeset_load(treeset_t *tree, char *fname );
// Clears the given tree then loads new elements to it from the
// named. Repeated calls to treeset_insert() are used to add strings read
// from the file.  If the tree is stored in pre-order in the file, its
// exact structure will be restored.  Returns 1 if the tree is loaded
// successfully and 0 if opening the named file fails in which case no
// changes should be made to the tree.

5.4 `treeset_main.c`: main function / application

In treeset_main.c implement an interactive program which allows users to type commands to manipulate a treeset. Most of these commands will dispatch directly to an analogous function in treeset_funcs.c. Example: the add command will likely call treeset_insert().

Once the files treeset_funcs.c and treeset_main.c are present, the provided Makefile should compile the complete program and allow it to run as follows:

>> make treeset_main
gcc -Wall -Wno-comment -Werror -g  -c treeset_main.c
gcc -Wall -Wno-comment -Werror -g  -c treeset_funcs.c
gcc -Wall -Wno-comment -Werror -g  -o treeset_main treeset_main.o treeset_funcs.o

>> ./treeset_main
Treeset Main
Commands:
  print:          shows contents of the tree in reverse sorted order
  size:           prints the number of nodes currently in the tree
  clear:          eliminates all elements from the tree
  quit:           exit the program
  add <name>:     inserts the given string into the tree, duplicates ignored
  find <name>:    prints FOUND if the name is in the tree, NOT FOUND otherwise
  preorder:       prints contents of the tree in pre-order which is how it will be saved
  save <file>:    writes the contents of the tree in pre-order to the given file
  load <file>:    clears the current tree and loads the one in the given file
TS#>

The following sections provide some implementation details.

Read commands, Execute

The basic flow of tree_main.c follows a provided lab exercise code closely.

Create a tree variable, likely on the stack as a local variable in main()
Start a loop that terminates when the user exits or there is no more input
Each time the user enters a string, read it and check for one of the built-in commands
On identifying the command, potentially read another string if needed (commands like add and find)
Call an appropriate treeset_XXX() function to handle the command

Note that each of the commands that is mentioned such as print and clear will need to do a specific action in the program so likely a large if/else if/else control structure will feature in most implementations.

Supported Commands

To indicate to users of the program the supported commands, use the following code to print out the initial option list.

  printf("Treeset Main\n");
  printf("Commands:\n");
  printf("  print:          shows contents of the tree in reverse sorted order\n");
  printf("  size:           prints the number of nodes currently in the tree\n");
  printf("  clear:          eliminates all elements from the tree\n");
  printf("  quit:           exit the program\n");
  printf("  add <name>:     inserts the given string into the tree, duplicates ignored\n");
  printf("  find <name>:    prints FOUND if the name is in the tree, NOT FOUND otherwise\n");
  printf("  preorder:       prints contents of the tree in pre-order which is how it will be saved\n");
  printf("  save <file>:    writes the contents of the tree in pre-order to the given file\n");
  printf("  load <file>:    clears the current tree and loads the one in the given file\n");

Paths to Tree files for Saving and Loading

Saving and loading trees involves writing to files. The names associated with the files must be specified as a path so that if tree files are to be saved or loaded from subdirectories, include this as part of the path. For example, the stranger.tree file is provided in the data/ directory so can be loaded as follows.

> ./treeset_main
...
TS#> load data/stranger.tree              # load the provided tree from a subdirectory
TS#> print                                # show in reverse sorted order
    Will
      Nancy
  Mike
    Max
Lucas
    El
  Dustin
    Barb
TS#> preorder                             # show in preorder
Lucas
  Dustin
    Barb
    El
  Mike
    Max
    Will
      Nancy
TS#> add Demigorgon                       # add more data
TS#> save cur.tree                        # save in the current directory
TS#> clear
TS#> print
TS#> load cur.tree                        # load cur.tree from the current directory
TS#> print
    Will
      Nancy
  Mike
    Max
Lucas
    El
  Dustin
      Demigorgon                          # added prior to the save
    Barb
TS#> add Jim                              # add more data
TS#> save data/other.tree                 # save to a new file in data/ subdir
TS#> quit

Command Echoing: `-echo` option to `treeset_main`

Some users may wish to "script" this the tree program. An example of such a script is in data/stranger-demo.script which looks like a lot of user commands:

add Lucas
add Mike
add Dustin
add Will
add El
size
print
preorder
find Mike
find Nancy
add Nancy
size
print
add Mike
add El
find Max
add Max
print
find Max
find Barb
add Barb
print
save stranger.tree
clear
size
print
add Demigorgon
print
load stranger.tree
size
print
add Jim
add Joyce
print
load stranger.tree
print
quit

This can be fed directly to the program without needing type it using Unix pipes as per the following:

> cat data/tree-demo.script | ./treeset_main -echo

Notice the use of a command line argument for treeset_main: the -echo option. This is a REQUIRED feature which prints commands typed by users to the screen. To implement this, do the following.

Model the structure of command echoing after what is shown in related Lab work.

Use a variable in main() to indicate whether command echoing is on or off; set it to off by default
Check when main() starts whether command line argument 1 is set to -echo in which case turn echoing on. A condition like the following is useful.
```
  if(argc > 1 && strcmp("-echo",argv[1])==0) {
```
Each command should check for echoing and print the command being run along with any arguments to it. This technique is demonstrated in related lab work.

It will take some work to get the exact placement of echoes correct but will ultimately lead to nice results that involve LITTLE typing like the example below.

>> cat data/stranger-demo.script | ./treeset_main -echo
Treeset Main
Commands:
  print:          shows contents of the tree in reverse sorted order
  size:           prints the number of nodes currently in the tree
  clear:          eliminates all elements from the tree
  quit:           exit the program
  add <name>:     inserts the given string into the tree, duplicates ignored
  find <name>:    prints FOUND if the name is in the tree, NOT FOUND otherwise
  preorder:       prints contents of the tree in pre-order which is how it will be saved
  save <file>:    writes the contents of the tree in pre-order to the given file
  load <file>:    clears the current tree and loads the one in the given file
TS#> add Lucas
TS#> add Mike
TS#> add Dustin
TS#> add Will
TS#> add El
TS#> size
5 nodes
TS#> print
    Will
  Mike
Lucas
    El
  Dustin
TS#> preorder
Lucas
  Dustin
    El
  Mike
    Will
TS#> find Mike
FOUND
TS#> find Nancy
NOT FOUND
TS#> add Nancy
TS#> size
6 nodes
TS#> print
    Will
      Nancy
  Mike
Lucas
    El
  Dustin
TS#> add Mike
duplicate element ignored
TS#> add El
duplicate element ignored
TS#> find Max
NOT FOUND
TS#> add Max
TS#> print
    Will
      Nancy
  Mike
    Max
Lucas
    El
  Dustin
TS#> find Max
FOUND
TS#> find Barb
NOT FOUND
TS#> add Barb
TS#> print
    Will
      Nancy
  Mike
    Max
Lucas
    El
  Dustin
    Barb
TS#> save stranger.tree
TS#> clear
TS#> size
0 nodes
TS#> print
TS#> add Demigorgon
TS#> print
Demigorgon
TS#> load stranger.tree
TS#> size
8 nodes
TS#> print
    Will
      Nancy
  Mike
    Max
Lucas
    El
  Dustin
    Barb
TS#> add Jim
TS#> add Joyce
TS#> print
    Will
      Nancy
  Mike
    Max
Lucas
        Joyce
      Jim
    El
  Dustin
    Barb
TS#> load stranger.tree
TS#> print
    Will
      Nancy
  Mike
    Max
Lucas
    El
  Dustin
    Barb
TS#> quit
>>

5.5 Grading Criteria for Problem 3 grading 40

The following criteria will be checked in this problem.

Weight	Criteria
	AUTOMATED TESTS via `make test-prob3`
20	`test_treeset.org` tests
	20 tests for `treeset_main` executable, exercises functions in `treeset_funcs.c`
	All tests run under Valgrind
	1 point per test passed
	Code compiles without warnings (`make clean` followed by `make test-prob3` gives no errors/warnings)
	NOTE: run individual tests via `make test-prob3 testnum=4`
	MANUAL INSPECTION
15	`treeset_funcs.c`
	Clear commenting indicating intent during functions such as "go left" or "item found"
	Clear use of binary search principle: left for less, right for greater, use of string functions for this
	Effective use of iteration in insert and find functions
	Effective use of recursion in printing and removal functions
	Relatively short functions: nothing needs to be too long (40 lines tops)
	Correct order of visiting/freeing in `tsnode_remove_all()`
	Use of one general `tsnode_write_preorder` in both `treeset_print_preorder()` and `treeset_save()`
	Tree cleared prior to load in `treeset_load()` to prevent memory leaks
	File closed after finished during saving and loading


5	`treeset_main.c`
	Comments indicating what high-level command is being implemented in each part of `main`
	Clear structure of main loop, reading commands, selecting actions
	Use of string functions to identify which command to execute
	Easy to recognize reading of additional arguments for `add/find/etc.`
	Clear efforts to honor `-echo` option and echo commands
	Clear effort to free all memory prior to exit by clearing tree on exit

6 Project Submission

6.1 Submit to Gradescope

Refer to the Project 1 instructions and adapt them for details of how to submit to Gradescope. In summary they are

Type make zip in the project directory to create p2-complete.zip
Log into Gradescope, select Project 2, and upload p2-complete.zip

6.2 Late Policies

You may wish to review the policy on late project submission which will cost 1 Engagement Point per day late. No projects will be accepted more than 48 hours after the deadline.

https://www.cs.umd.edu/~profk/216/syllabus.html#late-submission