The partitioning class should provide a method that moves the elements of the collection based on a pivot element, and we will need to know the position of the pivot element after the method finishes. The signature of the method should look something like this:

public int partition(SortableCollection<E> sortable, int start, int end, E pivot);

The class should also have access to Swapper and Comparator. In this case, we defined a class and not an interface; therefore, we will use constructor injection.

The partitioning class will look like the following:

package packt.java9.by.example.ch03.qsort; 

import packt.java9.by.example.ch03.SortableCollection; 
import packt.java9.by.example.ch03.Swapper; 

import java.util.Comparator; 

public class Partitioner<E> { 

    private final Comparator<E> comparator; 
    private final Swapper swapper; 
    public Partitioner(Comparator<E> comparator, Swapper swapper){ 
        this.comparator = comparator; 
        this.swapper = swapper; 
    } 

    public int partition(SortableCollection<E> sortable, int start, int end, E pivot){ 
        return 0; 
    } 
}

This code does nothing, but that is how TDD starts. We will create the definition of a requirement providing the skeleton of the code and the test that will call it. To do that, we will need something that we can partition. The simplest choice is an Integer array. The partition method needs a object of type SortableCollection<E>, and we will need something that wraps the array and implements this interface. We name that class ArrayWrapper. This class serves a general purpose and it is not only for the test. Because of that, we create it as production code and as such we put it in the directory main and not in the directory test. As this wrapper is independent from the implementation of Sort, the proper position of this class is in a new SortSupportClasses module. We will create the new module as it is not part of the interface. Implementations depend on the interface, but not on the support classes. There can also be some application that uses our libraries and may need the interface module and some of the implementation but still does not need the support classes when they deliver the wrapping functionality themselves. After all, we cannot implement all possible wrapping functionality. The SRP also holds for the modules.

Java libraries tend to contain unrelated functionalities. For the short run, it makes the use of the library simpler. You will only need to specify one dependency in your POM file and you will have all the classes and APIs that you need. In the long run, the application gets bigger, carrying a lot of classes that are part of some of the libraries but the application never uses them.

To add the new module, the module directory has to be created along with the source directories and the POM file. The module has to be added to the parent POM and it also has to be added to the dependencyManagement section so that the test code of the QuickSort module can use it without specifying the version. The new module depends on the interface module, so this dependency has to be added to the POM of the support classes.

The ArrayWrapper class is simple and general.

package packt.java9.by.example.ch03.support; 
import packt.java9.by.example.ch03.SortableCollection; 
public class ArrayWrapper<E> implements SortableCollection<E> { 
    private final E[] array; 
    public ArrayWrapper(E[] array) { 
        this.array = array; 
    } 
    public E[] getArray() { 
        return array; 
    } 
    @Override 
    public E get(int i) { 
        return array[i]; 
    } 
    @Override 
    public int size() { 
        return array.length; 
    } 
}

The ArraySwapper class, which we also need, comes into the same module. It is just as simple as the wrapper.

package packt.java9.by.example.ch03.support; 
import packt.java9.by.example.ch03.Swapper; 
public class ArraySwapper<E> implements Swapper { 
    private final E[] array; 
    public ArraySwapper(E[] array) { 
        this.array = array; 
    } 
    @Override 
    public void swap(int k, int r) { 
        final E tmp = array[k]; 
        array[k] = array[r]; 
        array[r] = tmp; 
    } 
}

Having these classes, we can create our first test.

package packt.java9.by.example.ch03.qsort; 

// imports deleted from print 

public class PartitionerTest {

Before creating the @Test method, we will need two helper methods that make assertions. Assertions are not always simple, and in some cases, they may involve some coding. The general rule is that the test and the assertions in it should be as simple as possible; otherwise, they are just possible source of programming errors. Additionally, we created them to avoid programming errors, not to create new ones.

The assertSmallElements method asserts that all elements before cutIndex are smaller than pivot.

    private void assertSmallElements(Integer[] array, int cutIndex, Integer pivot) { 
        for (int i = 0; i < cutIndex; i++) { 
            Assert.assertTrue(array[i] < pivot); 
        } 
    }

The assertLargeElements method makes sure that all elements following cutIndex are at least as large as pivot.

    private void assertLargeElemenents(Integer[] array, int cutIndex, Integer pivot) { 
        for (int i = cutIndex; i < array.length; i++) { 
            Assert.assertTrue(pivot <= array[i]); 
        } 
    }

The test uses a constant array of Integers and wraps it into an ArrayWrapper class.

    @Test 
    public void partitionsIntArray() { 
        Integer[] partitionThis = new Integer[]{0, 7, 6}; 
        Swapper swapper = new ArraySwapper<>(partitionThis); 
        Partitioner<Integer> partitioner = 
                new Partitioner<>((a, b) -> a < b ? -1 : a > b ? +1 : 0, swapper); 
        final Integer pivot = 6; 
        final int cutIndex = partitioner.partition(new ArrayWrapper<>(partitionThis), 0, 2, pivot); 
        Assert.assertEquals(1, cutIndex); 
        assertSmallElements(partitionThis, cutIndex, pivot); 
        assertLargeElemenents(partitionThis, cutIndex, pivot); 
    } 
}

There is no Comparator for Integer type in the JDK, but it is easy to define one as a lambda function. Now we can write the partition method, as follows:

public int partition(SortableCollection<E> sortable, int start, int end, E pivot){ 
    int small = start; 
    int large = end; 
    while( large > small ){ 
        while( comparator.compare(sortable.get(small), pivot) < 0 && small < large ){ 
            small ++; 
        } 
        while( comparator.compare(sortable.get(large), pivot) >= 0 && small < large ){ 
            large--; 
        } 
        if( small < large ){ 
            swapper.swap(small, large); 
        } 
    } 
    return large; 
}

If we run the test, it runs fine. However, if we run the test with coverage, then the IDE tells us that the coverage is only 92%. The test covered only 13 of the 14 lines of the partition method.

There is a red rectangle on the gutter at line 28. This is because the test array is already partitioned. There is no need to swap any element in it when the pivot value is 6. It means that our test is good, but not good enough. What if there is an error on that line?

To amend this problem, we will extend the test, changing the test array from { 0, 7, 6 } to { 0, 7, 6, 2}. Run the test and it fails. Why? After some debugging, we will realize that we invoke the method partition with the fixed parameter 2 as the last index of the array. But, we made the array longer. Why did we write a constant there in the first place? It is a bad practice. Let's replace it with partitionThis.length-1. Now, it says that cutIndex is 2, but we expected 1. We forgot to adjust the assertion to the new array. Let's fix it. Now it works.

The last thing is to rethink the assertions. The less code the better. The assertion methods are quite general, and we will use it for one single test array. The assertion methods are so complex that they deserve their own test. But, we do not write code to test. Instead of that, we can simply delete the methods and have the final version of the test.

@Test 
public void partitionsIntArray() { 
    Integer[] partitionThis = new Integer[]{0, 7, 6, 2}; 
    Swapper swapper = new ArraySwapper<>(partitionThis); 
    Partitioner<Integer> partitioner = 
            new Partitioner<>((a, b) -> a < b ? -1 : a > b ? +1 : 0, swapper); 
    final Integer pivot = 6; 
    final int cutIndex = partitioner.partition(new ArrayWrapper<>(partitionThis), 0, partitionThis.length-1, pivot); 
    Assert.assertEquals(2, cutIndex); 
    final Integer[] expected = new Integer[]{0, 2, 6, 7}; 
    Assert.assertArrayEquals(expected,partitionThis); 
}

And then again, is this a black-box test? What if the partitioning returns {2, 1, 7, 6}? It fits the definition. We can create more complex tests to cover such cases. But a more complex test may also have a bug in the test itself. As a different approach, we can create tests that may be simpler but rely on the internal structure of the implementation. These are not black-box tests and thus not ideal unit tests. I will go for the second one, but I will not argue if someone chooses the other.