aspose file tools*
The moose likes Java in General and the fly likes How TreeSet ensure the sorted order of data items Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "How TreeSet ensure the sorted order of data items" Watch "How TreeSet ensure the sorted order of data items" New topic
Author

How TreeSet ensure the sorted order of data items

isha krishnan
Ranch Hand

Joined: Nov 10, 2008
Posts: 50
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
Anayonkar Shivalkar
Bartender

Joined: Dec 08, 2010
Posts: 1509
    
    5

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.


Regards,
Anayonkar Shivalkar (SCJP, SCWCD, OCMJD, OCEEJBD)
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

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

Joined: Nov 10, 2008
Posts: 50
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

Joined: Dec 08, 2010
Posts: 1509
    
    5

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.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4422
    
    8

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.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39436
    
  28
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

Joined: Nov 10, 2008
Posts: 50
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.

 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: How TreeSet ensure the sorted order of data items