Week 8 Lab: 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.
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.
You need to have a way to switch between ArrayList and LinkedList backing structures for the
UnorderedList and Orderedlist implementations. How you implement the functionality in the GUI is
up to you, however they must be independent of each other (you can have one use an ArrayList while the
other uses a LinkedList) and the List must be completely loaded and ready to use after switching
between backing structures.
There are several word list files available in the data folder of the repository.
Your program should provide some GUI mechanism for the user to specify the word list file
to be used.
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 in the same way the OrderedList does.
You should ensure that the list does not contain duplicates, converts to lowercase and that
all 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. Again, there should be a one-argument constructor that takes
a java.util.List of Strings and adds them to the tree.
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. In other words, instantiate the implementation as
an AutoCompleter object using polymorphism and run all the tests on an AutoCompleter, not an
UnorderedList, OrderedList, etc.
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 in an Alert 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:
- 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.