Number aware string sorting with comparator Java

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 (http://stackoverflow.com/questions/8270784/how-to-split-a-string-between-letters-and-digits-or-between-digits-and-letters).

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

Any help to improve the solution would be appreciated. Thanks!

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;
            }
        }
}

Thanks for the suggestions. Based on the suggestions and discussions I have changed the code to the following improved versions. I've take out //end ;) Any other suggestions? If not I'll mark rolfl's solution.

import java.util.Comparator;
import java.util.regex.Pattern;

public class NumberAwareStringComparator implements Comparator<String>{

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

 public int compare(String s1, String s2) {

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

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

            //if parts are the same
            if(s1Parts[i].compareTo(s2Parts[i]) == 0){
                //go to next part
                ++i;
            }else{
                //check parts are both numeric
                if(s1Parts[i].charAt(0) >= '0' && s1Parts[i].charAt(0) <= '9' 
                        && s2Parts[i].charAt(0) >= '0' && s2Parts[i].charAt(0) <= '9'){
                    try{

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

                        int diff = intS1 - intS2;

                        if(diff == 0){
                            ++i;
                        }else{
                            return diff;
                        }
                    }catch(Exception ex){
                        //'should' never reach but ...
                        return s1Parts[i].compareTo(s2Parts[i]);
                    }
                }else{
                    //string compare if neither are numeric
                    return s1Parts[i].compareTo(s2Parts[i]);
                }
            }
        }

        //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;
        }

    }

 }

You want to compare digits no matter their place in the string, correct? For instance, given strings file1img, file10img, file2img, you want them sorted file1img, file2img, file10img? If so, the pattern matched in your linked answer should work. Otherwise you should compare from the ends of the strings. — Trojan, Dec 12 '13 at 7:24
Rule of thumb: }//end while If you need such comments to structure your code or make it more readable, there's something wrong with your code. — Bobby, Dec 12 '13 at 13:04
Bobby, Do you have any suggestions on improving the code? I think //end is entirely subjective and doesn't say anything about the code. — pbible, Dec 12 '13 at 14:03

200_success · Accepted Answer · 2013-12-12 20:35:35Z

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.

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

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

    private NumberAwareStringComparator() {
    }

    public int compare(String s1, String 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.

I thought that Integer.parseInt always had to be surrounded with try catch (maybe this post explains it stackoverflow.com/questions/14255880/…). If it does not need to be caught then I could just remove the try catch portion after the check for digits. This solution seems good though. Good idea making it effectively static with the singleton like INSTANCE. — pbible, Dec 12 '13 at 19:40
We have log files on our systems that have the following names: 201312121444.43234.log ... you still need the NumberFormatException — rolfl, Dec 12 '13 at 19:45
In this instance (because \\d does not match -) the expression return n1 - n2; is 'OK', but, in general, you should never use this 'pattern' in a comparator: If n1 = 2147483640 and n2 = -10 we would expect to return a 'positive' value, but, in reality, n1 - n2 will overflow, and will become very negative. — rolfl, Dec 12 '13 at 19:52
@200_success I think this is a good answer. If it really was me doing this compare, and if I thought of the regex pattern you used (which is a good one, BTW), then I also may add two checks before the BigInt work: make sure both values are same length (longer numbers are always bigger); do simple Integer.parseInt(...) for short values (9-digits or less) — rolfl, Dec 12 '13 at 20:07
Explained matcher.group() in comments. You could use return s1.length() - s2.length() as an epilogue, but I chose to test .hitEnd() because it's obviously related to how the while-loop terminated, and therefore makes the code more coherent. — 200_success, Dec 12 '13 at 20:44

rolfl · Answer 2 · 2013-12-12 12:38:24Z

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:

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.
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]);
}
```
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]);
```

Good points. Static pattern and a check before the exception are both great points. I think that adding a check on s2parts[i] in your if statement would ensure the try never thorws the exception. If s1part[i] is numeric but s2part[i] is not a normal string compare would be fine. Thoughts? — pbible, Dec 12 '13 at 14:21
@pbible - when I wrote my answer I worked on the assumption (which is broken, I think) that if s1parts[x] is a number then s2parts[x] is also a number (and visa-versa for string). As a result I thought I only needed to check one side to see if it was numeric. Now I see that, if the input is: "file10x" and "10filex" you will still get an exception.... so, you are right, you should have the second check. — rolfl, Dec 12 '13 at 14:25

200_success · Answer 3 · 2013-12-12 20:55:29Z

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:

The exception would have to be thrown from the Integer.parseInt() calls, since the diff portion is foolproof.
Obviously, Integer.parseInt() could throw NumberFormatException.
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.
What about NullPointerException? It seems impossible, since the parts arrays came from String.split().
Anything else? OutOfMemoryError, maybe? No, that's a Throwable but not an Exception.
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().

Definitely a good catch with NumberFormatException. What about the test for digits suggested by rolfl? Do you agree? — pbible, Dec 12 '13 at 18:56
See my other answer for an alternative to testing for digits. — 200_success, Dec 12 '13 at 19:17
@200_success - good catch on the NumberFormatException vs. Exception, but I think your other answer is much better, Excpetions should never be part of expected (routine) program flow. — rolfl, Dec 12 '13 at 20:10

asked	1 month ago
viewed	131 times
active	1 month ago

current community

more stack exchange communities

Number aware string sorting with comparator Java

3 Answers

Your Answer

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

Linked

Hot Network Questions

current community

more stack exchange communities

Number aware string sorting with comparator Java

3 Answers

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions