Can a PriorityQueue implement Cloneable?

[cmacdonald]

We had a use-case to make a copy of a PriorityQueue. Short of serialization and deserialization, the option was to make a sub-class that could handle cloneing:

    static class MyObjectHeapPriorityQueue<K> extends ObjectHeapPriorityQueue<K> implements Cloneable {
		public MyObjectHeapPriorityQueue(int capacity, Comparator<? super K> c) {
			super(capacity, c);
		}

		public MyObjectHeapPriorityQueue(Comparator<? super K> c) {
			super(c);
		}

		public MyObjectHeapPriorityQueue() {
			super();
		}

		public MyObjectHeapPriorityQueue(int capacity) {
			super(capacity);
		}

		@Override
		@SuppressWarnings("unchecked")
		protected Object clone() throws CloneNotSupportedException {
			try{
				MyObjectHeapPriorityQueue<K> rtr = (MyObjectHeapPriorityQueue<K>)super.clone();
				rtr.heap = this.heap.clone();
				rtr.size = this.size;
				rtr.c = this.c; //a comparator should be stateless, no need to clone
				return rtr;
			} catch (CloneNotSupportedException e) {
				throw new InternalError(e.toString());
			}
		}
	}

[vigna]

Cloning is quite broken, but a pull request with a Cloneable implementation would be great :).

[incaseoftrouble]

If you only need some way to copy a collection and not something passing instanceof Cloneable, a copy-constructor is preferable I think. Java standard library does this, too.

public HeapPriorityQueue(HeapPriorityQueue<? super K> queue) {
  // do copy here
}

PS: When you mask exceptions, be sure to pass the original exception to preserve the stack trace! e.toString() often is non-informative.

[vigna]

Yeah, you're right. A copy constructor is a better idea. Though many fastutil classes actually implement clone().

[cmacdonald]

thats fair @incaseoftrouble - my work in progress for the PR for Cloneable is at
master...cmacdonald:patch-1

Final decision?

[cmacdonald]

The point is that we don't want to reconstruct the queue by re-inserting every item - a copy of the (e.g.) heap is sufficient. Can the constructor be engineered in such a fashion?

[incaseoftrouble]

I think something like the following should work, with little modification to the code. Basically you take your clone() implementation and put it in the constructor. I strongly suggest following the approach of the standard library.

public MyHeapPriorityQueue(Collection<? super K> elements) {
  if (queue instanceof MyHeapPriorityQueue) {
    MyHeapPriorityQueue other = (MyHeapPriorityQueue) queue;
    this.heap = new CollectionImplementingTheHeap(other.heap); // or other.heap.clone() if necessary
    this.comparator = other.comparator; // etc.
  } else if (elements instanceof SortedSet) {
    this.heap = new CollectionImplementingTheHeap();
    this.comparator = elements.comparator
    addAll(queue);
  } else {
    // addAll()
  }
}

EDIT: Or what @vigna said. He's the maintainer, after all ;)

[vigna]

So, following the fastutil custom implementations can be Cloneable. Interfaces don't. So you should make (for coherence) the five implementation of PriorityQueue Cloneable, implement clone() and add some unit test for each clone() method.

Also, super.clone() will do shallow copying, so you just need to clone the backing array—the rest will be done for you.

[cmacdonald]

I gave a look at this:

• For the indirect queue, I wasn't sure if the inv[] array needs to be cloned (its final).

• If the Interface PriorityQueue isn't cloneable, I have would have to check and cast which implementation an object is before cloning.

• Making a SynchronizedPriorityQueue of a queue is also difficult.

• If I do put it in the interface, this means that the type-specific PriorityQueue clone() should return their type, e.g. CharPriorityQueue instead, and this means separate #ifdef branches for the definition of clone() in PriorityQueue.drv etc. Its not pretty...

I'm beginning to favour trying instead the constructor suggestion of @incaseoftrouble - however, note that a fastutils PriorityQueue doesn't extend Collection, so the constructor would look like:

public HeapPriorityQueue(PriorityQueue<? super K> q) {
  if (! q instanceof HeapPriorityQueue) throw IllegalArgumentException();
  this.size = q.size;
  this.heap = q.heap.clone();
 //etc
}

[incaseoftrouble]

• For the indirect queue, I wasn't sure if the inv[] array needs to be cloned (its final).

Depends on whether you want a shallow or deep copy.

• If the Interface PriorityQueue isn't cloneable, I have would have to check and cast which implementation an object is before cloning.

True. But this can be moved to a static utility class.

• Making a SynchronizedPriorityQueue of a queue is also difficult.

Why? This can be done via wrapping, right? Or do you mean copying a SynchronizedQueue?

• If I do put it in the interface...

Cloning should not be put in the interface I think, simply for consistency.

• fastutils PriorityQueue doesn't extend Collection

That's fine. I think the constructor should also work with different PriorityQueues, simply calling addAll().

[vigna]

@cmacdonald:

• Yes, you have to clone inv[].
• The problem with making interfaces cloneable is that you force all implementations to be cloneable. There might be implementation for which cloning is simply impossible. If you need really that, just create an interface that extends PriorityQueue and Cloneable.
• I don't see why synchronizing a PriorityQueue should be difficult.
• Java supports covariant return-type overriding. You can override a method with another one that returns a more specific type.

[Speiger]

@vigna wouldn't #168 fix that issue since you can use toarray and the array constructors?