DEV Community: Matylda Chmielewska

Test-driven implementation of an alpha-numerical comparator

Matylda Chmielewska — Mon, 23 Nov 2020 11:12:06 +0000

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.

Software maintenance strategies for 2020: how to level up your existing processes

Matylda Chmielewska — Thu, 20 Aug 2020 05:28:22 +0000

With almost all companies experiencing a slowdown and trying to find ways to keep their teams and operations in place, it’s safe to say that the core activities of many businesses are currently paused. Investments and new ventures may be suspended, but it shouldn’t mean that you should passively wait for what will happen next.

If there’s one thing that the current situation lends itself to it’s creating a more resilient business. That’s it. Resilience will help you prepare for any difficulties to come and get you ahead of your competitors. You’ll be able to come out of this stronger than ever.

This also means that there’s never been a better time to focus on software maintenance and leveling up your software maintenance processes. You can finally reflect on what your company has been doing and rethink some aspects. Here’s what you can do whether you’re just starting out or want to level up.

Crucially, the strategies I’m listing below will help you when you’re bringing new people on to your team or updating your product. They will also help you reduce software maintenance costs.

So, here are the strategies for getting your businesses ready for any challenges you may face and for reducing your costs. Use these separately or together for an optimised software maintenance process.

Review your documentation

Many developers do not update their software documentation or understand how important it is to do so. This can cause issues when you want to upgrade your application or hire new people on to your team. Contrary to the common opinion, writing comprehensive software documentation is an important part of the software maintenance process.

The current slowdown is an ideal opportunity to finally get it right. Start by auditing the state of the developer documentation at your company. Are there any parts that are missing? Are there any elements of the software that are not covered at all?

Remember that the main purpose of the documentation is to provide details of how code should work, with supporting examples. It should also be as useful, understandable and concise as possible, so make sure it’s free of unnecessary jargon. Use tools such as Tettra, GitHub Pages or MarkdownPad for ready-to-use templates and tips on how documentation should look like.

You can also introduce solutions such as developer playground or any other type of dynamic documentation that will make the process a bit more enjoyable. These can then be turned into interactive developer tutorials to train your junior developers.

Migrate your solutions to cloud

This is a no-brainer in 2020: migrating at least some part of your product or processes to cloud is an obvious choice for businesses. I’ve listed the benefits of using cloud solutions in one of the latest case studies, so I won’t go through them again, but in short: these solutions are not only cost-saving but also ideal for keeping your infrastructure light and contactless. They will also help you prepare for the next downturn.

So, how should you implement cloud solutions at your company?

Just a disclaimer before we start: although migration to cloud sounds like a huge project to take on, especially during the crisis, it doesn’t have to be this way. You can start slowly - by moving your services one by one – starting with less critical ones - so the process will be gradual and more cost-effective in the long term.

How to do it in practice?

Start by analysing which parts can be easily transferred to cloud as these can be the foundation of your hybrid solution. The migration process itself should also be divided into stages with the infrastructure being recreated and set up using AWS or Microsoft Azure. It can be then filled with data as you move closer to the final migration phase.

Going hybrid before going entirely serverless is also a good way to test and optimise your digital product.

With a lighter, serverless infrastructure you will also be switch on and off any parts of the applications that are not needed all the time. Once again, it’s a solution that will help you limit your spending.

With a cloud-based product, it will also be easier for your remote teams to collaborate on any maintenance or DevOps projects. And if you need to outsource some of these tasks, you can share any repositories and databases with a group of outsourced specialists.

Invest in Quality Assurance

Testing and ensuring the quality of the code is the most crucial part of your software development process. In reality, that’s not always the case. When you reorganise your processes take the time to check quality of your code.

We often think of QA as a set of tasks for testers that go in at the very last stage of the project to check if it’s working properly. The truth is it should start much earlier than that. Make sure you cover it during each stage of the process:

Planning - here’s where a QA specialist can prepare a requirements analysis that will be crucial for completing the further stages of the development process and for what’s maybe an even more important task, preventing any risks and bugs.

Design - a QA team can also collaborate with your UI/UX experts to create a test plan and review your design from a user’s viewpoint.

Development - test-driven development is an effective method where you simply write code with unit tests built-in and refactor it continuously.

Testing - last but not least, testing can also be carried out where QA specialists audit the product for any areas that need to be fixed and optimised.

Quality Assurance is also not ideal for making sure that your development process is (almost) perfect at every stage. It’s allows your team to gain a fresh perspective on what they do, especially if it’s done by the external team.

Where does software maintenance come into the picture? As you can see the above points are about reviewing and optimising your current processes. First and foremost, consider test coverage of your software, think about introducing automatic tests and check if your software has well-prepared regression tests.

Automate your software development process

Once your team has worked on the quality documentation, it will be easier for them to automate at least some parts of the software development processes. This assumes that you already have a shared repository where all developers are place the code they write. This is also the single source of software for your project.

The next step will be to set up a standardised process for creating software copies. This so-called ‘build process’ should be followed by every developer and tester on your team, as well as by every script and build-in mechanism.

Subsequently, you should be able to automate the ‘build process’ i.e. use a script for downloading the latest software version from the repository. This will save time for the developers and allow them to avoid going through multiple steps to do it.

Similar processes can be set up for pushing any changes to production. Your testing environment should resemble the user-facing one as closely as possible, so deployments can be completed by starting a single script or by clicking a button.

Rethink your product infrastructure

It may be that your product infrastructure has been growing organically and without a specific roadmap or a plan in mind. This can be fixed by auditing your current structure and applying process optimisations whenever possible. In the longer term, this approach will not only make your product easier to maintain but also save you money.

Make sure that you remove any parts of the product and tools that your team no longer need. Divide your product into more manageable parts that can updated and developed on their own at any time.

If you’re using customised applications, one of the ways to further limit your costs is replace some parts of your application with generic SaaS solutions for tasks such as a user messaging or a performance monitoring system.