Fun with Guava: Cross joining two iterables, binary functions vs pairs, and reconstructing inorder traversals from preorder and postorder

Suppose you have the following interface for a binary function:

interface BiFunction<L, R, T> {
    T apply(L left, R right);
}

Then you also have these utility methods:

public static <L, R, T> Function<R, T> fixLeft(
        final BiFunction<? super L, ? super R, ? extends T> f2,
        final L left
    ) {
    
    return new Function<R, T>() {
        @Override
        public T apply(R right) {
            return f2.apply(left, right);
        }
    };
}
    
public static <L, R, T> FluentIterable<T> crossJoin(
        final Iterable<? extends L> lefts,
        final Iterable<? extends R> rights,
        final BiFunction<? super L, ? super R, ? extends T> joiner
    ) {
    
    return FluentIterable.from(lefts).transformAndConcat(
        new Function<L, FluentIterable<T>>() {
            @Override
            public FluentIterable<T> apply(final L left) {
                return FluentIterable.from(rights).transform(fixLeft(joiner, left));
            }
        }
    );
}

public static FluentIterable<Integer> zeroToN(int n) {
    return FluentIterable.from(
        ContiguousSet.create(
            Range.closed(0,  n),
            DiscreteDomain.integers()
        )
    );
}

Then you can do the following:

System.out.println(
    crossJoin(
        ImmutableList.of('a', 'b', 'c'),
        zeroToN(3),
        new BiFunction<Character, Integer, String>() {
            @Override
            public String apply(Character letter, Integer count) {
                return "{" + Strings.repeat(String.valueOf(letter), count) + "}";
            }
        }
    )
);
// [{}, {a}, {aa}, {aaa}, {}, {b}, {bb}, {bbb}, {}, {c}, {cc}, {ccc}]

Note that there's an implicit pairing in the cross join, and if (for better or for worse) a Pair<L, R> type is made available, one would be tempted to write the obvious BiFunction<L, R, Pair<L, R>> pairing binary function and run wild with it. It seems that in this particular use case at least, the use of binary function as an alternative to using pairs as an intermediate step doesn't look that bad. Anyway, it's perhaps also worth mentioning that Java 8 still will not have a pair type, but it will have a binary function type.

---

As one more example, here's another fun thing you can do with the above: given the preorder and postorder traversals of some unknown binary tree T, try to reconstruct T and return its inorder traversal. If there are multiple solutions, then return all of them. Here's one way to solve it:

interface BinaryOp<T> extends BiFunction<T, T, T> {
}

public static Iterable<String> inorderReconstruction(final String preorder, final String postorder) {
    if (preorder.isEmpty()) {
        return Collections.singleton("");
    }
    final int n = preorder.length() - 1;
    final char root = preorder.charAt(0);
    if (postorder.charAt(n) != root) {
        return Collections.emptyList();
    }
        
    return zeroToN(n).transformAndConcat(
        new Function<Integer, Iterable<String>>() {
            @Override
            public Iterable<String> apply(Integer k) {
                return crossJoin(
                    inorderReconstruction(preorder.substring(1, k + 1), postorder.substring(0, k)),
                    inorderReconstruction(preorder.substring(k + 1),    postorder.substring(k, n)),
                    new BinaryOp<String>() {
                        @Override
                        public String apply(String left, String right) {
                            return "(" + left + root + right + ")";
                        }
                    }
                );
            }
        }
    );
}    

Thus:

System.out.println(
    inorderReconstruction("123", "321")
); // [(1(2(3))), (1((3)2)), ((2(3))1), (((3)2)1)]

System.out.println(
    inorderReconstruction("12345", "34251")
); // [(((3)2(4))1(5))]

The reconstruction is done lazily, as demonstrated here:

String x13 = Strings.repeat("x", 13);
FluentIterable<String> allBinaryTreesOfSize13 =
    FluentIterable.from(
        inorderReconstruction(x13, x13)   // FAST!!
    );
  
System.out.println(
    allBinaryTreesOfSize13.size()         // SLOW!!
); // 742900 == Catalan(13)

System.out.println(
    allBinaryTreesOfSize13.limit(2)       // FAST!!
); // [(x(x(x(x(x(x(x(x(x(x(x(x(x))))))))))))), (x(x(x(x(x(x(x(x(x(x(x((x)x))))))))))))]

The last line also provides an easy and fast way to check for uniqueness of solution: get up to 2, and then verify that there's exactly 1.