Thoughts on foundational framework development

Foundational framework development is very important in any technology companies. It solves common problems shared across departments, teams or projects. It generally is lauded by management. Many great open-source frameworks, e.g. AngularJS, React, I believe, are stemmed from in-house framework development then taken from companies like Google and Facebook to public.

There are two schools of thoughts to develop foundational frameworks: bottom-up or top-down. Bottom-up approach is to build it prior to any applications by foreseeing and analyzing various potential needs of applications, finding the common area then developing it. Sometimes the analysis phase becomes a bit of guessing work and shot in the dark. And at organizational level if there is division between foundational team and application team, it could makes this approach even harder. However this approach fits well to develop a well-defined public API or standard like JDBC driver for an in-house database.

Top-down approach is more practical, teams, without the division of foundational team and application team, start to build the applications to meet business needs and both with well-defined architectures. During the course of development teams start to discover the relationship between difference layers and modules, continue to refine the architecture and code-base. At the end of project or even after project delivery teams set out to refactor and harvest a framework from the applications. This approach usually has grounded success since it is based on real-life applications to solve real problems. Also this approach is well aligned with refactoring and iterative agile development.

The following diagrams further illustrate my thoughts above:

The bottom-up approach tends to assume the interfaces between foundation layer and applications are well-defined or the boundaries can be easily discovered.

 

However in reality, the picture looks more like this:

 

 So bottom-up approach ends up like this: 

 

What happens above is that application logics are everywhere in the foundation layer. In the code we see lots of if/else, case/switch statements, and any changes in foundation layer to accommodate one application will impact other applications.  That foundational layer eventually becomes a monolithic application.

So what is best way to develop foundation layer? Based on my experiences, there are few OO design principles and patterns can greatly help us.

1. Foundational interfaces should be minimum. Try not solve everything, leave as much as you can to application unless you are sure the functionality is needed. Develop a toolkit not a specific problem solver.Using java's java.util.List as example, it provides a method called get(index) and doesn't provide method getFirst() or getLast() since it leaves the clients to do that. In that way you leave the client assembles the jdk methods to any requirement it may need to accomplish.

1. Close to change, open to extension.

2. Dependency injection (IoC) or Hollywood principle  - Don't call me, I call you.

3. Develop pluggable interfaces.

Generics related design patterns: part I

Generics, introduced in Java 6, is one of the powerful features in Java to help developer to better design class and method, enabling type safety and compiling time check.

Here I introduced couple useful generics related design patterns.

1. typesafe hetergenous map, as described in book "Effective Java"

Mostly of time map contains certain type of keys and values, unless you create object as key or values, but if you do that, you lose the control of type checking. Using class literal introduced Java 5, we can create typesafe map. Here is the implementation:

/*

 * Typesafe container pattern

 */

public class TypeContainer {

Map<Class<?>, Object> map = new HashMap<Class<?>, Object>();

public <T> void put(Class<T> key, T instance){

map.put(key, instance);

}

public <T> T get(Class<T> key){

return key.cast(map.get(key));

}

}

2. Generified singleton pattern

We know the singleton holder pattern which is thread-safe way to create singleton. So how we can create generified singleton?

The idea is to created a typesafe container to hold all of the potential singleton instances. Note this is not a clean way.

/* 

 * generic singleton pattern

 */

public final static class Singleton<T> {

private Singleton(){}

public Singleton<T> getInstance(Class<T> type){

        // check if type is supported if does then return the singleton

return (Singleton<T>)(SingeltonHolder.store.get(type));

}

private final static class SingeltonHolder {

private static final Map<Class<?>, Singleton> store = new HashMap<Class<?>, Singleton>(){{

put(String.class, new Singleton<String>());

put(Integer.class, new Singleton<Integer>());

                        //add all of the supported types here

}};

}

}

3. Generic singleton factory pattern

/*

 * generic singleton factory pattern 

 */

public interface MyInterface<T> {
   T doSomthing(T arg);
}

public static class GenericFactory {

public static <T> MyInterface<T> getImpl() {
return (MyInterface<T>)IMPL;
}

/* here we only need one generic implementation */

private static final MyInterface<Object> IMPL = new MyInterface<Object>() {

@Override

public Object doSomthing(Object arg) {
return arg;
}
};
}

Immutable vs Unmodifiable

Immutable is one of the most important programming language concepts. Immutable is an read-only object which can not be changed, if there is any changes, a new copy will be created with updated version. internally the object state can be altered but the changes won't be reflected from the outside.

Most of immutable are value object to represent a certain business domain. Unmodifiable, is "read-only view" of the object. Similar to immutable it can not be changed from outside, but internally the object state can be altered and the changes can be reflected on the view.

In the Java Collection tutorial, one of the way to create immutable object is to construct one without reference to it, so it can't be changed.

In classic "effective java" book, it presents 5 rules to create immutable class:
1. don't provide methods to change object state. This is how JDK's Collections.unmodifiable does.
2. all fields are final
3. all fields are private
4. class can't be subclassed, either by declared it final or don't provide public/protected constructor.
5. exclusive access to object mutable state.

Immutable is particularly useful in concurrent programming since it is thread-safe. In Java and many other languages as well, String, Float, Double and Integer are immutable.

Here are two unit test cases to demonstrate the immutable and unmodifiable.

@Test

public void unmodifiableTest(){

List<String> modifiable = new ArrayList<String>();

modifiable.add("1");

List<String> unmodifiable = Collections.unmodifiableList(modifiable);

assertTrue("should have the same size", modifiable.size() == unmodifiable.size());

modifiable.add("2");

assertTrue("should still have the same size", modifiable.size() == unmodifiable.size());

try{

unmodifiable.add("3");

assertTrue("should not succeed", false);

}catch(UnsupportedOperationException ex){

assertTrue("should throw exception", true);

}

assertTrue("should still have the same size", modifiable.size() == unmodifiable.size());

}

@Test

public void immutableTest(){

List<String> modifiable = new ArrayList<String>();

modifiable.add("1");

List<String> immutable = Collections.unmodifiableList(new ArrayList<String>(modifiable));

assertTrue("should have the same size", modifiable.size() == immutable.size());

modifiable.add("2");

assertTrue("should no longer have the same size", modifiable.size() != immutable.size());

try{

immutable.add("3");

assertTrue("should not succeed", false);

}catch(UnsupportedOperationException ex){

assertTrue("should throw exception", true);

}

}

group sort

This post is responding to my friend Li Peng's page. http://allenlipeng47.com/PersonalPage/index/view/173/nkey

Given an array of string, and sequence. Sort the array according to the given sequence.
For example:
String str = "DCBAEECCAAABBAEEE"; String sequence = "ABCDE";
output should be: AAAAABBBCCCDEEEEE

The counting sort like sort algorithms are the ones can be done in O(n).

public static char[] sort(char[] strs, char[] comp){

char[] sorted = new char[strs.length];

int[] count = new int[256]; 

for(char s : strs){

count[s]++;

}

int index = 0;

for(char c : comp){

int num = count[c];

while(num-->0)

sorted[index++] = c;

}

return sorted;

}

if it is required to sort in place:

public static char[] sort(char[] strs, char[] comp){

int[] count = new int[256]; 

for(char s : strs){

count[s]++;

}

int index = 0;

for(char c : comp){

int num = count[c];

while(num-->0)

strs[index++] = c;

}

return strs;

}

Sort the Double linked list in place:

/*

* in place sort DLL of Rs, Gs and Bs, so that Rs in front, followed by Gs and Bs

* assume DLL has the sentinel node to separate the head and tail

*/

public static void sortDLL(DLL head, DLL sentinel){
final char[] setOfChars= new char[]{'R', 'G', 'B'};

DLL curr, p;
curr = p = head;

//push all R to the front

while(p != sentinel){
if(p.data == 'R'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}

 

curr = p = head.pre.pre;

//push all B to the back

while(p != sentinel){
if(p.data == 'B'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.pre;
}
p = p.pre;
}
}

How about Singled LinkedList?

//here I use DLL node to represent the SLL

//in this case DLL.pre = null

void sortSLL(DLL head){
DLL curr = head, p = head;

//push all Rs to the front

while(p != null){
if(p.data == 'R'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}

//now all Rs at front and curr points at candidate 

//position for next char which is G

//push all Gs to the front

p = curr;
while(p != null){
if(p.data == 'G'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}
}

Reservoir sampling

Reservoir sampling is algorithm to randomly choose m samples from a large sample pool. The algorithm is as following: Supposed index starts from 0 1. choose first m sample from the pool 2. for each sample after that, e.g. index at k, randomly choose number i in the range of [0, k] if(i<=m) swap number at i and k Output the numbers at index from 0 to m.


public int[] ReservoirSampling(int[] input, int m) {
if(input.length<=m)
return input;

int[] output = new int[m];
for(int i = 0; i<input.length; i++){
if(i<m)
output[i] = input[i];
else{
int pick = (int) (Math.random()*(i+1));
if(pick<m){
output[pick] = input[i];
}
}
}

return output;
}

Proof by induction:

If at step i-1, the probability of number in the list is m/i-1

The at step i, 

the probability of any number in the output remains is probability of number in step i-1 and
probability it survives the step 1: m/(i-1) * i-1/i = m/i, 

the probability of the number at i being chosen is m/i.

Thank you for my friend Peng Li for presenting this problem. Please see his link on this: http://allenlipeng47.com/PersonalPage/index/view/161/nkey

Rabin Karp Algorithm

There are couple string match algorithms which can achieve linear time to do the search in stead of O(n*m). Suffix tree algorithm requires to pre-compute the suffix tree and requires O(K*N) space, K is the alphabet size and N is the maximum length of the strings. KPM also needs to pre-compute a table of  failure function to quickly find the next starting positions in two string. Rabin Karp algorithm is probably the simplest one, which use hash to compare two strings.

The key to Rabin Karp algorithm is to compute the hash effectively and quickly. This is done by dynamic programming, which is current substring hash value is computed based on the previous one. 

Here is the Rabin Karp algorithm to solve an online algorithm for palindrome checking.

Thanks to Peng Li for bringing up this problem. Here is the link to his page on this: http://allenlipeng47.com/PersonalPage/index/view/157/nkey

Merge sort linked list

Merge sort, compared to quick sort has the best and worst time complexity of O(NLgN) and requires O(N) space.

However for linked list, merge sort doesn't require additional space.