Hello Sir or Ma\'am, First and foremost, I want to thank you very much for your

Question

Hello Sir or Ma'am,

First and foremost, I want to thank you very much for your help! I so deeply appreciate it!

-----------------------------------------------------------

Write and demonstrate the operation of an extended class that has all the operations of the Bag class. Use Java's Vector as the superclass. If this may help, I have provided the ArrayBag class below. Again, thank you very much.

------------------------------------------------------------

public class ArrayBag implements Cloneable
{
// Invariant of the ArrayBag class:
// 1. The number of elements in the bag is in the instance variable manyItems.
// 2. For an empty bag, we do not care what is stored in any of data;
// for a non-empty bag, the elements in the bag are stored in data[0]
// through data[manyItems-1], and we don’t care what’s in the rest of data.
private Object[ ] data;
private int manyItems;

/**
* Initialize an empty bag with an initial capacity of 10. Note that the
* <CODE>add</CODE> method works efficiently (without needing more
* memory) until this capacity is reached.
* @param - none
* <dt><b>Postcondition:</b><dd>
* This bag is empty and has an initial capacity of 10.
* @exception OutOfMemoryError
* Indicates insufficient memory for:
* <BR><CODE>new Object[10]</CODE>.
**/
public ArrayBag( )
{
final int INITIAL_CAPACITY = 10;
manyItems = 0;
data = new Object[INITIAL_CAPACITY];
}

/**
* Initialize an empty bag with a specified initial capacity. Note that the
* <CODE>add</CODE> method works efficiently (without needing more
* memory) until this capacity is reached.
* @param <CODE>initialCapacity</CODE>
* the initial capacity of this bag
* <dt><b>Precondition:</b><dd>
* <CODE>initialCapacity</CODE> is non-negative.
* <dt><b>Postcondition:</b><dd>
* This bag is empty and has the given initial capacity.
* @exception IllegalArgumentException
* Indicates that initialCapacity is negative.
* @exception OutOfMemoryError
* Indicates insufficient memory for:
* <BR><CODE>new Object[initialCapacity]</CODE>.
**/
public ArrayBag(int initialCapacity)
{
if (initialCapacity < 0)
throw new IllegalArgumentException
("The initialCapacity is negative: " + initialCapacity);
data = new Object[initialCapacity];
manyItems = 0;
}


/**
* Put a reference to an object into this bag. If the addition
* would take this bag beyond its current capacity, then the capacity is
* increased before adding the new element. The new element may be the null
* reference.
* @param <CODE>element</CODE>
* the element to be added to this bag
* <dt><b>Postcondition:</b><dd>
* The element has been added to this bag.
* @exception OutOfMemoryError
* Indicates insufficient memory for increasing the bag's capacity.
* <dt><b>Note:</b><dd>
* An attempt to increase the capacity beyond
* <CODE>Integer.MAX_VALUE</CODE> will cause the bag to fail with an
* arithmetic overflow.
**/
public void add(Object element)
{
if (manyItems == data.length)
{
// Double the capacity and add 1; this works even if manyItems is 0.
// However, in the case that manyItems*2 + 1 is beyond
// Integer.MAX_VALUE, there will be an arithmetic overflow and
// the bag will fail.
ensureCapacity(manyItems*2 + 1);
}

data[manyItems] = element;
manyItems++;
}


/**
* Add the contents of another bag to this bag.
* @param <CODE>addend</CODE>
* a bag whose contents will be added to this bag
* <dt><b>Precondition:</b><dd>
* The parameter, <CODE>addend</CODE>, is not null.
* <dt><b>Postcondition:</b><dd>
* The elements from <CODE>addend</CODE> have been added to this bag.
* @exception NullPointerException
* Indicates that <CODE>addend</CODE> is null.
* @exception OutOfMemoryError
* Indicates insufficient memory to increase the size of this bag.
* <dt><b>Note:</b><dd>
* An attempt to increase the capacity beyond
* <CODE>Integer.MAX_VALUE</CODE> will cause an arithmetic overflow
* that will cause the bag to fail. Such large collections should use
* a different bag implementation.
**/
public void addAll(ArrayBag addend)
{
// If addend is null, then a NullPointerException is thrown.
// In the case that the total number of elements is beyond
// Integer.MAX_VALUE, there will be an arithmetic overflow and
// the bag will fail.
ensureCapacity(manyItems + addend.manyItems);

System.arraycopy(addend.data, 0, data, manyItems, addend.manyItems);
manyItems += addend.manyItems;
}


/**
* Generate a copy of this bag.
* @param - none
* @return
* The return value is a copy of this bag. Subsequent changes to the
* copy will not affect the original, nor vice versa. Note that the return
* value must be type cast to an <CODE>ArrayBag</CODE> before it can be used.
* @exception OutOfMemoryError
* Indicates insufficient memory for creating the clone.
**/
public Object clone( )
{ // Clone an ArrayBag object.
ArrayBag answer;

try
{
answer = (ArrayBag) super.clone( );
}
catch (CloneNotSupportedException e)
{
// This exception should not occur. But if it does, it would probably
// indicate a programming error that made super.clone unavailable.
// The most common error would be forgetting the "Implements Cloneable"
// clause at the start of this class.
throw new RuntimeException
("This class does not implement Cloneable");
}

answer.data = (Object [ ]) data.clone( );

return answer;
}


/**
* Accessor method to count the number of occurrences of a particular element
* in this bag.
* @param <CODE>target</CODE>
* an element to be counted
* @return
* The return value is the number of times that <CODE>target</CODE> occurs
* in this bag. If <CODE>target</CODE> is non-null, then the occurrences
* are found using the <CODE>target.equals</CODE> method.
**/
public int countOccurrences(Object target)
{
int answer;
int index;

answer = 0;
if (target == null)
{ // Count how many times null appears in the bag.
for (index = 0; index < manyItems; index++)
if (data[index] == null)
answer++;
}
else
{ // Use target.equals to determine how many times the target appears.
for (index = 0; index < manyItems; index++)
if (target.equals(data[index]))
answer++;
}

return answer;
}


/**
* Change the current capacity of this bag.
* @param <CODE>minimumCapacity</CODE>
* the new capacity for this bag
* <dt><b>Postcondition:</b><dd>
* This bag's capacity has been changed to at least <CODE>minimumCapacity</CODE>.
* If the capacity was already at or greater than <CODE>minimumCapacity</CODE>,
* then the capacity is left unchanged.
* @exception OutOfMemoryError
* Indicates insufficient memory for: <CODE>new Object[minimumCapacity]</CODE>.
**/
public void ensureCapacity(int minimumCapacity)
{
Object biggerArray[ ];

if (data.length < minimumCapacity)
{
biggerArray = new Object[minimumCapacity];
System.arraycopy(data, 0, biggerArray, 0, manyItems);
data = biggerArray;
}
}


/**
* Accessor method to get the current capacity of this bag.
* The <CODE>add</CODE> method works efficiently (without needing
* more memory) until this capacity is reached.
* @param - none
* @return
* the current capacity of this bag
**/
public int getCapacity( )
{
return data.length;
}


/**
* Accessor method to retrieve a random element from this bag.
* @param - none
* <dt><b>Precondition:</b><dd>
* This bag is not empty.
* @return
* a randomly selected element from this bag
* @exception IllegalStateException
* Indicates that the bag is empty.
**/
public Object grab( )
{
int i;

if (manyItems == 0)
throw new IllegalStateException("Bag size is zero");

i = (int)(Math.random( ) * manyItems); // In range of 0 to manyItems-1
return data[i];
}


/**
* Remove one copy of a specified element from this bag.
* @param <CODE>target</CODE>
* an element to remove from the bag
* <dt><b>Postcondition:</b><dd>
* If <CODE>target</CODE> was found in the bag, then one copy of
* <CODE>target</CODE> has been removed and the method returns true.
* Otherwise the bag remains unchanged and the method returns false.
* Note that if <CODE>target</CODE> is non-null, then
* <CODE>target.equals</CODE> is used to find
* <CODE>target</CODE> in the bag.
**/
public boolean remove(Object target)
{
int index; // The location of target in the data array.

// First, set index to the location of target in the data array,
// which could be as small as 0 or as large as manyItems-1; If target
// is not in the array, then index will be set equal to manyItems;
if (target == null)
{ // Find the first occurrence of the null reference in the bag.
for (index = 0; (index < manyItems) && (data[index] != null); index++)
// No work is needed in the body of this for-loop.
;
}
else
{ // Use target.equals to find the first occurrence of the target.
for (index = 0; (index < manyItems) && (!target.equals(data[index])); index++)
// No work is needed in the body of this for-loop.
;
}

if (index == manyItems)
// The target was not found, so nothing is removed.
return false;
else
{ // The target was found at data[index].
// So reduce manyItems by 1 and copy the last element onto data[index].
manyItems--;
data[index] = data[manyItems];
return true;
}
}


/**
* Determine the number of elements in this bag.
* @param - none
* @return
* the number of elements in this bag
**/
public int size( )
{
return manyItems;
}


/**
* Reduce the current capacity of this bag to its actual size (i.e., the
* number of elements it contains).
* @param - none
* <dt><b>Postcondition:</b><dd>
* This bag's capacity has been changed to its current size.
* @exception OutOfMemoryError
* Indicates insufficient memory for altering the capacity.
**/
public void trimToSize( )
{
Object trimmedArray[ ];

if (data.length != manyItems)
{
trimmedArray = new Object[manyItems];
System.arraycopy(data, 0, trimmedArray, 0, manyItems);
data = trimmedArray;
}
}


/**
* Create a new bag that contains all the elements from two other bags.
* @param <CODE>b1</CODE>
* the first of two bags
* @param <CODE>b2</CODE>
* the second of two bags
* <dt><b>Precondition:</b><dd>
* Neither b1 nor b2 is null, and
* <CODE>b1.getCapacity( ) + b2.getCapacity( ) &lt;= Integer.MAX_VALUE</CODE>.
* @return
* the union of b1 and b2
* @exception NullPointerException
* Indicates that one of the arguments is null.
* @exception OutOfMemoryError
* Indicates insufficient memory for the new bag.
* An attempt to create a bag with a capacity beyond
* <CODE>Integer.MAX_VALUE</CODE> will cause an arithmetic overflow
* that will cause the bag to fail. Such large collections should use
* a different bag implementation.
**/
public static ArrayBag union(ArrayBag b1, ArrayBag b2)
{
// If either b1 or b2 is null, then a NullPointerException is thrown.
// In the case that the total number of elements is beyond
// Integer.MAX_VALUE, there will be an arithmetic overflow and
// the bag will fail.
ArrayBag answer = new ArrayBag(b1.getCapacity( ) + b2.getCapacity( ));

System.arraycopy(b1.data, 0, answer.data, 0, b1.manyItems);
System.arraycopy(b2.data, 0, answer.data, b1.manyItems, b2.manyItems);
answer.manyItems = b1.manyItems + b2.manyItems;

return answer;
}

}

Explanation / Answer

import java.io.Serializable;

import java.util.ArrayList;

import java.util.Collection;

import java.util.Collections;

import java.util.Iterator;

public class ArrayBag<T extends Comparable<? super T>> implements

Collection<T>, Serializable {

private static final long serialVersionUID = -5826185174214376115L;

protected ArrayList<T> arr = new ArrayList<T>();

private boolean modified;

public int size() {

return arr.size();

}

public boolean isEmpty() {

return arr.isEmpty();

}

public boolean contains(Object o) {

return arr.contains(o);

}

public Iterator<T> iterator() {

return new ArrayList<T>(arr).iterator();

}

public boolean containsAll(Collection<?> c) {

return arr.containsAll(c);

}

public Object clone() {

return arr.clone();

}

public Object[] toArray() {

return arr.toArray();

}

@SuppressWarnings("hiding")

public <T> T[] toArray(T[] a) {

return arr.toArray(a);

}

public boolean removeAll(Collection<?> c) {

modified = true;

return arr.removeAll(c);

}

public boolean retainAll(Collection<?> c) {

modified = true;

return arr.retainAll(c);

}

public boolean add(T e) {

modified = true;

return arr.add(e);

}

public boolean remove(Object o) {

modified = true;

return arr.remove(o);

}

public void clear() {

modified = true;

arr.clear();

}

public boolean addAll(Collection<? extends T> c) {

modified = true;

return arr.addAll(c);

}

@Override

public int hashCode() {

final int prime = 31;

int result = 1;

result = prime * result + ((arr == null) ? 0 : arr.hashCode());

return result;

}

@SuppressWarnings({"rawtypes","unchecked"})

@Override

public boolean equals(Object obj) {

if (this == obj)

return true;

if (obj == null)

return false;

if (getClass() != obj.getClass())

return false;

ArrayBag<T> other = (ArrayBag) obj;

if (arr == null) {

if (other.arr != null)

return false;

} else {

this .refresh();

other.refresh();

if (!arr.equals(other.arr))

return false;

}

return true;

}

public String toString() {

refresh();

return arr.toString();

}

private void refresh() {

if (arr.size() > 0 && modified) {

Collections.sort(arr);

modified = false;

}

}

}

or

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.