JDD conference is behind us. We had a great time doing a github dev contest (Chief Troublemaker Officer) for conference attendees. Some guys complained that the contest was too hard, good to hear! It was out intention not to make it too trivial.

We received less than 10 solutions. The Jury had a hard time doing Code Review, it wasn’t easy to agree which one is the best.

Three solutions were really good and to be honest, equally good. We decided not to draw lots, and choose the winner by delivery date.

So the winner is …

Maciek Prokopiuk - http://github.com/mcprok/jdd-14-dev-contest

Congrats! Hope that you will enjoy your new Nexus 7 :)

Maciek’s solution

package pl.allegro.jdd;

import com.google.common.collect.MapDifference;
import com.google.common.collect.Maps;
import com.google.common.collect.TreeTraverser;
import java.util.Map;
import static com.google.common.base.Preconditions.checkNotNull;

public class StructureDiff {
    public Changes calculate(Employee oldCTO, Employee newCTO){
        checkNotNull(oldCTO);
        checkNotNull(newCTO);

        TreeTraverser<Employee> treeTraverser = new TreeTraverser<Employee>() {
            @Override
            public Iterable<Employee> children(Employee employee) {
                return employee.getSubordinates();
            }
        };

        Map oldEmployees = treeTraverser.breadthFirstTraversal(oldCTO).toMap(Employee::getSalary);
        Map newEmployees = treeTraverser.breadthFirstTraversal(newCTO).toMap(Employee::getSalary);

        MapDifference diff = Maps.difference(oldEmployees, newEmployees);

        return new Changes(
                diff.entriesOnlyOnLeft().keySet(),
                diff.entriesOnlyOnRight().keySet(),
                diff.entriesDiffering().keySet()
        );
    }
}

What we like:

  • very clean and readable code
  • Guava to the rescue, usage of the right tool
  • usage of Java8 method reference Employee::getSalary

And the next two, equally good solutions, delivered later. Both guys were rewarded with Dice+ cubes.

What are the other options

Guava is the right tool to solve the problem but it has some limitations. First, you can compare only generic structures (like Maps), so the original object structure (tree in this case) has to be transformed into a Map.

In the Map, keys are Employees and values are their salary. It works well, but what if we think about adding and comparing more fields to Employee class? Things goes also harder when we think about tracking changes on boss-subordinates relation.

What we like to recommend is JaVers, a dedicated tool for calculating an object diff on complex data structures.

JaVers solution:

Add javers-core to project dependencies:

compile 'org.javers:javers-core:0.8.5'

StructureDiff.java

package pl.allegro.jdd;

import org.javers.core.Javers;
import org.javers.core.JaversBuilder;
import org.javers.core.diff.Diff;
import org.javers.core.diff.changetype.NewObject;
import org.javers.core.diff.changetype.ObjectRemoved;
import static com.google.common.base.Preconditions.checkNotNull;

public class StructureDiff {
    public Changes calculate(Employee oldCTO, Employee newCTO){
        checkNotNull(oldCTO);
        checkNotNull(newCTO);

        Javers javers = JaversBuilder.javers().build();
        Diff diff = javers.compare(oldCTO, newCTO);

        return new Changes(diff.getObjectsByChangeType(ObjectRemoved.class),
                           diff.getObjectsByChangeType(NewObject.class),
                           diff.getObjectsWithChangedProperty("salary"));
    }
}

As you can see, there is no data structures manipulation here. Just provide two handles to your graphs of objects and JaVers will calculate the diff.