LiveJournal embed tag extra whitespace - a solution

Whenever I embed a video on LiveJournal, I put below it a link to the original webpage so that the reader can launch it in a background tab and continue to scroll down on his LJ Friends page. But when LJ recently created a custom lj-embed tag that wraps the video in an iframe, it also added some unnecessary whitespace at the bottom of the iframe. So there would be a couple of extra blank lines b/w the embed and my caption link.

Luckily I know CSS, so I did a workaround: Use relative positioning to lift up the caption and any content following the caption. Here's the code:

<lj-embed>
..embed code for YouTube video ...
<div style="position:relative; top:-32px;"><a href="http://youtube.com/watch?v=blahblah">A cool video</a></div>
</lj-embed>
<div style="position:relative; top:-32px;" >..rest of my blog post...blahblah.....end of blog post</div>


The style attribute value for "A cool video" moves it upwards by the specified no. of units relative to where it would go by default. -32px worked just right for me. Since this line is moved up, you must also raise subsequent content, otherwise there will be a gap after the caption. This is easily accomplished by wrapping all content after the caption in a div with the same relative position values as the caption itself.

Predictive text input (T9) algorithm in Java

I have always been fascinated by the way mobile phones complete words for you when you are creating an SMS message. So I decided to try implement that algorithm in Java.

We know that each number key on the phone is mapped to a set of 3-4 letters. 1 is (a,b,c), 2 is (d,e,f) etc. I call them "buckets". Given a sequence of key strokes, a simple algorithm is to generate all combinations of letters from the corresponding buckets and then suggest only those combinations that exist in a dictionary of words.

For example:
Sequence 63 can be any of md, me, mf, nd, ne, nf, od, oe, of. The dictionary will have only "me" and "of". You can show them in alphabetical order, or in the order of most frequently used, last used etc.

Here are the 2 main functions in this approach. (You can find the full program here):
getMatchingWords returns a list of all alternatives for a given word. It also requires a dictionary of words and the bucket structure of the keypad.

getBucketWords is the recursive function where all the action happens. Assume the word has 4 letters (so 4 buckets) of which the first 2 you have somehow filled. Now you have to fill the 3rd letter (from all characters in the 3rd bucket). The way to proceed is to pick each letter in the current bucket, append it to the so-far generated string, and call yourself recursively. Here curStr and result are used as accumulator variables.

static Set getMatchingWords(String word, Set dict, 
    List buckets){
  Set matches = new HashSet();
  List wordBuckets = getWordBuckets(word, buckets);
  getBucketWords(wordBuckets, 0, "", matches);
  matches.retainAll(dict); 
  return matches;
}

static Set getBucketWords(List wordBuckets, int bucketIndex, 
    String curStr, Set result){
 if(bucketIndex == wordBuckets.size()){
     result.add(curStr);
 }else{
     String curBucket = (String)wordBuckets.get(bucketIndex);
     for(int i=0;<curBucket.length();i++){
         String newStr = new String(curStr);
         newStr = newStr + curBucket.charAt(i);
         getBucketWords(wordBuckets, bucketIndex+1, newStr, 
         result);
     }
 }
 return result;
}

The biggest failing of this method is all the invalid words that are generated only to be discarded. For a word of length n, if you have on average m options for each letter, then the number of words generated is m to the power n. This is the time complexity of this program.

But consider if the dictionary were already sorted into different buckets according to the key sequences. This is eminently possible because mobile phones can come loaded with such a data structure to facilitate fast lookup.

In that case, for a given key sequence, we only need to look up the data structure for all matching words and return 1 or more. Of course the dictionary pre-processing would have been done offline.

Here's a function which implements this improved algorithm. That full program is here.

public List getMatches(String word){
  List matches = new ArrayList();
  String key = getKeyForWord(word);
  if(key != null){
      if(bucketedWords.containsKey(key)){
          matches = (List)bucketedWords.get(key); 
      }
  }
  return matches;
}

The dictionary is pre-processed in 2 steps: First, each character in the keypad is mapped to its bucket number. Then, for each word in the dictionary, a bucket key is obtained by concatenating the bucket number of each character in the word. The word is added to the Map entry corresponding to that key.

To do a lookup, the bucket key for a given key sequence is derived as above, and all entries in the Map matching that bucket key are returned.

Each lookup is O(number of characters in the letter) to generate the key. To generate the bucketed dictionary itself, you need to examine every character in the dictionary once. If the dictionary has n words of average length m, it's O(m * n).

Referential transparency and memoization

Recently I wrote a Python function which performed some processor-intensive mathematical operations. Its return value depended only on the input parameters and no global state was being read or modified. Moreover, this function was invoked a few 1000 times often with the same set of parameters.

I felt that repeatedly calculating the same values which had already been generated in an earlier invocation was wasteful. So I went for the obvious solution of using a cache - with the parameter list as key, and the generated value as the value for the key. Right at the start of the function I check if the cache already contains a mapping for the current input parameters. If yes, I return this cached object. Only otherwise do I calculate a new value, but make sure to add it into the cache before exiting from the function.

Now you can imagine this entire if-else block sitting at the beginning of the function and looking up the cache. Along with a global useCache flag if I ever decide to bypass the cache. Not at all elegant. What if I have to add this feature to other functions tomorrow? The cache lookup code needs to be copied into every such function!

I started to search how other people have solved it. I knew that a function whose return value depends solely on input parameters (with no modification of global state) was called a Referentially Transparent function. So I naturally started at that Wikipedia entry. And lo, in para 3 you have: "referentially transparent functions can be memoized (transformed into equivalent functions which cache results)"

I had come across "memoize" a couple of times before, but only this time it made perfect sense. Wikipedia says about memoization: "It is an optimization technique used primarily to speed up computer programs by storing the results of function calls for later reuse, rather than recomputing them at each invocation of the function"

The article links to a Python recipe for memoization, using the recursive Fibonacci function as example. This is probably one of the best candidates for this technique: Since fib(n) is given by fib(n-1) + fib(n-2), you can pick up the stored values of fib(n-1) and fib(n-2) from the last 2 invocations of fib.

The key line is where a normal fib function is replaced by its memoized equivalent as fib = Memoize(fib). That adds the caching layer, much like a Decorator pattern in Java.

Well, the Decorator hints that you can use a Python decorator for the same. So here's a simple memoization decorator in Python, based on code from another recipe:

class Memoize:
    def __init__(self, fn):
        #Store the original function and create a cache
        self.fn = fn
        self.cache = {}

    # __call__ is invoked when the class name is used like
    # function
    def __call__(self, *args):
        if args in self.cache:
            return self.cache[args]
        else:
            #Not cached. Call original function and
            #add value to cache
            result = self.fn(*args)
            self.cache[args] = result
            return result

# The decorator - returns a Memoized instance
# created from input param
def memoize(func):
    return Memoize(func)

# Use the decorator on the fibonacci function
@memoize
def fib(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

# If I remove the decorator, fib() performs
# much slower for n > 30 on my machine
for i in range(0, 50):
    print fib(i)

This simple decorator does not work if any of the input parameters is a list or any other unhashable type. It also does not work for instance methods of an object, only global functions. At this point I don't need either and I don't know enough Python also :-) You can certainly find something better on the Net.

News.YC's web server

Paul Graham's known for his outspoken and often contrarian views. But to his credit, he has a few successes to show for his approach. After Viaweb and YCombinator, he's working on Arc, a Lisp style programming language. He's dogfooding it with news.yc , a forum to discuss startups. Just today someone asked him which web server he uses. That found a pithy reply:

this one:

(def serve ((o port 8080))
  (nil! quitsrv*)
  (ensure-dir logdir*)
  (let s (open-socket port)
    (prn "ready to serve port " port) (flushout)
    (= currsock* s)
    (after (while (no quitsrv*)
             (if breaksrv*
                 (handle-request s)
                 (errsafe (handle-request s))))
           (close s)
           (prn "quit server"))))

DOM Node dimensions, Viewport width/height, Scroll offsets

Node dimensions
---------------------
1) To get a node's dimensions (including padding and border):
offsetHeight, offsetWidth (works everywhere except IE5 on Mac)

2) To get dimensions without border but includes padding: clientHeight, clientWidth (works everywhere except IE5 on Mac)

There's no API to get dims excluding both padding and border.

3) If node's overflow is set to "hidden" and some part of the element has been cut off, then scrollHeight, scrollWidth gives the full dimensions including the hidden portions.

Of course you'll use a library for these. Let's compare 2 implementations:
1) mootools - In Element.Dimensions.js you find:

    getSize: function(){
...         'size': {'x': this.offsetWidth, 'y': this.offsetHeight},
'scrollSize': {'x': this.scrollWidth, 'y': this.scrollHeight}
...

}

2) YUI - in dom/dom.js you find:

YAHOO.util.Region.getRegion = function(el) {
...
    var r = p[0] + el.offsetWidth;
    var b = p[1] + el.offsetHeight;
...

}

References: Quirksmode, Sitepoint

Viewport dimensions
-------------------------
This API varies with browser and Doctype mode. In particular, IE gives it in different ways depending on whether it's running in Standards compliance mode or not. So you need 3 branches: one for IE in quirks mode, one for IE in Standards mode, and the 3rd for all other browsers. If you know for sure that the page will have a Doctype (which is very likely for new apps), then you can omit the "quirks mode in IE" test.

The properties of interest are innerWidth, innerHeight (Non-IE browsers) and clientHeight, clientWidth (IE). In Standards mode, the IE property should be read from document.documentElement, and in quirks mode it's read from document.body (whew!).

So the code becomes (note: use self instead of window so that your code works even if the page is framed):

if(self.innerHeight) { //all Non-IE..you can also check for innerWidth here
    height = self.innerHeight, width = self.innerWidth;
}else{ // for IE
    //in Standards mode, read from documentElement
    if(document.documentElement && document.documentElement.clientHeight){
        height = document.documentElement.clientHeight;
        width = document.documentElement.clientWidth;
    }else{
        //Quirks mode of IE, read from document.body
        height = document.body.clientHeight;
        width = document.body.clientWidth;
    }
}

YUI takes a slightly different approach, probably because it results in fewer lines of code. They make use of the fact that Mozilla browsers support both innerWidth, innerHeight and the IE properties. So inner* are effectively for Safari.
In dom/dom.js, you'll find:

getViewportWidth: function() {
var width = self.innerWidth;  // Safari
var mode = document.compatMode;

if (mode || isIE) { // IE, Gecko, Opera
width = (mode == 'CSS1Compat') ?
   document.documentElement.clientWidth : // Standards
   document.body.clientWidth; // Quirks
}
return width;
}

Here, document.compatMode is used to check the Standards mode. It returns "BackCompat" if no Doctype and "CSS1Compat" if in Standards mode.

Scroll offsets - how much the page has scrolled
---------------------
This follows the viewport size model: one branch for Non-IE, and one each for IE in Standards and Quirks mode. For IE, you read the scrollLeft, scrollTop from documentElement or document.body. For others, it's self.pageXOffset, pageYOffset.
So the code would be:

if (typeof(self.pageYOffset) != 'undefined' ){ // all but
    x = self.pageXOffset;
    y = self.pageYOffset;
}else if (document.documentElement &&
  typeof(document.documentElement.scrollTop)!='undefined'){
   // IE Standards mode
   x = document.documentElement.scrollLeft;
   y = document.documentElement.scrollTop;
}else if(document.body){ // IE Quirks mode
   x = document.body.scrollLeft;
   y = document.body.scrollTop;
}

Here, YUI again makes use of the fact that all browsers support the non-W3C, IE-invented scrollTop and scrollLeft. Nothing wrong in that, and results in a simple one-liner in dom/dom.js:

getDocumentScrollTop: function(){
 return Math.max(document.documentElement.scrollTop, document.body.scrollTop);
}

Math.max() works because in Standards mode, the property on the document.body is always zero and vice-versa.