Pages

Thursday, November 10, 2011

Introduction to LambdaJ: Get rid of those pesky loops

After a very long pause, I thought it'd be nice to introduce some cool Java technologies I stumbled upon lately.

So, straight to business, I want to talk a bit about LambdaJ. It's a super cool infrastructure which is targeting those loops you always end up writing in Java.

Let's see some examples.
Say you've got an address book, and it's saved in a List<Person> where Person has a getSurname() method.
We wish to get all those Smiths among the members of the address book.
Now, usually you find yourself writing something like:
List<Person> smiths = new ArrayList<person>();
for (Person person : addressBook) {
    if (person.getSurname().equals("Smith")) {
        smiths.add(person);
    }
}

Instead, we like this clean Python syntax:
smiths = [person for person in addressBook if person.getSurname() == "Smith"]

So, Java is not the most flexible language there is, but this LambdaJ syntax really nears perfection.
This will look like:
List<Person> smiths = select(addressBook, having(on(Person.class).getSurname().equals("Smith")));

Ok, that was nice. Now let's look at a foreach block.
Regularly, we'd see something like:
for (Person knight : newKnights) {
    knight.setTitle("Sir");
}

We could do this instead:
forEach(newKnights).setTitle("Sir");

Finally, lets sort. I won't even write the code that sorts the address book by first name without LambdaJ.
With LambdaJ it looks really cool:
sort(addressBook, on(Person.class).getFirstName());

So, many thanks to the developers who wrote this project, and for making it open source.
That's all for now, thanks for reading.

Sunday, April 3, 2011

Run a JUnit test repeatedly

I like JUnit. It's easy to extend, and easy to use.
After reading abyx's post on Retry Rule, I decided to write a post about running repeating tests with JUnit.


Hope you enjoy this:


Sometimes you wish to run a test many times. For example, it might have some random factor in it. To cover many cases, you'd like to run it a lot of times. What options are there?

First, and the most obvious, is a loop. Run a for loop, and see it fail:
 public class ExampleTest {  
      @Test  
      public void sometimesFail() {  
           for (int i = 0; i < 10; i++) {  
                int rand = new Random().nextInt(3);  
                if (rand % 3 == 0) {  
                     fail();  
                }  
           }  
      }  
 }  
This will generate a single test in the tree. It will fail on the first error and won't give you an assessment of how many times it took till it failed.


Another option is the Parametrized Runner. That would look like this:
 @RunWith(Parameterized.class)  
 public class ExampleTest2 {  
      @Parameters  
      public static Collection<Object[]>
                                 generateParams() {  
           List<Object[]> params =
                   new ArrayList<Object[]>();  
           for (int i = 1; i <= 10; i++) {  
                params.add(new Object[] {i});  
           }  
           return params;  
      }  
        
      public ExampleTest2(int param) {}  
        
      @Test  
      public void sometimesFail() {  
           int rand = new Random().nextInt(3);  
           if (rand % 3 == 0) {  
                fail();  
           }  
      }  
 }  
This is a nice solution, but the test is filled with unnecessary code. Also, all the tests in the class will run for each parameter. What if I only want to repeat a single method?


Here is a nice solution, in my opinion:
 @RunWith(ExtendedRunner.class)  
 public class ExampleTest3 {  
      @Test  
      @Repeat(10)  
      public void sometimesFail() {  
           int rand = new Random().nextInt(3);  
           if (rand % 3 == 0) {  
                fail();  
           }  
      }  
 }  
 Only state the method you want to repeat, and how many times to do this. The rest is done for you.


So, whats behind this code?
First, add an Annotation:
 @Retention(RetentionPolicy.RUNTIME)  
 @Target({ElementType.METHOD})  
 public @interface Repeat {  
      int value();  
 }  


Finally, lets add the Runner. This simply overrides the default JUnit runner (its a bit long, but not too much):
 public class ExtendedRunner extends BlockJUnit4ClassRunner {  
   
      public ExtendedRunner(Class<?> klass) throws InitializationError {  
           super(klass);  
      }  
   
      @Override  
      protected Description describeChild(FrameworkMethod method) {  
           if (method.getAnnotation(Repeat.class) != null &&  
                     method.getAnnotation(Ignore.class) == null) {  
                return describeRepeatTest(method);  
           }  
           return super.describeChild(method);  
      }  
   
      private Description describeRepeatTest(FrameworkMethod method) {  
           int times = method.getAnnotation(Repeat.class).value();  
   
           Description description = Description.createSuiteDescription(  
                     testName(method) + " [" + times + " times]",  
                     method.getAnnotations());  
   
           for (int i = 1; i <= times; i++) {  
                description.addChild(Description.createTestDescription(  
                          getTestClass().getJavaClass(),  
                          "[" + i + "] " + testName(method)));  
           }  
           return description;  
      }  
   
      @Override  
      protected void runChild(final FrameworkMethod method, RunNotifier notifier) {  
           Description description = describeChild(method);  
             
           if (method.getAnnotation(Repeat.class) != null &&  
                     method.getAnnotation(Ignore.class) == null) {  
                runRepeatedly(methodBlock(method), description, notifier);  
           }  
           super.runChild(method, notifier);  
      }  
   
      private void runRepeatedly(Statement statement, Description description,  
                RunNotifier notifier) {  
           for (Description desc : description.getChildren()) {  
                runLeaf(statement, desc, notifier);  
           }  
      }  
        
 }  


As always, here is the source code: http://tinyurl.com/3mu2zbc
Also, you can Search Amazon.com for JUnit books.

Friday, April 1, 2011

Building a Maze

I always like to discover some cool ways of using a simple data structure or algorithm to simplify a piece of code. Yesterday I overheard a conversation about Maze construction and the Disjoint-Set data structure, often considered used for optimization purposes only. So, I decided to try and implement this small example of how to quickly create a maze using this data structure.

The Disjoint-Set, for those who are not familiar, is a data structure that allows to keep track of groups, letting you join groups and find the group to which a specific component belongs, all in O(Log*(n)).
For more info, read: http://en.wikipedia.org/wiki/Disjoint-set_data_structure.

Now, lets think of a maze as a grid of cells. For cells X and Y, you can reach from X to Y through the winding maze if there is a continuous route without walls between the two. So, lets start with a maze in which each cell has all its 4 walls built. The goal is to get a maze in which there is exactly 1 way to get from any cell X to any cell Y. Now lets add the data structure into the image. We start with a Disjoint-set that has a group for each of the cells. Each turn we destroy a wall between 2 cells that belong to different groups. This way we open exactly 1 passage between each of the cells in one group to each in the other. We know we've finished when there is exactly one group in the set.

For those who like algorithms, this is actually an implementation of the Kruskal algorithm for finding Minimal Spanning Trees in graphs (if you take the grid cells as vertices and the walls as edges).
You can read more here: http://en.wikipedia.org/wiki/Kruskal%27s_algorithm
or you can look at some boos here: Books on Algorithms on Amazon

Lets look at some code.
A simple implementation of the Disjoint-set:

 public class DisjointSet {  
      private int[] set;  
      private int[] sizes;  
      private int size;  
      public DisjointSet(int size) {  
           this.set = new int[size];  
           for (int i = 0; i < size; i++) {  this.set[i] = i;  }  
           this.sizes = new int[size];  
           for (int i = 0; i < size; i++) {  this.sizes[i] = 1; }  
           this.size = size;  
      }  
      public int find(int item) {
           int root = item;
           // find the root
           while (set[root] != root) {
                 root = set[root];
           }
           // now shorten the paths
           int curr = item;
           while (set[curr] != root) {
                 set[curr] = root;
           }
           return root;
      }
      public int join(int item1, int item2) {  
           int group1 = find(item1);  
           int group2 = find(item2);  
           --size;  
           if (sizes[group1] > sizes[group2]) {  
                set[group2] = group1;  
                sizes[group1] += sizes[group2];  
                return group1;  
           } else {  
                set[group1] = group2;  
                sizes[group2] += sizes[group1];                 
                return group2;  
           }  
      }  
 }  

Now, lets build the maze:

 Maze createRandomMaze(int rows, int columns) {  
           Maze maze = new Maze(rows, columns);  
           // create all walls  
           List<Wall> walls = maze.getAllInnerWalls();  
           // remove all the walls you can  
           DisjointSet diset = new DisjointSet(rows*columns);  
           while (diset.size() > 1) {  
                int wallIndex = random.nextInt(walls.size());  
                int cell1 = walls.get(wallIndex).cell1;  
                int cell2 = walls.get(wallIndex).cell2;  
                if (diset.find(cell1) != diset.find(cell2)) {  
                     // we can remove the wall  
                     maze.removeWall(walls.get(wallIndex));  
                     diset.join(cell1, cell2);  
                }  
                walls.remove(wallIndex);  
           }  
           return maze;  
      }  

And here is the result:




















For the full code and much much more, visit my open-source project at: https://code.google.com/p/ai4u/
The code in this post is located at:
Disjoint-Set: https://code.google.com/p/ai4u/source/browse/com.ai4u.util/trunk/src/com/ai4u/util/disjointSet/ArrayDisjointSet.java
Maze: https://code.google.com/p/ai4u/source/browse/com.ai4u.util/trunk/src/com/ai4u/util/games/maze/Maze.java

Well, this is it for my first post.
Please, send me any ideas, questions or comments to My Email