CompareTo and equal in PriorityQueues

I'm a little confused with everyone "If the order placed by c on S is incompatible with equals, the sorted set (or sorted map) will behave strangely." warnings in javadok. I'm not even sure that PriorityQueue is what I need ...

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

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

I do not understand how I should solve this. I was thinking of creating a custom Comparator, but the same warning about strange behavior appears in the Java compiler. I do not want to insert several equal instances of the event, I just want them to be sorted by timestamp.

Thanks in advance for your help :)

Edit:
I just want events sorted by timestamp. It is possible that two different events have the same timestamp. Therefore, compareTo will return 0 because they have the same timestamp and are equal for sorting purposes. But equals () will not return true, because these are different events.
I'm not sure that PriorityQueue is the right thing. I looked at the SortedSet, but it had the same compareTo and equals consistency warnings.
Maybe I'm doing it from the wrong angle, I don't know ...

+6
source share
3 answers

Different events can have the same timestamp.

and sorts events by label

The last requirement is somewhat fuzzy. Should the iterator collector return instances in sorted order? Or should the collection, if you poll() in a loop, return the old contents in sorted order?

iterator() returns items in order

This does not apply to a PriorityQueue . You can use a SortedSet , but this requires that the sort order is consistent with equals, which, as you correctly noted, you cannot achieve. As far as I know, there is no Collection in the JDK that saves its elements in sorted order for a sort order that considers some elements to be equal. However, you can use an array or ArrayList and sort it manually after the changes using Arrays.sort or Collection.sort . If the collection rarely changes, this is the approach I would choose. If it changes frequently, you will have to search outside the JDK or implement the data structure yourself.

poll() returns items in sorted order

What suits a priority queue. A PriorityQueue does not require a Comparator (or Comparable implementation) to conform to equalities; its JavaDoc clearly writes:

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 bonds break arbitrarily.

In addition, the PriorityQueue implementation in JDK 6 uses equals only to implement indexOf(E) , contains(Object) and remove(Object) , none of which use the comparator in any way. Therefore, for this Collection there can be no consistency with equals.

Comparison with Comparator

Note that it doesn't matter if you use Comparable or Comparator, as far as consistency with equals. For a SortedSet must either be consistent with equals, for a PriorityQueue , Collection.sort or Arrays.sort , none of them should be.

TreeSet and consistency with equals

From the comments:

TreeSet is a SortedSet and explicitly indicates that it relies only on compareTo / compare. It clearly states: "The behavior of a set is well defined, even if its order is not consistent with equals, it simply does not obey the general contract of the Set interface."

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

Note that the order supported by the set (whether it be an explicit comparator) must be consistent with equals if it implements the Set interface correctly. [...] This is due to the fact that the Set interface is defined in terms of the equals operation, but the TreeSet instance performs all element comparisons using the compareTo (or compare ) method, so the two elements that are considered equal by this method are equal, from the point view of the multitude. The behavior of the set is well defined, even if its ordering does not match the equal; it simply does not obey the general contract of the Set interface.

So yes, it’s well defined, but it doesn’t fulfill what the question requires: if you pass TreeSet.add a Event with the same timestamp as another Event in the set, the new Event will be considered as a duplicate and will not be added. although Event not equal . The question asks about sorting Collection ; which should not exclude Events , which duplicates the sort key, should it not?

+5
source

If the order superimposed by c on S is incompatible with equal, the sorted set (or sorted map) will behave strangely.

This 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 .

This is what you need to do so that both methods are consistent.

So, by the way, you are implementing compareTo, you should also override equals () as:

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

Note. I do not know the timestamp data type, but if it is a primitive type, use == instead of equals() for the overriden method.

+4
source

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

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

And that's not it. Due to another contract, you must / must override hashCode() when overriding equals .

Equal objects must have the same hash codes.

 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, which you can see in java.lang.Long . You can also generate these methods using an IDE, such as Eclipse.

If you want to have a compareTo value that evaluates to 0 when equals should return false (as indicated in another comment), then you should implement a Comparator instead of a Comparable implementation.

 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)); } } 
0
source

Source: https://habr.com/ru/post/891347/


All Articles