Consider a bag as a way to organize data. A grocery bag, for example, contains items in no particular order. Some of them might be duplicate items. The ADT bag, like a grocery bag, is perhaps the simplest of data organizations. It holds objects but does not arrange or organize them further.

The attached BagIterface.java contains java interface that defines all the operations that can be performed on ADT bag. Please note that the interface has been expanded from its definition in Chapter 1; javadoc comments describe operations purpose, parameters and return values.

In addition to these basic operations, the following are included:

union - combines the contents of two bags into a third bag (see Exercise 5 in Chapter 1)

intersection - creates a third bag of only those items that occur in both two bags (see Exercise 6 in Chapter 1)

difference - creates a third bag of the items that would be left in the given bag after removing those that also occur in another bag (see Exercise 7 in Chapter 1)

getAllLessThan - creates a bag of all the items that are smaller than the given item

removeMax removes and returns the largest element from the bag

isSubset - returns true if all the elements of the given bag are also included in the other bag

equals - returns true if the contents of two bags are the same. Note that two equal bags contain the same number of entries, each entry occurs in each bag in the same position in the collection of objects

Your Task:

1. The class ResizableArrayBag implements the interface BagInterface where the bag is represented as an array that can expand dynamically as necessary. Make sure that the DEFAULT_CAPACITY in ResizableArrayBag is set to 25.

2. Analyze provided interface including javadoc comments that describe the purpose of each method, its parameters and return values. UML diagram is also provided for your reference.

3. Analyze the implementation of the methods provided in the ResizableArrayBag class. Note that the main is included in this class as well.

4. Implement the remaining methods that are stubs at this moment:

a. public boolean equals(BagInterface other);

b. public void removeEvery(T anEntry);

c. public T replace(T replacement);

d. public BagInterface union(BagInterface other);

e. public BagInterface intersection(BagInterface other);

f. public BagInterface difference(BagInterface other);

g. public boolean isSubset(BagInterface other);

h. public BagInterface getAllLessThan(T anEntry);

i. public T removeMax();

5. Make sure that the output is correct (see Sample Run below).

import java.util.Arrays;   * A class that implements a bag of objects by using an array.  * The bag is never full.  public class ResizableArrayBag> implements BagInterface { private T[] bag; // Cannot be final due to doubling private int numberOfEntries; private boolean initialized = false; // TODO Project3 - change the DEFAULT_CAPACITY to 25  private static final int DEFAULT_CAPACITY = 3; // 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 Comparable>[initialCapacity]; // Unchecked cast this.bag = tempBag; this.numberOfEntries = 0; this.initialized = true; } // end constructor /**  * Creates a bag containing given entries.  *  * @param contents An array of objects.  * @param numberOfElements - the number of entries we want to copy starting at index 0  */  public ResizableArrayBag(T[] contents, int numberOfElements) { this(numberOfElements); for (int i = 0; i /**  * 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(); } this.bag[this.numberOfEntries] = newEntry; this.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 Comparable>[this.numberOfEntries]; // Unchecked cast for (int index = 0; index /**  * Sees whether this bag is empty.  *  * @return True if this bag is empty, or false if not.  */  public boolean isEmpty() { return this.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 this.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 /**  * 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 // 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 stillLooking = true; for (int index = 0; stillLooking && (index /**  * 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(this.numberOfEntries - 1); return result; } // end remove /**  * Removes one occurrence of a given entry from this bag.  *  * @param anElement The entry to be removed.  * @return True if the removal was successful, or false if not.  */  public boolean removeElement(T anElement) { checkInitialization(); int index = getIndexOf(anElement); T result = removeEntry(index); return anElement.equals(result); } // end remove // Removes and returns the entry at a given index within the array. // If no such entry exists, returns null. // Precondition: 0 = 0)) { result = this.bag[givenIndex]; // Entry to remove this.numberOfEntries--; this.bag[givenIndex] = this.bag[this.numberOfEntries]; // Replace entry to remove with last entry this.bag[this.numberOfEntries] = null; // Remove reference to last entry } return result; } // end removeEntry // Returns true if the array bag is full, or false if not. private boolean isArrayFull() { return this.numberOfEntries >= this.bag.length; } // end isArrayFull // Doubles the size of the array bag. // Precondition: checkInitialization has been called. private void doubleCapacity() { int newLength = 2 * this.bag.length; checkCapacity(newLength); this.bag = Arrays.copyOf(this.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 (!this.initialized) throw new SecurityException("Uninitialized object used " + "to call an ArrayBag method."); } // end checkInitialization /**  * Displays all the elements in the bag  */  public void display() { if (this.numberOfEntries > 0) { System.out.print("There are " + this.numberOfEntries + " element(s): "); for (int index = 0; index out.print(this.bag[index] + " "); } System.out.println(); } else System.out.println("The bag is empty"); } // end display // // +++++++++++++++++++ NEW METHODS +++++++++++++++++++++++++++ // /**  * Checks if the given bag called other is the same as the bag  *  * @param o the other bag to be compared with  * @return true both bags are the same  */  public boolean equals(Object o) { boolean same; if (this == o) same = true; else if (o == null || getClass() != o.getClass()) same = false; else { ResizableArrayBag other = (ResizableArrayBag) o; //TODO Project3  // one return statement per method please // first compare number of entries in both bags // only if the number of entries is the same // use a regular for loop to compare elements // stop the loop as soon as the first unequal pair is found } return false; // this is a stub, must return the computed value of same } /**  * Removes the largest entry from the this.bag  *  * @return - null if the element was not found or the largest element. Uses removeEntry(givenIndex) method  */  public T removeMax() { //TODO Project3   // one return statement per method please return null; //THIS IS A STUB } // end removeMax /**  * Removes every occurrence of a given entry from this bag. Uses removeEntry(givenIndex) method  *  * @param anEntry the entry to be removed  */  public void removeEvery(T anEntry) { //TODO Project3   // must utilize only one loop that starts with the last element } // end removeEvery /**  * Replaces the last entry in this bag with a given object.  *  * @param replacement the given object  * @return the original entry in the bag that was replaced or null if the bag was empty  */  public T replace(T replacement) { //TODO Project3  // replace data at selected index // one return statement per method please return null; //THIS IS A STUB } // end replace /**  * Creates a new bag that combines the contents of this bag and  * the second given bag without affecting the original two bags.  *  * @param otherBag the given bag  * @return a bag that is the union of the two bags  */  public BagInterface union(BagInterface otherBag) { ResizableArrayBag other = (ResizableArrayBag) otherBag; ResizableArrayBag unionBag = new ResizableArrayBag(); //TODO Project3   // one return statement per method please return unionBag; } // end union /**  * Creates a new bag that contains those objects that occur in both this  * bag and the second given bag without affecting the original two bags.  * utilizes getIndexOf(anEntry) and removeEntry(givenIndex) methods  *  * @param otherBag the given bag  * @return a bag that is the intersection of the two bags  */  public BagInterface intersection(BagInterface otherBag) { ResizableArrayBag other = (ResizableArrayBag) otherBag; ResizableArrayBag intersectionBag = new ResizableArrayBag(); ResizableArrayBag copyOfOtherBag = new ResizableArrayBag(); //TODO Project3   // do NOT call contains, utilize getIndexOf(anEntry) and removeEntry(givenIndex) methods instead // one return statement per method please return intersectionBag; } // end intersection /**  * Creates a new bag of objects that would be left in this bag  * after removing those that also occur in a second given bag  * without affecting the original two bags.  *  * @param otherBag the given bag  * @return a bag that is the difference of the two bags  */  public BagInterface difference(BagInterface otherBag) { ResizableArrayBag other = (ResizableArrayBag) otherBag; ResizableArrayBag differenceBag = new ResizableArrayBag(); //TODO Project3   // do NOT call contains, utilize getIndexOf(anEntry) and removeEntry(givenIndex) methods instead // one return statement per method please return differenceBag; } // end difference /**  * Creates a new bag of objects that are in this bag and are less than a given object.  *  * @param anEntry a given object  * @return a new bag of objects that are in this bag and are less than anEntry  */  public BagInterface getAllLessThan(T anEntry) { BagInterface result = new ResizableArrayBag(); //TODO Project3   // utilize compareTo method // one return statement per method please return result; } // end getAllLessThan /**  * Checks if all the elements of the given bag are also included in the other bag  *  * @param other bag to check  * @return returns true if all the elements of the given bag are also included in the other bag  */  public boolean isSubset(BagInterface other) { //TODO Project3   // utilize difference method // one return statement per method please return false; //THIS IS A STUB } public static void main(String[] args) { System.out.println("RUNNING TEST CASES"); ResizableArrayBag bag1 = new ResizableArrayBag(3); ResizableArrayBag bag2 = new ResizableArrayBag(); bag1.add("C"); bag1.add("A"); bag1.add("A"); bag1.add("A"); bag1.add("X"); System.out.println("Created bag1:"); bag1.display(); System.out.println("Created bag2:"); bag2.display(); System.out.println("After removing the last element " + bag1.remove() + " from bag1, it contains:"); bag1.display(); // testing equals System.out.println(" ***Testing equals method***"); System.out.println("Are bag1 and bag2 equal? --> " + (bag1.equals(bag2) ? "YES" : "NO")); System.out.println("Are bag2 and bag1 equal? --> " + (bag2.equals(bag1) ? "YES" : "NO")); bag2.add("A"); bag2.add("A"); bag2.add("A"); bag2.add("C"); bag2.add("X"); System.out.println("bag2:"); bag2.display(); System.out.println("Are bag1 and bag2 equal? --> " + (bag1.equals(bag2) ? "YES" : "NO")); System.out.println("Removed " + bag2.remove() + " from bag2:"); bag2.display(); System.out.println("Are bag1 and bag2 equal now? --> " + (bag1.equals(bag2) ? "YES" : "NO")); ResizableArrayBag bagCopyOfBag1 = new ResizableArrayBag(bag1.toArray(), bag1.getCurrentSize()); System.out.println("Created bagCopyOfBag1:"); bagCopyOfBag1.display(); System.out.println("Are bag1 and bagCopyOfBag1 equal? --> " + (bag1.equals(bagCopyOfBag1) ? "YES" : "NO")); bag1.clear(); bag1.add("C"); bag1.add("A"); bag1.add("A"); bag1.add("X"); bag1.add("A"); bag2.clear(); bag2.add("A"); bag2.add("B"); bag2.add("B"); bag2.add("A"); bag2.add("C"); bag2.add("C"); bag2.add("D"); System.out.println(" ***Testing union, intersection, difference, removeMax, getAllLessThan and isSubset methods***"); System.out.println("bag1:"); bag1.display(); System.out.println("bag2:"); bag2.display(); // testing union System.out.println(" ***Testing union method***"); BagInterface everything = bag1.union(bag2); System.out.println("The union of bag1 and bag2 is:"); everything.display(); // testing removeMax System.out.println(" ***Testing removeMax method***"); String largest = everything.removeMax(); System.out.println("Removed the largest element \"" + largest + "\" from the union bag; the current content is:"); everything.display(); everything.clear(); largest = everything.removeMax(); if (largest == null) System.out.println("The bag is empty and removeMax returned null - CORRECT"); else System.out.println("The bag is empty bur removeMax returned did not return null - INCORRECT"); // testing intersection System.out.println(" ***Testing intersection method***"); BagInterface commonItems = bag1.intersection(bag2); System.out.println("The intersection of bag1 and bag2 is:"); commonItems.display(); // testing difference System.out.println(" ***Testing difference method***"); BagInterface leftOver = bag1.difference(bag2); System.out.println("The difference of bag1 and bag2 is:"); leftOver.display(); leftOver = bag2.difference(bag1); System.out.println("The difference of bag2 and bag1 is:"); leftOver.display(); // testing getAllLessThan System.out.println(" ***Testing getAllLessThan method***"); BagInterface smaller = bag1.getAllLessThan("Z"); System.out.println("The following entries in bag1 are smaller than \"Z\":"); smaller.display(); smaller = bag2.getAllLessThan("C"); System.out.println("The following entries in bag2 are smaller than \"C\":"); smaller.display(); // testing subset System.out.println(" ***Testing isSubset method***"); System.out.println("Is bag1 a subset of bag1 ? --> " + (bag1.isSubset(bag1) ? "YES" : "NO")); System.out.println("Is bag1 a subset of bag2 ? --> " + (bag1.isSubset(bag2) ? "YES" : "NO")); ResizableArrayBag emptyBag = new ResizableArrayBag(); System.out.println("Is an empty bag a subset of bag2 ? --> " + (emptyBag.isSubset(bag2) ? "YES" : "NO")); System.out.println("Is bag2 a subset of an empty bag ? --> " + (bag2.isSubset(emptyBag) ? "YES" : "NO")); ResizableArrayBag bag3 = new ResizableArrayBag(); ResizableArrayBag bag4 = new ResizableArrayBag(); bag3.add("A"); bag3.add("B"); bag3.add("C"); System.out.println("Created bag3:"); bag3.display(); bag4.add("B"); bag4.add("C"); bag4.add("A"); System.out.println("Created bag4:"); bag4.display(); System.out.println("Is bag3 a subset of bag4 ? --> " + (bag3.isSubset(bag4) ? "YES" : "NO")); bag4.add("Z"); System.out.println("Is bag3 a subset of bag4 after adding \"Z\" to it ? --> " + (bag3.isSubset(bag4) ? "YES" : "NO")); System.out.println("Is bag4 a subset of bag3 ? --> " + (bag4.isSubset(bag3) ? "YES" : "NO")); System.out.println("Adding \"Z\" to bag 3 twice"); bag3.add("Z"); bag3.add("Z"); System.out.println("bag3:"); bag3.display(); System.out.println("bag4:"); bag4.display(); System.out.println("Is bag3 a subset of bag4 ? --> " + (bag3.isSubset(bag4) ? "YES" : "NO")); bag1.clear(); bag1.add("A"); bag1.add("A"); bag1.add("B"); bag1.add("X"); bag1.add("A"); bag1.add("C"); bag1.add("A"); // testing replace System.out.println(" ***Testing replace method***"); System.out.println("bag1:"); bag1.display(); System.out.println("Replaced \"" + bag1.replace("X") + "\" with \"X\""); System.out.println("Now bag1 contains:"); bag1.display(); // testing removeEvery System.out.println(" ***Testing removeEvery method***"); System.out.println("bag1:"); bag1.display(); System.out.println("Removing all \"Z\""); bag1.removeEvery("Z"); System.out.println("After removing all \"Z\" bag1 contains:"); bag1.display(); System.out.println("Removing all \"A\""); bag1.removeEvery("A"); System.out.println("After removing all \"A\" bag1 contains:"); bag1.display(); System.out.println("Removing all \"X\""); bag1.removeEvery("X"); System.out.println("After removing all \"X\" bag1 contains:"); bag1.display(); } // end main } // end ResizableArrayBag

Sample Run:

RUNNING TEST CASES

Created bag1:

There are 5 element(s): C A A A X

Created bag2:

The bag is empty

After removing the last element X from bag1, it contains:

There are 4 element(s): C A A A

***Testing equals method***

Are bag1 and bag2 equal? --> NO

Are bag2 and bag1 equal? --> NO

bag2:

There are 5 element(s): A A A C X

Are bag1 and bag2 equal? --> NO

Removed X from bag2:

There are 4 element(s): A A A C

Are bag1 and bag2 equal now? --> NO

Created bagCopyOfBag1:

There are 4 element(s): C A A A

Are bag1 and bagCopyOfBag1 equal? --> YES

***Testing union, intersection, difference, removeMax, getAllLessThan and isSubset methods***

bag1:

There are 5 element(s): C A A X A

bag2:

There are 7 element(s): A B B A C C D

***Testing union method***

The union of bag1 and bag2 is:

There are 12 element(s): C A A X A A B B A C C D

***Testing removeMax method***

Removed the largest element "X" from the union bag; the current content is:

There are 11 element(s): C A A D A A B B A C C

The bag is empty and removeMax returned null - CORRECT

***Testing intersection method***

The intersection of bag1 and bag2 is:

There are 3 element(s): C A A

***Testing difference method***

The difference of bag1 and bag2 is:

There are 2 element(s): A X

The difference of bag2 and bag1 is:

There are 4 element(s): C B B D

***Testing getAllLessThan method***

The following entries in bag1 are smaller than "Z":

There are 5 element(s): C A A X A

The following entries in bag2 are smaller than "C":

There are 4 element(s): A B B A

***Testing isSubset method***

Is bag1 a subset of bag1 ? --> YES

Is bag1 a subset of bag2 ? --> NO

Is an empty bag a subset of bag2 ? --> YES

Is bag2 a subset of an empty bag ? --> NO

Created bag3:

There are 3 element(s): A B C

Created bag4:

There are 3 element(s): B C A

Is bag3 a subset of bag4 ? --> YES

Is bag3 a subset of bag4 after adding "Z" to it ? --> YES

Is bag4 a subset of bag3 ? --> NO

Adding "Z" to bag 3 twice

bag3:

There are 5 element(s): A B C Z Z

bag4:

There are 4 element(s): B C A Z

Is bag3 a subset of bag4 ? --> NO

***Testing replace method***

bag1:

There are 7 element(s): A A B X A C A

Replaced "A" with "X"

Now bag1 contains:

There are 7 element(s): A A B X A C X

***Testing removeEvery method***

bag1:

There are 7 element(s): A A B X A C X

Removing all "Z"

After removing all "Z" bag1 contains:

There are 7 element(s): A A B X A C X

Removing all "A"

After removing all "A" bag1 contains:

There are 4 element(s): X C B X

Removing all "X"

After removing all "X" bag1 contains:

There are 2 element(s): B C

Process finished with exit code 0

Bagin terface getCurrentSize0 int boolean boolean madd(T) remove() removeElement(T) boolean void int boolean mclear getFrequencyOf (T) % contains(T) mb toArray0 display0 equals(Object) removeEvery(T) void boolean void @..b replace( union(Baginterface intersection (Baginterface Baginterface Bagin terfaceT> m difference(B aginterface boolean Baginterface isSubset (BaginterfacecT>) getAllLess Than(T d bag a numberOf Entries int boolean int int initialized DEFAULT CAPACITY MAX CAPACITY mResizableArrayBag0 ResizableA rrayBag(int) @ ResizableArrayBag(m.int) @ add(T) mb toArray0 misEmpty0 boolean boolean nt int boolean int void b getCurrentSize0 @ getFrequencyOf(T) .' contains(T) getindexOr(T) clear remove0 removeElement(T boolean aremoveEntry(int) isArrayFull) doubleCapacity0 checkCapacity(int) m display0 @.b rrnoveMax() md checkinitialization 0 equals(Object) removeEvery(T) boolean void void void void boolean void replace(T) @'b union(Baginterface.) mb int ersection (Bagint erfaceT mdifference(B aginterface Baginterface Baginterface Baginterface boolean void getAILessThan(T @ isSubset(BagInterface) main (String[]