• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

Can someone explains what is natural ordering in Java ?

 
Ranch Hand
Posts: 1049
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Marshal
Posts: 80280
432
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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().If you use those values in a SortedSet, you will get “incorrect” results.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.
 
Campbell Ritchie
Marshal
Posts: 80280
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Note that case‑insensitive ordering of Strings would give the same problem as above: compareTo() not consistent with equals().
 
tangara goh
Ranch Hand
Posts: 1049
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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 ?
 
Campbell Ritchie
Marshal
Posts: 80280
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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?
 
tangara goh
Ranch Hand
Posts: 1049
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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 ?
 
Bartender
Posts: 15737
368
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Campbell Ritchie
Marshal
Posts: 80280
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.

[edit 2-Jan-2025]Somebody queried my last sentence, and I didn't notice at the time. Sorry. I meant it is probably not a good ides to use both together for a sorted set; use natural ordering or a Comparator, but not both together.[/edit]
 
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Campbell Ritchie
Marshal
Posts: 80280
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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?
 
Campbell Ritchie
Marshal
Posts: 80280
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
. . . 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.
 
Mike Simmons
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Mike Simmons
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You have to put the same code on the equals and the comparator for good behavior on the implementing class....good bye
 
Mike Simmons
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, obviously the "same code" would never work - one method returns a boolean, while the other returns an int.  You are encouraged to make the two compatible - but there can be very valid reasons why compatibility is not required - and in some cases, compatibility is a flat-out stupid idea.  (Like if you need 1.5 to be the same as 1.50 or 1.500, when using BigDecimal - compatibility with equals() would be stupid.) As already discussed extensively above.
 
Greenhorn
Posts: 2
IntelliJ IDE Java ChatGPT
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Natural ordering is how Java knows to put things in order by default. For numbers, it's smallest to largest. For words, it's A to Z. For your custom class, you decide what "natural" means by implementing compareTo method.Refere bellow example for natural ordering.
import java.util.*;

public class Main {
   public static void main(String[] args) {
       // Example with Strings
       List<String> fruits = Arrays.asList("Banana", "Apple", "Cherry");
       Collections.sort(fruits); // Natural ordering: Alphabetical
       System.out.println(fruits); // Output: [Apple, Banana, Cherry]

       // Example with Integers
       List<Integer> numbers = Arrays.asList(5, 3, 9, 1);
       Collections.sort(numbers); // Natural ordering: Ascending numeric
       System.out.println(numbers); // Output: [1, 3, 5, 9]
   }
}
refer bellow example for custom class by implementing compareTo method,
class Student implements Comparable<Student> {
   String name;
   int marks;

   public Student(String name, int marks) {
       this.name = name;
       this.marks = marks;
   }

   // Define natural ordering based on marks
   @Override
   public int compareTo(Student other) {
       return Integer.compare(this.marks, other.marks);
   }
}
 
Sheriff
Posts: 28371
99
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote: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.


People talking about Java Strings typically forget, or ignore, that a String is a sequence of Unicode characters, instead simply looking at ASCII characters in English.

It should be clear that a natural ordering for Strings must be based on a natural ordering for the Unicode characters. Now you might say that the natural ordering for the Unicode characters is the ordering based on the Unicode values of the characters. And fair enough, there aren't any other good candidates. Now let me ask you this: in this "natural" ordering, do the Cyrillic characters come before or after the Greek characters? (No fair peeking.) And why is that more natural than the opposite? And how can this ordering be called "natural" when the order it provides for the letters used in Turkish doesn't match the order used by Turks in real life?

So yes, I'm saying that String does not have a natural ordering.
 
Mike Simmons
Master Rancher
Posts: 5122
82
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Additionally, String.compareTo() sorts by the UTF-16 Unicode values, not the code point values, which would be more "natural" under the modern Unicode specification.

Of course, from a Java perspective, the definition of "natural ordering" to use is the one given in [url=https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/Comparable.html]Comparable[/ur] interface.  String implements Comparable; therefore the natural ordering is, by definition, whatever the compareTo() method is implemented to deliver as the natural ordering.  Even if it may seem quite "unnatural" from other perspectives.
 
Campbell Ritchie
Marshal
Posts: 80280
432
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

kushan dileep wrote:Natural ordering is how Java knows . . . you decide what "natural" means . . .

I disagree. The natural ordering of something depends on that something, not the language you are using. As we have said before, Strings have at least two possible orderings, so‑called ASCIIbetical, and one case‑insensitive. In ASCIIbetical, Zwolle (town in Netherlands) comes before aardvaark, and in case‑insensitive, aardvaark come before Zwolle. Most books use case‑insensitive ordering for words, and most computer languages use ASCIIbetical, only they call it lexical ordering. It follows Unicode and ASCII where capital letters come before lower‑case.
I think several other people think that Unicode Strings do not have a natural ordering in the first place. Nor I think do students. They have several ways they can be sorted, by name, by age, and by marks. So again, I think that Students don't have a natural ordering. When you write a Student class and want to order instances, you don't decide what “natural ordering” means, but which of the several orderings you are using at the moment. That is best done with a Comparator; I think only classes with a natural ordering should implement Comparable. In which case maybe String shouldn't have implemented it, aand I would be very interested to know what bright spark thinks a class which doesn't even override equals() should implement Comparable. I mean StringBuilder.
 
Mike Simmons
Master Rancher
Posts: 5122
82
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:The natural ordering of something depends on that something, not the language you are using.


Um, this ignores the just-stated fact that in Java, the Comparable interface defines natural ordering.  This definion is used in other classes as well, whenever ordering is discussed.  In general there can be more than one notion or definition of what "natural ordering" means, and we have been discussing different opionions and interpretations of that, in general.  But it's worthwhile to realize that if we are talking about Java classes, there is one very specific definition that takes precedence over others - namely, the definition in Comparable.  If a class implements Comparable, then whatever order the compareTo() method imposes is the natural order, by definition.  Whether we like it or not. I agree that it might make sense for them to have defined it differently, but  they didn't, and it's useful to be aware what the established definition actually is.  Especially when that's the very thing the original poster was aking about.
 
Campbell Ritchie
Marshal
Posts: 80280
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think we disagree much less than it might appear. I was however mistaken and you are correct. The documentation for Comparable (old edition here) says it imposes an ordering onto a class and then calls it its natural ordering. That permits Comparable to do something different from what may others would use as a natural ordering.
 
Paul Clapham
Sheriff
Posts: 28371
99
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Indeed. It's possible that a class can have many total orderings -- for example an Employee class could be ordered by name or date of hire or other characteristics. But if the class is going to implement Comparable then you can only choose one total ordering for that, so it's natural to call that one the "natural" ordering. The others can only be implemented by writing Comparators. Campbell and I are just griping that a "natural" ordering may not look that natural, but yes, that's distracting.

Incidentally the java.text package contains classes which help manage the un-naturalness of the sequence of characters in Unicode, in particular java.text.Collator.
 
Mike Simmons
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:I think we disagree much less than it might appear.


Yeah, we're largely in agreement.  I just wanted to make sure our discussion of what natural ordering could be or should be, didn't obfuscate the essential answer to the original poster's questions.
 
Campbell Ritchie
Marshal
Posts: 80280
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Paul Clapham wrote:Indeed. It's possible that a class can have many total orderings - - .

Agree. OP's Student class has at least two potential orderings.
 
So I left, I came home, and I ate some pie. And then I read this tiny ad:
New web page for Paul's Rocket Mass Heaters movies
https://coderanch.com/t/785239/web-page-Paul-Rocket-Mass
reply
    Bookmark Topic Watch Topic
  • New Topic