CodingBison

A NavigableSet interface is one of the widely used Collection interfaces. As shown the figure below, a NavigableMap interface extends both Map and SortedMap interfaces; accordingly, it inherits all the operations from both of these interfaces. It is highly recommended that one should go through the Map Interface and SortedMap Interface. before getting into the details of a NavigableMap interface.



Figure: Map Interfaces and Classes

Things To Remember
The ascending method is not available for NavigableMap since a SortedMap, by default is ordered in a natural ordering. The method descending reverses the order.

NavigableMap inherits all the basic/fundamental concepts from a Map and SortedMap, so like Map and SortedMap, a NavigableMap does not allow duplicate Keys, this means a NavigableMap cannot have two keys say, key1 and key2 where key1.equals(key2) is true. It also inherits the feature of "Sorting" from the SortedMap interface.

You may ask that how different is NavigableMap compared to SortedMap? Here is the answer. A NavigableMap, as the name suggests brings in the extra features that helps in navigating a SortedMap. Navigating features like descending order, ceiling, pollFirst, pollLast etc. The class that implements NavigableMap interface is a TreeMap.

Methods defined in NavigableMap interface

While the NavigableMap interface inherits all the methods from the Map and SortedMap interface, it also brings in the extra features of navigation to a SortedMap. So, NavigableMap interface defines additional methods on top of the ones inherited from Map and SortedMap interfaces. The below table has the list of the methods that are defined by the interface NavigableMap. You can imagine this table to be an extension of the table Map Interface Methods List and SortedMap Interface Methods.


Table: Methods defined by NavigableMap Interface
MethodDescription
<k key> ceiling(k key)Returns the least key in this Map (the one invokes this method) greater than or equal to the given key. Returns null if there is no such key in the map.
<k key, v value> ceilingEntry(k key)Returns the (key,value) pair from the Map (the one that invokes this method), where the "key" is greater than or equal to the given key (passed as the parameter). Returns null if there is no such key in the map.
NavigableSet descendingKeySet()Returns a reverse order "NavigableSet" view of the keys contained in this Map (the one that invokes this method) in descending order.
NavigableMap descendingMap()Returns a reverse order view of this Map (the one that invokes this method) in descending order.
NavigableMap headMap(k Key, bool inclusive)Returns the view of the Map, whose keys are less (or equal to, if inclusive is true) than the "key" passed as the parameter
<k Key> higherKey(k Key)Returns the least Key in this Map (the one that invokes this method) that is strictly greater than the given key (passed as the parameter). Returns null if there is no such element.
<k key, v value> higherEntry(k Key)Returns the least (key,value) pair in this Map (the one that invokes this method) that is strictly greater than the given key (passed as the parameter). Returns null if there is no such key.
<k key, v value> lastEntry()Returns the (key,value) pair associated with greatest Key in this Map (the one that invokes this method)
<k Key> lowerKey(k Key)Returns the greatest "key" in this Map (the one that invokes this method) that is strictly lesser than the given key (passed as the parameter). Returns null if there is no such element.
<k key, v value> lastEntry(k Key)Returns the greatest (key,value) pair in this Map (the one that invokes this method) that is strictly lesser than the given key (passed as the parameter). Returns null if there is no such key.
NavigableSet navigableKeySet()Returns "NavigableSet" view of the keys contained in this Map (the one that invokes this method).
<k key, v value> pollFirstEntry()Returns and removes the map entry, associated with the least Key in the Map (the one that invokes this method). Returns null if the Map is empty.
<k key, v value> pollLastEntry()Returns and removes the map entry, associated with the greatest Key in the Map (the one that invokes this method). Returns null if the Map is empty.
SortedMap tailMap(E element, bool inclusive)Returns the view of the Map, whose keys are greater than (or equal to if inclusive is true) the "key" passed as the parameter
SortedMap subMap(k key1, bool inclusive, k key2, bool inclusive)Returns the view of the Set, whose elements in the range of "key1" and "key2" (if inclusive true, includes the passed keys) that are passed as parameters

Like shown in the above figure, NavigableMap extends the SortedMap interface and the class that implements these interfaces is a "TreeMap"; more details about TreeMap class available here: Understanding TreeMap. Here is an example program that demonstrates the usage of all the above mentioned operations. The example have used TreeMap and demonstrated the usage of the methods defined by the NavigableMap interface.

 import java.util.TreeMap;

 public class NavigableMapDemo {
     public static void main(String[] args) {
         TreeMap tmapObj = new TreeMap();

         tmapObj.put(1237,"John");
         tmapObj.put(2013,"Ray");
         tmapObj.put(1024,"Mike");
         //tmapObj1.put("1","Chris");

         System.out.println(" TreeMap: " + tmapObj);
         System.out.println(" TreeMap (Descending order): " 
                            + tmapObj.descendingMap());
         System.out.println(" All Key Related Api's");
         System.out.println(" \t Ceiling: " 
                            + tmapObj.ceilingKey(1024)
                            + " Higher: " 
                            + tmapObj.higherKey(1024)
                            + " Lower: " 
                            + tmapObj.lowerKey(1024)
                            + " Floor: "
                            + tmapObj.floorKey(1024));
         System.out.println(" All Entry Related Api's");
         System.out.println(" \t Ceiling: " 
                            + tmapObj.ceilingEntry(1024)
                            + " Higher: " 
                            + tmapObj.higherEntry(1024)
                            + " Lower: " 
                            + tmapObj.lowerEntry(1024)
                            + " Floor: "
                            + tmapObj.floorEntry(1024)
                            + "\n\t Poll-First: "
                            + tmapObj.pollFirstEntry()
                            + " Poll-Last: "
                            + tmapObj.pollLastEntry());
         System.out.println(" TreeMap (After poll first/last): " 
                            + tmapObj.descendingMap());
     }
 }
Things To Remember
All the keys in a NavigableMap must be mutually comparable, which implies, key1.compareTo(key2) or comparator.compare(key1, key2) must not throw "ClassCastException"

The above program demonstrates quite a few important properties of the NavigableMap interface. Notice the output below, all the Keys of the Map are in sorted order. This is the basic difference between a Map vs SortedMap (this is also the property of a NavigableMap because, NavigableMap extends SortedMap).

The above program demonstrates yet another important property of the NavigableMap interface. If you notice the tmapObj, the keys of the SortedMap are mutually comparable. Which implies, key1.compareTo(key2) or comparator.compare(key1, key2) must not throw "ClassCastException". If we were to uncomment the commented line "tmapObj1.put("1","Chris");" in the above program and try to run it! The example program would throw "java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer" exception.

Let us compile/run the program and print the output. The output demonstrates the usage of other NavigableMap methods like ceiling, higher, pollFirst, pollLast, floor.

  TreeMap: {1024=Mike, 1237=John, 2013=Ray}
  TreeMap (Descending order): {2013=Ray, 1237=John, 1024=Mike}
  All Key Related Api's
  	 Ceiling: 1024 Higher: 1237 Lower: null Floor: 1024
  All Entry Related Api's
  	 Ceiling: 1024=Mike Higher: 1237=John Lower: null Floor: 1024=Mike
 	 Poll-First: 1024=Mike Poll-Last: 2013=Ray
  TreeMap (After poll first/last): {1237=John}




comments powered by Disqus