Salmon Run: April 2009

Monday, April 20, 2009

XPath over HTML using Jericho and Jaxen

I've been using Jericho to parse HTML for a while now. I mainly use it to extract pieces of text from specific locations in the HTML. To do this, I use the Jericho API - I have factored out the boilerplate code associated with XML/HTML parsing into utility classes, so the application code to extract an element's contents would be 1 or 2 lines tops. However, recently I needed to move the extraction logic out of the code and into configuration.

Using XPath in these situations is almost a no-brainer - given an XML document and tasked with extracting text for known elements, that is the first tool I would think about. Unfortunately, Jericho does not have XPath support, so being the foolish/foolhardy type, I set about trying to build one. This post describes a Jaxen based XPath adapter for Jericho.

The Jaxen project provides a universal XPath engine, capable of evaluating XPath expressions across multiple object models - currently supported in the GA (1.1.1 at the time of writing this) release are dom4j, JDOM, w3c DOM, Javabeans and XOM. The Jaxen FAQ has this to say about extending Jaxen for other object models.

The only thing required is an implementation of the interface org.jaxen.Navigator. Not all of the interface is required, and a default implementation, in the form of org.jaxen.DefaultNavigator is also provided. Since many of the XPath axes can be defined in terms of each other (for example, the ancestor axis is merely a the parent recursively applied), only a few low-level axis iterators are required to initially get started. Of course, you may implement them directly, instead of relying upon jaxen's composition ability.

In my opinion, the text above falls into the technically accurate but not very useful as a guideline category. Granted, there are multiple extension examples in the source tarball (for dom4j, JDOM, etc) to use as examples (which I did), but what would have helped immensely is a short howto style tutorial, that explains which methods of DefaultNavigator need to be customized and why.

I was finally able to get everything to work by running my unit test through a debugger, stepping through both the Jaxen and my extension code. For example, I found that I should implementing the methods of NamedAccessNavigator, although that is not a stated requirement. There are also places where the methods of DefaultNavigator return null or throw UnsupportedOperationException and are therefore expected to be extended by subclasses, but without being explicitly marked abstract.

In any case, I now know a little more than I knew about Jaxen internals, and I must say the extension model is very well thought out, and my gripe with the implementation may just be due to the fact that the authors haven't gotten around to cleaning it up so its more usable. Hopefully, if you are in a similar situation as I was recently, then the code in this blog post may be helpful - in the form of yet another example of extension.

My approach is based on the first paragraph of the guideline, ie, building a custom Navigator implementation using the JDOM implementation as a template. Basically, I have a JerichoXPath class which exposes two constructors and a custom getContext() method, and a DocumentNavigator implementation that contains calls to the Jericho API to do different things. The Jaxen XPath parser calls into these DocumentNavigator methods at specific points in its life cycle.

JerichoXPath

package org.jaxen.jericho;

import java.util.List;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.jaxen.BaseXPath;
import org.jaxen.Context;
import org.jaxen.JaxenException;
import org.jaxen.Navigator;
import org.jaxen.util.SingletonList;

import au.id.jericho.lib.html.Element;
import au.id.jericho.lib.html.Source;

public class JerichoXPath extends BaseXPath {

  private static final long serialVersionUID = -6969112785840871593L;

  private final Log log = LogFactory.getLog(getClass());
  
  public JerichoXPath(String xpathExpr, Navigator navigator) 
      throws JaxenException {
    super(xpathExpr, navigator);
  }
  
  public JerichoXPath(String xpathExpr) throws JaxenException {
    super(xpathExpr, DocumentNavigator.getInstance());
  }

  /**
   * Jericho specific method to get the context associated with a node.
   * @param node the current node being visited.
   * @return the Context associated with the node.
   */
  protected Context getContext(Object node) {
    if (node instanceof Context) {
      return (Context) node;
    }
    Context fullContext = new Context(getContextSupport());
    if (node instanceof Source) {
      Element rootNode = 
        (Element) getNavigator().getDocumentNode((Source) node);
      fullContext.setNodeSet(new SingletonList(rootNode));
    } else if (node instanceof List) {
      fullContext.setNodeSet((List) node);
    } else {
      List list = new SingletonList(node);
      fullContext.setNodeSet(list);
    }
    return fullContext;
  }
}

DocumentNavigator

package org.jaxen.jericho;

import java.io.IOException;
import java.net.MalformedURLException;
import java.net.URL;
import java.net.URLConnection;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.jaxen.DefaultNavigator;
import org.jaxen.JaxenConstants;
import org.jaxen.NamedAccessNavigator;
import org.jaxen.Navigator;
import org.jaxen.UnsupportedAxisException;
import org.jaxen.XPath;
import org.jaxen.saxpath.SAXPathException;
import org.jaxen.util.SingleObjectIterator;

import au.id.jericho.lib.html.Attribute;
import au.id.jericho.lib.html.Attributes;
import au.id.jericho.lib.html.CharacterReference;
import au.id.jericho.lib.html.Element;
import au.id.jericho.lib.html.Segment;
import au.id.jericho.lib.html.Source;
import au.id.jericho.lib.html.StartTagType;

public class DocumentNavigator extends DefaultNavigator 
    implements NamedAccessNavigator {

  private static final long serialVersionUID = 8640276699026512314L;

  private final Log log = LogFactory.getLog(getClass());
  
  // DocumentNavigator needs to expose a singleton. Strategy adapted from: 
  // http://www.ibm.com/developerworks/java/library/j-dcl.html

  private DocumentNavigator() {
    super();
  }
  private static DocumentNavigator INSTANCE = new DocumentNavigator(); 
  
  /**
   * Return a singleton instance of the DocumentNavigator object.
   * @return a Navigator.
   */
  public static Navigator getInstance() {
    return INSTANCE;
  }
  
  // various abstract isXXX method implementations. These are specified
  // in the Navigator interface but not defined in the abstract class,
  // so they must be implemented in the implementation specific subclass.

  /**
   * Returns true if the node is an Attribute.
   * @param obj the node to consider.
   * @return true if node is an attribute, else false.
   */
  public boolean isAttribute(Object obj) {
    return obj instanceof Attribute;
  }

  /**
   * Returns true if the node is a Comment.
   * @param obj the node to consider.
   * @return true if the node is a comment, else false.
   */
  public boolean isComment(Object obj) {
    if (obj instanceof Element) {
      Element element = (Element) obj;
      return isElementOfType(element, StartTagType.COMMENT);
    }
    return false;
  }

  /**
   * Returns true if the node is a Document.
   * @param obj the node to consider.
   * @return true if the node is a Document, else false.
   */
  public boolean isDocument(Object obj) {
    return (obj instanceof Source);
  }

  /**
   * Returns true if the node is an Element.
   * @param obj the node to consider.
   * @return true if the node is an Element, else false.
   */
  public boolean isElement(Object obj) {
    if (obj instanceof Element) {
      Element element = (Element) obj;
      return isElementOfType(element, StartTagType.NORMAL);
    }
    return false;
  }

  /**
   * Returns true if the node is a Namespace. Since Jericho HTML
   * does not work with Namespaces, this method always returns false.
   * @parm obj the node to consider.
   * @return always false.
   */
  public boolean isNamespace(Object obj) {
    return false;
  }

  /**
   * Returns true if the node is a Processing Instruction.
   * @param the node to consider.
   * @return true if the node is a PI, else false.
   */
  public boolean isProcessingInstruction(Object obj) {
    if (obj instanceof Element) {
      Element element = (Element) obj;
      return isElementOfType(element,
        StartTagType.XML_PROCESSING_INSTRUCTION) || 
        isElementOfType(element, StartTagType.XML_DECLARATION);
    }
    return false;
  }

  /**
   * Returns true if the node is Text.
   * @param obj the node to consider.
   * @return true if the node is text, else false.
   */
  public boolean isText(Object obj) {
    if (obj instanceof CharacterReference || obj instanceof String) {
      return true;
    }
    return false;
  }

  // various abstract getXXX method implementations. These are specified
  // in the Navigator interface but not defined in the abstract class,
  // so they must be implemented in the implementation specific subclass.
  
  /**
   * Return the name of the attribute.
   * @param obj the Attribute object.
   * @return the attribute name.
   */
  public String getAttributeName(Object obj) {
    if (obj instanceof Attribute) {
      Attribute attr = (Attribute) obj;
      return attr.getName();
    } else {
      return "";
    }
  }

  /**
   * Return the name of the attribute's namespace URI. Since there
   * are no Namespaces in Jericho, this returns an empty string.
   * @param obj the Attribute object.
   * @return an empty string.
   */
  public String getAttributeNamespaceUri(Object obj) {
    return "";
  }

  /**
   * Return the attribute's QName. Since there are no Namespaces in
   * Jericho, this is the same as returning the Attribute name.
   * @param obj the Attribute object.
   * @return the attribute name.
   */
  public String getAttributeQName(Object obj) {
    return getAttributeName(obj);
  }

  /**
   * Return the value of the attribute.
   * @param obj the attribute.
   * @return the attribute value as a string.
   */
  public String getAttributeStringValue(Object obj) {
    if (obj instanceof Attribute) {
      Attribute attr = (Attribute) obj;
      return attr.getValue();
    } else {
      return "";
    }
  }

  /**
   * Returns the comment as a string.
   * @param obj the comment element.
   * @return the comment's string value.
   */
  public String getCommentStringValue(Object obj) {
    if (isComment(obj)) {
      Element element = (Element) obj;
      return element.getContent().getTextExtractor().toString();
    } else {
      return "";
    }
  }

  /**
   * Returns the name of the Element.
   * @param obj the Element.
   * @return the name of the element.
   */
  public String getElementName(Object obj) {
    if (obj instanceof Element) {
      Element element = (Element) obj;
      return element.getName();
    } else {
      return "";
    }
  }

  /**
   * Returns the namespace URI for the Element. Since Namespaces are
   * not supported in Jericho, this returns an empty string.
   * @param obj the Element.
   * @return an empty string.
   */
  public String getElementNamespaceUri(Object obj) {
    return "";
  }

  /**
   * Returns the Element's QName. Since Namespaces are not supported
   * in Jericho, this is the same as getElementName().
   * @param obj the Element.
   * @return the Element name.
   */
  public String getElementQName(Object obj) {
    return getElementName(obj);
  }

  /**
   * Returns the text content of the Element.
   * @param obj the Element.
   * @return the text content or String value of the Element.
   */
  public String getElementStringValue(Object obj) {
    if (obj instanceof Element) {
      Element element = (Element) obj;
      return element.getContent().getTextExtractor().toString();
    } else if (obj instanceof String) {
      return ((String) obj);
    } else {
      return String.valueOf(obj);
    }
  }

  /**
   * Get the Namespace prefix for the Document. Always returns an
   * empty string since Jericho does not support Namespaces.
   * @param obj the Document.
   * @return an empty string.
   */
  public String getNamespacePrefix(Object obj) {
    return "";
  }

  /**
   * Returns the namespace string value for the Element. Same as
   * returning the element's string value.
   * @param obj the Element.
   * @return the name of the element.
   */
  public String getNamespaceStringValue(Object obj) {
    return getElementStringValue(obj);
  }

  /**
   * Return the text string value for the Element. Same as returning
   * the element's string value.
   * @param obj the Element.
   * @return the text content of the Element.
   */
  public String getTextStringValue(Object obj) {
    return getElementStringValue(obj);
  }

  // various overrides of incorrect or inefficient default behavior in 
  // parent class. Default behavior is usually returning null or throwing 
  // an UnsupportedOperationException, so we override to provide correct
  // behavior. 

  /**
   * Returns a Document object given a URL. We return a Source object,
   * and automatically do a fullSequentialParse() for performance.
   * @param url the URL for the document.
   * @return the Source object.
   */
  public Object getDocument(String url) {
    try {
      URLConnection conn = new URL(url).openConnection();
      Source source = new Source(conn.getInputStream());
      source.fullSequentialParse();
      return source;
    } catch (MalformedURLException e) {
      log.error("Malformed URL: " + url, e);
      return null;
    } catch (IOException e) {
      log.error("IO Exception for URL: " + url, e);
      return null;
    }
  }

  /**
   * Returns the root element for the Document context node.
   * @param contextNode the Source object.
   * @return the root Element of the document (html).
   */
  public Object getDocumentNode(Object contextNode) {
    if (contextNode instanceof Source) {
      Source source = (Source) contextNode;
      return ((Segment) source).findAllElements("html").get(0);
    } else {
      return contextNode;
    }
  }

  /**
   * Returns the parent node for the contextNode. Default behavior is
   * inefficient. Since a Jericho Element has a pointer to its parent
   * node, we can use that here.
   * @param contextNode the context node.
   * @return the parent node.
   */
  public Object getParentNode(Object contextNode) {
    if (isElement(contextNode)) {
      return ((Element) contextNode).getParentElement();
    } else {
      return null;
    }
  }

  /**
   * Returns an element by id. Default behavior always returns null,
   * but Jericho provides methods to return this object, so we override
   * it.
   * @param contextNode the context node.
   * @param elementId the name of the element being searched for.
   * @return an Element object.
   */
  public Object getElementById(Object contextNode, String elementId) {
    if (isElement(contextNode)) {
      Iterator eit = ((Element) contextNode).findAllElements().iterator();
      List elementsById = new ArrayList();
      while (eit.hasNext()) {
        Element element = (Element) eit.next();
        if (element.getAttributeValue("id") == null ||
            (! element.getAttributeValue("id").equals(elementId))) {
          continue;
        }
        elementsById.add(element);
      }
      return elementsById;
    } else {
      return Collections.emptyList();
    }
  }
  
  // iteration methods

  /**
   * Returns an iterator for the child Elements of the contextNode
   * Element.
   * @param contextNode the context node Element.
   * @return an Iterator over the child objects of this Element.
   */
  public Iterator getChildAxisIterator(Object contextNode) {
    if (isElement(contextNode)) {
      Element element = (Element) contextNode;
      List children = new ArrayList();
      children.addAll(element.getChildElements());
      children.add(element.getTextExtractor().toString());
      return children.iterator();
    } else {
      return JaxenConstants.EMPTY_ITERATOR;
    }
  }

  /**
   * Returns an iterator over the named child elements of this context
   * node. Comes from NamedAccessNavigator.
   * @param contextNode the context node Element.
   * @param localName the name of the element.
   * @param namespacePrefix not used.
   * @param namespaceURI not used.
   * @return an iterator over the named child elements.
   */
  public Iterator getChildAxisIterator(Object contextNode, String localName,
      String namespacePrefix, String namespaceURI)
      throws UnsupportedAxisException {
    if (contextNode instanceof Element) {
      List children = ((Element) contextNode).findAllElements(localName);
      return children.iterator();
    } else {
      return JaxenConstants.EMPTY_ITERATOR;
    }
  }

  /**
   * Jericho does not support Namespaces, so returns an empty iterator.
   * @param contextNode the context node Element.
   * @return an empty iterator.
   */
  public Iterator getNamespaceAxisIterator(Object contextNode) {
    return JaxenConstants.EMPTY_ITERATOR;
  }

  /**
   * Returns an iterator over the parent elements of this Context node.
   * @param contextNode the context node Element.
   * @return an iterator over the parent elements of this Element.
   */
  public Iterator getParentAxisIterator(Object contextNode) {
    if (isDocument(contextNode)) {
      return JaxenConstants.EMPTY_ITERATOR;
    }
    Element parent = null;
    if (isElement(contextNode)) {
      Element element = (Element) contextNode;
      parent = element.getParentElement();
    }
    if (parent == null) {
      return JaxenConstants.EMPTY_ITERATOR;
    } else {
      return new SingleObjectIterator(parent);
    }
  }
  
  /**
   * Returns an iterator over the attribute axis of this context node.
   * @param contextNode the context node Element.
   * @return an iterator over the Element's attributes.
   */
  public Iterator getAttributeAxisIterator(Object contextNode) {
    if (isElement(contextNode)) {
      Element element = (Element) contextNode;
      Attributes attrs = element.getAttributes();
      Iterator ait = attrs.iterator();
      List attrlist = new ArrayList();
      while (ait.hasNext()) {
        attrlist.add((Attribute) ait.next());
      }
      return attrlist.iterator();
    }
    return JaxenConstants.EMPTY_ITERATOR;
  }

  /**
   * Returns an iterator over the named attributes for this context node.
   * Comes from NamedAccessNavigator.
   * @param contextNode the context node Element.
   * @param localName the name of the attribute.
   * @param namespacePrefix not used.
   * @param namespaceURI not used.
   * @return an iterator over the named attributes of this Element.
   */
  public Iterator getAttributeAxisIterator(Object contextNode,
      String localName, String namespacePrefix, String namespaceURI)
      throws UnsupportedAxisException {
    List namedAttrs = new ArrayList();
    if (contextNode instanceof Element) {
      Attributes attrs = ((Element) contextNode).getAttributes();
      Iterator ait = attrs.iterator();
      while (ait.hasNext()) {
        Attribute attr = (Attribute) ait.next();
        if (localName.equals(attr.getName())) {
          namedAttrs.add(attr);
        }
      }
      return namedAttrs.iterator();
    } else {
      return JaxenConstants.EMPTY_ITERATOR;
    }
  }

  /**
   * Makes sure that we return the correct XPath implementation when
   * called.
   * @param xpath the XPath expression.
   * @return the JerichoXPath object wrapping the expression.
   */
  public XPath parseXPath(String xpath) throws SAXPathException {
    return new JerichoXPath(xpath);
  }

  /**
   * Convenience method to return a correct element type.
   * @param element the Element object.
   * @param tagType the correct tag type. 
   * @return true or false.
   */
  private boolean isElementOfType(Element element, StartTagType tagType) {
    if (element == null) {
      return false;
    }
    return element.getStartTag().getTagType().equals(tagType);
  }
}

Unit test

The Unit test is a JUnit 3.x test, and just takes an HTML document and hits it with the XPath expressions I am likely to use. Its nothing fancy, just a runner for the evaluate() method for various XPath expressions. It prints its output on the console.

package org.jaxen.test;

import java.util.List;

import junit.framework.TestCase;

import org.jaxen.Navigator;
import org.jaxen.XPath;
import org.jaxen.jericho.DocumentNavigator;
import org.jaxen.jericho.JerichoXPath;

import au.id.jericho.lib.html.Element;
import au.id.jericho.lib.html.Source;

public class JerichoNavigatorTest extends TestCase {

  private String testUrl = "http://path.to.your/document.html";
  private String[] xpaths = new String[] {
    "/html/body",
    "//body",
    "/html/body/../head",
    "/html/head/title/text()",
    "//div[@class='articlecontent']",
    "//div[@class]"
  };

  public void testParsingVisitor() throws Exception {
    Navigator navigator = DocumentNavigator.getInstance();
    Source doc = (Source) navigator.getDocument(testUrl);
    for (int i = 0; i < xpaths.length; i++) {
      String xpath = xpaths[i];
      System.out.println("*** Evaluating: " + xpath);
      XPath expr = new JerichoXPath(xpath, navigator);
      Object result = expr.evaluate(doc);
      if (result instanceof Element) {
        System.out.println("Element: " + ((Element) result).getName());
      } else if (result instanceof List) {
        System.out.println("List: size=" + ((List) result).size());
        List elements = (List) result;
        for (int j = 0; j < elements.size(); j++) {
          Element element = (Element) elements.get(j);
          System.out.println("Element: " + ((Element) element).getName());
        }
      } else if (result instanceof String) {
        System.out.println("String: " + ((String) result));
      } else if (result instanceof Number) {
        System.out.println("Number: " + ((Number) result));
      } else if (result instanceof Boolean) {
        System.out.println("Boolean: " + ((Boolean) result));
      } else {
        System.out.println("Unknown: " + result == null ? 
          "NULL" : result.getClass().getName());
      }
    }
  }
}

Other XPath methods

I haven't gotten around to testing the other public methods of the XPath object, but I suspect that Jaxen will do the right thing in all these cases, because all of the methods can be written as wrappers over the evaluate() method. If I see problems with the behavior, the plan is to override these methods in the JerichoXPath class, as shown below:

  public String valueOf(Object context) throws JaxenException {
    return stringValueOf(context);
  }

  public boolean booleanValueOf(Object context) throws JaxenException {
    String result = stringValueOf(context);
    return Boolean.valueOf(result);
  }

  public Number numberValueOf(Object context) throws JaxenException {
    String result = stringValueOf(context);
    if (NumberUtils.isNumber(result)) {
      return NumberUtils.createNumber(result);
    } else {
      throw new JaxenException("Value of " + xpathExpr + " is not numeric");
    }
  }

  public String stringValueOf(Object context) throws JaxenException {
    Object result = evaluate(context);
    if (result instanceof String) {
      return (String) result;
    } else {
      throw new JaxenException("Cannot return string value of " + xpathExpr);
    }
  }

  public Object selectSingleNode(Object context) throws JaxenException {
    List nodes = selectNodes(context);
    if (nodes.size() > 0) {
      return nodes.get(0);
    } else {
      return null;
    }
  }

  public List selectNodes(Object context) throws JaxenException {
    Object result = evaluate(context);
    if (result instanceof List) {
      return ((List) result);
    } else {
      return Collections.emptyList();
    }
  }

Alternative Approach

As outlined in the second paragraph of the guidelines, another approach is to build a Jericho implementation of the XPathHandler interface, and parse the XPath expression using the default XPathReader. I tried this in desperation midway through the above exercise, and it worked well for the simple element traversal events. However, I decided against going this route because of the complexity of the event handling code for handling predicates. However, if you are looking to build something that does not (or cannot for some reason) use the Jaxon Navigator approach, then this may be worth looking at.

XPath/Jaxen articles

There is not much information available on Jaxen and SAXPath Event API, but I found these two links quite useful.

Introduction to SAXPath and Jaxen by Bob McWhirter
Chapter 16 of Processing XML with Java by Elliote Rusty Harold

Update 2009-04-26: I contributed the code above back to the Jaxen project. However, they are planning on moving the examples out of the project since it imposes unnecessary JAR file dependencies on clients, so the code may become part of a jaxen-contrib project later. If you are looking to incorporate the code into your project, the only extra dependency are jericho-html. There is some commons-logging dependencies, but they can be removed or replaced with your favorite logger in the source code.

Friday, April 10, 2009

Maven2 plugin to generate shell scripts

Here is a silly, but potentially useful little Maven2 plugin that I wrote recently. It uses the application module's POM to build a bash script that runs a Java "executable" program (ie a class with a main() method).

For a given module, a bash script to run one class versus another is almost identical - the only difference is in the class name being passed to java. The rest of it is all boilerplate, and the largest portion is the CLASSPATH declaration. Since Java modules typically have tons of dependencies, it can be quite tedious to build the bash script by hand - in fact, it would probably qualify as my least favorite (coding) activity.

Why do it then, you ask? Well, I typically run small datasets (upto a couple 1000) through my program by writing a JUnit test and calling it using "mvn test", but I find that the JVM runs out of memory for large data sets, especially with a lot of logging. I suspect that this is because Maven2 buffers the logs in memory to write the results of the test in an XML file, but I could be wrong. The other reason is that if your program is going to production, then a shell script to run the code is one of the deliverables.

Plugin setup

The plugin is built inside an existing plugin project that I described in a previous post. For this plugin, I added in dependencies to JDOM and Velocity. The relevant snippet from my pom.xml is shown below:

<project>
  ...
  <dependencies>
  ...
    <dependency>
  ...
    <dependency>
      <groupId>velocity</groupId>
      <artifactId>velocity</artifactId>
      <version>1.4</version>
      <scope>compile</scope>
    </dependency>
    <dependency>
      <groupId>jdom</groupId>
      <artifactId>jdom</artifactId>
      <version>1.0</version>
      <scope>compile</scope>
    </dependency>
  </dependencies>
  ...
</project>

Plugin code

Here is the code for the plugin. It is set to be called in the "deploy" phase, so it does not interfere with the normal development (clean compile test-compile test) life cycle.

// Source: src/main/java/com/mycompany/plugin/BashScriptMojo.java
package com.mycompany.plugin;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.util.Date;
import java.util.List;
import java.util.Properties;

import org.apache.maven.plugin.AbstractMojo;
import org.apache.maven.plugin.MojoExecutionException;
import org.apache.velocity.VelocityContext;
import org.apache.velocity.app.Velocity;
import org.codehaus.plexus.util.StringUtils;
import org.jdom.Document;
import org.jdom.Element;
import org.jdom.Namespace;
import org.jdom.input.SAXBuilder;

/**
 * Builds a script to execute a given class in a project.
 * @goal script
 * @phase deploy
 */
public class BashScriptMojo extends AbstractMojo {
  
  /**
   * Location of the file.
   * @parameter expression="${project.build.directory}"
   * @required
   * @readonly
   */
  private File outputDir;
  
  /**
   * The project directory where the pom.xml file is located.
   * @parameter expression="${basedir}"
   * @required
   * @readonly
   */
  private File projectDir;
  
  /**
   * Full class name to build execution script for.
   * @parameter expression="${className}"
   * @required
   */
  private String className;

  @SuppressWarnings("unchecked")
  public void execute() throws MojoExecutionException {
    try {
      // parse the pom.xml to find the list of dependency and expand
      // them out to the correct path in the M2 repository to build
      // the classpath
      SAXBuilder parser = new SAXBuilder();
      Document doc = parser.build(new File(projectDir, "pom.xml"));
      Element root = doc.getRootElement();
      Namespace defaultNamespace = root.getNamespace();
      Element dependenciesElement = 
        root.getChild("dependencies", defaultNamespace);
      StringBuilder buf = new StringBuilder();
      List<Element> dependencyElements =
        dependenciesElement.getChildren("dependency", defaultNamespace);
      for (Element dependencyElement : dependencyElements) {
        String groupId = dependencyElement.getChildTextTrim(
          "groupId", defaultNamespace);
        String artifactId = dependencyElement.getChildTextTrim(
          "artifactId", defaultNamespace);
        String version = dependencyElement.getChildTextTrim(
          "version", defaultNamespace);
        String path = StringUtils.join(new String[] {
          "$M2_REPO",
          StringUtils.replace(groupId, ".", File.separator),
          artifactId,
          version,
          StringUtils.join(new String[] {artifactId, version}, "-") + ".jar"
        }, File.separator);
        buf.append(path).append(File.pathSeparator).append("\\\n");
      }
      // finally append the target/classes dir
      buf.append(projectDir.getAbsolutePath()).append("/target/classes");
      // calculate the class name only for script file and log file
      String shortClassName = 
        className.substring(className.lastIndexOf('.') + 1);
      // stick them into the context
      VelocityContext context = new VelocityContext();
      context.put("__classpath__", buf.toString());
      context.put("__date__", new Date());
      context.put("__classname__", className);
      context.put("__logfile__", shortClassName + ".log");
      // we want to load the .vm file from the classpath, so we configure
      // the ClassPathResourceLoader to get the vm file.
      Properties props = new Properties();
      props.setProperty("resource.loader", "classpath");
      props.setProperty(
        "classpath.resource.loader.class", 
              "org.apache.velocity.runtime.resource.loader.ClasspathResourceLoader");
      Velocity.init(props);
      File scriptFile = new File(outputDir, "run" + shortClassName + ".sh");
      BufferedWriter writer = new BufferedWriter(new FileWriter(scriptFile));
      Velocity.mergeTemplate("bash_script.vm", "UTF-8", context, writer);
      writer.flush();
      writer.close();
      getLog().info("Script " + scriptFile.getName() + 
        " written to " + scriptFile.getPath());
    } catch (Exception e) {
      getLog().error("Error executing BashScriptMojo", e);
      e.printStackTrace();
      throw new MojoExecutionException(e.getMessage(), e);
    }
  }
}

Finally, here is the Velocity template file. As you can see above, I had to use Velocity's ClassPathResourceLoader to load it from the classpath (src/main/resources) of the plugin project.

#!/bin/bash
# Generated by mvn mycompany:script on ${__date__}
M2_REPO=$HOME/.m2/repository
CLASSPATH=${__classpath__}
java -cp $CLASSPATH -Xmx2048m ${__classname__} $* 2>&1 | tee ${__logfile__}

Plugin configuration

To install this into your local repository, run "mvn install:install". On the target module, where you actually want to use this plugin, you need to configure it in the module's POM as shown below:

<project>
...
  <build>
  ...
    <plugins>
      ...
      <plugin>
        <groupId>com.mycompany.plugin</groupId>
        <artifactId>mycompany-maven-plugin</artifactId>
        <version>1.0-SNAPSHOT</version>
        <executions>
          <execution>
            <phase>deploy</phase>
            <goals>
              <goal>script</goal>
            </goals>
          </execution>
        </executions>
      </plugin>
    </plugins>
  </build>
</project>

To call this plugin from the target application, run the following command:

prompt$ mvn -o mycompany:script -DclassName=com.mycompany.foo.bar.Baz
[INFO] Scanning for projects...
[INFO] Searching repository for plugin with prefix: 'mycompany'.
[INFO] -------------------------------------------------------------------
[INFO] Building MyCompany Plugin Module
[INFO]    task-segment: [mycompany:script]
[INFO] -------------------------------------------------------------------
[INFO] [mycompany:script]
[INFO] Script runBaz.sh written to /home/.../target/runBaz.sh
[INFO] -------------------------------------------------------------------
[INFO] BUILD SUCCESSFUL
[INFO] -------------------------------------------------------------------
[INFO] Total time: 2 seconds
[INFO] Finished at: Fri Apr 10 16:24:33 GMT-08:00 2009
[INFO] Final Memory: 5M/9M
[INFO] -------------------------------------------------------------------

Which results in a shell script that looks something like this (edited for brevity):

#!/bin/bash
# Generated by mvn mycompany:script on Fri Apr 10 16:24:33 GMT-08:00 2009
M2_REPO=$HOME/.m2/repository
CLASSPATH=\
$M2_REPO/commons-cli/commons-cli/1.0/commons-cli-1.0.jar:\
$M2_REPO/commons-codec/commons-codec/1.3/commons-codec-1.3.jar:\
$M2_REPO/commons-io/commons-io/1.2/commons-io-1.2.jar:\
...\
/home/.../target/classes
java -cp $CLASSPATH -Xmx2048m com.mycompany.foo.bar.Baz $* \
  2>&1 | tee Baz.log

Conclusion

Of course, the bash scripts that we send to production are not quite this simple - there is additional validation to make sure another process is not already running, and hooks to email completion status, etc, but they too are boilerplate. I have intentionally kept the script simple, but it is easy to update the template file to produce something that is more robust and production-ready.

The plugin does not handle transitive dependencies - which kind of defeats the purpose of using Maven2, I know... But since we have parallel Maven2 and Ant descriptors (some of our developers haven't gotten around to becoming comfortable with Maven2 yet), this is not an issue in my case, since we explicitly list all dependencies in both the Maven2 POM and Ant's build.xml files. However, I hope to update the plugin at some point to include Maven2's transitive dependency detection. If you have already done the research on how to do this, I would appreciate pointers.

On a completely unrelated note...

On a completely unrelated note, I found yesterday that Stacey's, my favorite bookstore (for around the last 7 years) has gone out of business. They were selling off the book cases when I arrived yesterday. Up until 3 years ago, my last job was about a couple of blocks from the store, so I was a pretty frequent visitor, and would average about one computer book a month. I have since moved to another location that is a good half hour walk (or a 10 minute bus ride), so I haven't been going as often. In spite of the higher prices compared to Amazon's discounted prices, I liked going to the bookshop and buying from there, since (a) I did not have to wait for the book to be shipped and (b) I could compare different books before making a purchase. Not sure about you, but Amazon's look-inside feature just doesn't compare.

There is a Borders across the street from where I work, but most of the time they don't have what I want, and even if they do, the books are so disorganized that its like finding a needle in a haystack. The Barnes and Noble where I live is more organized, but their focus (probably rightly so, given the demographics) is on children's books.

If anybody knows of a good bookshop that sells computer books in or around the San Francisco Market Street area, would appreciate hearing from you. Otherwise, I guess I will just have to get used to buying books online.

Friday, April 03, 2009

Higher order functions in Java

I started learning a Scala sometime towards the beginning of this year. At a certain point during this period, I would find Java, my programming language at work (then and now), incredibly tedious to code in, mainly because of its verbosity. I remember thinking that the girlfriend metaphor described here summed up my situation quite aptly.

Since then, things have settled down somewhat (between the metaphorical wife and girlfriend), but I notice that my programming style has changed subtly to become more "Scala-like". Some of it is just smart programming, such as reorganizing method calls with dependencies on each other's side effects into stateless function calls which always return a copy of the original object. The other thing I have begun to notice is the huge number of for-loops that I end up writing in application code, mainly for doing some pretty mundane things such as filtering collections and converting a collection of one type to one of a different type.

Scala and Python (the other two languages that I know enough to code in) both have higher order functions which convert these for-loops into logical one-liners. Java does not have built-in language support for this, but the Apache commons-collections project and its generics-enabled cousin from Larvalabs both have methods in CollectionUtils that do.

However, quite a few of the CollectionUtils methods operate on collections in place and mutate them, so there is still the problem of unintended side effects if you are not careful, and potentially hard to read code if you are. To get around this, I decided to write my own versions that return a copy of the transformed collections. Unlike CollectionUtils, my methods operate on Lists and mimic the behavior of their Scala namesakes.

I do find some of the methods in CollectionUtils useful, such as find, exists and forAllDo. There are a bunch of nice recipes related to the Commons Collection classes in Philip Senger's blog, and I found this recipe dealing with functors particularly interesting.

The ListUtils class

The ListUtils class is a class that exposes a bunch of static methods to do various things with Lists, List of Lists, etc. The code is shown below. I describe each group in a little more detail below.

// Source: src/main/java/com/mycompany/utils/ListUtils.java
package com.mycompany.utils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.apache.commons.collections15.Predicate;
import org.apache.commons.collections15.Transformer;

/**
 * Static Utility Methods that operate on Lists. Inspired by List methods
 * available natively in Scala and Python.
 */
public class ListUtils {

  /**
   * Return a List made up of elements from another List that pass through
   * the given predicate. For example, {1,2,3,4,5}.filter(x => (x % 2 == 0))
   * would yield {2,4}.
   * @param <E> the type of the element in the List.
   * @param input the List of E.
   * @param predicate the Predicate on E to decide if it should be returned.
   * @return a List of E.
   */
  public static <E> List<E> filter(List<E> input, Predicate<E> predicate) {
    if (input == null) {
      return null;
    }
    List<E> output = new ArrayList<E>();
    for (E e : input) {
      if (predicate.evaluate(e)) {
        output.add(e);
      }
    }
    return output;
  }
  
  /**
   * Apply a transformation to each element of the input List, resulting in 
   * a List of objects of the same or different type. For example, 
   * {1,2,3}.map(x => "s" + x) would yield {"s1","s2","s3"}.
   * @param <E> the input type.
   * @param <O> the output type.
   * @param input the List of E.
   * @param transformer transformer to transform E to O.
   * @return the List of O.
   */
  public static <E,O> List<O> map(List<E> input, Transformer<E,O> transformer) {
    if (input == null) {
      return null;
    }
    List<O> output = new ArrayList<O>();
    for (E e : input) {
      O o = transformer.transform(e);
      output.add(o);
    }
    return output;
  }

  /**
   * The effect of this operation is the same as recursively combining 
   * all but the last element with the last element. For example,
   * {1,2,3,4,5}.reduceLeft((x,y) => x + y) would be the same as 
   * ((((1 + 2) + 3) + 4) + 5). The transformer takes a pair of E in
   * List<E> and returns a transformed reduction E.
   * @param <E> the type of the List element.
   * @param input the List of E to reduce.
   * @param reducer the reducing function modelled as a Transformer.
   * @return the reduced E value.
   */
  public static <E> E reduceLeft(List<E> input, Transformer<List<E>,E> reducer) {
    if (input == null) {
      return null;
    }
    E reduced = null;
    int size = input.size();
    for (int i = 0; i < size; i++) {
      if (i == 0) {
        reduced = input.get(i);
        continue;
      }
      reduced = (E) reducer.transform(pack(reduced, input.get(i)));
    }
    return reduced;
  }

  /**
   * The effect of this operation is the same as recursively combining the
   * first element of the input list with the results of combining the rest
   * of the list. For example, {1,2,3,4,5}.reduceRight((x,y) => x + y)
   * would be the same as (1 + (2 + (3 + (4 + 5)))). The transformer takes 
   * a pair of E and returns the reduced value E.
   * @param <E> the type of the List element.
   * @param input the List of E to reduce.
   * @param reducer the reducer function modelled as a Transformer.
   * @return the reduced E value.
   */
  public static <E> E reduceRight(List<E> input, Transformer<List<E>,E> reducer) {
    E reduced = null;
    int size = input.size();
    for (int i = size - 1; i >= 0; i--) {
      if (i == size - 1) {
        reduced = input.get(i);
        continue;
      }
      reduced = (E) reducer.transform(pack(input.get(i), reduced));
    }
    return reduced;
  }

  /**
   * Same as reduceLeft, but the reduced value is primed with a specified
   * initial value.
   * @param <E> the type of the List element.
   * @param input the List of E.
   * @param initialValue the initial value to start reducing from.
   * @param folder the folding transformer.
   * @return the folded value of E.
   */
  public static <E> E foldLeft(List<E> input, E initialValue, 
      Transformer<List<E>,E> folder) {
    int size = input.size();
    E folded = initialValue;
    for (int i = 0; i < size; i++) {
      folded = (E) folder.transform(pack(folded, input.get(i)));
    }
    return folded;
  }
  
  /**
   * Same as reduceRight, but the reduced value is primed with a specified
   * initial value.
   * @param <E> the type of the List element.
   * @param input the List of E.
   * @param initialValue the initial value for the reduction.
   * @param folder the folding transformer.
   * @return the folded value of E.
   */
  public static <E> E foldRight(List<E> input, E initialValue, 
      Transformer<List<E>,E> folder) {
    int size = input.size();
    E folded = initialValue;
    for (int i = size - 1; i >= 0; i--) {
      folded = (E) folder.transform(pack(input.get(i), folded));
    }
    return folded;
  }
  
  /**
   * Partitions an input List into two Lists. The first list contains the
   * elements where the Predicate returns true, and the second list contains
   * the elements where the Predicate returns false. For example, the call:
   * {1,2,3,4,5}.partition(x => (x % 2 == 0)) will return the lists {2,4} 
   * and {1,3,5}.
   * @param <E> the type of the List element.
   * @param input the List of E to be partitioned.
   * @param predicate the predicate to partition the list.
   * @return a pair of Lists partitioned by the predicate.
   */
  public static <E> List<List<E>> partition(List<E> input, Predicate<E> predicate) {
    List<E> truePartition = new ArrayList<E>();
    List<E> falsePartition = new ArrayList<E>();
    for (E e : input) {
      if (predicate.evaluate(e)) {
        truePartition.add(e);
      } else {
        falsePartition.add(e);
      }
    }
    List<List<E>> partitioned = new ArrayList<List<E>>();
    partitioned.add(truePartition);
    partitioned.add(falsePartition);
    return partitioned;
  }
  
  /**
   * Partitions an input list into multiple partitions based on a partitioning
   * transformer. The transformer takes an element and returns a 0-based integer
   * representing the list into which this element will be placed. 
   * @param <E> the type of the List element.
   * @param input the List of E.
   * @param partitioner a partitioning transformer.
   * @return the partitioned List of List<E>.
   */
  public static <E> List<List<E>> partition(List<E> input, 
      Transformer<E,Integer> partitioner) {
    Map<Integer,List<E>> parts = new HashMap<Integer,List<E>>();
    for (E e : input) {
      Integer partId = partitioner.transform(e);
      List<E> part;
      if (parts.containsKey(partId)) {
        part = parts.get(partId);
      } else {
        part = new ArrayList<E>();
      }
      part.add(e);
      parts.put(partId, part);
    }
    List<List<E>> partitions = new ArrayList<List<E>>();
    for (Integer partId : parts.keySet()) {
      if (parts.containsKey(partId)) {
        partitions.add(parts.get(partId));
      } else {
        partitions.add(new ArrayList<E>());
      }
    }
    return partitions;
  }

  /**
   * Flattens a List of Lists into a single flat list. Empty Lists and 
   * null elements are ignored during flattening. For example, the List
   * of Lists {{1,2,3},{4,5,6}}.flatten yields {1,2,3,4,5,6}.
   * @param <E> the type of the List element.
   * @param inputs the list of list of E.
   * @return a flattened list of E.
   */
  public static <E> List<E> flatten(List<List<E>> inputs) {
    List<E> flattened = new ArrayList<E>();
    for (List<E> le : inputs) {
      if (le == null || le.size() == 0) {
        continue;
      }
      for (E e : le) {
        if (e == null) {
          continue;
        }
        flattened.add(e);
      }
    }
    return flattened;
  }

  /**
   * Joins individual elements of a pair of lists. Result is a list of
   * pairs of elements. If the sizes of the two input lists are different,
   * then the size of the zipped list is the smaller of the two sizes of
   * the input. For example, {{1,2,3},{4,5}}.zip will yield {{1,4},{2,5}}.
   * @param <E> the type of the list element.
   * @param left the first list of E.
   * @param right the second list of E.
   * @return the zipped list of pairs of E.
   */
  public static <E> List<List<E>> zip(List<E> left, List<E> right) {
    List<List<E>> zipped = new ArrayList<List<E>>();
    int leftSize = left.size();
    int rightSize = right.size();
    int minSize = Math.min(leftSize, rightSize);
    for (int i = 0; i < minSize; i++) {
      List<E> listE = new ArrayList<E>();
      listE.add(left.get(i));
      listE.add(right.get(i));
      zipped.add(listE);
    }
    return zipped;
  }
  
  /**
   * Inverse of the zip operation. Given a List of pairs of elements, this
   * method breaks it up into two lists of E. For example, {{1,4},{2,5}.unzip
   * will yield {{1,2},{4,5}}.
   * @param <E> the type of the List element.
   * @param inputs the List of pairs of E.
   * @return two lists of E.
   */
  public static <E> List<List<E>> unzip(List<List<E>> inputs) {
    List<E> left = new ArrayList<E>();
    List<E> right = new ArrayList<E>();
    for (List<E> le : inputs) {
      left.add(le.get(0));
      right.add(le.get(1));
    }
    List<List<E>> unzipped = 
      new ArrayList<List<E>>();
    unzipped.add(left);
    unzipped.add(right);
    return unzipped;
  }
  
  /**
   * A combination of map and flatten. Each element of the input list is 
   * transformed into a List of E by the transformer, and flattened out into
   * the output list. For example, {1,2}.flatMap(x => List(x, x * 10))
   * will yield {1,10,2,20}.
   * @param <E> the type of the list element.
   * @param input the list of E.
   * @param transformer transforms each element to a List of elements.
   * @return the flattened mapped list.
   */
  public static <E> List<E> flatMap(List<E> input,
      Transformer<E,List<E>> transformer) {
    List<E> flattened = new ArrayList<E>();
    for (E e : input) {
      List<E> transformed = transformer.transform(e);
      if (transformed != null && transformed.size() > 0) {
        flattened.addAll(transformed); // nulls are allowed
      }
    }
    return flattened;
  }

  /**
   * Merges a List of Lists into a single list based on the sequencer. The
   * sequencer is a special transformer that takes an integer representing
   * the current list index (0-based) and returns the next list index to 
   * pick the next element from. It also needs to return the first list 
   * index when passed in an argument of -1.
   * @param <E> the type of the list element.
   * @param inputs the List of Lists of E.
   * @param sequencer a specialized transformer specifying merge sequence.
   * @return the merged list.
   */
  public static <E> List<E> merge(List<List<E>> inputs, 
      Transformer<Integer,Integer> sequencer) {
    int[] sizes = new int[inputs.size()];
    for (int i = 0; i < sizes.length; i++) {
      sizes[i] = inputs.get(i).size();
    }
    int[] current = new int[inputs.size()];
    List<E> merged = new ArrayList<E>();
    int lid = sequencer.transform(-1);
    for (;;) {
      if (lid > inputs.size()) {
        throw new IllegalArgumentException("List out of bounds");
      }
      if (current[lid] < sizes[lid]) {
        merged.add(inputs.get(lid).get(current[lid]));
      }
      current[lid]++;
      boolean alldone = true;
      for (int i = 0; i < sizes.length; i++) {
        if (current[i] < sizes[i]) {
          alldone = false;
          break;
        }
      }
      if (alldone) { 
        break;
      }
      lid = sequencer.transform(lid);
    }
    return merged;
  }
  
  /**
   * Convenience method to pack two elements E into a List<E>.
   * @param <E> the type of element.
   * @param first the first element in the list.
   * @param second the second element in the list.
   * @return the List containing the pair of E.
   */
  private static <E> List<E> pack(E first, E second) {
    List<E> packed = new ArrayList<E>();
    packed.add(first);
    packed.add(second);
    return packed;
  }
}

For each operation or set of operations, I wrote some JUnit code to show the usage in Java. I also tried the function out in Scala to make sure that I don't change the behavior. I describe these in the sections below.

filter

Filter extracts the elements for which the given predicate is true. Here is some Scala code to extract the even numbers from a List of Integers.

1
2
3

scala> val list = List(1,2,3,4,5,6,7,8,9,10)
scala> list.filter(x => (x % 2 == 0))
res0: List[Int] = List(2, 4, 6, 8, 10)

You can call this method in Java like this. Notice that although the Predicate is defined as an anonymous function, there is no reason you cannot define it as a variable and pass it in, or even make a class out of it (although the last approach may lead to a very large number of tiny classes in your application, and possibly make your code harder to maintain).

  @Test
  public void testFilter() throws Exception {
    List<Integer> list = 
      Arrays.asList(new Integer[] {1,2,3,4,5,6,7,8,9,10});
    List<Integer> evens = ListUtils.filter(list, 
      new Predicate<Integer>() {
        public boolean evaluate(Integer i) {
          return (i % 2 == 0);
        }
    });
    System.out.println(">>> evens = " + evens);
  }

which produces the following output:

1	>>> evens = [2, 4, 6, 8, 10]

map

Map applies a transformation to each element of the input list, resulting in either a list of the same or different type. We show two usages of map in Scala below.

scala> val list = List(1,2,3,4,5)
scala> val squares = list.map(x => x * x) 
squares: List[Int] = List(1, 4, 9, 16, 25)
scala> val strings = list.map(x => "s" + x)     
strings: List[java.lang.String] = List(s1, s2, s3, s4, s5)

Using the ListUtils.map method in Java is a little more verbose, but otherwise quite similar, as shown below:

  @Test
  public void testMap() throws Exception {
    List<Integer> list = 
      Arrays.asList(new Integer[] {1,2,3,4,5,6,7,8,9,10});
    List<Integer> squares = ListUtils.map(list, 
      new Transformer<Integer,Integer>() {
        public Integer transform(Integer i) {
          return i * i;
        }
    });
    System.out.println(">>> squares = " + squares);
    List<String> strings = ListUtils.map(list, 
      new Transformer<Integer,String>() {
        public String transform(Integer i) {
          return "s" + i;
        }
    });
    System.out.println(">>> strings = " + strings);
  }

and produces the following output:

1 2	>>> squares = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] >>> strings = [s1, s2, s3, s4, s5, s6, s7, s8, s9, s10]

reduceLeft, reduceRight, foldLeft and foldRight

All these functions aim to apply a transformation to combine the elements of a list into a single element. The left and right suffixes to the method names indicate the direction of the reduction - reduceLeft reduces starting from the left and reduceRight starts from the right. The corresponding fold methods are the same as reduce, but they allow you to specify an initial value to the reduction. Here are some Scala examples:

scala> val ints = List(1,2,3,4,5,6,7,8,9,10)
scala> ints.reduceLeft((x,y) => (x + y))
res0: Int = 55
scala> ints.reduceRight((x,y) => (x + y))
res1: Int = 55
scala> ints.foldLeft(0)((x,y) => (x+y))
res2: Int = 55
scala> ints.foldRight(0)((x,y) => (x+y))
res3: Int = 55
scala> ints.reduceLeft((x,y) => if (x > y) x else y)
res4: Int = 10
scala> ints.reduceRight((x,y) => if (x > y) x else y)
res5: Int = 10
scala> ints.foldLeft(0)((x,y) => if (x > y) x else y) 
res6: Int = 10
scala> ints.foldRight(0)((x,y) => if (x > y) x else y)
res7: Int = 10
scala> val strs = ints.map(x => "s" + x)
scala> strs.reduceLeft((x,y) => (x + "," + y))
res8: java.lang.String = s1,s2,s3,s4,s5,s6,s7,s8,s9,s10
scala> strs.reduceRight((x,y) => (x + "," + y))
res9: java.lang.String = s1,s2,s3,s4,s5,s6,s7,s8,s9,s10
scala> strs.foldLeft("")((x,y) => (x + "," + y))
res10: java.lang.String = ,s1,s2,s3,s4,s5,s6,s7,s8,s9,s10
scala> strs.foldRight("")((x,y) => (x + "," + y))
res11: java.lang.String = s1,s2,s3,s4,s5,s6,s7,s8,s9,s10,

Notice that in most cases (at least in our examples), there is no difference between the left and right reduces (and folds) - this is true when the operation is associative. The same operations using ListUtils is shown below:

  @Test
  public void testReduceLeft() throws Exception {
    List<Integer> list = Arrays.asList(
      new Integer[] {1,2,3,4,5,6,7,8,9,10});
    List<String> strings = ListUtils.map(list, 
      new Transformer<Integer,String>() {
        public String transform(Integer i) {
          return "s" + i;
        }
    });
    Integer sum = ListUtils.reduceLeft(list, 
      new Transformer<List<Integer>,Integer>() {
        public Integer transform(List<Integer> args) {
          Integer first = args.get(0);
          Integer second = args.get(1);
          return first + second;
        }
    });
    System.out.println(">>> sum from reduceLeft = " + sum);
    Integer max = ListUtils.reduceLeft(list, 
      new Transformer<List<Integer>,Integer>() {
        public Integer transform(List<Integer> args) {
          Integer first = args.get(0);
          Integer second = args.get(1);
          return (first > second ? first : second);
        }
    });
    System.out.println(">>> max from reduceLeft = " + max);
    String strcat = ListUtils.reduceLeft(strings, 
      new Transformer<List<String>,String>() {
        public String transform(List<String> args) {
          return args.get(0) + "," + args.get(1);
        }
    });
    System.out.println(">>> strcat from reduceLeft = " + strcat);
  }
  
  @Test
  public void testReduceRight() throws Exception {
    List<Integer> list = Arrays.asList(
      new Integer[] {1,2,3,4,5,6,7,8,9,10});
    List<String> strings = ListUtils.map(list, 
      new Transformer<Integer,String>() {
        public String transform(Integer i) {
          return "s" + i;
        }
    });
    Integer sum = ListUtils.reduceRight(list, 
      new Transformer<List<Integer>,Integer>() {
        public Integer transform(List<Integer> args) {
          Integer first = args.get(0);
          Integer second = args.get(1);
          return first + second;
        }
    });
    System.out.println(">>> sum from reduceRight = " + sum);
    Integer max = ListUtils.reduceRight(list, 
      new Transformer<List<Integer>,Integer>() {
        public Integer transform(List<Integer> args) {
          Integer first = args.get(0);
          Integer second = args.get(1);
          return (first > second ? first : second);
        }
    });
    System.out.println(">>> max from reduceRight = " + max);
    String strcat = ListUtils.reduceRight(strings, 
      new Transformer<List<String>,String>() {
        public String transform(List<String> args) {
          return args.get(0) + "," + args.get(1);
        }
    });
    System.out.println(">>> strcat from reduceRight = " + strcat);
  }

  @Test
  public void testFoldLeft() throws Exception {
    List<Integer> list = Arrays.asList(
      new Integer[] {1,2,3,4,5,6,7,8,9,10});
    List<String> strings = ListUtils.map(list, 
      new Transformer<Integer,String>() {
        public String transform(Integer i) {
          return "s" + i;
        }
    });
    Integer sum = ListUtils.foldLeft(list, 0, 
      new Transformer<List<Integer>,Integer>() {
        public Integer transform(List<Integer> args) {
          Integer first = args.get(0);
          Integer second = args.get(1);
          return first + second;
        }
    });
    System.out.println(">>> sum from foldLeft = " + sum);
    Integer max = ListUtils.foldLeft(list, 0, 
      new Transformer<List<Integer>,Integer>() {
        public Integer transform(List<Integer> args) {
          Integer first = args.get(0);
          Integer second = args.get(1);
          return (first > second ? first : second);
        }
    });
    System.out.println(">>> max from foldLeft = " + max);
    String strcat = ListUtils.foldLeft(strings, "", 
      new Transformer<List<String>,String>() {
        public String transform(List<String> args) {
          return args.get(0) + "," + args.get(1);
        }
    });
    System.out.println(">>> strcat from foldLeft = " + strcat);
  }

  @Test
  public void testFoldRight() throws Exception {
    List<Integer> list = Arrays.asList(
      new Integer[] {1,2,3,4,5,6,7,8,9,10});
    List<String> strings = ListUtils.map(list, 
      new Transformer<Integer,String>() {
        public String transform(Integer i) {
          return "s" + i;
        }
    });
    Integer sum = ListUtils.foldRight(list, 0, 
      new Transformer<List<Integer>,Integer>() {
        public Integer transform(List<Integer> args) {
          Integer first = args.get(0);
          Integer second = args.get(1);
          return first + second;
        }
    });
    System.out.println(">>> sum from foldRight = " + sum);
    Integer max = ListUtils.foldRight(list, 0, 
      new Transformer<List<Integer>,Integer>() {
        public Integer transform(List<Integer> args) {
          Integer first = args.get(0);
          Integer second = args.get(1);
          return (first > second ? first : second);
        }
    });
    System.out.println(">>> max from foldRight = " + max);
    String strcat = ListUtils.foldRight(strings, "", 
      new Transformer<List<String>,String>() {
        public String transform(List<String> args) {
          return args.get(0) + "," + args.get(1);
        }
    });
    System.out.println(">>> strcat from foldRight = " + strcat);
  }

The above four tests produce the following outputs.

>>> sum from reduceLeft = 55
>>> max from reduceLeft = 10
>>> strcat from reduceLeft = s1,s2,s3,s4,s5,s6,s7,s8,s9,s10
>>> sum from reduceRight = 55
>>> max from reduceRight = 10
>>> strcat from reduceRight = s1,s2,s3,s4,s5,s6,s7,s8,s9,s10
>>> sum from foldLeft = 55
>>> max from foldLeft = 10
>>> strcat from foldLeft = ,s1,s2,s3,s4,s5,s6,s7,s8,s9,s10
>>> sum from foldRight = 55
>>> max from foldRight = 10
>>> strcat from foldRight = s1,s2,s3,s4,s5,s6,s7,s8,s9,s10,

partition

The partition method in Scala uses a predicate to split the list into two parts and returns them. In addition, ListUtils has an extra method that allows you to split a List into multiple partitions based on a partitioning transformer. Heres how you would do this in Scala.

1
2
3

scala> val list = List(1,2,3,4,5)
scala> list.partition(x => (x % 2 == 0))
res0: (List[Int], List[Int]) = (List(2, 4),List(1, 3, 5))

And this JUnit test shows how to use the two partition methods with ListUtils.

  @Test
  public void testPartition() throws Exception {
    List<Integer> list = Arrays.asList(
      new Integer[] {1,2,3,4,5,6,7,8,9,10});
    List<List<Integer>> oddevens = ListUtils.partition(list, 
      new Predicate<Integer>() {
        public boolean evaluate(Integer i) {
          return (i % 2 == 1);
        }
    });
    List<List<Integer>> evenodds = ListUtils.partition(list, 
      new Predicate<Integer>() {
        public boolean evaluate(Integer i) {
          return (i % 2 == 0);
        }
    });
    System.out.println(">>> partition ints to odds and evens = " +
      oddevens.get(0) + " and " + oddevens.get(1));
    System.out.println(">>> partition ints to evens and odds = " +
      evenodds.get(0) + " and " + evenodds.get(1));
    List<List<Integer>> multiparts = ListUtils.partition(list, 
      new Transformer<Integer,Integer>() {
        public Integer transform(Integer i) {
          if (i <= 5) {
            if (i % 2 == 0) {
              return 0;
            } else {
              return 1;
            }
          } else {
           if (i % 2 == 0) {
             return 2;
           } else {
             return 3;
           }
          }
        }
    });
    System.out.println(">>> multipart partitioning ints = " +
      multiparts);
    List<String> strings = Arrays.asList(
      new String[] {"a1","a2","b1","b2","c1","c2"});
    List<List<String>> smultiparts = 
      ListUtils.partition(strings, new Transformer<String,Integer>() {
        public Integer transform(String s) {
          char firstchar = StringUtils.lowerCase(s).charAt(0);
          return firstchar - 'a';
        }
    });
    System.out.println(">>> multipart partitioning strings = " +
      smultiparts);
  }

and they produce the following output:

>>> partition ints to odds and evens = [1, 3, 5, 7, 9] and [2, 4, 6, 8, 10]
>>> partition ints to evens and odds = [2, 4, 6, 8, 10] and [1, 3, 5, 7, 9]
>>> multipart partitioning ints = [[2, 4], [1, 3, 5], [6, 8, 10], [7, 9]]
>>> multipart partitioning strings = [[a1, a2], [b1, b2], [c1, c2]]

forall, find and exists

The Scala forall method allows the caller to operate on each element of the list in some way. Its also called a List Comprehension (Python) or a Sequence Comprehension (Scala). CollectionUtils.forAllDo() provides the functionality of the forall method, so I did not implement it in ListUtils.

The same goes for find and exists methods - these are both read-only methods in CollectionUtils, so no need to implement them in ListUtils.

zip, unzip and flatten

These are some of Scala's methods that I thought would be useful, so I went ahead and implemented it in ListUtils.

The zip method "zips up" the elements of two input lists. If the sizes of the two input lists are different, the size of the zipped list is the smaller of the two. The unzip method is the inverse of the zip method. The flatten method takes a list of lists and flattens it out, ignoring empty lists but not null elements.

scala> val list1 = List(1,2,3,4,5)
scala> val list2 = List(10,20,30)
scala> val zipped = list1.zip(list2)
zipped: List[(Int, Int)] = List((1,10), (2,20), (3,30))
scala> val unzipped = List.unzip(zipped)
unzipped: (List[Int], List[Int]) = (List(1, 2, 3),List(10, 20, 30))
scala> val lol = List(List(1,2,3),List(10,20,30))
scala> List.flatten(lol)
res0: List[Int] = List(1, 2, 3, 10, 20, 30)
scala> val lol2 = List(List(1,2),List(),List(None,10,9,8))
scala> List.flatten(lol2)
res1: List[Any] = List(1, 2, None, 10, 9, 8)

The code snippet below shows how to use these three methods in ListUtils.

  @Test
  public void testFlatten() throws Exception {
    List<Integer> list0 = Arrays.asList(new Integer[] {1,2,3});
    Transformer<Integer,Integer> mult10 = 
      new Transformer<Integer,Integer>() {
        public Integer transform(Integer i) {
          return i * 10;
        }
    };
    List<Integer> list10 = ListUtils.map(list0, mult10);
    List<List<Integer>> zipped = ListUtils.zip(list0, list10);
    System.out.println(">>> zipped = " + zipped);
    List<Integer> flattened = ListUtils.flatten(zipped);
    System.out.println(">>> flattened = " + flattened);
    List<List<Integer>> unzipped = ListUtils.unzip(zipped);
    System.out.println(">>> unzipped = " + unzipped);
    List<Integer> list10Le20 = ListUtils.filter(list10, 
      new Predicate<Integer>() {
        public boolean evaluate(Integer i) {
          return (i <= 20);
        }
    });
    List<List<Integer>> zippedLe20 = ListUtils.zip(
      list0, list10Le20);
    System.out.println(">>> zipped (le 20) = " + zippedLe20);
    List<Integer> flattenedLe20 = ListUtils.flatten(zippedLe20);
    System.out.println(">>> flattened (le 20) = " + flattenedLe20);
    List<List<Integer>> unzippedLe20 = 
      ListUtils.unzip(zippedLe20);
    System.out.println(">>> unzipped (le 20) = " + unzippedLe20);
  }

which produce the following output:

>>> zipped = [[1, 10], [2, 20], [3, 30]]
>>> flattened = [1, 10, 2, 20, 3, 30]
>>> unzipped = [[1, 2, 3], [10, 20, 30]]
>>> zipped (le 20) = [[1, 10], [2, 20]]
>>> flattened (le 20) = [1, 10, 2, 20]
>>> unzipped (le 20) = [[1, 2], [10, 20]]

flatMap

The flatMap method is a combination of map to generate zero or more elements for each input element, then flatten them out. I have found this useful for navigating hierarchies and then flattening the nodes out. Here is a simple Scala example.

1
2
3

scala> val list = List(1,2,3)
scala> list.flatMap(x => List(x, x*10, x*100))   
res0: List[Int] = List(1, 10, 100, 2, 20, 200, 3, 30, 300)

And the corresponding example in Java using ListUtils.

  @Test
  public void testFlatMap() throws Exception {
    List<Integer> list = Arrays.asList(new Integer[] {1,2,3});
    List<Integer> flatmapped = ListUtils.flatMap(list, 
      new Transformer<Integer,List<Integer>>() {
        public List<Integer> transform(Integer i) {
          List<Integer> transformed = new ArrayList<Integer>();
          transformed.add(i);
          transformed.add(i * 10);
          transformed.add(i * 100);
          return transformed;
        }
    });
    System.out.println(">>> flatmapped = " + flatmapped);
  }

This code produces the following output:

1	>>> flatmapped = [1, 10, 100, 2, 20, 200, 3, 30, 300]

merge

The final method (not in Scala, as far as I know) is the merge method. I wrote this because I needed this. Essentially, the merge method attempts to merge multiple lists using a sequence rule, modelled here as a Transformer. Here is how one may use it.

  @Test
  public void testMerge() throws Exception {
    List<String> list1 = 
      Arrays.asList(new String[] {"a1", "a2", "a3"});
    List<String> list2 = Arrays.asList(new String[] {"b1"});
    List<String> list3 = Arrays.asList(new String[] {"c1", "c2"});
    List<String> list4 = Arrays.asList(new String[] {});
    List<List<String>> inputs = 
      new ArrayList<List<String>>();
    inputs.add(list1);
    inputs.add(list2);
    inputs.add(list3);
    inputs.add(list4);
    List<String> merged = ListUtils.merge(inputs, 
      new Transformer<Integer,Integer>() {
        public Integer transform(Integer i) {
          switch (i) { // sequence is {0,2,1,3}
            case -1:
              return 0;
            case 0:
              return 2;
            case 1:
              return 3; 
            case 2:
              return 1;
            case 3:
            default: // never happen
              return 0;
          }
        }
    });
    System.out.println(">>> merged = " + merged);
  }

The merge produces the following output:

1	>>> merged = [a1, c1, b1, a2, c2, a3]

I hope this stuff was useful. I've been using the functor objects from commons-collections (the larvalabs version) for a while now, but its only recently, after learning about them in Scala (and later Python), that I have been thinking how much cleaner my application would be with logical one-liners instead of for-loops. I think that judicious use of this feature (i.e. resisting the temptation of the golden hammer :-)) can result in code that is easier and more fun to write, as well as more readable and hence easier to maintain.

Salmon Run