Using Java

For this homework, you will be creating a class named ArraySet which is an implementation of the Set abstract data type. A Set is similar to a Bag (which we discussed in class), with the main difference being that duplicate entries are not added to a Set. For example, suppose the variable mySet references an ArraySet object:

mySet.add(5); mySet.add(10); mySet.add(5); // mySet already contains 5, so 5 is not added

After the previous three lines of code execute, mySet contains the following: (5, 10)

For this exam, you may use any code you want from ArrayBag as a starting point. A few things to note:

Unlike ArrayBag, ArraySet does not need to implement an interface.

ArraySet should be a generic class (i.e., the client should be able to create an ArraySet to hold any type of data).

ArraySet's internal array does not need to resize. If the user tries to add an item to a full Set, you can simply return false from the add method.

The major difference in ArraySet is that its add method should not add a new item to the internal array if it already exists in the internal array.

The other methods you should copy from ArrayBag are toString, remove, clear, contains, and the constructors. These should not need to be changed much, if at all.

After finishing the above steps, add the following two methods to ArraySet:

intersection. The intersection of two sets creates a new set containing all the elements that exist in both sets. For example, if Set1 contains (1, 3, 5) and Set2 contains (1, 5, 9), the intersection of Set1 and Set2 is (1, 5). Your intersection method should take a second ArraySet as an argument. This method should create a new ArraySet object, fill it with the required elements, and return it. The method header should look like this:

public ArraySet intersection(ArraySet otherSet)

union. The union of two sets creates a new set containing all elements in the first set and all elements in the second set. For example, if Set1 contains (1, 3, 5) and Set2 contains (1, 5, 9), the union of Set1 and Set2 is (1, 3, 5, 9). Recall that sets do not include duplicate entries, so the union does not include 1 twice or 5 twice. Your union method should take a second ArraySet as an argument. This method should create a new ArraySet object, fill it with the required elements, and return it. The method header should look like this:

public ArraySet union(ArraySet otherSet)

After you have finished your ArraySet class, you may use the following code in your program's Main method to test it. After running this code, your output should be:

( 5 10 12 ) ( 5 7 10 19 ) ( 5 10 ) ( 5 10 12 7 19 )

ArraySet set = new ArraySet<>(); set.add(5); set.add(10); set.add(5); set.add(12); set.add(12); System.out.println(set); ArraySet set2 = new ArraySet<>(); set2.add(5); set2.add(7); set2.add(10); set2.add(19); System.out.println(set2); System.out.println(set.intersection(set2)); System.out.println(set.union(set2));

PreviousNext

....................................................................................................

ArrayBag Class:

public class ArrayBag implements BagInterface { private T[] bag; private int numEntries; private static final int DEFAULT_CAPACITY = 25; private static final int MAXIMUM_CAPACITY = 1000; public ArrayBag() { this(DEFAULT_CAPACITY); } public ArrayBag(int capacity) { if (capacity > MAXIMUM_CAPACITY) { throw new IllegalArgumentException("Capacity is larger than 1000: " + capacity); } @SuppressWarnings("unchecked") T[] temp = (T[]) new Object[capacity]; bag = temp; numEntries = 0; } @Override public int getCurrentSize() { return numEntries; } @Override public boolean isEmpty() { return numEntries == 0; } @Override public boolean add(T item) { if (isArrayFull()) { return false; } // If array is not full, add the item bag[numEntries] = item; numEntries++; return true; } @Override public T remove() { // Remove an arbitrary item from the array if (isEmpty()) throw new IllegalStateException("Bag is empty, cannot remove"); T returnVal = bag[numEntries - 1]; bag[numEntries - 1] = null; numEntries--; return returnVal; } @Override public boolean remove(T item) { for (int i = 0; i < numEntries; i++) { if (bag[i].equals(item)) { // Remove item at index i, replacing with final item bag[i] = remove(); return true; } } return false; } @Override public void clear() { while (!isEmpty()) remove(); } @Override public int getFrequencyOf(T item) { int numOccurrences = 0; for (int i = 0; i < numEntries; i++) { if(bag[i].equals(item)) { numOccurrences++; } } return numOccurrences; } @Override public boolean contains(T item) { for (int i = 0; i < numEntries; i++) { if (bag[i].equals(item)) return true; } return false; } @Override public T[] toArray() { // Create a new array and return @SuppressWarnings("unchecked") T[] result = (T[]) new Object[numEntries]; for (int i = 0; i < numEntries; i++) { result[i] = bag[i]; } return result; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("( "); for (int i = 0; i < numEntries; i++) { sb.append(bag[i]).append(" "); } sb.append(" )"); return sb.toString(); } private boolean isArrayFull() { return numEntries >= bag.length; } }