CodingBison - Sorted Set

A SortedSet interface is one of the widely used Collection interfaces. It is highly recommended that, one should go through its parent interface, Set Interface, before getting into the details of a SortedSet interface.

Figure: SortedSet Interface and Class Hierarchy

SortedSet interface as shown in the above figure extends Set interface, and hence it inherits all the operations from Set interface. How different is SortedSet compared to Set ? Here is the answer. SortedSet inherits all the basic/fundamental concepts from a Set, so a SortedSet (like a Set) does not allow duplicate entries, this means a SortedSet cannot have 2 objects say, obj1 and obj2 where obj1.equals(obj2) is true. A SortedSet also brings in the extra feature of, "Sorting" to the set. So, all the elements of a SortedSet are ordered using their natural ordering. Because all the elements of a SortedSet would be in a particular order, the elements should be comparable; a SortedSet cannot contain any elements that cannot be comparable.

Things To Remember

All the elements in a SortedSet are ordered using their natural ordering.

Methods defined in SortedSet interface

The SortedSet interface inherits all the methods from the Set interface, but as we know SortedSet has its own properties that are added on top of the Set interface. So, SortedSet interface has defined more methods on top of what is has inherited from Set interface. The below table has the list of the methods, defined by the interface SortedSet. You can imagine this table to be an extension of the table Set Interface Methods List.

Table: Methods defined by SortedSet Interface
Method	Description
Comparator comparator()	Returns the comparator used to order the elements. Returns NULL if natural ordering is used.
<E element> first()	Returns the first(lowest) element in the SortedSet
<E element> last()	Returns the last(highest) element in the SortedSet
SortedSet headSet(E element)	Returns the view of the SortedSet, whose elements are less than the "element" passed as the parameter
SortedSet tailSet(E element)	Returns the view of the SortedSet, whose elements are greater or equal to the "element" passed as the parameter
SortedSet subSet(E element, E element)	Returns the view of the SortedSet, whose elements in the range of "element1" and "element2" that are passed as parameters

Like shown in the above figure, NavigableSet" extends the SortedSet interface. The class that implements these interfaces is "TreeSet" Class; more details about TreeSet class is available here understanding TreeSet. Here is an Example program that demonstrates the usage of the above mentioned operations. The example have used TreeSet and demonstrated the usage of the methods defined by the SortedSet interface.

 import java.util.TreeSet;

 public class SortedSetInterfaceDemo {
     public static void main(String[] args) {
         TreeSet tsetObj1 = new TreeSet();
         TreeSet tsetObj2 = new TreeSet();
         tsetObj1.add(4);
         tsetObj1.add(24);
         tsetObj1.add(13);

         tsetObj2.add("Lucy");
         tsetObj2.add("Adam");
         tsetObj2.add("Martin");
         //tsetObj2.add(1);
         System.out.println(" TreeSet1: " + tsetObj1);
         System.out.println(" TreeSet2: " + tsetObj2);

         System.out.println(" First Element: " + tsetObj1.first());
         System.out.println(" Tail Set: " + tsetObj1.tailSet(13));
     }
 }

Things To Remember

All the elements in a SortedSet must be mutually comparable, which implies, element1.compareTo(element2) or comparator.compare(element1, element2) must not throw "ClassCastException"

The above program demonstrates quite a few important properties of the SortedSet interface. Notice the output below, all the elements of the set are in sorted order. This is the basic difference between a Set vs a SortedSet.

Another important property of a SortedSet is demonstrated, if you notice, "tsetObj1 and tsetObj2", the elements of the both the SortedSets are mutually comparable. Which implies, element1.compareTo(element2) or comparator.compare(element1, element2) must not throw "ClassCastException". Uncomment the commented line "tsetObj2.add(1);" in the above program and try to run it. The example program throws "java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer" exception. In other works, the Integer("1") cannot be compared with String class like "Lucy" or "Adam" or "Martin".

Let us Compile/run the program. Here is the output:

  TreeSet1: [4, 13, 24]
  TreeSet2: [Adam, Lucy, Martin]
  First Element: 4
  Tail Set: [13, 24]