Navigable collections in Java

Java's collection framework is a very large subject. We can find there collections sorted by natural key name, containing only single element of given value, able to be extended thanks to no-fixed size needed at initialization. We can find there also collections considered as navigable.

In this article we'll talk about navigable collections: NavigableMap and NavigableSet. At the begin, we'll see the specificity of these two classes. The second part will present the particularities of navigable collections in general.

Navigable collections in Java

Normally, the collections need to be traversed from the first element, before we can find the interesting element (or subset of elements). For example imagine that we have a Map where years are the keys and a List<Person> values. The values correspond to the people born in given year. If we want to find who was born between 1980 and 1982, we can make following loop:

int startYear = 1980;
int endYear = 1982;
List<Person> borns = new ArrayList<>();
Map<Integer, List<Person>> births = new HashMap<Integer, List<Person>>();
for (int year = startYear; year <= endYear; year++) {
  borns.addAll(births.get(year)); 
} 

But there're more elegant ways to make this operation. One of them is already provided with Java's navigable objects, so we don't need to reinvent the wheel. To translate this situation in the case of NavigableMap use, we could receive one-line snippet:

NavigableMap<Integer, List<Person>> births = new TreeMap<Integer, List<Person>>();
SortedMap<Integer, List<Person>> birthsInYear = births.subMap(1980, 1982); 

Thanks to this example we can already deduce that the main purpose of navigable objects is flexible collections reading. We can get only one subset of given elements, the entry which is the closest to searched value etc. You can find full list of features in below list:

NavigableMap and NavigableSet in Java

To illustrate previously presented methods we'll write a test case. This test case will manipulate soccer team:

public class NavigableSoccerTeam {

  @Test
  public void test() {
    NavigableMap<Integer, String> team = new TreeMap<>();
    team.put(1, "Goalkeeper");
    team.put(2, "Defender (right side)");
    team.put(3, "Defender (central side)");
    team.put(4, "Defender (central side)");
    team.put(5, "Defender (left side)");
    team.put(6, "Defensive midfielder");
    team.put(7, "Offensive midfielder (right side)");
    team.put(8, "Offensive midfielder (left side)");
    team.put(9, "Central striker");
    team.put(10, "Playmaker");
    team.put(11, "Central midfielder");

    int[] expectedNr = {11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    NavigableMap<Integer, String> descending = team.descendingMap();
    int i = 0;
    for (Map.Entry<Integer, String> entry : descending.entrySet()) {
        assertEquals("After descending ordering the read value should be "+expectedNr[i]+" but was "+entry.getKey(),
                entry.getKey().intValue(), expectedNr[i]);
        i++;
    }
     /**
      * In Javadoc you can learn that descending map and original map are associated. The changes 
      * made from one side are visible in the other side:
      * <quote>
      * The descending map is backed by this map, so changes to the map are reflected in the descending map, and vice-versa.
      * </quote>
      */
    descending.put(10, "Playmaker (as Zidane)");
    assertEquals("The 10th entry from descending map should be 'Playmaker (as Zidane)' but was "+descending.get(10),
            descending.get(10), "Playmaker (as Zidane)");
    assertEquals("The 10th entry from both maps should be the same", descending.get(10), team.get(10));

    // Imagine that we need only field players (without goalkeeper).
    SortedMap<Integer, String> fieldPlayers = team.subMap(2, 11);
    i = 0;
    int[] expectedPlayers = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    for (Map.Entry<Integer, String> player : fieldPlayers.entrySet()) {
        assertEquals("Field player ("+player.getKey()+") is not the same as expected ("+expectedPlayers[i]+")"
                , expectedPlayers[i], player.getKey().intValue());
        i++;
    }
    System.out.println("Field player are: "+fieldPlayers);
    // This sample shows how to get only goalkeeper in different ways
    Map.Entry<Integer, String> goalkeeper = team.firstEntry();
    assertEquals("Goalkeeper should be "+team.get(1)+" but is "+goalkeeper.getValue(), team.get(1), goalkeeper.getValue());

    SortedMap<Integer, String> goalkeepers = team.headMap(2);
    assertEquals("1 goalkeeper should be found but "+goalkeepers.size()+" were instead", goalkeepers.size(), 1);

    Map.Entry<Integer, String> goalkeeperRemoved = team.pollFirstEntry();
    assertNotNull("Goalkeeper retrieved with pollFirstEntry() shouldn't be null", goalkeeperRemoved);
    assertEquals("Goalkeeper should be "+goalkeeper.getValue()+" but is "+goalkeeperRemoved.getValue(), goalkeeper.getValue(),
            goalkeeperRemoved.getValue());
    assertTrue("Team shouldn't contain goalkeeper anymore", !team.containsKey(1));

    // reset goalkeeper
    team.put(goalkeeperRemoved.getKey(), goalkeeperRemoved.getValue());
    assertTrue("Team should contain goalkeeper", team.containsKey(1));

    // get only offensive players with exclusive flag
    SortedMap<Integer, String> offensivePlayers = team.tailMap(6, false);
    int[] expectedOffensive = {7, 8, 9, 10, 11};
    i = 0;
    for (Map.Entry<Integer, String> player : offensivePlayers.entrySet()) {
        assertEquals("Field player ("+player.getKey()+") is not the same as expected ("+expectedOffensive[i]+")"
                , expectedOffensive[i], player.getKey().intValue());
        i++;
    }

    // first value lower value to 7
    Map.Entry<Integer, String> defensiveMidfielder = team.lowerEntry(7);
    System.out.println("defensiveMidfielder: "+defensiveMidfielder);
    assertEquals("Defensive midfielder should have number 6 but has "+defensiveMidfielder.getKey(),
            defensiveMidfielder.getKey().intValue(), 6);

    // first value greater to 9
    Map.Entry<Integer, String> playmaker = team.higherEntry(9);
    System.out.println("Playmaker: "+playmaker);
    assertEquals("Playmaker should have number 10 but has "+playmaker.getKey(), playmaker.getKey().intValue(), 10);

    // first value greater or equal to 10
    Map.Entry<Integer, String> playmakerCeil = team.ceilingEntry(10);
    System.out.println("Playmaker from ceil: " + playmakerCeil);
    assertEquals("Playmaker from ceil should have number 10 but has " + playmakerCeil.getKey(), playmakerCeil.getKey().intValue(), 10);
    team.remove(10);
    playmakerCeil = team.ceilingEntry(10);
    System.out.println("Playmaker from ceil: " + playmakerCeil);
    assertEquals("Playmaker from ceil should have number 11 but has " + playmakerCeil.getKey(),
            playmakerCeil.getKey().intValue(), 11);

    // first value lower or equal to 3
    Map.Entry<Integer, String> defenderFloor = team.floorEntry(3);
    System.out.println("Defender from floor: "+defenderFloor);
    assertEquals("Defender from floor should have number 3 but has " + defenderFloor.getKey(),
            defenderFloor.getKey().intValue(), 3);
    team.remove(3);
    defenderFloor = team.floorEntry(3);
    System.out.println("Defender from floor: "+defenderFloor);
    assertEquals("Defender from floor should have number 2 but has " + defenderFloor.getKey(),
            defenderFloor.getKey().intValue(), 2);
  }

}

This article described the specificity of navigable map in Java. The first part listed some of important methods belonging to this class. We discovered how to access directly the first or the last element, or even how to find an entry with the closest value to desired parameter. The second part shown illustrated how to use navigable features in the case of sample Java class.

The comments are moderated. I publish them when I answer, so don't worry if you don't see yours immediately :)

📚 Newsletter Get new posts, recommended reading and other exclusive information every week. SPAM free - no 3rd party ads, only the information about waitingforcode!