Lab 9: Morse Code Decoder

Learning Outcomes

• Implement a binary tree
• Recursively traverse a tree

Overview

Morse Code is a method for communicating using two symbols: dots and dashes. Each character has a code, consisting of zero or more dots and zero or more dashes. The following table describes the mapping for many popular characters:

In this assignment, you will create a Morse Code decoder. You will write and test two main classes: MorseDecoder and MorseTree.

In order to decode each series of dots and dashes, you must build a binary tree. A partially constructed tree is shown below. The tree contains the letters A to E in the alphabet.

Notice that the resulting binary tree provides a decoding path. For example, the letter D can be decoded from its Morse Code: -... To accomplish this, we start at the root of the tree and traverse to the left or right depending on whether the code begins with a dot or a dash, respectively. In this case, -.. begins with a dash followed by two dots, so we would traverse from the root of the tree once to the right and then twice to the left. Doing so causes us to arrive at a node in the tree with the value D.

Once the tree is fully populated, all symbols in it can be decoded by visiting the dot child when a dot is encountered and visiting the dash child when a dash is encountered. When all of the dots and dashes in the code have been processed, the resulting node in the tree contains the symbol represented by the code.

Procedure

Your program must read a file consisting of characters that have been encoded in Morse Code. In the encoded file, each character is translated into its Morse code. Each code is separated by whitespace. For example, HI THERE would appear in an encoded file as: .... .. .-... - .... . .-. ..

Your program must make use of a MorseTree to store the Morse Code decoding tree.

MorseTree Class

The MorseTree class stores Character values. It is not generic.

The class must define a private static nested class named Node. Each Node contains the following private instance variables:

private Character symbol;
private Node dot;
private Node dash;

A node may exist without storing a symbol. In that case, symbol is null.

The MorseTree class has one instance variable:

private final Node root;

The root itself is always a Node. A newly constructed tree contains an empty root node whose symbol, dot, and dash values are all null.

The MorseTree class must have the following public methods:

• MorseTree() — constructs an empty tree containing only the empty root node.

• add(Character symbol, String code) — inserts symbol at the location represented by code.

  • A dot (.) moves to the dot child.
  • A dash (-) moves to the dash child.
  • Create intermediate nodes as needed while following the path.
  • Throw an IllegalArgumentException if code contains any character other than . or -.
  • If the final node already contains a symbol, throw an IllegalArgumentException. Existing mappings must not be overwritten.

  For example, if A with code .- is the first symbol added to the tree, the root node already exists. An empty dot child is created, followed by a dash child whose symbol is set to A.

• decode(String code) — follows the path described by code and returns the symbol at the resulting node in an Optional<Character>.

  • Return Optional.empty() if the path does not exist or the final node contains no symbol.
  • Throw an IllegalArgumentException if code contains anything other than . or -.
  • The public method must call a private recursive helper method that performs most of the traversal.

• toString() — returns all symbol/code mappings using a preorder traversal.

  • Use a private recursive helper method.
  • Do not include nodes whose symbol is null.
  • For each stored symbol, use a left-justified width of 4, then append its Morse code, followed by a newline.
  • If the stored symbol is the newline character, display it as the two characters \n rather than inserting an actual newline in the symbol field.

For example, part of the output might resemble:

E   .
A   .-
T   -
N   -.

MorseDecoder Utility Class

The logic for loading the Morse dictionary and decoding a message should be implemented in the MorseDecoder utility class.

MorseDecoder must provide the following public static methods.

loadDecoder(Path path)

public static MorseTree loadDecoder(Path path)

This method loads a Morse Code dictionary file and returns a populated MorseTree.

Each line of the dictionary contains one mapping. Normally the first character is the symbol and the remainder of the line is its Morse code. For example:

D-..

represents the symbol D with the code -...

The newline character is a special case because it requires two characters to represent the symbol in the dictionary:

\n.-.-

When a dictionary line begins with \n, interpret the symbol as the newline character and begin reading the Morse code after those two characters.

Malformed dictionary entries must cause loadDecoder() to throw an IllegalArgumentException. This includes:

• an empty line;
• a symbol with no Morse code;
• a \n entry with no Morse code;
• a Morse code containing anything other than . or -;
• a duplicate Morse code mapping.

decodeMessage(File input, MorseTree tree)

public static List<String> decodeMessage(File input, MorseTree tree)

This method reads Morse code tokens from input, decodes them using tree, and returns both the decoded message and any warnings that were generated.

The returned list must use the following structure:

index 0   decoded message
index 1+  warning messages, one for each skipped token

For completely valid input, the returned list contains exactly one element: the decoded message.

Each encoded symbol is separated by whitespace. Whitespace in the input file, including spaces, tabs, and line breaks, is treated only as a separator. A newline should appear in the decoded message only when the Morse code .-.- is encountered and decoded as the newline character.

If a token is a valid sequence of dots and dashes but is not present in the tree, skip it and add a warning.

If a token contains any character other than . or -, skip it and add a warning.

After a bad token is encountered, decoding must continue with the remaining input.

MorseDecoderDriver

Create a MorseDecoderDriver class that extends Application.

It must:

• provide a public static void main(String[] args) method that launches the application;
• override public void start(Stage stage);
• load morsedecoder.fxml;
• create and display the scene;
• use Morse Code Decoder as the application title.

Interface

Your program should use a clean GUI that automatically loads the Morse Code dictionary and builds the MorseTree when the application starts.

The GUI should match the provided example as closely as reasonably possible, including the overall layout, menus, and two large text areas. Minor platform-specific differences in fonts, spacing, and native control appearance are acceptable.

When a user loads an encoded file, the program should display the original encoded text in the upper text area, decode the file, and display the decoded message in the lower text area.

MorseController

Your MorseController class must implement the Initializable interface and provide at minimum the following functionality:

• public void initialize(URL url, ResourceBundle resourceBundle) — loads the Morse Code dictionary once the GUI has been loaded.

• void open() — asks the user to select an encoded text file, displays the original message, decodes it, and displays the decoded message.

• void save() — asks the user for a filename and saves the decoded message.

• void quit() — exits the program.

• void clear() — clears both the encoded input and decoded output text.

• void about() — displays a dialog containing instructions for using the program.

There will be three menus in the GUI: File, Edit, and Help.

File contains:

• Open
• Save
• Quit

Edit contains:

• Clear

Help contains:

• About

If the dictionary cannot be loaded, or another recoverable file error occurs after the GUI is displayed, show a meaningful error Alert.

If one or more invalid or unknown Morse tokens are encountered while decoding, skip those tokens, continue decoding, and display one warning Alert after decoding completes that lists all skipped tokens.

Example

Running your program on this file:

.- .-... ... .--. .- -.-. . .-... ... .... --- ..- .-.. -.. .-... -... . .-... .--. .-.. .- -.-. . -.. .-... -... . - .-- . . -. .-... . .- -.-. .... .-... . -. -.-. --- -.. . -.. .-... -.-. .... .- .-. .- -.-. - . .-. .-.-.- .-.-
.-.-
.- .-... * .-... ... .... --- ..- .-.. -.. .-... -... . .-... .--. .-.. .- -.-. . -.. .-... -... . - .-- . . -. .-... . .- -.-. .... .-... .-- --- .-. -.. .-.-.- .-.-
.-.-
.-.. .. -. . .-... -... .-. . .- -.- ... .-... .. -. .-... - .... . .-... .. -. .--. ..- - .-... ..-. .. .-.. . .-... ... .... --- ..- .-.. -.. .-... -... . .-... .-. . .--. .-.. .. -.-. .- - . -.. .-... .. -. .-... - .... . .-... . -. -.-. --- -.. . -.. .-... ..-. .. .-.. . .-.-.-  .-.-

should display this decoded message:

A SPACE SHOULD BE PLACED BETWEEN EACH ENCODED CHARACTER.

A  SHOULD BE PLACED BETWEEN EACH WORD.

LINE BREAKS IN THE INPUT FILE SHOULD BE REPLICATED IN THE ENCODED FILE.

The * in the example input is invalid and should be skipped. After decoding is complete, the warning dialog should include that skipped token.

Acknowledgements

This assignment was originally developed by Dr. Jay Urbain.