commons-rng-core/src/test/java/org/apache/commons/rng/core/ProvidersCommonParametricTest.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.rng.core;

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.concurrent.Callable;

import org.junit.Assert;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.RestorableUniformRandomProvider;
import org.apache.commons.rng.RandomProviderState;

/**
 * Tests which all generators must pass.
 */
@RunWith(value = Parameterized.class)
public class ProvidersCommonParametricTest {
    /** RNG under test. */
    private final RestorableUniformRandomProvider generator;

    /**
     * Initializes generator instance.
     *
     * @param rng RNG to be tested.
     */
    public ProvidersCommonParametricTest(RestorableUniformRandomProvider rng) {
        generator = rng;
    }

    @Parameters(name = "{index}: data={0}")
    public static Iterable<RestorableUniformRandomProvider[]> getList() {
        return ProvidersList.list();
    }


    // Precondition tests

    @Test(expected = IllegalArgumentException.class)
    public void testPreconditionNextInt1() {
        generator.nextInt(-1);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testPreconditionNextInt2() {
        generator.nextInt(0);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testPreconditionNextLong1() {
        generator.nextLong(-1);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testPreconditionNextLong2() {
        generator.nextLong(0);
    }

    @Test(expected = IndexOutOfBoundsException.class)
    public void testPreconditionNextBytes1() {
        final int size = 10;
        final int num = 1;
        final byte[] buf = new byte[size];
        generator.nextBytes(buf, -1, num);
    }
    @Test(expected = IndexOutOfBoundsException.class)
    public void testPreconditionNextBytes2() {
        final int size = 10;
        final byte[] buf = new byte[size];
        generator.nextBytes(buf, size, 0);
    }
    @Test(expected = IndexOutOfBoundsException.class)
    public void testPreconditionNextBytes3() {
        final int size = 10;
        final int offset = 2;
        final byte[] buf = new byte[size];
        generator.nextBytes(buf, offset, size - offset + 1);
    }
    @Test(expected = IndexOutOfBoundsException.class)
    public void testPreconditionNextBytes4() {
        final int size = 10;
        final int offset = 1;
        final byte[] buf = new byte[size];
        generator.nextBytes(buf, offset, -1);
    }


    // Uniformity tests

    @Test
    public void testUniformNextBytesFullBuffer() {
        // Value chosen to exercise all the code lines in the
        // "nextBytes" methods.
        final int size = 23;
        final byte[] buffer = new byte[size];

        final Runnable nextMethod = new Runnable() {
            @Override
            public void run() {
                generator.nextBytes(buffer);
            }
        };

        Assert.assertTrue(isUniformNextBytes(buffer, 0, size, nextMethod));
    }

    @Test
    public void testUniformNextBytesPartialBuffer() {
        final int totalSize = 1234;
        final int offset = 567;
        final int size = 89;

        final byte[] buffer = new byte[totalSize];

        final Runnable nextMethod = new Runnable() {
            @Override
            public void run() {
                generator.nextBytes(buffer, offset, size);
            }
        };

        // Test should pass for the part of the buffer where values are put.
        Assert.assertTrue(isUniformNextBytes(buffer, offset, offset + size, nextMethod));

        // Test must fail for the parts of the buffer where no values are put.
        Assert.assertFalse(isUniformNextBytes(buffer, 0, offset, nextMethod));
        Assert.assertFalse(isUniformNextBytes(buffer, offset + size, buffer.length, nextMethod));
    }

    @Test
    public void testUniformNextIntegerInRange() {
        // Statistical test uses 10 bins so tests are invalid below this level
        checkNextIntegerInRange(10, 1000);
        checkNextIntegerInRange(12, 1000);
        checkNextIntegerInRange(31, 1000);
        checkNextIntegerInRange(32, 1000);
        checkNextIntegerInRange(2016128993, 1000);
        checkNextIntegerInRange(1834691456, 1000);
        checkNextIntegerInRange(869657561, 1000);
        checkNextIntegerInRange(1570504788, 1000);
    }

    @Test
    public void testUniformNextLongInRange() {
        // Statistical test uses 10 bins so tests are invalid below this level
        checkNextLongInRange(11, 1000);
        checkNextLongInRange(19, 1000);
        checkNextLongInRange(31, 1000);
        checkNextLongInRange(32, 1000);

        final long q = Long.MAX_VALUE / 4;
        checkNextLongInRange(q, 1000);
        checkNextLongInRange(2 * q, 1000);
        checkNextLongInRange(3 * q, 1000);
    }

    @Test
    public void testUniformNextFloat() {
        checkNextFloat(1000);
    }

    @Test
    public void testUniformNextDouble() {
        checkNextDouble(1000);
    }

    @Test
    public void testUniformNextIntRandomWalk() {
        final Callable<Boolean> nextMethod = new Callable<Boolean>() {
            @Override
            public Boolean call() throws Exception {
                return generator.nextInt() >= 0;
            }
        };

        checkRandomWalk(1000, nextMethod);
    }

    @Test
    public void testUniformNextLongRandomWalk() {
        final Callable<Boolean> nextMethod = new Callable<Boolean>() {
            @Override
            public Boolean call() throws Exception {
                return generator.nextLong() >= 0;
            }
        };

        checkRandomWalk(1000, nextMethod);
    }

    @Test
    public void testUniformNextBooleanRandomWalk() {
        final Callable<Boolean> nextMethod = new Callable<Boolean>() {
            @Override
            public Boolean call() throws Exception {
                return generator.nextBoolean();
            }
        };

        checkRandomWalk(1000, nextMethod);
    }

    // State save and restore tests.

    @Test
    public void testStateSettable() {
        // Should be fairly large in order to ensure that all the internal
        // state is away from its initial settings.
        final int n = 10000;

        // Save.
        final RandomProviderState state = generator.saveState();
        // Store some values.
        final List<Number> listOrig = makeList(n);
        // Discard a few more.
        final List<Number> listDiscard = makeList(n);
        Assert.assertNotEquals(0, listDiscard.size());
        Assert.assertNotEquals(listOrig, listDiscard);
        // Reset.
        generator.restoreState(state);
        // Replay.
        final List<Number> listReplay = makeList(n);
        Assert.assertNotSame(listOrig, listReplay);
        // Check that the restored state is the same as the original.
        Assert.assertEquals(listOrig, listReplay);
    }

    @Test(expected = IllegalStateException.class)
    public void testStateWrongSize() {
        final RandomProviderState state = new DummyGenerator().saveState();
        // Try to restore with an invalid state (wrong size).
        generator.restoreState(state);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testRestoreForeignState() {
        generator.restoreState(new RandomProviderState() {});
    }


    ///// Support methods below.

    /**
     * Populates a list with random numbers.
     *
     * @param n Loop counter.
     * @return a list containing {@code 11 * n} random numbers.
     */
    private List<Number> makeList(int n) {
        final List<Number> list = new ArrayList<Number>();

        for (int i = 0; i < n; i++) {
            // Append 11 values.
            list.add(generator.nextInt());
            list.add(generator.nextInt(21));
            list.add(generator.nextInt(436));
            list.add(generator.nextLong());
            list.add(generator.nextLong(157894));
            list.add(generator.nextLong(5745833));
            list.add(generator.nextFloat());
            list.add(generator.nextFloat());
            list.add(generator.nextDouble());
            list.add(generator.nextDouble());
            list.add(generator.nextBoolean() ? 1 : 0);
        }

        return list;
    }

    /**
     * Checks that the generator values can be placed into 256 bins with
     * approximately equal number of counts.
     * Test allows to select only part of the buffer for performing the
     * statistics.
     *
     * @param buffer Buffer to be filled.
     * @param first First element (included) of {@code buffer} range for
     * which statistics must be taken into account.
     * @param last Last element (excluded) of {@code buffer} range for
     * which statistics must be taken into account.
     * @param nextMethod Method that fills the given {@code buffer}.
     * @return {@code true} if the distribution is uniform.
     */
    private boolean isUniformNextBytes(byte[] buffer,
                                       int first,
                                       int last,
                                       Runnable nextMethod) {
        final int sampleSize = 10000;

        // Number of possible values (do not change).
        final int byteRange = 256;
        // Chi-square critical value with 256 degrees of freedom
        // and 1% significance level.
        final double chi2CriticalValue = 311.560343;
        // To transform a byte value into its bin index.
        final int byteRangeOffset = 128;

        // Bins.
        final long[] observed = new long[byteRange];
        final double[] expected = new double[byteRange];

        for (int i = 0; i < byteRange; i++) {
            expected[i] = sampleSize * (last - first) / (double) byteRange;
        }

        try {
            for (int k = 0; k < sampleSize; k++) {
                nextMethod.run();

                for (int i = first; i < last; i++) {
                    final byte b = buffer[i];
                    ++observed[b + byteRangeOffset];
                }
            }
        } catch (Exception e) {
            // Should never happen.
            throw new RuntimeException("Unexpected");
        }

        // Compute chi-square.
        double chi2 = 0;
        for (int k = 0; k < byteRange; k++) {
            final double diff = observed[k] - expected[k];
            chi2 += diff * diff / expected[k];
        }

        // Statistics check.
        return chi2 < chi2CriticalValue;
    }

    /**
     * Checks that the generator values can be placed into 2 bins with
     * approximately equal number of counts.
     * The test uses the expectation from a fixed-step "random walk".
     *
     * @param nextMethod Method that returns {@code true} if the generated
     * values are to be placed in the first bin, {@code false} if it must
     * go to the second bin.
     */
    private void checkRandomWalk(int sampleSize,
                                 Callable<Boolean> nextMethod) {
        int walk = 0;

        try {
            for (int k = 0; k < sampleSize; ++k) {
                if (nextMethod.call()) {
                    ++walk;
                } else {
                    --walk;
                }
            }
        } catch (Exception e) {
            // Should never happen.
            throw new RuntimeException("Unexpected");
        }

        final double actual = Math.abs(walk);
        final double max = Math.sqrt(sampleSize) * 2.576;
        Assert.assertTrue(generator + ": Walked too far astray: " + actual +
                          " > " + max +
                          " (test will fail randomly about 1 in 100 times)",
                          actual < max);
    }

    /**
     * Tests uniformity of the distribution produced by {@code nextInt(int)}.
     *
     * @param max Upper bound.
     * @param sampleSize Number of random values generated.
     */
    private void checkNextIntegerInRange(final int max,
                                         int sampleSize) {
        checkNextIntegerInRange(generator, max, sampleSize);
    }

    /**
     * Tests uniformity of the distribution produced by {@code nextInt(int)}.
     *
     * @param rng Generator.
     * @param max Upper bound.
     * @param sampleSize Number of random values generated.
     */
    private void checkNextIntegerInRange(final UniformRandomProvider rng,
                                         final int max,
                                         int sampleSize) {
        final Callable<Integer> nextMethod = new Callable<Integer>() {
            @Override
            public Integer call() throws Exception {
                return rng.nextInt(max);
            }
        };

        checkNextInRange(max, sampleSize, nextMethod);
    }

    /**
     * Tests uniformity of the distribution produced by {@code nextLong(long)}.
     *
     * @param max Upper bound.
     * @param sampleSize Number of random values generated.
     */
    private void checkNextLongInRange(final long max,
                                      int sampleSize) {
        final Callable<Long> nextMethod = new Callable<Long>() {
            @Override
            public Long call() throws Exception {
                return generator.nextLong(max);
            }
        };

        checkNextInRange(max, sampleSize, nextMethod);
    }

    /**
     * Tests uniformity of the distribution produced by {@code nextFloat()}.
     *
     * @param sampleSize Number of random values generated.
     */
    private void checkNextFloat(int sampleSize) {
        final int max = 1234;
        final Callable<Integer> nextMethod = new Callable<Integer>() {
            @Override
            public Integer call() throws Exception {
                return (int) (max * generator.nextFloat());
            }
        };

        checkNextInRange(max, sampleSize, nextMethod);
    }

    /**
     * Tests uniformity of the distribution produced by {@code nextDouble()}.
     *
     * @param sampleSize Number of random values generated.
     */
    private void checkNextDouble(int sampleSize) {
        final int max = 578;
        final Callable<Integer> nextMethod = new Callable<Integer>() {
            @Override
            public Integer call() throws Exception {
                return (int) (max * generator.nextDouble());
            }
        };

        checkNextInRange(max, sampleSize, nextMethod);
    }

    /**
     * Tests uniformity of the distribution produced by the given
     * {@code nextMethod}.
     * It performs a chi-square test of homogeneity of the observed
     * distribution with the expected uniform distribution.
     * Repeat tests are performed at the 1% level and the total number of failed
     * tests is tested at the 0.5% significance level.
     *
     * @param max Upper bound.
     * @param nextMethod method to call.
     * @param sampleSize Number of random values generated.
     */
    private <T extends Number> void checkNextInRange(T max,
                                                     int sampleSize,
                                                     Callable<T> nextMethod) {
        final int numTests = 500;

        // Do not change (statistical test assumes that dof = 9).
        final int numBins = 10; // dof = numBins - 1

        // Set up bins.
        final long n = max.longValue();
        final long[] binUpperBounds = new long[numBins];
        final double step = n / (double) numBins;
        for (int k = 0; k < numBins; k++) {
            binUpperBounds[k] = (long) ((k + 1) * step);
        }
        // Rounding error occurs on the long value of 2305843009213693951L
        binUpperBounds[numBins - 1] = n;

        // Run the tests.
        int numFailures = 0;

        final double[] expected = new double[numBins];
        long previousUpperBound = 0;
        for (int k = 0; k < numBins; k++) {
            final long range = binUpperBounds[k] - previousUpperBound;
            expected[k] = sampleSize * (range / (double) n);
            previousUpperBound = binUpperBounds[k];
        }

        final int[] observed = new int[numBins];
        // Chi-square critical value with 9 degrees of freedom
        // and 1% significance level.
        final double chi2CriticalValue = 21.67;

        try {
            for (int i = 0; i < numTests; i++) {
                Arrays.fill(observed, 0);
                for (int j = 0; j < sampleSize; j++) {
                    final long value = nextMethod.call().longValue();
                    Assert.assertTrue("Range", (value >= 0) && (value < n));

                    for (int k = 0; k < numBins; k++) {
                        if (value < binUpperBounds[k]) {
                            ++observed[k];
                            break;
                        }
                    }
                }

                // Compute chi-square.
                double chi2 = 0;
                for (int k = 0; k < numBins; k++) {
                    final double diff = observed[k] - expected[k];
                    chi2 += diff * diff / expected[k];
                }

                // Statistics check.
                if (chi2 > chi2CriticalValue) {
                    ++numFailures;
                }
            }
        } catch (Exception e) {
            // Should never happen.
            throw new RuntimeException("Unexpected", e);
        }

        // The expected number of failed tests can be modelled as a Binomial distribution
        // B(n, p) with n=500, p=0.01 (500 tests with a 1% significance level).
        // The cumulative probability of the number of failed tests (X) is:
        // x     P(X>x)
        // 10    0.0132
        // 11    0.00521
        // 12    0.00190

        if (numFailures > 11) { // Test will fail with 0.5% probability
            Assert.fail(generator + ": Too many failures for n = " + n +
                        " (" + numFailures + " out of " + numTests + " tests failed)");
        }
    }

    /**
     * @param rng Generator.
     * @param chunkSize Size of the small buffer.
     * @param numChunks Number of chunks that make the large buffer.
     */
    static void checkNextBytesChunks(RestorableUniformRandomProvider rng,
                                     int chunkSize,
                                     int numChunks) {
        final byte[] b1 = new byte[chunkSize * numChunks];
        final byte[] b2 = new byte[chunkSize];

        final RandomProviderState state = rng.saveState();

        // Generate the chunks in a single call.
        rng.nextBytes(b1);

        // Reset to previous state.
        rng.restoreState(state);

        // Generate the chunks in consecutive calls.
        for (int i = 0; i < numChunks; i++) {
            rng.nextBytes(b2);
        }

        // Store last "chunkSize" bytes of b1 into b3.
        final byte[] b3 = new byte[chunkSize];
        System.arraycopy(b1, b1.length - b3.length, b3, 0, b3.length);

        // Sequence of calls must be the same.
        Assert.assertArrayEquals("chunkSize=" + chunkSize + " numChunks=" + numChunks,
                                 b2, b3);
    }

    /**
     * Dummy class for checking that restoring fails when an invalid state is used.
     */
    class DummyGenerator extends org.apache.commons.rng.core.source32.IntProvider {
        /** {@inheritDoc} */
        @Override
        public int next() {
            return 4; // https://www.xkcd.com/221/
        }

        /** {@inheritDoc} */
        @Override
        protected byte[] getStateInternal() {
            return new byte[0];
        }

        /** {@inheritDoc} */
        @Override
        protected void setStateInternal(byte[] s) {
            // No state.
        }
    }
}