Null and 3-Dimensional Ordering Helpers in Java

When dealing with data sets retrieved from a database, if we want them ordered, we usually will want to order them right in the SQL, rather than order them after retrieval. Our database will typically be more efficient due to available processing power, potential use of available indexes and overall algorithm efficiency in modern RDBMSes. You also have great flexibility to have complex ordering criteria when you use these ORDER BY clauses. For example, assume you had a query that retrieved employee information including salary and relative steps (position) from the top position. You could easily have a first-level ordering where salaries are grouped into categories (<= $50 000, $50 001 to $100 000, > $100 001), and the next level ordered by relative position. If you could assume that salaries were appropriate for all employees, this might give you a nice idea of where there is too much or too little management in the company – a very rough approach I wouldn’t recommend, this is just a sample usage.

You get some free behaviour from your database when it comes to ordering, whether you realize it or not. When dealing with NULLs, the database has to make a decision how to order them. Every database I’ve ever worked with and likely all relational databases have a default behaviour. In ascending order, MySQL and SQL Server put NULL ahead of real values, they are “less than” a non-NULL value. Oracle and Postgres put NULL after real values, they are “greater than” non-NULL values. Oracle and Postgres nicely give you the NULLS FIRST and NULLS LAST instructions so you can actually override the defaults. Even in MySQL and SQLServer, you can find ways to override the defaults using functions in your order by clause. In MySQL I use IFNULL. In SQL Server, you could use ISNULL. These both give you the option of replacing null with a particular value. Just replace an appropriate value for the type you are sorting.

All sorting supported in these types of queries is two-dimensional. You pick columns and the rows are ordered by those. When you need to sort by additional dimensions of the data, you’re probably getting into areas that are addressed in other related technologies such as data warehousing and OLAP cubes. If that is appropriate and available for your case, by all means use those powerful features.

In many cases though, we either don’t have access to those technologies or we need our operations to be on current data. For example, let’s say you are working on an investment system, investor’s accounts, trades, positions, etc. are all maintained. You need to write a query to help extract trade activity for a given time frame. Our data comes back as a two-dimensional datasets even though we have more dimensions. Our query will return data on account(s) and the trade(s) per account. We need our results to be ordered by those accounts whose effected trades have the highest value. But we need to maintain the trades with their accounts. Simply ordering our query by the value of the effected trade would likely break the rows of the same account apart.

We have a choice, we can either order in the database and control our reconstruction of returning data to maintain the state and order of reconstructed objects or we can sort after the fact. In most cases, we probably don’t want to write new code each time we come across this problem that deals specifically with reconstituting the data from that query into our object model’s representation. Hopefully our ORM will help or we have some preexisting, functional and well-tested code that we can reuse to do so.

Another option is to sort in our code. We actually get lots of flexibility by doing this. Perhaps we have some financial functions that are written in our application that we can now use. We also don’t have to do all the sorting ourselves as we can take advantage of JDK features for Comparator and Collection sorting.

First, let’s deal with our null ordering problem. Let’s say our Trade object has some free public constant Comparators. These allow us to use a collection of Trades along with java.util.Collections.sort(List<Trade>, Comparator<Trade>). Trade.TRADE_VALUE_NULL_FIRST is the one we want to use. This Comparator is nothing more than a passthrough to a global Null Comparator helper.

private static final Comparator<Trade> TRADE_VALUE_NULL_FIRST = new Comparator<Trade>(){
  public int compare(Trade o1, Trade o2) {
    return ComparatorUtil.DECIMAL_NULL_FIRST_COMPARATOR.compare(
        o1.getTradeValue(), 
        o2.getTradeValue());
}};

... ComparatorUtil ...

public static NullFirstComparator<BigDecimal> DECIMAL_NULL_FIRST_COMPARATOR = 
  new NullFirstComparator<BigDecimal>();
public static NullLastComparator<BigDecimal> DECIMAL_NULL_LAST_COMPARATOR = 
  new NullLastComparator<BigDecimal>();
...snip...
public static NullLastComparator<String> STRING_NULL_LAST_COMPARATOR = 
  new NullLastComparator<String>();

public static class NullFirstComparator<T extends Comparable<T>> implements Comparator<T> {
  public int compare(T o1, T o2) {
    if (o1 == null && o2 == null) {
	return 0;
    } else if (o1 == null) {
	return -1;
    } else if (o2 == null) {
	return 1;
    } else {
	return o1.compareTo(o2);
    }
  }
}
public static class NullLastComparator<T extends Comparable<T>> implements Comparator<T> {
  public int compare(T o1, T o2) {
    if (o1 == null && o2 == null) {
	return 0;
    } else if (o1 == null) {
	return 1;
    } else if (o2 == null) {
	return -1;
    } else {
	return o1.compareTo(o2);
    }
  }
}

Now we have a simple, reusable solution we can use with any class and any nullable value in JDK sorting. Now we expose any ordering constants appropriate for business usage in our class. Now let’s deal with the more complex issue of hierarchical value ordering. We don’t want to write new code everytime we have to do something like this. So let’s just extend our idea of ordering helpers to hiearchical entities.

public interface Parent<C> {
  public List<C> getChildren();
}
public class ParentChildPropertiesComparator<P extends Parent<C>, C> implements Comparator<P> {
  private List<Comparator<C>> mChildComparators;
  public ParentChildPropertiesComparator(List<Comparator<C>> childComparators) {
    mChildComparators = Collections.unmodifiableList(childComparators);
  }
  public List<Comparator<C>> getChildComparators() {
    return mChildComparators;
  }
  public int compare(P o1, P o2) {
    int compareTo = 0;
    for (int i=0; i < mChildComparators.size() && compareTo == 0; i++) {
	Comparator<C> cc = mChildComparators.get(i);
	List<C> children1 = o1.getChildren();
	List<C> children2 = o2.getChildren();
	Collections.sort(children1, cc);
	Collections.sort(children2, cc);
	int max = Math.min(children1.size(), children2.size());
	for (int j=0; j < max && compareTo == 0; j++) {
	  compareTo = cc.compare(children1.get(j), children2.get(j));
	}
    }
    return compareTo;
  }
}

This is a little more complex, but still simple enough to easily grasp and reuse. We have the idea of a parent. This is not an OO relationship. This is a relationship of composition or aggregation. A parent can exist anywhere in the hierarchy, meaning a parent can also be a child. But in our sample, we have a simple parent/child relationship - Account/Trade. This new class, ParentChildPropertiesComparator supports the idea of taking in a List of ordered Comparators on the children entities but sorting on the parents. In our scenario, we are only sorting on one child value, but it could easily be several just as you could sort more than 2 levels of data.

We are assuming in our case that Account already implements the Parent interface for accounts. If not, you can always use the Adapter Design Pattern. Our Account/Trade sorting would now look like this.

List<Account> accounts = fetchPreviousMonthsTradeActivityByAccount();
List<Comparator<Trade>> comparators = Arrays.asList(Trade.TRADE_VALUE_NULL_FIRST);
ParentChildPropertiesComparator<Account, Trade> childComparator = 
  new ParentChildPropertiesComparator<Account, Trade>(comparators);
Collections.sort(accounts, childComparator);

Really! That's it. Our annoying problem of sorting accounts by those with highest trade values where some of those trade values could be null is solved in just a few lines of code. Our accounts are now sorted as desired. I came up with this approach and it is used successfully as a part of a query builder for a large-volume financial reconciliation system. Introduction of new sortable types and values requires only minimal additions. Take this approach for a whirl and see how incredibly powerful it is for dealing with sorting requirements across complex hierarchies of data. And drop us a line if you need help in implementation or have any comments.

Computing Common and Unique Elements In Multiple Collections – Java

This week, we’ll take a break from higher level problems and technology posts to deal with just a little code problem that a lot of us have probably faced. It’s nothing fancy or too hard, but it may save one of you 15 minutes someday, and occasionally it’s nice to get back to basics.

So let’s get down to it. On occasion, you’ll find you need to determine which elements in one collection exist in another, which are common, and/or which don’t exist in another collection. Apache Commons Collections has some some utility methods in CollectionUtils that are useful, notably intersection(), but this post goes a bit beyond that into calculating unique elements in collection of collections, and it’s always nice to get down to the details. We’ll also make the solution more generic by supporting any number of collections to operate against, rather than just two collections as CollectionUtils does. Plus there’s the fact that not all of us choose to or are able to include libraries just to get a couple useful utility methods.

When dealing with just two collections, it’s not a difficult problem, but not all developers are familiar with all the methods that java.util.Collection defines, so here is some sample code. They key is using the retainAll and removeAll methods together to build up the three sets – common, present in collection A only, and present in B only.

Set<String> a = new HashSet<String>();
a.add("a");
a.add("a2");
a.add("common");

Set<String> b = new HashSet<String>();
b.add("b");
b.add("b2");
b.add("common");

Set<String> inAOnly = new HashSet<String>(a);
inAOnly.removeAll(b);
System.out.println("A Only: " + inAOnly );

Set<String> inBOnly = new HashSet<String>(b);
inBOnly .removeAll(a);
System.out.println("B Only: " + inBOnly );

Set<String> common = new HashSet<String>(a);
common.retainAll(b);
System.out.println("Common: " + common);

Output:

A Only: [a, a2]
B Only: [b, b2]
Common: [common1]

Handling Three or More Collections

The problem is a bit more tricky when dealing with more than two collections, but it can be solved in a generic way fairly simply, as shown below:

Computing Common Elements
Computing common elements is easy, and this code will perform consistently even with a large number of collections.

   
public static void main(String[] args) {
   List<String> a = Arrays.asList("a", "b", "c");
   List<String> b = Arrays.asList("a", "b", "c", "d");   
   List<String> c = Arrays.asList("d", "e", "f", "g");
    
   List<List<String>> lists = new ArrayList<List<String>>();
   lists.add(a);
   System.out.println("Common in A: " + getCommonElements(lists));
   
   lists.add(b);
   System.out.println("Common in A & B: " + getCommonElements(lists));
   
   lists.add(c);
   System.out.println("Common in A & B & C: " + getCommonElements(lists));
   
   lists.remove(a);
   System.out.println("Common in B & C: " + getCommonElements(lists));
}
    
    
public static <T> Set<T> getCommonElements(Collection<? extends Collection<T>> collections) {

    Set<T> common = new LinkedHashSet<T>();
    if (!collections.isEmpty()) {
       Iterator<? extends Collection<T>> iterator = collections.iterator();
       common.addAll(iterator.next());
       while (iterator.hasNext()) {
          common.retainAll(iterator.next());
       }
    }
    return common;
}

Output:

Common in A: [a, b, c]
Common in A & B: [a, b, c]
Common in A & B & C: []
Common in B & C: [d]

Computing Unique Elements
Computing unique elements is just about as straightforward as computing common elements. Note that this code’s performance will degrade as you add a large number of collections, though in most practical cases it won’t matter. I presume there are ways this could be optimized, but since I haven’t had the problem, I’ve not bothered tryin. As Knuth famously said, “We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil”.

   
public static void main(String[] args) {
   List<String> a = Arrays.asList("a", "b", "c");
   List<String> b = Arrays.asList("a", "b", "c", "d");   
   List<String> c = Arrays.asList("d", "e", "f", "g");
    
   List<List<String>> lists = new ArrayList<List<String>>();
   lists.add(a);
   System.out.println("Unique in A: " + getUniqueElements(lists));
   
   lists.add(b);
   System.out.println("Unique in A & B: " + getUniqueElements(lists));
   
   lists.add(c);
   System.out.println("Unique in A & B & C: " + getUniqueElements(lists));
   
   lists.remove(a);
   System.out.println("Unique in B & C: " + getUniqueElements(lists));
}
    
    
public static <T> List<Set<T>> getUniqueElements(Collection<? extends Collection<T>> collections) {
    
    List<Set<T>> allUniqueSets = new ArrayList<Set<T>>();
    for (Collection<T> collection : collections) {
       Set<T> unique = new LinkedHashSet<T>(collection);
       allUniqueSets.add(unique);
       for (Collection<T> otherCollection : collections) {
          if (collection != otherCollection) {
             unique.removeAll(otherCollection);
          }
       }
   }
       
    return allUniqueSets;
}

Output:

Unique in A: [[a, b, c]]
Unique in A & B: [[], [d]]
Unique in A & B & C: [[], [], [e, f, g]]
Unique in B & C: [[a, b, c], [e, f, g]]

That’s all there is to it. Feel free to use this code for whatever you like, and if you have any improvements or additions to suggest, leave a comment. Developers all benefit when we share knowledge and experience.