Test-driven implementation of an alpha-numerical comparator

This time, I'm sharing an article written by my colleague at GOD Nearshore SE, Tomasz Zychewicz.

Test-driven development (TDD) is – in short - an agile way of implementation that assumes creating automated tests before the business code. The goal of this approach is to track the real progress of the implementation, but also helps while refactor or cleaning code (red-green-refactor cycle).

The goal of this article is to present a test-driven development approach in a practical way. In this article, I will present how to implement an alpha-numerical sorting using JAVA and JUnit framework.

REQUIREMENTS
One of the requirements is that nodes in a tree are sorted in an alpha-numerical order.

Alpha-numerical order means that nodes containing numbers should be sorted according to the numbers, and not like strings (string-like sorting orders "node 10" before "node 2", because alphabetical order compares characters one after another until the compared strings differ. Then the result of the different characters effects of the comparison of the whole strings. That is why, it may happen that "node 10" will be located before "node 2".

The requirement includes also leading zeros and letter suffixes, but focuses only on natural numbers, which mean, that negative numbers are not taken into account.

The full requirement is described in Table 1.

Table 1. Alpha numerical sorting of strings containing digits.

How to start

There is a basic implementation of a string comparator that is to be described in the article.

1 class AlphaNumericalComparator implements Comparator<String> { 
2 @Override 
3 public int compare(String o1, String o2) { 
4 return o1.compareTo(o2); 
5 } 
6 } 

How to prepare tests

Now some JUnit tests should be prepared to check the progress of the implementation. Following tests are designed to see if the requirement is covered properly.

For this article, let’s focus on most obvious cases:
• threeNodes() - tests it strings are sorted according to included numbers
• leadingZero() - tests, if a string containing a leading zero precedes the string without one
• suffix() - tests, if string with suffix is properly sorted
• alphaNumerical() - covers the full requirement

1 @Test 
2 public void threeNodes() { 
3 List<String> actuals = Arrays.asList("node 2", "node 1", "node 10"); 
4 List<String> expected = Arrays.asList("node 1", "node 2", "node 10"); 
5 6 
Collections.sort(actuals, new AlphaNumericalComparator()); 
7 Assert.assertEquals(expected, actuals); 
8 } 
9 
10 @Test 
11 public void leadingZero() { 
12 List<String> actuals = Arrays.asList("node 1", "node 01"); 
13 List<String> expected = Arrays.asList("node 01", "node 1"); 
14 
15 Collections.sort(actuals, new AlphaNumericalComparator()); 
16 Assert.assertEquals(expected, actuals); 
17 } 
18 
19 @Test 
20 public void suffix() { 
21 List<String> actuals = Arrays.asList("node 1a", "node 1"); 
22 List<String> expected = Arrays.asList("node 1", "node 1a"); 
23 
24 Collections.sort(actuals, new AlphaNumericalComparator()); 
25 Assert.assertEquals(expected, actuals); 
26 } 
27 
28 @Test 
29 public void alphaNumerical() { 
30 List<String> actuals 
31 = Arrays.asList("node 2", "node 1", "node 10", "node 1a", "node 01"); 
32 List<String> expected 
33 = Arrays.asList("node 01", "node 1", "node 1a", "node 2", "node 10"); 
34 
35 Collections.sort(actuals, new AlphaNumericalComparator()); 
36 Assert.assertEquals(expected, actuals); 
37 } 

First execution’s results are presented in Table 2. Using a regular string-like comparator, there are two failed tests.

A reason for that is that given strings -to be sorted contain numbers -cannot be sorted in a proper way using this comparator.

Table 2. First execution results.

Splitting the given input

In order to compare input string, considering possible numbers, given inputs should be split into the numerical and non-numerical parts. This part will be called "groups" below.

Example: the given string should be split into the following groups:

"10node 2abc100" -! "10"; "node "; "2"; "abc"; "100" 
If the input string is splitted correctly we test with the test below: 
1 @Test 
2 public void split() { 
3 String actuals = "10node 2abc100"; 
4 List<String> expected = Arrays.asList("10", "node ", "2","abc","100"); 
5 Assert.assertEquals(expected, AlphaNumericalComparator.split(actuals); 
6 } 

Implementation of the splitting method uses regular expressions to find numerical and non-numerical groups.

Following expressions are defined as fields of the comparator:

1 private static final String digit = "\\d+"; 
2 private static final String nonDigit = "\\D+"; 
3 private static final Pattern pattern = Pattern.compile(digit + "|" + nonDigit); 

Splitting function is implemented as a method of the comparator class, and has a following implementation.

1 public static List<String> split(String toSplit) { 
2 List<String> splitted = new ArrayList<String>(); 
3 Matcher m = pattern.matcher(toSplit); 
4 while (m.find()) { 
5 splitted.add(m.group()); 
6 } 
7 return splitted; 
8 } 

When string is correctly split, group comparison may be performed.

Algorithm

If comparing groups are (string-like) equal they may be skipped and the next one may be compared.
Method compare() is to be extended, so that the equal groups would be skipped, and not equal group compared. Implementation of the compare() uses the already defined and tested split() method to extract the groups.

1 @Override 
2 public int compare(String o1, String o2) { 
3 List<String> groups1 = split(o1); 
4 List<String> groups2 = split(o2); 
5 6 
for (int i = 0; i < Math.max(groups1.size(), groups2.size()); i++) { 
7 String group1 = groups1.get(i); 
8 String group2 = groups2.get(i); 
9 
10 if (group1.equals(group2)) { 
11 continue; 
12 } 
13 return group1.compareTo(group2); 
14 } 
15 return o1.compareTo(o2); 
16 } 

Table 3. Second execution results.

Result of this tests executions are presented in Table 3. Using a modified compare() methods makes the suffix() test failing. . Important is, that alphaNumerical() and suffix() tests are failing because of IndexOutOfBoundsException.

Reason for this exception is different number of extracted groups.
To avoid this exception the comparison should be possible. If the number of comparing groups is different, an existing group should be compared to an empty string:

1 String group1 = getEmptyWhenNoGroups(groups1, i); 
2 String group2 = getEmptyWhenNoGroups(groups2, i); 
3 4 
private String getEmptyWhenNoGroups(List<String> groups, int i) { 
5 return groups.size() > i ? groups.get(i) : ""; 
6 } 

Table 4. Third execution results.

Table 4 presents test results with the comparing empty string, when numbers of split groups are different.

There is no more IndexOutOfBoundsException, however there are two failing tests. The reason is that numbers are not sorted correctly. Now numbers-like comparison is to be introduced.

In order to compare numerical groups as numbers we can parse them as integers, using Integer.parseInt() method. Using Integer.parseInt() however, we should be able to answer the question if it is possible, that parsed number may exceed the Integer.MAX_VALUE. At the beginning we assume, that the numerical group shouldn’t exceed the maximum integer value.

So if both groups are numbers, they should be compared as numbers, otherwise string-like, as before:

1 if (group1.matches(digit) && group2.matches(digit)) { 
2 int int1 = Integer.parseInt(group1); 
3 int int2 = Integer.parseInt(group2); 
4 5 
return int1 - int2; 
6 } 

Table 5. Fourth execution results.

Table 5 presents test results having compared numerical parts of the given string as numbers, however leadingZero() test fails. Reason for that is that Integer.parseInt() method, doesn’t distinguish numbers with leading zeros – results of Integer.parseInt("1") and Integer.parseInt("01") equals.
In order to distinguish numbers considering leading zero(s), the numerical group have to be compared like regular strings, and like numbers otherwise:

1 return int1 == int2 ? group1.compareTo(group2) : int1 - int2; 

Table 6. Final execution results.

Table 6 presents test results having considered leading zero. All tests are passed.

Now go back to the big numbers issue. Try to check the behaviour with the additional bigNumbers() test, that should provoke NumberFormatException. Having this executed the NumberFormatException is thrown, as expected.

1 @Test 
2 public void bigNumbers() { 
3 List<String> actuals = Arrays.asList("a1000000000000000", "a1000000000000001"); 
4 List<String> expected = Arrays.asList("a1000000000000000", "a1000000000000001"); 
5 6 
Collections.sort(actuals, new AlphaNumericalComparator()); 
7 Assert.assertEquals(expected, actuals); 
8 } 

The easiest way to handle this exception is to limit the numerical group size, so that the parsed number never exceeds
the max. allowed number. How to do this? Go back to the defined regexp extracting numbers and change the current
expression so that the length of the parsed number is no longer than 6 digits, so that we are sure, that the maximal
allowed size of the integer number is not exceeded.
1 //private static final String digit = "\d+";
2 private static final String digit = "\d{1,6}";

SUMMARY
The requirement comes from the real project. While estimating it, I couldn’t find any existing solutions covering these requirements. I have decided to implement algorithm on my own, as a programming exercise, because normally I don’t write any line of code. Furthermore, I wanted to write the article to present the test driven way of implementation the algorithm.