Tuesday, 30 June 2009

Practical Example of GSON

Please note that this page has moved to: http://www.javacreed.com/simple-gson-example/.

GSON is a Java API, developed by Google, used to convert between Java objects and JSON objects. This article discusses and provides examples about this API and how it can be used. More information about this API can be found at: http://sites.google.com/site/gson/.

This is the first from three articles about GSON. No GSON or JSON experience is required as this article acts as a primer for the other two articles. The second article provides more examples about the use of GSON deserializer (from JSON to Java) and the third and final article provides more examples about the GSON serializer (from Java to JSON). All code for all three articles is available at: http://code.google.com/p/gson-practical-examples/source/checkout.

Download and Install

Before you can do any work with this API, you need to download the library (jar file) and include it in the classpath. The library, together with the source and JavaDocs, can be downloaded from: http://code.google.com/p/google-gson/downloads/list. Once downloaded, add the gson-<version>.jar to the classpath. For those readers who prefer to use maven to manage the dependencies (JAR files), add the following dependency to the pom.xml.

    <dependency>
      <groupId>com.google.code.gson</groupId>
      <artifactId>gson</artifactId>
      <version>2.2.1</version>
    </dependency>

Change the <version>2.2.1</version> as required. All code examples shown in this article use the version listed above. A copy of the pom.xml file can be found here.

If this library is to be used in a web application, make sure to have a copy saved under the WEB-INF/lib folder. Alternatively, the library can be added to the application server and made available to the web application.

A Simple Example

The GSON API provides a stateless class, Gson, that handles the conversions between Java and JSON objects. An instance of this class can be created by invoking the default constructor or as shown in the simple example below, using the GsonBuilder class. The GsonBuilder class provides customisation and allows the developer to instantiate Gson as required.

package com.albertattard.examples.gson.part1_1;

import com.google.gson.Gson;
import com.google.gson.GsonBuilder;

public class SimpleExample1 {
  public static void main(String[] args) {
    Gson gson = new GsonBuilder().create();
    gson.toJson("Hello", System.out);
    gson.toJson(123, System.out);
  }
}
In the above example, we've created an instance of Gson and converted the Java String and int to JSON objects. The above code produces the following as its output to the command prompt:
"Hello"123
It's not rocket science, but it's a start. Note that the output of the above is all going to the command prompt. The toJason() method takes two parameters, the Java object to be converted to JSON and an instance of Appendable. We can easily change the out to a file or network stream.

package com.albertattard.examples.gson.part1_1;

import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;
import com.google.gson.Gson;
import com.google.gson.GsonBuilder;

public class SimpleExample2 {
  public static void main(String[] args) throws IOException {
    Writer writer = new FileWriter("Output.json");

    Gson gson = new GsonBuilder().create();
    gson.toJson("Hello", writer);
    gson.toJson(123, writer);

    writer.close();
  }
}
Why is the variable declared as a Writer when the actual type is FileWriter?
It is a good practice to have your variables as generic as possible. In the above example, we're only using methods defined by the Appendable and Writer interfaces. Having the variable type more specific than required will make the code less portable and harder to maintain as we'll see in the following example.

Note that in the above example we are not handling the steams (Writer) properly. Ideally the resources are closed within the finally block or used within the try-with-resources as shown below. We've ignored this to keep the code as simple as possible.


  public static void main(String[] args) throws IOException {
    try (Writer writer = new FileWriter("Output.json")) {

      Gson gson = new GsonBuilder().create();
      gson.toJson("Hello", writer);
      gson.toJson(123, writer);
    }
  }

The above code produces the file: Output.json with the JSON objects. Note that here we used the character streams and not the byte streams. We cannot use the byte streams as the toJson() method is expecting an Appendable instance and the byte streams are not descendants from the Appendable interface. The Appendable interface works with characters and not bytes. Java provides the InputStreamReader and the OutputStreamWriter classes that convert byte streams into character streams as illustrated in the following example.


package com.albertattard.examples.gson.part1_1;

import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.Writer;
import com.google.gson.Gson;
import com.google.gson.GsonBuilder;

public class SimpleExample3 {

  public static void main(String[] args) throws IOException {
    Writer writer = new OutputStreamWriter(
            new FileOutputStream("Output.json"));

    Gson gson = new GsonBuilder().create();
    gson.toJson("Hello", writer);
    gson.toJson(123, writer);

    writer.close();
  }
}
As you can see, we only needed to change the instantiation part. The rest (expect for the imports) of the code is unchanged.

Consuming JSON objects

Let's say that we need to consume JSON objects and load them as Java objects. Assume that a web server will produce the following JSON when queried:

{
  NAME:"Albert Attard",
  P_LANGUAGE:"Java",
  LOCATION:"Malta"
}
This JSON object contains three fields with their respective values. Let's say that we need to consume the JSON object and create a Java object that represents this data. To make this example more interesting, let assume that we're only interested from the name and the location fields.

First we need to create a Java class with the fields that we want to represent (name and location). Let's call the class Person1. The name of this class is irrelevant, but the name of the fields is not. The field names must match (including the case) with the names in JSON. Also, the class must include a default constructor. As shown below, the fields name and location are in uppercase as found in JSON. The JSON field P_LANGUAGE is ignored as the Java object does not include a field with this name. It is understandable that the fields' names do not follow the Java naming convention, but for the time being let's keep things simple. More about this is discussed in part 2.


package com.albertattard.examples.gson.part1_2;

public class Person1 {
  private String NAME;
  private String LOCATION;

  // Getters and setters are not required for this example.
  // GSON sets the fields directly.

  @Override
  public String toString() {
    return NAME + " - " + LOCATION;
  }
}
With the Java object ready, we can read the JSON objects and load them as Java objects as illustrated below. To simulate a real life situation, we're using a byte stream as input with default encoding. Also note that the JSON content is saved into a file (which is not usually the case) located in the same directory of the following class.

package com.albertattard.examples.gson.part1_2;

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import com.google.gson.Gson;
import com.google.gson.GsonBuilder;

public class JsonToJava1 {

  public static void main(String[] args) throws IOException {
    Reader reader = new InputStreamReader(JsonToJava1.class
        .getResourceAsStream("Server1.json"));

    Gson gson = new GsonBuilder().create();
    Person1 p = gson.fromJson(reader, Person1.class);
    System.out.println(p);

    reader.close();
  }
}
This should produce: Albert Attard - Malta. Gson parsed the JSON object and created an instance of the Person1 class.

Nested JSON Objects

Let's take the above example one step further and include a nested object as illustrated in the following JSON code fragment.

{
  NAME:"Albert Attard",
  P_LANGUAGE:"Java",
  LOCATION:"Malta",
  EXAM: {
    SUBJECT:"Programming",
    GRADE:4.5
  }
}
Here we have an EXAM field which is made from two other fields: SUBJECT and GRADE. Likewise, we need to modify the Person1 class defined above to include the EXAM field and create a new Java class to represent the SUBJECT and GRADE fields.

We first create the new class that will represent the nested object. As we discussed before, the class name is irrelevant but the fields' names must match those define in JSON.


package com.albertattard.examples.gson.part1_3;

public class Exam1 {
  private String SUBJECT;
  private double GRADE;

  // Getters and setters are not required for this example.
  // GSON sets the fields directly.

  @Override
  public String toString() {
    return SUBJECT + " - " + GRADE;
  }
}
Now we can modify the Person1 class (Person2 in the following example) and include a new field with the same name as in JSON of type Exam1 as shown next. Instead we created a new class to keep track of the progress made.

package com.albertattard.examples.gson.part1_3;

public class Person2 {

  private String NAME;
  private String LOCATION;
  private Exam1 EXAM; 

  @Override
  public String toString() {
    return NAME + " - " + LOCATION + " (" + EXAM + ")";
  }
}
Note that the changes required are minimal as Gson dynamically discovers (through reflection) the class and its fields. This article does not cover reflection. For more information about reflection please refer to: Reflection in Action.
Finally, let's test the new changes.

package com.albertattard.examples.gson.part1_3;

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import com.google.gson.Gson;
import com.google.gson.GsonBuilder;

public class JsonToJava2 {

  public static void main(String[] args) throws IOException {
    Reader reader = new InputStreamReader(JsonToJava2.class
        .getResourceAsStream("Server2.json"));

    Gson gson = new GsonBuilder().create();
    Person2 p = gson.fromJson(reader, Person2.class);
    System.out.println(p);

    reader.close();
  }
}
Instead of using person 1, we're using the new class which include the new exam field.

Conclusion

Even though it may be a new concept, JSON is very simple and straight forward. The Gson API makes it very simple to use and even though not discussed here, it provides a great deal of flexibility.

For more GSON examples please visit the second part (part-2), where we explore more complex examples and discuss how to use the GSON deserializer to take full control over the deserialization process.

Thursday, 18 June 2009

PreparedStatement and NULLs in the WHERE Clause

The java.sql.PreparedStatement comes with a method for setting nulls as values for the parameters: setNull(int, int). This method is very tricky and does not work as expected when it comes to the SQL WHERE clause.

This article talks about a common pitfall that may developers fall in and never test. More details about the prepared statement interface can be found at http://java.sun.com/docs/books/tutorial/jdbc/basics/prepared.html

The Problem

Consider the following query SELECT * FROM EMPLOYEES WHERE MANAGED_ID = ?. This query returns all employees for a given manager id. The following code fragment illustrates how this query is used to retrieve all employees for manager id 100.


  PreparedStatement statement = connection.prepareStatement(
      "SELECT * FROM EMPLOYEES WHERE MANAGED_ID = ?");
  statement.setLong(1, 100L);
  ResultSet resultSet = statement.executeQuery();

The above code works well for any manager id. But what if we would like to select all employees that do not have a manager, that is, the manager id column is set to NULL (SQL NULL)? If we do the following we will get nothing back, even if there are employees with no manager assigened.


  PreparedStatement statement = connection.prepareStatement(
      "SELECT * FROM EMPLOYEES WHERE MANAGED_ID = ?");
  statement.setNull(1, Types.INTEGER);
  ResultSet resultSet = statement.executeQuery();

Why? The advantage of the prepared statement is that the statement is compiled once and it is executed many times. This provides performance benefits but comes with a cost. That is, once the statement is compiled, the only things that can change are the parameters' values. The equals sign stays there. This instead of having our SQL statement WHERE MANAGER_ID IS NULL we have WHERE MANAGER_ID = NULL, which does not yield the same results.

The Solution

The solution is very simple. We have to modify the string version of the SQL statement to handle NULLs. Assume we have the following method that returns a list of employees for a given manager id, where a connection is already established and available to the same method.


  public List getEmployeesWithManagerId(Long managerId)
                                        throws SQLException {
    List employees = new ArrayList();
    String select = "SELECT * FROM EMPLOYEES WHERE MANAGER_ID "
                    + (managerId == null?"IS NULL":"= ?");
    PreparedStatement statement = 
        connection.prepareStatement(select);
    if(managerId != null){
      statement.setLong(1, 100L);
    }
    ResultSet resultSet = statement.executeQuery();
    while(resultSet.next()){
      // Get the employee details and add it to the list
    }
    return employees;
  }

Why are we still using the prepared statement? Can we use the select statement instead and concatenate the values? Yes you can but not suggested as the prepared statement also provides protection against SQL injections.

Conclusion

Even though very simple, this is a common bug which can be easily iron out with proper testing. Since the database columns can accept NULLs, refrain from using Java primitives and use their wrappers instead. Note that the result set getXXX methods return the primitive values which can be tricky too. A 0 (zero - the default value for most of the primitives) is returned if the database field was NULL. In that case make sure to use to the method wasNull().

Thursday, 4 June 2009

From XML to Java using SAX Parser

XML is a common way to save data especially while in transit between applications. For example, a program used to register students (written by a company) needs extract/load data produced by another program written by another company (may be in a different language). One of the best ways to do this is by having the source program producing an XML file and the destination program loading this file.

This article discusses how the Java SAX parser can be used to load an XML file as a List of Java objects.

The problem

Assume we need to develop a program that read the following simple XML file and loads it as a list of Java objects. The file is called Test.xml.


<students>
  <student name="Albert Attard">
    <class>Java</class>
    <class>Math</class>
    <grade>65</grade>
  </student>
  <student name="Mary Borg">
    <class>English</class>
    <grade>93</grade>
  </student>
  <student name="Joe Vella">
    <class>Math</class>
    <class>English</class>
    <grade>47</grade>
  </student>
  <student name="Paul Galea">
    <class>Math</class>
    <class>Maltese</class>
    <grade>52</grade>
  </student>
</students>

The above XML file contains a list of four students, each student having a name, a list of classes that he/she will attend and their grade. The student name is an attribute of the student tag while the class and grade are inner tags of the student tag.

Loading data from XML file

There are various ways how we can load data from XML files in the Java language, each have cons and prons. Two common ways are DOM and SAX. What are these and why we're using one and not the other? The main difference between the two is that the DOM parser loads the XML file in a tree structure using DOM related classes. Once loaded, we can then create our structure from the DOM tree. On the other hand SAX parser does not load the XML but triggers a series of events thought which we can build our structure. SAX does not load anything into the memory.

The SAX parser

Before proceeding, let's first understand the SAXParser and the required elements. The SAX parser requires a handler to handle the events triggered by the same SAX parser. The handler is a java class that extends the DefaultHandler and provides implementation for some (or many) of the methods in the default handler. Note that the default handler implements a set of interfaces and provides a default implementation (methods doing nothing) for all inherited abstract methods.

SAX Parser

The SAX parser is created using the SAXParserFactory and the XML file is parsed using the provided handler (the default handler in this case) as illustrated in the following example:


import javax.xml.parsers.SAXParser;
import javax.xml.parsers.SAXParserFactory;
import org.xml.sax.helpers.DefaultHandler;

public class Example1 {
  public static void main(String[] args) throws Exception {
    DefaultHandler handler = new DefaultHandler();
    
    SAXParserFactory factory = SAXParserFactory.newInstance();
    SAXParser p = factory.newSAXParser();
    p.parse(Example1.class.getResourceAsStream("Test.xml"), 
            handler);
  }
}

Note that, here I'm using the default package for all examples and the Test.xml file is in the same folder as the class files. If you move the classes into a package make sure to also move the xml file with them or emend the file path accordingly.

Executing the above example will produce nothing as the default handler simply ignores all events triggered by the parser. The SAX parses starts parsing the file and for every tag opened and close it invokes specific methods in the handler and pass the information from the XML file. Let's create a simple handler and some basic methods to helps us understand this better. This handler will be used to load a list of students from the XML file define above (Test.xml).


import org.xml.sax.Attributes;
import org.xml.sax.SAXException;
import org.xml.sax.helpers.DefaultHandler;

public class StudentHandler1 extends DefaultHandler {

  @Override
  public void characters(char[] ch, int start, int length)
                         throws SAXException {
  }

  @Override
  public void endElement(String uri, String localName, 
                         String name) throws SAXException {
  }

  @Override
  public void startDocument() throws SAXException {
  }

  @Override
  public void startElement(String uri, String localName, 
                           String name,Attributes attributes) 
                           throws SAXException {
  }
}

The above class override four methods from the default handler class.

The startDocument method is invoked once when the SAX parser start parsing the XML document. This method has not parameters and can be used to initialise fields (similar to a constructor or initialising block). The default handler also includes the endDocument method which is invoked when the SAX parser is done parsing the file. This method can be used as a destructor method (or the final block) to clean up or wrap up and resources/fields as required.

The startElement method is invoked when the SAX parser encounters an XML tag. For example, this method is invoked when the SAX parser encounters an open tag such as: <students>. Similar, the endElement method is invoked by the parser when the close tag is found (for example: </students>).

Finally, the characters method is invoked when the parser encounters the tag body. The tag body is the text (not XML) within the tags. For example, the characters for the grade XML tag: <grade>85</grade>, is 85. Note that whitespaces are not removed or truncated and must be handled by the handler.

Simple example

Let's start with a simple example that counts the number of students in the XML file (Test.xml). All we need to do here is create an integer field, initialise it to 0 in the start document method and for every student tag we increment this variable. We removed the unnecessary method from the previous handler (StudentHandler1 ) and added the end document method.


import org.xml.sax.Attributes;
import org.xml.sax.SAXException;
import org.xml.sax.helpers.DefaultHandler;

public class StudentHandler2 extends DefaultHandler {

  private int studentsCount;

  @Override
  public void endDocument() throws SAXException {
    System.out.println(studentsCount);
  }

  @Override
  public void startDocument() throws SAXException {
    studentsCount = 0;
  }

  @Override
  public void startElement(String uri, String localName, 
                           String name, Attributes attributes) 
                           throws SAXException {
    if ("student".equalsIgnoreCase(name)) {
      studentsCount++; // Increment statement
    }
  }
}

Note that we enclosed the increment statement within the if statement. The if statement is checking the name of the XML tag. Note that our XML document has four different tags: students, student, class and grade. We only want to increment our counter when the student tag is opened. Also, the if statement is comparing the tag but ignoring case (case insensitive) as XML is not case sensitive and the tags may be in upper case.

Now, using the new handler (StudentHandler2), we can process our XML file (Test.xml) and see how many students we have.


import javax.xml.parsers.SAXParser;
import javax.xml.parsers.SAXParserFactory;

public class Example2 {
  public static void main(String[] args) throws Exception {
    StudentHandler2 handler = new StudentHandler2();

    SAXParserFactory factory = SAXParserFactory.newInstance();
    SAXParser p = factory.newSAXParser();
    p.parse(Example2.class.getResourceAsStream("Test.xml"), 
            handler);
  }
}

The above should produce 4 when executed against the Test.xml file.

As you can see, we didn’t loaded any data from the XML file into the memory. Instead we only performed the require operation (counting the number of student in this case). Using DOM here would be an overkill as all the students would have been loaded into the memory for nothing. We only required a count. I'm not saying that DOM is not good. All I'm saying is that DOM is not the right tool for this job.

Some XML processing

Let's improve our parser and calculate the average grade for all students. In order to calculate the average, we need to first calculate the sum and then divide by the number of students. This is not as simple as it sound as the SAX parser invokes the handler's methods independent from the tag. For example, the startElement method is invoked for every XML open tag. Same applies for all other handler methods. Thus we have to keep track which tag we're handling.

Let's understand this problem first. We need to get the contents between the grade's XML tag. This can be retrieved from the characters method. But this method is executed for every tag (as we established above). So we first need to see which tag is being processed from the start element method. Using a boolean field (referred to as addToTotal in the following example), we set this field to true when the start element method is invoked for the grade tag. Then, we only process characters when this field is set to true. We have to remember to set this field to false once the grade tag is processed. This can be done in the end element method. All this is captured in the following example. Note that changes are shown in bold.


import org.xml.sax.Attributes;
import org.xml.sax.SAXException;
import org.xml.sax.helpers.DefaultHandler;

public class StudentHandler3 extends DefaultHandler {

  private boolean addToTotal;
  private StringBuffer buffer;
  private int studentsCount;
  private int totalGrade;

  @Override
  public void characters(char[] ch, int start, int length)
      throws SAXException {
    if (addToTotal) {
      buffer.append(ch, start, length);
    }
  }

  @Override
  public void endDocument() throws SAXException {
    System.out.println(studentsCount);
    System.out.println(totalGrade * 1.0 / studentsCount);
  }

  @Override
  public void endElement(String uri, String localName, 
                         String name) throws SAXException {
    if ("grade".equalsIgnoreCase(name)) {
      addToTotal = false;
      totalGrade += Integer.parseInt(buffer.toString().trim());
    }
  }

  @Override
  public void startDocument() throws SAXException {
    studentsCount = 0;
    totalGrade = 0;
  }

  @Override
  public void startElement(String uri, String localName, 
                           String name, Attributes attributes) 
                           throws SAXException {
    if ("student".equalsIgnoreCase(name)) {
      studentsCount++;
    } else if ("grade".equalsIgnoreCase(name)) {
      addToTotal = true;
      buffer = new StringBuffer();
    }
  }
}

Why are we using a string buffer in the characters method? The XML tag body (where the grade value is) can be very long and spread across multiple lines. For example, we can have the following:


<grade>
65
</grade>

In this case, the character method will be invoked three times (one for every line). Initially, it will be called with the new-line UNICODE symbol (\n), then with the text 65, and finally with the other new-line UNICODE symbol. Thus we first need to accumulate all content (in this case: \n65\n) and then remove all leading and trailing whitespaces before parsing it into an integer. Note that our example will throw a NumberFormatException is the given grade is not an integer.

Handling XML attributes

The XML student tag also includes an attribute, the student name. We can get this value and from the start element method's Attributes parameter. The attribute parameter holds all attributes that belong to the tag being handled. The SAX parser takes care of populating the attributes when parsing the XML document.


import org.xml.sax.Attributes;
import org.xml.sax.SAXException;
import org.xml.sax.helpers.DefaultHandler;

public class StudentHandler4 extends DefaultHandler {

  @Override
  public void startElement(String uri, String localName, 
                           String name, Attributes attributes) 
                           throws SAXException {
    if ("student".equalsIgnoreCase(name)) {
      String studentName = attributes.getValue("name");
      System.out.println(studentName);
    }
  }
}

The above handler will list all student names one following another. We can enhance this handler and save all students and their grade in a list as illustrated below. Ideally, before we proceed we create a Java class that represents the student. In this case the class only requires two fields, that is, the name and the grade. Note that in our problem we're not handling the student's class XML tag (we're ignoring it).


public class Student1 {

  private int grade;
  private String name;

  // The getters and setters are omitted for brevity

  @Override
  public String toString() {
    return name + " " + grade;
  }
}

Putting it all together

Let's now combine everything together and build a list of student from the XML file. We need to change some of the fields and introduce new ones. For example, we need a list to put all the students in (listOfStudents) and we need a temporary variable to save the student until this is added into the list (student). No changes are highlighted in the following example as there are many changes.


import java.util.List;
import java.util.Vector;
import org.xml.sax.Attributes;
import org.xml.sax.SAXException;
import org.xml.sax.helpers.DefaultHandler;

public class StudentHandler5 extends DefaultHandler {

  private StringBuffer buffer;
  private boolean isStudentGrade;
  private List listOfStudents;
  private Student1 student;

  @Override
  public void characters(char[] ch, int start, int length)
      throws SAXException {
    if (isStudentGrade) {
      buffer.append(ch, start, length);
    }
  }

  @Override
  public void endDocument() throws SAXException {
    System.out.println(listOfStudents);
  }

  @Override
  public void endElement(String uri, String localName, 
                         String name) throws SAXException {
    if ("grade".equalsIgnoreCase(name)) {
      isStudentGrade = false;
      student.setGrade(
        Integer.parseInt(buffer.toString().trim()));
    } else if ("student".equalsIgnoreCase(name)) {
      listOfStudents.add(student);
      student = null;
    }
  }

  @Override
  public void startDocument() throws SAXException {
    listOfStudents = new Vector();
  }

  @Override
  public void startElement(String uri, String localName, 
                           String name, Attributes attributes) 
                           throws SAXException {
    if ("student".equalsIgnoreCase(name)) {
      String studentName = attributes.getValue("name");
      student = new Student1();
      student.setName(studentName);
    } else if ("grade".equalsIgnoreCase(name)) {
      isStudentGrade = true;
      buffer = new StringBuffer();
    }
  }
}

Why the student is added into the list when the student close tag is processed when we could do this at the grade close tag? The reason behind that is if in the future we also add more fields, such as the student's class, we can easily do so with minimal changes to the code.

Conclusion

In this article I covered how to use the SAX parse for simple processing of XML files. The SAX parser is ideal when we need to perform some processing such as count the number of students or calculate the average grade without having to load the entire XML file into the memory.

Saturday, 6 December 2008

Generate all combinations of chars

Generating all combinations of the characters is not a simple task and one must think before starting any coding. The problem size (example 4 represents all combinations between 'a' and 'ZZZZ') can vary and this makes the problem more complex to solve but simpler to program! There are various ways how to solve this problem. The solution discussed here describes how to convert an integer into a sequence of characters.

This article describes how to write a Java program which returns all combinations of characters for a given length. Note that even though this is a programming related article it requires a good knowledge of mathematics. The examples make use of logs and power of to carry out the calculations required.

An overview of the solution

The solution discussed here describes how to convert an integer into a sequence of characters. Let's have a simple example, the integer 0 is equivalent to ['a'], while integer 1 is equivalent to ['b'] and the integer 51 is equivalent to ['Z']. This is great for a problem of size one. What about a problem of size two? In this case 0 is still ['a'] and 1 is still ['b'] and 51 is still equivalent to ['Z']. Now 52 is (or should be) equivalent to ['a', 'a']. The array size has changed from one to two. The integer 53 is equivalent ['a', 'b'] and so on.

Not everything that shines is gold! Let's switch to numbers instead of characters for now so we appreciate the problem that this will lead us into. We have ten numbers, from 0 until 9. The leading 0s are usually ignored and are not used. This creates a problem for our solution as the 0 is representing the char 'a'. What I'm saying here? In numbers the value 00140 is equivalent to 140, but this is not the case with our solution as the combination: 'aabda' is not equivalent to 'bda'. To avoid this problem we have to build sets of combinations with unique size. Thus the value 0 for problem size 4 is 'aaaa' while the same value for a problem with size 7 will be: 'aaaaaaa'. This is covered mathematically below.

Let's start with the simplest version of the problem when the size is one, that is, all the characters available in the English alphabet.

Convert an int into a char

We need to provide map for all characters in the alphabet. The following function does so by returning the char 'a' for the integer 0 and the char 'z' for the int 25. The char 'A' is returned for the int 26 while the char 'Z' is returned for the int 51. Integer values outside the mentioned range (0 and 51 inclusive) will throw an illegal argument exception.


public static char getCharForInt(int i) 
                   throws IllegalArgumentException {
  if (i < 0 | i >= BASE) {
    throw new IllegalArgumentException(
              "Integer value out of range: " + i);
  }
  int length = (BASE) / 2;

  // Lower case char
  if (i < length) {
    return (char) (i + 'a');
  }
  // Upper case char
  return (char) (i - length + 'A');
}

This method is quite straight forward and simple to understand. This method returns just a single character which is only valid for a problem with size one. We need yet another method to generate an array of these. And that's what we're discussing next. Like here, this method will expect an integer and it will return the relative array of chars for the given integer. But before we proceed it's good to note that the method makes use of a constant named BASE which is declared at class level as illustrated below.


private static final int BASE = ('z' - 'a') + ('Z' - 'A') + 2;

Build an array of chars for a given int

If we can provide a map of chars to ints programmatically, then we can also provide a map between an integer (referred to as key in this method) to an array of chars in conjunctions with the previous method. How? Let's have a numerical example first. The number 143 (base 10) can be expressed as: 1 * 102 + 4 * 101 + 3 * 100. So to convert the number 14310 into the array of chars ['1', '4', '3'] we need to perform the following steps:


0) 143 / 102 = 1
1) 143 – (102*1) / 101
1) 143 – (100) / 101 = 4
2) 143 - ((102*1) + (101*4)) / 100
2) 143 - (140) / 100 = 3

Using the above approach we can convert the key integer value into an array of characters by changing the base from 10 to our base: 52. Before we can sing victory, we have to appreciate that this approach has a limitation. It will work well for the least significant character but it will miss one on the other characters. What am I saying? Let's have another example first:

Key Expression Value Expected Output
0 0 * 520 0 'a' 'a'
52 52 * 521
0 * 520
1
0
'aa' 'ba'

When dividing 52 by 52 we get 1, which is equivalent to 'b' not the answer we wanted! A simple way around this problem the solution and to reduce the number conditions we're going to make a small change to solution discussed before. We'll build sets of combinations with unique size. Thus the key value 0 for problem size 4 is ['a', 'a', 'a', 'a'] while the same value for a problem with size 7 will be: ['a', 'a', 'a', 'a', 'a', 'a', 'a'] .

This immediately provokes the following question, how are we going to generate all combinations? We can still obtain all combinations by first generating all combinations for size one and size two and so on.

With that out of the way, we can proceed in our adventure. The following code provides the algorithm used to generate all combination for a specific size.


private static char[] getCharsFormKey(int key, int size) {
  char[] chars = new char[size];
  for (int i = size - 1, j = 0; i >= 0; i--, j++) {
    // Get the divider for this character position
    int divider = (int) Math.pow(BASE, i);
    // Calculate the character index by dividing the 
    // key with the divider
    int c = key / divider;
    chars[j] = getCharForInt(c);
    // Deduct the processed numbers
    key -= (c * divider);
  }
  return chars;
}

Given a key integer and a size, this method returns the equivalent array of chars mapping the given key integer. Note that an illegal argument exception is thrown if the key integers requires a larger array that the specified size. This immediately brings us the following question: can we calculate the size automatically to fit the given key value? Yes and to do so we need to make use of the BigDecimal class to perform some calculations. We can determine the number of digits within a number by calculating the log to base 10 of that number incrementing it by one. In our case we have to calculate the log to base 52. There is not function ready which does that. But we can calculate the log of any base by using log to base 10 or ln as logn(X) is equivalent to log10(X) / log10(n).


private static char[] getCharsFormKey(int key) {
  int size = 1;
  if (key > 0) {
    BigDecimal keyDB = 
                 new BigDecimal(String.valueOf(Math.log(key)));
    size = (int) (keyDB.divide(
                   BASE_LOG_BD, RoundingMode.HALF_UP).doubleValue()
                  ) + 1;
  }
  return getCharsFormKey(key, size);
}

This method may be more attractive as it requires less parameters. The calculations involved here take some time and affect the performance. This method is mentioned for the sake of completeness and should be avoided if possible. This method makes use of a constant named BASE_LOG_BD which is declared at class level as illustrated below. Also note that the string version of the big decimal class is used as the double version is more prone to error as discussed at: http://www.opensourcestrategies.com/ofbiz/ofbiz_bigdecimal_cookbook.txt.


private static final BigDecimal BASE_LOG_BD = 
    new BigDecimal(String.valueOf(Math.log(52)));

Generating all combinations

To generate all combinations for a problem size 4, that is, generate all combinations starting from 'a' until 'ZZZZ'. We need two loops in order to achieve this: one to generate all combinations for a specific size or length, while the other to go through all sizes/lengths starting from 1 until the problem size, four in this case.


int size = 4;
for (int i = 1; i <= size; i++) {
  int maxKeyForSize = (int) Math.pow(BASE, i);
  for (int j = 0; j < maxKeyForSize; j++) {
    char[] chars = getCharsFormKey(j, i);
    String text = String.copyValueOf(chars);
    System.out.println(text);
  }
}

Conclusion

This article describes how to generate all combinations of characters for a given size using the mathematical functions ln and power of.

Friday, 14 November 2008

Sorting Objects using Comparator

Sorting is common functionality required by many applications. Questions like: How do we sort in Java? or What should we use as sorting algorithm? need to answered before we can perform any kind of sorting. Definitely we're not the first ones who require this feature and others have already done it before for us. So we can simple use the Java API provided to perform sorting.

The following article explains the concept of sorting and how to use the Java API to solve this problem and closes with some programming tips.

Concept behind sorting

In order to be able to sort elements we need to be able to compare them. What does this mean? If you have two things and you need to pick one of them, which one would you pick? Let's make this more realistic. If you're not rich and you can choose between €1 and €100, which one would you choose? I don't know what would you do, but I would go for the hundred. Why? Because 100 is greater than 1! I was able to make this decision because I was able to compare the choice at hand. If instead of numbers I said choose between A and B, where A and B can be anything, would you be able to do an informed decision? No, it would be pure gamble - a matter of luck. There is no way to compare A and B without further knowledge.

In order to be able to sort two elements (or more), you need to be able to compare them. Similar to the problem discussed above, we need to be able to evaluate elements and then sort them based on this value. For example, if we need to sort the following list: {8, 5, 9}, we know that 5 is less than 8 so these two have to be swapped. Sorting numbers is very simple and straight forward. We cannot say the same for any other object (Java and real). For example, if we have a list of boxes, how would we sort them? If we're sorting by size, we first determine the size of each and then using the size value (a number) as sorting criteria. So in order to sort any kind of object, all we need to do is to convert the object into a number that we can compare with. So if we have the following list of objects: {a, b, c, d} (the letters in the previous list is used only to define the object name and has no effect on the sorting) with sorting values {4, 3, 7, 5} respectively, we know that object b should come first while object c should be placed last and so on.

How do we implement this in Java?

Java provides a set of classes and interfaces which we can use to sort lists and arrays. Most of the following examples will use lists but the same concept can be applied for arrays. A final example will show this.

Let's start by creating a list of Integers and sort these using the Collections.sort method. The Collections class (part of the Java Collection Framework) provides a list of static methods which we can use when working with collections such as list, set and the like. So in a nutshell, we can sort a list by simply calling: java.util.Collections.sort(the list) as shown in the following example:


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Example1 {
  public static void main(String[] args) {
    List<Integer> ints = new ArrayList<Integer>();
    ints.add(4);
    ints.add(3);
    ints.add(7);
    ints.add(5);

    Collections.sort(ints);
    System.out.println(ints);
  }
}

The above class creates a list of four integers and, using the collection's sort method, sorts this list (in one line of code) without us having to worry about the sorting algorithm.

Java was able to sort this list because it knows how to compare integers as the Integer class implements the Comparable interface. Note that, as from Java 1.5, the primitive int value is autoboxed into an Integer (the object wrapper for int) before added to the list. Thus in order to be able to make use of the collection's sort method, all we need to do is implement the comparable interface by our objects.

Let's take this example one step further and create our own class. Let's create a list of students and sort them by their grade (which is a number). The student class will have two fields: name and grade. In order to be able to use the sort method from the collections class, as we did in the above example (Example1), we have to implement the comparable interface and its method, as illustrated below:


public class Student1 implements Comparable<Student1> {

  private int grade;
  private String name;

  public Student1(String name, int grade) {
    setName(name);
    setGrade(grade);
  }

  @Override
  public int compareTo(Student1 o) {
    return grade - o.grade;
  }

  @Override
  public String toString() {
    return name + " " + grade;
  }

  // Getters and setters are removed for brevity
} 

The compareTo method should return a negative integer, zero, or a positive integer if this student's grade is less than, equal to, or greater than the specified/given student's grade. The simplest way to do it is to subtract the grades of these students. Why and how would that help sorting? If this student's grade is larger than the grade of the given student, then a positive number is returned, while if the grades are equal, zero is returned. This follows the method's contract/specifications. Note that our job is to provide information to the sorting algorithm and not sorting the objects ourselves.

The toString method was overridden so that we can see readable results when we print the list. Otherwise the output will look something like: [Student1@19821f, Student1@addbf1, Student1@42e816, Student1@9304b1] (instead of: [Joe Vella 47, Paul Galea 52, Albert Attard 65, Mary Borg 93]) which is not readable.

Let's modify the previous class (Example 1) and sort a list of students.


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Example2 {
  public static void main(String[] args) {
    List<Student1> students = new ArrayList<Student1>();
    students.add(new Student1("Albert Attard", 65));
    students.add(new Student1("Mary Borg", 93));
    students.add(new Student1("Joe Vella", 47));
    students.add(new Student1("Paul Galea", 52));

    Collections.sort(students);
    System.out.println(students);
  }
}

Making full use of the API

How can we sort the student by both name and grade? In order to achieve this using the comparable interface (above) we have to add more fields to the student class in order to be able to determine which field we're sorting on. The following approach is not recommended and included here only for demonstration and comparisons purposes. Changes are shown in bold.


public class Student2 implements Comparable<Student2> {

  private int grade;
  private String name;
  private int sortBy;

  public Student2(String name, int grade, int sortBy) {
    setName(name);
    setGrade(grade);
    setSortBy(sortBy);
  }

  @Override
  public int compareTo(Student2 o) {
    switch (sortBy) {
    case 1: // Sort by name
      return name.compareTo(o.name);
    default: // Sort by grade by default
      return grade - o.grade;
    }
  }

  // Getters, setters and toString method are removed for 
  // brevity
}

We had to add a new field in the student class, called sortBy, which we have to set to 1 in order to sort the students by their name. Any other value will sort the students by their grade as illustrated in the following example. Ideally we use enums instead of int as the data type of the sortBy field which will prevent illegal values. Changes are shown in bold.


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Example3 {
  public static void main(String[] args) {
    List<Student2> students = new ArrayList<Student2>();
    students.add(new Student2("Albert Attard", 65, 1));
    students.add(new Student2("Mary Borg", 93, 1));
    students.add(new Student2("Joe Vella", 47, 1));
    students.add(new Student2("Paul Galea", 52, 1));
    
    // Sort by name
    Collections.sort(students);
    System.out.println(students);
    
    // Change these to sort them by grade
    for(Student2 student:students){
      student.setSortBy(0);
    }
    Collections.sort(students);
    System.out.println(students);
  }
}

This approach has two main pitfalls. First, the student class has to include fields and methods that are not related to the student object. Sorting properties are not student properties. The other issue is that for any new fields or sorting order we have to change the student class and emend the compareTo method accordingly, adding complexity to a method making it harder to maintain. Also, the sorting method is bound with the student class and cannot be used alone (apart from the object). The sorting state are saved with the object's state which is not what we want. For every student we have an instance of the sortby field, which we cannot make static. Why? If we have two lists, one to be sorted by name and the other by grade, then the static value will be shared by all instance of student and may effect the sorting outcome.

Java provides another way to compare objects. Instead of implementing the comparable interface (Student2), we can implement the Comparator interface. What's the difference? The main difference between these two interfaces is that the comparable interface defines one method compareTo, which takes one parameter. This parameter is compared with this object (the instance of student). In other words, the student object has a method which makes it able to compare to another student. On the other hand, the comparator interface defines one method (in reality two, but we're not interested from the second one) that takes two parameters (of the same type) and returns the comparison of these two objects (an int exactly the same as the method compareTo from the comparable interface). As such, the comparator allows us to remove the unnecessary fields and methods from the student class and move these elsewhere as illustrated below.

With reference to the Student1 class defined above.


import java.util.Comparator;

public class StudentGradeComparator1 implements Comparator<Student1> {

  @Override
  public int compare(Student1 a, Student1 b) {
    return a.getGrade() - b.getGrade();
  }
}

How can we use this? The collections class has an overloaded version of the sort method (http://java.sun.com/javase/6/docs/api/java/util/Collections.html#sort(java.util.List, java.util.Comparator)). The overloaded version accepts two parameters: the list to be sorted and an instance of comparator. The comparator outcome will be used by the sorting algorithm to determine the elements' magnitude and relation. Changes from the previous examples, are shown in bold.


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Example4 {
  public static void main(String[] args) {
    List<Student1> students = new ArrayList<Student1>();
    students.add(new Student1("Albert Attard", 65));
    students.add(new Student1("Mary Borg", 93));
    students.add(new Student1("Joe Vella", 47));
    students.add(new Student1("Paul Galea", 52));

    Collections.sort(students, new StudentGradeComparator1());
    System.out.println(students);
  }
}

How can we sort by name? We can create another class that implements comparator and compare the student class as required. All we need to do is replace the compare method as shown below.


  @Override
  public int compare(Student1 a, Student1 b) {
    return a.getName().compareTo(b.getName());
  }

Making the difference

Let's analyse the StudentGradeComparator1 class created above. This class has no fields, thus we can say that this class is stateless. Do we need to create more than one instance of this class? No. We don't need to have more than one instance of this class as the fields of this class (that are none) never change. So we can have one instance a always use it. This is referred to the singleton pattern. In simple terms, this pattern prevents the user to create more than one instance of this object. For more information about this, please refer to: http://java.sun.com/developer/JDCTechTips/2006/tt0113.html article. Why should we have it? Every object created consumes memory. Since our class (StudentGradeComparator1) is stateless, there is no need to enable/allow the user to create hundreds or thousands instance of this class as these will be identical. Changes are shown in bold.


import java.util.Comparator;

public class StudentGradeComparator2 implements Comparator<Student1> {

  private static final StudentGradeComparator2 instance = 
      new StudentGradeComparator2();

  public static StudentGradeComparator2 getInstance() {
    return instance;
  }

  private StudentGradeComparator2() {
  }

  @Override
  public int compare(Student1 a, Student1 b) {
    return a.getGrade() - b.getGrade();
  }
}

This got more complex, but in reality it got simpler. The student class only contain code related to the student, while the sorting classes contain the code required by the comparator. This means that each class is doing only thing.

How can we use it? Instead of creating an instance of the comparator, we call the get instance method: Collections.sort(students, StudentGradeComparator2.getInstance()) as shown in bold below:


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Example5 {
  public static void main(String[] args) {
    List students = new ArrayList();
    students.add(new Student1("Albert Attard", 65));
    students.add(new Student1("Mary Borg", 93));
    students.add(new Student1("Joe Vella", 47));
    students.add(new Student1("Paul Galea", 52));

    Collections.sort(students, 
        StudentGradeComparator2.getInstance());
    System.out.println(students);
  }
}

How can we sort the students by their grade but in descending order? Taking this another level, we can have two instances of the comparator class (not singleton anymore): one to sort ascending and the other descending. Here we're extending the singleton concept to prevent the user from freely creating instances. We can remove the get instance method and allow access to the static fields as shown below. Since, the class is radically changed, no changes are highlighted.


import java.util.Comparator;

public class StudentGradeComparator3 implements Comparator {

  public static final StudentGradeComparator3 ASC = 
      new StudentGradeComparator3(1);

  public static final StudentGradeComparator3 DESC = 
      new StudentGradeComparator3(-1);

  private final int order;

  private StudentGradeComparator3(int order) {
    this.order = order;
  }

  @Override
  public int compare(Student1 a, Student1 b) {
    return order * (a.getGrade() - b.getGrade());
  }
}

Here we removed the get instance method and included two instances ASC and DESC. We added an integer (named order) with values 1 or -1 which is used to switch the sorting polarity. Note that when a number is multiplied by a negative number, its sign (negative or positive) is changed. Changing the sign will change the sorting order. This field is constant (not static) and is set through the solo private constructor by the two static fields.


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Example6 {
  public static void main(String[] args) {
    List<Student1> students = new ArrayList<Student1>();
    students.add(new Student1("Albert Attard", 65));
    students.add(new Student1("Mary Borg", 93));
    students.add(new Student1("Joe Vella", 47));
    students.add(new Student1("Paul Galea", 52));

    Collections.sort(students, StudentGradeComparator3.ASC);
    System.out.println(students);

    Collections.sort(students, StudentGradeComparator3.DESC);
    System.out.println(students);
  }
}

Arrays

We can easily adopt the above example for arrays. Instead of using collection's sort method we use the array's version (http://java.sun.com/javase/6/docs/api/java/util/Arrays.html#sort(T[], java.util.Comparator)).


import java.util.Arrays;

public class Example7 {
  public static void main(String[] args) {
    Student1[] students = { new Student1("Albert Attard", 65),
        new Student1("Mary Borg", 93), 
        new Student1("Joe Vella", 47),
        new Student1("Paul Galea", 52) };

    Arrays.sort(students, StudentGradeComparator3.ASC);
    System.out.println(students);
  }
}

The same comparator is used to sort the array of students.

Conclusion

This article discusses how to perform sorting without having to worry about the sorting algorithm. From the collections Java doc:

"...the sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. The specified list must be modifiable, but need not be resizable. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place...

One thing to take away from this article is don't reinvent the wheel. Before implementing something, have a look around as most probably others did it before you