Chapter 47: Searching TreeSets and TreeMaps

We spoke about searching lists and arrays in a previous chapter. We have seen Sets and Maps in the previous chapters and how to use them. So you might probably be pondering over a question that might sound like “Do Sets and Maps have options to search for stuff”. Well, if you had such a question lurk in your mind, this chapter is going to give you the answer.

So, lets get Started!!!

Searching TreeSets and TreeMaps

Let’s turn our attention to searching TreeSets and TreeMaps. Java 6 introduced two new interfaces: java.util.NavigableSet and java.util.NavigableMap. For the purposes of the exam, you’re interested in how TreeSet and TreeMap implement these interfaces.

Imagine that the Singapore-Sentosa ferry has an irregular schedule. Let’s say that we have the daily ferry departure times stored, in military time, in a TreeSet. Let’s look at some code that determines two things:

1. The last ferry that leaves before 4 PM (1600 hours)
2. The first ferry that leaves after 8 PM (2000 hours)

import java.util.*;
public class FerryExample {
public static void main(String[] args) {
TreeSet times = new TreeSet();
times.add(1205); // add some departure times
times.add(1505);
times.add(1545);
times.add(1830);
times.add(2010);
times.add(2100);
// Java 5 version

TreeSet subset = new TreeSet();
subset = (TreeSet)times.headSet(1600);
System.out.println("J5 - last before 4pm is: " + subset.last());

TreeSet sub2 = new TreeSet();
sub2 = (TreeSet)times.tailSet(2000);
System.out.println("J5 - first after 8pm is: " + sub2.first());

// Java 6 version using the new lower() and higher() methods

System.out.println("J6 - last before 4pm is: " + times.lower(1600));
System.out.println("J6 - first after 8pm is: " + times.higher(2000));
}
}

This should produce the following:

J5 - last before 4pm is: 1545
J5 - first after 8pm is: 2010
J6 - last before 4pm is: 1545
J6 - first after 8pm is: 2010

As you can see in the preceding code, before the addition of the NavigableSet interface, zeroing in on an arbitrary spot in a Set—using the methods available in Java 5—was a compute-expensive and clunky proposition. On the other hand, using the new Java 6 methods lower() and higher(), the code becomes a lot cleaner.

For the purpose of the exam, the NavigableSet methods related to this type of navigation are lower(), floor(), higher(), ceiling(), and the mostly parallel NavigableMap methods are lowerKey(), floorKey(), ceilingKey(), and higherKey(). The difference between lower() and floor() is that lower() returns the element less than the given element, and floor() returns the element less than or equal to the given element. Similarly, higher() returns the element greater than the given element, and ceiling() returns the element greater than or equal to the given element.

Below is a Table that summarises the important methods that you need to know for the exam:

Method Name	Method Description/Purpose
TreeSet.ceiling(e)	Returns the lowest element >= e
TreeMap.ceilingKey(key)	Returns the lowest key >= key
TreeSet.higher(e)	Returns the lowest element > e
TreeMap.higherKey(key)	Returns the lowest key > key
TreeSet.floor(e)	Returns the highest element <= e
TreeMap.floorKey(key)	Returns the highest key <= key
TreeSet.lower(e)	Returns the highest element < e
TreeMap.lowerKey(key)	Returns the highest key < key
TreeSet.pollFirst()	Returns and removes the first entry
TreeMap.pollFirstEntry()	Returns and removes the first key-value pair
TreeSet.pollLast()	Returns and removes the last entry
TreeMap.pollLastEntry()	Returns and removes the last key-value pair
TreeSet.descendingSet()	Returns a NavigableSet in reverse order
TreeMap.descendingMap()	Returns a NavigableMap in reverse order

Other Navigation Methods

In addition to the methods we just discussed there are a few more new Java 6 methods that could be considered “navigation” methods.

Polling

Although the idea of polling isn’t new to Java 6, it is new to TreeSet and TreeMap. The idea of polling is that we want both to retrieve and remove an element from either the beginning or the end of a collection. In the case of TreeSet, pollFirst() returns and removes the first entry in the set, and pollLast() returns and removes the last. Similarly, TreeMap now provides pollFirstEntry() and pollLastEntry() to retrieve and remove key-value pairs.

Descending Order

Also new to Java 6 for TreeSet and TreeMap are methods that return a collection in the reverse order of the collection on which the method was invoked. The important methods for the exam are TreeSet.descendingSet() and TreeMap .descendingMap().

Previous Chapter: Chapter 46 - Using Maps

Next Chapter: Chapter 48 - Backed Collections