CSE 303, Autumn 2007, Assignment 4

Due: Wednesday, November 14, 2007 at Noon

Turnin link here

Assignment goals

In this assignment, you will develop a larger software system composed of multiple files and even multiple executable programs. By doing so, you will:

This assignment is extensive enough that we suggest you work with a partner. You and your partner should turn in only one copy of the solution. Please be sure that both of your names appear inside each of the files that you turn in.

Please get started early. Even if you are working with a partner, there is enough to do that you will be in trouble if you wait to begin until the weekend before this assignment is due.

Background Reading

In addition to the lecture notes, you may find "Programming in C" a useful reference for completing this assignment. We also encourage you to use the Web to find additional examples and documentation.

As you work on this assignment, you may find it helpful to examine the list.c sample code from Lecture 11. It gives an example of one way to build a simple linked list. You should not feel obligated to use this code directly or even base your code on it, but it may be a helpful source of ideas.

Getting ready

Download the file: hw4.tar.gz. and extract all the files for this assignment using the command

> tar zxvf hw4.tar.gz

You should now see a directory called hw4. If you see it, you are ready to start the assignment. If this procedure did not work for you, please contact us or talk to one of your colleagues.

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

translated into morse code is:

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

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.

General advice for software development

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 will finish because you will spend less time debugging. Experienced software developers 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, we would like you to create a module 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 dimmensional 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.

Hints:

2. Test 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.

Use this program to test the code you have written above. Feel free to modify this file to add more tests. Problem 4 asks you to create the proper Makefile. At this point, 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 two additional functions. Please complete the implementation of this module by implementing these remaining functions.

Hints:

4. Complete your test file

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 target clean, make a backup of all your files. It is easy to make a mistake that will cause make clean to delete all your code!

6. Interactive ascii-to-morse converter

You are now ready to write an 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.

Hint:

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 hashtable, 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 should 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:

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:

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.

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

You can assume that the user will never enter more than 256 characters.

10. Dictionary module

We would like you to 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.

Turn-in instructions

You should work on this assignment in a group of two. Each group should turn-in only one copy of the solution. Please make sure to write both names inside each file that you hand in.

For this assignment, you should turn in the following files: a2m_index.h, a2m_index.c, test_a2m_index.c, m2a_index.h, m2a_index.c, test_m2a_index.c, dict.h, dict.c, a2m.c, m2a.c, Makefile, and any other source or header files you implemented to complete the assignment.

Specific turnin instructions will be given later.