Saurabh Gupta
Saurabh Gupta

Reputation: 459

How to define comparator on SortedSet<> like TreeSet<>?

I want to make a lexical sorted list of strings, so i went with the basic SortedSet

1)  Set<String> words = new SortedSet<String>(){}

and realized that SortedSet is an abstract class, in which I will have to implement the comapartor method. So i went and searched on google and found out that treeSet is better and i can use its predefined comparator method.

2)  SortedSet<String> words = new TreeSet<String>(){}

When went to java docs i realized that TreeSet extends AbstractSet rather than SortedSet. Question 1 - Can anyone explain how the 2nd line is still working(like i am not generalizing the Set which i would normally do instead i am using two totally different Classes with no Parent child relation). Question 2 - how to define comparator of SortedSet which will work as TreeSet. So here is the working code with TreeSet

SortedSet<String> words = new TreeSet<>();
    Scanner scanner1 = new Scanner(System.in);
    String s1 = scanner1.nextLine();
    int a = scanner1.nextInt();
    while(s1.length()>a){
        words.add(s1.substring(0,a));
        s1 = s1.substring(a);
    }
    Iterator itr  = words.iterator();
    while(itr!= null&&itr.hasNext()){
        System.out.println(itr.next());
    }

Normal Input

welcometojava
3

Expected Output

com
eto
jav
wel

Edit-1 For the answer of Question 2, i am expecting something like this

Set<String> words = new SortedSet<String>() {
        @Override
        public Comparator<? super String> comparator() {
            return null;
        }
        ......

I basically want to learn, how to make a basic comparator "like" in TreeSet while using SortedSet? I understand that if there is natural ordering i don't need to define a new comparator.

Upvotes: 6

Views: 40535

Answers (4)

kazenorin
kazenorin

Reputation: 1465

Answer 1:

TreeSet<T> implements the NavigableSet<T> interface, which extends SortedSet<T> who also extends Set<T>.

The interfaces themselves doesn't actually do the sorting, the concrete class does.

So:

Set<String> myStrings = new TreeSet<>();
// Add a bunch of strings
// ...
for (String s : myStrings) {
 System.out.println(s);
}

You would still have them in sorted order.

Answer 2:

Firstly, for classes that already implement Comparable<T>, you can omit the Comparator for the TreeSet, as "Natural Ordering" is meant by using the Comparable<T>'s compareTo method.

Otherwise you can supply a Comparator instance to as the TreeSet constructor's first argument:

    Set<String> myStrings = new TreeSet<>(new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            // Define comparing logic here
            return o1.compareTo(o2);
        }
    });

or use Java 8 Lambdas:

    Set<String> myStrings = new TreeSet<>((o1, o2) -> o1.compareTo(o2));

Upvotes: 16

toro
toro

Reputation: 194

TreeSet implements NavigableSet, which in turn extends SortedSet, which is why line 2) works. See TreeSet Java doc.

For the second part, try this:

SortedSet<String> ts = new TreeSet<String>(new TSComparator());

class TSComparator implements Comparator<String>{

    @Override
    public int compare(String str1, String str2) {
        return str1.compareTo(str2);
    }

}

Upvotes: 3

Saravana
Saravana

Reputation: 12817

To answer your question,

TreeSet also implements NavigableSet which extends SortedSet

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable

public interface NavigableSet<E> extends SortedSet<E>

By default sort will be done based on natural ordering and the basic primitives wrappers (Integer, Long, ...) implements Comparable interface, so no need to implement the Comparable if the collection holds wrappers of Primitives and natural ordering is expected

But your custom class should implement Comparable if it should be ordered in TreeSet else ClassCastException will be thrown once you add the second element

Upvotes: 3

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727087

SortedSet<T> is not an abstract class, it is an interface.

TreeSet<T> does implement SortedSet<T>, but not directly: the chain of inheritance goes as follows:

Set<T> - SortedSet<T> - NavigableSet<T>

That is why the assignment SortedSet<String> words = new TreeSet<String>() works: TreeSet<T> is a NavigableSet<T>, and NavigableSet<T> is a SortedSet<T>, so the assignment is legal.

When you do not supply an explicit comparator, TreeSet<T>'s uses natural ordering supplied by T's implementation of Comparable<T>.

Upvotes: 2

Related Questions