Write a complete method that takes a bag as a parameter and returns the minimum
ID: 3580897 • Letter: W
Question
Write a complete method that takes a bag as a parameter and returns the minimum number in the bag.
The method header is: public Integer findMin(BagInterface<Integer> bag)
The bag should not be altered when the method completes.
Use only the methods listed below from BagInterface.
Note that toArray is not listed and should not be used in your solution.
You can also refer to BagInterface and ListInterface Files for the full details about the bag.
You are writing code at the client level, which means you do not know how the list is implemented.
BagInterface methods:
public boolean add(T newEntry)
public boolean isEmpty()
public boolean contains(T anObject)
public T remove()
public boolean remove(T anEntry)
public int getFrequencyOf(T anEntry)
public int getCurrentSize()
public void clear()
Explanation / Answer
import java.util.*;
public class Bag implements Bag {
private Object[] items;
private Integer numItems;
public static final Integer DEFAULT_MAX_SIZE = 50;
public Bag() {
items = new Object[DEFAULT_MAX_SIZE];
numItems = 0;
}
public Bag(Integer maxSize) {
if (maxSize <= 0)
throw new IllegalArgumentException("maxSize must be > 0");
items = new Object[maxSize];
numItems = 0;
}
public boolean add(Object item) {
if (item == null)
throw new IllegalArgumentException("item must be non-null");
if (numItems == items.length)
return false; // no more room!
else {
items[numItems] = item;
numItems++;
return true;
}
}
public boolean removeBag(Object item) {
for (Integer i = 0; i < numItems; i++) {
if (items[i] != null && items[i].equals(item)) {
System.arraycopy(items, i+1, items, i, numItems-i-1);
items[numItems-1] = null;
numItems--;
return true;
}
}
return false; // item not found
}
public boolean containsBag(Object item) {
for (Integer i = 0; i < numItems; i++) {
if (items[i] != null && items[i].equals(item))
return true;
}
return false;
}
public boolean containsAllBag(Bag otherBag) {
if (otherBag == null || otherBag.numItems() == 0)
return false;
Object[] otherItems = otherBag.toArray();
for (Integer i = 0; i < otherItems.length; i++) {
if (!contains(otherItems[i]))
return false;
}
return true;
}
public Integer numItems() {
return numItems;
}
public Object grab() {
if (numItems == 0)
throw new NoSuchElementException("the bag is empty");
Integer whichOne = (int)(Math.random() * numItems);
return items[whichOne];
}
public Object[] toArray() {
Object[] copy = new Object[numItems];
// no array copy!
System.arraycopy(items, 0, copy, 0, numItems);
return copy;
}
public Integer roomLeft() {
return items.length - numItems;
}
public Integer capacity() {
return items.length;
}
public boolean isEmpty() {
return (numItems == 0);
}
public boolean isFull() {
return (numItems == items.length);
}
public void increaseCapacityBag(Integer increment) {
//increment cannot be <0, throw exception
if(increment < 0) {
throw new IllegalArgumentException("increment cannot be < 0");
}
//increment ==0, nothing to be done
if(increment == 0){
return;
}
//increment >0, create new array, copy, etc..
else{
Object[] temp = new Object[items.length + increment];
// no array copy!
//System.arraycopy(items, 0, temp, 0, items.length);
for(Integer i=0; i<items.length; ++i){
temp[i] = items[i];
}
// copy pointer address
items = temp;
}
}
public boolean removeItemsBag(Bag otherBag){
// check input
if (otherBag == null || otherBag.numItems() == 0)
return false;
boolean removedSth = false;
Object[] otherItems = otherBag.toArray();
for (Integer i = 0; i < otherItems.length; i++) {
while (contains(otherItems[i])){
removedSth = remove(otherItems[i]);
}
}
return removedSth;
}
public Bag unionWithBag(Bag otherBag){
if (otherBag == null)
throw new IllegalArgumentException("No input bag");
// Create bag of size 1, which is the minimum size of a bag.
Bag unionBag = new ArrayBag(this.capacity() + otherBag.capacity());
// Go through all bags and add value if the "union bag" doesn't already contain it
// Go though current bag
Object[] otherItems = this.toArray();
for (Integer i = 0; i < otherItems.length; i++) {
if (!unionBag.contains(otherItems[i])){
unionBag.add(otherItems[i]);
}
}
// Go through other bag
otherItems = otherBag.toArray();
for (Integer i = 0; i < otherItems.length; i++) {
if (!unionBag.contains(otherItems[i])){
unionBag.add(otherItems[i]);
}
}
return unionBag;
}
public String toString() {
String str = "{";
for (Integer i = 0; i < numItems; i++)
str = str + " " + items[i];
str = str + " }";
return str;
}
public static void main(String[] args) {
// Create a Scanner object for user input.
Scanner in = new Scanner(System.in);
// Create an ArrayBag named bag1.
System.out.print("Size of bag 1:");
Integer size = in.nextInt();
Bag bag1 = new ArrayBag(size);
in.nextLine(); // consume the rest of the line
// Read in strings, add them to bag1, and print out bag1.
String itemStr;
for (Integer i = 0; i < size; i++) {
System.out.print("item " + i + ": ");
// should make sure we write sth
itemStr = in.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();
// test capacity
Integer capacity = bag1.capacity();
System.out.println("capacity: " + capacity);
// test isFull
Boolean isFull = bag1.isFull();
System.out.println("is full: " + isFull);
// increase capacity
System.out.print("increase capacity ");
// should make sure we write sth
Integer increment = in.nextInt();
bag1.increaseCapacity(increment);
// test capacity
capacity = bag1.capacity();
System.out.println("capacity: " + capacity);
// test isFull
isFull = bag1.isFull();
System.out.println("is full: " + isFull);
// remove item
// Create an ArrayBag named bag1.
System.out.print("Size of bag 2:");
size = in.nextInt();
Bag bag2 = new ArrayBag(size);
in.nextLine(); // consume the rest of the line
// Read in strings, add them to bag1, and print out bag1.
for (Integer i = 0; i < size; i++) {
System.out.print("item " + i + ": ");
// should make sure we write sth
itemStr = in.nextLine();
bag2.add(itemStr);
}
System.out.println("bag 2 = " + bag2);
System.out.println();
//
Boolean removed = bag1.removeItems(bag2);
System.out.println("removed items: " + removed);
System.out.println("bag 1 = " + bag1);
System.out.println();
// union with
Bag union = bag1.unionWith(bag2);
System.out.println("union = " + union);
System.out.println();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.