/*
 * $Id$
 */

package edu.jas.structure;


import java.util.List;

import org.apache.log4j.Logger;


/**
 * Power class to compute powers of RingElem.
 * @author Heinz Kredel
 */
public class Power> {


    private static final Logger logger = Logger.getLogger(Power.class);


    private static boolean debug = logger.isDebugEnabled();


    private final RingFactory fac;


    /**
     * The constructor creates a Power object.
     */
    public Power() {
        this(null);
    }


    /**
     * The constructor creates a Power object.
     * @param fac ring factory
     */
    public Power(RingFactory fac) {
        this.fac = fac;
    }


    /**
     * power of a to the n-th, n positive.
     * @param a element.
     * @param n integer exponent > 0.
     * @return a^n.
     */
    public static > C positivePower(C a, long n) {
        if (n <= 0) {
            throw new IllegalArgumentException("only positive n allowed");
        }
        if (a.isZERO() || a.isONE()) {
            return a;
        }
        C b = a;
        long i = n - 1;
        C p = b;
        do {
            if (i % 2 == 1) {
                p = p.multiply(b);
            }
            i = i / 2;
            if (i > 0) {
                b = b.multiply(b);
            }
        } while (i > 0);
        return p;
    }


    /**
     * power of a to the n-th, n positive.
     * @param a element.
     * @param n java.math.BigInteger exponent > 0.
     * @return a^n.
     */
    public static > C positivePower(C a, java.math.BigInteger n) {
        if (n.signum() <= 0) {
            throw new IllegalArgumentException("only positive n allowed");
        }
        if (a.isZERO() || a.isONE()) {
            return a;
        }
        C b = a;
        if (n.compareTo(java.math.BigInteger.ONE) == 0) {
            return b;
        }
        C p = a;
        java.math.BigInteger i = n.subtract(java.math.BigInteger.ONE);
        do {
            if (i.testBit(0)) {
                p = p.multiply(b);
            }
            i = i.shiftRight(1);
            if (i.signum() > 0) {
                b = b.multiply(b);
            }
        } while (i.signum() > 0);
        return p;
    }


    /**
     * power of a to the n-th, n positive, modulo m.
     * @param a element.
     * @param n integer exponent > 0.
     * @param m modulus.
     * @return a^n mod m.
     */
    public static > C modPositivePower(C a, long n, C m) {
        if (n <= 0) {
            throw new IllegalArgumentException("only positive n allowed");
        }
        if (a.isZERO() || a.isONE()) {
            return a;
        }

        C b = a.remainder(m);
        long i = n - 1;
        C p = b;
        do {
            if (i % 2 == 1) {
                p = p.multiply(b).remainder(m);
            }
            i = i / 2;
            if (i > 0) {
                b = b.multiply(b).remainder(m);
            }
        } while (i > 0);
        return p;
    }


    /**
     * power of a to the n-th.
     * @param a element.
     * @param n integer exponent.
     * @param fac ring factory.
     * @return a^n, with 0^0 = 0 and a^{-n} = {1/a}^n.
     */
    @SuppressWarnings("unchecked")
    public static > C power(RingFactory fac, C a, long n) {
        if (a == null || a.isZERO()) {
            return a;
        }
        //return a;
        return (C) Power. power((MonoidFactory) fac, a, n);
    }


    /**
     * power of a to the n-th.
     * @param a element.
     * @param n integer exponent.
     * @param fac monoid factory.
     * @return a^n, with a^{-n} = {1/a}^n.
     */
    public static > C power(MonoidFactory fac, C a, long n) {
        if (n == 0) {
            if (fac == null) {
                throw new IllegalArgumentException("fac may not be null for a^0");
            }
            return fac.getONE();
        }
        if (a.isONE()) {
            return a;
        }
        C b = a;
        if (n < 0) {
            b = a.inverse();
            n = -n;
        }
        if (n == 1) {
            return b;
        }
        C p = fac.getONE();
        long i = n;
        do {
            if (i % 2 == 1) {
                p = p.multiply(b);
            }
            i = i / 2;
            if (i > 0) {
                b = b.multiply(b);
            }
        } while (i > 0);
        if (n > 11 && debug) {
            logger.info("n  = " + n + ", p  = " + p);
        }
        return p;
    }


    /**
     * power of a to the n-th modulo m.
     * @param a element.
     * @param n integer exponent.
     * @param m modulus.
     * @param fac monoid factory.
     * @return a^n mod m, with a^{-n} = {1/a}^n.
     */
    public static > C modPower(MonoidFactory fac, C a, long n, C m) {
        if (n == 0) {
            if (fac == null) {
                throw new IllegalArgumentException("fac may not be null for a^0");
            }
            return fac.getONE();
        }
        if (a.isONE()) {
            return a;
        }
        C b = a.remainder(m);
        if (n < 0) {
            b = a.inverse().remainder(m);
            n = -n;
        }
        if (n == 1) {
            return b;
        }
        C p = fac.getONE();
        long i = n;
        do {
            if (i % 2 == 1) {
                p = p.multiply(b).remainder(m);
            }
            i = i / 2;
            if (i > 0) {
                b = b.multiply(b).remainder(m);
            }
        } while (i > 0);
        if (n > 11 && debug) {
            logger.info("n  = " + n + ", p  = " + p);
        }
        return p;
    }


    /**
     * power of a to the n-th modulo m.
     * @param a element.
     * @param n integer exponent.
     * @param m modulus.
     * @param fac monoid factory.
     * @return a^n mod m, with a^{-n} = {1/a}^n.
     */
    public static > C modPower(MonoidFactory fac, C a, java.math.BigInteger n, C m) {
        if (n.signum() == 0) {
            if (fac == null) {
                throw new IllegalArgumentException("fac may not be null for a^0");
            }
            return fac.getONE();
        }
        if (a.isONE()) {
            return a;
        }
        C b = a.remainder(m);
        if (n.signum() < 0) {
            b = a.inverse().remainder(m);
            n = n.negate();
        }
        if (n.compareTo(java.math.BigInteger.ONE) == 0) {
            return b;
        }
        C p = fac.getONE();
        java.math.BigInteger i = n;
        do {
            if (i.testBit(0)) {
                p = p.multiply(b).remainder(m);
            }
            i = i.shiftRight(1);
            if (i.signum() > 0) {
                b = b.multiply(b).remainder(m);
            }
        } while (i.signum() > 0);
        if (debug) {
            logger.info("n  = " + n + ", p  = " + p);
        }
        return p;
    }


    /**
     * power of a to the n-th.
     * @param a element.
     * @param n integer exponent.
     * @return a^n, with 0^0 = 0.
     */
    public C power(C a, long n) {
        return power(fac, a, n);
    }


    /**
     * power of a to the n-th mod m.
     * @param a element.
     * @param n integer exponent.
     * @param m modulus.
     * @return a^n mod m, with 0^0 = 0.
     */
    public C modPower(C a, long n, C m) {
        return modPower(fac, a, n, m);
    }


    /**
     * power of a to the n-th mod m.
     * @param a element.
     * @param n integer exponent.
     * @param m modulus.
     * @return a^n mod m, with 0^0 = 0.
     */
    public C modPower(C a, java.math.BigInteger n, C m) {
        return modPower(fac, a, n, m);
    }


    /**
     * Logarithm.
     * @param p logarithm base.
     * @param a element.
     * @return k ≥ 1 minimal with p^k ≥ b.
     */
    public static > long logarithm(C p, C a) {
        //if ( p.compareTo(a) < 0 ) {
        //    return 0L;
        //}
        long k = 1L;
        C m = p;
        while (m.compareTo(a) < 0) {
            m = m.multiply(p);
            k++;
        }
        return k;
    }


    /**
     * Multiply elements in list.
     * @param A list of elements (a_0,...,a_k).
     * @param fac ring factory.
     * @return prod(i=0,...k) a_i.
     */
    public static > C multiply(RingFactory fac, List A) {
        return multiply((MonoidFactory) fac, A);
    }


    /**
     * Multiply elements in list.
     * @param A list of elements (a_0,...,a_k).
     * @param fac monoid factory.
     * @return prod(i=0,...k) a_i.
     */
    public static > C multiply(MonoidFactory fac, List A) {
        if (fac == null) {
            throw new IllegalArgumentException("fac may not be null for empty list");
        }
        C res = fac.getONE();
        if (A == null || A.isEmpty()) {
            return res;
        }
        for (C a : A) {
            res = res.multiply(a);
        }
        return res;
    }


    /**
     * Sum elements in list.
     * @param A list of elements (a_0,...,a_k).
     * @param fac ring factory.
     * @return sum(i=0,...k) a_i.
     */
    public static > C sum(RingFactory fac, List A) {
        return sum((AbelianGroupFactory) fac, A);
    }


    /**
     * Sum elements in list.
     * @param A list of elements (a_0,...,a_k).
     * @param fac monoid factory.
     * @return sum(i=0,...k) a_i.
     */
    public static > C sum(AbelianGroupFactory fac, List A) {
        if (fac == null) {
            throw new IllegalArgumentException("fac may not be null for empty list");
        }
        C res = fac.getZERO();
        if (A == null || A.isEmpty()) {
            return res;
        }
        for (C a : A) {
            res = res.sum(a);
        }
        return res;
    }

}