/*
 * GFPolynomial.java - Implements A polynomial over a Finite Field GF(p^m).
 *
 * ------------------------------------------------------------------
 *
 * @begin[license]
 * Copyright (C) 2003  Kai Chen, Caltech
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program 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 for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * @author: Kai Chen
 * @email{kchen@cs.caltech.edu}
 * @end[license]
 *
 */


public class GFPolynomial
{
    /* The field the polynomial is over */
    protected GF gf;
    /* Coefficients of the polynomial */
    protected int coeff[];
    /* Degree of the polynomial */
    protected int degree;



    /*
     * post: constructs a default polynomial
     */
    public GFPolynomial()
    {
        /* construct a default GF */
        this.gf = new GF();
        /* the default polynomial is zero */
        this.coeff = new int[1];
        this.coeff[0] = 0;
        this.degree = 0;
    }


    /*
     * post: constructs a zero polynomial over gf
     */
    public GFPolynomial(GF gf)
    {
        this(gf, 0);
    }
    
    
    /* 
     * post: constructs a polynomial over gf with degree zero
     */
    public GFPolynomial(GF gf, int c0)
    {
        this.gf = gf;
        this.coeff = new int[1];
        this.coeff[0] = c0;
        this.degree = 0;
    }

    
    /*
     * post: constructs a polynomial over gf with coeff
     */
    public GFPolynomial(GF gf, int coeff[])
    {
        this.gf = gf;
        setCoeff(coeff);
    }


    /*
     * post: sets the coefficients of the polynomial
     */
    public void setCoeff(int coeff[])
    {
        this.coeff = coeff;

        /* set the degree */
        for(degree=coeff.length-1; degree>0 && coeff[degree]==0; degree--);
    }


    /*
     * post: returns the coefficients of the polynomial
     */
    public int[] getCoeff()
    {
        return coeff;
    }


    /*
     * post: returns the i-th coefficient of the polynomial
     */
    public int getCoeffAt(int i)
    {
        return (i<0 || i>degree) ? 0 : coeff[i];
    }


    /*
     * post: sets the degree of the polynomial.
     */
    public void setDegree(int deg)
    {
        /* not allowed to set a higher degree */
        if(deg < degree)
            for(degree=deg; degree>0 && coeff[degree]==0; degree--);
    }


    /*
     * post: returns the degree of the polynomial
     */
    public int getDegree()
    {
        return degree;
    }


    /*
     * post: sets the GF of the polynomial
     */
    public void setGF(GF gf)
    {
        this.gf = gf;
    }


    /*
     * post: returns the gf of the polynomial
     */
    public GF getGF()
    {
        return gf;
    }


    /*
     * post: returns true if the polynomial is the zero-poly
     */
    public boolean isZero()
    {
        return (degree==0 && getCoeffAt(0)==0);
    }
        
    
    /*
     * pre: polynomial 'other' is over the same GF
     * post: returns the sum of the two polynomials
     */
    public GFPolynomial add(GFPolynomial other)
    {
        int d = getDegree()>other.getDegree() ? getDegree() : other.getDegree();
        int sum[] = new int[d+1];

        for(int i=0; i<=d; i++)
            sum[i] = gf.add(getCoeffAt(i), other.getCoeffAt(i));

        return new GFPolynomial(gf, sum);
    }


    /*
     * pre: polynomial 'other' is over the same GF
     * post: returns the difference between the two polynomials
     */
    public GFPolynomial sub(GFPolynomial other)
    {
        int d = getDegree()>other.getDegree() ? getDegree() : other.getDegree();
        int diff[] = new int[d+1];

        for(int i=0; i<=d; i++)
            diff[i] = gf.sub(getCoeffAt(i), other.getCoeffAt(i));

        return new GFPolynomial(gf, diff);
    }


    /*
     * post: returns the additive inverse of this polynomial
     */
    public GFPolynomial neg()
    {
        return new GFPolynomial(gf).sub(this);
    }
    
    /*
     * pre: polynomial 'other' is over the same GF
     * post: returns the product of the two polynomials
     */
    public GFPolynomial mul(GFPolynomial other)
    {
        int d = getDegree() + other.getDegree();
        int prod[] = new int[d+1];

        for(int i=0; i<=getDegree(); i++)
            for(int j=0; j<=other.getDegree(); j++)
                prod[i+j] = gf.add(prod[i+j], 
                    gf.mul(getCoeffAt(i), other.getCoeffAt(j)));
        
        return new GFPolynomial(gf, prod);
    }
    

    /* 
     * post: returns the resulting polynomial of scaler multiplication
     */
    public GFPolynomial mulScaler(int c)
    {
        if(c==0) return new GFPolynomial(gf);
       
        int prod[] = new int[getDegree()+1];

        for(int i=0; i<=getDegree(); i++)
            prod[i] = gf.mul(getCoeffAt(i), c);

        return new GFPolynomial(gf, prod);
    }


    /*
     * pre: polynomial 'other' is over the same GF
     * post: returns the quotient of the two polynomials
     */
    public GFPolynomial div(GFPolynomial other) throws RSException
    {
        if(other.isZero()) 
            throw new RSException("GFPolynomial.div: other poly is zero");
            
        if(getDegree()<other.getDegree()) return new GFPolynomial(gf);

        /* degree of the quotient polynomial */
        int d = getDegree() - other.getDegree();
        
        /* 
         * inverse of the leading coefficient of other, 
         * will be used to generate quotient. 
         */
        int invOfLeadingCoeff = gf.inv(other.getCoeffAt(other.getDegree()));
        
        /* quotient and remainder polynomials */ 
        int quotient[] = new int[d+1];
        int remainder[] = (int[]) coeff.clone();

        for(int i=d; i>=0; i--){
            /* compute quotient */
            quotient[i] = 
                gf.mul(remainder[i+other.getDegree()], invOfLeadingCoeff);

            /* update remainder */
            for(int j=0; j<=other.getDegree(); j++)
                remainder[i+j] = gf.sub(remainder[i+j], 
                    gf.mul(quotient[i], other.getCoeffAt(j)));
        }

        return new GFPolynomial(gf, quotient);
    }


    /*
     * post: returns the resulting polynomial of scaler division 
     */
    public GFPolynomial divScaler(int c) throws RSException
    {
        return mulScaler(gf.inv(c));
    }


    /*
     * pre: this polynomial is not zero
     * post: returns the multiplicative inverse of this polynomial
     */
    public GFPolynomial inv() throws RSException
    {
        if(isZero()){
            throw new RSException
                ("GFPolynomial.isZero: Zero polynomial has no inverse.");
        }

        return new GFPolynomial(gf, 1).div(this);
    }

    
    /*
     * post: evaluates the polynomial at x
     */
    public int eval(int x)
    {
        /* the function value */
        int f=0;

        /* evaluate f(x) */
        for(int i=0, powerOfX=gf.getUnity(); 
            i<=getDegree(); 
            i++, powerOfX=gf.mul(powerOfX, x))
            f = gf.add(f, gf.mul(getCoeffAt(i), powerOfX));

        return f;
    }
    

    /*
     * post: computes the derivative of the polynomial
     */
    public GFPolynomial deriv()
    {
        int derivative[] = new int[getDegree()];

        for(int i=0; i<getDegree(); i++)
            derivative[i] = gf.mul(getCoeffAt(i+1), (i+1)%gf.getP());

        return new GFPolynomial(gf, derivative);
    }

   
    /*
     * post: computes the Discrete Fourier Transformation of length r vector
     */
    public GFPolynomial dft(int r)
    {
        /* frequency domain components */
        int freq[] = new int[r];

        /* V_hat_i = V(alpha^(i)) */
        for(int i=0; i<r; i++)
            freq[i] = eval(gf.power(i));

        return new GFPolynomial(gf, freq);
    }
    
    
    /* 
     * post: computes the Discrete Fourier Transformation 
     */
    public GFPolynomial dft()
    {
        return dft(getDegree()+1);
    }
    

    /* 
     * post: computes the Inverse Discrete Fourier Transformation of length r
     */
    public GFPolynomial idft(int r) throws RSException
    {
        int time[] = new int[r];

        /*
         * V_i = (1/n)V_hat(alpha^(-i))
         * we need to be careful about the 1/n in the front
         */
        if(r%gf.getP()!=0)
            for(int i=0; i<r; i++)
                time[i] = gf.div(eval(gf.power(-i)), (r%gf.getP()));

        return new GFPolynomial(gf, time);
    }
    
            
    /* 
     * post: computes the Inverse Discrete Fourier Transformation
     */
    public GFPolynomial idft() throws RSException
    {
        return idft(getDegree() + 1);
    }
    
    
    /*
     * for printing, 
     */
    public String toString(int n)
    {
        StringBuffer sb = new StringBuffer();

        sb.append("<");
        
        for(int i=0; i<=getDegree(); i++)
            sb.append(" "+Integer.toString(getCoeffAt(i)));
            
        for(int i=getDegree()+1; i<n; i++)
            sb.append(" 0");
            
        sb.append(" >");

        return sb.toString();
    }


    /*
     * print up to highest degree
     */
    public String toString()
    {
        return toString(getDegree()+1);
    }
    
    /*
     * A test drive for GFPolynomial
     */
    public static void main(String[] args)
    {
        /* This corresponds to Example 9.8 in the red book */
        int poly[] = {1, 1, 0, 1};
        GF gf = new GF(2, 3, poly);
        
        int sigma_coeff[] = {1, gf.power(5), gf.power(5)};
        GFPolynomial sigma = new GFPolynomial(gf, sigma_coeff);
        System.out.println(sigma);

        int v_coeff[] = {gf.power(5), gf.power(3), gf.power(3)};
        GFPolynomial v = new GFPolynomial(gf, v_coeff);
        System.out.println(v);
        
        sigma = v.mulScaler(gf.power(-5));
        System.out.println(sigma);

        int omega_coeff[] = {gf.power(3), gf.power(2)};
        GFPolynomial omega = new GFPolynomial(gf, omega_coeff);
        System.out.println(omega);
        
        int r_coeff[] = {gf.power(1), 1};
        GFPolynomial r = new GFPolynomial(gf, r_coeff);
        System.out.println(r);

        omega = r.mulScaler(gf.power(-5));
        System.out.println(omega);

        GFPolynomial sigma_deriv = sigma.deriv();
        System.out.println(sigma_deriv);

        int result_coeff[] = {gf.power(5), gf.power(4)};
        GFPolynomial result = new GFPolynomial(gf, result_coeff);
        System.out.println(result);

        try{
            result = omega.div(sigma_deriv);
            System.out.println(result);
        }catch(RSException ex){
            ex.printStackTrace();
        }
    }
}