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

Question

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.

Got the answer to first question. Now need the answer to second question. — Saurabh Gupta, Jun 28 '16 at 03:02
Possible duplicate of [What is the difference between an interface and abstract class?](http://stackoverflow.com/questions/1913098/what-is-the-difference-between-an-interface-and-abstract-class) — shmosel, Jun 28 '16 at 04:23

score 15 · Accepted Answer · edited Aug 11 '22 at 04:45

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));

toro · Answer 2 · 2016-06-28T03:09:35.687

3

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);
    }

}

edited Jun 28 '16 at 03:09

answered Jun 28 '16 at 03:01

toro

194
5

I wanted to define comparator in SortedSet not TreeSet, want to extend the SortedSet Class then define the comparator over it. – Saurabh Gupta Jun 28 '16 at 03:11
2

SortedSet is an interface. So you will not be able to provide implementation for the Comparator interface in SortedSet. Neither will you be able to instantiate a SortedSet object. I hope this makes sense and that my statement is not tangential to your point. Thanks – toro Jun 28 '16 at 03:19

Saravana · Answer 3 · 2016-06-28T03:06:27.743

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

score 2 · Answer 4 · answered Jun 28 '16 at 03:03

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>.

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

4 Answers4