"""
Polynomial class
by Kirby Urner, Oregon Curriculum Network w/ thanks to
Brent Burley et al

First posted:  May 1, 2001
Most recently modified:  May 1, 2001

For background see:
http://www.mathforum.com/epigone/k12.ed.math/blunpharthah
http://mail.python.org/pipermail/edu-sig/2001-April/date.html
http://mail.python.org/pipermail/edu-sig/2001-May/date.html
"""

class Poly:
    """
    Build a polynomial function object from coefficients
    """
  
    def __init__(self, coeffs):
        self.coeffs = []
        if len(coeffs)==0:  self.coeffs=[0]
        else:
           for c1 in range(len(coeffs)):
               if coeffs[c1]<>0:
                  break
           self.coeffs = coeffs[c1:]
        self.degree = len(self.coeffs)-1
        self.strview = self._express()
 
    def __call__(self,x):
        return eval(self.strview)

    def __repr__(self):
        return self.strview
    
    def _express(self):
        """
        Represent self as an algebraic expression
        """
        expr = ""
        exponent = self.degree            
        for coeff in self.coeffs:

            if coeff <> 0:
               if coeff>0:  sign = " + "
               else:        sign = " - "
                     
               if abs(coeff) == 1:  strcoeff = ""
               else: strcoeff = str(abs(coeff))+ "*"                                          
                           
               if exponent > 1:
     	          expr = (expr+sign+strcoeff+"x**"+str(exponent))
  	       elif exponent == 1:
                  expr = expr+sign+strcoeff+"x"
               elif exponent == 0:
                  expr = expr+sign+str(abs(coeff))
                  
            exponent = exponent - 1
               
        if    len(expr)==0: expr = '0'
        elif  expr[1]=="-": expr = expr[1]+expr[3:]
        else: expr = expr[3:]
        return expr

    def deriv(self):
        """
        Return the derivative of self as another polynomial
        """
        exponent = self.degree
        newcoeffs = []
        for coeff in self.coeffs[:-1]:
            newcoeffs.append(coeff * exponent)
            exponent = exponent - 1
        return Poly(newcoeffs)

    def __add__(self, other):
        """
        Add self and other polynomial
        """
        newcoeffs = []
        exponent = self.degree
        if type(other) == type(3):
            other = Poly([other])
        # Pad with 0s to make len(coeffs) >= len(other.coeffs)
        if exponent < other.degree:
            coeffs = [0]*(other.degree - exponent) + self.coeffs
            exponent = other.degree
        else:
            coeffs = self.coeffs
        for coeff in coeffs:
            if exponent > other.degree:
                newcoeffs.append(coeff)            
            else:
                newcoeffs.append(coeff + other.coeffs[-(exponent+1)])
            exponent = exponent - 1        
        return Poly(newcoeffs)

    def __neg__(self):
        """
        Return negative of polynomial
        """
        newcoeffs = map(lambda x: -x, self.coeffs)
        return Poly(newcoeffs)

    def __sub__(self,other):
        """
        Subtract a polynomial from self
        """
        return self + (-other)

    def __mul__(self, other):
        """
        Multiply self and other polynomial
        """
        if type(other) == type(3):
            other = Poly([other])
        newpoly = Poly([0])
        for c1 in range(len(self.coeffs)):
            newcoeffs = [0]*(self.degree + other.degree + 1)
            for c2 in range(len(other.coeffs)):
                newcoeffs[c1+c2]=self.coeffs[c1]*other.coeffs[c2]
            newpoly = newpoly + Poly(newcoeffs)
        return newpoly
    
    def __rmul__(self, other):
        """
        Multiply other polynomial and self
        """
        return self * other
    
    def __radd__(self, other):
        """
        Add other polynomial and self
        """
        return self + other
    
    def __rsub__(self, other):
        """
        Subtract other polynomial and self
        """
        return other + (-self)

    def __pow__(self, other):
        """
        Raise self to a power
        """
        if type(other) == type(3):
            newpoly = Poly([1])
            for i in range(other):
                newpoly = newpoly * self
            return newpoly
        else:
            raise TypeError

    def compose(self, other):
        """
	Compose self with other
	"""
        if type(other) == type(3):
           other = Poly([other])
	if type(other) != type(self):
	   raise TypeError
	newpoly = Poly([0])
        exponent = self.degree            
        for coeff in self.coeffs:
            if coeff:
	       newpoly = newpoly + coeff * other**exponent
            exponent = exponent - 1
	return newpoly