HERE ARE THE SUPPLIED CLASSES

//TrieMap.java

//Note: All of your TrieMapInterface method implementations must function recursively //I have left the method signatures from my own solution, which may be useful hints in how to approach the problem //You are free to change/remove/etc. any of the methods, as long as your class still supports the TrieMapInterface import java.util.ArrayList; public class TrieMap implements TrieMapInterface{ TrieMapNode root; public TrieMap(){ } //Indirectly recursive method to meet definition of interface public void put(String key, String value){ } //Recursive method public void put(TrieMapNode current, String curKey, String value){ } //Indirectly recursive method to meet definition of interface public String get(String key){ return ""; } //Recursive method public String get(TrieMapNode current, String curKey){ return ""; } //Indirectly recursive method to meet definition of interface public boolean containsKey(String key){ return false; } //Recursive method public boolean containsKey(TrieMapNode current, String curKey){ return false; } //Indirectly recursive method to meet definition of interface public ArrayList getValuesForPrefix(String prefix){ return new ArrayList(); } //Recursive helper function to find node that matches a prefix public TrieMapNode findNode(TrieMapNode current, String curKey){ return null; } //Recursive helper function to get all keys in a node's subtree public ArrayList getKeys(TrieMapNode current){ return new ArrayList(); } //Indirectly recursive method to meet definition of interface public void print(){ } //Recursive method to print values in tree public void print(TrieMapNode current){ } public static void main(String[] args){ //You can add some code in here to test out your TrieMap initially //The TrieMapTester includes a more detailed test } }

//===============================================================

//TrieMapInterface.java

import java.util.ArrayList; public interface TrieMapInterface{ //Adds the key/value pair to the TrieMap public void put(String key, String value); //Returns the object value associated with the given key //If the key is not present in the TrieMap, returns null public String get(String key); //Returns true if key is in the TrieMap, false otherwise public boolean containsKey(String key); //Returns an ArrayList of objects containing all keys that start with prefix public ArrayList getValuesForPrefix(String prefix); //Prints all values stored inside the TrieMap public void print(); }

//=========================================================

//TrieMapNode.java

import java.util.HashMap; public class TrieMapNode{ //Keys are characters //Values are other TrieMapNodes //This way, you can use the next character in a String to determine the next node //This allows you to progress deeper into the tree private HashMap children; private String value; public TrieMapNode(){ children = new HashMap(); value = null; } public String getValue(){ return value; } public void setValue(String newVal){ value = newVal; } public HashMap getChildren(){ return children; } }

A trie, also known as a prefix tree, is a tree-based data structure that stores key/value pairs (like a HashMap). The keys in tries are usually strings. In this assignment, you will implement a trie data structure that uses recursion to store string keys and their associated string values. The root node in the trie will be empty (no key or value). Each node in the trie, including the root, will store a hash map with character keys and trie node values. This structure will allow you to search for a string key in the trie by repeatedly looking up the node associated with the next character in the key (if it exists). As an example, consider the picture below (ignore the red for now). This trie contains the keys/values "A", "ATE", "ARE", "BE", "SIT", and "SO" (assume the key and value are the same, null values indicate nothing has been added there) 0 SO If you were to look up the key "ATE" in the trie, you would end up following the red node path. Starting at the root node, look up and go to the node associated with 'A'. From that node, look up and go to the node associated with 'T', and then look up and go to the node associated with 'E'. If the value stored in this final node is null, the key does not exist in the trie. If the value is not-null, the node's value represents the value associated with the given key (alternatively, if you are performing a put operation, you can add the value to the node). If you were to look up the key "BAT", you would start at the root node, look up and go to the node associated with 'B', and then determine that they key "BAT" is not in the trie since 'A' is not associated with the current node (i.e., is not in that node's hashmap). If the additional keys "AT", "BE", and SOD" were added, the trie would then look like null null 0 null An interesting property of the trie structure is that the key for any node contained within a subtree rooted at a node Xhas the key that would lead to X as a prefix. As examples, "SIT", "SO", and "SOD" all begin with the character 'S' and are all contained within the sub-trie rooted at the node you would reach if you looked up the key 'S'. If "SOME", "SODA", and "SOAR" were added to the above trie, they would all be contained in the subtrees of the key "S" and the key "SO". This allows tries to easily produce a set of keys that begin with a particular prefix To start the assignment, download the Assignment 5 - Base Code.zip file from cuLearn. This zip contains 4 Java files 1. TrieMaplnterface: This interface defines the methods that your TrieMap class must support These methods should work similarly to how they would for a hash map or any other map data structure. The put method should add the associated key/value pair to the trie. If the key is already in the trie, the value should be updated. The get method should return the value associated with the given key, if the key exists. If the key does not exist in the trie, the get method should return null. The containsKey method should return true if the trie contains the given key and false otherwise. The getValuesForPrefix method must return an ArrayList of String values that contains all keys within the trie that start with the specified prefix. The print method should print all of the values contained within the trie 2. TrieMap: This class contains skeleton code outlining the methods required to implement the TrieMaplnterface. I have also left method signatures from my own solution, which may provide hints regarding possible solutions. You can remove or otherwise change the class however you wish, so long as your class still implements the TrieMaplnterface. All method implementations must function recursively. This is the only class that you must add code to in order to complete the assignment. You are free to add code to the other classes if you wish. 3. TrieMapNode: The class representing a node in the trie. It contains a hashmap with character keys and TrieMapNode values (similar to a binary tree but with more than left/right children), along with a constructor and necessary get/set methods. You don't need to change this class but can make changes if you want 4. TrieMapTester: This class will run several tests on your TrieMap implementation and count the number of errors. This will run a significant number of operations, so it is probably a good idea to un your own smaller tests first to verify your TrieMap implementation is likely correct. The implementation of the TrieMap class may seem difficult initially. However, after becoming familiar with recursively moving through the trie structure, you will find that most methods are quite similar. So completing the first few methods is likely to be significantly more difficult than completing the others. Personally, I would recommend implementing and testing the methods in this order: constructor, put, print containsKey, get, getValuesForPrefix. A trie, also known as a prefix tree, is a tree-based data structure that stores key/value pairs (like a HashMap). The keys in tries are usually strings. In this assignment, you will implement a trie data structure that uses recursion to store string keys and their associated string values. The root node in the trie will be empty (no key or value). Each node in the trie, including the root, will store a hash map with character keys and trie node values. This structure will allow you to search for a string key in the trie by repeatedly looking up the node associated with the next character in the key (if it exists). As an example, consider the picture below (ignore the red for now). This trie contains the keys/values "A", "ATE", "ARE", "BE", "SIT", and "SO" (assume the key and value are the same, null values indicate nothing has been added there) 0 SO If you were to look up the key "ATE" in the trie, you would end up following the red node path. Starting at the root node, look up and go to the node associated with 'A'. From that node, look up and go to the node associated with 'T', and then look up and go to the node associated with 'E'. If the value stored in this final node is null, the key does not exist in the trie. If the value is not-null, the node's value represents the value associated with the given key (alternatively, if you are performing a put operation, you can add the value to the node). If you were to look up the key "BAT", you would start at the root node, look up and go to the node associated with 'B', and then determine that they key "BAT" is not in the trie since 'A' is not associated with the current node (i.e., is not in that node's hashmap). If the additional keys "AT", "BE", and SOD" were added, the trie would then look like null null 0 null An interesting property of the trie structure is that the key for any node contained within a subtree rooted at a node Xhas the key that would lead to X as a prefix. As examples, "SIT", "SO", and "SOD" all begin with the character 'S' and are all contained within the sub-trie rooted at the node you would reach if you looked up the key 'S'. If "SOME", "SODA", and "SOAR" were added to the above trie, they would all be contained in the subtrees of the key "S" and the key "SO". This allows tries to easily produce a set of keys that begin with a particular prefix To start the assignment, download the Assignment 5 - Base Code.zip file from cuLearn. This zip contains 4 Java files 1. TrieMaplnterface: This interface defines the methods that your TrieMap class must support These methods should work similarly to how they would for a hash map or any other map data structure. The put method should add the associated key/value pair to the trie. If the key is already in the trie, the value should be updated. The get method should return the value associated with the given key, if the key exists. If the key does not exist in the trie, the get method should return null. The containsKey method should return true if the trie contains the given key and false otherwise. The getValuesForPrefix method must return an ArrayList of String values that contains all keys within the trie that start with the specified prefix. The print method should print all of the values contained within the trie 2. TrieMap: This class contains skeleton code outlining the methods required to implement the TrieMaplnterface. I have also left method signatures from my own solution, which may provide hints regarding possible solutions. You can remove or otherwise change the class however you wish, so long as your class still implements the TrieMaplnterface. All method implementations must function recursively. This is the only class that you must add code to in order to complete the assignment. You are free to add code to the other classes if you wish. 3. TrieMapNode: The class representing a node in the trie. It contains a hashmap with character keys and TrieMapNode values (similar to a binary tree but with more than left/right children), along with a constructor and necessary get/set methods. You don't need to change this class but can make changes if you want 4. TrieMapTester: This class will run several tests on your TrieMap implementation and count the number of errors. This will run a significant number of operations, so it is probably a good idea to un your own smaller tests first to verify your TrieMap implementation is likely correct. The implementation of the TrieMap class may seem difficult initially. However, after becoming familiar with recursively moving through the trie structure, you will find that most methods are quite similar. So completing the first few methods is likely to be significantly more difficult than completing the others. Personally, I would recommend implementing and testing the methods in this order: constructor, put, print containsKey, get, getValuesForPrefix