/*
 * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

/*
 * @test
 * @bug 8026236
 * @summary test primality verification methods in BigInteger
 * @author bpb
 */
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.net.URL;
import java.util.NavigableSet;
import java.util.Random;
import java.util.TreeSet;
import static java.util.stream.Collectors.toCollection;
import java.util.stream.Stream;
import java.util.zip.GZIPInputStream;

public class PrimeTest {

    private static final String DEFAULT_PRIMES_FILE = "primes-100000.txt.gz";
    private static final int DEFAULT_MAX_NUM_PRIMES = 1000000;
    private static final int DEFAULT_CERTAINTY = 100;
    private static final int NUM_NON_PRIMES = 10000;
    private static final String DEFAULT_PRIMES_SOURCE;

    // Set up default prime number source
    static {
        try {
            String dir = System.getProperty("test.src", ".");
            File testFile = new File(dir, DEFAULT_PRIMES_FILE);
            DEFAULT_PRIMES_SOURCE = testFile.getAbsolutePath();
        } catch (Throwable t) {
            throw new Error(t);
        }
    }

    /**
     * Run the test.
     *
     * @param args The parameters. The zeroth parameter should be either a file
     * path or a URL string.
     * @throws Throwable
     */
    public static void main(String[] args) throws Throwable {
        // Prepare arguments
        String primesSource = args.length > 0 ? args[0] : DEFAULT_PRIMES_SOURCE;
        int maxNumPrimes = args.length > 1 ? Integer.valueOf(args[1]) : DEFAULT_MAX_NUM_PRIMES;
        int certainty = args.length > 2 ? Integer.valueOf(args[2]) : DEFAULT_CERTAINTY;
        boolean parallel = args.length > 3 ? Boolean.valueOf(args[3]) : true;

        // Echo parameter settings
        System.out.println("Primes source: " + primesSource + "\nupper bound = " + maxNumPrimes
                + "\ncertainty = " + certainty
                + "\nparallel = " + parallel);

        // Check whether known primes are identified as such
        boolean primeTest = checkPrime(primesSource, maxNumPrimes, certainty, parallel);
        System.out.println("Prime test result: " + (primeTest ? "SUCCESS" : "FAILURE"));
        if (!primeTest) {
            System.err.println("Prime test failed");
        }

        // Check whether known non-primes are not identified as primes
        boolean nonPrimeTest = checkNonPrime(primesSource, maxNumPrimes, certainty);
        System.out.println("Non-prime test result: " + (nonPrimeTest ? "SUCCESS" : "FAILURE"));

        if (!primeTest || !nonPrimeTest) {
            throw new Exception("PrimeTest FAILED!");
        }

        System.out.println("PrimeTest succeeded!");
    }

    /**
     * Parse the primes into a list of [@code BigInteger}s.
     *
     * @param gis InputStream of prime numbers assumed to be from a GZIPped text
     * file with one number per line in the default character set
     * @param n The maximum number of primes to load
     * @return A {@code NavigableSet<BigInteger>} containing the loaded primes
     * @throws IOException If something nasty happens
     */
    private static NavigableSet<BigInteger> parsePrimesStream(InputStream is, long n) throws IOException {
        GZIPInputStream gis = new GZIPInputStream(is);
        BufferedReader br = new BufferedReader(new InputStreamReader(gis));
        try (Stream<String> lines = br.lines()) {
            return lines.limit(n).map(BigInteger::new).collect(toCollection(TreeSet::new));
        }
    }

    private static NavigableSet<BigInteger> parsePrimesFile(File f, long n) throws IOException {
        InputStream gis = new FileInputStream(f);
        return parsePrimesStream(gis, n);
    }

    private static NavigableSet<BigInteger> parsePrimesURL(URL u, long n) throws IOException {
        InputStream is = u.openStream();
        return parsePrimesStream(is, n);
    }

    private static NavigableSet<BigInteger> parsePrimes(String primesSource, long n) throws IOException {
        File file = new File(primesSource);
        if (file.exists()) {
            return parsePrimesFile(file, n);
        } else {
            URL url = new URL(primesSource);
            return parsePrimesURL(url, n);
        }
    }

    /**
     * Verifies whether the fraction of probable primes detected is at least 1 -
     * 1/2^certainty.
     *
     * @return true if and only if the test succeeds
     */
    private static boolean checkPrime(String primesSource, int maxNumPrimes,
            int certainty,
            boolean parallel) throws FileNotFoundException, IOException {

        NavigableSet<BigInteger> primes = parsePrimes(primesSource, maxNumPrimes);

        System.out.println(String.format("Loaded %d primes", primes.size()));

        long probablePrimes = (parallel ? primes.parallelStream() : primes.stream())
                .filter(bi -> bi.isProbablePrime(certainty))
                .count();

        System.out.println(probablePrimes + " probable primes out of "
                + primes.size() + " candidates");
        if (probablePrimes != primes.size()) {
            System.err.println("Number of probable primes unequal to number of actual primes");
        }

        // N = certainty / 2
        // Success if p/t >= 1 - 1/4^N
        // or (p/t)*4^N >= 4^N - 1
        // or p*4^N >= t*(4^N - 1)
        BigInteger p = BigInteger.valueOf(probablePrimes);
        BigInteger t = BigInteger.valueOf(primes.size());
        BigInteger fourToTheC = BigInteger.valueOf(4).pow(certainty / 2);
        BigInteger fourToTheCMinusOne = fourToTheC.subtract(BigInteger.ONE);
        BigInteger left = p.multiply(fourToTheC);
        BigInteger right = t.multiply(fourToTheCMinusOne);

        if (left.compareTo(right) < 0) {
            System.err.println("Probable prime certainty test failed.");
        }

        return left.compareTo(right) >= 0;
    }

    /**
     * Verifies whether all {@code BigInteger}s in the tested range for which
     * {@code isProbablePrime()} returns {@code false} are <i>not</i>
     * prime numbers.
     *
     * @return true if and only if the test succeeds
     */
    private static boolean checkNonPrime(String primesSource, int maxNumPrimes,
            int certainty) throws FileNotFoundException, IOException {
        NavigableSet<BigInteger> primes = parsePrimes(primesSource, maxNumPrimes);

        int maxPrime = 100000;
        try {
            maxPrime = primes.last().intValueExact();
        } catch (ArithmeticException e) {
            // ignore it
        }

        // If it's not a probable prime but is in the primes list then fail.
        boolean result = !(new Random()).ints(NUM_NON_PRIMES, 2, maxPrime).mapToObj(BigInteger::valueOf).filter(b -> !b.isProbablePrime(certainty)).anyMatch(primes::contains);

        return result;
    }
}