Week 9 Lab: 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.

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.

In fact, once the tree is fully populated, all symbols in it can be decoded by visiting the left child when a dot is encountered and visiting the right child when a dash is encountered. When all of the dots/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 in 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 a space. For example, HI THERE would appear in an encoded file as: .... .. .-... - .... . .-. .. Your MorseDecoder class must read an encoded file and write the decoded result to an output file. Your program must make use of a MorseTree class to store the Morse Code in a binary tree.

The MorseTree class must define a private static nested Node class. Each Node will contain the instance variable symbol as a Character as well as its two child Nodes dot and dash. If the Node does not contain a symbol, then symbol should be null. The MorseTree will have a single instance variable, root.

The MorseTree class must have the following public methods:

• MorseTree() — constructor that initializes root to a new empty Node (a node with symbol == null)
• add(Character symbol, String code) — where symbol is the letter/digit/punctuation mark and code is the Morse Code associated with the symbol and inserts it into the tree. Keep in mind that this may involve adding multiple nodes to the tree. For example, if A is added to the tree first, the following nodes are added to the tree: An empty node (that is, a node no symbol) as the root node as well as an empty node that is the root node's left child. That node must have a right child that is a node whose symbol is set to A. This method should throw an IllegalArgumentException if the code passed to the method contains anything other than . or - or if a symbol already exists that uses the same code.
• decode(String code) — where code is the code for a symbol that is returned by the method (in an Optional<Character>). If a code is not found or the code is an empty String (i.e. just whitespace), the method should return an empty optional. This method should throw an IllegalArgumentException if the String passed to the method contains anything other than . or -. This method must make a call to a private recursive method that does most of the work. Note: This method will function correctly only if the tree has been correctly populated in advance.
• toString() — Use a preorder traversal (visit current node, then dot subtree, then dash subtree). For every node whose symbol is not null, append a line using:
  • the symbol formatted left-justified in width 4 ("%-4s")
  • then the code
  • then a newline (%n)
  • If the symbol is the newline character ('\n'), print it as the two-character string "\n".

The logic of your program should be implemented in the MorseDecoder utility class. The design for this class is your responsibility; however, you are required to have three methods:

• a private no-arg constructor to ensure the utility class will not be instantiated.
• loadDecoder(Path path) that accepts a Path object containing the Morse Code file as an argument. The method calls the add() from the MorseTree class multiple times in order to populate the tree. Each line of the file contains one codeword mapping. The first character is the symbol (e.g., D) immediately followed by the corresponding morse codeword (e.g., -..). The method will return a completed MorseTree object.
  • loadDecoder(Path path) must validate the dictionary file. If any line is invalid, it must throw IllegalArgumentException and stop loading. Invalid lines include (at minimum):
    • empty or whitespace-only lines
    • a symbol without a Morse code
    • a newline symbol (\n) without a Morse code
    • Morse codes containing characters other than . or -
• decodeMessage(File input, MorseTree tree) which decodes the contents of the file using the MorseTree. It will traverse one symbol at a time through the encoded file and translate the symbol into a character. The method will return a List<String> containing the decoded message in the first index, followed by any warning messages (see below) added in the order they were encountered. If the input file is empty, the returned list contains a single element: the empty decoded string.

Notes:

• decodeMessage processes whitespace-separated tokens. For each token:
  • If the token contains characters other than . or -, add a warning containing "invalid token" and the token.
  • If the token contains only . and - but is not found in the tree, add a warning containing "unknown code" and the token.
  • Otherwise append the decoded character to the decoded output.
• The returned List must contain:
  • the decoded message at index 0
  • then any warning messages in encounter order
  • If the input file is empty, the returned list contains a single element: the empty decoded string.
• Line breaks in the following file are included for clarity but should be treated as whitespace. Newlines should be added to the output file only when the .-.- codeword is encountered.

Interface

Your program should use a clean GUI that automatically loads the dictionary file of morse code and builds the MorseTree before showing the GUI to the user. This will mean using the Initializable interface and loading the tree in the initialize method. The user should have a way to bring up a FileChooser and select a file, at which point the program should decode the file and present it to the user below the original, encoded file. Below is an example interface:

Note that your program should be able to both load a new message and save the decoded text to a text file. At a minimum, you will need two TextArea controls, input and output to display the encoded and decoded messages, respectively.

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.

Additionally, if there were any illegal characters found during decoding, an alert listing all the characters skipped should pop up when the decoding is complete.

Acknowledgements

This assignment was originally developed by Dr. Jay Urbain.