Subtypes of `PriorityQueue` violate its specification

[mernst]

The specification of PriorityQueue states "Elements that are smaller in the specified order are dequeued first." A FIFO queue violates this contract, so it is not a behavioral subtype of a priority queue.

In fastutil, IntArrayFIFOQueue implements PriorityQueue, which violates behavioral subtyping and leads to buggy behavior in clients. I think that the right fix is to change all FIFO queues (in ArrayFIFOQueue.drv) to not implement PriorityQueue.

This Java program illustrates the problem:

import it.unimi.dsi.fastutil.ints.IntArrayFIFOQueue;
import it.unimi.dsi.fastutil.ints.IntArrayPriorityQueue;
import it.unimi.dsi.fastutil.ints.IntPriorityQueue;

public class PriorityQueueTest {

  public static void main(String[] args) {
    testPriorityQueue(new IntArrayPriorityQueue());
    testPriorityQueue(new IntArrayFIFOQueue());
  }

  static void testPriorityQueue(IntPriorityQueue pq) {
    pq.clear();
    pq.enqueue(2);
    pq.enqueue(1);
    int i = pq.dequeueInt();
    System.out.println(pq.getClass() + " " + (i == 1 ? "OK" : "FAILED") + " dequeue returned " + i);
  }
}

To run it, execute these commands:

wget -O fastutil-core-8.5.4.jar https://search.maven.org/remotecontent?filepath=it/unimi/dsi/fastutil-core/8.5.4/fastutil-core-8.5.4.jar
javac -cp fastutil-core-8.5.4.jar PriorityQueueTest.java
java -cp .:fastutil-core-8.5.4.jar PriorityQueueTest

The program outputs

class it.unimi.dsi.fastutil.ints.IntArrayPriorityQueue OK dequeue returned 1
class it.unimi.dsi.fastutil.ints.IntArrayFIFOQueue FAILED dequeue returned 2

Also, I noticed that the tests IntArrayPriorityQueueTest.java and IntHeapPriorityQueueTest.java always enqueue and dequeue values in the same order. This does not test the priority queue functionality. It might be good to expand these tests.

[vigna]

The specification of PriorityQueue states "Elements that are smaller in the specified order are dequeued first." A FIFO queue violates this contract, so it is not a behavioral subtype of a priority queue.

No, it doesn't. Why it is so?

[mernst]

The given test case shows an example: 1 is smaller, but there exists a PriorityQueue such that 1 is not dequeued first.

[vigna]

I think you are very confused about the notion of "specified order". A FIFO queue has only one possible order—insertion order. That's the priority order. The nature of the elements is irrelevant. This is algorithm 101.

[mernst]

As the term is used by computer scientists, a priority queue's order depends on the values, never on the order of insertion. This definition is consistent with the JDK, Wikipedia, and every algorithms and data structures textbook I know of. Do you know of a reputable text that says otherwise?

In a regular queue, the order depends on the order of insertion.

I agree that it is a bit confusing that queues and priority queues are unrelated data structures, but that is the standard terminology.

Perhaps fastutil uses the term "priority queue" differently than the rest of the field. That is fine, but if so, I think it would be helpful for the documentation to highlight that fact. As currently written, the naming is confusing for someone who expects standard terminology.

[vigna]

I think you should read the Wikipedia entry, rather than just quote it 🤷🏻‍♂️...