Navigable collections in Java on waitingforcode.com

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.

Data Engineering Design Patterns

Looking for a book that defines and solves most common data engineering problems? I'm currently writing one on that topic and the first chapters are already available in 👉 Early Release on the O'Reilly platform

I also help solve your data engineering problems 👉 contact@waitingforcode.com 📩

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:

ceilingEntry(K key) / ceilingKey(K key): returns the smallest key or Map.Entry from the map which is greater or equal to passed key parameter.
descendingKeySet(): returns a set in descending keys order.
descendingMap(): returns a map in descending keys order.
firstEntry() / lastEntry(): returns first or last entry from given collection.
floorEntry(K key) / floorKey(K key): returns the biggest key or Map.Entry from the map which is less or equal to passed key parameter.
higherEntry(K key) / lowerEntry(K key)returns the Map.Entry which higher or lower to used key.
higherKey(K key) / lowerKey(K key): makes the same as higherEntry/lowerEntry but they return map's key.
pollFirstEntry() / pollLastEntry(): removes and returns first or last entry from given collection
subMap(K fromKey, K toKey): allows to get a part of map, delimited by the first and the last parameter of this method. The limitation is inclusive, ie. both parameters will be included in the result. Another method with the same name exists and it accepts two boolean parameters to indicate if keys should be inclusive or not.
tailMap(K fromKey): acts as String.substring method. tailMap allows to get only a portion of given map, beginning by the fromKey method's parameter. As subMap, there're also a second tailMap method which accepts boolean parameter to indicate if fromKey should be exclusive (false) or inclusive (true).
headMap(K toKey): makes reverse operation to tailMap and returns the elements which are present in the map before toKey parameter. There're also a boolean version of this method to indicate if toKey should be inclusive or exclusive.

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.