corejava-collection: What is NavigableSet in java collection?

NavigableSet is a interface found in java.util package. It is a sub type of java.util.SortedSet interface.
It has navigation methods in addition to the sorting mechanisms of the SortedSet.

In Java 6 there was only one implementation of the NavigableSet interface that is java.util.TreeSet in java.util package. It has the following important methods.

1. descendingIterator() and descendingSet()
2. headSet(), tailSet() and subSet()
3. ceiling(), floor(), higher() and lower()
4. pollFirst() and pollLast()


1. descendingSet(): returns a NavigableSet in which the order of the elements is reversed compared to the original one. The returned "view" is backed by the original NavigableSet, so changes to the descending set are also reflected in the original set.
NavigableSet reverse = original.descendingSet();


2. The descendingIterator(): allows us to iterate the elements of the NavigableSet (which is also a SortedSet) in reverse order, without changing the order of the elements internally.
Iterator reverse = original.descendingIterator();

3. headSet(): returns a view of the original NavigableSet which only contains elements that are lesser than the given element. Here is an example:
NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");

//this headset will contain "1" and "2"
SortedSet headset = original.headSet("3");

//this headset will contain "1", "2", and "3" because "inclusive"=true
NavigableSet headset = original.headSet("3", true);

4. tailSet(): works the same way, except it returns all elements that are higher than the given parameter element.

5. subSet(): allows you to pass two parameters demarcating the boundaries of the view set to return. The elements matching the first boundary is included, where as elements matching the last boundary are not. Here is an example:
NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");
original.add("4");
original.add("5");

//this subset will contain "2" and "3"
SortedSet subset = original.subSet("2", "4");

//this subset will contain "2", "3" and "4" because
// fromInclusive=true, and toInclusive=true
NavigableSet subset = original.subSet("2", true, "4", true);

6. ceiling(): returns the least (smallest) element in this set that is greater than or equal to the element passed as parameter to the ceiling() method. Here is an example:
NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");


//ceiling will be "2".
Object ceiling = original.ceiling("2");

//floor will be "2".
Object floor = original.floor("2");
7. The floor(): does the opposite of ceiling()
8. The higher(): returns the least (smallest) element in this set that is greater than (not equal too) the element passed as parameter to the higher() method. Here is an example:
NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");


//higher will be "3".
Object higher = original.higher("2");

//lower will be "1"
Object lower = original.lower("2");
The lower() method does the opposite of the higher() method.

9. pollFirst(): returns and removes the "first" element in the NavigableSet or null if the set is empty.
10. pollLast(): returns and removes the "last" element in the set or null if the set is empty. "First" means smallest element according to the sort order of the set. "Last" means largest according to teh element sorting order of the set.
Here are two examples:
NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");


//first is "1"
Object first = original.pollFirst();

//last is "3"
Object last = original.pollLast();