CSE 303, Autumn 2009
Homeworks 5 and 6: ascii-to-morse

Each HW 100 points

In this assignment, you will develop a larger software system composed of multiple files and multiple executable programs. (It is a slightly modified version of an assignment from Magda Balazinska for an early 303, or perhaps from someone she borrowed from.) By doing so, you will:

Each of you must complete Parts 1-5 (inclusive) on your own!  Parts 6-10 must be done in pairs. 

System overview

In this assignment, you will build programs to convert between ascii and Morse code. In Morse code, letters are represented by various sequences of dots and dashes. Letters are separated by spaces, and words are separated by slashes ('/'). For example, the string:

hello world example

Translates into:

.... . .-.. .-.. --- / .-- --- .-. .-.. -.. / . -..- .- -- .--. .-.. . /

Note that there is a space on either side of the / character.

For more information about Morse code, here is the link to the Wikipedia entry.

Getting ready

Download the file: hw56.tar.gz.  Extract all the files for this assignment using the following command:

> tar zxvf hw56.tar.gz

You should now see a directory called hw4. If this procedure did not work for you, please contact the staff or talk to another student in the class.

General advice 

Implement at most ONE function at the time and test it. Even better, implement one piece of a function at the time and test that piece. For example, write only the code that opens a file and prints "Successfully opened file. Test that piece. Then try to actually read something from the file. The less code you write between each test, the faster you end-up coding because you spend less time debugging. Experienced software developers almost always take this approach: they write as little code as possible and they test often.

1. Creating the ascii-to-Morse conversion module

We provide you with a text file, morse.txt, that contains the Morse code representation of each letter of the English alphabet.

At the core of the module, there is a lookup table that maps ascii characters to the corresponding Morse code strings. This lookup table takes the form of a primitive hashtable defined as a two-dimensional array of characters:

  #define NB_CHARS 26
#define MORSE_MAX 4

typedef struct a2m_lookup_table {
char table[NB_CHARS][MORSE_MAX+1];
} A2MLookupTable;

Please examine the files a2m_index.h and a2m_index.c that we provide.

In the start-up code that we provide, you will find prototypes for the following five functions. Please implement ONLY these five functions for now:

Note: You are allowed to add additional functions to a2m_index.c that will remain private to the module (i.e, that will not go into the header file). You are NOT allowed to add a main function to this module. To test your module, see Problem 2.

Remember that the null-character terminates all strings. Hence, if Morse code strings are up to four dots and dashes in length, you need a buffer of length five to store any such string. Related to this, to copy and compare strings, we recommend that you use the standard functions strncmp and strncpy because they explicitly check that you do not read or write memory past the boundaries of your buffers.

2. Testing your ascii-to-Morse lookup table

In a file called test_a2m_index.c, we provide a simple program that will help you test the above functions. Note that test_a2m_index.c needs to include a2m_index.h.  Feel free to modify this file to add more tests. At this point (below you will build a Makefile to help), you can compile your code with the following command:

> gcc -Wall -g -o test_a2m_index test_a2m_index.c a2m_index.c

Hints:

3. Complete the ascii-to-Morse conversion module

The ascii-to-Morse conversion module contains several additional functions that you must implement:

Hints:

4. Complete your test file

Please add extra tests to the file test_a2m_index.c. Each function that appears in a2m_index.h should be invoked at least once in your test file test_a2m_index.c. You should first test your module on strings containing a single character. Then, you should test your module on strings with a single word. FInally, you should test your module on strings with multiple words.

5. Simple Makefile

Write a Makefile with the following three targets: test_a2m_index, all (should only build test_a2m_index for now), and clean. Warning! Before creating and testing the clean target, make a backup of all your files. It is easy to make a mistake and cause make clean to delete all your code!

6. Interactive ascii-to-Morse converter

In a file called a2m.c, write a C program that takes the name of a file with the ascii-to-Morse mappings as a command-line argument and performs the following actions:

Update your Makefile to add a target for a2m. Make sure that the target all builds both a2m and test_a2m_index.

Hints:

7. Morse-to-ascii lookup tree

You will now build a module to convert Morse code to ascii.

To convert in this direction, instead of using a simple lookup, we would like you to use a binary tree. In this section, we refer to the binary tree simply as "tree".

Each node in the tree should correspond to a struct. Each struct should have two pointers labeled "dot" and "dash". In particular, we suggest that you use the following struct:

   
#define MORSE_MAX 4
typedef struct node {
char ascii; // The ascii character that corresponds to the sequence of dots and dashes from the root to this node
char morse[MORSE_MAX+1]; // This field is not needed. It is redundant. Use it for debugging if you want, or get rid of it.
struct node *dot;
struct node *dash;
} Node;

Starting from the root of the tree, it should be possible to follow a sequence of "dot" and "dash" pointers to find the ascii character that matches the corresponding sequence of dots and dashes in Morse code. For example, starting from the root of the tree and following a "dash", a "dot", and another "dot" should lead to the letter "d". More specifically, walking down the tree will lead to an instance of Node with the field ascii set to 'd' and the field Morse set to the string "-.." (if you chose to keep that field).

The root of the tree will be a Node with empty values for the ascii character and the corresponding string in Morse code. You can also initialize these fields to some defaults that will indicate that no character corresponds to this location in the tree.

In a file called m2a_index.c, write a module that provides a set of utility functions to convert from Morse code to ascii. Your module should implement the following functions:

We do not provide you any start-up code for this module. It is up to you to choose the proper function prototypes and otherwise design and implement this module.

In a file called m2a_index.h, put the prototypes of the functions that form the public interface of your module. You should also put the definition of the structure Node into the header file.

Once again, write as little code as possible and test as often as possible.

Please comment the functions that appear in the header file.

Hint:

8. Testing your Morse-to-ascii lookup tree

In a file called test_m2a_index.c, write a simple program to test your tree. Each function that appears in m2a_index.h should be invoked at least once. Remember that test_m2a_index.c needs to include m2a_index.h.

Include a target for this new test in your Makefile. Make sure that target all also builds this test program.

9. Interactive Morse-to-ascii converter

Write a C program called m2a.c that prompts the user for a string in Morse code and translates it into ascii.

As for a2m.c, your program should perform some basic error checking and should prompt the user for new strings until the user chooses to exit the program. You can assume that the user will never enter more than 256 characters.

Include a target for m2a.c in your Makefile. Make sure that target all also builds this program.

10. Dictionary module

Extend the functionality of a2m.c and m2a.c with a dictionary that keeps track of the previously translated strings. Both programs should use the same dictionary module.

The extended programs should allow the user to perform the following four actions, selected from a menu using 4 numbers:

We would like you to implement the dictionary in a file called dict.c. The dictionary should hold the previously translated strings in a linked list. To help you with this question, we provide you the header file dict.h and a partial implementation in file dict.c. You only need to complete the function that deletes elements from the list. The dict module will be used by a2m and m2a to provide the dictionary functionality to users. Please note that for simplicity, we chose to use fixed-size buffers to hold strings. This choice limits the length of a string that the system can translate. You can get rid of this limitation if you want, although we recommend that you use this simpler version.

Here is an example of the output while using a2m, with the user input in boldface. Using m2a should work similarly, except for the direction of the translation:

  To use a2m
1: translate a string
2: view dictionary
3: delete a string from dictionary
4: exits
> 1
Enter string: hello world
Morse is: .... . .-.. .-.. --- / .-- --- .-. .-.. -.. /
> 1
Enter string: bananas
Morse is: -... .- -. .- -. .- ... /
> 1
Enter string: apples
Morse is: .- .--. .--. .-.. . ... /
> 1
Enter string: oranges
Morse is: --- .-. .- -. --. . ... /
> 2
apples -> .- .--. .--. .-.. . ... /
bananas -> -... .- -. .- -. .- ... /
hello world -> .... . .-.. .-.. --- / .-- --- .-. .-.. -.. /
oranges -> --- .-. .- -. --. . ... /
> 3
Enter string to delete: hello world
> 2
apples -> .- .--. .--. .-.. . ... /
bananas -> -... .- -. .- -. .- ... /
oranges -> --- .-. .- -. --. . ... /
> 4

Be sure you use the same menu numbers above for our tests. Your exact output format does not matter as long as it contains the correct Morse or ASCII translation somewhere.

You should be able to send a test file of inputs into your program to automate the translation of ASCII strings to Morse strings. For example, we provide you a test file called 'test-a2m.txt' with the following lines, including an ending linebreak:

    
1
hello world
1
bananas
1
apples
1
oranges
2
3
hello world
2
4

you should be able to type the following command to get the output given above (without the input commands in boldface):

./a2m Morse.txt < test-a2m.txt

Compare that the output you are getting is similar to the one in the file test-a2m.output.txt. Once again, the output does not have to be identically formatted. It only needs to contain the correct Morse or ASCII strings.

Similar instructions apply for testing m2a. We provide you the files test-m2a.txt and test-m2a.output.txt to help you verify that your program will work with our test scripts.

Hint: If you are using fgets to read the string to translate, you should also use fgets to read the user menu choice.