Here is another example of when consistency with equals AND total ordering are important to implement.
Say we have an object MyObject which has two fields: id and quantity.
id as its name suggests is the natural key of the object and quantity is just an attribute.
public class MyObject {
int id;
int quantity;
...
}
Let's imagine that we want to use a collections of MyObject sorted by quantity descending.
The First comparator we can write is:
Comparator<MyObject> naiveComp = new Comparator<MyObject>() {
@Override
public int compare(MyObject o1, MyObject o2) {
return o2.quantity - o1.quantity;
}
};
Using MyObject instances equipped with this comparator in a TreeMap/TreeSet fails because it comparator is not consistent with equals (see full code below). Let's make it consistent with equals:
Comparator<MyObject> slightlyBetterComp = new Comparator<MyObject>() {
@Override
public int compare(MyObject o1, MyObject o2) {
if (o1.equals(o2)) {
return 0;
}
if (o1.quantity == o2.quantity) {
return -1; // never 0
}
return o2.quantity - o1.quantity; // never 0
}
};
However, this fails again to fit in TreeSet/TreeMap! (see full code below)
This is because the ordering relation is not total, i.e. not any two objects can be strictly put in an ordering relationship. In this comparator, when quantity fields are equal, the resulting ordering is undetermined.
A better comparator would be:
Comparator<MyObject> betterComp = new Comparator<MyObject>() {
@Override
public int compare(MyObject o1, MyObject o2) {
if (o1.equals(o2)) {
return 0;
}
if (o1.quantity == o2.quantity) {
return o1.id - o2.id; // never 0
}
return o2.quantity - o1.quantity; // never 0
}
};
This comparator ensures that:
- when compareTo returns 0 it implies that two objects are
equal (initial check for equality)
- all items are totally ordered by using
id as a discriminant ordering field when quantity are equal
Full Testing Code:
package treemap;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class MyObject {
int id;
int quantity;
public MyObject(int id, int quantity) {
this.id = id;
this.quantity = quantity;
}
@Override
public int hashCode() {
int hash = 7;
hash = 97 * hash + this.id;
return hash;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final MyObject other = (MyObject) obj;
if (this.id != other.id) {
return false;
}
return true;
}
@Override
public String toString() {
return "{" + id + ", " + quantity + "}";
}
public static void main(String[] args) {
String format = "%30.30s: %s\n";
Map<MyObject, Object> map = new HashMap();
map.put(new MyObject(1, 100), 0);
map.put(new MyObject(2, 100), 0);
map.put(new MyObject(3, 200), 0);
map.put(new MyObject(4, 100), 0);
map.put(new MyObject(5, 500), 0);
System.out.printf(format, "Random Order", map.keySet());
// Naive non-consisten-with-equal and non-total comparator
Comparator<MyObject> naiveComp = new Comparator<MyObject>() {
@Override
public int compare(MyObject o1, MyObject o2) {
return o2.quantity - o1.quantity;
}
};
Map<MyObject, Object> badMap = new TreeMap(naiveComp);
badMap.putAll(map);
System.out.printf(format, "Non Consistent and Non Total", badMap.keySet());
// Better consisten-with-equal but non-total comparator
Comparator<MyObject> slightlyBetterComp = new Comparator<MyObject>() {
@Override
public int compare(MyObject o1, MyObject o2) {
if (o1.equals(o2)) {
return 0;
}
if (o1.quantity == o2.quantity) {
return -1; // never 0
}
return o2.quantity - o1.quantity; // never 0
}
};
Map<MyObject, Object> slightlyBetterMap = new TreeMap(naiveComp);
slightlyBetterMap.putAll(map);
System.out.printf(format, "Non Consistent but Total", slightlyBetterMap.keySet());
// Consistent with equal AND total comparator
Comparator<MyObject> betterComp = new Comparator<MyObject>() {
@Override
public int compare(MyObject o1, MyObject o2) {
if (o1.equals(o2)) {
return 0;
}
if (o1.quantity == o2.quantity) {
return o1.id - o2.id; // never 0
}
return o2.quantity - o1.quantity; // never 0
}
};
Map<MyObject, Object> betterMap = new TreeMap(betterComp);
betterMap.putAll(map);
System.out.printf(format, "Consistent and Total", betterMap.keySet());
}
}
Output:
Random Order: [{5, 500}, {4, 100}, {3, 200}, {2, 100}, {1, 100}]
Non Consistent and Non Total: [{5, 500}, {3, 200}, {4, 100}]
Consistent but Not Total: [{5, 500}, {3, 200}, {4, 100}]
Consistent and Total: [{5, 500}, {3, 200}, {1, 100}, {2, 100}, {4, 100}]
Conclusion:
Although I think it is very legitimate to segregate identity from ordering conceptually. For instance, in relational database terms:
select * from MyObjects order by quantity
works perfectly. We don't care about object identity here, nor we want total ordering
However, due to constraints in tree based collections implementation, one has to ensure that any comparator they write:
- is consistency with equals
- provide a total ordering over all possible objects
