#Copyright 2015 B. Johan G. Svensson
#Licensed under the terms of the MIT license (see LICENSE).

'''
#Generic methods and wrappers
removeunused() Polynom only
copy()
degree()
iszero()
neg()          Polynom only

#getcoeff/setcoeff - normally only for internal use
getcoeff(n)
setcoeff(n, val)

#Four basic arithmetic operations:
add(other)
sub(other)
mul(other)
div(other) - returns (quotient, remainder)

#Special functions - external use only:
divprintstep(other)          Polybinary only
divprintstep2(other)         Polybinary only
getfibonaccileftshftpoly()   Polybinary only
getfibonaccirightshftpoly()  Polybinary only
getgaloisleftshftpoly()      Polybinary only
getgaloisrightshftpoly()     Polybinary only

#Display function used by __repren__(self)
repren()
'''


class Polynom(object):
    #YOU are responsible that the coefficients work!
    def __init__(self, inpt):
        self.coeff = list(inpt)
        self.removeunused()
    ########
    #Generic methods and wrappers
    def removeunused(self):
        for i in xrange(len(self.coeff)-1,-1,-1):
            if self.coeff[i] == 0:
                self.coeff.pop()
            else:
                break
    def copy(self):
        return Polynom(self.coeff[:])
    def degree(self):
        self.removeunused()
        deg = len(self.coeff) - 1
        if deg >= 0:
            return deg
        else:
            # Wikipedia says -Inf is 'convenient' http://en.wikipedia.org/wiki/Degree_of_a_polynomial#Degree_of_the_zero_polynomial
            return -float('infinity')
    def iszero(self):
        for coeff in self.coeff:
            if coeff != 0:
                return False
        return True
    def neg(self):
        return Polynom([0]).sub(self)
    ########
    #getcoeff/setcoeff - normally only only used by add, sub, mul, div
    def getcoeff(self,n):
        try:
            return self.coeff[n]
        except IndexError:
            return 0
    def setcoeff(self,n, val):
        try:
            self.coeff[n] = val
        except IndexError:
            if val != 0:
                self.coeff.extend([0] * (1 + n - len(self.coeff)))
                self.coeff[n] = val
    ########
    #Four basic arithmetic operations:
    def add(self, other):
        if isinstance(other, (int, long, float)):
            other = Polynom([other])
        maxdeg = max(self.degree(), other.degree())
        newpoly = []
        for i in xrange(maxdeg + 1):
            newpoly.append(self.getcoeff(i)+other.getcoeff(i))
        return Polynom(newpoly)
    def sub(self, other):
        if isinstance(other, (int, long, float)):
            other = Polynom([other])
        maxdeg = max(self.degree(), other.degree())
        newpoly = []
        for i in xrange(maxdeg + 1):
            newpoly.append(self.getcoeff(i)-other.getcoeff(i))
        return Polynom(newpoly)
    def mul(self, other):
        if isinstance(other, (int, long, float)):
            other = Polynom([other])
        newdegree = self.degree() + other.degree()
        newpoly = [0]*(newdegree + 1)
        for i in xrange(self.degree() + 1):
            for j in xrange(other.degree() + 1):
                newpoly[i+j] += self.getcoeff(i)*other.getcoeff(j)
        return Polynom(newpoly)
    def div(self, other):
        if other.iszero():
            raise ZeroDivisionError
        q = Polynom([0])
        r = self.copy()
        d = other.copy()
        while not(r.iszero()) and r.degree() >= d.degree():
            deg = r.degree() - d.degree()
            coef = r.getcoeff(r.degree())/d.getcoeff(d.degree())
            tlst = [0] * (1 + deg)
            tlst[-1] = coef
            t = Polynom(tlst)
            q += t
            r -= t.mul(d)
        return (q, r)
    ########
    #Special functions - external use only:
    def divprintstep(self, other):
        if other.iszero():
            raise ZeroDivisionError
        q = Polynom([0])
        r = self.copy()
        d = other.copy()
        print 'Printing long division:'
        print '=',r
        while not(r.iszero()) and r.degree() >= d.degree():
            deg = r.degree() - d.degree()
            coef = r.getcoeff(r.degree())/d.getcoeff(d.degree())
            tlst = [0] * (1 + deg)
            tlst[-1] = coef
            t = Polynom(tlst)
            q += t
            r -= t.mul(d)
            print '',t.mul(d), ' = ', t, ' * (', d, ')'
            print '--------'
            print '=',r
        return (q, r)
    ########
    #Display function used by __repr__(self)
    def repren(self):
        strng = ''
        coefflst = []
        for i in xrange(len(self.coeff)-1,-1,-1):
            #
            if self.coeff[i] == 0:
                continue
            #
            if i == len(self.coeff) - 1 and self.coeff[i] >= 0:
                strsign = ''
            elif self.coeff[i] < 0:
                strsign = '-'
            else:
                strsign = '+'
            #
            if i == 0 or abs(self.coeff[i]) != 1:
                strcoeff = str(abs(self.coeff[i]))
            else:
                strcoeff = ''
            #
            if i == 0:
                strx = ''
            elif i == 1:
                strx = 'x'
            else:
                strx = 'x**' + str(i)               
            if len(strng) > 0:
                strng += ' '
            if len(strsign) > 0:
                strng += strsign + ' '
            if len(strcoeff) > 0 and len(strx) > 0:
                strng += strcoeff + ' * ' + strx
            else:
                strng += strcoeff + strx
        if len(strng) == 0:
            strng = '0'
        return strng
    ################
    ####Operator methods
    #Basic customization
    def __repr__(self):
        return self.repren()
##    def __str__(self):
##        return ''
##    def __unicode__(self):
##        return u''
##    def __lt__(self, other):
##        return NotImplemented
##    def __le__(self, other):
##        return NotImplemented
##    def __eq__(self, other):
##        return NotImplemented
##    def __ne__(self, other):
##        return NotImplemented
##    def __gt__(self, other):
##        return NotImplemented
##    def __ge__(self, other):
##        return NotImplemented
##    def __hash__(self):
##        return None
##    def __nonzero__(self):
##        return True

    #Customizing attribute access
##    def __getattr__(self, name):
##        return NotImplemented
##    def __setattr__(self, name, value):
##        return NotImplemented
##    def __delattr__(self, name):
##        return NotImplemented
##    def __getattribute__(self, name):
##        return NotImplemented
##    def __get__(self, instance, owner):
##        return NotImplemented
##    def __set__(self, instance, value):
##        return NotImplemented
##    def __delete__(self, instance):
##        return NotImplemented

    #Emulating callable objects
##    def __call__(self, *args):
##        pass

    #Emulating container types
##    def __len__(self):
##        pass
##    def __getitem__(self, key):
##        pass
##    def __setitem__(self, key, value):
##        pass
##    def __delitem__(self, key):
##        pass
##    def __iter__(self):
##        pass
##    def __reversed__(self):
##        pass
##    def __contains__(self, item):
##        pass
    #Additional methods for emulation of sequence types
    #DEPRECATED since version 2.0 - __getitem__, __setitem__ and __delitem__ above
##    def __getslice__(self, i, j):
##        pass
##    def __setslice__(self, i, j, sequence):
##        pass
##    def __delslice__(self, i, j):
##        pass

    #Emulating numeric types
    def __add__(self, other):
        return self.add(other)
    def __sub__(self, other):
        return self.sub(other)
    def __mul__(self, other):
        return self.mul(other)
    def __floordiv__(self, other):
        return self.div(other)[0]
    def __mod__(self, other):
        return self.div(other)[1]
    def __divmod__(self, other):
        return self.div(other)
##    def __pow__(self, other, modulo = None):
##        return NotImplemented
##    def __lshift__(self, other):
##        return NotImplemented
##    def __rshift__(self, other):
##        return NotImplemented
##    def __and__(self, other):
##        return NotImplemented
##    def __xor__(self, other):
##        return NotImplemented
##    def __or__(self, other):
##        return NotImplemented
    def __div__(self, other):
        return self.div(other)[0]
    def __truediv__(self, other):
        return self.div(other)[0]
    def __radd__(self, other):
        try:
            return other.add(self)
        except AttributeError:
            return Polynom([other]).add(self)
    def __rsub__(self, other):
        try:
            return other.sub(self)
        except AttributeError:
            return Polynom([other]).sub(self)
    def __rmul__(self, other):
        try:
            return other.mul(self)
        except AttributeError:
            return Polynom([other]).mul(self)
    def __rdiv__(self, other):
        #other / self
        try:
            return other.div(self)[0]
        except AttributeError:
            return Polynom([other]).div(self)[0]
    def __rtruediv__(self, other):
        try:
            return other.div(self)[0]
        except AttributeError:
            return Polynom([other]).div(self)[0]
    def __rfloordiv__(self, other):
        try:
            return other.div(self)[0]
        except AttributeError:
            return Polynom([other]).div(self)[0]
    def __rmod__(self, other):
        try:
            return other.div(self)[1]
        except AttributeError:
            return Polynom([other]).div(self)[1]
    def __rdivmod__(self, other):
        try:
            return other.div(self)
        except AttributeError:
            return Polynom([other]).div(self)
##    def __rpow__(self, other):
##        return NotImplemented
##    def __rlshift__(self, other):
##        return NotImplemented
##    def __rrshift__(self, other):
##        return NotImplemented
##    def __rand__(self, other):
##        return NotImplemented
##    def __rxor__(self, other):
##        return NotImplemented
##    def __ror__(self, other):
##        return NotImplemented
    #Correct behavour of i-methods - Modify self and return the result
    #If not possible do not define these - will be handled automatically
##    def __iadd__(self, other):
##        return NotImplemented
##    def __isub__(self, other):
##        return NotImplemented
##    def __imul__(self, other):
##        return NotImplemented
##    def __idiv__(self, other):
##        return NotImplemented
##    def __itruediv__(self, other):
##        return NotImplemented
##    def __ifloordiv__(self, other):
##        return NotImplemented
##    def __imod__(self, other):
##        return NotImplemented
##    def __ipow__(self, other, modulo = None):
##        return NotImplemented
##    def __ilshift__(self, other):
##        return NotImplemented
##    def __irshift__(self, other):
##        return NotImplemented
##    def __iand__(self, other):
##        return NotImplemented
##    def __ixor__(self, other):
##        return NotImplemented
##    def __ior__(self, other):
##        return NotImplemented
    def __neg__(self):
        return Polynom([0]) - self
    def __pos__(self):
        return self.copy()
##    def __abs__(self):
##        pass
##    def __invert__(self):
##        pass
##    def __complex__(self):
##        pass
##    def __int__(self):
##        pass
##    def __long__(self):
##        pass
##    def __float__(self):
##        pass
##    def __oct__(self):
##        pass
##    def __hex__(self):
##        pass
##    def __index__(self):
##        pass
##    def __coerce__(self, other):
##        pass

    #With Statement Context Managers
##    def __enter__(self):
##        pass
##    def __exit__(self, exc_type, exc_value, traceback):
##        pass
