Thursday, March 20, 2014

Sorted List to height-balanced binary search tree.

There is elegant algorithm to convert a Sorted List to height-balanced binary search tree in leetcode. It is asked in stackoverflow and various other websites.  This algorithm is elegant. Here I give a proof that it is correct.


public TreeNode sortedListToBST(int start, int end) {
  if (start > end)
   return null;
 
  // mid
  int mid = (start + end) / 2;
 
//first recursion 
 TreeNode left = sortedListToBST(start, mid - 1); 
 
//constant 1. There is one advance for each node inserted into tree. 
 TreeNode root = new TreeNode(h.val);
  h = h.next; 
//second recursion 
 TreeNode right = sortedListToBST(mid + 1, end);
 
  root.left = left;
  root.right = right;
 
  return root;
 }
 
Here we want to prove 
 sortedListToBST(start, end) will consume exactly end-start+1 nodes. 
If this is true, we can be certain that 1) sortedListToBST does not consume more nodes 
than expected.  2) the h is positioned for next sortedListToBST call.
 Give i=end-start, we need to prove f(i)=i+1
first, it is observed that 
f(0)=1
f(1)=2 
f(2)=3;
f(3)=f(0)+f(1)+1=4
f(4)=f(1)+f(1)+1=5.
So the statement is true for i when i<=4.
 
When i is even and i>=5.
mid=i/2.
First recursion is equal to f(mid-1-start)=f(i/2-1-0)=f(i/2-1);
Second recursion=f(end-(mid+1))=f(i-(i/2+1))=f(i/2-1).
So f(i)=f(i/2-1)+f(i/2-1)+1. Given that f(i/2)=i/2+1. We can conclude that 
f(i)=(i/2-1+1)+1 +(i/2-1+1)=i+1
So this statement is true when i>4 and i is even.


When i is odd, and i>=5.
f(i)=f((i-1)/2-1)+1+f(i-((i-1)/2+1))=(i-1)/2-1+1 + 1 + (i+1)/2-1+1=i+1.
So this statement is true for i is odd and i>=5.
 
 
It is proved! 

Tuesday, March 11, 2014

Software Degin Pattern in JEE

Recently, I need to fresh up my memory for design pattern.  When I look through the pattern list in http://en.wikipedia.org/wiki/Software_design_pattern, I associate them with my experience web development. Here are the patterns used in a typical JEE web application.

Server Side

When the request comes from client, servlet container retrieves a thread from pool to handle the request. This is object pool pattern.  Thread is not created from scratch, it is retrieved from pool.

Request is forwarded to servlet filter: We could expect a chain of filters. This is a chain of responsibility pattern.  Each specific filter is a command object do some tasks and forward request to next step.

Let use assume that JSF is used to generate web interface.

Finally request reaches the FacesServlet. This is a front controller pattern.

Servlet and filter are "Template Method" patterns: Parent classes define the hooks for child class to plug its implementation. "Template method" pattern is specifically for algorithm in the wikipedia. If the request handling is treated as algorithm, you can think it as a template pattern.

FacesServlet will use FactoryFinder to find Various Factories. These factories are used use to create component in the system. These factories are example of "Factory method" pattern. FactoryFinder is not abstract factory pattern, however. Abstract factory is supposed to be abstract and  create a set of objects in a theme. But FactoryFinder creates a set of factories(not objects). Moreover, these created factories are not related to each others.

Finally, the request will go to a series of phase(state restore, decode, converter/validation, update model value, execute application, render). We can assume there is a component tree. At each phase, we will go through the component tree and do some work. Each phase can be viewed as state pattern. The work is done in each phase is very similar: travel the tree, do something with each component, and broadcast event if necessary, stop or go to next phase. The exact work depends on current phase.
To travel the component tree, we have an iterator pattern. The tree iterator knows how to go through the tree. To do work at each component, we have vistor pattern. For a particular node, we could do many things for it: decoding, converter, rendering, etc. Instead of having all these functions in component, we implement Vistor. 

When it comes to rendering, one component could be rendered into multiple ways: html, pdf, etc. In the JSF system, we could multiple render kits. Each render kit can be viewed as a strategy pattern: a strategy to handle the tree in a particular way. The strategy selection is left to JSF framework.

A render kit can be viewed as an abstract factory pattern. All renders from this render kit behaves according to similar principle to produce a cohesive result: html or pdf.  But render kit does not follow traditional abstract factory pattern. It has one factory method parametrized by input arguments instead of multiple factory method.

At any phase, phase event/system event/component event can be broadcast/published, this is a observer/publish/subscribe pattern.

IN JSF 2.2, the jsf bean is managed by CDI. A CDI can have decorator (decorator pattern), interceptor(proxy pattern). When one bean is injected, CDI framework will look up the bean and create it if necessary(Lazy Initialization).  If the bean is an application-scoped, there is only one instance for the whole application, this is essentially the singleton pattern in JEE environment.

CDI supports the @observe annotation, this is observer pattern. @produce method is a factory method pattern. @Qualifier is a strategy selection at run time. @alternative is a strategy selection at deployment time.

When it is comes to authentication, we could have plug-in for password-based authentication, certificate-based authentication, smart card authentication. The authentication mechanism selected at runtime depends on the authentication data passed from client. This is a strategy pattern. Conceivably, we will have user, group and role. We could use a composite pattern to handle this.

Suppose our system also supports JAX-RS response, javax.ws.rs.core.Response.ResponeBuilder can be used to build the response. This is a builder pattern. Moreover, the javax.ws.rs.core.Response.ResponeBuilder implements all the methods in fluent invocation pattern.

We have JAXB helper class to do marshalling and marshalling. To shield end user from internal implementation, the helper class is a Facade pattern. The helper class can used by JAX-RS by convert it to MessageBodyReader and MessageBodyWriter(Adapter pattern).

JPA is used to access database. JPA will use proxy for Lazy Initialization.

Suppose, we need to support asynchronous process. We have a command pattern. We will capture all necessary information in an object. The servlet will handle this command and sends result to client when it is ready.