Software developer blog

Test driven mockery

This year I have talked at different Hungarian venues about software development related topics several times. Although these presentations are captured on video and are available on the internet they are in Hungarian, so I decided that the next few posts will explore some of them in English, and in more depth.

I gave the Test Driven Mockery talk at the April event of PHP Meetup Budapest. Although code examples and frameworks are in PHP, the talk is basically language agnostic, and it's just as useful for PHP programmers as it is for Java, C#, Ruby or even C++ coders. After all: it's about test doubles in general.

At the time of writing this blog entry more and more software developers and companies decide to adapt test driven development as one of their primary practices to avoid code rot and fear of change. Of course there are crowds who still haven't even tried TDD either because they haven't heard about it, or it sounded too weird for them to try. However there is another lot more interesting group of educated professionals who after practicing TDD for a considerable amount of time decide to abandon it. As I was talking with a group of these people I recognized that most of the time their disappointment in the technique is easily tracked back to their misunderstanding of a very important related topic: test doubles and mocking. On one hand if you completely avoid using them you end up with a slow and fragile test suite that's hard to maintain, but if you use too many of them the promise of ease of change, well tested and flexible code becomes a lie. Finding a good balance is kind of an art.

How to find maximal cliques

Facebook used to have this awesome list of programming puzzles that were freely available. One of them was peak-traffic, which can be rephrased as the maximal cliques problem pretty easily. Unfortunately a graph can have exponential number of maximal cliques, so it's not surprising that we can not find a polynomial algorithm for listing all possible maximal cliques in a graph. However there are output sensitive algorithms: as long as the number of maximal cliques is relatively low each can be reported in a short time.

A complete sub-graph of a graph is called a clique, much like we call a group of friends a clique if they all know each other.

I knew that I was looking for such an algorithm, but it was kind of hard to find a detailed enough description on the Internet.  At the time of writing Wikipedia does provide a short description of the algorithm devised by Tsukiyama et al. but there are a number of details omitted, making it kind of hard to come up with the right implementation.

My aim is to provide a simple to understand description of the algorithm (without proof that it works correctly) and share my implementation in C++. (Type `make smoke` to compile and test.) The source I've been using - apart from Wikipedia - was a 2004 paper written by Kazuhisa Makino and Takeaki Uno: New Algorithms for Enumerating All Maximal Cliques.

Snake cube

Few weeks ago one of my colleagues showed me this puzzle:

Snake cube

Snake cube puzzle

It's basically composed of 27 cubes, which are linked together by their faces. Each pair can be rotated around their common face. The aim is to fold the snake into a cube like this:

Solved snake cube

The snake cube once it is solved

Needless to say, my first thought was to write a backtracker that solves the cube for me. After all it's more fun to write the program, than to play around with it for hours. It didn't take long. After I was done with that, I started to ask myself questions like:

  • Are there other combinations with a single solution?
  • Are there combinations with more than one solution?
  • Are there palindromic snakes, that are solvable?
  • How many different solvable snakes are there?

I quickly found the answers to those on Jaap's Puzzle Page. I won't repeat the results that are available there, go and check it out if you are interested. On the other hand, it did not contain the source code for the backtracker, so I decided to show you how something like that could be done.

@ //

Postponable iterator

When I started this blog I had no idea how hard it will be to post useful things without revealing too much about the "top secret" projects we are involved in. 🙂 This time though I've been allowed to release an entire class that turned out to be useful in an application we were developing a while back. The piece of software below was created with a financial support by Uratim Ltd. and can be used under the terms of the GPL license. YAY for free software.

Postponable Iterator source

The iterator pattern is one of the most frequently occurring patterns used in software design. Even before one learns about design patterns inevitably implements an iterator without actually realizing. The problem I came across not so long ago was that I had an iterator that was returning  jobs from job packets that would have to be processed but there were a number of constrains I had to keep in mind:

  • For each job there is a resource assigned for the job. It can only be executed using the resource assigned to it.
  • As long as possible certain resources should not be accessed too frequently. (But they can be accessed more frequently when it is necessary.)
  • Packages are processed semi asynchronously: all jobs in one package are returned at once, but there may be more that one pending package. The maximal number of packages under simultaneous processing is a parameter.
  • When there are too many jobs waiting for a single resource than access times should be gradually decreased to avoid too long waiting times for jobs.
@ //

Event based template method

The last few weeks were more than hectic for me. We are approaching the end of a bigger project, and starting a new one, so I didn't have much time for my blog. Anyhow... during the design phase of the newer project I came across a very interesting design problem. We are developing an algorithm that has a pretty rigid structure at a higher level with steps that are invariable, and other (more heuristic) steps that can vary independently. Since we want to be able to quickly replace the heuristic steps of the algorithm (maybe even at runtime), and have a clean design with as few code duplication as possible I had to come up with a way to decouple these steps from the higher level structure of the algorithm.

The first solution that came to my mind was using the Template Method design pattern as described in the excellent book on Design Patterns by Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides. While their version comes with many advantages, in this particular situation it has a quite obvious drawback: it uses inheritance, which would make it less convenient to adjust the algorithm, and vary the different heuristic steps independently, and downright impossible to do this at runtime.

I decided to use an event based approach. Instead of defining pure virtual functions for the hooks I defined callbacks similar to events. When the algorithm runs on a callback during execution, it calls the function(s) registered for it. There is however a significant difference between these callbacks and traditional events: in some cases you may want to make sure, that one and only one function is registered for a specific callback, and you may also want to use the return value of the function for something more complex. (Some implementations of event handling require the return value to be a boolean, and use it to prevent further listeners from getting executed when one of the listeners returns false.)

@ //