6
\$\begingroup\$

Given an array \$A = (a_1, a_2, \dots, a_n)\$, the number of inversions in \$A\$ is the number of index pairs \$i,j\$ (\$i < j\$) such that \$a_i > a_j\$. We can find the number of inversions in an array by running it through a slightly modified mergesort, which runs in \$\Theta(n \log n)\$. Even better, we can deploy a natural mergesort which runs in \$\Theta(n \log m)\$ time where \$m\$ is the number of runs in the input array. As a reminder, a run is a contiguous subsequence that is ascending. Needless to say, \$m \leq n\$. Without further ado, let's proceed to code:

BruteForceInversionCounter.java

package net.coderodde.util;

import java.util.Comparator;
import java.util.Objects;
import static net.coderodde.util.Utils.NATURAL_ORDER;
import static net.coderodde.util.Utils.checkIndices;

/**
 * This class implements a brute force inversion counting algorithm that runs in
 * quadratic time.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 30, 2017)
 */
public final class BruteForceInversionCounter {

    public static <T> int count(T[] array, 
                                int fromIndex,
                                int toIndex, 
                                Comparator<? super T> comparator) {
        Objects.requireNonNull(array);
        Objects.requireNonNull(comparator);
        checkIndices(array.length, fromIndex, toIndex);
        int inversions = 0;

        for (int i = fromIndex; i < toIndex; ++i) {
            for (int j = i + 1; j < toIndex; ++j) {
                if (comparator.compare(array[i], array[j]) > 0) {
                    inversions++;
                }
            }
        }

        return inversions;
    }

    public static <T> int count(T[] array, int fromIndex, int toIndex) {
        return count(array, fromIndex, toIndex, NATURAL_ORDER);
    }

    public static <T> int count(T[] array, Comparator<? super T> comparator) {
        Objects.requireNonNull(array);
        return count(array, 0, array.length, comparator);
    }

    public static <T> int count(T[] array) {
        return count(array, NATURAL_ORDER);
    }

    private BruteForceInversionCounter() {}
}

MergesortInversionCounter.java

package net.coderodde.util;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Objects;
import static net.coderodde.util.Utils.NATURAL_ORDER;
import static net.coderodde.util.Utils.checkIndices;

/**
 * This class implements a modification of merge sort that sorts an input array 
 * range and returns the number of inversions in the input range.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 30, 2017)
 */
public final class MergesortInversionCounter {


    public static <T> int count(T[] array, 
                                int fromIndex, 
                                int toIndex, 
                                Comparator<? super T> comparator) {
        Objects.requireNonNull(array);
        checkIndices(array.length, fromIndex, toIndex);
        int rangeLength = toIndex - fromIndex;

        if (rangeLength < 2) {
            return 0;
        }

        T[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);
        return count(aux, array, 0, fromIndex, rangeLength, comparator);
    }

    private static <T> int count(T[] sourceArray,
                                 T[] targetArray,
                                 int sourceOffset,
                                 int targetOffset,
                                 int rangeLength,
                                 Comparator<? super T> comparator) {
        if (rangeLength < 2) {
            return 0;
        }

        int halfRangeLength = rangeLength >>> 1;
        int inversions = count(targetArray,
                               sourceArray,
                               targetOffset,
                               sourceOffset,
                               halfRangeLength,
                               comparator);

        inversions += count(targetArray,
                            sourceArray,
                            targetOffset + halfRangeLength,
                            sourceOffset + halfRangeLength,
                            rangeLength - halfRangeLength,
                            comparator);

        return inversions + merge(sourceArray,
                                  targetArray,
                                  sourceOffset,
                                  targetOffset,
                                  halfRangeLength,
                                  rangeLength - halfRangeLength,
                                  comparator);
    }

    public static <T> int count(T[] array, int fromIndex, int toIndex) {
        return count(array, fromIndex, toIndex, NATURAL_ORDER);
    }

    public static <T> int count(T[] array, Comparator<? super T> comparator) {
        Objects.requireNonNull(array);
        return count(array, 0, array.length);
    }

    public static <T> int count(T[] array) {
        return count(array, NATURAL_ORDER);
    }

    private static <T> int merge(T[] sourceArray,
                                 T[] targetArray,
                                 int sourceOffset,
                                 int targetOffset,
                                 int leftRunLength,
                                 int rightRunLength,
                                 Comparator<? super T> comparator) {
        int inversions       = 0;
        int leftRunIndex     = sourceOffset;
        int leftRunEndIndex  = sourceOffset + leftRunLength;
        int rightRunIndex    = sourceOffset + leftRunLength;
        int rightRunEndIndex = rightRunIndex + rightRunLength;
        int targetIndex      = targetOffset;

        while (leftRunIndex < leftRunEndIndex 
                && rightRunIndex < rightRunEndIndex) {
            if (comparator.compare(sourceArray[rightRunIndex], 
                                   sourceArray[leftRunIndex]) < 0) {
                inversions += leftRunEndIndex - leftRunIndex;
                targetArray[targetIndex++] = sourceArray[rightRunIndex++];
            } else {
                targetArray[targetIndex++] = sourceArray[leftRunIndex++];
            }
        }

        System.arraycopy(sourceArray, 
                         leftRunIndex, 
                         targetArray,
                         targetIndex, 
                         leftRunEndIndex - leftRunIndex);
        System.arraycopy(sourceArray,
                         rightRunIndex,
                         targetArray, 
                         targetIndex, 
                         rightRunEndIndex - rightRunIndex);
        return inversions;
    }

    private MergesortInversionCounter() {}
}

NaturalMergesortInversionCounter.java

package net.coderodde.util;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Objects;
import static net.coderodde.util.Utils.NATURAL_ORDER;
import static net.coderodde.util.Utils.checkIndices;

/**
 * This class implements a modification of the natural mergesort that counts 
 * inversion in the input array range.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 30, 2017)
 */
public final class NaturalMergesortInversionCounter {

    public static <T> int count(T[] array,
                                int fromIndex,
                                int toIndex) {
        return count(array, fromIndex, toIndex, NATURAL_ORDER);
    }

    public static <T> int count(T[] array) {
        Objects.requireNonNull(array);
        return count(array, 0, array.length);
    }

    public static <T> int count(T[] array, Comparator<? super T> comparator) {
        Objects.requireNonNull(array);
        return count(array, 0, array.length, comparator);
    }

    public static <T> int count(T[] array, 
                                int fromIndex, 
                                int toIndex, 
                                Comparator<? super T> comparator) {
        Objects.requireNonNull(array);
        Objects.requireNonNull(comparator);
        checkIndices(array.length, fromIndex, toIndex);
        int rangeLength = toIndex - fromIndex;

        if (rangeLength < 2) {
            return 0;
        }

        RunLengthQueue runLengthQueue = 
                buildRunLengthQueue(array, 
                                    fromIndex, 
                                    toIndex, 
                                    comparator);

        T[] bufferArray = Arrays.copyOfRange(array, fromIndex, toIndex);
        T[] sourceArray;
        T[] targetArray;
        int sourceOffset;
        int targetOffset;
        int mergePasses = getNumberOfMergePasses(runLengthQueue.size());

        if ((mergePasses & 1) == 1) {
            // Odd amount of merge passes over the entire input array range.
            // Set the buffer array as the source array so that the sorted 
            // result ends in in the input array.
            sourceArray = bufferArray;
            targetArray = array;
            sourceOffset = 0;
            targetOffset = fromIndex;
        } else {
            sourceArray = array;
            targetArray = bufferArray;
            sourceOffset = fromIndex;
            targetOffset = 0;
        }

        int runsLeftInCurrentMergePass = runLengthQueue.size();
        int offset = 0;
        int inversions = 0;

        // While there are runs to merge, iterate:
        while (runLengthQueue.size() > 1) {
            int leftRunLength  = runLengthQueue.dequeue();
            int rightRunLength = runLengthQueue.dequeue();

            inversions += merge(sourceArray,
                                targetArray,
                                sourceOffset + offset,
                                targetOffset + offset,
                                leftRunLength,
                                rightRunLength,
                                comparator);

            runLengthQueue.enqueue(leftRunLength + rightRunLength);
            runsLeftInCurrentMergePass -= 2;
            offset += leftRunLength + rightRunLength;

            switch (runsLeftInCurrentMergePass) {
                case 1:
                    int lastRunLength = runLengthQueue.dequeue();
                    // In the target array, this 'unmarried' run might be
                    // in the form of two unmerged runs.
                    System.arraycopy(sourceArray,
                                     sourceOffset + offset, 
                                     targetArray,
                                     targetOffset + offset,
                                     lastRunLength);
                    runLengthQueue.enqueue(lastRunLength);
                    // FALL THROUGH!

                case 0:
                    runsLeftInCurrentMergePass = runLengthQueue.size();
                    offset = 0;

                    T[] tmpArray = sourceArray;
                    sourceArray = targetArray;
                    targetArray = tmpArray;

                    int tmpOffset = sourceOffset;
                    sourceOffset = targetOffset;
                    targetOffset = tmpOffset;
                    break;
            }
        }

        return inversions;
    }

    static <T> RunLengthQueue 
    buildRunLengthQueue(T[] inputArray, 
                        int fromIndex,
                        int toIndex,
                        Comparator<? super T> comparator) {
        int last = toIndex - 1;
        int left = fromIndex;
        int right = left + 1;
        RunLengthQueue runLengthQueue =
                new RunLengthQueue(toIndex - fromIndex);
        while (left < last) {
            int head = left;

            while (left < last 
                    && comparator.compare(inputArray[left],
                                          inputArray[right]) <= 0) {
                ++left;
                ++right;
            }

            ++left;
            ++right;

            runLengthQueue.enqueue(left - head);
        }

        if (left == last) {
            runLengthQueue.enqueue(1);
        }

        return runLengthQueue;
    }

    /**
     * This static inner class implements a simple queue of integers used to 
     * represent the run sequence in the array to sort.
     */
    private static final class RunLengthQueue {

        /**
         * The minimum capacity of the storage array.
         */
        private static final int MINIMUM_CAPACITY = 256;

        /**
         * Stores the run lengths.
         */
        private final int[] storage;

        /**
         * The index of the array component that will be dequeued next.
         */
        private int head;

        /**
         * The index of the array component to which the next run length will
         * be set.
         */
        private int tail;

        /**
         * The current number of run lengths stored in this queue.
         */
        private int size;

        /**
         * A bit mask used for simpler modulo calculation (at least at the level
         * of hardware).
         */
        private final int mask;

        /**
         * Creates a run length queue large enough to hold maximum of 
         * {@code capacity} elements.
         * 
         * @param capacity the requested capacity, may be increased in the 
         *                 constructor.
         */
        RunLengthQueue(int capacity) {
            capacity = ceilPowerOfTwo(Math.max(capacity, MINIMUM_CAPACITY));
            this.mask = capacity - 1;
            this.storage = new int[capacity];
        }

        /**
         * Enqueues a given run length to the tail of this queue.
         * 
         * @param runLength the run length to enqueue.
         */
        void enqueue(int runLength) {
            storage[tail] = runLength;
            tail = (tail + 1) & mask;
            size++;
        }

        /**
         * Dequeues the run length from the head of this queue.
         * 
         * @return the run length stored in the head of this queue.
         */
        int dequeue() {
            int ret = storage[head];
            head = (head + 1) & mask;
            size--;
            return ret;
        }

        /**
         * Returns the number of run lengths stored in this queue.
         * 
         * @return the number of run lengths.
         */
        int size() {
            return size;
        }

        /**
         * Returns a smallest power of two no less than {@code number}.
         * 
         * @param number the number to ceil.
         * @return a smallest power of two no less than {@code number}.
         */
        private static int ceilPowerOfTwo(int number) {
            int ret = Integer.highestOneBit(number);
            return ret != number ? (ret << 1) : ret;
        }
    }

    /**
     * Computes the required number of merge passes needed to sort an input
     * array range containing {@code runs} runs.
     * 
     * @param runs the number of runs in the input array range.
     * @return the number of required merge passes.
     */
    private static int getNumberOfMergePasses(int runs) {
        return 32 - Integer.numberOfLeadingZeros(runs - 1);
    }

    private static <T> int merge(T[] sourceArray,
                                 T[] targetArray,
                                 int sourceOffset,
                                 int targetOffset,
                                 int leftRunLength,
                                 int rightRunLength,
                                 Comparator<? super T> comparator) {
        int leftRunIndex = sourceOffset;
        int rightRunIndex = leftRunIndex + leftRunLength;
        int leftRunEndIndex = rightRunIndex;
        int rightRunEndIndex = rightRunIndex + rightRunLength;
        int targetIndex = targetOffset;
        int inversions = 0;

        while (leftRunIndex != leftRunEndIndex 
                && rightRunIndex != rightRunEndIndex) {
            if (comparator.compare(sourceArray[rightRunIndex],
                                   sourceArray[leftRunIndex]) <0) {
                inversions += leftRunEndIndex - leftRunIndex;
                targetArray[targetIndex++] = sourceArray[rightRunIndex++];
            } else {
                targetArray[targetIndex++] = sourceArray[leftRunIndex++];
            }
        }

        System.arraycopy(sourceArray,
                         leftRunIndex,
                         targetArray,
                         targetIndex,
                         leftRunEndIndex - leftRunIndex);

        System.arraycopy(sourceArray, 
                         rightRunIndex,
                         targetArray,
                         targetIndex,
                         rightRunEndIndex - rightRunIndex);

        return inversions;
    }

    private NaturalMergesortInversionCounter() {}
}

Utils.java

package net.coderodde.util;

import java.util.Comparator;

/**
 * This class contains generic facilities.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 30, 2017)
 */
public final class Utils {

    public static final Comparator NATURAL_ORDER = new Comparator() {
        @Override
        public int compare(Object o1, Object o2) {
            return ((Comparable) o1).compareTo(o2);    
        }
    };

    public static void checkIndices(int arrayLength,
                                    int fromIndex, 
                                    int toIndex) {
        if (fromIndex < 0) {
            throw new IndexOutOfBoundsException(
                    "fromIndex(" + fromIndex + ") < 0");
        }

        if (toIndex > arrayLength) {
            throw new IndexOutOfBoundsException(
                    "toIndex(" + toIndex + ") > " + 
                    "arrayLength(" + arrayLength + ")");
        }

        if (fromIndex > toIndex) {
            throw new IndexOutOfBoundsException(
                    "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
    }
}

AbstractInversionCounterTest.java

package net.coderodde.util;

import java.util.Arrays;
import java.util.Random;
import org.junit.Test;
import static org.junit.Assert.*;

/**
 * This abstract test class implements all the actual unit tests.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 30, 2017)
 */
public abstract class AbstractInversionCounterTest {

    private static final int TEST_ITERATIONS = 100;
    private static final int MAXIMUM_ARRAY_LENGTH = 1000;

    protected final InversionCounter<Integer> inversionCounter;
    private final Random random = new Random();

    public AbstractInversionCounterTest(
            InversionCounter<Integer> inversionCounter) {
        this.inversionCounter = inversionCounter;
    }

    @Test
    public void test() {
        for (int iteration = 0; iteration < TEST_ITERATIONS; iteration++) {
            int length = random.nextInt(MAXIMUM_ARRAY_LENGTH + 1);
            int fromIndex = random.nextInt(Math.max(1, length / 10));
            int toIndex = 
                    length - random.nextInt(
                            Math.max(1, (length - fromIndex) / 10));

            Integer[] array1 = getRandomIntegerArray(length,
                                                     -length / 2 - 10,
                                                     +length / 2 + 10,
                                                     random);
            Integer[] array2 = array1.clone();

            assertEquals(BruteForceInversionCounter.count(array1, 
                                                          fromIndex, 
                                                          toIndex, 
                                                          Integer::compareTo),
                         inversionCounter.count(array2, 
                                                fromIndex, 
                                                toIndex, 
                                                Integer::compareTo));
            Arrays.sort(array1, fromIndex, toIndex);
            assertTrue(Arrays.equals(array1, array2));
        }
    }

    /**
     * Creates a random integer array.
     * 
     * @param length   the desired length of the array.
     * @param minValue the minimum integer value.
     * @param maxValue the maximum integer value.
     * @param random   the random number generator.
     * @return a randomly generated integer array.
     */
    private Integer[] getRandomIntegerArray(int length,
                                            int minValue,
                                            int maxValue,
                                            Random random) {
        Integer[] array = new Integer[length];

        for (int i = 0; i < length; ++i) {
            array[i] = randomValue(minValue, maxValue, random);
        }

        return array;
    }

    /**
     * Returns a random integer value from the range {@code minValue,
     * minValue + 1, ..., maxValue - 1, maxValue}, according to the uniform 
     * distribution.
     * 
     * @param minValue the minimum integer value.
     * @param maxValue the maximum integer value.
     * @param random   the random number generator.
     * @return a random integer value within the range.
     */
    private Integer randomValue(int minValue, int maxValue, Random random) {
        return minValue + random.nextInt(maxValue - minValue + 1);
    }
}

InversionCounter.java

package net.coderodde.util;

import java.util.Comparator;

/**
 * Defines the most specific API for inversion counting algorithms.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 30, 2017)
 * @param <T> the array component type.
 */
@FunctionalInterface
public interface InversionCounter<T> {

    public int count(T[] array, 
                     int fromIndex,
                     int toIndex, 
                     Comparator<? super T> comparator);
}

MergesortInversionCounterTest.java

package net.coderodde.util;

/**
 * This unit test tests the correctness of the mergesort-based inversion 
 * counter.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 30, 2017)
 */
public class MergesortInversionCounterTest 
        extends AbstractInversionCounterTest {

    public MergesortInversionCounterTest() {
        super(MergesortInversionCounter::count);
    }
}

NaturalMergesortInversionCounterTest.java

package net.coderodde.util;

/**
 * This unit test tests the correctness of the mergesort-based inversion 
 * counter.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 30, 2017)
 */
public class NaturalMergesortInversionCounterTest 
        extends AbstractInversionCounterTest {

    public NaturalMergesortInversionCounterTest() {
        super(NaturalMergesortInversionCounter::count);
    }
}

MyBenchmark.java

package net.coderodde;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.TimeUnit;
import net.coderodde.util.MergesortInversionCounter;
import net.coderodde.util.NaturalMergesortInversionCounter;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

/**
 * This class implements benchmark for inversion counter algorithms.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 31, 2017)
 */
public class MyBenchmark {

    private static final int ARRAY_LENGTH = 1_000_000;
    private static final int MINIMUM_INTEGER_VALUE = -100_000;
    private static final int MAXIMUM_INTEGER_VALUE = +100_000;
    private static final int RUN_LENGTH_IN_PRESORTED_ARRAY = 2000;

    @State(Scope.Thread)
    public static class MyRandomState {

        private final Random random = new Random();
        Integer[] array;

        @Setup(Level.Trial)
        public void createRandomArray() {
            array = createRandomIntegerArray(ARRAY_LENGTH,
                                             MINIMUM_INTEGER_VALUE,
                                             MAXIMUM_INTEGER_VALUE, 
                                             random);
        }
    }

    @State(Scope.Thread)
    public static class MyPresortedState {
        private final Random random = new Random();
        Integer[] array;

        @Setup(Level.Trial)
        public void createPresortedArray() {
            array = createPresortedIntegerArray(ARRAY_LENGTH,
                                                MINIMUM_INTEGER_VALUE,
                                                MAXIMUM_INTEGER_VALUE,
                                                random);
        }
    }

    @Benchmark 
    @BenchmarkMode(Mode.AverageTime) 
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public void testMergesortOnRandomArray(MyRandomState state) {
        MergesortInversionCounter.count(state.array);
    }

    @Benchmark
    @BenchmarkMode(Mode.AverageTime) 
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public void testMergesortOnPresortedArray(MyPresortedState state) {
        MergesortInversionCounter.count(state.array);
    }

    @Benchmark 
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public void testNaturalMergesortOnRandomArray(MyRandomState state) {
        NaturalMergesortInversionCounter.count(state.array);
    }

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public void testNaturalMergesortOnPresortedArray(MyPresortedState state) {
        NaturalMergesortInversionCounter.count(state.array);
    }

    private static Integer[] createRandomIntegerArray(int length,
                                                      int minimumIntegerValue,
                                                      int maximumIntegerValue,
                                                      Random random) {
        Integer[] array = new Integer[length];

        for (int i = 0; i < length; ++i) {
            array[i] = getRandomIntegerValue(minimumIntegerValue,
                                             maximumIntegerValue,
                                             random);
        }

        return array;
    }

    private static Integer[] 
        createPresortedIntegerArray(int length,
                                    int minimumIntegerValue,
                                    int maximumIntegerValue,
                                    Random random) {
        Integer[] randomArray = createRandomIntegerArray(length,
                                                         minimumIntegerValue,
                                                         maximumIntegerValue,
                                                         random);
        for (int i = 0; i < length; i += RUN_LENGTH_IN_PRESORTED_ARRAY) {
            Arrays.sort(randomArray,
                        i, 
                        Math.min(length, i + RUN_LENGTH_IN_PRESORTED_ARRAY));
        }

        return randomArray;
    }

    private static Integer getRandomIntegerValue(int minimumIntegerValue,
                                                 int maximumIntegerValue,
                                                 Random random) {
        return minimumIntegerValue + random.nextInt(maximumIntegerValue -
                                                    minimumIntegerValue + 1);
    }

    public static void main(String[] args) 
    throws RunnerException {
        Options options = new OptionsBuilder()
                          .include(MyBenchmark.class.getSimpleName())
                          .warmupIterations(5)
                          .measurementIterations(10)
                          .forks(1)
                          .build();
        new Runner(options).run();
    }
}

Benchmark figures


Benchmark                                         Mode  Cnt    Score     Error  Units
MyBenchmark.testMergesortOnPresortedArray         avgt   10  317.640 ± 187.535  ms/op
MyBenchmark.testMergesortOnRandomArray            avgt   10  168.408 ±  37.833  ms/op
MyBenchmark.testNaturalMergesortOnPresortedArray  avgt   10   39.191 ±  17.872  ms/op
MyBenchmark.testNaturalMergesortOnRandomArray     avgt   10   50.237 ±  11.120  ms/op

Info

The actual counters live here. The benchmark lives here.

Critique request

Please tell me anything that comes to mind, be it related to algorithms, unit testing or benchmarking.

\$\endgroup\$
  • \$\begingroup\$ I don't see any UnitTest since the classes you named *Test do not verify anything accept that the called constructors do not fail... \$\endgroup\$ – Timothy Truckle Dec 31 '17 at 17:37
  • \$\begingroup\$ @TimothyTruckle I just checked it by inserting fail() into the abstract test. It gets called two times (once for each algo), so, yes, they are getting tested. \$\endgroup\$ – coderodde Dec 31 '17 at 17:43
  • 1
    \$\begingroup\$ then you have a problem in your (Test-) class design. Since the behavior in each test is the same there should be only one test class using the different Sorter classes. A parameterized Test would have been appropriate... \$\endgroup\$ – Timothy Truckle Dec 31 '17 at 17:50
  • \$\begingroup\$ @Timothy Truckle Looks interesting, thanks! \$\endgroup\$ – coderodde Dec 31 '17 at 17:53
1
\$\begingroup\$

Working for 1+ years in QA Blackbox/Whitebox team I would say that you must test every possible combination that could be in your code. So you have check indexes util - ok, you need to have IndexesUtilTest You check happy scenarios, you check unhappy scenarios. You will see enter image description here

Which means that you haven't covered some method. You might be sure about your code if you covered different scenarios. Even if you missed 20%, you will not start from scratch if you find some bug - you'll just add unit test, sample input and you're done.

If we take class for example: public final class Utils {

public static final Comparator NATURAL_ORDER = new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {            
        return ((Comparable) o1).compareTo(o2);    
    }
};

public static void checkIndices(int arrayLength,
                                int fromIndex, 
                                int toIndex) {
    if (fromIndex < 0) {
        throw new IndexOutOfBoundsException(
                "fromIndex(" + fromIndex + ") < 0");
    }

    if (toIndex > arrayLength) {
        throw new IndexOutOfBoundsException(
                "toIndex(" + toIndex + ") > " + 
                "arrayLength(" + arrayLength + ")");
    }

    if (fromIndex > toIndex) {
        throw new IndexOutOfBoundsException(
                "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
    }
}

}

So for your comparator - you might have

    public int compare(Object o1, Object o2) {            

null pointer exception if o1 == null. so for comparator

test_o1_o2_not_null()
test_o1_null_o2_not_null(), etc

So go with coverage and all possible scenarios, name your tests nicely and you're fine!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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