clone() method implementation in PriorityQueue

Question

For my data structures class our assignment is to implement a PriorityQueue class that uses an already created array based queue. Everything is working in the PriorityQueue class except for the clone method. When the clone method is activated nothing is returned even though there is data in the queue that is being cloned. The PriorityQueue class uses an array of ArrayQueues. I just copied the constructor and clone method from my class.

Thanks for the help

private ArrayQueue<E>[] queues;
private int manyItems;
private int highest;

public PriorityQueueArray(int a_highest) {
    manyItems = 0;
    highest = a_highest;
    queues = new ArrayQueue[a_highest+1];
    for(int i = 0; i <= a_highest; i++) {
        queues[i] = new ArrayQueue();
    }
}

public PriorityQueueArray<E> clone() {
    PriorityQueueArray<E> answer;

    try{
        answer = (PriorityQueueArray<E>) 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
        // 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");         
    }
    for(int i = 0; i <= highest; i++) {
        answer.queues[i] = queues[i].clone();
    }   
    return answer;
}

Answer 1

I think that the problem is that queues is not being cloned properly. Try this:

public PriorityQueueArray<E> clone() {
    PriorityQueueArray<E> answer;
    answer.manyItems = manyItems;
    answer.highest = highest;
    answer.queues = new ArrayQueue<E>[queues.length]; // This is the key!
    for (int i = 0; i <= highest; i++) {
        answer.queues[i] = queues[i].clone();
    }   
    return answer;
}

Your original code relies on super.clone() to do a lot of the work, but the default version of that method does a shallow clone, and that doesn't make a copy of the queues array. So you end up with a "clone" that shares its queue array with the original. That will mean that the ArrayQueue instances will be shared, and strange things will happen ...

(Given that we need to manually new the queues array, it simplest to manually copy the other 2 fields as well.)

We'd need to see your unit test to figure out how / why this results in the symptoms you are seeing.