GHads mind

developers thoughts & finds

Filter Collections via “Double Brace Initialization”

with 3 comments

Hi again,

here’s another little code I did recently while trying to answer a Stackoverflow-Question.

The author of the question (here) asks for a smarter way to filter collections/lists in Java like it is done in Python/Scala/Groovy, as one-liner.

I immediatly thought of JDK7 closures, but as it is widly known Oracle shifted the featurelists for JDK7 and 8 not long ago and it seems, closures will come not earlier than 2012. But even with closures the accepted answers shows that in its current state event closures would be an akward and over-complicated solution compared to groovy for example (quoted from the seanizers answer):

JDK7 sample code:

findItemsLargerThan(List l, int what){
  return filter(boolean(Integer x) { x > what }, l);
}
findItemsLargerThan(Arrays.asList(1,2,5,6,9), 5)

Groovy sample code:

  Arrays.asList(1,2,5,6,9).findAll{it > 5}

You see…

So I started to experiment with pure Java to find a solution that is easy to read and easy to program while not beein too verbose. After some hours I came up with the following code

List<Integer> filtered = new Filter<Integer>(Arrays.asList(1,2,5,6,9)) {
  {
    findAll(it > 5);
  }
};

I thinks it’s quite elegant, because it’s readable pure Java code and fits one line sans code-formating. How does it work? Obvisually one needs a class Filter. The abstract Filter class implements the List interface (delegates all methods to an internal List variable) and takes the collection to filter (assigned to the internal List variable) as argument for its constructor and throws a RuntimeException when the collection is null or empty. Then we have the double brace initialization pattern which allows to dynamicly and anonymously subclass the filter class while providing an instance initalizer which will be executed after the constructor of the Filter class is done. Inside the instance initializer all we do now is a method call to findAll(), which takesa boolean argument. But where does “it” come from and how will “it” be mapped to each element of the collection?

“it” is a variable inside the Filter class. As the instance initializer is executed after the constructor, we can set “it” to the first element of the collection to filter. The instance initializer is then executed and the boolean condition it > 5 is evaluated. So at the time findAll() is executed, the condition whether to include the first element in the filtered result is already done. So the magic to repeat the evaluation for each element must be inside the findAll() method:

protected void findAll(boolean b) {
  // exit condition for future calls
  if (values.size() > 1) {
    // only repeat for each entry, if values has multiple entries
    Constructor constructor = this.getClass()
       .getDeclaredConstructors()[0];
    Iterator iterator = values.iterator();
    boolean first = true;
    while (iterator.hasNext()) {
      T element = iterator.next();
      // don't evalute again for the first entry
      if (first) {
        if (!b) {
          iterator.remove();
        }
        first = false;
      } else {
        // else repeat Filter invocation for all elements
        Filter filtered = null;
        try {
          // invoked constructor for the element
          filtered = (Filter) constructor.newInstance(
            new Object[] { null, Arrays.asList(element) });
        } catch (Exception e) {
          e.printStackTrace();
        }
        // if values is empty, the condition didn't match and the
        // element can be removed
        if (filtered != null && filtered.isEmpty()) {
          iterator.remove();
        }
      }
    }
  } else {
    // one element can be checked directly
    if (!b) {
      values.clear();
    }
  }
}

(a little bit more polished than my answer at Stackoverflow)

First thing is to define an exit condition as the findAll() method will be executed multiple times eventually. The condition says, if there is more than one element in the list, we must iterate, else we can look at the evaluted boolean condition directly. In the last case “false” will just clear the internal List, whereas “true” does not change it.

When iteration is needed we get the constructor of this class once (there is only one) and take the next element. If it is the first one, we already know the evaluated condition and thus remove or keep the first item. For all other items we will create a new instance of the anonymous class that extended Filter via instance initalizer in the first place. By creating a new instance and providing a list as argument with a single element, the instance initializer is called again after the constructer set “it”. So the evaluation of the boolean condition starts again, but for the next element this time. After instance creation it’s a simple check whether the boolean condition had matched or not. If the internal List is empty, the condition was “false” and the element can be removed from the Filter instance that iterates the elements and creates new instances.

So the only catch is that there are n-1 additional instances created for a collection n to filter, when n is the number of elements. But as Instance creation is quite cheap these days and every additional instance does not need to iterate again, this runs quite fast. I’m sure there is still potential to optimize the Filter class as new ArrayLists are created here and there but im very satisfied with the result so far.

The filter class can be used for each kind of object, for example checking if people are 18 would be “findAll(it.getAge() >= 18);”, if there is a People Class with a getAge() method.

So long this time, hope you enjoyed this blogpost (feedback is appriciated).
Greetz,
GHad

Advertisements

Written by ghads

September 22, 2010 at 3:49 pm

3 Responses

Subscribe to comments with RSS.

  1. awesome, but geez, that’s a lot of work. anonymous class extending filter would be much easier no?

    davem

    August 24, 2012 at 3:44 am

    • yeah sure, this was just for testing the rough edges of Java and for fun, never used this in production 🙂

      ghads

      August 24, 2012 at 8:50 am

      • 😉

        davem

        August 24, 2012 at 12:09 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: