At work we are working on a project that involves pushing out correspondence to students.  This necessitates sorting by multiple factors, including name, homeroom, etc.  This is trivial when using SQL ORDER BY, but I already had all the information I needed in the business objects, so I really needed to implement a mult-field sort in Java.

The algorithm works off of the same principals as ORDER BY.  A list of field names and objects are passed in and then the objects are hierarchically (i.e. recursively) sorted using reflection and each of the field names passed in.  It’s pretty sweet in that the field list can be arbitrarily deep and it is not tied to a specific object type.

As I was trying to solve a specific problem, there are several limitations:

• I’m not sure the performance is great — I am using the TreeMap object to do the sorting (basically a sort of insertion sort…) so hopefully that helps a bit.
• The algorithm assumes fields are parseable using String.valueOf because it is geared mainly towards simple fields of type String, int, etc.
• There is no ability to control order.  Items are sorted in terms of default String rules (i.e. ASCIIbetically ascending).

OK, here’s the code:

/**
 * 
 */
package util;

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * This class supports sorting Objects hierarchically using multiple fields.
 * @author travismiller
 *
 */
public class ListMultiSorter<T> {
	protected T t;
	
	/**
	 * 
	 * @param t
	 * 		Instance of T used for reflection purposes
	 */
	public ListMultiSorter(T t){
		//ugly freaking hack - bloody compiler...
		this.t = t;
	}
	
	/**
	 * This method recursively / hierarchically sorts <code>objs</code> using each of the<code>fields</code>.
	 * It is basically an analogue of the SQL ORDER BY syntax
	 * TODO: 	1. this currently only sorts ascending based on string sorting - may need to evolve as needs change
	 * 			2. Natural number String comparator? http://www.davekoelle.com/alphanum.html
	 * @param fields
	 * 			Ordered list of field names to be sorted by
	 * @param objs
	 * 			Objects to be inspected and sorted
	 * @return
	 * 			Sorted objects
	 * @throws SecurityException
	 * @throws NoSuchFieldException
	 * @throws IllegalArgumentException
	 * @throws IllegalAccessException
	 */
	public List<T> sort(List<String> fields, List<T> objs) throws SecurityException, NoSuchFieldException, IllegalArgumentException, IllegalAccessException {
		LinkedList<T> retList = new LinkedList<T>();
		
		if(objs.size() <= 1) {
			return objs;
		}
		else {
			Field f = t.getClass().getField(fields.get(0));
			TreeMap<String, LinkedList<T>> sortList = new TreeMap<String, LinkedList<T>>();
			for(T obj: objs) {
				String key = String.valueOf(f.get(obj));
				
				//Push onto correct key bucket
				if(sortList.get(key) == null) {
					LinkedList<T> list = new LinkedList<T>();
					list.add(obj);
					sortList.put(key, list);
				}
				else {
					sortList.get(key).add(obj);
				}
			}
			if(fields.size() > 0) {
				ArrayList<String> newFields = new ArrayList<String>(fields);
				newFields.remove(0);
				
				//Sort each bucket on next field
				Iterator<Map.Entry<String, LinkedList<T>>> it = sortList.entrySet().iterator();
				while(it.hasNext()) {
					retList.addAll(sort(newFields, it.next().getValue()));
				}
			}
			return retList;
		}
	}
}



Written on December 22nd, 2011 , Java, Tech