8
\$\begingroup\$

I've seen a number of questions on Stack Overflow of the kind of "How do I sort on fields X AND Y?" The most common answers to those questions consists of "Write a custom Comparator."

But what if you have 3 fields you can sort on? Or 13? or 300? My solution is this utility class, so that rather than writing a billion different Comparators for every possible combination you might want, you write just 3 (or 13, etc.) simple ones and essentially composite them to get the desired behavior.

This method is designed to be used as essentially an expanded version of Collections.sort(List list, Comparator c) so I want to adhere to the same contract as much as possible.

I am also interested in ways to improve the documentation/API and finding possibly troublesome corner cases.

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

/**
 * A utility class for sorting a list using multiple sorting criteria.
 *
 */
public class Multisorter {
    /**
     * Sorts the given List using the given Comparators.
     * 
     * The List is sorted by the Comparators in the order the Comparators are
     * given; the elements are sorted according to the first Comparator, then
     * all of the elements that are considered "equal" are subsorted recursively
     * by the next Comparator and so on.
     * 
     * This method makes use of Collections.sort(List<T>, Comparator<T>)
     * internally and obeys the same contract.
     * 
     * @param <T>
     *            the generic type of the list.
     * 
     * @param list
     *            the List to sort
     * @param comparators
     *            the comparators to sort with
     * @return the sorted List
     */
    public static <T> void sort(List<T> list, Comparator<? super T>... comparators) {
        if (comparators.length <= 0) {
            throw new IllegalArgumentException("Must provide at least one Comparator to sort with.");
        }
        Collections.sort(list, comparators[0]);
        if (comparators.length > 1) {
            List<List<T>> subCollections = new ArrayList<>();
            for (T element : list) {
                boolean matchFound = false;
                for (List<T> subList : subCollections) {
                    if (comparators[0].compare(element, subList.get(0)) == 0) {
                        subList.add(element);
                        matchFound = true;
                    }
                    if (matchFound) {
                        break;
                    }
                }
                if (!matchFound) {
                    int lastIndex = subCollections.size();
                    subCollections.add(lastIndex, new ArrayList<>());
                    subCollections.get(lastIndex).add(element);
                }
            }

            // Sort each of the subcollections recursively without the first Comparator
            for (List<T> subList : subCollections) {
                sort(subList, Arrays.copyOfRange(comparators, 1, comparators.length));
            }
            // Aggregate all the subcollections
            list.clear();
            for (List<T> subList : subCollections) {
                list.addAll(subList);
            }
        }
    }
}

However, based on comments by Alnitak and rolfl, I would just use the new thenComparing method in Comparator added in Java 8 that I didn't know about.

\$\endgroup\$
  • 1
    \$\begingroup\$ Did you see the new Java 8 model for doing this? \$\endgroup\$ – Alnitak Dec 24 '14 at 12:25
6
\$\begingroup\$

I find your code fairly complicated. Especially the part where you split the list into sequences of sublists of equal elements is a bit convoluted. Here's what you're doing in pseudocode:

given a comparator,
for each element in the list:
    for each sublist:
       if per the comparator, the element is equal to an element in that sublist:
           add the element to the sublist,
           continue with next element
    if no sublist matched:
        add a new sublist containing that element

The most straightforward way to implement that in Java is using a labeled loop. Using that, we can continue with the next element in the outer loop once a match was found. We do not have to maintain a matchFound variable:

List<List<T>> subCollections = new ArrayList<>();

element:
for (T element : list) {
    for (List<T> subList : subCollections) {
        if (comparators[0].compare(element, subList.get(0)) == 0) {
            subList.add(element);
            continue element;
        }
    }
    // no sublist matched
    List<T> newList = new ArrayList<>();
    newList.add(element);
    subCollections.add(newList);
}

There's also no need to use a lastIndex here.

Unfortunately, what you are doing is tremendously inefficient. You re-sort each list multiple times, and invoke each comparator unnecessarily often. You are more or less implementing a crazy inefficient multi-level quicksort that partitions into multiple parts per level.

The better solution would be to create a custom comparator that loops through the list of comparators and stops when they are no longer equal:

class MultiComparator<T> implements Comparator<T> {
    private final List<Comparator<T>> comparators;

    public MultiComparator(List<Comparator<? super T>> comparators) {
        this.comparators = comparators;
    }

    public MultiComparator(Comparator<? super T>... comparators) {
        this(Arrays.asList(comparators));
    }

    public int compare(T o1, T o2) {
        for (Comparator<T> c : comparators) {
            int result = c.compare(o1, o2);
            if (result != 0) {
                return result;
            }
        }
        return 0;
    }

    public static <T> void sort(List<T> list, Comparator<? super T>... comparators) {
        Collections.sort(list, new MultiComparator<T>(comparators));
    }
}

(untested)

\$\endgroup\$
  • \$\begingroup\$ A special "aggregate" Comparator is a good idea. I'll test it to see if it gives the same results as my implementation. \$\endgroup\$ – ThisIsNoZaku Dec 24 '14 at 13:34
  • 1
    \$\begingroup\$ +1 for a good answer +2 if I could for the MultiComparator if I could, but ... seen: thenCOmparing(...) in Java8, which allows you to do this using the Java util library ;-) \$\endgroup\$ – rolfl Dec 24 '14 at 14:04
  • 1
    \$\begingroup\$ For a list of approaches to sorting on multiple fields, this might be of interesting to you over at SO: Collections.sort with multiple fields \$\endgroup\$ – Benny Bottema Nov 16 '15 at 14:37
  • \$\begingroup\$ Apache's Commons Collections has this built in btw: ComparatorUtils.chainedComparator(comparatorList) \$\endgroup\$ – Benny Bottema Nov 16 '15 at 14:42
  • \$\begingroup\$ @Plantface thanks for that link. I'm not a regular Java user so I tend to reinvent the wheel quite often – unnecessarily, as it seems. \$\endgroup\$ – amon Nov 16 '15 at 14:44
3
\$\begingroup\$
  • Instead of checking for (comperators.length > 1) you can check for == 1 and use it as a guard condition. In this way you are saving horizontal space.

    if (comparators.length == 1) {
        return ;
    }  
    
  • you have boilerplate code in your inner loop. You first set matchFound = true and then breakif matchFound == true.

    for (List<T> subList : subCollections) {
        if (comparators[0].compare(element, subList.get(0)) == 0) {
            subList.add(element);
            break;
        }
    }  
    
  • you are iterating over subCollections but name the items subList this seems strange IMHO.

  • instead of clearing the list at the end and then adding the items of the subCollections you should consider to change the return type from void to List<T>.

\$\endgroup\$
  • \$\begingroup\$ The first two items are good points, I'll fix those up. The third is a result of some incomplete refactoring. The reason for #4 is to adhere more closely to the functionality of the existing sort method in Collections, which is a void return method. \$\endgroup\$ – ThisIsNoZaku Dec 24 '14 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.