The Filter Pattern: Java Conditional Abstraction With Iterables

January 18, 2008 By: erik Category: Geeky 23,387 views

Rate this post:
1 Star2 Stars3 Stars4 Stars5 Stars (11 votes, average: 4.64 out of 5)
Loading...

shiny 2As 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?

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.

 
  • Ooh, today I got “balls”…interesting. I can truthfully say I’ve never written any code that looks anything like that. The closest I’ve gotten to writing code of any sort has been mucking around in my blogger template (that and learning to write stuff in BASIC back in high school). But I’m glad you got whatever it is fixed…I guess…you did fix it, right? Okay, I don’t have a clue. 🙂

  • Masklinn

    You probably want to check Google Collections (http://code.google.com/p/google-collections/) instead of reimplementing what they’ve already done.

  • Thanks for that link, Masklinn. It’s good to see solid generics code coming from Google. The java apis (e.g. Google Checkout) I’ve worked with to communicate with Google have been disgusting.

  • Heather

    I didn’t know it was possible to feel intelligent and mind blowingly dumb at the same time………

  • Erik,

    I attempted to compile your Filter class with JRE 6.0_07 but I got an error here:
    public Iterable filter(Iterable iterable) {
    return new Iterable() {
    public Iterator iterator() {
    //** next line: “cannot refer to a non-final variable iterator inside an inner class defined in a different method.
    return filter(iterable.iterator());
    }
    };
    }

    Have you seen this error?
    Thanks, Phil Young, Xerox Corp.

  • No, Phil, I had not seen that. But I’m not sure I actually compiled this code either. It’s meant as an example only. You probably just need to make the parameter “final”, like the compiler says. Maybe I left that out for formatting (so it wouldn’t wrap) reasons. I can’t remember.

    The concept is still sound. I use it every day.

  • Erik, making the parameter final got past the compilation error. The Filter is a very useful concept. Thanks, Phil

  • Should I be the only one to bring up the elephant in the room? The code at the top we’re trying to get rid of is smaller, faster, less error prone, easier to test, more easily readable…I could go on. Why would you want to implement the filter pattern except as a programming exercise?

  • HG, I guess the two main reasons would be clarity and code reuse. But I suppose one man’s clarity is another man’s obfuscation.

  • Rx

    Thanks Erik – the Filter is a very clever and indeed a VERY powerful pattern. Used it to construct complex filters (composite AND/OR, inverters) on different business objects – very handy and powerful especially with code flexibility and reusability in mind.

    to Hardwareguy: you really think so? Well, THAT is why youre the HARDWARE guy.

  • Abhijeet

    Thanks for the informative post.

    But I can’t get the base class of your code to compile.
    Your abstract base class Filter contains a private class, the FilterIterator. This FilterIterator has a toNext method, which internally calls the abstract method passes. This is where my code fails to compile.
    “The method passes(T) in the type Filter is not applicable for the arguments (T)”
    Is it even valid for an abstract method to be invoked this way?
    Or have I got my generics all wrong?

    • Yes, that call is valid. The code I have here does compile, after fixing the one error that Phil pointed out above: The iterable parameter on line 11 must be marked final.

      Once I fixed that, I just compiled the class fine.

  • Yeaaah !, great job, thanks for sharing.

    I change your class to filter a tree…
    Not so easy but your work help me a lot, thanks again.

  • Subhasish

    Excellent Code… I like it !

  • x

    I agree with Hardware guy. You didn’t motivate this properly, Erik.

    Replacing

    if (meetsSomeCriteria(thing))

    with

    someCriteria.meets(thing)

    does not help.

    Passing functions around – fine, if that’s what you need. But your presentation here is completely misleading.

  • Arora Hitesh

    Beautiful code.