• 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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

How TreeSet ensure the sorted order of data items

 
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi All,

I am practicing collections. Regarding TreeSet,its written that it maintain the sort order of object added to TreeSet.
An object which is added to TreeSet should implement Comparable Interface and implemented compareTo(Object obj).

I added objects to Set and when iterated Set,ojects are displayed in Sorted order.
When i debug application, i can see that for every set.add(..) call, compareTo() is called [Please Confirm this understanding].

compareTo says a.compareTo(obj.a) (Comparison is done the basis a instance variable)

How does compareTo() ensure comparison i mean to ask how it know it has to compare (Where is the implementation of this operation or i could say rules it follow to compare)??

Thanks in Advance,
Isha
 
Bartender
Posts: 1558
5
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello isha krishnan,

If I understand your question correctly, it is - how compareTo method understands which object is smaller. Is that right?

Well, a simple answer is that - when your class (e.g. Employee) implements Comparable interface, it must also implement compareTo method.
Now, you can implement the method in any way you want - e.g. you can decide that Employee A is greater than B if A's salary is bigger than B. Or A's name comes after B's name in alphabetical order. Or any other criteria.

Based on that criteria, TreeSet will decide the order of the members.

To make things even more flexible, you can also have a separate class which implements Comparator interface (and its compare method). That way, you can use different Comparator (and hence different logic) to sort same collection.

I hope this helps.
 
Ranch Hand
Posts: 5575
Eclipse IDE Windows XP Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you want to know the under hood implementation then,
first read binary search tree and go for a red black tree(balanced tree implementation)
 
isha krishnan
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yeah ,i want to understand default behaviour of this operation
eg in my method ,i simply wrote in compareTo()


here i never described 1) if list in ascending or descending order 2) if char a> char b or any other criteria..it mean there are some default rules defined.

I hope it clears my concern. Yes i 'll refer binary search tree and red black tree(balanced tree implementation) for understanding.

Any other details are most welcome!


 
Anayonkar Shivalkar
Bartender
Posts: 1558
5
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

isha krishnan wrote:if list in ascending or descending order


Well, what you are doing here is - invoking compareTo method of 'Songs'. Thus, it will be sorted according to Songs' class' compareTo method. That is, if Songs is a String object, then you are invoking String class' compareTo method.

Now, if you want to reverse the logic, it can be simply done by modifying return statement to:

Regarding 'by default rules', yes there are - e.g. for Integer class, compareTo returns result of simple numeric comparison, for String class, compareTo returns result of alphabetic comparison and so on.

I hope this helps.
 
Bartender
Posts: 4568
9
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

isha krishnan wrote:
here i never described 1) if list in ascending or descending order 2) if char a> char b or any other criteria


You have described it. What you've effectively said is "sort according to the Songs variable, based on whatever the natural ordering for that type is". So if Songs is a String, you're sorting according to the ordering built in to the String class (see java.lang.String#compareTo(java.lang.String) for details). If you wanted to reverse that order, you could have written return -Songs.compareTo(s2.Songs) instead.
 
Marshal
Posts: 79177
377
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Why are you making it implement Comparable rather than Comparable<Song>? That way you could dispense with all those casts. It looks peculiar to have a class called Song with a field called Songs.
 
isha krishnan
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks all,

yeah ,i have found doc of String.java on [http://www.docjar.com/html/api/java/lang/String.java.html].It clears doubt of defualt behaviour.
Now i can corelate flow of statments.

 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic