Saturday, December 28, 2013

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.

Friday, December 27, 2013

Fun with Guava: Interleaving Iterables

Problem: given some number (finite, possibly 0) of iterables, create an iterable that interleaves their elements.
For example, given [1, 2, 3] and [x, y, z], return [1, x, 2, y, 3, z]. Note that the iterables may be of different sizes -- some may be empty or even infinite. When a particular iterable has no more elements, just skip it (i.e. don't pad with nulls for the purpose of interleaving).
public static <T> FluentIterable<T> interleave(final Iterable<? extends Iterable<? extends T>> iterables) {        
    return new FluentIterable<T>() {
        @Override
        public Iterator<T> iterator() {
            return new AbstractIterator<T>() {
                final Iterator<Iterator<? extends T>> iterators; {
                    List<Iterator<? extends T>> list = Lists.newLinkedList();
                    for (Iterable<? extends T> iterable : iterables) {
                        list.add(iterable.iterator());
                    }
                    iterators = Iterators.cycle(list);
                }
                
                @Override
                protected T computeNext() {
                    while (iterators.hasNext()) {
                        Iterator<? extends T> iter = iterators.next();
                        if (iter.hasNext()) {
                            return iter.next();
                        } else {
                            iterators.remove();
                        }
                    }
                    return endOfData();
                }
            };
        }
    };
}
And thus:
System.out.println(
    interleave(
        ImmutableList.of(
            Iterables.cycle("+", "-"),
            ImmutableList.of(1, 2, 3, 4),
            Collections.emptyList(),
            Iterables.cycle(true, false, null)
        )
    ).limit(20)
);
// [+, 1, true, -, 2, false, +, 3, null, -, 4, true, +, false, -, null, +, true, -, false]

Tuesday, February 7, 2012

Annotation with annotation element annotating itself

So... this works...
@Awesomeness(level = 100, item = @Awesomeness.Thing("Ice cream!"))
@interface Awesomeness {

   int level() default 42;

   Thing item() default @Thing("Hamburger!");

   @interface Thing {
      String value() default "Bacon!";
   }
 
}
Now if I can only do something useful with this...

And yes, the compiler does detect cycles. Awesome!!

Friday, July 29, 2011

Compile-time constants in Java annotation element values

In hindsight, this should've been obvious:
public class CompileTimeConstantsTest {
 
    @interface Awesome { String value(); }
 
    private static final String X = "X";
    private final int a = 1;
    public final int b = 1;

    @Awesome(a < b ? X : X + X) // compiles just fine
    int whatever;
 
}

Friday, June 24, 2011

Add menu accelerator for FindBugs plugin

One way to run FindBugs is to:
  1. Right click on the Java source file you’re editing
  2. Move cursor and hover over "Find Bugs"
  3. Wait until child menu appears
  4. Move cursor to select and then click on "Find Bugs"
You can greatly accelerate this process by modifying eclipse/plugins/edu.umd.cs.findbugs.plugin.eclipse_1.3.9.20090821/plugin.xml:
REPLACE:
   label="Find Bugs"

WITH:
   label="Find Bu&amp;gs"
Then restart Eclipse with -clean command line argument. Now, to run FindBugs, you can just:
  1. Press Menu key
  2. Press G (this didn’t use to have an accelerator, but now does)
  3. Press F (this already has an accelerator)
Similarly, you can clear all FindBugs markers by pressing the key sequence Menu G C.

Monday, February 14, 2011

Pascal's triangle using regex

The pattern can probably be simplified, but this works.
String s;
System.out.println(s = "-;");
for (int n = 10; n --> 0 ;) {
   System.out.println(s = s.replaceAll("^(?=(-;))|;(?=(-*;))", "$1$2"));
}

Wednesday, February 9, 2011

Per-site user stylesheet rules for Firefox

I'll summarize this later:

userContent.css and @-moz-document
https://developer.mozilla.org/en/CSS/@-moz-document

Where's my profile directory?
about:support

You'll probably want to use !important.
http://www.w3.org/TR/CSS2/cascade.html#important-rules