Java: a comparator always return 1 doesn't make a priority queue into a queue? [duplicate]

Question

Possible Duplicate:
Java: strange order of queue made from priority queue

I tired to turn a priority queue into a queue by implementing the following comparator:

• Hack: The QueueComparator makes a PriorityQueue behaves like queue (FIFO) by always return 1
• Since the "natural ordering" of a priority queue has the least element at the head and a conventional comparator returns -1 when the first is less than the second, the hacked comparator always return 1 so that the current (last) square will be placed at the tail (recursively)

Here is the code:

import java.util.Comparator;
public class QueueComparator implements Comparator<Square>{
    public int compare(Square square1, Square square2)
    {
        return 1;
    }
}

But the resulting "queue" does not keep things in order(FIFO). Why?

Answer 1

The question is why should it?

First your Comparator is completely broken, since it violates the basic constraint that

sign(compare(a,b)) = - sign(compare(b,a))

and

compare(a,a) == 0

So anything using it might come up with all kinds of results like loosing entries, running in an endless loop, throwing a stackoverflow ...

If you want to implement a IDontGiveAShitComparator it should return 0 all the time. Everything depending on a Comparator should be able to handle that.

What order results is still up to the implementation. If it stores elements in a list FIFO or LIFO are kind of probable, If it stores in a balanced tree, it will probably add elements always on one side, causing rebalancing of the tree, which will pretty much mix everything up.

Maybe it uses something based on hashes, in which case all elements with the same priority might come out ordered by their hash values.

Answer 2

Well, it's a hack. So if it's not working, I wouldn't be too surprised.

The Javadoc of PriorityQueue says:

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily.

Well, there you have it. If your comparator returns the same value for all pairs of elements, you have nothing but ties. So the queue order is indeed arbitrary.