Test failing for unexpected Collections.sort behavior

user_5235665 0
Viewed 124

Please note: I mention JUnit here and provide a SSCCE code example using it but this is a Java collections question at heart and can be answered by anyone with Java experience regardless of their experience with JUnit.

Java 8 here and I am trying to sort a list of strings but am getting some unexpected behaviors out of Collections.sort(myList) and am wondering what is happening.

Here is my full unit test:

@RunWith(MockitoJUnitRunner.class)
public class SorterTest {

    @Test
    public void should_sort_correctly_including_capitalization_rules() {

        // given
        String[] actualNames = new String[] {
            "DCME",
            "CCME",
            "ACME",
            "BCME",
            "AGME",
            "AACME",
            "aCME",
            "Acme",
            "AaCME",
            "aACME",
        };
        List<String> actual = Arrays.asList(actualNames);

        // the order I would *expect* them to sort into...
        String[] expectedNames = new String[] {
                "aACME",
                "aCME",
                "AaCME",
                "AACME",
                "Acme",
                "ACME",
                "AGME",
                "BCME",
                "CCME",
                "DCME"
        };
        List<String> expected = Arrays.asList(expectedNames);

        // when
        Collections.sort(actual);

        // then
        assertTrue(actual.equals(expected));

    }

}

The JUnit assertTrue here fails at runtime because the actual list is sorted into:

0 = "AACME"
1 = "ACME"
2 = "AGME"
3 = "AaCME"
4 = "Acme"
5 = "BCME"
6 = "CCME"
7 = "DCME"
8 = "aACME"
9 = "aCME"

Thats ^^^ debugger output, and the numbers represent the list index of each element.

So for some reason Collections.sort is saying that the string "BCME" is lexiconographically "lower" (will appear earlier in a sorted list) than "aCME", which is just plain nuts to me. :-)

I should mention that I will only be dealing with ASCII characters in UTF-8 here, but my application will perform pre-validation that assures us all characters in each string/name will be in the range of [a-z][A-Z].

Either way, the sorting rules I'm looking for my Java code to use are this:

  • when I say "lower", I mean "will appear earlier in a sorted list" and when I say "higher" I mean "will appear later in a sorted list"
    • hence I would say "3 is lower than 43", because in a sorted list of ints, 3 will appear earlier in that list than 43 would, etc.
  • lower-case letters are lower than uppercase; so "a" should appear before "A"
    • hence the order of all letters is aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
  • shorter words come before longer words, provided that they are an identical (casing included) subsets of the longer word
    • "but" is lower than (comes before) "butterfly"
    • "butterfly" is lower than "But" (b < B)
    • "butterfly" is lower than "bUt" (b and b are the same, but u < U)

Given these sorting rules, the list from my unit test should sort into:

Sort Order   Reason why it comes after the last one in the list
================================================================
aACME        
aCME         1st letter is 'a' but 2nd letter is 'C' and A < C
AaCME        1st letter is 'A' and a < A
AACME        1st letter is 'A' and 2nd letter is 'A' and a < A
Acme         1st letter is 'A' but 2nd letter is 'c' and A < c
ACME         1st letter is 'A' but 2nd letter is 'C' and c < C
AGME         1st letter is 'A' but 2nd letter is 'G' and C < G
BCME         1st letter is 'B' and aA < bB
CCME         1st letter is 'C' and bB < cC
DCME         1st letter is 'D' and cC < dD

How can I change the code above so that the unit test passes and the list is sorted the way I need?

junit collections sorting java
3 Answers

Java has class RuleBasedCollator which allows to customize sorting/ordering of characters.

In this case, lower case letters should come before the upper case letters, so the rules may look as follows:

static RuleBasedCollator lowerFirst() {
    try {
        return new RuleBasedCollator(
            "< a < A < b < B < c < C < d < D < e < E < f < F < g < G < h < H < i < I < j < J < "
            + "k < K < l < L < m < M < n < N < o < O < p < P < q < Q < r < R < s < S < t < T < "
            + "u < U < w < W < x < X < y < Y < z < Z"
        );
    } catch (ParseException parsex) {
        throw new IllegalArgumentException("Failed to create lowerFirst collator", parsex);
    }
}

Test:

String[] names = new String[] {
    "DCME",  "CCME", "ACME", "BCME",  "AGME",
    "AACME", "aCME", "Acme", "AaCME", "aACME",
};

String[] expected = new String[] {
    "aACME", "aCME", "AaCME", "AACME", "Acme",
    "ACME", "AGME", "BCME", "CCME", "DCME"
};
        
Arrays.sort(names, lowerFirst());

System.out.println("sorted:   " + Arrays.toString(names));
System.out.println("expected: " + Arrays.toString(expected));

Output

sorted:   [aACME, aCME, AaCME, AACME, Acme, ACME, AGME, BCME, CCME, DCME]
expected: [aACME, aCME, AaCME, AACME, Acme, ACME, AGME, BCME, CCME, DCME]
user_132798310

Assuming you only have letters, you can define a comparator something like:

Comparator<String> comparator = (a, b) -> {
    // Compare the characters pairwise.
    for (int i = 0, m = Math.min(a.length(), b.length()); i < m; ++i) {
      char aa = a.charAt(i);
      char bb = b.charAt(i);
      // If one is lowercase but the other isn't, say that the lowercase comes first.
      if (Character.isLowerCase(aa) != Character.isLowerCase(bb)) {
        return Character.isLowerCase(aa) ? -1 : 1;
      }

      // If the characters are the same case but aren't the same, say the lexicographically first one is first.
      if (aa != bb) {
        return aa < bb ? -1 : 1;
      }
    }
    // If the pair-wise comparison doesn't find a difference, say the shortest one is first; or they are equal if the same length.
    return Integer.compare(a.length(), b.length());
};
user_37881760

Write a comparator to sort things the way you want. We're not going to write it for you, but it should be simple to have the comparator map/translate the strings into corresponding sort keys...

For example, assuming only [A-Za-z] map

a->0x00
A->0x01 
b->0x02
B->0x03

etc.

Remember that the comparator will visit elements more than once, so if the data volume is sufficiently high (say, >106 strings) and performance is an issue, you might have to cache the sort keys.

user_181570
Related