Java NavigableMap Interface

---

The NavigableMap interface in Java extends the SortedMap interface and provides additional functionality for navigating the entries in a sorted map. It introduces methods for searching for entries relative to a given key and allows you to navigate the map in various ways—either upwards or downwards, providing a more powerful and flexible way to interact with sorted key-value pairs.

While SortedMap gives basic sorting and range methods, NavigableMap adds enhanced functionality to navigate through the map and retrieve keys and values that are "near" a given entry. Implementing classes like TreeMap implement NavigableMap, making it the most commonly used map when key-ordering and navigation are required.

In this article, we will discuss the NavigableMap interface, its key methods, and provide practical examples of how it can be used in your Java projects.

---

What is NavigableMap in Java?

The NavigableMap interface is part of the java.util package and extends SortedMap to provide additional methods for navigating through the sorted map. It allows you to retrieve the closest matches for a given key, find entries greater than or less than a certain key, and perform navigational operations in a map that is already sorted.

Key features of NavigableMap:

• Enhanced Navigation: It provides methods to retrieve keys that are higher or lower than a given key.
• Inclusive and Exclusive Navigation: Methods in NavigableMap allow you to specify whether the navigation should include the given key or exclude it.
• Range Views: It supports operations like subMap(), headMap(), and tailMap() which allow you to create views of specific portions of the map.

---

Core Methods of NavigableMap

The NavigableMap interface provides several methods that enhance navigation and sorting. Here are some of the most important ones:

1. higherKey(K key)

This method returns the first key that is strictly greater than the specified key, or null if no such key exists.

K higherKey(K key);

2. lowerKey(K key)

This method returns the last key that is strictly less than the specified key, or null if no such key exists.

K lowerKey(K key);

3. ceilingKey(K key)

This method returns the least key that is greater than or equal to the specified key, or null if no such key exists.

K ceilingKey(K key);

4. floorKey(K key)

This method returns the greatest key that is less than or equal to the specified key, or null if no such key exists.

K floorKey(K key);

5. pollFirstEntry()

This method retrieves and removes the first (lowest) entry in the map, or returns null if the map is empty.

Map.Entry<K, V> pollFirstEntry();

6. pollLastEntry()

This method retrieves and removes the last (highest) entry in the map, or returns null if the map is empty.

Map.Entry<K, V> pollLastEntry();

7. descendingMap()

This method returns a view of the map with the keys in descending order.

NavigableMap<K, V> descendingMap();

8. subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)

This method returns a view of the portion of the map whose keys are in the specified range. You can specify whether the range should include or exclude the boundary keys.

NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive);

---

Example: Using NavigableMap with TreeMap

TreeMap is the most common implementation of NavigableMap in Java. Below is an example that demonstrates how to use NavigableMap to navigate and manipulate key-value pairs.

import java.util.*;

public class NavigableMapExample {
    public static void main(String[] args) {
        // Create a NavigableMap using TreeMap
        NavigableMap<String, Integer> map = new TreeMap<>();

        // Add some key-value pairs
        map.put("Apple", 3);
        map.put("Banana", 1);
        map.put("Mango", 2);
        map.put("Pineapple", 4);

        // Print the map
        System.out.println("Navigable Map: " + map);

        // Demonstrate navigation methods
        System.out.println("Higher key than Banana: " + map.higherKey("Banana"));  // Output: Mango
        System.out.println("Lower key than Mango: " + map.lowerKey("Mango"));  // Output: Banana
        System.out.println("Ceiling key for 'Grapes': " + map.ceilingKey("Grapes"));  // Output: Mango
        System.out.println("Floor key for 'Grapes': " + map.floorKey("Grapes"));  // Output: Banana

        // Polling first and last entries
        System.out.println("Poll First Entry: " + map.pollFirstEntry());  // Output: Apple=3
        System.out.println("Poll Last Entry: " + map.pollLastEntry());  // Output: Pineapple=4

        // Print the map after polling
        System.out.println("Navigable Map after polling: " + map);

        // Get a descending map
        NavigableMap<String, Integer> descendingMap = map.descendingMap();
        System.out.println("Descending Map: " + descendingMap);

        // Submap example
        NavigableMap<String, Integer> subMap = map.subMap("Banana", true, "Mango", true);
        System.out.println("SubMap (Banana to Mango): " + subMap);
    }
}

Output:

Navigable Map: {Apple=3, Banana=1, Mango=2, Pineapple=4}
Higher key than Banana: Mango
Lower key than Mango: Banana
Ceiling key for 'Grapes': Mango
Floor key for 'Grapes': Banana
Poll First Entry: Apple=3
Poll Last Entry: Pineapple=4
Navigable Map after polling: {Banana=1, Mango=2}
Descending Map: {Mango=2, Banana=1}
SubMap (Banana to Mango): {Banana=1, Mango=2}

Explanation:

• Navigation Methods:

  • higherKey("Banana") returns "Mango", which is the next key after "Banana".
  • lowerKey("Mango") returns "Banana", which is the key before "Mango".
  • ceilingKey("Grapes") returns "Mango" because it is the closest key greater than or equal to "Grapes".
  • floorKey("Grapes") returns "Banana" because it is the closest key less than or equal to "Grapes".

• Polling:

  • pollFirstEntry() removes and returns the first entry ("Apple=3").
  • pollLastEntry() removes and returns the last entry ("Pineapple=4").

• Descending Map: The descendingMap() method returns a map with the entries in reverse order.

• SubMap: The subMap("Banana", true, "Mango", true) method returns a sub-map from "Banana" to "Mango", including both "Banana" and "Mango".

---

When to Use NavigableMap

You should use NavigableMap when:

1. Key Navigation is Required: When you need to find keys that are higher, lower, ceiling, or floor relative to a given key.
2. Ordered Map Operations: When you want to efficiently work with portions of a sorted map, like creating sub-maps or navigating in reverse order.
3. Range Queries: If you need to frequently perform operations like finding ranges of keys or values, NavigableMap provides efficient methods for these tasks.

---

---