Lab 13: Auto Complete Continued

Overview

This week you will implement a custom Trie data structure and use it to implement the AutoCompleter interface. The trie data structure is a tree where each node can have an arbitrary number of children.

Video introduction for the lab

Assignment

Details

Incorporate Instructor Feedback

Update your previous implementations based on feedback from your instructor.

ListMap class

You must implement a ListMap<K, V> class that implements the Map<K, V> interface. The class must have only one attribute, private final List<Map.Entry<K, V>> entries, that is assigned to a new ArrayList in a no-argument constructor.

All but the following methods may throw an UnsupportedOperationException: clear(), containsKey(Object key), get(Object key), entrySet(), isEmpty(), put(K key, V value), remove(Object key), and size().

Use the MapTest class in the repository to test your implementation of the ListMap class.

Trie Implementation

Implement the AutoCompleter interface using a trie data structure. A trie stores each string as a chain of characters.

The trie in the above figure contains the following strings: SHE, SELLS, SEA, SHELLS, and BY. Each letter in the string is an edge to a node. The T or F in each node indicates whether the node terminates a word in the trie. For example, T at the end of the right-most branch indicates that SHELLS is a word in the trie; however, the F in the parent's node indicates that SHELL is not in the trie.

Each node in the tree is a Trie object that must have at least the following two private attributes: boolean endsWord and Map<Character, Trie> edges. You must use objects from your ListMap class as the Maps in your trie.

To add BY to the trie, you first need to check to see if any word that begins with B is already in the trie. If so, there will already be a mapping from B to a trie one level down in the tree. If not, you'll need to add a mapping to edges that maps B to a new trie. You'll then need repeat the process for Y on the trie to which B maps. Since Y is the last letter in the word, you'll also need to ensure that endsWord for the trie to which Y maps is set to true. You may find it helpful to add a few words to a Trie on paper before you begin designing the code for the add() method.

Note: getBackingClass() should return [username].ListMap.

Testing

Update your JUnit test class for the AutoCompleter interface from lab 8 to test your Trie implementation of the AutoCompleter interface.

Graphical User Interface

Update your program from the previous week to include text fields shown the timing results for your Trie implementation.

Efficient Implementations

Your implementations should provide the best \( O() \) performance you can. You may want to analyze the asymptotic time complexity for your implementations. If you do, preserve your notes, since you will be required to provide this analysis in a future lab assignment.

Just For Fun

Ambitious students may wish to:

• Add allNonPrefixMatches(String substring) to the interface. This method returns all strings that contain the substring passed as an argument.

Acknowledgement

This laboratory assignment, developed by Dr. Chris Taylor.