Fun with TreeMap

TreeMap is the only implementation of a SortedMap that is included in the JDK. It stores its values in a Red-black tree, therefore its entries can be accessed, inserted and deleted really fast.

Unfortunately, using the class is not really intuitive, so you better read the API docs carefully or prepare to spend hours of your time chasing mysterious bugs.

Imagine that you want to use a TreeMap with String keys and String values that is ordered according to the length of the key in a way so that the longest key comes first. Should be quite simple, just implement a comparator that does the work for you:

import java.util.Comparator;

public class StringLengthComparator implements Comparator<String> {

    public int compare(String o1, String o2) {
        // if both lengths are the same return 0
        return o2.length() - o1.length();
    }
}

If both Strings have the same length we return 0 and a negative or positive value otherwise. As I always get confused when to return a positive value and when a negative let's create a simple test:

    Map<String, String> map;
    
    @Before
    public void setUp() {
        map = new TreeMap<String, String>(new StringLengthComparator());
    }
    
    @Test
    public void testValuesWithDifferentLength() {

        map.put("zero", "0");
        map.put("one", "1");
        map.put("three", "3");

        assertThat("Length failed", map.size(), is(3));

        Iterator<String> it = map.keySet().iterator();
        assertThat(it.next(), is("three"));
        assertThat(it.next(), is("zero"));
        assertThat(it.next(), is("one"));
    }

If we run this test everything seems to be ok;

Testsuite: StringLengthComparatorTest
Tests run: 1, Failures: 0, Errors: 0, Time elapsed: 0,018 sec

But what happens if we just insert the missing two? Lets see:

    @Test
    public void testDifferentValuesWithSameLength() {

        map.put("zero", "0");
        map.put("one", "1");
        map.put("two", "2");
        map.put("three", "3");

        assertThat("Length failed", map.size(), is(4));

        Iterator<String> it = map.keySet().iterator();
        // just check the first two values as we do not know the order of the same length
        assertThat(it.next(), is("three"));
        assertThat(it.next(), is("zero"));
    }

This test should also pass, we just can't tell the ordering of the same length keys:

Testcase: testDifferentValuesWithSameLength(StringLengthComparatorTest):        FAILED
Length failed
Expected: is <4>
     got: <3>

Oops ... what happened here? One of the values just disappeared? We are inserting 4 entries but there are only 3 in the Map?

The first time I stumbled across this it took me several hours to figure out what was going on. After I found out what the problem was it should have taught me to always read the javadoc carefully. The contract for TreeMap states the following:

Note that the ordering maintained by a sorted map (whether or not an explicit comparator is provided) must be consistent with equals if this sorted map is to correctly implement the Map interface.

What exactly does this mean? Comparator tells us more about consistent with equals:

The ordering imposed by a comparator c on a set of elements S is said to be consistent with equals if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 and e2 in S.

Normally, the Map- and Set-Interface use equals to determine if a certain key (for a Map) or a certain value (for a Set) is already inserted. But for TreeMap and TreeSet this is not the case. These implementations use compareTo for determining whether an Object is equal to another Object. This means you are not allowed to return 0 from a compare-method if the two Objects are not equal!

How to fix it? Just test if the two Strings are equal before comparing the length in the Comparator:

    public int compare(String o1, String o2) {

        // return 0 only if both are equal
        if (o1.equals(o2)) {
            return 0;
        } else if (o1.length() > o2.length()) {
            return -1;
        } else {
            return 1;
        }
    }

Alright, the test passes. Just to be sure we add another test:

    @Test
    public void testYetMoreValues() {

        map.put("zero", "0");
        map.put("one", "1");
        map.put("four", "4");

        assertThat("Length failed", map.size(), is(3));

        assertNotNull("Zero's not there", map.get("zero"));
    }

Seems to be a stupid test but let's see what happens:

Testsuite: StringLengthComparatorTest
Tests run: 3, Failures: 1, Errors: 0, Time elapsed: 0,027 sec

Testcase: testYetMoreValues(StringLengthComparatorTest):        FAILED
Zero's not there
junit.framework.AssertionFailedError: Zero's not there
        at StringLengthComparatorTest.testYetMoreValues(StringLengthComparatorTest.java:51)

How can this happen? We tested for equality but the "zero" value still is not there? Let's see what the tree looks like on every step.

Still simple if the first value ("zero") is inserted: The entry is the root node:

When inserting "one" afterwards, the Comparator tells that the result of the comparison is 1, which means that the node has to be inserted on the right side:

When inserting "four", the tree looks a little bit different. As our Comparator in this case also return 1, the node is also inserted right of "zero" but needs to be left of "one". "four" is our new root node:

Seems to look ok. When reading from left to right the nodes are sorted according to their length. But let's see what happens when we try to look up "zero" based on the tree above. We start with the root node "four". As the length of "zero" and "four" is the same, our Comparator returns 1. But on the right side it only finds the "one" node. Our comparator returns -1 when comparing "four" to "one". Nothing there, so null is returned.

The Javadoc for Comparator tells us more on what went wrong here:

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.

This means that the method needs to be implemented symetrically. When calling compare("zero", "one") we always need to return the negated value of calling compare("one", "zero"). With our implementation this is not the case as we always return 1 as a fallback.

I hope this is a final implementation of the Comparator delegating to Strings compareTo()-method which is already implemented symetrically:

    public int compare(String o1, String o2) {

        // return 0 only if both are equal
        if (o1.equals(o2)) {
            return 0;
        } else if (o1.length() == o2.length()) {
            // delegate to Strings compareTo to get symmetric behavior
            return o1.compareTo(o2);
        } else if (o1.length() > o2.length()) {
            return -1;
        } else {
            return 1;
        }
    }

I struggled with both of these problems on two different projects and it always took me some hours. Thanks to my colleague Marc who led me to the solution of the symmetric problem.

Implementing an API abstraction using Google Collections

I am using OpenCms, the open source content management system, quite often. It is a good choice for building structured medium to large sized websites. One drawback though sometimes is the layout of the APIs. E.g. for accessing the resources managed in the system programatically you have to use some final and nonfinal classes that depend on a running instance of OpenCms. The original developers very likely chose this approach for security reasons but this can become quite cumbersome, e.g. when dealing with tests, as you cannot mock some of these classes easily. There is an integration test facility that comes with OpenCms but as this starts an OpenCms instance every time a test is executed, running tests takes some time. I tend to write tests that work without a running system whenever possible.

To improve testability of my components I implemented a thin layer above the normal OpenCms access means using some interfaces and simple POJOs so that my business logic can be tested without starting OpenCms. One interface and its default implementation act as a kind of DAO for accessing the virtual filesystem of OpenCms. Its method signatures do not contain any OpenCms dependencies that can't be mocked or reconstructed easily. E.g. to represent file resources the OpenCms class normally used is CmsResource. This class is quite difficult to instanciate outside of a running OpenCms instance as it contains internal references to different database tables. To reduce the need for mocking these external classes I implemented a simple POJO, Resource, that contains relevant information like the path to the resource and it's type.

Some methods of my VFS DAO return a Collection of Resources, e.g. when reading all resources in a subfolder. As the OpenCms API returns an untyped List that contains CmsResources and in my interface method signature I use List<? extends Resource> some transformation needs to take place. In the first project I used the abstraction I implemented it in a really simple way:

List<Resource> resources = new ArrayList<Resource>();
@SupressWarnings("Unchecked")
List<CmsResources> cmsResources = cms.readResources(...);
for (CmsResource cmsResource: cmsResources) {
 resources.add(transform(cmsResource);
}

The transform method just creates an instance of the Resource and fills it with the needed values.

private Resource transform(CmsResource cmsResource) {
 Resource resource = new Resource();
 resource.setDateLastModified(cmsResource.getDateLastModified());
 ...
 return resource;
}

This approach works and in my opinion is ok to use in many circumstances. I sacrificed some performance for a gain in testability and design. But for large collections or operations that are triggered frequently this of course can become a performance issue as for the sake of abstraction it is necessary to iterate the collection.

The better solution is to use a lazy list that transforms the CmsResources on the fly to Resources. With a lazy list you don't have to iterate it when transforming. The transformation happens when you are accessing the list.

Google Collections provides a functional style approach for transforming lists lazily. You create a class that implements the interface Function that can be typed for the source and target. In its apply method the transformation step is implemented in basically the same way as in the method displayed above.

public class ResourceTransformationFunction implements Function {

   public Resource apply(CmsResource cmsResource) {
       Resource resource = new Resource();
       resource.setDateCreated(cmsResource.getDateCreated());
       resource.setDateLastModified(cmsResource.getDateLastModified());
       ...
       return resource;
   }
}

The original List is transfomed using a static method call that accepts an instance of our Function:

@SuppressWarnings("unchecked")
List<CmsResource> cmsResources = cms.readResources(...);
List<Resource> resources =  Lists.transform(cmsResources, new ResourceTransformationFunction());

The transformation happens when the List is accessed so when you are iterating the collection only once, which should be the case in most applications, there is no overhead at all (besides the creation of the new objects).

I really like the ease of use and reusabilty of the Google Collections solution. Also, the jar comes with absolutely no dependencies which makes it easily embedabble in any project.

A similiar functional approach will be part of the new concurrency features in JDK 7. ParallelArray, which makes use of the Fork/Join framework will provide the ability to use functions and predicates when constructing arrays. Brian Goetz' talk on Devoxx 2008 contained a detailed introduction to these features.

On Devoxx 2009, Dick Wall of the Javaposse held a really good talk about appliying a more functional style of programming to the Java programming language. This talk will be available some time in the future at parleys.com