/*
 * Copyright (c) 2013, 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.
 */
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.math.BigInteger;
import java.util.HashSet;

//I would like to see the functional tests.
//
//We can take the list of prime numbers [1] as set P, and then check:
// a) numbers in intersect([2;N), P) return isProbablyPrime=true in more
//than >(1 - 1/2^cert) cases;
// b) all numbers in difference([2;N), P) return isProbablyPrime=false
//---
//Wait, this is one is wrong (too general). I meant to say all numbers in
//[2;N) that return isProbablyPrime=false are not in P.
//
//N > 50.000.000 would sound convincing.
//
//I need this list for another reason, so I had preprocessed the first 50M
//primes here:
//  http://cr.openjdk.java.net/~shade/scratch/primes-50M.txt.xz
//---
//Plus the certainty is capped at 100 if the bit length of the big int < 100
//(which is the case for the first 50M primes). For large bit lengths it is
//even less (capped at 4 for > 1024). (IIUC it is (1 - 1/4^N) for N iterations
//[1], for the impl N = certainty/2.)
//
//[1] http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

public class PrimeTest {
    public static void main(String[] args) throws Throwable {
        File primesFile = new File(args[0]);
        int upperBound = Integer.valueOf(args[1]);
        int certainty = Integer.valueOf(args[2]);
        System.out.println("Primes: "+primesFile+"\nN = "+upperBound+
                "\ncertainty = "+certainty);

        boolean primeTest = checkPrime(primesFile, upperBound, certainty);
        System.out.println("Prime test = "+primeTest);

        boolean notPrimeTest = checkNotPrime(primesFile, upperBound, certainty);
        System.out.println("Not-prime test = "+notPrimeTest);

        if (!primeTest || !notPrimeTest) {
            throw new Exception("Test failed!");
        }
        System.out.println("Test succeeded!");
    }

    /**
     * Verifies whether the fraction of probable primes detected in the range
     * [2,upperBound) is at least 1 - 1/2^certainty.
     * 
     * @return true if and only if the test succeeds
     */
    private static boolean checkPrime(File primesFile, int upperBound,
            int certainty) throws FileNotFoundException, IOException {
        BufferedReader reader = new BufferedReader(new FileReader(primesFile));
        BigInteger bigBound = BigInteger.valueOf(upperBound);

        int total = 0;
        int prime = 0;
        String line;
        while ((line = reader.readLine()) != null) {
            BigInteger bigInt = new BigInteger(line);
            if (bigInt.compareTo(bigBound) >= 0) {
                //System.out.println("Break at "+bigInt);
                break;
            }
            total++;
            if (bigInt.isProbablePrime(certainty)) {
                prime++;
            }
        }
        System.out.println(prime+" probable primes out of "+total+" candidates");

        // Success if p/t >= 1 - 1/2^certainty
        // or (p/t)*2^c >= 2^c - 1
        // or p*2^c >= t*(2^c - 1)
        BigInteger p = BigInteger.valueOf(prime);
        BigInteger t = BigInteger.valueOf(total);
        BigInteger twoToTheC = BigInteger.ONE.shiftLeft(certainty);
        BigInteger twoToTheCMinusOne = twoToTheC.subtract(BigInteger.ONE);
        BigInteger left = p.multiply(twoToTheC);
        BigInteger right = t.multiply(twoToTheCMinusOne);
        return left.compareTo(right) >= 0;
    }

    /**
     * Verifies whether all {@code BigInteger}s in the range [2,upperBound) 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 checkNotPrime(File primesFile, int upperBound,
            int certainty) throws FileNotFoundException, IOException {
        BufferedReader reader = new BufferedReader(new FileReader(primesFile));
        HashSet<Integer> primes = new HashSet<Integer>(upperBound);
        String line;
        while ((line = reader.readLine()) != null) {
            Integer primeValue = Integer.valueOf(line);
            if (primeValue >= upperBound) {
                //System.out.println("Break at "+primeValue);
                break;
            }
            primes.add(primeValue);
        }
        reader.close();

        boolean result = true;
        for (int i = 2; i < upperBound; i++) {
            BigInteger bigInt = BigInteger.valueOf(i);
            if (!bigInt.isProbablePrime(certainty) &&
                    primes.contains(Integer.valueOf(i))) {
                result = false;
                break;
            }
        }

        return result;
    }
}