Playing around with HTML 5

Playing around with HTML 5

Yesterday, while browsing DZone, I encountered a couple of HTML 5 blogs. So I decided to try and code some HTML5 - Canvas myself.

This is the result of one hour trail-and-error:

Sorry, no support, please upgrade your browser!

Maybe I’ll do a write-up soon, but for now, just check the sources. (Yes they are wrong/hack-ish, I know…).


Some of my software development rules

Some of my software development rules

Here are (in my opinion) five of the most important ‘rules’ in software development.

Changes happen

The reason why waterfall doesn’t work and agile works a lot better. Changes happen. People will always change their mind, over time technology changes and situations change. So during software development you will have to be flexible with the requirements.

Create software that the client wants, not what he says he wants.

What the clients tells you he wants might not (entirely) be what he/she actually wants or the organisation needs. It is vital to ask questions and release early. When you have something visible, let the client judge it.
Some people say there is one major drawback of showing designs and the application early on, the client probably gets new ideas and wants to change the design. But that actually is a good thing, you still have much time left to plan these changes! If you do a waterfall-method and release on delivery date.. the client still wants his/her changes (!).

Always write down decisions.

During a project, especially during the startup, there are a lot of choices to be made. Is it going to be a web application, or standalone? What frameworks are we going to use?
All these decisions are made with arguments, pro’s and con’s, write those down! A project-wiki would be a perfect place. If some members leave the team and new members join the team this information is vital. When the new members join the team their first reaction will be “Why are they doing it this way and not …?”. Reading the argumentation will help them understand the situation and get them up to speed. Also, during projects there are always moments when you reflect on choices made in the past: “Why did we do … wouldn’t we have done better if we did/used …”. You can now always review the past arguments to see if the current situation has changed so much that a reconsideration would be in order or not.

The team owns the code.

If you write a piece of code, it is not your code. The code belongs to the collective, the team. If somebody changes your code, embrace it, it was probably needed. If you see an ugly piece of code you didn’t write, you are also responsible, refactor it.

Commit driven development.

Test driven development is a great idea. First write a unit-test, check to see if it fails, now write your code until the test succeeds. This way you know two important things, the final code is easy to test (it was written with testing in mind) and the code does what the test expects. But there is one major drawback, most people (not all) simply can’t work this way. For some people it works great, but some developers want to write their tests afterwards. And that is ok, there is just one important rule: Never check your code in (the trunk) if it isn’t tested and doesn’t have proper documentation (e.g. JavaDoc). So: It is no problem if you write code and then tests, or tests then the code, as long as you write them before commiting to your SCM repository.

There are situations when you need to write a lot of new code, in that case you still want to be able to check your code in, even if you aren’t done yet. For these situations you create a feature-branch. On this branch you develop all the new funtionality and once it is done, documented and tested, merge it with the trunk.


Compression by prediction

Compression by prediction

The last couple of weeks I have been playing around with compression/decompression algorithms. This is a field that has always intrigued me. It gives me a magical feeling, like a magician you wave some algorithm around and suddenly the files shrink and bytes dissapear. With the same motion you can undo all your actions and re-generate the original files from thin air!

Arithmetic Coding

Arithmetic coding is a different method to encode bytes. On itself it doesn’t compress, but it is the backbone of a whole family of compression algorithms. To explain how it works we need some example text we want to compress: “ABACB”

First we assign a probability to each symbol:

  • A: 45%
  • B: 40%
  • C: 15%

Lets change these probabilities into ranges from 0.0 to 1.0:

  • A: 0.00 to 0.45
  • B: 0.45 to 0.85
  • C: 0.85 to 1.00

Now we start reading our input (ABACB). The first character we find is ‘A’. First we do a lookup in the table, what range does ‘A’ have: 0.00 to 0.45. Lets remember these values as ‘low’ and ‘high’.

Time to encode the second character ‘B’. The first thing we need to do is reset our ranges to be between low and high:

  • A: 0.0000 to 0.2025
  • B: 0.2025 to 0.3805
  • C: 0.3805 to 0.4500

We want to encode ‘B’, so we’ll end up with low=0.2025 and high=0.3805. Time to update the table again:

  • A: 0.2025 to 0.2826
  • B: 0.2826 to 0.3538
  • C: 0.3538 to 0.3805

Encode ‘A’, we get low=0.2025 and high=0.2826. And adjust the table again:

  • A: 0.202500 to 0.238545
  • B: 0.238545 to 0.270585
  • C: 0.270585 to 0.282600

Encode ‘C’, we get low=0.270585 and high=0.282600. Adjust the table one last time:

  • A: 0.27058500 to 0.27599175
  • B: 0.27599175 to 0.28079775
  • C: 0.28079775 to 0.28260000

So, lets encode the final symbol ‘B’ and stop right here. Now we save/output a value betwee low (0.27599175) and high (0.28079775) which takes the least amount of bytes, for example 0.28!

Now I we want to decode our message “0.28” we start by building the ranges again, these are the same as the first table above. Now we look at which range our 0.28 fall in. The result is ‘A’ (between 0.0 and 0.45). So we output this symbol. Next we have to update the table, because we outputted ‘A’ we know our encoder encoded ‘A’, so we can follow the same steps as the encoder did and update the ranges in the same way, so we’ll end up with the second table (with values between 0.0 and 0.45). If we look at 0.28 it now falls into range ‘B’, so we output ‘B’ and adjust again.

As you can see this number “0.28” describes our whole message “ABACB”! So we encoded a whole message in one small number. There are a lot of improvements possible to implement this algorithm efficiently, for example look at range encoding. Another website that helped me a lot is this basic arithmetic coding by Arturo Campos.

Prediction

The previous example works great, but there is a problem… if we assign equal probabilities to each possible symbol (each byte) we won’t compress anything! The example above works because I took bigger probabilities for A and B then for C… So for it to work we need to guess the correct probabilities, and the better we do this, the smaller our file gets! Luckely there are a couple of methods to assign/guess these probabilities.

Read and save table

One thing you can do is to first read the whole file and save the amount you see each character. Then you can scale these amounts into probabilities between 0.0 and 1.0 and save these probabilities to a file. Next we can use these probabilities to encode (and decode) our message! This will take quite a bit of overhead because you have to save the table..

Runtime adjustment

Another thing we can do is to just start with equal probabilities for each symbol and adjust the probabilities during the encoding. If we use the same method in encoding and decoding our probability table will remain the same.

Prediction by Partial Matching (PPM)

So, we can adjust the probabilities at runtime and for example count all the symbols we have seen. But why stop there? For example in a piece of English text, the letter ‘E’ will probably have the highest count/probabilty. But if we encouter the symbols: “COMPRESSI” we know the next character will likely be an “O”, not an “E”! So what if we can enlarge our context? This is what PPM does, looking at the bigger picture. Not only count single symbols, but also combinations. The longer the combinations the more specific our predictions get (but also more memory is needed).

Context Mixing (CM)

With PPM you have one model which predicts the probability of the next symbol by looking at its past statistics. But why stop there? With Context Mixing (CM) you can have multiple models predicting the next symbol work together. When you do this right you and predict the next symbol even better and thus get better compression ratios! This is how the best current compression algorithms work.

Other methods

This is just one family of compression algorithms, there are a lot more which I won’t describe here (yet?). Instead of processing/guessing the next symbol you could also replace long series of symbols with shorter unique symbols. This is known as dictionary coding, an entire other family of compressors (including LZ, zip, gz).


Handling null in Java

Handling null in Java

Its a problem I encouter in most JEE projects I’ve worked on so far. Handling null-values. But why is this a problem? And what strategies can we follow to reduce the problem? That is what I’m trying to find out in this post.

Lets start with a piece of business logic, in a world where we don’t have null-values:

public BigDecimal getBalance(Person person) {
    Set<Account> accounts = person.getAccounts();
    BigDecimal totalBalance = BigDecimal.ZERO;
    for(Account account: accounts) {
        totalBalance = totalBalance.add(account.getBalance());
    }
    return totalBalance;
}

This looks good and understandable! But this isn’t what I see in most projects. Usually I see code like this:

public BigDecimal getBalance(Person person) {
	if(person != null) {
	    Set<Account> accounts = person.getAccounts();
	    if(accounts != null) {
	    	BigDecimal totalBalance = BigDecimal.ZERO;
	    	for(Account account: accounts) {
	    		if(account != null) {
	    			totalBalance = totalBalance.add(account.getBalance());
	    		}
	    	}
	    }
	    return totalBalance;
	} else {
		return null;
	}
}

Wow, that is not a pretty sight, not at all! What can we do about it and how did it happen?

Inversion of logic

The first strategy we can follow is based on inversion of logic which I’ve blogged about before. The idea is that we exit early, this will improve the readability of our method. Lets see that happens to our method is we follow this pattern:

public BigDecimal getBalance(Person person) {
	if(person == null || person.getAccounts() == null) {
		return null;
	}
	Set<Account> accounts = person.getAccounts();
   	BigDecimal totalBalance = BigDecimal.ZERO;
   	for(Account account: accounts) {
   		if(account != null) {
   			totalBalance = totalBalance.add(account.getBalance());
   		}
   	}
	return totalBalance;
}

This is somewhat better, a bit shorter, but we still have all the ‘!= null’ and ‘== null’ checks we don’t want.

Code by contract

The best way to get rid of null-checks is to get rid of nulls in your applicaties. Just don’t return a null in all of the methods…! This sounds very easy and straight forward, but it is a bit harder then it sounds because it has become such a habbit.

The good thing is that current IDE’s are implementing the @NotNull and @Nullable annotations. With these annotations you can tell other programmers, your IDE and static code analysis tools what your idea was when creating a method:

@Nullable
public Person getPerson(Long id) {
	return something.retrievePerson(id);
}
    

public void printPersonName(Long id) {
	Person person = getPerson(id);
	System.out.println(person.getName());
	//Causes warning: getPerson is Nullable, thus this is a possible NPE! 

}

It also helps you to clearly state your assumed preconditions:

public void printPersonName(@NotNull Person person) {
	System.out.println(person.getName());
	//Very good, we know we won't get a NPE here! 

}
    
    
public void executeThis() {
	Person person = null;
	printPersonName(person);
	//Causes warning: person might be null, thus can cause a NPE!

	//Code analysis tools and/or IDE will warn you about this.

}

It will also help you correct possible coding errors:

@NotNull
public Person getPersonFromDatabase(@NotNull Long id) {
	//Use JPQL

	Query query = em.createQuery("SELECT p FROM Person p WHERE p.id = :value");
	q.setParameter("value", id);
	return q.getSingleResult();
	//The IDE will complain about this. 

	//The database might return null, we don't allow returning null in this method.

}

Using this method you have some more certainties. But it isn’t a silver-bullet on its own. We have to stop and think, where do the null-values come from?

Actually, when you stop returning null (which is entirely up to you and your team) there are still situations which are ‘unchecked’. Namely external API’s, frameworks, the ORM-mapper you are using. So everywhere where you execute methods that you haven’t written, you still have to do manual checks. But make sure you do this right away. Then further on in the code, you don’t have to check anything because of your @NotNull-contracts.
If you do this to the Person object above, and all its fields, you will end up with the beautiful clean code of the first example. No checks, its just always filled by contract. The only thing you want to add is information about the parameters:

@NotNull
public BigDecimal getBalance(@NotNull Person person) {
    Set<Account> accounts = person.getAccounts();
    BigDecimal totalBalance = BigDecimal.ZERO;
    for(Account account: accounts) {
        totalBalance = totalBalance.add(account.getBalance());
    }
    return totalBalance;
}

In my experience this works very well, I’ve done this a couple of times, even before the @NotNull and @Nullable existed. Before this we would just add the information in our Javadoc. But with the IDE checking for it this has become a lot easier to use.

Null object pattern

A whole different approach then coding-by-contract is the use of a null-object. The idea behind this pattern is that you don’t return null, but instead you return a real object. In our example we would do the following:

public interface Person {

	String getName();
	void setName(String name);

	List<Account> getAccounts();
	
	//..etc..

}

public class NullPerson implements Person {
	
	public String getName() {
		return "";
	}
	
	public void setName(String name) {}

	public List<Account> getAccounts() {
		return Collections.emptyList();
	}
}

The huge advantage is that you can always safely call “person.getName()” and “person.getAccounts()” because even if you have a NullPerson the object still exists. This Null-Object is obviously usually a singleton.

public BigDecimal getBalance(Person person) {
    Set<Account> accounts = person.getAccounts();
                //NullPerson returns empty list, no more NPE!

    BigDecimal totalBalance = BigDecimal.ZERO;
    for(Account account: accounts) {
        totalBalance = totalBalance.add(account.getBalance());
    }
    return totalBalance;
}

A more elaborate but general version of this pattern is the special case pattern, named by Martin Fowler. Instead of just having a Null-special case you could also develop:

public class UnknownPerson implements Person {
	
	public String getName() {
		return "";
	}
	
	public void setName(String name) {}

	public List<Account> getAccounts() {
		return Collections.emptyList();
	}

}
public class InvalidatedPerson implements Person {
	
	public String getName() {
		return "";
	}
	
	public void setName(String name) {}

	public List<Account> getAccounts() {
		return Collections.emptyList();
	}
}

Now you can return much more information then just a meaningless “null”!

There is just one problem with this pattern. It also doesn’t just solve your problems. Why do we want to calculate the total balance of a NullPerson? The moment you retrieve a person and it is an instance of NullPerson, catch it and handle the situation appropiatly, don’t just continue.

Safe null operator

For a time there was speculation that the Safe-null-operator would make its way into Java 7 through Project Coin. If you’ve programmed in Groovy you might have seen it before:

public String getFirstLetterOfName(Person person) {
	return person?.getName()?.substring(0, 1);
}

The idea is that you use “?.” instead of “.”. The questionmark means: “If the variable we’re calling is null, the result is null, else, call the next method”.

So in this case:

  • If person is null: return null, else:
  • If getName() is null: return null, else:
  • Return result of substring(0, 1)

If you would now write this code it would be:

public String getFirstLetterOfName(Person person) {
	if(person == null) {
		return null;
	}
	if(person.getName() == null) {
		return null;
	}
	return person.getName().substring(0, 1);
}

You could also give a default value:

public void printName(Person person) {
	System.out.println(person?.getName() ?: "Anonymous");
}

If person or getName() produce a null the “?:” operator will return the default String.

Sounds pretty good eh? The only problem is that this new operator didn’t make the final list of changes for Java 7.

Fun fact: Do you know why the “?:”-operator is called the “Elvis”-operator? When viewed from the side, as smiley , it looks like Elvis. Including the big curl in his hair.


Placement of circle over points

Placement of circle over points

For the Queue ICPC programming game Capture I ran into a geometrical problem.
While programming my little robot I wanted to have an algorithm calculate this for me:

  1. I have a field with 122 points
  2. I have a circle of fixed size

How do I calculate where to put the circle so it encapsulates the most points?

This is what I came up with, three algorithms:

Algorithm #1: Centerpoint

The first algorithm was created as a test. It doesn’t find the perfect solution, but gives a decent solution.
First I loop over all the points, and I check if there are points located at CIRCLE_RADIUS length from our point. This returns a score. The best point has a lot of other points nearby.

This algorithm is very quick, but it has a huge disadvantage, the circle will always have one of our points as center.

It will never yield the perfect solution… In the following picture this algorithm produces the green circle:

Picture of points and three calculated circles

Algorithm #2: Heatmap

The next idea I got was based on a heatmap. It is very computer heavy, but it will generate the best solution.

It works like this (psuedocode):

for( int x = 0 to FIELD_SIZE )
	for( int y = 0 to FIELD_SIZE )
		Point pixel = new Point(x,y);
		pixelScore = 0;
		for( Point point: points ) {
			if( point.distance(pixel) < CIRCLE_RADIUS*2 ) {
				pixelScore++;
			}
		}
	}
}

The pixel with the best score is used in most circles. Thus, this would need to be the center of our circle!

In the image above you can see the resulting heatmap, and the cyan circle is placed on the best possible pixel.

(In most cases, there are more then one ‘best pixels’, which one you choose doesn’t matter)

Algorithm #3: Bron-Kerbosch-myself

The heatmap algorithm, mentioned above, takes a LOT of processing time and is far from the most efficient algorithm. For the Queue ICPC contest there is a time limit for each calculation, and I need it to speed up!

So I started to wonder:

- What do all the points in the perfect circle have in common?

Well, they all have a maximum distance to each other of CIRCLE_RADIUS * 2.

So I started to play with graph algorithms.

The lines you see in the image above are all the points that can be connected with a maximum length of CIRCLE_RADIUS * 2. All the lines show points that could possibly be in the same circle together.
Then I googled a bit and found the term ‘clique’. A clique is a group of points that all point to each other, just what we want with the graph shown in the picture!

When I searched a little further I came across the Bron-Kerbosch algorithm. It finds the perfect maximum clique for a given undirected graph! Again, just what we want!

Here is the pseudocode (from Wikipedia):

BronKerbosch1(R,P,X):
    if P and X are both empty:
        report R as a maximal clique
    for each vertex v in P:
        BronKerbosch1(R  {v}, P  N(v), X  N(v))
        P := P \ {v}
        X := X  {v}

But I ran into a little problem, I’d made a false assumption… If you have a triangle of three points, with all legs size N, and then draw a circle from the center… none of the points fall into the circle.

Picture of a circle inside a triangle, where the legs of the triangle are the circle's diameter. This causes all the corners to fall outside the circle.

Now I tried two ways to solve this, the first one is to use a smaller distance in the graph. If you only select points that are located (cosine(30) * CIRCLE_RADIUS * 2) every point will eventually fall into our circle. But this could eliminate the perfect circle obviously if two points in the perfect solution are further apart then (cosine(30) * CIRCLE_RADIUS * 2).

Then I desected the Bron-Kerbosch algorithm, and decided to change it a bit. This is what I ended up with:

BronKerboschVanRijn(R,P,X):
    if P and X are both empty:
        report R as a maximal clique
    for each vertex v in P:
        BronKerbosch1(R  {v}, InCircle({R,v}, P), InCircle({R,v}, X))
        P := P \ {v}
        X := X  {v}
        
InCircle(A, B):
    calculate minimal enclosing circle for points A
    return all B that are (euclidean distance) inside A

This returns all the maximal cliques that fall into our circle, and we are always sure they fall into our circle..! I think this will always generate the perfect solution, just as the heat map. In this the above picture, this algorithm produces the red circle.

It already is light years faster then the heat map algorithm, but I still need a bit more speed. I’m still struggling to improve my implementation, like trying to use a pivot as bronKerbosch2 (see wikipedia again) does.

Algorithm #4: ???

For some reason I still fail to believe I’m the first person in the world to tackle this problem. But I haven’t been able to find an algorithm for this. Some people recommended using a sweeping algorithm but I don’t understand how this is used to find the circle’s location. Others pointed me to Voronoi maps…

So if you have any suggestions, or know the algorithm I’m looking for, please add a comment :-)


I hate printers

I hate printers

  1. Why, when one color has run out of ink, you can’t print anything!?
  2. Why does a pencil cost $0,50 and does an ink-cartridge cost $30,-?
  3. Why does a pencil still work after 5 years and is an ink-cartridge completely dried up?
  4. Why is a new printer (including ink cartridge) sometimes cheaper then a seperate ink-cartridge (crazy!)
  5. Why do printers eat paper for lunch?
  6. Why is printer-software so invasive? What happened to a simple ‘driver’
  7. Why does most hardware run perfectly under Linux, except printers?

Screw this, I’ll just mail my report instead of printing it…

Printer-bashing comic: Why I believe printers were sent from Hell


Guess the algorithm

Guess the algorithm

Yesterday I found and programmed a nice little algorithm. I’m not going to tell you (yet) what it does and how its called, but I’ll just show the code:

private int function(int x, int y) {
	int r = 0;
	while(x!=0) {
		if((x&1)==1) {
			r+=y;
		}
		x>>>=1;
		y<<=1;
	}
	return r;
}

So tell me, what does this do, and what is the algorithm called?

Edit:

And indeed (it was a simple one) the correct solution is multiplication, and to be specific, Ethiopian or Russian Multiplication.

I’ll probably do more, harder ones, in the future..!


Learn to use Dependency Injection

Learn to use Dependency Injection

Recently I placed a comment on this interesting blog from Uncle Bob Martin (Robert C. Martin). It contains a brief description on how I teach people how to use the Spring Framework.

Now, by popular demand (one person requested it over Twitter), I’ll guide you through the method and examples I use in this blogpost. It explains why people should use frameworks like Spring and/or Google Guice, and how.

Ordering Milk

Lets take a look at the application we have. We have a service:

package nl.redcode.examples.milkman;

public interface MilkRequestService {

	/**
	 * Process a new order.
	 * @param customer
	 * @param amountOfBottles
	 */
	public void processOrder(String customer, Integer amountOfBottles);

}

And we have a DAO (data access object) which will take care of persisting our order:

package nl.redcode.examples.milkman;

public interface MilkDAO {

	/**
	 * Save a new order.
	 * @param customer
	 * @param amountOfBottles
	 */
	public void saveOrder(String customer, Integer amountOfBottles);
}

The implementation of this DAO isn’t really interesting, lets just pretent it goes to the database:

package nl.redcode.examples.milkman;

public class MilkDAODatabaseImpl implements MilkDAO {

	public void saveOrder(String customer, Integer amountOfBottles) {
		//Puts order in database

	}
	
}

And finally we have our service implementation:

package nl.redcode.examples.milkman;

public class MilkRequestServiceImpl implements MilkRequestService {

	private MilkDAO milkDAO;
	
	/**
	 * Create a new service:
	 */
	public MilkRequestServiceImpl() {
		milkDAO = new MilkDAODatabaseImpl(
				//With SQLConnection or something

				);
	}
	
	/**
	 * Place a new order for milk.
	 */
	public void processOrder(String customer, Integer amountOfBottles) {
		//Log the order:

		System.out.println("LOG: Customer " + customer + " wants "
				+ amountOfBottles + " bottle"
				+ ((amountOfBottles > 1) ? "s" : ""));
		//Save the order:

		milkDAO.saveOrder(customer, amountOfBottles);
	}
}

Lets pretent that we are good obeying programmers, although we didn’t write our unit test up front, we are going to do it right away.

So… we want to test the service, how are we going to do this? Well, lets just create the service, call it, and then check if it does what we want it to do!

package nl.redcode.examples.milkman;

public class MilkRequestServiceTest {

	MilkRequestService milkRequestService = new MilkRequestServiceImpl();
	
	@Test
	/**
	 * Test our milk request service.
	 * Pre:
	 * - We have a customer that wants to order 5 bottles of milk
	 * Post:
	 * - The milk DAO got a request to save 5 bottles of milk
	 */
	public void testProcessOrder() {
		
		final String customer = "testUser";
		final Integer amountOfBottles = 5;
		
		milkRequestService.processOrder(customer, amountOfBottles);
		
		//Eeehh.... how do we check the call to the DAO?

		
		//HELP!!

	}
}

We run into a problem rather quickly. Now this code makes a connection to the database and it might or might not save our order. But how do we check this? We could go to the database and check…

NO! Never go to the database in a unit test. We only want to test a single unit of work, and the database ain’t one of them.

We need to refactor our code…!

The Factory

One possible solution to this problem is using a factory method. A factory creates objects so you don’t have to. Its best shown using an example:

package nl.redcode.examples.milkman;

import java.util.HashMap;
import java.util.Map;

public class MilkFactory { //no pun intended

	
	/**
	 * Here we save the mapping:
	 */
	private static Map<Class, Object> mapping;
	
	/**
	 * Create the mapping
	 */
	static {
		mapping = new HashMap<Class, Object>();
		mapping.put(MilkDAO.class, new MilkDAODatabaseImpl());
		mapping.put(MilkRequestService.class, new MilkDAODatabaseImpl());
	}
	
	/**
	 * Set a mapping by hand.
	 * Should only be used when unit testing.
	 * 
	 * @param <T>
	 * @param clazz
	 * @param impl
	 */
	public static<T> void replaceMapping(Class<T> clazz, T impl) {
		mapping.put(clazz, impl);
	}

	/**
	 * Not threadsafe ugly code-monkey code.
	 * @param <T>
	 * @param requestedClass
	 * @return
	 */
	public static<T> T get(Class<T> requestedClass) {
		if(mapping.containsKey(requestedClass)) {
			return (T)mapping.get(requestedClass);
		} else {
			throw new IllegalArgumentException("Doesn't exist");
		}
	}
}

So, lets dissect this.

The method get(class, object) will return an implementation for a given Class. It uses a Map to get the mapping. The map is created during the static initialization (yuk!) and contains the default mapping, but we can also provide our own mapping using replaceMapping(class, object).

Now how do we use it? Lets see our new MilkRequestServiceImpl:

package nl.redcode.examples.milkman;

public class MilkRequestServiceImpl implements MilkRequestService {

	/**
	 * Place a new order for milk.
	 */
	public void processOrder(String customer, Integer amountOfBottles) {
		//Log the order:

		System.out.println("LOG: Customer " + customer + " wants "
				+ amountOfBottles + " bottle"
				+ ((amountOfBottles > 1) ? "s" : ""));
		
		//Save the order:

		MilkFactory.get(MilkDAO.class).saveOrder(customer, amountOfBottles);
	}
}

As you can see we no longer need the constructor, we get the required DAO from the factory when we need it.

Now we can test it using the replaceMapping method:

package nl.redcode.examples.milkman;

public class MilkRequestServiceTest {

	MilkRequestService milkRequestService = new MilkRequestServiceImpl();
	
	//@Test

	/**
	 * Test our milk request service.
	 * Pre:
	 * - We have a customer that wants to order 5 bottles of milk
	 * Post:
	 * - The milk DAO got a request to save 5 bottles of milk
	 */
	public void testProcessOrder() {
		
		final String customer = "testUser";
		final Integer amountOfBottles = 5;
		
		//Better use a mock here, for example using Mockito or EasyMock.

		MilkFactory.replaceMapping(MilkDAO.class, new MilkDAO() {
			public void saveOrder(String customer, Integer amountOfBottles) {
				//Check if the customer = testUser

				//Check if the amountOfBottles = 5;

			}
		});
		
		MilkFactory.get(MilkRequestService.class)
			.processOrder(customer, amountOfBottles);
	}
}

As the comment says, you are probably much better of here using a mocking framework like EasyMock or Mockito. But the point is, we can test our class now without going to the database! We got our control back.

Dependency Injection

Instead of writing a factory, there is a better way to do this. It is the Hollywood principle “Don’t call us, we’ll call you”.

All the dependencies of the objects are injected into them instead of created (initial example) or retrieved (factory example). So our service will look like this:

package nl.redcode.examples.milkman;

public class MilkRequestServiceImpl implements MilkRequestService {

	private MilkDAO milkDao;
	
	/**
	 * The milkDao is given to us by our creator.
	 * 
	 * @param milkDao
	 */
	public MilkRequestServiceImpl(MilkDAO milkDao) {
		this.milkDao = milkDao;
	}
	
	/**
	 * Place a new order for milk.
	 */
	public void processOrder(String customer, Integer amountOfBottles) {
		//Log the order:

		System.out.println("LOG: Customer " + customer + " wants "
				+ amountOfBottles + " bottle"
				+ ((amountOfBottles > 1) ? "s" : ""));
		
		//We just use the milkDao we got:

		milkDao.saveOrder(customer, amountOfBottles);
	}
}

Now lets take a look at our test-code, it now looks like this:

public void testProcessOrder() {
	
	final String customer = "testUser";
	final Integer amountOfBottles = 5;
	
	//Better use a mock here, for example using Mockito or EasyMock.

	MilkDAO testMilkDao = new MilkDAO() {
		public void saveOrder(String customer, Integer amountOfBottles) {
			//Check if the customer = testUser

			//Check if the amountOfBottles = 5;

		}
	};
	
	MilkRequestService milkRequestService = new MilkRequestServiceImpl(testMilkDao);
	
	milkRequestService.processOrder(customer, amountOfBottles);
}

We now have full control over the wiring. First we create our own little testMilkDao (use a mock here!) and we place it into our service. That’s all. Instead of the hidden creation in the service itself or in the factory we are in full control.

But if you want to use this application you’ll need “something else” to create all the objects and do the actual wiring. Lets create our own Spring or Google Guice..!!

package nl.redcode.examples.milkman;

public class MilkApplication {

	public static void main(String[] args) {
		MilkApplication app = new MilkApplication();
		app.run();
	}

	public MilkApplication() {
		//-----   Provide wiring:  -----

		MilkDAO milkDao = new MilkDAODatabaseImpl();
		milkRequestService = new MilkRequestServiceImpl(milkDao);
		//------------------------------

	}
	
	private MilkRequestService milkRequestService;
	
	/**
	 * Do stuff:
	 */
	public void run() {
		milkRequestService.processOrder("Roy van Rijn", 1);
	}
}

Using Spring

The wiring we do in the constructor is what Spring and Google Guice would do for us. In the case of Spring you’ll write something like this:

<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xsi:schemaLocation="
http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans-2.5.xsd">

	<bean id="milkDao" class="nl.redcode.examples.milkman.MilkDAODatabaseImpl" />

	<bean id="milkRequestService" class="nl.redcode.examples.milkman.MilkRequestServiceImpl">
		<property name="milkDao" ref="milkDao" />
	</bean>
</beans>

Now you’ll still need to retrieve these “beans” from Spring, this can be done using our old-friend the Factory!
It’ll look something like this:

ClassPathXmlApplicationContext appContext = new ClassPathXmlApplicationContext(
	new String[] {"applicationContext.xml"});
MilkRequestService milkRequestService = appContext.getBean("milkRequestService");

This instructs Spring to load the XML file and create all the objects. Then we retrieve the milkRequestService and it is fully wired and ready to use!

Using Guice

Google Guice works exacly the same, only instead of using XML to define the mapping it only uses Java code and annotations.

First we tell Guice which implementations are the default implementations, for example:

package nl.redcode.examples.milkman;

@ImplementedBy(MilkDAODatabaseImpl.class)
public interface MilkDAO {

	/**
	 * Save a new order.
	 * @param customer
	 * @param amountOfBottles
	 */
	public void saveOrder(String customer, Integer amountOfBottles);
}

We also do this to the MilkRequestService. Next we tell Guice where to inject these implementations, in this case using ‘Constructor Injection’:

/**
 * The milkDao is injected by Guice.
 * 
 * @param milkDao
 */
@Inject
public MilkRequestServiceImpl(MilkDAO milkDao) {
	this.milkDao = milkDao;
}

Now if we want to use it, we retrieve it from Guice like so:

public class MilkApplication {

	public static void main(String[] args) {
		MilkApplication app = new MilkApplication();
		app.run();
	}
	
	/**
	 * Do stuff:
	 */
	public void run() {
		
	    Injector injector = Guice.createInjector();
	    MilkRequestService milkRequestService = 
	        injector.getInstance(MilkRequestService.class);

		milkRequestService.processOrder("Roy van Rijn", 1);
	}
}

Thats about it, you’ve seen:

  • Why you should use these patterns
  • How you would program them yourself (ugly monkey-code-style)
  • How using Spring (with XML)
  • How using Google Guice!

Good luck and happy programming!

ps. The code examples are just examples…!!


What if your favourite movie was remade as porno

What if your favourite movie was remade as porno

What if your favourite movie was remade as a porn movie? How would it be called, what would the title be?

My collegues and I were discussing this, and we came up with a top 10. We’ve also started a twitter hashtag.

Top 10

  1. Shaving Ryan’s Privates (everybodies favourite)
  2. The Curious Taste of Benjamin’s Bottom
  3. Honey, I shagged the kids
  4. Missionary Impossible III
  5. Good Will Humping
  6. Free my Willy
  7. Legally Boned
  8. I Know Who you did last Summer
  9. Schindler’s Fist
  10. Cliff Banger

Honourable mentions

And some honourable mentions to the titles that just didn’t make the list:

  • When Harry ate Sally
  • Saturday Night Beaver
  • Spankenstein
  • Swollow Hal
  • Sorest Rump
  • Bangs of New York
  • American Bangster
  • Thighs Wide Shut
  • Citizen Came
  • The Green Milf
  • The Porn Identity
  • Crouching Woman, Hidden Camera

Does my car hate me?

Does my car hate me?

Why does my car do this to me? It bugs me everyday. When I drive with the snow outside I have to use my windscreen washer quite a lot. When I pull the little lever behind my steering wheel it spurts a jet of antifreeze/washer fluid onto my screen and it starts to wipe for about 10 times. Then it stops… my window is clean again!

picture of dirty windscreen

But after about 15 seconds it does one final sweep… and this last sweep always leaves ugly marks!

Why do cars do this!!!? First it cleans my window perfectly, and then spoils it!

Update:
A collegue adviced me this: If the car has just finished wiping, quickly switch on the manual and stop it. This will still cause one extra wipe, but it comes right after the others. This produces a slightly better result.

I tried this two times on my car (a Fiat Bravo) and it worked one time, the other time it still did the final whipe after around 10 seconds.


MD5 quine, fixed point

MD5 quine, fixed point

MD5 quines

Sometimes I let my mind wonder and I get crazy questions. Today was a good example, I encountered a MD5 hash and I started to wonder, would there be a hash which would (when hashed again) be the same?

Thus: MD5(x) = x

This would be a kind of MD5 quine, when fed into the algorithm you get the original value back. This is actually called an MD5 fixed point.

Information I’ve found

So I started investigating, soon I discovered this website about collisions. Its well known that all hashing algorithms must have collisions, you can’t always produce a unique hash for input larger then the output of course.

The output of the MD5 sum is 128 bit (16 byte) long, so the input should also have the same length. But the MD5 algorithm is defined to have 512 bits as input. This isn’t really a problem because the algorithm will extend smaller input with padding. Lets assume the MD5 sum of any input is uniformly distributed over all possible sums, then the probability that a 128-bit string is a fixed point is 1/2^128. This isn’t a crazy assumption because all hashing-algorithms are designed to distribute the output as uniformly as possible to avoid collisions.

So, the probability that no 128-bit string is a real fixed point is (1 - 1/2^128)^(2^128). The probability that there IS a fixed point is 1 - (1 - 1/2^128)^(2^128).

Since the limit as N goes to infinity of (1 - 1/N)^N is 1/e, and 2^128 is most certainly a very large number, this probability is almost exactly 1 - 1/e = 63.21%.

But, of course, there is no randomness involved here - there either is a fixed point or there isn’t. But, we can be 63.21% confident that there is a fixed point. (Also, notice that this number does not depend on the size of the keyspace - if MD5 sums were 32 bits or 1024 bits, the answer would be the same).

Looking for the fixed point

I’ve just implemented a small program to look for these hashes, even though I know it will take millions of years to check all the numbers. But you never know, I might get lucky ;-)

The first algorithm I created took a single random String as input and kept applying the algorithm to the output. Eventually it will:

  1. Go into a loop
  2. Find a fixed point (which is a loop of size 1)

The weird thing is, if it ends up in a loop of size 1… I’ve found two things. Not only a md5 fixed point, which creates itself after applying the algorithm. But also an input-value that produces this md5 as output, a collision!

Graph

Another interesting thing would be a complete graph of all md5 answers. Which loops can we find, which md5 has most collisions etc. But this would take eternity to calculate, even using all the machines in the world.

Open questions

  • Are there loops? (It is possible there aren’t any loops at all…?)
  • Are there loops of size 1, a.k.a. fixed points?
  • Which/how many 128 bit combinations can’t be created with the input values?
  • Which/how many collisions will you get with all the input values?

More thoughts, errors, solutions..?


Splitting up Spring Web Flow & Facelets into JARs

Splitting up Spring Web Flow & Facelets into JARs

In our current project we want to have multiple Spring Web Flow-flows in one WAR-file. But we also want the flows and pages to be inside seperate JAR files, making the application a bit more managable and modulair.

This sounds straightforward but it took quite a bit of code and time…

First I created a single WAR-project with all the basic Spring, JSF and Facelet configuration. Like any Spring Web Flow (SWF) project we have a project-servlet.xml.

The first thing I did was changing our flowRegistry:

<!-- The registry of executable flow definitions -->
<webflow:flow-registry id="flowRegistry" 
   flow-builder-services="facesFlowBuilderServices" 
   base-path="classpath*:flows">
      <webflow:flow-location-pattern value="/**/*-flow.xml" />
</webflow:flow-registry>

The classpath*: allows SWF to search the whole classpath for flow-directories containing a flow definition.
In our case it would be: /flows/module1/module1-flow.xml

When you try to run this, and access a page we got the following exception:

Caused by: java.lang.IllegalStateException: A ContextResource is required to get relative view paths within this context; the resource was file [D:\projects\projectfromjar\module1\bin\flows\module1\page1.xhtml]
	at org.springframework.faces.webflow.FlowViewHandler.resolveResourcePath(FlowViewHandler.java:110)
	at org.springframework.faces.webflow.FlowViewHandler.restoreView(FlowViewHandler.java:74)
	at com.sun.facelets.FaceletViewHandler.restoreView(FaceletViewHandler.java:316)
	at org.springframework.faces.webflow.JsfViewFactory.getView(JsfViewFactory.java:93)
	at org.springframework.webflow.engine.ViewState.resume(ViewState.java:193)
	at org.springframework.webflow.engine.Flow.resume(Flow.java:545)
	at org.springframework.webflow.engine.impl.FlowExecutionImpl.resume(FlowExecutionImpl.java:259)
	... 38 more

For some reason Spring Web Flow doesn’t want to load the facelet. After browsing around Spring’s forums I came across some solutions. They didn’t do the trick, only when combining several methods I got it working for Spring Web Flow 2.0.7.

This is how I did it, we need to tell Facelets to use our custom ClassPathResourceResolver:

<!-- To load flows and pages from JARs, use this resolver -->
<context-param>
      <param-name>facelets.RESOURCE_RESOLVER</param-name>
      <param-value>nl.redcode.ClassPathResourceResolver</param-value>
</context-param>

The resolver itself is basic but does the job:

package nl.redcode;

import java.net.URL;

import com.sun.facelets.impl.ResourceResolver;

public class ClassPathResourceResolver implements ResourceResolver {

	public URL resolveUrl(String path) {
	    return getClass().getResource(path);
	}
}

This will help Facelets to translate a given path to a java.net.URL using the current classloader.
Spring Web Flow is currently giving us a FileSystemResource, and this doesn’t work because we want to load the pages with our classloader. For this we have the following wrapper:

package nl.redcode;

import org.springframework.core.io.ClassPathResource;
import org.springframework.core.io.ContextResource;
import org.springframework.core.io.Resource;
import org.springframework.util.StringUtils;

class CustomClassPathContextResource extends ClassPathResource implements ContextResource {

    public CustomClassPathContextResource(String path, ClassLoader classLoader) {
        super(path, classLoader);
    }

    public String getPathWithinContext() {
        return getPath();
    }

    public Resource createRelative(String relativePath) {
        String pathToUse = StringUtils.applyRelativePath(getPath(), relativePath);
        return new CustomClassPathContextResource(pathToUse, getClassLoader());
    }
}

To force Spring to use this Resource instead of FileSystemResource we use a post processor:

package nl.redcode;

import org.springframework.beans.BeansException;
import org.springframework.beans.factory.config.BeanPostProcessor;
import org.springframework.context.ApplicationContext;
import org.springframework.context.support.GenericApplicationContext;
import org.springframework.core.io.ClassPathResource;
import org.springframework.core.io.Resource;
import org.springframework.core.io.ResourceLoader;
import org.springframework.webflow.definition.registry.FlowDefinitionRegistry;

public class FlowRegistryClassPathPostProcessor implements BeanPostProcessor {
	
    public Object postProcessBeforeInitialization(Object bean, String beanName) throws BeansException {
        return bean;
    }
    
    public Object postProcessAfterInitialization(Object bean, String beanName) throws BeansException {
        if(bean instanceof FlowDefinitionRegistry) {
            alterRegistry((FlowDefinitionRegistry) bean);
        }
        return bean;
    }
    
    protected void alterRegistry(FlowDefinitionRegistry registry) {
        for(String flowId : registry.getFlowDefinitionIds()) {
            ApplicationContext ctx = registry.getFlowDefinition(flowId).getApplicationContext();
            overrideResourceLoader((GenericApplicationContext) ctx);
        }
    }
    
    /**
     * Override the ResourceLoader:
     * We know our flow is always defined as "flows/module1".
     * From the context we can derive the name of the flow (module1)
     * So we build up the ClassPathResource base as:
     * "flows/"+ ctx.getResource("")+ "/"
     * 
     * @param ctx
     */
    protected void overrideResourceLoader(GenericApplicationContext ctx) {
    	final ClassPathResource cpr = new ClassPathResource("flows/"+ctx.getResource("").getFilename()+"/");

    	ctx.setResourceLoader(new ResourceLoader() {
        	
        	public ClassLoader getClassLoader() {
        		return cpr.getClassLoader();
        	}

        	public Resource getResource(String location) {
        		return new CustomClassPathContextResource(cpr.getPath() + location, getClassLoader());
        	}
        });
    }
}

When the FlowDefinitionRegistry is created we provide it with a new ResourceLoader. When the resources are requested by Spring Web Flow we create our own CustomClassPathContextResource. This consists of our current location plus the defined location (viewId).

To register this post processor add it to your project-servlet.xml:

<bean id="flowRegistryClassPathPostProcessor" class="nl.redcode.FlowRegistryClassPathPostProcessor" />

How to use it

In our project we have the following flow(s) defined in a seperate JAR:
/flows/module1/module1-flow.xml

And our pages are in the same directory:
/flows/module1/page1.xhtml
/flows/module1/page2.xhtml
etc…

In the flow we can now use the following view-id’s:

<?xml version="1.0" encoding="UTF-8"?>
<flow 	xmlns="http://www.springframework.org/schema/webflow"
		xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
		xsi:schemaLocation="http://www.springframework.org/schema/webflow
							http://www.springframework.org/schema/webflow/spring-webflow-2.0.xsd">

    <view-state id="start" view="page1.xhtml"/>

</flow>

Its also possible to have pages in other places, you can define the views as relative paths. For example:
”../../shared_pages/page2.xhtml” turns into “/shared_pages/page2.xhtml”
”../pages/page3.xhtml” turns into “/flows/pages/page3.xhtml”

The only problem we still have using this method is the deployment with RAD/Eclipse WTP and Facelets auto-refresh. For some reason after deploying our application locks the files in the bin-directory. Eclipse then can’t delete this directory and fails to publish. Ending in one big #fail. But a simple clean, clean, republish, clean, rebuild, restart, shout, scream, cry, rebuild and republish will solve this.

The big advantage is the fact that the flows and pages are now defined in their own JAR files, making releases and sharing classes (like shared services/shared menu’s etc) much easier.

Information on Spring forum


Cleaner code: Inversion of logic

Cleaner code: Inversion of logic

Design patterns

Almost all programmers have heard about and used design patterns. And there are a lot of them. Famous design patterns include the Singleton, Observer, Template method. These are all patterns that focus on objects and the relationship between them.

There are more groups of patterns, for example take Dependency Injection (or Inversion of Control). This is an architectural pattern. They tell you things about the design of the whole program. And there are specific pattern groups, like concurrency patterns.

These patterns help you solve common problems in a well defined way, other programmers will recognise the patterns used and it will help produce more maintainable code.

Inversion of logic

The patterns described above all say something about classes/methods and architecture. But I think another class of design patterns exist, which have a smaller granularity. These patterns say something about the code inside a single method. A good example is Inversion of logic.

Let me give an example, lets take the following code:

public void processRequests(List<RentalRequest> requests) {
	
	for (RentalRequest rentalRequest : requests) {
		if(rentalRequest.isFormFilledCorrectly()) {
			Tenant tenant = rentalRequest.getTenant();
			if(tenant.getAge() >= 25 && checkLicenceStillValid(tenant)) {
				//Approve the request

				//Process the request in database

				//Send email to HQ

				//Etc...

			}				
		}
	}
}

Its a basic car-rental service and is has some logic before a request is processed. To make this code more readable and maintainable we can do two things. Of course it would be better to factor out the validation-logic into another piece of code. So lets do that first:

public void processRequests(List<RentalRequest> requests) {
	
	for (RentalRequest rentalRequest : requests) {
    
		if(validateRequest(rentalRequest)) {
			//Approve the request

			//Process the request in database

			//Send email to HQ

			//Etc...

		}
	}
}

private boolean validateRequest(RentalRequest rentalRequest) {
	if(rentalRequest.isFormFilledCorrectly()) {
		Tenant tenant = rentalRequest.getTenant();
		if(tenant.getAge() >= 25 && checkLicenceStillValid(tenant)) {
			return true;
		}
	}
	return false;
}

Some programmers don’t like the validateRequest() method above because there are multiple exit points. This was more problematic in C code then in Java because in C you needed to do a bit more resource management (freeing mallocs etc), in Java I actually don’t mind having more then one exit-point in my code. In this case it makes it just a bit more readable. It would be easy to add a ‘requestIsValid’ boolean and fill that instead.

Anyway, the next step in refactoring this code is using what I call “Inversion of Logic”. The idea is that you don’t continue nesting if something is true, but instead inverse it, and bail out if something is false. The big advantage is that you’ll lose a lot of nesting, making the code more readable. I’m going to do this in two places, first in the processRequest for-loop, and second in the validateRequest method.

public void processRequests(List<RentalRequest> requests) {
	
	for (RentalRequest rentalRequest : requests) {
    
		if(!validateRequest(rentalRequest)) {
			continue;
		}
		
		//Approve the request

		//Process the request in database

		//Send email to HQ

		//Etc...

	}
}

private boolean validateRequest(RentalRequest rentalRequest) {
	if(!rentalRequest.isFormFilledCorrectly()) {
		return false;
	}
	Tenant tenant = rentalRequest.getTenant();
	if(tenant.getAge() < 25 || !tenant.checkLicenceStillValid(tenant)) {
		return false;
	}
	return true;
}

As you can see in the for-loop all the business logic is moved one indent back, this will make your code easier to scan for business rules. And if you look at the validateRequest method the code reads more fluent. Instead of stacking up and remembering the valid cases:

IF form is correct
AND tenant age correct
AND tenant licence is valid
THEN proceed

We now eliminate the bad cases first:

IF form is incorrect: deny rental
IF tenant’s age or licence is invalid: deny rental
ELSE proceed

I’m trying to do this everywhere I can, it realy helps the readability.


Java EE 6 released, including Servlet 3.0

Java EE 6 released, including Servlet 3.0

Today marks the release of Java EE 6. The reference implementation (Glassfish V3) has been released and the specifications are going into their final state very soon.

About two years ago, while I was attending the JavaOne conference, I first heard about the Servlet 3.0 ideas. As a web developer I’ve worked a lot with these Servlets so I was curious about the ideas. But what I saw wasn’t what I hoped for. On the contrary, what I saw was a huge mistake in my opinion!

So I decided to contact the guys behind this JSR, to ask for some more information and share my views. Some time passed but I never got a reply… My next move was just to write about it, first on my own blog, then on DZone (05/30/2008) and on The Server Side a half year later, december 2008.

The only ‘reply’ I got from the people of the JSR was in the days following my (re-)post on The Server Side. Glassfish has a short re-cap on what happened here.

Now that the release is final I’m actually glad with the result. All the issues I raised from the early draft have been fixed. This is what a simple servlet would have looked like in the early draft:

@Servlet(urlMappings={"/foo", "/bar"})
public class MyServlet {
     @GET
     public void handleGet(HttpServletRequest req, HttpServletResponse res) {
          //Handle the GET

     }
}

And this was my suggestion on how to improve it (see second article/link):

@ServletMapping(name="myServlet", mapping={"/foo", "/bar"})
public class MyServlet extends HttpServlet {

     @Override //keep strong typing!

     public void doGet(HttpServletRequest req, HttpServletResponse res) {
          ...
     }
}

And this is from the final release:

@WebServlet(name="myServlet", urlPatterns={"/foo","/bar"})
public class MyServlet extends HttpServlet {

     @Override //keep strong typing!

     public void doGet(HttpServletRequest req, HttpServletResponse res) {
          ...
     }
}

That’s very similair, maybe a little too similair..? But anyway, I’m pleased about the result. It’ll be a lot easier in the future to write Servlets and Filters and a lot of cool new features have been added too.

I love the spec, despite the lack of feedback and replies from the expert group, ignoring all positive feedback and constructive advice. If I now look at the way the annotations turned out its almost identical to my first sketch after their JavaOne presentation in March 2008.


Steve Oakley, the head hunter

Steve Oakley, the head hunter

Every once in a while head hunters call me. They call you at home, at work, they work out your email adress and mail you… This will probably sound very familiar to most IT professionals.

Anyway, the thing that strikes me is that about 50% of the time a head hunter calls, its Steve Oakley! And it isn’t just me that is getting calls from Steve Oakley, no, all my collegues and friends are getting calls from him as well!

So, are you in or out? Have you been called by Steve Oakley yet?

I went to work, and all I got was a call from Steve Oakley