Java Generics Note: Reification vs. Covariance

During my study of Java generics, two terms often comes up are reification and covariance.

Reification means the resolution of a instance's exact type at run time. A type is reifiable if JVM can tell the type given an instance at runtime, otherwise we say the type is unreifiable. All generic types are not reifiable, except when it's a unbounded wildcard type or raw type. This is because the Java compiler erases all type argument information with a procedure called type erasure. On the other hand, array types are reifiable, because the element type is available at run time.

Covariance is a property about deriving a set of types given a set of basic types. For instance, for any reference type T, List<T> and T[] are types of its own. Such a derived set of types is said to be covariant they inherit the type compatibility of the basic types. In this case, List<T> is not covariant, because List<Integer> is not a subtype of List<Object>

To conclude, generic types are unreifiable and incovariant, whereas array types are reifiable and covariant. One might ask, can we have other combination of this properties? Such as a set of types that are reifiable and incovariant, or unreifiable and covariant? To answer this question, one need to first understand an very important property that guides the design of strongly type language, such as Java, which is type-safety. For generic types, it means that the program shall not call List<Integer>'s add() method with a String type argument. For array, it means the program shall not call arr[i] = "foobar" if the type of arr is Integer[].

Generic types such as List<T> is unreifiable, meaning that the runtime can't tell List<String> from List<Integer>. Let's assume that List<T> is covariant, this means that List<String> and List<Integer> will both be a subtypes of List<Object>

List<Object> = new List<Integer>()
List<String> strList = (List&ltString>) intList; // Allowed as a down cast.
strList.add(100);
strList.get(0).length();

The issue happen at runtime. Since List<T> is unreifiable, JVM can't tell that line 3 is wrong, so no runtime exception will be thrown.However, line 4 will fail because Integer doesn't have a length() method (in reality a ClassCastException is thrown because Java compiler adds a cast before calling length()). Therefore, a unreifiable type have to also be incovariant to avoid issues like this.

Auto Margin in CSS

Auto margin is normally used to center an element horizontally. Basically, set margin to auto will cause margin-left and margin-right to be set by browser so that the element is centered horizontally in its containing block. An exception is that margin-left can not be less than 0 in this automatic setting, thus margin-left will not go negative if the width of the element is larger than the width of the containing block.

Auto margin can also be used to center element vertically. This is much rarer though. This happens when the element is absolutely positioned and when top and bottom are set. If that is the case, then the element will be centered both horizontally and vertically in its positioning parent. The difference is that margin-top can be negative but margin-left can not. In other words, when its positioning parent is narrower than itself in width, then it won't be centered horizontally, just as the discussion in previous paragraph. However, when its positioning parent is shorter than itself in height, it will still be centered vertically, by having a negative margin-top. This is useful when you want to have a image background that is always centered even if the view port size is small, as used in the second CSS trick in this article. Notice that the trick in the article has the flaw that when the window is very narrow in width, the background will no longer be centered due to non-negative margin-left discussed above, while it is still fine for the vertical centering no matter how short the window is.

Ignoring Mouse Event on DOM Element Using CSS 'pointer-events' Property

Yesterday, I was trying to write my simple Javascript tooltip library that can handle customized feature such as tooltip width, orientation of appearance, and also support arbitrary div content. An example page is here.

Basically, the tooltip div element is positioned absolutely and it shall fade in and out when the trigger text's mouseenter and mouseleave events are fired.

The first difficulty is when the trigger text, say a span, span across multiple lines, such as example two. In CSS term, this span has more than one bounding boxes. This is not a problem if the trigger is a block element as a block element has exactly one bounding box. The desired effect is that the tooltip shall appear next to the bounding box that the mouse enters. This can be solved using the getClientRects method to get all the bounding rectangles of an inline element and decide which of them is entered by the mouse.

The second difficulty, which I want to record here, is as follows. Sometime, due to resizing of browser window, the tooltip will cover part of the trigger text. In extreme case, the tooltip will cover up the entire trigger. As a result, when the tooltip covers the trigger, mouseleave event will be fired on the trigger, even if the mouse is still "on" the trigger. Then the tooltip will fade out and the mouseenter will be fired again... Of course, due to browser event handle time, this will not repeat indefinitely, but it still causes an unpleasant glitch, as show in this JS fiddle. After having some discussion on StackOverflow, I finally found the solution, then "pointer-events" CSS property, which can be used to disable any pointer event on the tooltip and let the event go through to the trigger underneath it, as shown in this JS fiddle. This saved my day.

More info can be found here or here.

Synchronize YouTube videos

Recently, I created a website to synchronize YouTube videos. The idea is that there is a master video and all other videos (called slave videos)  will be synchronized to the master one, in the sense that all playback action on the master video will be reflected on slave videos. This is useful when you want to watch a clip with friends on the other side of the Internet and want to keep your videos play synchronously, even if you pause or seek.

The master page send all playback actions to the web server for temporary storage using standard Ajax. The slave page, on the other hand, need to get these event updates from the server. This is a problem because in the HTTP paradigm, web clients are supposed to send queries to web server, not the other way around. The technology used here is called Comet, which is also called reverse Ajax. The idea of Comet is to allow server to push data to the client. There are multiple methods and framework to achieve Comet. The method I chose is called long polling. As its name suggests, the client need to poll the server continuously with high frequency to ask for update. This is normally done by send a new XMLHttpRequest at the end of the onload callback of the previous XMLHttpRequest. In my code, I add some rate limit so about 2 polling are executed per second. This seems to work but will be harder to scale as the server is being queried continuously, even if there is no event to update.

Keep the same heights for multi-column layouts in CSS

When having a multiple column layout using float, it is sometimes important to ensure that the columns all having the same height. This is especially important when the columns have backgrounds that are different from the background of the container.

There are quite a few way ensure identical heights: .

Among those, my favorite one is the Flexbox Method by Paul Irish. The flexbox method make use of very large padding and is a pure CSS solution.

Suppose we have a div "container", whose direct children are the columns, then the flexbox only requires extra-large padding and negative margin with the same magnitude, as follows:

HTML
CSS

The mechanism is simple, since the column has a very large bottom padding, the background extends downwards almost infinitely. Then a negative margin make sure that the effective height of the column is not affected. The container will automatically cut of the extra backgrounds so nothing pokes out.

Random JavaScript Tips (1)

After learning JavaScript for 2 days, there are quite a bit of difference between it and Java. One big difference that I am stilling getting used to is the omission of block scope.

In JavaScript, all variable declaration are hoisted to the top of enclosing function or the global script, where as in Java the best practice is to declare variables in the nearest enclosing block. According the creator of JavaScript, Brendon, this design choice is due to short of time when they developed it: a relevant question on StackOverflow.

A more important fact is the implementation of a full Closure in JavaScript. The closure a nested function, together with the reference to local variables of all its outer functions. This is very similar to how Java handle nested classes, where inner class can access the instance variables and methods of (the instance of) it outer class. However, Java don't have a function level closure. For example, the anonymous inner class or local class can only access local variables of enclosing method that are declared final. So this is not real closure.

Leetcode OJ: Recover Binary Search Tree

Recover Binary Search Tree

 

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure. 

An O(n) space algorithm is straight-forward. One can write the in-order traversal of the BST to a linear array, then find the two swapped elements and swap them back.

A better solution is to not explicitly write the in-order traversal to an array. In fact, we can just do an in-order traversal on the BST itself and find the swapped elements in the process. Notice that if we exchange two adjacent (in terms of in-order) nodes, then the logic to find swapped elements is a little different, but this is handled subtly in the code.


However, since the previous solution uses recursion, then the worst case space complexity is the depth of the tree, which could be as bad as O(n).

A tree O(1) space solution requires the used of Threaded Binary Tree, which I learned from other's solution. A threaded binary tree allows one to truly traverse a binary tree with constant space. In our case, we want a forward traversal, so the right child of any node who doesn't have a right child points to its in-order successor. Since we want to preserve the structure, we make that pointing on the fly and recover it after that pointing after use. A threaded binary tree solution is as follows. Notice that we need to find the in-order predecessor of each node twice. The total complexity of finding in-order predecessor of all nodes is O(n), since it's easy to see that every edge is traversed only once. So it is not too bad.