PriorityQueue size increases when adding disparate objects

Question

Consider the following code:

import java.util.PriorityQueue; public class Test { public static void main(String argv[]) { PriorityQueue<A> queue = new PriorityQueue<>(); System.out.println("Size of queue is " + queue.size()); // prints 0 queue.add(new A()); // does not throw an exception try { queue.add(new A()); // this time, an exception is thrown } catch (ClassCastException ignored) { System.out.println("An exception was thrown"); } System.out.println("Size of queue is " + queue.size()); // prints 2 } } class A { } // non-comparable object 

In this code, an incompatible object is first added to the PriorityQueue . This code works great, as mentioned here .

Then a second object is added to this queue. As expected, for PriorityQueue.add Javadoc, a ClassCastException is ClassCastException because the second object is not comparable to the first.

However, it seems that the queue size has been increased, although an exception has been thrown: the second print statement prints 2 instead of 1.

Is this behavior expected? If so, what is the reason for this and where is it documented?

Answer 1

According to the GrepCode.com version of the source , it looks like this might be a mistake in their implementation.

The whole add function is a call

 public boolean add(E e) { return offer(e); } 

The offer function looks like this:

 public boolean offer(E e) { if (e == null) throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) grow(i + 1); size = i + 1; if (i == 0) queue[0] = e; else siftUp(i, e); return true; } 

You will notice that size = i + 1 is called before the element is actually inserted through siftUp. When siftUp is called, the very first thing it does is try to apply to Comparable and throw an exception before inserting the element. Therefore, it increases the size without actually inserting the element.

Answer 2

The source code of an offer (called add ) shows an invalid state that occurs when a non- Comparable object is transferred with a PriorityQueue that does not have a Comparator .

 public boolean More offer(E e) { if (e == null) throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) grow(i + 1); size = i + 1; if (i == 0) queue[0] = e; else siftUp(i, e); return true; } 

Size changes before siftUp is siftUp . The siftUp method, which is usually responsible for inserting an element into the queue, (in the end) throws a ClassCastException , but the size is already changed, which makes it the wrong size.

It does not appear to be documented that size will increase even if << 28> happens. A simple fix would be to put the string size = i + 1; after if / else and before the return statement.