Hacking Cocoon during summer

I guess that most of you reading my blog do not know that I was accepted for Google Summer of Code. I proposed to work on Cocoon’s expression handling during upcoming summer, you can find detailed proposal here.

What are benefits you may ask. Current situation is quite depressing when it comes to expression handling. First of all, we have dozen of them in use across the Cocoon. Some of them operate on similar but still different model so it’s very usual that you may access the same values differently depending on you ask for them from flowscript or jx template. What is worse, models and expressions itself are poorly documented. My task is to change that reality and I hope to not fail.

It is interesting that on Cocoon’s dev mailing list almost nothing happens. My guess is that everyone just waits for RC1 in silence and keeps fingers crossed. Yes, we need a lot of good faith because Maven seems to hurt us really badly. Torsten has told me about his never-ending struggle with Maven bugs, limitations or bad implementation of nice idea. Basing on my own experience I must say that from time to time Maven disappoints me also. The worst thing is that when you get stuck you also get the feeling that there is no way out. It’s also a time when you feel that you really wasting your time.
I hope we’ll not waste to much time because of Maven and Apache Cocoon 2.2 RC1 will get released soon.

Last thing I would like to mention is ongoing discussion about Cocoon’s minimal requirement for JVM version. As you may already seen reading the discussion I opt for Java 1.5 as minimal. The main argument for abandoning Java 1.4 compatibility is a cost for community of maintaining that compatibility. Really, only few persons develop (or at least test) Cocoon with Java 1.4, Continuum is running on Java 1.5, etc.
If you have something to add drop a comment here or post your thoughts to Cocoon’s mailing list.

Solution for singly-circularly-linked problem

I promised to post a solution for the problem I set earlier. Now it’s time to keep the promise.

The solution is really simple because the problem itself is trivial I would say. Imagine two racers at the running track that has circular shape both starting from the same position. Let’s assume that one trained harder and can run at double speed of the another racer. Let’s imagine that they start to race but do not finish after running a one lap. They continue to race, what will happen eventually? The answer is that faster one will lap the slower runner. That’s main idea behind the solution…

Let’s translate it to a terms used in programming. You have two variables (runners) pointing at the first element of the list. Now, each time one pointer moves two elements further but other one moves only by one element from the list further. You can observe the process at this picture:

Now we have two cases:

1. If list is not circularly-linked faster runner (pointer) will reach its end and that will be a sign for us that we have detected list that is not circularly-linked
2. If list has a cycle faster runner (pointer) will lap the slower one at some point and that will be an information for the algorithm that circularly-linked list has been detected

Obviously, the algorithm uses constant memory (two pointers). I’ll leave as an exercise to show that number of pointer shifts is not great than 2n where n is number of elements in the list.

Here you have simple implementation of this algorithm:

public class DetectCycle {

	static int steps = 0;

	public static void main(String[] args) {
		System.out.println(detectCycle(createLinkedList(50, -1)));
		System.out.println(steps);
	}

	static private boolean detectCycle(ListItem head) {
		ListItem slowerRunner = head;
		ListItem fasterRunner = head;
		steps = 0;
		while (true) {
			if (fasterRunner.getNext() == null) return false;
			fasterRunner = fasterRunner.getNext();
			if (fasterRunner.equals(slowerRunner)) return true;

			if (fasterRunner.getNext() == null) return false;
			fasterRunner = fasterRunner.getNext();
			if (fasterRunner.equals(slowerRunner)) return true;

			slowerRunner = slowerRunner.getNext();
			steps = steps + 2;
		}
	}

	static private ListItem createLinkedList(int numberOfItems,
                                                 int closeCycleAtPosition) {
		ListItem head = new ListItem();
		ListItem tail = head;

		for (int i = 1; i <= numberOfItems; i++) {
			tail.setNext(new ListItem());
			tail = tail.getNext();
		}

		if (closeCycleAtPosition >= 0) {
			ListItem item = head;
			for (int i = 1; i < closeCycleAtPosition; i++)
				item = item.getNext();
			tail.setNext(item); //closing cycle at specified position
		}

		return head;
	}

}

and ListItem class:

public class ListItem {
	private ListItem next;

	public ListItem() {
		next = null;
	}

	public ListItem getNext() {
		return next;
	}

	void setNext(ListItem next) {
		this.next = next;
	}
}

EDIT: I thought that it would be nice to tell you similar riddle. Here it goes:
How to count number of elements (legnth) of the list despite it has cycle or not. Rules are the same: algorithm must be linear and use constant amount of memory. Again solution is simple!

Cocoon 2.2 RC1 release delayed

I have finally some free time. In Poland, 7th of June is a catholic feast so everyone has a free day.

I have a bad news about Cocoon’s upcoming release. Even though it was nearly there we had to delay the release because of small but important issue. We had a dependency on a artifact that is not officially released (and is not available on Maven’s central repository).

I think that the fault comes from the bad practice of Cocoon 2.1.x days that we were depending on snapshot versions and shipping them with our big, fat distribution. Use of Maven enforces us to be more careful on how we handle our dependencies, we need to work out new rules and practices.

I must admit that I do not blame Maven and I’m quite happy with the situation. The blocking issue should be fixed really soon and we’ll make that eagerly awaited announcement. What’s also important, we’ll not have a dependency on cryptic version of commons-jci that no one will have an idea what it was a year later.

Stay patient a little bit longer, Cocoon will come.