Can someone explains what is natural ordering in Java ?

I am revising this Comparable and Comparator and there's this paragraph that I need help to understand what is it about :

t is strongly recommended (though not required) that natural orderings be consistent with equals. This is so because sorted sets (and sorted maps) without explicit comparators behave "strangely" when they are used with elements (or keys) whose natural ordering is inconsistent with equals. In particular, such a sorted set (or sorted map) violates the general contract for set (or map), which is defined in terms of the equals method.

Can someone gives me some examples that illustrate this paragraph ?

Tks alot.

Natural ordering is a general computing concept,, not a Java® concept. It means that for any two instances x and y of a type, one is large than the other or the two are equal in size, and that relationship doesn't change if no other data change, and there is one criterion for that comparison. [Actually, natural ordering can be applied backwards.] Example: floating‑point numbers: 1.23 is always smaller than 1.234, and -9.99 is the same as -9.99. And you won't think of any other way to order such numbers. [Yes, the Double datatype supports -0.0 and NaN.] If you read that link, you will find how Double interprets natural ordering in light of the IEEE754 standard.

On the other hand, BigDecimal has a compareTo() method not consistent with equals().BigDecimal bd1 = new BigDecimal("1.234"); BigDecimal bd2 = new BigDecimal("1.2340"); System.out.println(bd1.equals(bd2)); // false System.out.println(bd1.compareTo(bd2)); // 0If you use those values in a SortedSet, you will get “incorrect” results./* Anonymous class follows */ Set<BigDecimal> numbers = new TreeSet<>() {   {      add(bd1);      add(bd2);   } }; System.out.println(numbers); // [1.234] numbers.size(); // 1 numbers.contains(bd2); // true for (var bd : numbers) {    System.out.println(bd.equals(bd2)); // prints false once }I have my own ideas about String, which differ from Java®'s. Thee are at least two ways of comparing Strings, the classic IT version, unofficially called ASCIIbetical, where Zymurgy comes before aardvark, and case‑insensitive, where aardvark comes first. I think that means the Strings don't have a natural ordering. But I shan't manage to implement that notion anywhere.

Note that case‑insensitive ordering of Strings would give the same problem as above: compareTo() not consistent with equals().

Campbell Ritchie wrote:Note that case‑insensitive ordering of Strings would give the same problem as above: compareTo() not consistent with equals().

can i sum it up that we need to use compareTo for set, and we won't go wrong ?

tangara goh wrote:. . . can i sum it up that we need to use compareTo for set, and we won't go wrong ?

No.


I think you couldn't, not even if I understood the whole of that sentence. What have sets got to do with it?

Campbell Ritchie wrote:

tangara goh wrote:. . . can i sum it up that we need to use compareTo for set, and we won't go wrong ?

No.


I think you couldn't, not even if I understood the whole of that sentence. What have sets got to do with it?

ok. then what does this sentence mean from Oracle site :

This is so because sorted sets (and sorted maps) without explicit comparators behave "strangely" when they are used with elements (or keys) whose natural ordering is inconsistent with equals.

maybe my set is different from the sets ?

What Campbell meant is that, what you said before:

tangara goh wrote:. . . can i sum it up that we need to use compareTo for set, and we won't go wrong ?

is just not an accurate way of summing up his explanation. We're not even sure what you meant to express with your summation, it doesn't make sense to us.


Let me try to explain it to you once more:

The equals() method determines whether two objects represent the same value. The compareTo() method determines whether one object is less than, greater than or equal to another object in value.

If two objects are equal in value, as determined by the compareTo() method returning 0, you'd also expect them to represent the same value, as determined by the equals() method returning true. If for some reason the compareTo() method and the equals() method disagree with each other on whether two objects are equal, then we say the compareTo() method is inconsistent with equals().

If compareTo() is inconsistent with equals(), it can lead to strange results when you use a class that assumes that those methods are consistent with each other. An example is TreeSet:

TreeSet implements the Set interface. When you try to add an object to a set, but the set already contains an object that is equal() to it, then the object must not be added a second time. The problem is that TreeSet never calls equals() on its elements. Instead, it assumes that compareTo() is consistent with equals(), and it calls compareTo() on its elements instead. If compareTo() is not consistent with equals(), it might happen that the same value is added to a set twice, or that the set can't find a value that has been added to it earlier.

It's a very strong recommendation that when you implement compareTo(), its implementation be consistent with equals(). Sadly, this recommendation isn't a hard requirement, and there exist classes that violate this recommendation. BigDecimal is an example of such a class, and Campbell already gave you a good example of what can happen if you add it to a TreeSet.

tangara goh wrote:. . . maybe my set is different from the sets ?

You don't use Comparators, nor ordering, for most Sets. If you look up the Set interface, you will find there are quite a lot of implementing classes. The most commonly used is the HashSet, where the iteration order is usually unpredictable. Some people call that an unordered collection, but that isn't a completely accurate title.
Another implementing class is LinkedHashSet, which I like to think of as a hybrid collection; it combines a hash set and a linked list, so the iteration order depends on the insertion order, remembering that an element is only inserted once. Some people call that an ordered set, but that isn't again a really accurate name.
Neither of the preceding types of set uses Comparators nor natural ordering.
The only kind of set to use natural ordering or Comparators is the SortedSet, which some people call a sorted collection. The best‑known type is the TreeSet. It uses the results of compareTo() or a Comparator to decide where to put a new element. Look at the example I showed you with BigDecimal. It has a compareTo() method not consistent with equals(). Look back at my example. How are you going to create a Comparator that will sort out the problem? Is your Comparator going to say that new BigDecimal("1.234") is larger than new BigDecimal("1.2340") or smaller or the same amount? You are either going to have the same problem, or have a Comparator lying about those two numbers.

So, no, both compareTo() and a Comparator most probably will not be all right for a sorted set.

Campbell Ritchie wrote:So, no, both compareTo() and a Comparator most probably will not be all right for a sorted set.

Hmmm... do you think there is any use for, say, TreeSet or TreeMap at all?  Is it not possible to do something useful with them?  I ask because those necessarily use either compareTo() or a Comparator, and many programmers seem to find them useful on occasion.  I think you may be overstating things a bit here.

Perhaps you meant, these methods will not be all right if they are inconsistent with equals.  That would be a more justifiable statement.  But even there - I think it's entirely possible to get useful results from a TreeSet of BigDecimal.  You just have to accept that it behaves a little differently, not following the original API for Set exactly.

Specifically, if you use natural ordering, or any Comparator that treats 1.234 as equal to 1.2340 - that's fine.  As far as I'm concerned, that's 100% correct.  The problem is that they implemented the equals() method differently from that, and equals() says they are not the same.  Solution: ignore the equals() method of BigDecimal.  It's stupid.  You can still use a TreeSet of BigDecimal, and it will give sensible results.  If you try to put 1.234 and 1.2340 in the same TreeSet, only one will be allowed.  That is as it should be.  Don't worry about what equals() says in this case; it's wrong.

Alternately, one could implement a Comparator that treats 1.234 and 1.2340 as different, perhaps putting the lower-precision number before the higher-precision number.  That works, and is consistent with equals().  And it will allow 1.234 and 1.2340 to both exist in the same set.  And you can use the equals() method as well. It's not consistent with what I consider common sense, but it can be done; it works.

Basically, if you think 1.234 and 1.2340 should be equal, you can do that, with natural ordering.  Just ignore the results of equals(), which is wrong.  Or if you think 1.234 and 1.2340 should not be equal, you can do that too, with a custom comparator.

Mike Simmons wrote:. . . do you think there is any use for, say, TreeSet or TreeMap at all? . . . I think you may be overstating things a bit here.

Yes, I was What a mistake! Stephan also contacted me behind the scenes to say I was mistaken.

Perhaps you meant, these methods will not be all right if they are inconsistent with equals. . . .

Yes, that is exactly what I meant to say.

. . . if you think 1.234 and 1.2340 should be equal . . .

Shows how much interesting discussion you can get from a mistake.
But if a HashSet adds 1.234 and 1.2340 as two different elements, and a TreeSet only adds one element, which is behaving correctly? Or are there two variants of the general contract of add(E) depending on what you define as equal?

. . . Or maybe the correct answer is to read what the SortedSet interface says,

. . . the ordering maintained by a sorted set (whether or not an explicit comparator is provided) must be consistent with equals if the sorted set is to correctly implement the Set interface.

. . . and say you are violating the preconditions of that interface by using it for BigDecimal or anything else with compareTo() inconsistent with equals()? And if you violate that precondition, you only have yourself to blame for incorrect results.

Oh no, what will happen if the general contract of Set is violated?   Will the world end?  

We can look at the API for TreeSet for a clue:

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. (See Comparable or Comparator for a precise definition of consistent with equals.) 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.

(Emphasis mine)

Yes, it's violating the general contract, because it's relying on compareTo() instead of equals().  But it is following its own contract.  TreeSet will ignore equals() entirely, and use compareTo() or a Comparator instead.  Which still produces perfectly usable, consistent results.  They just don't make sense with the parts of the Set interface that mention the equals() method.  Which is why we should ignore that, when using a TreeSet or TreeMap with a comparision that's inconsistent with equals().  The results will still make sense, according to the alternate definition of "equals()" that we supply with the Comparator or compareTo().  They warn us about it because it's something to be aware of, not because it's a deal breaker.

Let us also read from the Book of Joshua, 3:14 (p. 67 in 3rd Ed.):

Joshua Bloch wrote:It is strongly recommended, but not required, that (x.compareTo(y) == 0) == (x.equals(y)).  Generally speaking, any class that implements the Comparable interface and violates this condition should clearly indicate this fact.  The recommended language is "Note: This class has a natural ordering that is inconsistent with equals."

And later on p. 68:

Joshua Bloch wrote:The final paragraph of the compareTo contract, which is a strong suggestion rather than a true requirement, simply states that the equality test imposed by compareTo method should generally return the same results as the equals method.  If this provision is obeyed, the ordering imposed by the compareTo method is said to be consistent with equals.  If it's violated, the ordering is said to be inconsistent with equals.  A class whose compareTo method imposes an order that is inconsistent with equals will still work, but sorted collections containing elements of the class may not obey the general contract of the appropriate collection interfaces (Collection, Set, or Map).  This is because the general contracts for those interfaces are defined in terms of the equals method, but sorted collections use the equality test imposed by comareTo instead of equals.  It is not a catastrophe if this happens, but it's something to be aware of.

For BigDecimal, you can use a TreeSet or TreeMap just fine.  You just have to decide whether you want the precision to be part of the comparison or not, and understand the consequences of that.  The Set API only has one idea of how to compare two instances, by using equals.  The TreeSet API allows more than one way, which you achieve by ignoring equals.  It's OK.

Note that this is not like having a hashCode() method inconsistent with equals() - if you do that with a HashSet or HashMap, it may very well not work at all, being unable to find things that were inserted into it.  Because HashSet and HashMap necessarily use both hashCode() and equals() internally, and bad things happen when those do not agree.  TreeSet And TreeMap, however, avoid this by not using equals() at all, and instead using compareTo() or a Comparator.  So they do give consistent, useful results, even for "incompatible" comparison implementations... if we're not too paralyzed by fear to be able to use them.

Campbell Ritchie wrote:But if a HashSet adds 1.234 and 1.2340 as two different elements, and a TreeSet only adds one element, which is behaving correctly? Or are there two variants of the general contract of add(E) depending on what you define as equal?

They are both behaving correctly as designed, and as documented*.  The difference depends on how you want to define equality. The HashSet is using the equals() definition, and the TreeSet is using the compareTo() definition.  Both can be valid - though I would usually prefer the latter, for BigDecimal.

* By "as documented", I mean if you include the fact that TreeSet specifically defines how it behaves in violation of the general contract.  Yes, it's against the original Set and Collection documentation, but if we accept that and read what TreeSet says it does, that describes the behavior perfectly.

I should retract the earlier comment describing the equals() method of BigDecimal as stupid.  It's... well, it's not the policy that I would want, most of the time.  However, sometimes it may be the policy you want.  So in  order for them to support both notions of equality, they have settled on a reasonable compromise.  For equality that includes comparing precision, use a HashSet, which will rely on equals() and hashCode(), which are compatible with each other.  For equality that excludes comparing precision, use a TreeSet, which will rely on compareTo(), and don't worry about equals().

In retrospect, they probably should have defined Collection, Set, Map, etc not in terms of equals(), but in terms of a ComparisonStrategy which could be set for a particular Collection, Set or Map.  It would be similar to Comparator, but more flexible to include subinterfaces that might rely on hashCode() or compareTo() or whatever other strategies we might devise for comparing things.  Then the general contract would be flexible enough to allow for possible deviations in specific subclasses.  And you could redefine equality for different applications, regardless of how a particular class implemented hashCode(), equals() or compareTo().  Sigh.  If only they had consulted me.