Wednesday, July 8, 2015

The wonderful world of Java 8's default interface methods

For those of you with experience in Scala, Java 8's default methods in interfaces are no big news. For Java-only folks my guess is, that some may have wondered, why an interface - in its essence a contract between a client and a library - would need to contain implementation details.

I think one of the greatest benefits of default methods is, that functionality can be composed through implementing interfaces, thereby using them as mixins or traits as they are called in Scala.

Today, i would like to share an exemplary use case of default methods when working with tree structures.

Suppose you have the following two classes somewhere in your project...one might be used for the internal representation of your binary-tree data, the other one is used as a DTO for a REST API and also needs to be able to handle non-binary trees.

public class BinaryTree {  
    private final String name;
    private final BinaryTree left;
    private final BinaryTree right;

    public BinaryTree(final String name, final BinaryTree left, final BinaryTree right) {
        this.name = name;
        this.left = left;
        this.right = right;
    }

    public String getName() {
        return name;
    }

    public BinaryTree getLeft() {
        return left;
    }

    public BinaryTree getRight() {
        return right;
    }
}
public class SomeTree {  
    private final String name;
    private final Set<SomeTree> children;

    public SomeTree(final String name, final Set<SomeTree> children) {
        this.name = name;
        this.children = children;
    }

    public String getName() {
        return name;
    }

    public Set<SomeTree> getChildren() {
        return children;
    }
}

Many times when working with tree structures, we need to be able to find nodes somehow. So usually we implement some methods to recursively or iteratively locate the node in question and return it. Since our two tree representations are structurally different, we might think that we need to write a separate method for finding nodes for each of our two types.

Fortunately, we can use Java 8's default methods in interfaces to write just one implementation and mix the interface into both our classes. Note, that this could also have been done using an abstract base class for both our tree classes, but that would mean tighter coupling and worse maintainability, since any class in java can only extend one other class, but implement multiple interfaces.

Thus we continue to create a generic implementation enabling us to find nodes in a tree:

public interface FindableNode {

    String getName();

    <T extends FindableNode> Set<T> getChildren();

    default <T extends FindableNode> Optional<T> findByName(final String name) {
        if (getName().equalsIgnoreCase(name)) {
            return Optional.of((T) this);
        }
        return findByName(getChildren(), name);
    }

    default <T extends FindableNode> Optional<T> findByName(final Set<T> nodes, final String name) {
        final Optional<T> matchingNode = nodes.stream()
                .filter(node -> node.getName().equalsIgnoreCase(name))
                .findAny();
        if (matchingNode.isPresent()) {
            return matchingNode;
        }
        return (Optional<T>) nodes.stream()
                .map(c -> findByName(c.getChildren(), name))
                .filter(Optional::isPresent)
                .map(Optional::get)
                .findFirst();
    }
}

Now all we need to do is to mix our new interface into our two tree classes and provide the required abstract methods getName() and getChildren():

public class BinaryTree implements FindableNode {  
    private final String name;
    private final BinaryTree left;
    private final BinaryTree right;

    public BinaryTree(final String name, final BinaryTree left, final BinaryTree right) {
        this.name = name;
        this.left = left;
        this.right = right;
    }

    @Override
    public String getName() {
        return name;
    }

    @Override
    public Set<BinaryTree> getChildren() {
        final ImmutableSet.Builder<BinaryTree> builder = ImmutableSet.<BinaryTree>builder();
        if (left != null) {
            builder.add(left);
        }
        if (right != null) {
            builder.add(right);
        }
        return builder.build();
    }


    public BinaryTree getLeft() {
        return left;
    }

    public BinaryTree getRight() {
        return right;
    }
}

public class SomeTree implements FindableNode {  
    private final String name;
    private final Set<SomeTree> children;

    public SomeTree(final String name, final Set<SomeTree> children) {
        this.name = name;
        this.children = children;
    }

    @Override
    public String getName() {
        return name;
    }

    @Override
    public Set<SomeTree> getChildren() {
        return children;
    }
}

We can check if our construct does what we expect using a Unit Test:

public class FindableNodeTest {

    @Test
    public void testFindBranchByNameWithSomeTree() {
        final Optional<SomeTree> result = createSomeTree().findByName("branch2");
        assertThat(result.isPresent(), is(true));
        assertThat(result.get().getName(), is("branch2"));
        assertThat(result.get().getChildren().size(), is(2));
    }

    @Test
    public void testFindLeafByNameWithSomeTree() {
        final Optional<SomeTree> result = createSomeTree().findByName("leaf3");
        assertThat(result.isPresent(), is(true));
        assertThat(result.get().getName(), is("leaf3"));
        assertThat(result.get().getChildren().size(), is(0));
    }

    @Test
    public void testFindBranchByNameWithBinaryTree() {
        final Optional<BinaryTree> result = createBinaryTree().findByName("branch2");
        assertThat(result.isPresent(), is(true));
        assertThat(result.get().getName(), is("branch2"));
        assertThat(result.get().getChildren().size(), is(2));
    }

    @Test
    public void testFindLeafByNameWithBinaryTree() {
        final Optional<BinaryTree> result = createBinaryTree().findByName("leaf3");
        assertThat(result.isPresent(), is(true));
        assertThat(result.get().getName(), is("leaf3"));
        assertThat(result.get().getChildren().size(), is(0));
    }

    private SomeTree createSomeTree() {
        final SomeTree leaf1 = new SomeTree("leaf1", ImmutableSet.of());
        final SomeTree leaf2 = new SomeTree("leaf2", ImmutableSet.of());
        final SomeTree leaf3 = new SomeTree("leaf3", ImmutableSet.of());
        final SomeTree leaf4 = new SomeTree("leaf4", ImmutableSet.of());
        final SomeTree branch1 = new SomeTree("branch1", ImmutableSet.of(leaf1, leaf2));
        final SomeTree branch2 = new SomeTree("branch2", ImmutableSet.of(leaf3, leaf4));
        return new SomeTree("root", ImmutableSet.of(branch1, branch2));
    }

    private BinaryTree createBinaryTree() {
        final BinaryTree leaf1 = new BinaryTree("leaf1", null, null);
        final BinaryTree leaf2 = new BinaryTree("leaf2", null, null);
        final BinaryTree leaf3 = new BinaryTree("leaf3", null, null);
        final BinaryTree leaf4 = new BinaryTree("leaf4", null, null);
        final BinaryTree branch1 = new BinaryTree("branch1", leaf1, leaf2);
        final BinaryTree branch2 = new BinaryTree("branch2", leaf3, leaf4);
        return new BinaryTree("root", branch1, branch2);
    }
}

Note, that with Java 9 there will be the possibility to create private default methods, which would maybe enable us to hide the default <T extends FindableNode> Optional<T> findByName(final Set<T> nodes, final String name) method from the world, thus making the interface even more concise and clear. Since i haven't tried Java 9 yet i'm not sure if it would really work :D

Also we could get rid of the Type casts inside FindableNode using an inner class with a type parameter, but for the sake of simplicity, i deliberately left the typecasts in.

Happy Hacking!