compareTo and equals in PriorityQueues

i'm a little confused with all the "If the ordering imposed by c on S is inconsistent with equals, the sorted set (or sorted map) will behave strangely." warnings in the Javadoc. I'm not even sure anymore a PriorityQueue is what i need...

My situation is this: I have a class Event with an integer timestamp and some other fields. I'm looking for a datastructure, in which I can insert these events and which sorts the events by timestamp. Different events can have the same timestamp, so - if I understand correctly - compareTo and equals would be inconsistent.

My first approach was to let the Event implement Comparable and provide compareTo like this: public int compareTo(Event e) { return this.timestamp - e.getTimestamp(); }

I don't understand how I'm supposed to solve this. I thought about creating a custom Comparator, but the same warning about strange behaviour pops up in the Comparator's javadoc as well. I don' want to insert multiple equal instances of an event, i just want them to be sorted by timestamp.

Thanks in advance for your 开发者_StackOverflowhelp :)

Edit:

I just want the Events to be sorted by timestamp. It could very well be, that two different events have the same timestamp. So compareTo would return 0, because they have the same timestamp and are equal for the purpose of sorting. But equals() would not return true, because they are different events.

I'm not sure, a PriorityQueue is the right thing to use. I looked at SortedSet, but it had the same warnings about the consistency of compareTo and equals.

Maybe I'm tackling this from the wrong angle, I don't know...

Different events can have the same timestamp

and which sorts the events by timestamp

That latter requirement is somewhat unclear. Should the Collection's iterator return instances in sorted order? Or should the collection, if you poll() in a loop, return its former contents in sorted order?

iterator() returns elements in order

That wouldn't be the case for a PriorityQueue. You could use a SortedSet, but those require the sort order to be consistent with equals, which, as you note correctly, you can't achieve. As far as I know, there is no Collection in the JDK that would keep its elements in sorted order for a sort order that considers some elements equal. However, you could use an array or ArrayList, and sort it manually after changes using Arrays.sort or Collection.sort. If the collection changes rarely, this is the approach I'd choose. If it changes frequently, you'll have to look beyond the JDK or implement the data structure yourself.

poll() returns elements in sorted order

That's what a priority queue is good for. A PriorityQueue does not require the Comparator (or implementation of Comparable) to be consistent with equals; its JavaDoc clearly writes:

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.

Moreover, the implementation of PriorityQueue in JDK 6 uses equals only to implement indexOf(E), contains(Object) and remove(Object), neither of which use the comparator in any way. So there really isn't a way consistency with equals could matter for this Collection.

Comparable vs. Comparator

Note that it doesn't matter whether you implement Comparable or Comparator as far as consistency with equals is concerned. For a SortedSet, either must be consistent with equals, for a PriorityQueue, Collection.sort or Arrays.sort, neither has to be.

TreeSet and consistency with equals

Lifted from the comments:

TreeSet is a SortedSet and explicitly states to only rely on compareTo/compare. It says explicit: "The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface."

If you quote, please quote all relevant parts. The full paragraph reads:

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. [...] This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

So yes it is well-defined, but it doesn't do what the question calls for: If you pass TreeSet.add an Event with the same timestamp as another Event in the set, the new Event will be considered a duplicate and not added, even though the Events are not equal. The question asks about sorting a Collection; that should not eliminate Events that duplicate a sort key, should it?

If the ordering imposed by c on S is inconsistent with equals, the sorted set (or sorted map) will behave strangely.

That just means that if and only if e1.equals(e2) then e1.compareTo(e2) == 0.

And if and only if !e1.equals(e2) then e1.compareTo(e2) != 0.

That is what you have to do to make both methods consistent.

So by the way you implement compareTo you should also override equals() as:

@Override
public boolean equals(Event e) {
    return this.timestamp.equals(e.timestamp);
}

Note: I don't know timestamp's data type, but if it is a primitive type, use == instead of equals() for the overriden method.

When you implement Comparable then you should also override equals(Object), because compareTo should only return zero if and only if equals return true.

compareTo(T) should only return zero if and only if equals(Object) return true.

And that's not all. Due to another contract you should/must override hashCode() when you override equals.

Equal objects must have equal hashcodes.

public class Event implements Comparable<Event> {

    private long timestamp;

    public long getTimestamp() {
        return this.timestamp;
    }

    @Override
    public int compareTo(Event o) {
        return (this.timestamp < o.timestamp ? -1
                : (this.timestamp == o.timestamp ? 0 : 1));
    }

    @Override
    public int hashCode() {
        return (int) (this.timestamp ^ (this.timestamp >>> 32));
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Event) {
            return this.timestamp == ((Event) obj).timestamp;
        }

        return false;
    }

}

compareTo, equals and hashCode implementation was taken from the implementation you can see in java.lang.Long. You can also generate these methods by an IDE like Eclipse.

If you want to have a compareTo that evals to 0 when equals must return false (as stated in another comment), then you must implement a Comparator instead of implementing Comparable.

public class EventComparator implements Comparator<Event>, Serializable {

    private static final long serialVersionUID = 1L;

    @Override
    public int compare(Event o1, Event o2) {
        return (o1.getTimestamp() < o2.getTimestamp() ? -1
                : (o1.getTimestamp() == o2.getTimestamp() ? 0 : 1));
    }

}