Tech and Media Labs
This site uses cookies to improve the user experience.


Java NavigableSet

Jakob Jenkov
Last update: 2019-10-03

The Java NavigableSet interface, java.util.NavigableSet, is a subtype of the Java SortedSet interface. Therefore the NavigableSet behaves like a SortedSet, but with an additional set of navigation methods available in addition to the sorting mechanisms of the SortedSet. In this text I will look closer at some of the navigation methods of the Java NavigableSet.

Java NavigableSet Implementations

In Java 6 to 13 there is only one implementation of the NavigableSet interface in the java.util package: The java.util.TreeSet class. There is an implementation in the java.util.concurrent package called ConcurrentSkipListSet but that is outside the scope of this trail.

Create a NavigableSet

To create a Java NavigableSet you must create an instance of one of the classes implementing the NavigableSet interface. Here is an example of creating an instance of the class TreeSet which implements the NavigableSet interface:

NavigableSet navigableSet = new TreeSet();

descendingSet()

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

Here is a simple example:

NavigableSet reverse = original.descendingSet();

descendingIterator()

The descendingIterator() method allows you 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();    

headSet()

The headSet() method returns a view of the original NavigableSet which only contains elements that are "less 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);

tailSet()

The tailSet() method works the same way as the headSet() method, except it returns all elements that are equal to or higher than the given parameter element. Here is a NavigableSet tailSet() method example:

NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");

//this tailSet will contain "2" and "3"
SortedSet tailSet = original.tailSet("2");

//this tailSet will contain "3" only because "inclusive"=false
NavigableSet tailSet = original.tailSet("2", false);

subSet()

The subSet() method 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 a Java NavigableSet subSet() 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);

ceiling()

The ceiling() method 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 a Java NavigableSet ceiling() example:

NavigableSet original = new TreeSet();
original.add("1");
original.add("3");
original.add("5");

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

floor()

The floor() method does the opposite of the ceiling() method, meaning it returns the greatest element that is less than or equal to the given parameter value. Here is a Java NavigableSet floor() example:

NavigableSet original = new TreeSet();
original.add("1");
original.add("3");
original.add("5");

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

higher()

The higher() method 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 a Java NavigableSet higher() example:

NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");


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

lower()

The lower() method does the opposite of the higher() method, meaning it returns the highest element that is less than (not equal to) the given parameter. Here is a Java NavigableSet lower() example:

NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");

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

pollFirst()

The pollFirst() method returns and removes the "first" element in the NavigableSet or null if the set is empty. "First" means smallest element according to the sort order of the set. Here is a Java NavigableSet pollFirst() example:

NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");


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

pollLast()

The pollLast() method returns and removes the "last" element in the NavigableSet. "Last" means largest according to the element sorting order of the set. Here is a Java NavigableSet pollLast() example:

NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");

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

Jakob Jenkov




Copyright  Jenkov Aps
Close TOC