Lab 8: Auto Complete

Overview

This is the first week of a multi-week project that will build on your lab 6 assignment. The project will allow you to integrate learning from throughout the freshman software development and data structures sequence. You will develop several data structures and analyze the advantages and disadvantages of each. The project will result in a user interface showing the results.

Video introduction for the lab

Assignment

Your program must have a user interface similar to the one shown here.

Auto Complete UI
Figure 1: Auto Complete UI

Users may type characters into search box. The list of matches below must be shown immediately after a letter is typed or deleted, however there must be at least three characters in the search box before the matching will run. If there are ever less than three characters in the search box, the program will display all the contents of the word list file. In addition, the time required to find an exact match and all matches with the same prefix should be displayed in appropriate text boxes for both the sorted list and unsorted list data structures.

There are several word list files available in the data folder of the repository. Your program should provide a mechanism for the user to specify the word list file to be used. This can be via a command line argument or a mechanism in the graphical user interface.

Details

Build on Lab 6

Begin by incorporating your instructor's feedback from lab 6 and build on that IntelliJ project.

Unordered List Implementation

Update your UnorderedList implementation from lab 6 to incorporate feedback from your instructor, if available. Use this implementation as one of the AutoCompleter interface implementations.

Ordered List Implementation

Implement the AutoCompleter interface using a ordered list. Your class, OrderedList, must have at least the following private attribute: private final List<String> items that is assigned via a one-argument constructor. You should ensure that the list does not contain duplicates and that all of the items are in order.

Your implementation of add() must use Collections.binarySearch() to find the position where the element to be added should be inserted such that the order of the list is maintained.

You must also make use of one call to Collections.binarySearch() in your implementations of exactMatch() and allMatches().

Binary Search Tree Implementation

Implement the AutoCompleter interface using a binary search tree. Your class, BinarySearchTree, must have only one private attribute: private final TreeSet<String> items. Note: getBackingClass() should return java.util.TreeSet.

Testing

Update your JUnit test class for the AutoCompleter interface from lab 6 to test your OrderedList and BinarySearchTree implementations of the AutoCompleter interface. You should not have to rewrite your tests, but merely change the type of AutoCompleter you are using. The results of the method calls should be identical.

Graphical User Interface

Update your program from the previous week to include text fields shown the timing results for your OrderedList and BinarySearchTree implementations.

Efficient Implementations

Your implementations should provide the best \( O() \) performance you can for matching. 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.

Exception Handling

If any problems are encountered with reading the input file with the word list, the program should display a useful error message to the console and terminate gracefully. If any other exceptions occur once the GUI has been displayed, the program should display a meaningful Alert and recover appropriately. The program should not crash or display any exceptions.

Just For Fun

Ambitious students may wish to:

Acknowledgement

This laboratory assignment, developed by Dr. Chris Taylor.

See your professor's instructions for details on submission guidelines and due dates.