this is the book name. Data Structures and Abstractions with Java 1) Description
ID: 3663910 • Letter: T
Question
this is the book name. Data Structures and Abstractions with Java
1) Description: The sample programs in Chapter 1 of your textbook are not complete. They are used for illustration purpose only. The implementation of Listing 1-1 on page 39 is explained in Chapter 2. And, in order to see the result of using it, we will need the following set of files: i. BagInteface.java – the specification only. ii. ArrayBag.java – the implementation of BagInerface.java. iii. ArrayBagDemo.java – a sample program to show us how to use the Bag Interface. 2) Assignment: Download and run the above mentioned programs to ensure they work properly. Study the code and make necessary changes so that the program will run according to the following: i. Default capacity is 5. ii. When the current capacity is full, increment the capacity by 3 and resize the array accordingly. iii. There is no capacity limit.
i sent the above files which we need it .
here are the demo program
Array bag.java // these is the next file
Explanation / Answer
Answer:
Modifications to be done in BagInterface class:
To make the required modifications, the following changes need to be done as mentioned below:
Modifications to be done in ArrayBag class:
/**
* Gets the length of the array bag
*
* @return The length of the bag array
*/
public int getArrayBagSize()
{
return bag.length;
}
/**
* Expands the bag by 3 elements to the
* existing the bag capacity.
*/
private void resize()
{
bag = Arrays.copyOf(bag, bag.length + 3);
}
/**
* Creates an empty bag having a given capacity.
*
* @param desiredCapacity
* The integer capacity desired.
*/
public ArrayBag(int desiredCapacity)
{
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempBag = (T[]) new Object[desiredCapacity]; // Unchecked
// cast
bag = tempBag;
numberOfEntries = 0;
initialized = true;
} // end constructor
/**
* 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)
{
checkInitialization();
boolean result = true;
if (isArrayFull())
{
resize();
}
// Assertion: result is true here
bag[numberOfEntries] = newEntry;
numberOfEntries++;
return result;
} // end add
Modifications to be done in ArrayBagDemo class:
Program:
// BagInterface.java
/**
* 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);
/**
* Gets the array size of the bag.
* @return size of the bag array.
*/
public int getArrayBagSize();
} // end BagInterface
// ArrayBag.java
import java.util.Arrays;
/**
* A class of bags whose entries are stored in a fixed-size array.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
*/
public final class ArrayBag<T> implements BagInterface<T>
{
private T[] bag;
private int numberOfEntries;
private boolean initialized = false;
private static final int DEFAULT_CAPACITY = 5;
/** Creates an empty bag whose initial capacity is 25. */
public ArrayBag()
{
this(DEFAULT_CAPACITY);
} // end default constructor
/**
* Creates an empty bag having a given capacity.
*
* @param desiredCapacity
* The integer capacity desired.
*/
public ArrayBag(int desiredCapacity)
{
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempBag = (T[]) new Object[desiredCapacity]; // Unchecked
// cast
bag = tempBag;
numberOfEntries = 0;
initialized = true;
} // end constructor
/**
* 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)
{
checkInitialization();
boolean result = true;
if (isArrayFull())
{
resize();
}
// Assertion: result is true here
bag[numberOfEntries] = newEntry;
numberOfEntries++;
return result;
} // end add
/**
* Expands the bag by 3 elements to the
* existing the bag capacity. *
*/
private void resize()
{
bag = Arrays.copyOf(bag, bag.length + 3);
}
/**
* Gets the length of the array bag
*
* @return The length of the bag array
*/
public int getArrayBagSize()
{
return bag.length;
}
/**
* 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;
// Note: The body of this method could consist of one return
// statement,
// if you call Arrays.copyOf
} // 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
// Returns true if the array bag is full, or false if not.
private boolean isArrayFull()
{
return numberOfEntries >= bag.length;
} // end isArrayFull
// 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
// Throws an exception if this object is not initialized.
private void checkInitialization()
{
if (!initialized)
throw new SecurityException(
"ArrayBag object is not initialized properly.");
} // end checkInitialization
} // end ArrayBag
//ArrayBagDemo.java
/**
* A demonstration of the class ArrayBag
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
*/
public class ArrayBagDemo
{
public static void main(String[] args)
{
String[] contentsOfBag =
{ "A", "A", "B", "A", "C", "A" };
// Tests on an empty bag
BagInterface<String> aBag = new ArrayBag<String>(contentsOfBag.length);
// BagInterface<String> aBag = new ArrayBag<>();
System.out.println("Testing an initially empty bag:");
testIsEmpty(aBag, true);
String[] testStrings1 = { "", "B" };
testFrequency(aBag, testStrings1);
testContains(aBag, testStrings1);
testRemove(aBag, testStrings1);
// Adding strings
System.out.println("Adding " + contentsOfBag.length
+ " strings to an initially empty bag with"
+ " the capacity to hold more than " + contentsOfBag.length
+ " strings:");
testAdd(aBag, contentsOfBag);
// Tests on a bag that is not empty
testIsEmpty(aBag, false);
String[] testStrings2 = { "A", "B", "C", "D", "Z" };
testFrequency(aBag, testStrings2);
testContains(aBag, testStrings2);
// Removing strings
String[] testStrings3 = { "", "B", "A", "C", "Z" };
testRemove(aBag, testStrings3);
System.out.println(" Clearing the bag:");
aBag.clear();
testIsEmpty(aBag, true);
displayBag(aBag);
// Filling an initially empty bag to capacity
System.out.println(" Testing an initially empty bag that "
+ " will be filled to default capacity:");
aBag = new ArrayBag<String>();
String[] contentsOfBag2 = { "A", "B", "A", "C", "B" };
testAdd(aBag, contentsOfBag2);
System.out.println("Try to add another string to the full bag:");
if (aBag.add("another_string"))
System.out.println("Added another string by expanding the bag: OK");
displayBag(aBag);
System.out.println("Number of contents in the bag is: "
+ aBag.getCurrentSize());
System.out.println("Now the current size of the bag is: "
+ aBag.getArrayBagSize());
} // end main
// Tests the method add.
private static void testAdd(BagInterface<String> aBag, String[] content)
{
System.out.print("Adding ");
for (int index = 0; index < content.length; index++)
{
aBag.add(content[index]);
System.out.print(content[index] + " ");
} // end for
System.out.println();
displayBag(aBag);
} // end testAdd
// Tests the two remove methods.
private static void testRemove(BagInterface<String> aBag, 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 bag:");
String removedString = aBag.remove();
System.out.println("remove() returns " + removedString);
}
else
{
// test remove(aString)
System.out.println(" Removing "" + aString
+ "" from the bag:");
boolean result = aBag.remove(aString);
System.out.println("remove("" + aString + "") returns "
+ result);
} // end if
displayBag(aBag);
} // end for
} // end testRemove
// Tests the method isEmpty.
// correctResult indicates what isEmpty should return.
private static void testIsEmpty(BagInterface<String> aBag,
boolean correctResult)
{
System.out.print("Testing isEmpty with ");
if (correctResult)
System.out.println("an empty bag:");
else
System.out.println("a bag that is not empty:");
System.out.print("isEmpty finds the bag ");
if (correctResult && aBag.isEmpty())
System.out.println("empty: OK.");
else if (correctResult)
System.out.println("not empty, but it is empty: ERROR.");
else if (!correctResult && aBag.isEmpty())
System.out.println("empty, but it is not empty: ERROR.");
else
System.out.println("not empty: OK.");
System.out.println();
} // end testIsEmpty
// Tests the method getFrequencyOf.
private static void testFrequency(BagInterface<String> aBag, String[] tests)
{
System.out.println(" Testing the method getFrequencyOf:");
for (int index = 0; index < tests.length; index++)
{
String aString = tests[index];
if (!aString.equals("") && (aString != null))
{
System.out.println("In this bag, the count of "
+ tests[index] + " is "
+ aBag.getFrequencyOf(tests[index]));
} // end if
} // end for
} // end testFrequency
// Tests the method contains.
private static void testContains(BagInterface<String> aBag, String[] tests)
{
System.out.println(" Testing the method contains:");
for (int index = 0; index < tests.length; index++)
{
String aString = tests[index];
if (!aString.equals("") && (aString != null))
{
System.out.println("Does this bag contain " + tests[index]
+ "? " + aBag.contains(tests[index]));
} // end if
} // end for
} // end testContains
// Tests the method toArray while displaying the bag.
private static void displayBag(BagInterface<String> aBag)
{
System.out.println("The bag contains " + aBag.getCurrentSize()
+ " string(s), as follows:");
Object[] bagArray = aBag.toArray();
for (int index = 0; index < bagArray.length; index++)
{
System.out.print(bagArray[index] + " ");
} // end for
System.out.println();
} // end displayBag
} // end ArrayBagDemo
Sample Output: Here the highlighted code is the modified output.
Testing an initially empty bag:
Testing isEmpty with an empty bag:
isEmpty finds the bag empty: OK.
Testing the method getFrequencyOf:
In this bag, the count of B is 0
Testing the method contains:
Does this bag contain B? false
Removing a string from the bag:
remove() returns null
The bag contains 0 string(s), as follows:
Removing "B" from the bag:
remove("B") returns false
The bag contains 0 string(s), as follows:
Adding 6 strings to an initially empty bag with the capacity to hold more than 6 strings:
Adding A A B A C A
The bag contains 6 string(s), as follows:
A A B A C A
Testing isEmpty with a bag that is not empty:
isEmpty finds the bag not empty: OK.
Testing the method getFrequencyOf:
In this bag, the count of A is 4
In this bag, the count of B is 1
In this bag, the count of C is 1
In this bag, the count of D is 0
In this bag, the count of Z is 0
Testing the method contains:
Does this bag contain A? true
Does this bag contain B? true
Does this bag contain C? true
Does this bag contain D? false
Does this bag contain Z? false
Removing a string from the bag:
remove() returns A
The bag contains 5 string(s), as follows:
A A B A C
Removing "B" from the bag:
remove("B") returns true
The bag contains 4 string(s), as follows:
A A C A
Removing "A" from the bag:
remove("A") returns true
The bag contains 3 string(s), as follows:
A A C
Removing "C" from the bag:
remove("C") returns true
The bag contains 2 string(s), as follows:
A A
Removing "Z" from the bag:
remove("Z") returns false
The bag contains 2 string(s), as follows:
A A
Clearing the bag:
Testing isEmpty with an empty bag:
isEmpty finds the bag empty: OK.
The bag contains 0 string(s), as follows:
Testing an initially empty bag that will be filled to default capacity:
Adding A B A C B
The bag contains 5 string(s), as follows:
A B A C B
Try to add another string to the full bag:
Added another string by expanding the bag: OK
The bag contains 6 string(s), as follows:
A B A C B another_string
Number of contents in the bag is: 6
Now the current size of the bag is: 8
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.