The learning goals of this lab are the following:
In this lab, you are asked to implement the ArraySet class. An object of this class represents a set of String objects. Strings can be added, removed, and there are methods for supporting set union, intersection, and difference.
Your implementation should be backed by an array (similar to how Java’s ArrayList is implemented).
What to do In general with this lab and others, you are expected to implement every method. Look for the methods that throw an implement me! exception. But you should also check the other methods because sometimes I provide a partial implementation with a comment for you to fill in more (e.g., see main).
Restrictions You are forbidden from using any of Java class that will do the work for you (e.g., LinkedList, ArrayList, HashSet, etc.). The spirit of the lab is to write a Set implementation more or less “from scratch.”
Teaming up You may work with a partner. Larger groups are not permitted.
Cardinality vs. capacity The cardinality of the set is the number of distinct elements in it. The capacity of the ArraySet is the size of the array used to store the elements. The capacity may be larger than the cardinality.
Resizing The capacity should always be at least 1. When the array is full (cardinality = capacity), the capacity should be doubled. When the array is 1/4 full (cardinality = capacity / 4), then the capacity should be cut in half. You may use the built-in method Arrays.copyOf if you wish.
Testing and Grading When you submit to Gradescope, you will see the results of only a few tests that check some basic functionality. When your assignment is graded, many more tests will be run to check your implementation for correctness. You are responsible for testing your own work before submitting it. Use the main method to test your implementation.
Make your implementation more efficient by storing elements according to their hash value. You can use linear probing to handle elements that have the same hash value. (Note: be careful with removal! You will need to create an object that can serve as a tombstone.)
Before attempting the milestone, I suggest you first complete the assignment as is, upload it, and then revise your implementation for the challenge problem. That way, if you get stuck on the challenge problem, you can always go back to earlier version.