Program Specification

What is 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.

Your Task: write tests for a T9 implementation¶

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 the algorithm¶

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.

The 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.

The safe_assert test 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, workflow and getting started¶

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.

You should use each function that are declared in t9_lib.h at least three times (except DestroyT9()). You don’t have to write tests to check for appropriate error messages.

Your tests must always pass when run against the correct implementation. However, they should fail when run against the buggy version; our autograder will evaluate your tests on both this sample and other, more involved, bugs.

In past assignments, you have had all of the source code available to you, and were able to try things out incrementally to see what happens. This is not quite true in HW5: we provide no way to edit the T9 implementation. This mimics a true test-driven development workflow, where your goal is to write the tests first. You must come up with test cases using only your mind, the correct implementation (which, in the real word, would also be imagined), and the autograder output. You should rely on the first two more than the autograder, since it will not give you all the information you need to identify the scenario.