Wielkość kolejka priorytetowa zwiększa się, gdy przedmioty nie porównywalne dodaje

Question

Rozważmy następujący kod:

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 

W ten kod to nieporównywalne obiekt jest najpierw dodawany do PriorityQueue. Ten kod działa dobrze, as already answered here.

Następnie do tej kolejki dodawany jest drugi obiekt. Zgodnie z oczekiwaniami na PriorityQueue.add Javadoc, ClassCastException jest generowany, ponieważ drugi obiekt nie jest porównywalny z pierwszym.

Wydaje się jednak, że wielkość kolejki została zwiększona chociaż wyjątek: druga wydruk wyjścia rachunku 2 zamiast 1.

Czy takie zachowanie powinno? Jeśli tak, to jaka jest tego przyczyna i gdzie jest udokumentowana?

Answer 1

Zgodnie z wydaniem GrepCode.com version of the source, wygląda na to, że może to być błąd w ich implementacji.

Wszystkie funkcje dodatek nie jest zadzwonić

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

Funkcja oferta wygląda następująco

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; 
} 

Zauważysz, że rozmiar = i + 1 jest wywoływana przed elementu jest właściwie włożona poprzez siftUp. Gdy wywoływana jest funkcja siftUp, pierwszą rzeczą, którą robi, jest próba rzutowania na Porównywalne i wyrzucenie wyjątku przed faktycznym wstawieniem elementu. Dlatego zwiększa rozmiar bez wstawiania elementu.

Answer 2

kod źródłowy offer (zwanego add) wykazuje nieprawidłowy stan, który występuje podczas mijania niebędącą Comparable obiektu do PriorityQueue które nie mają 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; 
} 

Wielkość jest modyfikowany przed siftUp nazywa. Metoda siftUp, zwykle odpowiedzialna za wstawienie elementu do kolejki, (ostatecznie) wyrzuca ClassCastException, ale rozmiar został już zmodyfikowany, co powoduje, że rozmiar jest niepoprawny.

Wygląda na to, że nie udokumentowano, że size zostanie zwiększony, nawet jeśli wystąpi ClassCastException. Prostą poprawką byłoby umieszczenie linii size = i + 1; po instrukcji if/else i before instrukcji return.