The Filter Pattern: Java Conditional Abstraction With Iterables

January 18, 2008

As a java programmer, I find myself very often wanting to perform a particular operation on only certain items in a collection. How many times have you written code that looks like this? code span.keyword { font-weight:bold; color: #000080; } code span.member { font-weight:bold; color: #660e7a; } code span.annotation { color: #808000; } code span.static { font-style:italic; font-weight:bold; color: #660e7a; } code span.comment { font-style:italic; color: #cccccc; } Collection<Thing> things = getThingsFromSomewhere(); for(Thing thing : things) { if(meetsSomeCriteria(thing)) { // do stuff } }

Code like this is just a natural part of many programming problems and a pattern that pops up quite often. A good programmer will notice when the same code gets repeated over and over again and, language permitting, abstract the logic away. Since Java 1.5, there has been a way to do just that by mimicking first-class functions with the java.lang.Iterable interface and what I will call the "Filter Pattern".

The Base Class

Let's define the Filter base class:

import java.util.Iterator; import java.util.NoSuchElementException; public abstract class Filter<T> { public abstract boolean passes(T object); public Iterator<T> filter(Iterator<T> iterator) { return new FilterIterator(iterator); } public Iterable<T> filter(Iterable<T> iterable) { return new Iterable<T>() { public Iterator<T> iterator() { return filter(iterable.iterator()); } }; } private class FilterIterator implements Iterator<T> { private Iterator<T> iterator; private T next; private FilterIterator(Iterator<T> iterator) { this.iterator = iterator; toNext(); } public boolean hasNext() { return next != null; } public T next() { if (next == null) throw new NoSuchElementException(); T returnValue = next; toNext(); return returnValue; } public void remove() { throw new UnsupportedOperationException(); } private void toNext() { next = null; while (iterator.hasNext()) { T item = iterator.next(); if (item != null && passes(item)) { next = item; break; } } } } }

A Simple Example

Okay, so what does this give us? At its core, it's just a way to ask a yes/no question about an object and get back a boolean result. So let's define a few. In practice, many filters end up being static final anonymous singletons.

public static final Filter<Product> IN_STOCK = new Filter<Product>() { public boolean passes(Product product) { return product.getQuantityInStock() > 0; } };

So now, let's say that we have a collection of products, but that we only want to display the ones that are in stock. We could do this:

Collection<Product> allProducts = getAllProducts(); for(Iterator<Product> iterator = IN_STOCK.filter(allProducts.iterator()); iterator.hasNext(); ) { Product product = iterator.next(); display(product); }

Note that this will only go through the collection of products once, checking each product to see if it is in stock, and displaying only the products that are in stock. But wait! Because Filter provides a way to get an Iterable, we can use Java 1.5's for-each structure like so:

Collection<Product> allProducts = getAllProducts(); for(Product product : IN_STOCK.filter(allProducts)) { display(product); }

Beautiful, isn't it? But our IN_STOCK example only begins to scratch the surface of the power of the Filter Pattern.

Comparable Filters

What if we want to filter some objects by their relationship to another object? We simply keep that object inside our filter and compare each of the objects as we iterate through the collection. It can even be done generically, like so:

public abstract class ComparableFilter<T extends Comparable<T>> extends Filter<T> { private final T comparable; protected ComparableFilter(T comparable) { this.comparable = comparable; } @Override public boolean passes(T object) { return passes(object.compareTo(comparable)); } protected abstract boolean passes(int result); }

We could make a concrete LessThanFilter class that extends ComparableFilter, but if we make it anonymous, inside a static function on ComparableFilter, we'll get type inference that we would not get otherwise.

public static <T extends Comparable<T>> Filter<T> lessThan(T comparable) { return new ComparableFilter<T>(comparable) { @Override protected boolean passes(int result) { return result < 0; } }; }

Now we can iterate through a collection of objects and only perform the body of the for loop when the object is less than a given value. For instance:

Collection<Integer> values = getValues(); for(Integer value : ComparableFilter.lessThan(5).filter(values)) { // do stuff }

Compound Filters

This is where filters get even more powerful. With compound filters, we can continue to combine other filters together to any arbitrary amount of complexity.

public class AndFilter<T> extends Filter<T> { private final Filter<T>[] filters; public AndFilter(final Filter<T>... filters) { this.filters = filters; } @Override public boolean passes(T object) { for (Filter<T> filter : filters) { if (!filter.passes(object)) return false; // short circuit } return true; } }

So what if we wanted to iterate through only the numbers that were "either even and below 50 or odd and above 100"? Easy:

Collection<Integer> values = getValues(); Filter<Integer> filter = new OrFilter( new AndFilter( EvenFilter.INSTANCE, ComparableFilter.lessThan(50)), new AndFilter( OddFilter.INSTANCE, ComparableFilter.greaterThan(100))); for(Integer value : filter.filter(values)) { // do stuff }

I will leave the implementations of EvenFilter, OddFilter (note that they could both extend a more generic ModFilter), OrFilter, and ComparableFilter.greaterThan() as exercises for the reader.

Obviously it wouldn't make sense to define a complex filter right before your loop, use it once, and throw it to the garbage collector. The real benefit of filters comes from storing them to be used many times or passing them around, effectively making them into first-class functions.

Filters as First-Class Functions

Imagine that we have a mailbox full of messages and we want to be able to mark messages as "sent" or "flagged" or "spam".

public class Mailbox { private List<Message> messages; ... public void markAs(Status status, Filter<Message> filter) { for(Message message : filter.filter(messages)) message.markAs(status); } }

Notice what we've gained by this design:

The method doing the iteration does not know which messages are being affected.
The internal collection is not exposed.
We've created a facade that allows us to change the internal structure of how the messages are stored without changing any code outside the Mailbox class

The filter that we pass into markAs() could be filtering by the selected messages in the UI, messages older than 5 days, ...anything!

Conclusion

The Filter Pattern is a great example of how learning a functional programming language can make you a better programmer, even if you don't program in one. The next time you find yourself writing a for loop that contains one big if block, consider how you could abstract that logic out and make your method more generic and more reusable.