I'm currently learning different DataStructures in Java, one being Array Bags and Linked Bags. I understand the reason why data structures are so important and how generics allow us to more easily handle objects in a uniform way, no matter their type (if my thinking or understanding by that statement is wrong for the reason behind the use of Data Structures, please tell me).
With that said, there are some facets of generics and data structures that I'm not fully understanding. This thread is not mentioning those in particular as I will continue to look those things up separately, but it may have an impact on why I'm having problems properly implementing a method that will allow me to duplicate all items of a given bag.
Below is the code for a lab that I am working on. The lab asks that I complete certain methods in this file so that, when the driver is compiled and ran, the appropriate answers are returned to the command prompt. I believe that what I've done so far is correct when I run the driver. But when I try to complete the duplicateAll() method (second to last method in the file below), I continue to run into the same error(s) no matter how I try to change it. Please keep in mind, that my last method removeDuplicates() is not complete, but I'm not at that part yet of the lab.
Here is the code:
import java.util.Arrays;
import java.util.Random;
public final class ArrayBag<T> implements BagInterface<T> {
private final T[] bag;
private int numberOfEntries;
private static final int DEFAULT_CAPACITY = 25;
private boolean initialized = false;
private static final int MAX_CAPACITY = 10000;
/** Creates an empty bag whose initial capacity is 25. */
public ArrayBag() {
this(DEFAULT_CAPACITY);
} // end default constructor
/**
* Creates an empty bag having a given initial capacity.
*
* @param desiredCapacity The integer capacity desired.
*/
public ArrayBag(int desiredCapacity) {
if (desiredCapacity <= MAX_CAPACITY) {
// 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;
}
else
throw new IllegalStateException("Attempt to create a bag " +
"whose capacity exceeds " +
"allowed maximum.");
} // 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()) {
result = false;
} else { // Assertion: result is true here
bag[numberOfEntries] = newEntry;
numberOfEntries++;
} // end if
return result;
} // end add
/** Throws an exception if this object is not initialized.
*
*/
private void checkInitialization()
{
if (!initialized)
throw new SecurityException("ArrayBag object is not initialized " +
"properly.");
}
/** Retrieves all entries that are in this bag.
@return A newly allocated array of all the entries in the bag. */
public T[] toArray() {
// 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 full.
@return True if the bag is full, or false if not. */
private boolean isArrayFull() {
return numberOfEntries >= bag.length;
} // end isArrayFull
/** Sees whether this bag is empty.
@return True if the 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 the 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 the bag. */
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 the bag contains anEntry, or false if not. */
public boolean contains(T anEntry) {
checkInitialization();
return getIndexOf(anEntry) > -1;
} // 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 if otherwise. */
public T remove() {
checkInitialization();
// MODIFY THIS METHOD TO REMOVE A RANDOM ITEM FROM THE BAG
Random randomNum = new Random();
if(numberOfEntries > 0){
int randomKey = randomNum.nextInt(numberOfEntries);
T result = removeEntry(randomKey);
return result;
}else{
return null;
}
} // 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
// Removes and returns the entry at a given array index within the array bag.
// If no such entry exists, returns null.
// Preconditions: 0 <= givenIndex < numberOfEntries;
// checkInitialization has been called.
private T removeEntry(int givenIndex) {
T result = null;
if (!isEmpty() && (givenIndex >= 0)) {
result = bag[givenIndex]; // entry to remove
bag[givenIndex] = bag[numberOfEntries - 1]; // Replace entry with last entry
bag[numberOfEntries - 1] = null; // remove last entry
numberOfEntries--;
} // end if
return result;
} // end removeEntry
// 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 stillLooking = true;
int index = 0;
while ( stillLooking && (index < numberOfEntries)) {
if (anEntry.equals(bag[index])) {
stillLooking = false;
where = index;
} // end if
index++;
} // end for
// 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
/** Override the equals method so that we can tell if two bags contain the same items
* the contents in the bag.
* @return a string representation of the contents of the bag */
public String toString() {
String result = "Bag{Size:" + numberOfEntries + " ";
for (int index = 0; index < numberOfEntries; index++) {
result += "[" + bag[index] + "] ";
} // end for
result += "}";
return result;
} // end toArray
/*********************************************************************
*
* METHODS TO BE COMPLETED
*
*
************************************************************************/
/** Check to see if two bags are equals.
* @param aBag Another object to check this bag against.
* @return True the two bags contain the same objects with the same frequencies.
*/
public boolean equals(ArrayBag<T> aBag) {
boolean result = false; // result of comparison of bags
boolean sameLength = false;
T[] thisBag = this.toArray();
T[] otherBag = aBag.toArray();
Arrays.sort(thisBag);
Arrays.sort(otherBag);
if (thisBag.length == otherBag.length){
sameLength = true;
}
if(sameLength){
for(int index = 0; index < otherBag.length; index++)
{
if(thisBag[index].equals(otherBag[index])){
result = true;
}
}
}
return result;
} // end equals
/** Duplicate all the items in a bag.
* @return True if the duplication is possible.
*/
public boolean duplicateAll() {
checkInitialization();
boolean success = false;
T[] thisBag = this.toArray();
if(!thisBag.isEmpty()){
int originalTotalEntries = numberOfEntries;
for(int index = 0; index < originalTotalEntries; index++){
success = thisBag.add(thisBag[index]);
numberOfEntries++;
}
}
return success;
} // end duplicateAll
/** Remove all duplicate items from a bag
*/
public void removeDuplicates() {
checkInitialization();
// COMPLETE THIS METHOD
return;
} // end removeDuplicates
} // end ArrayBag
When I attempt to compile the code, I get the following errors:
./ArrayBag.java:260: error: cannot find symbol
if(!thisBag.isEmpty()){
^
symbol: method isEmpty()
location: variable thisBag of type T[]
where T is a type-variable:
T extends Object declared in class ArrayBag
./ArrayBag.java:263: error: cannot find symbol
success = thisBag.add(thisBag[index]);
^
symbol: method add(T)
location: variable thisBag of type T[]
where T is a type-variable:
T extends Object declared in class ArrayBag
2 errors
I've tried this. in place of thisBag like the following (only pasting the duplicateAll() method:
public boolean duplicateAll() {
checkInitialization();
boolean success = false;
T[] thisBag = this.toArray(); //not needed anymore
if(!this.isEmpty()){
int originalTotalEntries = this.numberOfEntries;
for(int index = 0; index < originalTotalEntries; index++){
success = this.add(this[index]);
numberOfEntries++;
}
}
return success;
} // end duplicateAll
And I get the following error at compile time:
./ArrayBag.java:263: error: array required, but ArrayBag<T> found
success = this.add(this[index]);
^
where T is a type-variable:
T extends Object declared in class ArrayBag
1 error
So I know that since I didn't cast this properly, I'm getting the error directly above. But the two errors posted above the last is where I'm getting hung up on.
My questions are:
Why am I receiving those errors? I've received similar errors concerning cannot find symbol in my last class of Java and that was when I believe I wasn't instantiating properly? I thought that my approach was correct because I casted T[] thisBag = this.toArray();, and then tried to use thisBag and the entries in the code within the method. Since this is wrong, I am unsure how to clear these with generics and ArrayBag/Bag DataStructures.
Also, am I approaching the duplication of entries in a generic bag appropriately or is there a better way that I'm unaware of? I'm trying to use the add() method within this file to my advantage but am obviously having difficulty. In looking at the documentation for Java's API online, I see that there may be a couple of routes I could take to achieve this duplication:
arrays.fill
arrays.setAll(T[] array, IntFunction<? extends T> generator)
arrays.clone
I'm thinking that I'd have to first make sure that there was enough fixed space in the array to duplicate it in memory. If not, I'd have to use a dynamic array and double the space and copy the contents twice into a new array. This is new to me and have not personally delved into this type of an approach (just learned the concept).
As always, I look forward to hearing how you all would approach a similar problem! And also tell me what I'm doing wrong!
ETA: ADDING THE ANSWER THAT WAS PROVIDED AND ANOTHER ISSUE EXPERIENCED WITH MY FIX
After @gar had suggested below, I implemented the following:
public boolean duplicateAll() {
checkInitialization();
boolean success = false;
T[] thisBag = this.toArray(); //not needed anymore
if(!this.isEmpty()){
int originalTotalEntries = this.numberOfEntries;
for(int index = 0; index < originalTotalEntries; index++){
success = this.add(thisBag[index]);
numberOfEntries++;
}
}
return success;
} // end duplicateAll
When I did this, I began to receive the following error:
Exception in thread "main" java.lang.NullPointerException
at java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:325)
at java.util.ComparableTimSort.sort(ComparableTimSort.java:188)
at java.util.Arrays.sort(Arrays.java:1246)
at ArrayBag.equals(ArrayBag.java:234)
at BagExtensionsTest.checkDuplicateAll(BagExtensionsTest.java:720)
at BagExtensionsTest.main(BagExtensionsTest.java:52)
I did some digging on this site and read that this is caused by null entries in arrays (hence the java.lang.NullPointerException. Added some System.out.println lines to see the changes in sizes to my arrays when duplicating them and noticed that the first array (which contained one entry) ended with three entries. I removed the numberOfEntries++; from the end of the duplicateAll() method and it corrected my problem.
Just thought that I would share that information for others to know.
As always, great information!
You're getting confused between methods on your object and the array. You seem to be pretty close on the second attempt you provided. The isEmpty method is on your ArrayBag class while the [...] accessor is only for arrays. Modifying your code snippet to get the entry to add from the array instead of the object, would look like:
public boolean duplicateAll() {
checkInitialization();
boolean success = false;
T[] thisBag = this.toArray(); //not needed anymore
if(!this.isEmpty()){
int originalTotalEntries = this.numberOfEntries;
for(int index = 0; index < originalTotalEntries; index++){
success = this.add(thisBag[index]);
numberOfEntries++;
}
}
return success;
} // end duplicateAll
I haven't tested this out, so it's possible there are other errors, but hopefully it gets you further along the path.