import java.util.Arrays; /** A class that implements a bag of objects by using a
ID: 3751437 • Letter: I
Question
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<T> implements BagInterface<T>
{
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
//BagInterface
/**
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<T>
{
/** 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.
@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> 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<T> union(BagInterface<T> anotherBag);
/** Creates a new bag that contains those objects that occur
in both this bag and anotherBag.
@param anotherBag The bag that is to be compared.
@return A combined bag. */
// public BagInterface<T> intersection(BagInterface<T> anotherBag);
/** Creates a new bag of objects that would be left in this bag
after removing those that also occur in anotherBag.
@param anotherBag The bag that is to be removed.
@return A combined bag. */
// public BagInterface<T> difference(BagInterface<T> anotherBag);
} // end BagInterface
//SetInterface
/**
An interface that describes the operations of a bag of objects.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.1
*/
public interface SetInterface<T>
{
public int getCurrentSize();
public boolean isEmpty();
/** Adds a new entry to this set, avoiding duplicates.
@param newEntry The object to be added as a new entry.
@return True if the addition is successful, or
false if the item is already in the set. */
public boolean add(T newEntry);
/** Removes a specific entry from this set, if possible.
@param anEntry The entry to be removed.
@return True if the removal was successful, or false if not. */
public boolean remove(T anEntry);
public T remove();
public void clear();
public boolean contains(T anEntry);
public T[] toArray();
} // end SetInterface
2. Define a class ArraySet that represents a set and implements the interface described in Segment 1.21 of the previous chapter. Use the class ResizableArrayBag in your implementation. Then write a program that adequately demonstrates your implementation.Explanation / Answer
TestArraySet.java
public class TestArraySet
{
public static void main(String[] args)
{
//create string array to test set
String[] contentsOfSet = {"A", "B", "C", "D", "E", "F"};
//Test on an empty set
SetInterface<String> aSet = new ArraySet<>(contentsOfSet.length);
System.out.println("Testing an initially empty bag:");
testIsEmpty(aSet, true);
//Test set if it contains item
String[] testString1 = {"C", "B"};
testContains(aSet, testString1);
//Test adding to set
String[] testString2 = {"A"};
System.out.println("Adding " + contentsOfSet.length + " strings to an initially " +
"empty set with the capacity to hold more than " +
contentsOfSet.length + " strings:");
testAdd(aSet, contentsOfSet);
//Test a filled set
testIsEmpty(aSet, false);
testContains(aSet, testString1);
//Remove strings from set
testRemove(aSet, testString1);
System.out.println("Testing to add duplicate string to set:");
testAdd(aSet, testString2);
//Add more strings to set
String[] testString3 = {"Y", "X", "Z"};
testAdd(aSet, testString3);
//Removing an entry from set
System.out.println("Removing an entry from set:");
aSet.remove();
displaySet(aSet);
//Clear set
System.out.println("Removing all strings from set:");
aSet.clear();
testIsEmpty(aSet, true);
displaySet(aSet);
} //end main
private static void testIsEmpty(SetInterface<String> aSet, boolean correctResult)
{
System.out.print("Testing isEmpty with ");
if (correctResult)
System.out.println("an empty set:");
else
System.out.println("a set that is not empty:");
System.out.print("isEmpty finds the set ");
if (correctResult && aSet.isEmpty())
System.out.println("empty: OK.");
else if (correctResult)
System.out.println("not empty, but it is empty: ERROR.");
else if (!correctResult && aSet.isEmpty())
System.out.println("empty, but it is not empty: ERROR.");
else
System.out.println("not empty: OK.");
System.out.println();
} //end testIsEmpty
private static void testContains(SetInterface<String> aSet, 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] +
"? " + aSet.contains(tests[index]));
} // end testContains
private static void testAdd(SetInterface<String> aSet, String[] content)
{
for (int index = 0; index < content.length; index++)
{
if(aSet.contains(content[index]))
{
System.out.println("Already in set, cannot add duplicates.");
} //end if
else
{
aSet.add(content[index]);
System.out.print("Adding ");
System.out.print(content[index] + " ");
} //end else
} // end for
System.out.println();
displaySet(aSet);
} //end testAdd
private static void testRemove(SetInterface<String> aSet, 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 set:");
String removedString = aSet.remove();
System.out.println("remove() returns " + removedString);
}
else
{
// test remove(aString)
System.out.println(" Removing "" + aString + "" from the set:");
boolean result = aSet.remove(aString);
System.out.println("remove("" + aString + "") returns " + result);
} // end if
displaySet(aSet);
} // end for
} // end testRemove
private static void displaySet(SetInterface<String> aSet)
{
System.out.println("The set contains " + aSet.getCurrentSize() +
" string(s), as follows:");
Object[] setArray = aSet.toArray();
for (int index = 0; index < setArray.length; index++)
{
System.out.print(setArray[index] + " ");
} // end for
System.out.println(" ");
} //end displaySet
}
ArraySet.java
public final class ArraySet<T> implements SetInterface<T>
{
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;
public ResizableArrayBag resizableArrayBag = new ResizableArrayBag(); //create object to be called
public ArraySet(ResizableArrayBag ResizeBag)
{
this.resizableArrayBag = resizableArrayBag;
} //end constructor
public ArraySet()
{
this(DEFAULT_CAPACITY);
} //end default constructor
public ArraySet(int initialCapacity)
{
T[] tempBag = (T[]) new Object[initialCapacity];
bag = tempBag;
numberOfEntries = 0;
initialized = true;
} //end constructor
public int getCurrentSize()
{
return resizableArrayBag.getCurrentSize();
}
//end getCurrentSize
public boolean isEmpty()
{
return resizableArrayBag.isEmpty();
} //end isEmpty
public boolean add(T newEntry)
{
if(!(contains(newEntry)))
{
resizableArrayBag.add(newEntry);
return false;
}
return true;
} //end add
public boolean remove(T anEntry)
{
return resizableArrayBag.remove(anEntry);
} //end remove
public T remove()
{
return (T) resizableArrayBag.remove();
} //end remove
public void clear()
{
resizableArrayBag.clear();
} //end clear
public boolean contains(T anEntry)
{
return resizableArrayBag.contains(anEntry);
} //end contains
public T[] toArray()
{
return (T[])resizableArrayBag.toArray();
} //end toArray
} //end ArraySet
SetInterface.java
public interface SetInterface<T>
{
public int getCurrentSize();
public boolean isEmpty();
/**Adds a new entry to this set, avoiding duplicates.
* @param newEntry The object to be added as a new entry.
* @return True if the addition is successful, or false if the item already is in the set */
public boolean add(T newEntry);
/**Removes a specific entry from this set, if possible.
* @param anEntry The entry to be removed.
* @return True if the removal was successful, or false if not. */
public boolean remove(T anEntry);
public T remove();
public void clear();
public boolean contains(T anEntry);
public T[] toArray();
} //end SetInterface
ResizableArrayBag.java
import java.util.Arrays;
public final class ResizableArrayBag<T> implements BagInterface<T>
{
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.
public 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
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.