Number aware string sorting with comparator

Question

I have this class for use in sorting strings such that if strings have a number in the same position it will order the numbers in increasing order.

Alphabetical gives:

• file1
• file10
• file2

What I'm calling "number aware" string sorting should give:

• file1
• file2
• file10

Here is what I have using a regex split from there.

The code seems to work. Any cases where I could run into problem? If not any suggestions on making it simpler or more efficient.

import java.util.Comparator;

public class NumberAwareStringComparator implements Comparator<String>{
     public int compare(String s1, String s2) {

            String[] s1Parts = s1.split("(?<=\\D)(?=\\d)|(?<=\\d)(?=\\D)");
            String[] s2Parts = s2.split("(?<=\\D)(?=\\d)|(?<=\\d)(?=\\D)");

            int i = 0;
            while(i < s1Parts.length && i < s2Parts.length){

                //if parts are the same
                if(s1Parts[i].compareTo(s2Parts[i]) == 0){
                    ++i;
                }else{
                    try{

                        int intS1 = Integer.parseInt(s1Parts[i]);
                        int intS2 = Integer.parseInt(s2Parts[i]);

                        //if the parse works

                        int diff = intS1 - intS2; 
                        if(diff == 0){
                            ++i;
                        }else{
                            return diff;
                        }
                    }catch(Exception ex){
                        return s1.compareTo(s2);
                    }
                }//end else
            }//end while

            //Handle if one string is a prefix of the other.
            // nothing comes before something.
            if(s1.length() < s2.length()){
                return -1;
            }else if(s1.length() > s2.length()){
                return 1;
            }else{
                return 0;
            }
        }
}

Answer 1

Exceptions should be reserved for exceptional situations, and should be avoided if possible. The fundamental reason you have to deal with NumberFormatException is that after splitting, you don't know whether each part contains a number or a non-number.

Here's a strategy that always compares non-digits to non-digits, and numbers to numbers.

import java.math.BigInteger;
import java.util.Comparator;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class NumberAwareStringComparator implements Comparator<CharSequence> {
    public static final NumberAwareStringComparator INSTANCE =
        new NumberAwareStringComparator();

    private static final Pattern PATTERN = Pattern.compile("(\\D*)(\\d*)");

    private NumberAwareStringComparator() {
    }

    public int compare(CharSequence s1, CharSequence s2) {
        Matcher m1 = PATTERN.matcher(s1);
        Matcher m2 = PATTERN.matcher(s2);

        // The only way find() could fail is at the end of a string
        while (m1.find() && m2.find()) {
            // matcher.group(1) fetches any non-digits captured by the
            // first parentheses in PATTERN.
            int nonDigitCompare = m1.group(1).compareTo(m2.group(1));
            if (0 != nonDigitCompare) {
                return nonDigitCompare;
            }

            // matcher.group(2) fetches any digits captured by the
            // second parentheses in PATTERN.
            if (m1.group(2).isEmpty()) {
                return m2.group(2).isEmpty() ? 0 : -1;
            } else if (m2.group(2).isEmpty()) {
                return +1;
            }

            BigInteger n1 = new BigInteger(m1.group(2));
            BigInteger n2 = new BigInteger(m2.group(2));
            int numberCompare = n1.compareTo(n2);
            if (0 != numberCompare) {
                return numberCompare;
            }
        }

        // Handle if one string is a prefix of the other.
        // Nothing comes before something.
        return m1.hitEnd() && m2.hitEnd() ? 0 :
               m1.hitEnd()                ? -1 : +1;
    }
}

Since strings of digits (such as those representing dates, like 20131212123456.log) can overflow an int, I've used java.math.BigInteger.

Also, since the code works just as well with CharSequence as with String, I've generalized the type to Comparator<CharSequence>.

Answer 2

In general, I think this solutions is doing the right thing, and the algorithm, in a broad sense is doing it the right way.

There are two specific areas where I think it can be improved:

1. Regular Expressions can be compiled and reused. This compareTo method is splitting many, many strings, and it would make a big difference to reuse the patterns rather than to recompile them twice each time the method is called. So, compile the pattern and use a static reference to it:

   private static final Pattern BOUNDARYSPLIT = Pattern.compile("(?<=\\D)(?=\\d)|(?<=\\d)(?=\\D)");
   

   Then, in your method you can reuse that pattern easily with:

   String[] s1Parts = BOUNDARYSPLIT.split(s1);
   String[] s2Parts = BOUNDARYSPLIT.split(s2);
   

   This will save a lot of performance.

2. The second issue is the 'convenience' of using a try/catch block for the ParseInt. Creating, throwing, and catching an exception is a surprisingly slow and complicated process. Using a try/catch as part of a 'routine' code-path is a mistake. Especially in something as frequent as a compareTo method. You should first make an attempt to see whether the input has a small hope of converting before throwing an exception:

   if (s1parts[i].charAt(0) >= '0' && s1parts[i].charAt(0) <= '9') {
       // put your try-catch block here....
   } else {
       return s1parts[i].compareTo(s2parts[i]);
   }
   

3. I noticed, while writing this up, that in your catch-block, you use:

    return s1.compareTo(s2);
   

   I don't think it makes a difference in the functionality, but, you should probably use:

    return s1parts[i].compareTo(s2parts[i]);
   

Answer 3

Your approach appears to be basically sound.

My main concern is catch(Exception ex). Catching all exceptions like that makes me very nervous and puzzled about your intent. I have to wonder, what could possibly go wrong inside the try-block? My thought process:

1. The exception would have to be thrown from the Integer.parseInt() calls, since the diff portion is foolproof.
2. Obviously, Integer.parseInt() could throw NumberFormatException.
3. What about ArrayIndexOutOfBoundsException? No, we're safe, because you already checked in the while-loop condition. Furthermore, if ++i got executed, it wouldn't enter the else-clause.
4. What about NullPointerException? It seems impossible, since the parts arrays came from String.split().
5. Anything else? OutOfMemoryError, maybe? No, that's a Throwable but not an Exception.
6. Any other possibilities? No. Am I sure? No.

For my sanity, please change that to catch (NumberFormatException ex)!

Changing the while-loop into a for-loop would make it easier to recognize the flow control. You can also save a level of indentation.

for (int i = 0; i < s1Parts.length && i < s2Parts.length; ++i) {
    //if parts are the same
    if (s1Parts[i].compareTo(s2Parts[i]) == 0) {
        continue;
    }
    try {
        int intS1 = Integer.parseInt(s1Parts[i]);
        int intS2 = Integer.parseInt(s2Parts[i]);

        //if the parse works
        int diff = intS1 - intS2; 
        if (diff == 0) {
            // continue;    // Actually, this is a no-op
        } else {
            return diff;
        }
    } catch (NumberFormatException ex) {
        // Buggy, as noted by @rolfl
        // return s1.compareTo(s2);
        return s1Parts[i].compareTo(s2Parts[i]);
    }
}

The epilogue could be simplified to just return s1.length() - s2.length().

Answer 4

Changes the pattern to this if you want to use decimals:

private static Pattern BOUNDARYSPLIT = Pattern.compile("(?<=\\D\\.)(?=\\d)|(?<=\\d)(?=\\D)");