The SortedSet interface in Java is part of the java.util package and is a specialized version of the Set interface. It ensures that the elements in the set are sorted in their natural order or according to a custom comparator provided at the time of set creation.
Unlike Set, which only guarantees uniqueness, SortedSet guarantees both uniqueness and a sorted order of elements.
In this tutorial, we'll cover:
Overview of the SortedSet interface.
Common methods in SortedSet.
Implementations of SortedSet (TreeSet).
Code examples demonstrating various SortedSet operations.
1. SortedSet Interface Overview
A SortedSet maintains its elements in ascending order by default. If you insert elements into a SortedSet, they will automatically be arranged according to their natural ordering (for example, numbers are sorted numerically, and strings are sorted lexicographically).
Common Implementations of SortedSet
TreeSet: The most common implementation of SortedSet. It uses a balanced tree structure (Red-Black Tree) to store elements in a sorted manner.
2. Common Methods in SortedSet
Apart from the usual methods provided by the Set interface, the SortedSet interface provides some additional methods related to sorting:
Comparator<? super E> comparator(): Returns the comparator used to order the elements in the set, or null if natural ordering is used.
E first(): Returns the first (lowest) element currently in the set.
E last(): Returns the last (highest) element currently in the set.
SortedSet headSet(E toElement): Returns a view of the portion of this set whose elements are strictly less than toElement.
SortedSet tailSet(E fromElement): Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
SortedSet subSet(E fromElement, E toElement): Returns a view of the portion of this set whose elements range from fromElement (inclusive) to toElement (exclusive).
3. TreeSet Implementation of SortedSet
The TreeSet class is the most common implementation of SortedSet. It stores elements in sorted order using a self-balancing tree (Red-Black Tree).
Example 1: Basic TreeSet Operations
import java.util.SortedSet;
import java.util.TreeSet;
public class TreeSetExample {
public static void main(String[] args) {
// Creating a TreeSet (SortedSet) of integers
SortedSet treeSet = new TreeSet<>();
// Adding elements to the TreeSet
treeSet.add(10);
treeSet.add(5);
treeSet.add(20);
treeSet.add(15);
// Displaying the elements (sorted order)
System.out.println("TreeSet: " + treeSet); // [5, 10, 15, 20]
// Accessing the first and last elements
System.out.println("First element: " + treeSet.first()); // 5
System.out.println("Last element: " + treeSet.last()); // 20
// Getting a subset of elements (between 5 and 15)
SortedSet subSet = treeSet.subSet(5, 15);
System.out.println("SubSet (5 to 15): " + subSet); // [5, 10]
}
}
Explanation:
TreeSet: Maintains the elements in sorted order.
first() and last(): Retrieve the smallest and largest elements, respectively.
subSet(): Returns a view of the portion of the set between the specified range of elements.
4. Working with headSet and tailSet
Example 2: Using headSet and tailSet
import java.util.SortedSet;
import java.util.TreeSet;
public class HeadTailSetExample {
public static void main(String[] args) {
// Creating a TreeSet of string elements
SortedSet treeSet = new TreeSet<>();
// Adding elements to the TreeSet
treeSet.add("Apple");
treeSet.add("Banana");
treeSet.add("Orange");
treeSet.add("Grapes");
treeSet.add("Mango");
// Getting a headSet (elements less than Mango)
SortedSet headSet = treeSet.headSet("Mango");
System.out.println("HeadSet (less than Mango): " + headSet); // [Apple, Banana, Grapes]
// Getting a tailSet (elements greater than or equal to Mango)
SortedSet tailSet = treeSet.tailSet("Mango");
System.out.println("TailSet (greater than or equal to Mango): " + tailSet); // [Mango, Orange]
}
}
Explanation:
headSet(toElement): Returns a view of the portion of the set that contains elements less than the specified element.
tailSet(fromElement): Returns a view of the portion of the set that contains elements greater than or equal to the specified element.
5. Custom Comparator in TreeSet
By default, TreeSet uses the natural ordering of elements. However, you can provide a custom comparator when creating the TreeSet to define a different sorting order.
Example 3: TreeSet with Custom Comparator (Reverse Order)
import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;
public class CustomComparatorExample {
public static void main(String[] args) {
// Creating a TreeSet with a custom comparator (reverse order)
SortedSet treeSet = new TreeSet<>(Comparator.reverseOrder());
// Adding elements
treeSet.add(10);
treeSet.add(5);
treeSet.add(20);
treeSet.add(15);
// Displaying the elements (sorted in reverse order)
System.out.println("TreeSet with custom comparator: " + treeSet); // [20, 15, 10, 5]
}
}
Explanation:
Comparator.reverseOrder(): A built-in comparator that sorts elements in descending (reverse) order.
The elements in the TreeSet are now sorted from largest to smallest.
6. Navigating a SortedSet
SortedSet provides methods like first(), last(), headSet(), and tailSet() to navigate through the set. Letโs explore more navigation techniques.
Example 4: Using Navigation Methods in SortedSet
import java.util.SortedSet;
import java.util.TreeSet;
public class SortedSetNavigation {
public static void main(String[] args) {
SortedSet treeSet = new TreeSet<>();
treeSet.add("Apple");
treeSet.add("Banana");
treeSet.add("Orange");
treeSet.add("Mango");
treeSet.add("Grapes");
// Accessing the first and last elements
System.out.println("First element: " + treeSet.first()); // Apple
System.out.println("Last element: " + treeSet.last()); // Orange
// Accessing a subset (between Apple and Orange)
SortedSet subSet = treeSet.subSet("Apple", "Orange");
System.out.println("SubSet (Apple to Orange): " + subSet); // [Apple, Banana, Grapes, Mango]
// Accessing headSet (less than Mango)
SortedSet headSet = treeSet.headSet("Mango");
System.out.println("HeadSet (less than Mango): " + headSet); // [Apple, Banana, Grapes]
}
}
Explanation:
subSet() returns a view of the set between two elements.
headSet() and tailSet() return parts of the set based on the specified elements.
7. Using Custom Objects in a TreeSet
You can use custom objects in a TreeSet. However, the custom object class must either implement the Comparable interface or you must provide a Comparator to define the ordering.
Example 5: Using Custom Objects in TreeSet
import java.util.SortedSet;
import java.util.TreeSet;
class Person implements Comparable {
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person other) {
return Integer.compare(this.age, other.age); // Sorting by age
}
@Override
public String toString() {
return name + " (" + age + ")";
}
}
public class TreeSetCustomObjectExample {
public static void main(String[] args) {
// Creating a TreeSet where elements are Person objects
SortedSet personSet = new TreeSet<>();
personSet.add(new Person("Alice", 30));
personSet.add(new Person("Bob", 25));
personSet.add(new Person("Charlie", 35));
// Displaying the TreeSet (sorted by age)
for (Person person : personSet) {
System.out.println(person);
}
}
}
Explanation:
The Person class implements the Comparable interface and defines the compareTo() method to sort the objects by age.
The TreeSet stores Person objects and automatically sorts them based on age.
8. Key Considerations for SortedSet
Sorting: Elements in a SortedSet are automatically sorted. By default, it uses natural ordering (as defined by Comparable), but you can provide a custom Comparator.
Uniqueness: Like all sets, a SortedSet ensures that duplicate elements are not allowed.
Navigability: SortedSet allows efficient navigation through the set using methods like first(), last(), subSet(), headSet(), and tailSet().
Conclusion
In this tutorial, we explored the SortedSet interface in Java, focusing on its common implementation TreeSet. We covered:
Basic operations like add(), remove(), first(), and last().
Navigation methods like headSet(), tailSet(), and subSet().
Creating TreeSet objects with custom comparators and using custom objects in the set.
The SortedSet interface is a powerful tool when you need to maintain a sorted collection of elements, and it offers efficient operations with logarithmic time complexity for most operations.