11
\$\begingroup\$

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;
            }
        }
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Trojan Dec 12 '13 at 7:24
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Bobby Dec 12 '13 at 13:04
  • 1
    \$\begingroup\$ Bobby, Do you have any suggestions on improving the code? I think //end is entirely subjective and doesn't say anything about the code. \$\endgroup\$ – pbible Dec 12 '13 at 14:03
8
\$\begingroup\$

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>.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – pbible Dec 12 '13 at 19:40
  • 1
    \$\begingroup\$ We have log files on our systems that have the following names: 201312121444.43234.log ... you still need the NumberFormatException \$\endgroup\$ – rolfl Dec 12 '13 at 19:45
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – rolfl Dec 12 '13 at 19:52
  • 1
    \$\begingroup\$ @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) \$\endgroup\$ – rolfl Dec 12 '13 at 20:07
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – 200_success Dec 12 '13 at 20:44
7
\$\begingroup\$

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]);
    
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – pbible Dec 12 '13 at 14:21
  • \$\begingroup\$ @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. \$\endgroup\$ – rolfl Dec 12 '13 at 14:25
3
\$\begingroup\$

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().

\$\endgroup\$
  • \$\begingroup\$ Definitely a good catch with NumberFormatException. What about the test for digits suggested by rolfl? Do you agree? \$\endgroup\$ – pbible Dec 12 '13 at 18:56
  • \$\begingroup\$ See my other answer for an alternative to testing for digits. \$\endgroup\$ – 200_success Dec 12 '13 at 19:17
  • \$\begingroup\$ @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. \$\endgroup\$ – rolfl Dec 12 '13 at 20:10
1
\$\begingroup\$

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

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

protected by Community Feb 1 '17 at 10:18

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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