package meerkat.crypto.secretsharing.shamir;

import meerkat.crypto.utils.Arithmetic;

import java.math.BigInteger;
import java.util.Arrays;

/**
 * Created by Tzlil on 1/27/2016.
 */
public class Polynomial implements Comparable<Polynomial> {
    private final int degree;
    private final BigInteger[] coefficients;
    private final Arithmetic<BigInteger> arithmetic;

    /**
     * constructor
     * @param coefficients
     * @param arithmetic
     *        degree set as max index such that coefficients[degree] not equals zero
     */
    public Polynomial(BigInteger[] coefficients,Arithmetic<BigInteger> arithmetic) {
        int d = coefficients.length - 1;
        while (d >  0 && coefficients[d].equals(BigInteger.ZERO)){
            d--;
        }
        this.degree = d;
        this.coefficients = coefficients;
        this.arithmetic = arithmetic;
    }

    /**
     * Compare to another polynomial (order by degree, then coefficients).
     */
    @Override
    public int compareTo(Polynomial other) {
        if (this.degree != other.degree)
            return this.degree - other.degree;
        int compare;
        for (int i = degree; i >= degree ; i--){
            compare = this.coefficients[i].compareTo(other.coefficients[i]);
            if (compare != 0){
                return compare;
            }
        }
        return 0;
    }

    /**
     * @param x
     * @return sum of coefficients[i] * (x ^ i)
     */
    public BigInteger evaluate(BigInteger x){
        BigInteger result = BigInteger.ZERO;
        BigInteger power = BigInteger.ONE;
        for(int i = 0 ; i <= degree ; i++){
            result = arithmetic.add(result,arithmetic.mul(coefficients[i],power));
            power = power.multiply(x);
        }
        return result;
    }

    /**
     * @param points
     * @return polynomial of minimal degree which goes through all points.
     *  If there exists i != j s.t points[i].x == points[j].x, method returns null.
     */
    public static Polynomial interpolation(Point[] points, Arithmetic<BigInteger> arithmetic) {
        LagrangePolynomial[] l = LagrangePolynomial.lagrangePolynomials(points,arithmetic);
        if (l == null){
            return null;
        }
        // product = product of l[i].divisor
        BigInteger product = BigInteger.ONE;
        for (int i = 0; i < l.length;i++){
            product = arithmetic.mul(product,l[i].divisor);
        }

        // factor[i] = product divided by l[i].divisor = product of l[j].divisor s.t j!=i
        BigInteger[] factors = new BigInteger[l.length];
        for (int i = 0; i < l.length;i++){
            factors[i] = arithmetic.div(product,l[i].divisor);
        }
        int degree = l[0].polynomial.degree;

        // coefficients[j] = (sum of l[i].evaluate * factor[i] * l[i].coefficients[j] s.t i!=j) divide by product =
        //                 =  sum of l[i].evaluate * l[i].coefficients[j] / l[i].divisor s.t i!=j
        BigInteger[] coefficients = new BigInteger[degree + 1];
        for (int j = 0; j < coefficients.length;j++){
            coefficients[j] = BigInteger.ZERO;
            for (int i = 0; i < l.length; i++){
                BigInteger current = arithmetic.mul(l[i].image,factors[i]);
                current = arithmetic.mul(current,l[i].polynomial.coefficients[j]);
                coefficients[j] = arithmetic.add(coefficients[j],current);
            }
            coefficients[j] = arithmetic.div(coefficients[j],product);
        }
        return new Polynomial(coefficients,arithmetic);
    }

    /**
     * @param other
     * @return new Polynomial of degree max(this degree,other degree) s.t for all x
     *         new.evaluate(x) = this.evaluate(x) + other.evaluate(x)
     */
    public Polynomial add(Polynomial other){
        Polynomial bigger,smaller;
        if(this.degree < other.degree){
            bigger = other;
            smaller = this;
        }else{
            bigger = this;
            smaller = other;
        }
        BigInteger[] coefficients = bigger.getCoefficients();

        for (int i = 0; i <= smaller.degree ; i++){
            coefficients[i] = arithmetic.add(smaller.coefficients[i],bigger.coefficients[i]);
        }
        return  new Polynomial(coefficients,other.arithmetic);
    }

    /**
     * @param constant
     * @return new Polynomial of degree this.degree s.t for all x
     *         new.evaluate(x) = constant * this.evaluate(x)
     */
    public Polynomial mul(BigInteger constant){

        BigInteger[] coefficients = this.getCoefficients();

        for (int i = 0; i <= this.degree ; i++){
            coefficients[i] = arithmetic.mul(constant,coefficients[i]);
        }
        return  new Polynomial(coefficients,arithmetic);
    }

    /**
     * @param other
     * @return new Polynomial of degree this degree + other degree + 1 s.t for all x
     *         new.evaluate(x) = this.evaluate(x) * other.evaluate(x)
     */
    public Polynomial mul(Polynomial other){

        BigInteger[] coefficients = new BigInteger[this.degree + other.degree + 1];
        Arrays.fill(coefficients,BigInteger.ZERO);

        for (int i = 0; i <= this.degree ; i++){
            for (int j = 0; j <= other.degree; j++){
                coefficients[i+j] = arithmetic.add(coefficients[i+j],arithmetic.mul(this.coefficients[i],other.coefficients[j]));
            }
        }
        return  new Polynomial(coefficients,arithmetic);
    }


    /** getter
     * @return copy of coefficients
     */
    public BigInteger[] getCoefficients() {
        return Arrays.copyOf(coefficients,coefficients.length);
    }

    /** getter
     * @return degree
     */
    public int getDegree() {
        return degree;
    }

    /**
     * inner class
     * container for (x,y) x from range and y from evaluate of polynomial
     */
    public static class Point implements java.io.Serializable {
        public final BigInteger x;
        public final BigInteger y;

        /**
         * constructor
         * @param x
         * @param polynomial y = polynomial.evaluate(x)
         */
        public Point(BigInteger x, Polynomial polynomial) {
            this.x = x;
            this.y = polynomial.evaluate(x);
        }

        /**
         * constructor
         * @param x
         * @param y
         */
        public Point(BigInteger x,BigInteger y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            //TODO: is this implementation correct? cannot understand its logic (hai)
            if(!super.equals(obj))
                return false;
            Point other = (Point)obj;
            return this.x.equals(other.x) && this.y.equals(other.y);
        }
    }

}
