daily tweets

• 21:55 Watched 2007's Die Falscher: at last, a good movie. #

daily tweets

• 12:13 Omnia custom rings hack: create My Device/Storage Card/My Documents/My Documents/My Ringtones and stick your mp3s there. #
• 12:45 All about Samsung Omnia blog of note: mysamsungomnia.wordpress.com/ #

daily tweets

• 20:14 Toying around with my new Samsung Omnia tinyurl.com/6mzfpk More to come in a full blog post as soon as I find my way around. #
• 14:26 WinMo Device Center for Vista waaay better than horrible ActiveSync. #

daily tweets

• 22:09 American Scientist's100 or so Books that shaped a Century of Science tinyurl.com/6krrmf Knuth's up there along with Einstein/Feynman! #
• 11:24 Insanely large FAQ on Java generics by Angelika Langer: tinyurl.com/56eet7 #
• 13:04 Looking at some astonishing A4 papercut works by Peter Callesen: tinyurl.com/2nxhxu #

the ISO paper size concept

I've been using ISO paper sizes (A4, A3, etc) since the dawn of (my) time. I have even worked for a company that makes optimisation software for paper industries around the world. But I have never ever questioned the rationale behind their sizes. Well it turns out that the sizes are such that if you take any paper sheet of size An and fold it across the long side you'll get two An+1 sheets. So, if An has (x, y) dimensions, then An+1 will have (y, x/2) dimensions. Keeping the ratio constant gives us x/y = y/(x/2) or x/y = 2y/x hence x/y=sqrt(2)! So the aspect ratio of the sides for every paper size is 1:sqrt(2). In other words the ratio of any square's side to its diagonal. Given that A0 has this ratio and an area of 1sqm, we get the (0.841, 1.189) dimensions, and applying the halving process we reach the all too familiar A4 paper size of (0.210, 0.297). Since the sqrt(2) is an irrational number (1,4142135623730950488016887242097...), actual dimensions are always rounded to the nearest millimetre; there's even a type for calculating that but I'll spare you the details. ISO 216 has all that and more. For a free summary of the standard you may also have a look at Wikipedia.

one-pass tree pruning

A friend of mine wondered the other day if one-pass tree pruning was possible. Common sense dictates that a two-pass algorithm is required to first mark the subtrees due for deletion and then a second walk to do the actual pruning. I have since revisited this thought and managed to get a one-pass proof of concept:

boolean pruneTree(Iterator parentIterator, TreeNode root, Set allowedNodeValues) {
    boolean pruneNode = true;

    Iterator nodeIterator = root.getChildren().iterator();
    while (nodeIterator.hasNext()) {
        TreeNode child = nodeIterator.next();
        pruneNode = pruneTree(nodeIterator, child, allowedNodeValues) && pruneNode;
        }

    pruneNode = pruneNode && !allowedNodeValues.contains(root.getValue());
    if (pruneNode && parentIterator != null) {
        parentIterator.remove();
    }

    return pruneNode;
}

This will remove parts of the tree whose node values are of no interest to us, otherwise retaining the same structural properties as those of the original tree:

    a                                               a
   / \                                             / \
  b   c                                           b   c
 / \  | \     pruneTree(it, a, {a,b,c,d}) -->    /    | 
d  e  b  e                                      d     b     
   |    / \                                                 
   c   d   f                                           

To make sure this was doing what was meant to do, a pretty print method was necessary. I used indentation and nested parentheses (with slight adjustments from Knuth's original):

void printTreeIndented(TreeNode root, int currentDepth) {
    System.out.println();
    for (int i = 0; i < currentDepth - 1; i++) {
        System.out.print("\t");
    }
    System.out.print(root.getValue());

    currentDepth++;
    for (TreeNode node : root.getChildren()) {
        printTreeIndented(node, currentDepth);
    }
}

void printTreeParenthesized(TreeNode root) {
    System.out.print(root);
    List children = root.getChildren();
    if (children.size() == 0) {
        return;
    }

    System.out.print('(');
    printTreeParenthesized(children.get(0));
    for (int i = 1; i < children.size(); i++) {
        System.out.print(", ");
        printTreeParenthesized(children.get(i));
    }
        
    System.out.print(')');
}

The first one will print:

a
  b
    d
    e
      c
  c
    b
    e
      d
      f

while the second will print a(b(d, e(c)), c(b, e(d, f))). Unfortunately after some runs I realised that the tree pruning algorithm's performance is dismal; it prunes by removing nodes bottom up, one by one. After all, it has no other way of knowing what to prune in one pass. Compare this with a fast mark pass and a second prune pass whereby whole sub-trees can be pruned. What's worse, as it's written, it runs out of heap space for large trees with more than a handful of levels. I guess the question is, does anybody know of any fast one-pass tree pruning algorithm?

daily tweets

• 22:11 Enjoying a Frey Supreme Passion Pecan & Caramel Swiss milk chocolate tinyurl.com/6z6g4w.Best when accompanying a malty Breakfast tea. #

daily tweets

• 21:46 An exceptional Agiorgitiko:Domaine Helios-Grande Reserve 2003,by Kokotos. A must for the coming festive season. #
• 22:50 OMG: tinyurl.com/5tuldy I think I'm scared. #

daily tweets

• 09:36 Outlook 2003 complains about MAPI32.DLL? Try renaming the MSMAPI32.DLL to MSMAPI32.XXX and restart Outlook. Likely cause: 2007 residue... #
• 09:44 LinkedIn added Applications (Box.net, Slideshare, etc). Hmmm..... #
• 10:14 Enabled Google Calendar gadget from Labs and put it on top, using nav bar drag&drop, also enabled in Labs. Highly recommended. #

daily tweets

• 22:00 Finished Philip Dick's Radio Free Albemuth: what a flop... #