Using Java

You will be designing a second class that implements BagInterface named ResizableArrayBag. In this class, the internal 'bag' array is resized whenever the array becomes full. Since an array cannot actually be resized, we need to create a new one and copy everything over from the original. However, this can become inefficient, so we do not want to continually resize the array. Therefore, whenever the array is filled, your code should double the size of the internal array. This will prevent the array from being resized too frequently.

Add BagInterface and ArrayBag (posted below) to your project. Then, add ResizableArrayBag (make sure it implements BagInterface) and Main. In your client code, show the creation of a small ResizableArrayBag and add enough items to it so that it correctly grows in size. You only have to submit ResizableArrayBag and Main.

Extra Credit (worth 10 points toward your homework grade): If the client creates a ResizableArrayBag and then adds a large amount of items to it and then removes most of those items, a lot of memory is being wasted. For example, if there are 100 indexes in a ResizableArrayBag and only two items, we are wasting 98 memory locations. To fix this, we can make our internal array "shrink" whenever it gets too empty. One way to determine when to do this is to cut the size of the array in half whenever it is less than 1/3 full.

BagInterface

public interface BagInterface { /** * Returns the number of entries in the bag * @return The integer number of entries currently in the bag */ int getCurrentSize(); /** * Determines whether or not the bag is empty * @return True if the Bag is empty, false otherwise */ boolean isEmpty(); /** * Add a given item to the Bag * @param item Item to add to the Bag * @return True if the addition is successful, false otherwise */ boolean add(T item); /** * Removes an arbitrary item from the Bag * @return The removed item */ T remove(); /** * Removes a given item from the Bag * @param item Item to remove from the Bag * @return True if the removal was successful, false otherwise */ boolean remove(T item); /** * Removes all items from the bag */ void clear(); /** * Counts the number of times a given entry appears in this bag. * @param item: The entry to be counted * @return The number of times item appears in the bag. */ int getFrequencyOf(T item); /** * Tests whether this bag contains a given entry. * @param item: The entry to locate * @return True if the bag contains item, false otherwise */ boolean contains(T item); /** * Retrieves all entries in this bag. * @return A newly allocated array of all entries in the bag. */ T[] toArray(); }

ArrayBag

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; } }