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:

• Learn how to develop a larger system one piece at the time, testing each piece as soon as you create it. The assignment has multiple parts, not only for academic purposes, but also to show some of the steps that software developers take when developing even simple systems.
• Get experience programming dynamic data structures including a binary tree and a list.
• Learn how to read data from files in C.
• Practice writing simple Makefiles.
• Get some limited experience working in a small team.
  

• Parts 1-5 comprise Homework 5: this is due Sunday November 22, 2009, 11:30PM. 
  
• Parts 6-10 comprise Homework 6: this is due Tuesday December 1, 2009, 11:30PM.
• You may pick your own teammates: email the staff your pairing as soon as you wish, but no later than noon on Friday November 20, 2009.  At that point, the staff will assign pairs among those who haven't paired up already.  (Yes, I may need to create odd-numbered sized team; but you cannot propose to be this team!)
  
• For HW6, you may start from either of the team members' HW5 solution.
• We will provide additional information about reasonable ways to work together and keep your files and updates straight.
• Each team will share the grade on HW6 -- unless we have evidence that there is a serious gap in the contributions of each student.  You are each responsible for understanding every part of the solution to HW6, whether you wrote it, your partner wrote, or you both wrote it.
  

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.

• As a first step, create a module (in C, this is usually a single file or a small set of files) that provides a set of utility functions to convert from ascii to Morse code. The source code for the module should go into a file called a2m_index.c. The prototypes of the functions that form the public interface of the module (i.e., the functions that will be invoked by clients using your module) should go into the header file, called a2m_index.h. We provide you this header file along with the function prototypes. We also provide you a skeleton for a2m_index.c.

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:

• Function hash: in the file a2m_index.c, the function int hash(char c), maps a character to an index in the lookup table: i.e., for a given ascii character, the function returns the index in the lookup table with the corresponding Morse code representation of the character. The function should be very simple. This function is internal to the module, which means it will not be invoked by clients of the module.  Thus it does not appear in the header file.
• Function put_ascii_morse: this function inserts a mapping from ascii to Morse code into the A2MLookupTable structure. This function is also internal to your module. It should be used by the create_lookup_table function below.
• Function create_lookup_table: this function takes the name of the file with the ascii-to-Morse mappings as argument, reads the file, creates the lookup table (on the heap), and returns a pointer to the new table. If any error occurs while opening or reading the file, the function should print an error message and return NULL. Your function, however, does NOT need to check that the content of the file was valid. Assume that if you are given a valid filename, it will contain the mapping for the 26 letters of the English alphabet. Nothing more and nothing less. We will make this assumption to simplify the assignment.
• Function destroy_lookup_table: reclaims the space associated with an A2MLookupTable structure given as argument. This function is already implemented for you.
• Function print_lookup_table: pretty prints the content of the lookup table in whatever form you want. It is there to help you debug your module. It is ok for this function to assume that if it is given a pointer that is not null, and that the given lookup table will contain mappings for letters from 'a' to 'z'.

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:

• Using the -Wall flag will make gcc print useful warnings that will help you debug more quickly.
• Using the -g flag will make gcc compile-in debugging information that you need to run gdb.

3. Complete the ascii-to-Morse conversion module

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

• get_morse: Given an ascii character and a pointer to the lookup table, returns a pointer to the corresponding string in Morse code. This function is internal to the module. It should be used by the ascii_to_Morse function.
• check_ascii_string: Tests if a null terminated string contains only valid characters. To check for valid characters, simply check that the character's ascii value is in the range [97,122] or that the character is a space.
• ascii_to_Morse: Converts an ascii string into a string in Morse code.

Hints:

• You may find the standard function strtok useful in splitting a string into words. Be careful! This function modifies the string that it tokenizes. Therefore, always make a copy of the string you want to parse and operate on the copy! Also note that this function is not safe against buffer overruns, so be sure that you pass in null-terminated strings. (The bounded version, strntok, is not yet standard).
• Use preprocessor directives to define constants, such as the characters or strings used as delimiters.

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:

• If the user does not provide a filename, prints an error message and exits. If there are any problems opening or reading the file, prints an error message and exits.
• Prompts the user for an English-language string (the string can be composed of multiple words).
• Reads the given string, translates it into Morse code, and prints the corresponding Morse code string. You can assume that the input lines are no more than 256 characters long, including any terminating nulls or newlines.
• Prompts the user for new strings to convert until the user chooses to exit the program.
• Your program should perform some simple error-checking: it should produce an error message if the file with the Morse code mappings does not exist, it should also produce an error if the user enters a special character for which there is no translation, etc. You are not required to recover from an error or even to print the translated message up to that point. You can simply print the error message and prompt the user for a new string.
• Your program should use the a2m_index module that you just developed.

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

Hints:

• To read a full line of input, try the function fgets instead of scanf.
• Be careful, though, because fgets will keep the newline character at the end of the string. You can easily get rid of it, though ... think about how.
  

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:

• create_lookup_tree: A function that takes the name of the file containing the ascii-to-Morse mappings, reads the file, creates the binary tree (on the heap), and returns a pointer to the new tree.
• destroy_lookup_tree: A function that frees the space associated with the lookup tree.
• get_ascii: Given a Morse code string and a pointer to the tree, returns the corresponding ascii character.
• put_morse_ascii: Given a Morse code string, an ascii character, and a pointer to the tree, inserts the ascii character at the appropriate location in the tree.
• print_lookup_tree: Prints the content of the tree. This method will serve for debugging purposes.
• check_morse_string: Verifies that the given null terminated string contains only dots, dashes, spaces, and slashes.
• morse_to_ascii: Converts a string in Morse code to a string in ascii.
• Feel free to write additional functions as you need.
• There should be NO main function in this file.

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:

• Searching Google for "binary tree" will give you a lot of information about this data structure. Here's a link to a useful reference that comes up among the top pages when performing this search: http://cslibrary.stanford.edu/110/BinaryTrees.html.
• If you are going to use strtok to break the string first into words and then into letters, note that strtok is NOT re-entrant. It uses static local variables to keep state. So be careful.

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:

• 1. Translate a string: this option gives the user access to the functionality that you implemented above.
• 2. View dictionary: displays the list of all known strings and their translations. The strings should be printed in lexicographical order. You do not need to check for duplicates. (use strncmp to sort the strings).
• 3. Remove a word: this option allows the user to delete a previously translated word from the dictionary. If there are multiple instances of the same word, you only need to delete the first instance in the linked list.
• 4. Exit the program

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.