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;
}
}