Java: comparator always returns 1, doesn't priority queue queue?

Question

Possible duplicate:
Java: weird queue order from priority queue

I'm tired of turning a priority queue into a queue by implementing the following comparator:

• Hack: QueueComparator makes PriorityQueue behaves like a queue (FIFO), always return 1
• Since the "natural order" of the priority queue has the smallest element in the head, and the usual comparator returns -1 when the first is less than the second, the hacked comparator always returns 1 so that the current (last) square is placed on 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 order (FIFO). Why?

Answer 1

The question is, why should it be?

First, your Comparator is completely broken, as it violates the main restriction, which

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

and

 compare(a,a) == 0 

So, everything that can be used can bring all kinds of results, such as losing records, starting in an endless loop, resetting stackoverflow ...

If you want to implement IDontGiveAShitComparator , it must return 0 all the time. Everything that depends on the comparator should be able to handle this.

What order results are still consistent with implementation. If it stores items in a FIFO or LIFO list, they are likely. If it is stored in a balanced tree, it will probably add elements always on one side, which will lead to a rebalancing of the tree, which will largely lead to a mixture of everything.

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

Answer 2

Well, it's a hack. Therefore, if it does not work, I would not be too surprised.

Javadoc PriorityQueue says:

The head of this queue is the smallest element relative to the specified order. If several elements are attached to the smallest value, the head is one of these elements - the bindings are broken arbitrarily .

Ok, there you have it. If your comparator returns the same value for all pairs of elements, you have nothing but links. Thus, the order of the queues is really arbitrary.

Answer 3

compareTo(a,b) should generally return -compare(b,a) , and compareTo(a,a) should return zero. Your comparator violates both of these rules.

Check out the Javadoc .

Answer 4

The general implementation for the priority queue is done using the Binary Heap (like the default Java implementation). The comparator is used only to save the heap properties (a node is always greater than / equal (or less / equal) for all its children) true. If the comparator will always return 1, the behavior of PriotityQueue may lead to unexpected behavior when trying to restore the heap property after insertion, but will not end in the FIFO queue.

Remember that there is no real tail in BinaryHeap because it is organized like a tree. The elements that should be the last are the nodes of the sheet, but not "at the end."