Data Structures

BrailleTranslator.java

• DO NOT add new import statements.
• DO NOT change any of the method’s signatures.

Methods to be implemented by you:

createSymbolTree (provided)

This method reads symbols from an input file and calls the following two methods to create a Symbol object and insert it into the tree rooted at treeRoot.

You are given input files containing different characters as well as their Braille encodings. They are formatted as follows:

• One line specifying the number of characters, n
• n lines with a character and its corresponding Braille encoding, space-separated

Do not update this method, it has been implemented for you. IMPLEMENT the first two methods (readSingleEncoding and addCharacter).

1. readSingleEncoding

This method does not take in any parameters. It reads ONE character and returns a symbol containing the character and encoding.
You can do the following to read one character:

• Call StdIn.readChar() to read the character. You must use StdIn.readChar().
• Call StdIn.readString() to read the encoding.
• Call StdIn.readLine() to read the newline character \n.

Return a Symbol object containing the character AND encoding. This will be added as a leaf node in the next method.

Test this using createSymbolTree AFTER you have implemented the next method. Use the debugger in VS Code to verify that symbols are being read and created correctly on each iteration of this method

EARLY SUBMISSION CONSISTS OF THIS METHOD AND addCharacter. Make sure you submit BOTH methods for early submission; we will not make exceptions if you only implement this method.

2. addCharacter

This method inserts a symbol into the tree rooted at treeRoot. Given the encoding from the symbol object, trace the encoding path (L = left, R = right), starting with an empty root. The Symbol object is the leaf, but you’ll need to insert its partial encodings as well. 

First, use .getEncoding() on the symbol in parameters to get the encoding you’ll need. You’ll insert its partial encodings as well as the leaf (character node) itself. Here’s how (you should also refer to the note below):

1. ONLY leaf nodes have Symbol objects with characters. Initialize intermediate nodes with Character.MIN_VALUE characters and the partial encodings — the constructors below will handle the expected logic.
2. Create intermediate nodes along the encoding path if nodes do not exist; do not put any characters in them. USE the (String encoding) constructor for symbols: new Symbol(partialEncoding). You should keep track of a partial encoding – the root has an empty string, and its left or right children would have either “L” or “R” as encodings.
   1. Note that in the example below, the next character is appended to the previous “partial” encoding. For instance, if the current node is “RL” and an L is the next character, the resulting string is “RLLL”. 
3. The last digit of the encoding represents the position (left or right) of the character with respect to its parent. Characters are at level 6 on the tree (starting from level 0, the empty root). Use the new Symbol(character, encoding) constructor for leaves.

• The tree is made of TreeNodes, but note that this is NOT a binary search tree (BST).
• A TreeNode contains a Symbol object
  • The TreeNode’s Symbol at the root has the empty String for encoding.
  • The TreeNode’s Symbol at the leaf level contains a character and an encoding. This represents a lowercase letter.
    • Use new Symbol(character, fullEncoding) to initialize a leaf symbol at this level.
    • The TreeNode’s Symbol at other levels (the intermediate nodes) contain a character with Character.MIN_VALUE and the partial encoding. Each encoding for non-leaves has the path we took.
  • • Use new Symbol(partialEncoding) to initialize a symbol at these levels.

To test this method, use the provided createSymbolTree method.

Early submission. Implement the first two methods for extra credit: readSingleEncoding() and addCharacter(). We will not make exceptions if you only implement one method.

+--- ""
     |+R- R 
     |    |+R- RR 
     |    |    |+R- null
     |    |    --L- RRL 
     |    |         |+R- RRLR 
     |    |         |    |+R- null
     |    |         |    --L- RRLRL 
     |    |         |         |+R- null
     |    |         |         --L- d -> RRLRLL
     |    |         --L- RRLL 
     |    |              |+R- null
     |    |              --L- RRLLL 
     |    |                   |+R- null
     |    |                   --L- c -> RRLLLL
     |    --L- RL 
     |         |+R- RLR 
     |         |    |+R- null
     |         |    --L- RLRL 
     |         |         |+R- null
     |         |         --L- RLRLL 
     |         |              |+R- null
     |         |              --L- b -> RLRLLL
     |         --L- RLL 
     |              |+R- RLLR 
     |              |    |+R- RLLRR 
     |              |    |    |+R- null
     |              |    |    --L- o -> RLLRRL
     |              |    --L- null
     |              --L- RLLL 
     |                   |+R- null
     |                   --L- RLLLL 
     |                        |+R- null
     |                        --L- a -> RLLLLL
     --L- L 
          |+R- LR 
          |    |+R- LRR 
          |    |    |+R- LRRR 
          |    |    |    |+R- LRRRR 
          |    |    |    |    |+R- null
          |    |    |    |    --L- t -> LRRRRL
          |    |    |    --L- null
          |    |    --L- LRRL 
          |    |         |+R- LRRLR 
          |    |         |    |+R- null
          |    |         |    --L- s -> LRRLRL
          |    |         --L- null
          |    --L- null
          --L- null