Java Lab #3 -- Bags Which Are Sets!

In lecture we looked at how to implement a Bag strictly as defined. But how about how to implement a Bag which is also an unordered set? The big difference here will be that we WILL NOT allow duplicates in our Bag. To get started, I've included the book's code for ResizableArrayBag (including the driver) in this assignment. What I would like you to do is to modify this code so that the ResizableArrayBag will correctly exclude duplicate values, add the new methods described below, and ensure that the driver (either modify the existing driver or write a new driver) tests all of your new features!

Point Breakdown:

Enforce the no duplicates rule to make ResizableArrayBag into Set:

Modify the add() method [20 points]

Modify the ResizableArrayBag() constructor that takes an array as input [20 points]

Create an equals() method which will check to see if two Bags are equal. To be equal, the Bags must have the same number of elements and have the same element values inside both Bags. Order of the elements is NOT important. [20 points]HINTS:

equals() methods should take in an Object datatype

Check to see if the input parameter is an instanceof ResizableArrayBag

If not don't bother trying to evaluate further, just return false.

If it is, cast the input parameter to a ResizableArrayBag and then check the two bags' contents

Create an union() method which should : [20 points]

Compare the contents of two Bags

Produce/Return a Bag which contains elements which appear in AT LEAST ONE of the two initial Bags

HINT: Our BagInterface has the union() header commented out. So you should start by uncommenting out the union() header in the interface. You can then use that header in your ResizableArrayBag

Create an intersection() method which should: [20 points]

Compares the contents of two Bags

Produce/Return a Bag which contains elements which appear in BOTH of the initial two Bags

HINT: Our BagInterface has the intersection() header commented out. So you should start by uncommenting out the intersection() header in the interface. You can then use that header in your ResizableArrayBag

Reminder: To achieve full credit for each task, your driver MUST adequately test the features of the task AND all changes and/or new methods must be JavaDoc'd.

Not updating the driver to test your changes/new code may result in up to 15 points of deduction

Not Java Docing your changes/new methods may result in up to 10 points of deduction

Resizable

/** A demonstration of the class ResizableArrayBag * * @author Frank M. Carrano * @author Timothy M. Henry * @version 4.0 */ public class ResizableArrayBagDemo {

public static void main(String[] args) { // A bag whose initial capacity is small BagInterface aBag = new ResizableArrayBag<>(3); testIsEmpty(aBag, true);

System.out.println("Adding to the bag more strings than its initial capacity."); String[] contentsOfBag = { "A", "D", "B", "A", "C", "A", "D" }; testAdd(aBag, contentsOfBag);

testIsEmpty(aBag, false); String[] testStrings2 = { "A", "B", "C", "D", "Z" }; testFrequency(aBag, testStrings2); testContains(aBag, testStrings2);

// Removing strings String[] testStrings3 = { "", "B", "A", "C", "Z" }; testRemove(aBag, testStrings3);

System.out.println(" Clearing the bag:"); aBag.clear(); testIsEmpty(aBag, true); displayBag(aBag); } // end main

// Tests the method add. private static void testAdd(BagInterface aBag, String[] content) { System.out.print("Adding to the bag: "); for (int index = 0; index < content.length; index++) { aBag.add(content[index]); System.out.print(content[index] + " "); } // end for System.out.println();

displayBag(aBag); } // end testAdd

// Tests the two remove methods. private static void testRemove(BagInterface aBag, String[] tests) { for (int index = 0; index < tests.length; index++) { String aString = tests[index]; if (aString.equals("") || (aString == null)) { // Test remove() System.out.println(" Removing a string from the bag:"); String removedString = aBag.remove(); System.out.println("remove() returns " + removedString); } else { // Test remove(aString) System.out.println(" Removing \"" + aString + "\" from the bag:"); boolean result = aBag.remove(aString); System.out.println("remove(\"" + aString + "\") returns " + result); } // end if

displayBag(aBag); } // end for } // end testRemove

// Tests the method isEmpty. // correctResult indicates what isEmpty should return. private static void testIsEmpty(BagInterface aBag, boolean correctResult) { System.out.print("Testing isEmpty with "); if (correctResult) { System.out.println("an empty bag:"); } else { System.out.println("a bag that is not empty:"); }

System.out.print("isEmpty finds the bag "); if (correctResult && aBag.isEmpty()) { System.out.println("empty: OK."); } else if (correctResult) { System.out.println("not empty, but it is empty: ERROR."); } else if (!correctResult && aBag.isEmpty()) { System.out.println("empty, but it is not empty: ERROR."); } else { System.out.println("not empty: OK."); } System.out.println(); } // end testIsEmpty

// Tests the method getFrequencyOf. private static void testFrequency(BagInterface aBag, String[] tests) { System.out.println(" Testing the method getFrequencyOf:"); for (int index = 0; index < tests.length; index++) { System.out.println("In this bag, the count of " + tests[index] + " is " + aBag.getFrequencyOf(tests[index])); } } // end testFrequency

// Tests the method contains. private static void testContains(BagInterface aBag, String[] tests) { System.out.println(" Testing the method contains:"); for (int index = 0; index < tests.length; index++) { System.out.println("Does this bag contain " + tests[index] + "? " + aBag.contains(tests[index])); } } // end testContains

// Tests the method toArray while displaying the bag. private static void displayBag(BagInterface aBag) { System.out.println("The bag contains " + aBag.getCurrentSize() + " string(s), as follows:"); Object[] bagArray = aBag.toArray(); for (int index = 0; index < bagArray.length; index++) { System.out.print(bagArray[index] + " "); } // end for

System.out.println(); } // end displayBag } // end ResizableArrayBagDemo /*

Testing isEmpty with an empty bag: isEmpty finds the bag empty: OK. Adding to the bag more strings than its initial capacity. Adding to the bag: A D B A C A D The bag contains 7 string(s), as follows: A D B A C A D Testing isEmpty with a bag that is not empty: isEmpty finds the bag not empty: OK. Testing the method getFrequencyOf: In this bag, the count of A is 3 In this bag, the count of B is 1 In this bag, the count of C is 1 In this bag, the count of D is 2 In this bag, the count of Z is 0 Testing the method contains: Does this bag contain A? true Does this bag contain B? true Does this bag contain C? true Does this bag contain D? true Does this bag contain Z? false Removing a string from the bag: remove() returns D The bag contains 6 string(s), as follows: A D B A C A Removing "B" from the bag: remove("B") returns true The bag contains 5 string(s), as follows: A D A A C Removing "A" from the bag: remove("A") returns true The bag contains 4 string(s), as follows: C D A A Removing "C" from the bag: remove("C") returns true The bag contains 3 string(s), as follows: A D A Removing "Z" from the bag: remove("Z") returns false The bag contains 3 string(s), as follows: A D A Clearing the bag: Testing isEmpty with an empty bag: isEmpty finds the bag empty: OK. The bag contains 0 string(s), as follows: */

Array

import java.util.Arrays;

/** * A class that implements a bag of objects by using an array. The bag is never * full. * * @author Frank M. Carrano * @author Timothy M. Henry * @version 4.0 */ public final class ResizableArrayBag implements BagInterface {

private T[] bag; // Cannot be final due to doubling private int numberOfEntries; private boolean initialized = false; private static final int DEFAULT_CAPACITY = 25; // Initial capacity of bag private static final int MAX_CAPACITY = 10000;

/** * Creates an empty bag whose initial capacity is 25. */ public ResizableArrayBag() { this(DEFAULT_CAPACITY); } // end default constructor

/** * Creates an empty bag having a given initial capacity. * * @param initialCapacity The integer capacity desired. */ public ResizableArrayBag(int initialCapacity) { checkCapacity(initialCapacity);

// The cast is safe because the new array contains null entries @SuppressWarnings("unchecked") T[] tempBag = (T[]) new Object[initialCapacity]; // Unchecked cast bag = tempBag; numberOfEntries = 0; initialized = true; } // end constructor

/** * Creates a bag containing given entries. * * @param contents An array of objects. */ public ResizableArrayBag(T[] contents) { checkCapacity(contents.length); bag = Arrays.copyOf(contents, contents.length); numberOfEntries = contents.length; initialized = true; } // end constructor

/** * Adds a new entry to this bag. * * @param newEntry The object to be added as a new entry. * @return True. */ public boolean add(T newEntry) { checkInitialization(); if (isArrayFull()) { doubleCapacity(); } // end if

bag[numberOfEntries] = newEntry; numberOfEntries++;

return true; } // end add

/** * Retrieves all entries that are in this bag. * * @return A newly allocated array of all the entries in this bag. */ public T[] toArray() { checkInitialization();

// The cast is safe because the new array contains null entries. @SuppressWarnings("unchecked") T[] result = (T[]) new Object[numberOfEntries]; // Unchecked cast for (int index = 0; index < numberOfEntries; index++) { result[index] = bag[index]; } // end for

return result; } // end toArray

/** * Sees whether this bag is empty. * * @return True if this bag is empty, or false if not. */ public boolean isEmpty() { return numberOfEntries == 0; } // end isEmpty

/** * Gets the current number of entries in this bag. * * @return The integer number of entries currently in this bag. */ public int getCurrentSize() { return numberOfEntries; } // end getCurrentSize

/** * Counts the number of times a given entry appears in this bag. * * @param anEntry The entry to be counted. * @return The number of times anEntry appears in this ba. */ public int getFrequencyOf(T anEntry) { checkInitialization(); int counter = 0;

for (int index = 0; index < numberOfEntries; index++) { if (anEntry.equals(bag[index])) { counter++; } // end if } // end for

return counter; } // end getFrequencyOf

/** * Tests whether this bag contains a given entry. * * @param anEntry The entry to locate. * @return True if this bag contains anEntry, or false otherwise. */ public boolean contains(T anEntry) { checkInitialization(); return getIndexOf(anEntry) > -1; // or >= 0 } // end contains

/** * Removes all entries from this bag. */ public void clear() { while (!isEmpty()) { remove(); } } // end clear

/** * Removes one unspecified entry from this bag, if possible. * * @return Either the removed entry, if the removal was successful, or null. */ public T remove() { checkInitialization(); T result = removeEntry(numberOfEntries - 1); return result; } // end remove

/** * Removes one occurrence of a given entry from this bag. * * @param anEntry The entry to be removed. * @return True if the removal was successful, or false if not. */ public boolean remove(T anEntry) { checkInitialization(); int index = getIndexOf(anEntry); T result = removeEntry(index); return anEntry.equals(result); } // end remove

// Locates a given entry within the array bag. // Returns the index of the entry, if located, // or -1 otherwise. // Precondition: checkInitialization has been called. private int getIndexOf(T anEntry) { int where = -1; boolean found = false; int index = 0;

while (!found && (index < numberOfEntries)) { if (anEntry.equals(bag[index])) { found = true; where = index; } // end if index++; } // end while

// Assertion: If where > -1, anEntry is in the array bag, and it // equals bag[where]; otherwise, anEntry is not in the array. return where; } // end getIndexOf

// Removes and returns the entry at a given index within the array. // If no such entry exists, returns null. // Precondition: 0 <= givenIndex < numberOfEntries. // Precondition: checkInitialization has been called. private T removeEntry(int givenIndex) { T result = null;

if (!isEmpty() && (givenIndex >= 0)) { result = bag[givenIndex]; // Entry to remove int lastIndex = numberOfEntries - 1; bag[givenIndex] = bag[lastIndex]; // Replace entry to remove with last entry bag[lastIndex] = null; // Remove reference to last entry numberOfEntries--; } // end if

return result; } // end removeEntry

// Returns true if the array bag is full, or false if not. private boolean isArrayFull() { return numberOfEntries >= bag.length; } // end isArrayFull

// Doubles the size of the array bag. // Precondition: checkInitialization has been called. private void doubleCapacity() { int newLength = 2 * bag.length; checkCapacity(newLength); bag = Arrays.copyOf(bag, newLength); } // end doubleCapacity

// Throws an exception if the client requests a capacity that is too large. private void checkCapacity(int capacity) { if (capacity > MAX_CAPACITY) { throw new IllegalStateException("Attempt to create a bag whose capacity exceeds " + "allowed maximum of " + MAX_CAPACITY); } } // end checkCapacity

// Throws an exception if receiving object is not initialized. private void checkInitialization() { if (!initialized) { throw new SecurityException("Uninitialized object used " + "to call an ArrayBag method."); } } // end checkInitialization } // end ResizableArrayBag

Interface

/** * An interface that describes the operations of a bag of objects. * * @author Frank M. Carrano * @author Timothy M. Henry * @version 4.1 */ public interface BagInterface {

/** * Gets the current number of entries in this bag. * * @return The integer number of entries currently in the bag. */ public int getCurrentSize();

/** * Sees whether this bag is empty. * * @return True if the bag is empty, or false if not. */ public boolean isEmpty();

/** * Adds a new entry to this bag. No duplicates may be added to the bag! * * @param newEntry The object to be added as a new entry. * @return True if the addition is successful, or false if not. */ public boolean add(T newEntry);

/** * Removes one unspecified entry from this bag, if possible. * * @return Either the removed entry, if the removal. was successful, or * null. */ public T remove();

/** * Removes one occurrence of a given entry from this bag. * * @param anEntry The entry to be removed. * @return True if the removal was successful, or false if not. */ public boolean remove(T anEntry);

/** * Removes all entries from this bag. */ public void clear();

/** * Counts the number of times a given entry appears in this bag. * * @param anEntry The entry to be counted. * @return The number of times anEntry appears in the bag. */ public int getFrequencyOf(T anEntry);

/** * Tests whether this bag contains a given entry. * * @param anEntry The entry to locate. * @return True if the bag contains anEntry, or false if not. */ public boolean contains(T anEntry);

/** * Retrieves all entries that are in this bag. * * @return A newly allocated array of all the entries in the bag. Note: If * the bag is empty, the returned array is empty. */ public T[] toArray(); // public T[] toArray(); // Alternate // public Object[] toArray(); // Alternate

/** * Creates a new bag that combines the contents of this bag and anotherBag. * * @param anotherBag The bag that is to be added. * @return A combined bag. */ //public BagInterface union(BagInterface anotherBag); /** * Creates a new bag that contains those objects that are present in both this bag * and anotherBag. * * @param anotherBag The bag that is to be compared. * @return A combined bag. */ //public BagInterface intersection(BagInterface anotherBag); /** * Creates a new bag of objects appeared in both bags. * * @param anotherBag The bag that is to be removed. * @return A combined bag. */ // public BagInterface difference(BagInterface anotherBag); } // end BagInterface