Homework: Test Suite for T9

Due: Monday, November 4, 2024, at 11:59pm

Jump To:

Goals
Synopsis
Set-Up
Background Information
Provided Files
Your Task
Assessment
Turn-in instructions

Synopsis

Testing is an essential component in software development. In this assignment you will write tests to evaluate an implementation of “T9”. In the next homework assignment you will use the test suite developed here to practice Test Driven Develpoment as you build a trie data-structure to run the T9 system.

For this homework we will provide you with a number of files comprising the trie behavior specification, a working version of the code to test, and a testing framework `safe_assert`. You will develop test cases using your understanding of the code specifications. You will be able to evaluate your test-suite using a working version of T9, and the Gradescope autograder.

This project should be done independently. If you work with a classmate, make sure you are each editing and working on your own set of files. You should not copy and paste code.

Background Information

T9

T9 was an algorithm used back in the day when everybody had flip phones, whose only input interface was the buttons to dial a phone number. However, these phones did have letters on the buttons. The problem is, how can we know which of the 3 or more letters the user “meant” when they pressed that button?

T9 is an algorithm to help predict which letters, and which word overall, the user meant. It works by translating each word in the dictionary into its number sequence. For example: apple => 27753, book => 2665. It can then check the sequence of numbers you type to see if it matches a known word from its dictionary. If it finds a plausible word which matches, that word is entered for you.

However, since multiple letters map to a single number, many key sequences represent multiple words. For example, the input 2665 represents “book” and “cool”, among other possibilities.

To remedy this, T9 has a special extra input: “#”, or the “pound” sign. Typing this character after a number sequence chooses the next matching word. For our purposes, “next” refers to the order they appeared in the dictionary: if “book” was listed before “cool”, then typing 2665 will return “book” while typing “2665#” will return “cool”.

The “0”, “1” and “*” buttons are not used for T9.

Test-Driven Development

One common style of software engineering is called “Test-Driven Development” (TDD). With this workflow, you write tests for the intended behavior before writing the code which implements that behavior. This is what you will be doing!

For the purposes of this assignment, you are only doing the first part of TDD: writing the tests. We have provided a header file which specifies interface for T9, as well as an object file which contains a completely correct implementation of that interface. You will write unit tests for all functions exposed by the T9 module. See the “provided files” section below for more details on the starter files and workflow.

As you are writing tests, you can run them against our provided implementation of the algorithm. All your unit tests must pass when run on the correct solution — that is the point of automated testing! However, our autograder will run your tests against buggy implementations too, which are not provided with the starter code. Your score is an indicator of the number of buggy programs your unit tests identified.

The real challenge in this assignment is in thinking through the cases which should be tested. Some bugs are related to handling of edge-cases, while others are a consequence of slight errors in the basic calculations performed by T9.

Exploring T9

Part of the goal of TDD is that you don’t know how the algorithm is implemented, so you aren’t biased by the aspects you believe to be correct – you’re going in blind! That being said, you do need to understand its behavior.

We have provided you with an implementation of the T9 algorithm, including an interactive program called ./t9_demo and two sample dictionaries. When you run the demo and provide a dictionary file as a command-line argument, it will load those words and then prompt you to enter a sequence of numbers. You can enter a sequence of digits 2 through 9, followed by any number of “#” signs. If you enter only digits, it will print the first word matching those numbers (e.g. “book” for 2665). If you append a “#” symbol to your digit sequence, it will print the next word alphabetically which also matches (e.g. “cool” for 2665#). You can append as many “#”s as desired. Here is a transcript of running ./t9_demo small_dictionary.txt:

Welcome to T9!
Type "exit" and press Enter to quit.
Enter key sequence:
> 2665
book
Enter key sequence:
> 2665#
cool
Enter key sequence:
> 76737
ropes
Enter key sequence:
> 76737###
No entry for 76737###.
Enter key sequence:
> 234#5
No entry for 234#5

This program is a simple wrapper around the interface you will be testing, and you can read its code in the t9_demo.c file. See the “provided files” section below to learn how to compile this program.

T9 Interface

Our T9 algorithm is specified in a header file, called t9_lib.h and provided in the starter code. DO NOT MODIFY THIS FILE. Each method is documented and has associated pre- and post-conditions in comments above them; these are your primary reference for how the code is intended to work. You should read these comments thoroughly.

It is important to call attention to the type declaration at the top of the header:

struct t9;
typedef struct t9 t9;

This declares a struct, and then uses typedef to make it available under the name T9. You will notice, however, that the struct is completely empty: this is intentional. It means that the implementation of T9 will, internally, define the fields within the struct, but users of the header do not know what those fields are. This type can only be used as a pointer type to be returned from, and passed to, other T9 functions.

The provided demo program, t9_demo.c, is a great reference for the usage of this interface, and a good way to familiarize yourself with the behavior of T9.

Safe-Assert Framework

We gave a brief overview of the custom safe_assert test framework in lecture. We have also provided two example unit-tests to give you a starting point and reference; you may want to follow their example when writing your own.

As a reminder, there should only ever be one “suite” declaration in the file, and there should only be one file for tests.

Provided Files

Your hw5 folder contains the following files:

• t9_tests.c: Starter file for your tests. You can change the sample tests however you wish. You must rename the test with a silly name to accurately describe its behavior.
• t9_demo.c: Demo program to try out the correct T9 implementation.
• dictionary.txt: Large dictionary file, containing most of the English language.
• small_dictionary.txt: Small dictionary file, containing just a handful of words.
• safe_assert.h: The test framework you will be using.
• t9_lib.h: The header describing T9’s interfaces. These are the functions you will be testing.
• Makefile: Discussed below.
• t9_lib.o: A correct, bug-free implementation of T9.
• t9_lib_buggy.o: A slightly-buggy implementation of T9 to play with. Our autograder will test against these bugs and more.

The Makefile is there to help you work with our files. To run your tests on the correct T9 implementation (t9_lib.o), run the “test” target:

$ make test
./t9_tests
Suite: T9
    Empty initialization
        (OK)
    Rename me! What is this testing?
        (OK)
Final results:
    ALL PASS (2/2)

Other helpful targets are the “test-buggy” target, which will run your tests on our buggy T9 implementation (t9_lib_buggy.o), and “t9_demo”, which will compile the demo program to an executable of the same name.

To get started, try using make on a variety of targets to observe the behavior. You can also run ./t9_demo dictionary.txt to experiment with the interface directly.

Assessment

This homework is worth a total of 60 points. There will be an autograder, with no manual grading for this homework. The autograder evaluates whether your test suite catches a pre-defined set of errors. You are encouraged to resubmit until you achieve a score of 60 points.

Your tests file should contain a variety of unit tests which you write by hand to cover edge-cases, simple data, and extremes, as you see fit. Since these are primarily “unit” tests, each test should be as small as possible: it should test one thing, and one thing only. This might mean you have to create a T9 instance, perform an operation or two on it, and then free it; however, try not to lump all cases into one. You should explicitly call and test every T9 function at least three times (except DestroyT9()).

You will need to rename one of our provided test cases to accurately describe what it does. You are also free to modify or remove this test case, but will likely have to replace it with a new one.

When submitting to the autograder, it may be tempting to delete or replace test cases. We recommend you keep them instead! Having too many tests is rarely a problem, as long as they all are correct (i.e., pass on a correct implementation).

Our own reference test suite contains around 30 tests; yours may contain more or fewer, but will likely be at least 20 or so.

You don’t have to cover all the cases to get full points.