Maps

Today, we will explore how to implement the Map interface found in

Setup

Create a new lab repository for this week using our template for Maven-based Java projects. You should use this template repository to create a new repository on your account, giving the repo an appropriate name for this week’s work, e.g., maps.

• https://github.com/Tools-for-Thinking-About-Programs/java-maven-template

Once you have created and locally cloned your repository, add the following files, taking care to ensure that you add them to folders consistent with their declared packages, edu.ttap.maps.

• AssociationList.java
• SubstitutionCipher.java

Part 1: Association Lists

As a warm-up, we’ll explore how to implement the java.util.Map interface using the association list structure described in the reading. Recall that an association list is simply a list of key-value pairs. While simplistic, association lists are go-to implementations of maps for when you need a quick and dirty map and one is not easily available.

Implement the stubs found in AssociationList.java. These include the following required interface methods:

• void clear()
• boolean containsKey(Object key)
• boolean containsValue(Object value)
• V get(Object key)
• boolean isEmpty()
• V put(K key, V value)
• Set<K> keySet()
• V remove(Object key)
• int size()
• Collection<V> values()

You do not need to implement the Map’s entrySet, putAll.

Here some implementation notes to guide your development:

• You can use a standard library list implementation, e.g., ArrayList<T>, as your backing data structure for your map.
• For keySet, you can create a java.util.HashSet<K, V>, populate it with the keys of your map, and return it. We’ll talk about what sets are very soon!
• For values, you can create any collection, e.g., an ArrayList<T>, to store the values.

Part 2: Substitution Ciphers

Now, you’ll employ your association list implementation for a simple task: encrypting and decryption messages using substitution ciphers. A substitution cipher is a general form of cipher where we have a known mapping between characters. Encyption amounts to following the mapping in the “left-to-right” direction; decryption follows the mapping in the “right-to-left” direction.

For example, consider the following substitution cipher:

'a' -> 'i'
'b' -> 'g'
'c' -> 'w'
'd' -> 'o'
'e' -> 'h'
'f' -> 'z'
'g' -> 'f'
'h' -> 'a'
'i' -> 'k'
'j' -> 'n'
'k' -> 't'
'l' -> 'm'
'm' -> 'r'
'n' -> 'v'
'o' -> 'c'
'p' -> 'b'
'q' -> 'j'
'r' -> 'e'
's' -> 'y'
't' -> 's'
'u' -> 'l'
'v' -> 'd'
'w' -> 'p'
'x' -> 'u'
'y' -> 'q'
'z' -> 'x'

For the text "hello world", encryption yields the ciphertext "ahmmc pcemo".

Implement this functionality by completing the functions found in SubstitutionCipher.java. SubstitionCipher expects three command-line arguments as input:

• encypt or decrypt denoting whether the program should encrypt or decrypt the text.
• <ciphertext> the path to the file containing the cipher
• <text> the path to the file containing the text to either encode or decode

Each file of ciphertext contains one of the mappings of the cipher in the form k v where k is the original letter and v is the letter that should be substituted. For example, here are the contents of the above cipher as a file for testing purposes:

• example-cipher.txt

Note that the plain text may have spaces in it! You should translate spaces as is rather than trying to encrypt/decrypt them.

Make sure that your SubstitionCipher program works on the following examples, all using example-cipher.txt:

• Encrypting some text from the Wikipedia article on substitution ciphers yields:

  kv i ylgyskslskcv wkbahe i elmh ky lyho sc waivfh hiwa mhsshe cz sah rhyyifh cvh is i skrh
  

• Decrypting some encrypted text from the same Wikipedia article yields:

  theruleistoreplaceorsubstituteeachletterwithanotherletterfromthealphabet 
  

• Round-tripping on the text helloworld: helloworld-example.txt

Make sure that your program works on all three examples before you move onto the next lab!