Navigable Set
A NavigableSet interface is one of the widely used Collection interfaces. It is highly recommended that one should go through the Set Interface and SortedSet Interface. before getting into the details of a NavigableSet interface.
Figure: Navigable Set Interface
NavigableSet interface as shown in the below figure extends both Set and SortedSet interfaces, and hence it inherits all the operations from both of these interfaces. How different is NavigableSet compared to SortedSet ? Here is the answer. NavigableSet inherits all the basic/fundamental concepts from a Set and SortedSet, so a NavigableSet like SortedSet and a Set does not allow duplicate entries, this means a NavigableSet cannot have 2 objects say, obj1 and obj2 where obj1.equals(obj2) is true. It also inherits the feature of "Sorting" from the SortedSet interface. A NavigableSet, as the name suggests brings in the extra features that helps in navigating a SortedSet. Navigating features like descending order, ceiling, pollFirst, pollLast etc. The class that implements NavigableSet interface is a TreeSet.
Methods defined in NavigableSet interface
The NavigableSet interface inherits all the methods from the Set and SortedSet interface, but as we know NavigableSet brings in the extra features of navigation to a SortedSet.So, NavigableSet interface has defined more methods on top of the ones inherited from Set and SortedSet interfaces. The below table has the list of the methods, defined by the interface NavigableSet. You can imagine this table to be an extension of the table Set Interface Methods List and SortedSet Interface Methods.
| Method | Description |
|---|---|
| <E element> ceiling(E element) | Returns the least element in this Set (The Set that invoked this method) greater than or equal to the given element, or null if there is no such element. |
| Iterator descendingIterator() | Returns an iterator over the elements in this Set (The Set that invoked this method), in descending order. |
| NavigableSet descendingSet() | Returns a reverse order view of the elements contained in this Set (The set that invoked this method), in descending order. |
| NavigableSet headSet(E element, bool inclusive) | Returns the view of the Set, whose elements are less (or equal to, if inclusive is true) than the "element" passed as the parameter |
| <E element> higher(E element) | Returns the least element in this Set (The Set that invoked this method) strictly greater than the given element, or null if there is no such element. |
| <E element> lower(E element) | Returns the greatest element in this Set (The Set that invoked this method) strictly lesser than the given element, or null if there is no such element. |
| <E element> pollFirst() | Returns and removes the first(lowest) element in the Set (The Set that invoked this method) or Null if the Set is empty. |
| <E element> pollLast() | Returns and removes the last(highest) element in the Set (The Set that invoked this method) or Null if the Set is empty. |
| SortedSet tailSet(E element, bool inclusive) | Returns the view of the Set, whose elements are greater than (or equal to if inclusive is true) the "element" passed as the parameter |
| SortedSet subSet(E element, bool inclusive, E element, bool inclusive) | Returns the view of the Set, whose elements in the range of "element1" and "element2" ( if inclusive true, includes the passed elements) that are passed as parameters |
Like shown in the above figure, NavigableSet" extends the SortedSet interface. The class that implements these interfaces is a "TreeSet", more details about TreeSet class available here understanding TreeSet. Here is an Example program that demonstrates the usage of all the above mentioned operations. The example have used TreeSet and demonstrated the usage of the methods defined by the NavigableSet interface.
import java.util.TreeSet;
public class NavigableSet {
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"); // TODO Auto-generated method stub
//tsetObj2.add(1);
System.out.println (" TreeSet1: " + tsetObj1);
System.out.println (" TreeSet2: " + tsetObj2);
System.out.println (" TreeSet1 (Descending order): "
+ tsetObj1.descendingSet());
System.out.println (" TreeSet2 (Descending order): "
+ tsetObj2.descendingSet());
System.out.println (" TreeSet1 Ceiling: "
+ tsetObj1.ceiling(4)
+ " Higher: "
+ tsetObj1.higher(4)
+ " Floor: "
+ tsetObj1.floor(4)
+ " Poll-First: "
+ tsetObj1.pollFirst()
+ " Poll-Last: "
+ tsetObj1.pollFirst());
System.out.println (" TreeSet1 (After poll first/last): "
+ tsetObj1.descendingSet());
}
}
The above program demonstrates quite a few important properties of the NavigableSet interface. Notice the output below, all the elements of the set are in sorted order. This is the basic difference between a Set vs SortedSet (this is also the property of a NavigableSet because, NavigableSet extends SortedSet).
Another important property of a SortedSet (also a property of a NavigableSet) 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.
Also, notice the output, the above program demonstrates the usage of other NavigableSet methods like ceiling, higher, pollFirst, pollLast, floor.
Let us Compile/run the program, Here is the output:
TreeSet1: [4, 13, 24] TreeSet2: [Adam, Lucy, Martin] TreeSet1 (Descending order): [24, 13, 4] TreeSet2 (Descending order): [Martin, Lucy, Adam] TreeSet1 Ceiling: 4 Higher: 13 Floor: 4 Poll-First: 4 Poll-Last: 13 TreeSet1 (After poll first/last): [24]