Got Object?

There are several places that describe this problem in detail. However, there is one place that describes very well (IMHO). That is the Wolfram MathWorld site. Since I am reading Python Algorithms by Magnus Lie Hetland, and I am trying to improve my python skills, I decided to tackle this problem using python. Here is the code. I hope you will find it useful.

#!/usr/bin/env python
# encoding: utf-8
"""
Josephus permutation. A theoretical problem related to a certain
counting out game. See en.wikipedia.org/wiki/Josephus_problem
or http://mathworld.wolfram.com/JosephusProblem.html for more details.

Created by Huascar A. Sanchez on 2011-03-21.
Copyright (c) 2011 Huascar A. Sanchez. All rights reserved.
"""

from collections import deque
def Josephus(m,n,s = 1):
    """Josephus problem. Only s survivor (s) (the winner(s)).
       Input: n - number of people in the circle
              m - frequency of people to be killed.
              s - number of survivors you want.
       Output: not output. all results will be printed
       on screen.
    """
    N = n + 1
    M = m - 1
    S = s;
    if S <= 0: S = 1 # only one survivor
    Q = deque()
    #print("construct the list\n")
    for p in range(1,N):
        Q.append(p)

    toString = []
    #print("start the game now!!\n")
    while len(Q) > S:
        for dp in range(0,M):
            Q.append(Q.popleft())
        toString.append(str(Q.popleft()))

    print(' '.join(toString))
    while Q:
       print("winner " + str(Q.popleft()))

Josephus(5,9)
Josephus(3,40,2)

Wow, version 0.3 of FilterQ has been released and is available at filterq.googlecode.com. Several cool features have been added, several bugs have been fixed. But the best of all things, at least for me, is that I am using it in my JUnit 4.5 extensions project. FilterQ is my lightweight filtering API for Iterable Objects (yeah, you got it right, it is an API for objects implementing the Java’s Iterable interface). The concepts behind FilterQ’s API have been inspired by LinQ, and Quaere use cases. In order to illustrate its specific API methods, I have compiled some interesting usage scenarios, which will be distributed in 3 posts. The first post will illustrate the basic usage scenarios. While these are small scenarios they convey the power of this API.

Basic usage scenarios
1. basic filtering

// select all the prime numbers found within (0...1000),
// while making sure that that 117 is not included in our result.
from(range(1,1000)).where(numIsPrime()).select(not(eq(117)));
// or simply
from(range(1,1000, numIsPrime().or(not(eq(117))))).select();

//  which one should I choose? well, it depends. If you prefer readability
//  over brevity, then choose the first one.

2. dealing with results

//  from the above results, count all of the prime numbers greater than 100 and less than 500.
//  Let's assume that the result is stored in a var of type "Iterable<Integer>" called foo.
count(foo, gt(100).and(lt(500));

// or simply count them all
count(foo);

3. dealing with two Iterables in a single loop

for(Integer each : intersect(range(1,100, mod(3)), range(60,250, mod(13)))){
       System.out.println(each)
}

// or
for(Integer each : union(range(1,100, mod(3)), range(60,250, mod(13))))){
	System.out.println(each)
}

3. dealing with transformations

final Integer[] numbers = {5, 4, 1, 3, 9, 8, 6, 7, 2, 0};
final String[]   strings   = {"zero","one","two","three","four","five","six","seven","eight", "nine" };
final Iterable<String>  result  =  from(numbers).apply(indexed(strings));

System.out.println(asList(result));
// result: five, four, one, three, nine, eight, six, seven, two, zero	

4. skipping elements

from(Arrays.asList(1, 2, 3, 40, 20, 30, 100)}).where(gt(20).and(lt(100))).skip(1);
// and the result is?

5. ordering elements

from(Arrays.asList("John", "Mary", "Roberto", "David", "Fernando")).orderBy(length()).select();
// and the result is? [John, Mary, David, Roberto, Fernando]

6. dealing with objects’ private members

final Person a = new Person("John", "Peterson");
final Person b = new Person("Pete", "Peterzon");

final List<Person> ppl = Arrays.asList(a, b);
final Iterable<Person> t = from(ppl).where(eq("lastName", "Peterson")).select();

System.out.println(t);
// and the result is?	   	   

7. concatenating elements

final List<Integer> a = Arrays.asList(1, 2, 3, 3, 4);
final List<Integer> b = Arrays.asList(2, 3, 4);

final Iterable<Integer> result = concat(a, b);
System.out.println(result);

// and the result is?

This is all for today. I’ve just covered the first out of 3 posts covering FilterQ’s usage scenarios. Next post will illustrate other functionality, such as FilterQ’s XML support and Java Reflection API. Till next time.

VarArgs Null checking? This should be easy, right? All we need to do is put a “VarArgs”.length == 0 check before the important method’s body and we are set (See Checker class), correct?

class Checker {
	public void check(Arg... args){
		if(args.length == 0) return;
		final List<Arg> someArgs = Arrays.asList(args);
		for(Arg each: someArgs){
			System.out.println("checked:" + each.toString());
		}
	}
}

class Arg{
  private final String name;
  Arg(String name){this.name = name;}
  @Override public String toString(){return name;}
}

The above check should work nicely under the following circumstances

new Checker().check(new Arg("one"), new Arg("two"));
new Checker()

Unfortunately, it won’t work under the following one, which will actually throw the exception that you were trying to avoid: NullPointerException.

new Checker().check(null, null); // Ooh! a NullPointerException....

how to fix this? Easy…

class Checker {
	public void check(Arg... args){
		if(args.length == 0 || Arrays.asList(args).contains(null)) return;
		final List<Arg> someArgs = Arrays.asList(args);
		for(Arg each: someArgs){
			System.out.println(each.toString());
		}
	}
}

This should definitely work nicely. This is all for today. Until next time.

This post will show you how to use the for-each loop for reading files.  This approach tried to replace the following approach

    try {
        BufferedReader in = new BufferedReader(new FileReader("infilename"));
        String str;
        while ((str = in.readLine()) != null) {
            process(str);
        }
        in.close();
    } catch (IOException e) {
    }

with this one:

    final IterableFileReader e = new IterableFileReader(new File("SomeFile.WithSomeExtension"));
    for(String eachLine: e){
        process(eachLine);
    }

The source code of my solution is illustrated herein:

public class IterableFileReader implements Iterable<String>{
    private final BufferedReader reader;
    public IterableFileReader(InputStream is, Charset encoding) throws IOException {
        reader = new BufferedReader(new InputStreamReader(is, encoding.toString()));
    }

    public IterableFileReader(File file) throws IOException {
        this(new FileInputStream(file), Charset.UTF_8);
    }

    public Iterator<String> iterator() {
        return new Iterator<String>(){
            private String line;
            public boolean hasNext() {
                try {
                    line = reader.readLine();
                } catch (IOException e) {
                    throw new IllegalStateException(e);
                }
                return line != null;
            }

            public String next() {
                return line;
            }

            public void remove() {
                throw new UnsupportedOperationException("remove is not supported. sorry dude!");
            }
        };
    }
}

I hope you will find this approach useful. Ok, time is up. I gotta go, my daughter is crying. Till next time.

By expanding (more like enhancing :) ) the filter pattern described here and borrowing some of the beauties of the matcher pattern in Guice, I coded a more concise version of this filter pattern. Now this pattern’s implementation has a fluent API for combining other filters together, a place where all filters can be defined, a way of negating filters, etc. Further in this post I will provide a simple example that describes how the newer version of this pattern can be utilize. But before showing the example, I will provide the pattern’s newer definition and implementation herein.

Filter pattern’s main interface…

public interface Filter <T> {
    Filter <T> and(Filter <? super T> thing);
    Iterable <T> filter(Iterable <T> thing);
    boolean evaluate(T thing);
    Filter <T> or(Filter <? super T> thing);
}

and its abstract implementation…

public abstract class AbstractFilter <T> implements Filter <T> {
    public Filter<T> and(Filter<? super T> thing) {
        return new AndFilter<T>(this, thing);
    }

    public Iterable<T> filter(final Iterable<T> thing) {
        return new Iterable<T>(){
            public Iterator<T> iterator() {
                return new FilteringIterator<T>(
                	AbstractFilter.this,
                	thing.iterator()
                );
            }
        };
    }

    public Filter<T> or(Filter<? super T> thing) {
        return new OrFilter<T>(this, thing);
    }

    private static class AndFilter<T> extends AbstractFilter<T> {
        private final Filter<? super T> one;
        private final Filter<? super T> two;

        AndFilter(
        	Filter<? super T> one,
            Filter<? super T> two
        ) {
            this.one = one;
            this.two = two;
        }

        public boolean evaluate(T thing) {
            return one.evaluate(thing)
            	   && two.evaluate(thing);
        }
    }

    private static class OrFilter<T> extends AbstractFilter<T> {
        private final Filter<? super T> one;
        private final Filter<? super T> two;

        OrFilter(
        	Filter<? super T> one,
            Filter<? super T> two
        ) {
            this.one = one;
            this.two = two;
        }

        public boolean evaluate(T thing) {
            return one.evaluate(thing)
            	   || two.evaluate(thing);
        }
    }

    private static class FilteringIterator<T> implements Iterator <T> {
        private final Filter <T>     filter;
        private final Iterator <T>   base;
        private       T              next;

        FilteringIterator(
        	Filter<T> filter,
        	Iterator<T> base
        ){
            this.filter = filter;
            this.base = base;
            tryNext();
        }

        private void tryNext() {
            next = null;
            while (base.hasNext()) {
                final T item = base.next();
                if (item != null && filter.evaluate(item)) {
                    next = item;
                    break;
                }
            }
        }

        public boolean hasNext() {
            return next != null;
        }

        public T next() {
            if (next == null) throw new NoSuchElementException();
            final T returnValue = next;
            tryNext();
            return returnValue;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}

Now that I have provided this pattern’s definition and implementation, I will proceed with a simple example of its use. This example will deal with the Java Reflection API. Imagine that you are trying to query all the methods in a class which names start with “eq”, “has”, “toS” and have the Object class as a parameter. Most of the times you will have multiple IFs checking the methods of your interest. What if I don’t want to do that and instead, I want to use the Filter design pattern. Well, in order to do that all you need to code are two basic filters: one for looking at the methods’ names and the other one for looking at the methods’ parameters types.

    public static Filter <Method> containedParameters(final Class<?>... params){
        return new AbstractFilter <Method>(){
            public boolean evaluate(Method thing) {
                final List<Class<?>> s = Arrays.asList(
                	thing.getParameterTypes()
                );

                for(Class<?> each : params){
                    if(s.contains(each)){
                        return true;
                    }
                }
                return false;
            }
        };
    }

    public static Filter <Method> startedWith(final String... prefixes) {
        return new AbstractFilter <Method>(){
            public boolean evaluate(Method thing) {
                for(String prefix : prefixes) {
                    if(thing.getName().startsWith(prefix)){
                        return true;
                    }
                }
                return false;
            }
        };
    }

Simple, huh? totally!
Well, what if you want to negate one of those filters? Well, this is even simpler to implement:

    public static <T> Filter <T> not(final Filter <T> filter) {
        return new AbstractFilter <T>(){
            public boolean evaluate(T thing) {
                return !filter.evaluate(thing);
            }
        };
    }

And to finalize this post, here is how to put these filters to work:

public class RunPattern {
    private RunPattern(){}
    public static void main(String... args) {
        // calling filters one after another
        for(Method each : containedParameters(Object.class)
        	.filter(startedWith("eq", "has", "toS")
        	.filter(Arrays.asList(Object.class.getDeclaredMethods())))){
           System.out.println(each.getName());
        }

        // or maybe you can start using and & or operators
        final Filter <Method> m1 = containedParameters(Object.class)
        						   .and(startedWith("eq", "has", "toS"));

        for(Method each : m1.filter(Arrays.asList(Object.class.getDeclaredMethods()))){
            System.out.println(each.getName());
        }

        // which method do you you prefer?
        // it will be up to you...

        // hmmm....what if?
        final Filter <Method> m2 = not(containedParameters(Object.class))
        						   .and(startedWith("eq", "has", "toS"));
        for(Method each : m2.filter(Arrays.asList(Object.class.getDeclaredMethods()))){
            System.out.println(each.getName());
        }

    }
}

Hopefully you will find this newer version of this pattern useful. Ciao!

As you know when it comes to casting a la Java 1.4 a developer will have to write, typically, something like this:

Object a = "iron man";
String  b = (String)a;

Well, there is nothing wrong with this code. However, it is not pretty :). With Java 5.0 the casting mechanism is more explicit and nicer. The best thing of it is that it does not throw warnings, which it is a big deal :)

Object a = "iron man";
String  b = String.class.cast(a);

Not that bad, huh? Hmm, well…Okay, Okay, you got me. This still does not look that pretty and it is more verbose than the (Object)a style. How can I make it prettier? the ans: Generics

public static <T, E extends T> E cast(T me, Class<? extends E> to){
    return to.cast(me);
}
....
Object a = "iron man";
String  b = cast(a, String.class); 

Believe it or not, I love this technique. It works like a charm with objects that are part of the same inheritance chain. I know this method requires more tweaking to make it suitable for handling the casting of collections. But hey! this is just a working idea!

Jesse described a technique for handling methods that always throws. This is a very interesting technique. Having written that, would it not be nice to encourage the use of this technique, in our Java coding conventions, as a way to document DRY exceptions? Honestly, I’d’ think we should. It would prevent us from repeating the same description of our exceptions numerous times in our JavaDocs… Disclaimer: this is just a very simple example that tries to convey my point :)

/**
 * @throws Violation
 *      due to {@link #unableToFindConfigFile(String, Throwable)}
 */
public void loadConfig() throws
Violation {
  try {
     //.... some code goes here to
     //.... load a config file.
  } catch (RuntimeException re){
	throw unableToFindConfigFile(
           "loadConfig():void",
           re
        );
  }
}

/**
 * @throws Violation
 *      due to {@link #unableToFindConfigFile(String, Throwable)}
 */
public void refreshConfig() throws
Violation {
	loadConfig();
}

private static Violation unableToFindConfigFile(
	String pointOfCall,
	Throwable cause
) throws Violation
{
	final StringBuilder msg = new StringBuilder()
		.append("Error when calling ")
		.append(pointOfCall)
		.append(". Reason:")
		.append(cause);
	throw new Violation(msg.toString(), cause);
}

/**
 * @throws Violation
 *   due to {@link #unableToFindConfigFile(String, Throwable)}
 */
public void loadConfig() throws
Violation {
   try {
	//.... some code goes here to load
	//.... a config file.
    } catch (RuntimeException re){
	throw unableToFindConfigFile(
		"loadConfig():void",
		re
	);
    }
}

/**
 * @throws Violation
 *   due to {@link #unableToFindConfigFile(String, Throwable)}
 */
public void refreshConfig() throws
Violation {
	loadConfig();
}

private static Violation unableToFindConfigFile(
	String pointOfCall,
	Throwable cause
) throws Violation
{
	final StringBuilder msg = new StringBuilder()
		.append("Error when calling ")
		.append(pointOfCall)
		.append(". Reason:")
		.append(cause);
	throw new Violation(msg.toString(), cause);
}

Some of this approach’s benefits:

1. No more boilerplate text when documenting exceptions.
2. The intent of the exception is clearly communicated via a factory method.
3. We are hiding the complexity of the exception’s declaration behind a consistent exterior.

I’ve found the Cache Management Pattern very useful in more than a couple of projects that needed a simple caching mechanism. Now that we have Generics at our disposal, I think this pattern deserves a tiny change. Something like a generic structure or code that we can follow or use every time we need to cache specific objects.

The Structure

public interface ObjectCacheManager<K, T> {
    T fetch(K aKey);
}

public interface ObjectFactory<K, T> {
    T make(K aKey);
}

public interface Cache<K, T> {
    void add(T anEntry);
    T fetch(K aKey);
}

An Example

Note: this is just a toy example… you’ve been warned :) Its purpose is to show you the dynamics of this pattern.

public class FooCache implements Cache<String, Foo> {
    private final Map<String, Foo> cache;
    public FooCache(){
        cache = new ConcurrentHashMap<String, Foo>();
    }

    public void add(Foo entry) {
        final String key = entry.getName();
        if(cache.get(key) == null){
            cache.put(key, entry);
        }
    }

    public Foo fetch(String givenAKey) {
       return cache.get(givenAKey);
    }
}

public class FooFactory implements ObjectFactory<String, Foo> {
    public Foo make(String aKey) {
        return new Foo(aKey);
    }
}

public class FooCacheManager implements ObjectCacheManager<String, Foo> {
    private final ObjectFactory<String, Foo>    server;
    private final Cache<String, Foo>            cache;
    public FooCacheManager(){
        server  = new FooFactory();
        cache   = new FooCache();
    }

    public Foo fetch(String aKey) {
        Foo foo = cache.fetch(aKey);
        if(null == foo){
            foo = server.make(aKey);
            if(null != foo){
                cache.add(foo);
            }
        }
        return foo;
    }
}

Let’s get more specific with its use.. shall we?

    @Test
    public void verifyFooCachingSystem(){
        final FooCacheManager manager = new FooCacheManager();
        final Foo a = manager.fetch("Superman");
        final Foo b = manager.fetch("Superman");
        Assert.assertEquals(a, b);
    }

And there you go…

Every time we try to write a benchmark for particular functionality, we habitually specify a load (max iterations), write a for-loop, set timers before and after the loop, and call the method of interest inside this loop. This typically involves copying & pasting from another benchmark and adapting the current benchmark to your needs. Why don’t we try, instead of copy & paste, to define an idiom that we could reuse for writin benchmarks? Something like this

public class Benchmark {
    private final int iters;
    public Benchmark(int iters){
        this.iters = iters;
    }

    public <T>long given(
    final Callable<? extends T> op
    ) throws Exception
    {
    	// warm things up
        for(int idx = 0; idx < 10000; idx++){}

        long time = System.nanoTime();
        for(int idx = 0; idx < iters; idx++){
            op.call();
        }
        time = System.nanoTime() - time;
        return TimeUnit.NANOSECONDS.toMillis(time);
    }
}

How can use this? This is simple….

    public static void main(
    String[] args
    ) throws Exception
    {
      System.out.println(new Benchmark(100000).given(
      	new Callable<Void>(){
            public Void call() throws Exception {
                System.out.println();
                return null;
            }
      }));
    }

Using this idiom will make the benchmarking of method calls easier…So please start using it :)

I recently coded a fairly tiny application that made use of the MVC pattern. One of the things that I noticed while I was writing it was that I was down-casting a lot. Imagine something like this:

Example

// main type
interface Model {
	void someMethod();
}

// implementation
class Mixer implements Model {
    public void anotherMethod(){
    	System.out.println("hey");
	}
    public void someMethod() {
    	System.out.println("dude");
	}
}

Now If I want to invoke both methods, I’d have to do something like this:

    final Model m = new Mixer();
    m.someMethod();
    // downcasting .
    // imagine this with more model objects
    // with unique methods...
    ((Mixer)m).anotherMethod();

I am really annoyed about this whole downcasting. It does not make my code look that pretty. So I decided to use Generics; more in specific the recursive bounds idiom which was used in the implementation of the Java 5.0′s Enums.

The solution

interface SuperClass<S extends SuperClass<S>> {
    S subclassInstance();
}

interface AnotherType {
    void print();
}

The next step is to implement the previous interfaces. Something like this:

/**
 * subclass A
 */
static
class SubClassA implements
        SuperClass<SubClassA>,
        AnotherType
{
    private final String name;
    SubClassA(){
        final Random random = new Random(19580427);
        name = getClass().getName()
                + random.nextInt();
    }
    public SubClassA subclassInstance(){
    	return this;
	}
    public void print(){
    	System.out.println(name);
	}
}

/**
 * subclass B
 */
static class SubClassB implements SuperClass<SubClassB>,
        AnotherType
{
    private final String name;
    SubClassB(){
        final Random random = new Random(19580427);
        name = getClass().getName()
                + random.nextInt();
    }
    public SubClassB subclassInstance(){
    	return this;
	}
    public void print(){
    	System.out.println(name);
	}
}

Then I can write code like this one and totally avoid dowcasting between objects:

public static void main(String... args){
 final SubClassA      		 sca  = new SubClassA();
 final SuperClass<SubClassA> sc   = sca;
 final SubClassA      sca2    = sca.subclassInstance();
 final SubClassA      sca3    = sc.subclassInstance();

 // no casting..cool huh!
 sca2.print();
 sca3.print();
}

And there you go… I’ve totally solved my downcasting problem!