import java.util.*;

public class ArrayBag {

/*

* The array used to store the items in the bag.

*/

private Object[] items;

/**

* The number of items in the bag.

*/

private int numItems;

public static final int DEFAULT_MAX_SIZE = 50;

/**

* Constructor with no parameters - creates a new, empty ArrayBag with

* the default maximum size.

*/

public ArrayBag() {

this.items = new Object[DEFAULT_MAX_SIZE];

this.numItems = 0;

}

/**

* A constructor that creates a new, empty ArrayBag with the specified

* maximum size.

*/

public ArrayBag(int maxSize) {

if (maxSize <= 0) {

throw new IllegalArgumentException("maxSize must be > 0");

}

this.items = new Object[maxSize];

this.numItems = 0;

}

/**

* numItems - accessor method that returns the number of items

* in this ArrayBag.

*/

public int numItems() {

return this.numItems;

}

/**

* add - adds the specified item to this ArrayBag. Returns true if there

* is room to add it, and false otherwise.

* Throws an IllegalArgumentException if the item is null.

*/

public boolean add(Object item) {

if (item == null) {

throw new IllegalArgumentException("item must be non-null");

} else if (this.numItems == this.items.length) {

return false; // no more room!

} else {

this.items[this.numItems] = item;

this.numItems++;

return true;

}

}

/**

* remove - removes one occurrence of the specified item (if any)

* from this ArrayBag. Returns true on success and false if the

* specified item (i.e., an object equal to item) is not in this ArrayBag.

*/

public boolean remove(Object item) {

for (int i = 0; i < this.numItems; i++) {

if (this.items[i].equals(item)) {

// Shift the remaining items left by one.

for (int j = i; j < this.numItems - 1; j++) {

this.items[j] = this.items[j + 1];

}

this.items[this.numItems - 1] = null;

this.numItems--;

return true;

}

}

return false; // item not found

}

/**

* contains - returns true if the specified item is in the Bag, and

* false otherwise.

*/

public boolean contains(Object item) {

for (int i = 0; i < this.numItems; i++) {

if (this.items[i].equals(item)) {

return true;

}

}

return false;

}

/**

* grab - returns a reference to a randomly chosen item in this ArrayBag.

*/

public Object grab() {

if (this.numItems == 0) {

throw new IllegalStateException("the bag is empty");

}

int whichOne = (int)(Math.random() * this.numItems);

return this.items[whichOne];

}

/**

* toArray - return an array containing the current contents of the bag

*/

public Object[] toArray() {

Object[] copy = new Object[this.numItems];

for (int i = 0; i < this.numItems; i++) {

copy[i] = this.items[i];

}

return copy;

}

/**

* toString - converts this ArrayBag into a string that can be printed.

* Overrides the version of this method inherited from the Object class.

*/

public String toString() {

String str = "{";

for (int i = 0; i < this.numItems; i++) {

str = str + this.items[i];

if (i != this.numItems - 1) {

str += ", ";

}

}

str = str + "}";

return str;

}

/* Test the ArrayBag implementation. */

public static void main(String[] args) {

// Create a Scanner object for user input.

Scanner scan = new Scanner(System.in);

// Create an ArrayBag named bag1.

System.out.print("size of bag 1: ");

int size = scan.nextInt();

ArrayBag bag1 = new ArrayBag(size);

scan.nextLine(); // consume the rest of the line

// Read in strings, add them to bag1, and print out bag1.

String itemStr;

for (int i = 0; i < size; i++) {

System.out.print("item " + i + ": ");

itemStr = scan.nextLine();

bag1.add(itemStr);

}

System.out.println("bag 1 = " + bag1);

System.out.println();

// Select a random item and print it.

Object item = bag1.grab();

System.out.println("grabbed " + item);

System.out.println();

// Iterate over the objects in bag1, printing them one per

// line.

Object[] items = bag1.toArray();

for (int i = 0; i < items.length; i++) {

System.out.println(items[i]);

}

System.out.println();

// Get an item to remove from bag1, remove it, and reprint the bag.

System.out.print("item to remove: ");

itemStr = scan.nextLine();

if (bag1.contains(itemStr)) {

bag1.remove(itemStr);

}

System.out.println("bag 1 = " + bag1);

System.out.println();

}

}

Add the methods described below to the ArrayBag class, and then add code to the main()method to test these methods. You should not add any new fields to the class.

1. public int size() This method should return the maximum number of items that the called ArrayBag is able to hold. This value does not depend on the number of items that are currently in the ArrayBag. Rather, it is the same value as the maximum size specified when the ArrayBagwas created. For example:

ArrayBag b1 = new ArrayBag(10); System.out.println(b1.size()); 

should output:

10 

Hint: This method should only need one or two lines of code.

2. public int count(Object item) This method should return a count of the number of times that the parameter itemoccurs in the called ArrayBag. For example:

ArrayBag b2 = new ArrayBag(10); int[] vals = {7, 5, 3, 7, 7, 2, 5}; for (int x : vals) { b2.add(x); } System.out.println(b2.count(2)); System.out.println(b2.count(7)); System.out.println(b2.count(8)); 

should output:

1 3 0 

Your method must not change the internals of the ArrayBag object.

3. public boolean reduceSize(int decrease) This method should reduce the size of the called ArrayBag by the specified amount but only if it is feasible to do so. For example, if b has a size of 20, then b.reduceSize(5)should give b a size of 15.

However, the requested change should only be made if it doesnt cause the ArrayBag to be too small for its current contents. If the requested reduction in size wouldnt leave enough room for all of the items in the ArrayBag, the method should return false and it should not make any changes.

If the requested reduction can be made, you will need to create a new array with just enough room for the new size, copy any existing items into that array, and replace the original array with the new one by storing its reference in the called object. Finally, the method should return true to indicate success.

For example, the following test code:

ArrayBag b3 = new ArrayBag(8); b3.add("hello"); b3.add("world"); System.out.println(b3); System.out.println("size before: " + b3.size()); b3.reduceSize(5); System.out.println(b3); System.out.println("size after: " + b3.size()); 

should produce the following output:

{hello, world} size before: 8 {hello, world} size after: 3 

Other special cases:

If decrease is 0, the method should just return true.

If decrease is negative, the method should throw an IllegalArgumentException.

4. public boolean equals(ArrayBag other) This method should determine if the called ArrayBag is equal to the parameter other. Two bags are equal if they contain the same items. The location of the items in the bags does not matter (e.g., {5, 6, 6, 7} is equal to {7, 6, 5, 6}), but bags that are equal must have the same number of occurrences of each item (e.g., {5, 6, 6, 7} is notequal to {5, 6, 7}). The method should return true if the two bags are equal, and false otherwise (including cases in which the parameter is null).

Notes:

Your method must not change the internals of either ArrayBag object.

For full credit, you should take advantage of the one of the other methods that you are implementing for this problem. Doing so will make your job much easier!

5. public ArrayBag subtract(ArrayBag other) This method should create and return an ArrayBag containing one occurrence of any item from the called ArrayBag object that is not also present in the ArrayBagrepresented by the parameter other. For full credit, the resulting bag should not include any duplicates. For example, if b1 represents the bag {2, 2, 3, 5, 7, 7, 7, 8} and b2 represents the bag {4, 5, 6, 8}, then b1.subtract(b2) should return an ArrayBagrepresenting the bag {2, 3, 7}. Note that the resulting bag should not include the 5 or 8 from b1, because those values are also in b2.

Give the new ArrayBag a maximum size that is equal to the number of items in the called ArrayBag (but see below for an exception). The order of the items in the returned ArrayBag does not matter.

Special cases:

If the parameter is null, the method should throw an IllegalArgumentException.

In general, the returned ArrayBag should have a maximum size that is equal to the number of items in the called ArrayBag. However, because its not possible to construct an ArrayBag with a maximum size of 0, you should give the new ArrayBaga maximum size of 1 if the called ArrayBag has no items.

Notes:

Your method must not change the internals of either of the original ArrayBag objects.

For full credit, you should take full advantage of the existing ArrayBagmethods. They will make your job much easier!

Here is some additional test code:

ArrayBag b5 = new ArrayBag(10); String[] letters5 = {"a", "a", "b", "d", "f", "f", "f", "g"}; for (String ltr: letters5) { b5.add(ltr); } System.out.println(b5); ArrayBag b6 = new ArrayBag(7); String[] letters6 = {"b", "c", "e", "e", "g"}; for (String ltr: letters6) { b6.add(ltr); } System.out.println(b6); ArrayBag b7 = b5.subtract(b6); System.out.println(b7); System.out.println(b7.numItems()); System.out.println(b7.size()); System.out.println(b5); // make sure original bags are unchanged System.out.println(b6); 

Running it should output:

{a, a, b, d, f, f, f, g} {b, c, e, e, g} {a, d, f} 3 8 {a, a, b, d, f, f, f, g} {b, c, e, e, g} 

Note: The items in the result ({a, d, f}) can appear in any order.