Apache Commons Collections OrderedMap

1. Overview

The Apache Commons Collections library provides useful classes that complement the Java Collections Framework.

In this article, we will review the interface OrderedMap, which extends java.util.Map.

2. Maven Dependency

The first thing we need to do is to add the Maven dependency in our pom.xml :

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-collections4</artifactId>
    <version>4.5.0-M2</version>
</dependency>

You can find the latest version of the library on the Maven Central repository.

3. OrderedMap Properties

Simply put, a map that implements the OrderedMap interface:

• Maintains order in its set of keys, although the set isn’t sorted
• Can be iterated over in both directions with methods: firstKey() and nextKey(), or lastKey() and previousKey()
• Can be traversed with a MapIterator (also provided by the library)
• Provides methods to find, alter, remove, or replace elements

4. Using OrderedMap

Let’s set up an OrderedMap of runners and their ages in a test class. We will use a LinkedMap – one of the OrderedMap implementations provided in the library.

First, let’s set up arrays of runners and ages that we will use to load the map and verify the order of the values:

public class OrderMapUnitTest {
    private String[] names = {"Emily", "Mathew", "Rose", "John", "Anna"};
    private Integer[] ages = {37, 28, 40, 36, 21};
    private LinkedMap<String, Integer> runnersLinkedMap;
 
    //...
}

Now, let’s initialize our map:

@Before
public void createRunners() {
    this.runnersLinkedMap = new LinkedMap<>();
    
    for (int i = 0; i < RUNNERS_COUNT; i++) {
        runners.put(this.names[i], this.ages[i]);
    }
}

4.1. Forward Iteration

Let’s see how the forward iterator is used:

@Test
public void givenALinkedMap_whenIteratedForwards_thenPreservesOrder() {
    String name = this.runnersLinkedMap.firstKey();
    int i = 0;
    while (name != null) {
        assertEquals(name, names[i]);
        name = this.runnersLinkedMap.nextKey(name);
        i++;
    }
}

Note that when we have reached the last key, the method nextKey() will return a null value.

4.2. Backward Iteration

Now let’s iterate back, starting with the last key:

@Test
public void givenALinkedMap_whenIteratedBackwards_thenPreservesOrder() {
    String name = this.runnersLinkedMap.lastKey();
    int i = RUNNERS_COUNT - 1;
    while (name != null) {
        assertEquals(name, this.names[i]);
        name = this.runnersLinkedMap.previousKey(name);
        i--;
    }
}

Once we reach the first key, the previousKey() method will return null.

4.3. MapIterator Example

Now let’s use the mapIterator() method to obtain a MapIterator as we show how it preserves the order of runners as defined in the arrays names and ages:

@Test
public void givenALinkedMap_whenIteratedWithMapIterator_thenPreservesOrder() {
    OrderedMapIterator<String, Integer> runnersIterator 
      = this.runnersLinkedMap.mapIterator();
    
    int i = 0;
    while (runnersIterator.hasNext()) {
        runnersIterator.next();
 
        assertEquals(runnersIterator.getKey(), this.names[i]);
        assertEquals(runnersIterator.getValue(), this.ages[i]);
        i++;
    }
}

4.4. Removing Elements

Finally, let’s check how an element can be removed by index or by object:

@Test
public void givenALinkedMap_whenElementRemoved_thenSizeDecrease() {
    LinkedMap<String, Integer> lmap 
      = (LinkedMap<String, Integer>) this.runnersLinkedMap;
    
    Integer johnAge = lmap.remove("John");
 
    assertEquals(johnAge, new Integer(36));
    assertEquals(lmap.size(), RUNNERS_COUNT - 1);

    Integer emilyAge = lmap.remove(0);
 
    assertEquals(emilyAge, new Integer(37));
    assertEquals(lmap.size(), RUNNERS_COUNT - 2);
}

5. Provided Implementations

Currently, in version 4.1 of the library, there are two implementations of the OrderedMap interface – ListOrderedMap and LinkedMap.

ListOrderedMap keeps track of the order of the key set using a java.util.List. It is a decorator of OrderedMap and can be created from any Map by using the static method ListOrderedMap.decorate(Map map).

LinkedMap is based on a HashMap and improves on it by allowing bidirectional iteration and the other methods of the OrderedMap interface.

Both implementations also provide three methods that are outside the OrderedMap interface:

• asList() – obtains a list of type List<K> (where K is the type of the keys) preserving the order of the map
• get(int index) – gets the element at position index as opposed to method get(Object o) provided in the interface
• indexOf(Object o) – gets the index of the object o in the ordered map

We can cast the OrderedMap into a LinkedMap to use asList() method:

@Test
public void givenALinkedMap_whenConvertedToList_thenMatchesKeySet() {
    LinkedMap<String, Integer> lmap 
      = (LinkedMap<String, Integer>) this.runnersLinkedMap;
    
    List<String> listKeys = new ArrayList<>();
    listKeys.addAll(this.runnersLinkedMap.keySet());
    List<String> linkedMap = lmap.asList();
 
    assertEquals(listKeys, linkedMap);
}

Then we can check the functioning of method indexOf(Object o) and get(int index) in the LinkedMap implementation:

@Test
public void givenALinkedMap_whenSearchByIndexIsUsed_thenMatchesConstantArray() {
    LinkedMap<String, Integer> lmap 
      = (LinkedMap<String, Integer>) this.runnersLinkedMap;
    
    for (int i = 0; i < RUNNERS_COUNT; i++) {
        String name = lmap.get(i);
 
        assertEquals(name, this.names[i]);
        assertEquals(lmap.indexOf(this.names[i]), i);
    }
}

6. Conclusion

In this quick tutorial, we’ve reviewed the OrderedMap interface and its primary methods and implementations.

For further information, see the JavaDoc of the Apache Commons Collections library.