Question SOLVED: Using an instance of an ArrayList Create an integer set data structure
You will be using an instance of an ArrayList to create an integer set data structure. A set is a collection of unique values. In this case, our set will hold only integers, and we will also add the additional property that our set will be sorted (mathematical sets are unordered and two sets are equivalent if they contain the same elements, regardless of order).
You should implement the IntSet class according to the following UML diagram. Be sure to include a small comment for at least each non-trivial method.
- The default (no-argument) constructor should initialize an empty set.
- The copy constructor should initialize the set to be a clone of other. This is useful for creating a duplicate of a set (so the copy can be modified independently from the original). You must ensure that both constructors initialize elements to something, otherwise it remains null and will surely cause a problem elsewhere in your problem.
- The equals method should return true if the element lists have identical contents.
- The toString method should return a string representation of the set (see sample output for a concrete format).
- The size method should return the number of elements in the set.
- The isEmpty method should return true if the set contains no elements.
- The contains method should return true if element is in the set and false otherwise. All three methods can be implemented easily by calling a method on elements with the appropriate arguments (these methods should not require much logic).
- The add method should attempt to add an element to the set. If the element is present in the set, it should return false and make no changes. If the element is absent from the set, then it should add the element to elements and return true. You have an additional requirement: elements must remain sorted after this method returns. The easiest way to do this is to ensure that when you insert a new element you insert it in the correct spot. Use the add(i, value) method on elements to insert value into index i. This method will slide all the elements to the right down by one so that no elements are overwritten. It’s your task to find the correct value of i (which must satisfy 0 ≤ i < elements.size()).
- The remove method should attempt to remove an element from the set. If the element is present, remove it and return true. Otherwise, do nothing and return false.
- The clear method should remove all elements from the set. These meth- ods should also be quite easy to implement.
- The union, difference, and intersection methods should return a new instance of IntSet. Neither this nor other should be modified when these methods are called. The union of two sets contains all the elements of either set. The difference of one set from another is all of the elements of the first set with the elements of the second set removed (if present in the first set). The intersection of two sets contains only the elements in both sets. Remember that if you insert into a set directly you must ensure that it remains sorted. Notice that union and intersection is symmetric while difference is not (hence two different difference outputs).
Notice that we are dealing with Integer objects and not primitive ints. This means that you cannot compare two objects with == (unfortunately, this op- erator happens to work for some small integer values, but not all). You must use the equals method.
The program should mimic the sample run using the provided driver.
Enter items:5 3 2 4 1
Enter items:5 4 7 6 3
Set1 = [1, 2, 3, 4, 5]
Set2 = [3, 4, 5, 6, 7]
Union = [1, 2, 3, 4, 5, 6, 7]
Intersection = [3, 4, 5]
Set1 – Set2 = [1, 2]
Set2 – Set1 = [6, 7]